Manhattan-Distance
Home * Chess * Squares * Manhattan-Distance
The Manhattan-Distance between two squares is determined by the minimal number of orthogonal King moves between these squares on the otherwise empty board, also called Taxicab- or Taxi-Distance - opposed to Chebyshev Distance, which may be shorter due to diagonal moves. Manhattan-Distance and Distance are equal for squares on a common file or rank.
The underlying metric what has become known as taxicab geometry was first proposed as a means of creating a non-Euclidean geometry by Hermann Minkowski early in the 20th century [2]. In 1952, Karl Menger created a geometry exhibit at the Museum of Science and Industry in Chicago. Menger also created a booklet entitled You Will Like Geometry [3] [4]. It was in this booklet that the term "taxicab geometry" was first used [5].
Contents
Definition
The Manhattan-Distance is the sum of the absolute rank-distance and file-distance of both squares.
Dtaxi = |r2 - r1| + |f2 - f1|
- The minimum square Manhattan-Distance is 0 (if both squares are equal)
- The maximum square Manhattan-Distance is 14 (between the endpoints of the main-diagonals)
Application
The main application of square Manhattan-Distance (in conjunction with Distance) is the static evaluation of the late endgame, where for instance races of the two king to certain squares is often an issue - or in so called Mop-up evaluation, which considers the Manhattan-Distance between winning and losing king.
Routine
The following C-routine performs the computation. One may use the mentioned square-, rank- or file-enumeration types instead of the used integers, or rely on anonymous enumeration in C or C++ treated as integers anyway. One should use the abs function for a likely branchless implementation.
int manhattanDistance(int sq1, int sq2) { int file1, file2, rank1, rank2; int rankDistance, fileDistance; file1 = sq1 & 7; file2 = sq2 & 7; rank1 = sq1 >> 3; rank2 = sq2 >> 3; rankDistance = abs (rank2 - rank1); fileDistance = abs (file2 - file1); return rankDistance + fileDistance; }
Lookup
Since the computation is relative expensive, often two dimensional tables with precalculated values are used for that purpose. A Byte as lowest addressable unit is more than enough and easily zero extended:
unsigned char arrManhattanDistance[64][64]; // 4 KByte inline int manhattanDistance(enumSquare sq1, enumSquare sq2) { return arrManhattanDistance[sq1][sq2]; }
Lookup by 0x88 Difference
The 0x88 square relation permits a denser lookup approach. The difference of valid 0x88 coordinates of two squares is uniquely with respect to Distance, Manhattan-Distance and Direction. That way, one can greatly reduce the size of the lookup array to only 240 instead of 4096 elements. Some additional computation required, if one has to convert usual square coordinates to 0x88. If one already relies on 0x88 coordinates, it becomes even cheaper:
unsigned char arrManhattanDistanceBy0x88Diff[240]; unsigned int x88diff(enumSquare sq1, enumSquare sq2) { return sq2 - sq1 + (sq2|7) - (sq1|7) + 120; } inline int manhattanDistance(enumSquare sq1, enumSquare sq2) { return arrManhattanDistanceBy0x88Diff[x88diff(sq1, sq2)]; }
See also
- 0x88 Square Relations
- Center Distance
- Center Manhattan-Distance
- Direction
- Distance
- KBNK Endgame
- King Pawn Tropism
- Knight-Distance
- Mop-up Evaluation
Forum Posts
- unique distance relationship by Gerd Isenberg, CCC, August 15, 2002
External Links
- Von Neumann neighborhood from Wikipedia
- CAB - Decisions, Tony MacAlpine, Bunny Brunel, Dennis Chambers, Brian Auger, YouTube Video
References
- ↑ Voronoi Diagram, named after Georgy Voronoy, using Manhattan distance metric, by user: Raincomplex, November 06, 2013, Voronoi diagram from Wikipedia
- ↑ Hermann Minkowski, Andreas Speiser, Hermann Weyl, David Hilbert (1911). Gesammelte Abhandlungen von Hermann Minkowski. republished by Chelsea Publishing Co., New York, 1967
- ↑ Karl Menger (1952). You Will Like Geometry. Guidebook of the Illinois Institute of Technology Geometry Exhibit, Museum of Science and Industry, Chicago, Illinois
- ↑ Louise Golland (1990). Karl Menger and Taxicap Geomery. Mathematics Magazine, Vol. 63. No. 5,pdf
- ↑ Taxicab Geometry - History