ManhattanDistance
Home * Chess * Squares * Manhattan-Distance
[ Manhattan-Distance Voronoi Diagram [1] 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].
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.
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:
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:
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
CAB - Decisions, Tony MacAlpine, Bunny Brunel, Dennis Chambers, Brian Auger, YouTube Video
CAB live, Tony MacAlpine, Bunny Brunel, Virgil Donati, Patrice Rushen, 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