Manhattan-Distance

Home * Chess * Squares * Manhattan-Distance

Manhattan-Distance Voronoi Diagram

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 . 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 . It was in this booklet that the term "taxicab geometry" was first used .

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

• Manhattan-Distance from Wikipedia
• Taxicab Geometry - Home

Taxicab Geometry - History

• Von Neumann neighborhood from Wikipedia
• 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

Up one Level