Home * Chess * Squares * Distance

		The term distance refers to the minimal number of moves a certain piece, which resides on the first square, needs, to reach the second square. The so called Chebyshev distance is the minimal number of king moves between those squares on the otherwise empty board. The so called Manhattan- or Taxi-distance is restricted to orthogonal king moves, while knight-distance refers to knight moves. In a wider sense, distance can be interpreted as a generalization of mobility, for instance determined by fill algorithms in bitboards.
Paul Klee, Colors from a Distance, 1932 [1]

Chebyshev Distance

The Chebyshev distance is the maximum of the absolute rank- and file-distance of both squares.

• $D = \max \left ( \left | r_2 - r_1 \right | , \left | f_2 - f_1 \right | \right )$

while the orthogonal Manhattan-Distance is the sum of both absolute rank- and file-distance distances.

• $D_{taxi} = \left | r_2 - r_1 \right | + \left | f_2 - f_1 \right |$

• The minimum square Distance is 0 (if both squares are equal)
• The maximum square Distance is 7

while

• The maximum square Manhattan-Distance is 14 (between the endpoints of the main-diagonals)

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 and max functions for likely branchless implementations.

int distance(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 max (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 arrDistance[64][64]; // 4 KByte
 
inline int distance(enumSquare sq1, enumSquare sq2) {
   return arrDistance[sq1][sq2];
}

Lookup by 0x88 Difference

Vector attacks like 0x88 square relation permits a denser lookup approach. The difference of valid 0x88 coordinates of two squares is uniquely with respect to 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 arrDistanceBy0x88Diff[240];
 
unsigned int x88diff(enumSquare sq1, enumSquare sq2) {
   return sq2 - sq1 + (sq2|7) - (sq1|7) + 120;
}
 
inline int distance(enumSquare sq1, enumSquare sq2) {
   return arrDistanceBy0x88Diff[x88diff(sq1, sq2)];
}

Lookup of Array 15*15

An approach with a 225 element table for king move distance, as well for other piece move distances, directions, vector attacks and increment vectors, was used in Pioneer as described by Boris Stilman ^[2]. The 8x8 array is superimposed on the array 15x15 in such a way that square x coincides with the central square (112) of the array 15x15, see the sample with c2:

     ╔════╤════╤════╤════╤════╤════╤════╤════╤════╤════╤════╤════╤════╤════╤════╗
 210 ║  7 |  7 |  7 |  7 |  7 |  7 |  7 |  7 |  7 |  7 |  7 |  7 |  7 |  7 |  7 ║
     ╟────┼────┼────┼────┼────╔════╤════╤════╤════╤════╤════╤════╤════╗────┼────╢
 195 ║  7 |  6 |  6 |  6 |  6 ║  6 |  6 |  6 |  6 |  6 |  6 |  6 |  6 ║  6 |  7 ║
     ╟────┼────┼────┼────┼────╟────┼────┼────┼────┼────┼────┼────┼────╢────┼────╢
 180 ║  7 |  6 |  5 |  5 |  5 ║  5 |  5 |  5 |  5 |  5 |  5 |  5 |  5 ║  6 |  7 ║
     ╟────┼────┼────┼────┼────╟────┼────┼────┼────┼────┼────┼────┼────╢────┼────╢
 165 ║  7 |  6 |  5 |  4 |  4 ║  4 |  4 |  4 |  4 |  4 |  4 |  4 |  5 ║  6 |  7 ║
     ╟────┼────┼────┼────┼────╟────┼────┼────┼────┼────┼────┼────┼────╢────┼────╢
 150 ║  7 |  6 |  5 |  4 |  3 ║  3 |  3 |  3 |  3 |  3 |  3 |  4 |  5 ║  6 |  7 ║
     ╟────┼────┼────┼────┼────╟────┼────┼────┼────┼────┼────┼────┼────╢────┼────╢
 135 ║  7 |  6 |  5 |  4 |  3 ║  2 |  2 |  2 |  2 |  2 |  3 |  4 |  5 ║  6 |  7 ║
     ╟────┼────┼────┼────┼────╟────┼────┼────┼────┼────┼────┼────┼────╢────┼────╢
 120 ║  7 |  6 |  5 |  4 |  3 ║  2 |  1 |  1 |  1 |  2 |  3 |  4 |  5 ║  6 |  7 ║
     ╟────┼────┼────┼────┼────╟────┼────╔════╗────┼────┼────┼────┼────╢────┼────╢
 105 ║  7 |  6 |  5 |  4 |  3 ║  2 |  1 ║  0 ║  1 |  2 |  3 |  4 |  5 ║  6 |  7 ║
     ╟────┼────┼────┼────┼────╟────┼────╚════╝────┼────┼────┼────┼────╢────┼────╢
  90 ║  7 |  6 |  5 |  4 |  3 ║  2 |  1 |  1 |  1 |  2 |  3 |  4 |  5 ║  6 |  7 ║
     ╟────┼────┼────┼────┼────╚════╧════╧════╧════╧════╧════╧════╧════╝────┼────╢
  75 ║  7 |  6 |  5 |  4 |  3 |  2 |  2 |  2 |  2 |  2 |  3 |  4 |  5 |  6 |  7 ║
     ╟────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────╢
  60 ║  7 |  6 |  5 |  4 |  3 |  3 |  3 |  3 |  3 |  3 |  3 |  4 |  5 |  6 |  7 ║
     ╟────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────╢
  45 ║  7 |  6 |  5 |  4 |  4 |  4 |  4 |  4 |  4 |  4 |  4 |  4 |  5 |  6 |  7 ║
     ╟────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────╢
  30 ║  7 |  6 |  5 |  5 |  5 |  5 |  5 |  5 |  5 |  5 |  5 |  5 |  5 |  6 |  7 ║
     ╟────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────╢
  15 ║  7 |  6 |  6 |  6 |  6 |  6 |  6 |  6 |  6 |  6 |  6 |  6 |  6 |  6 |  7 ║
     ╟────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────╢
   0 ║  7 |  7 |  7 |  7 |  7 |  7 |  7 |  7 |  7 |  7 |  7 |  7 |  7 |  7 |  7 ║
     ╚════╧════╧════╧════╧════╧════╧════╧════╧════╧════╧════╧════╧════╧════╧════╝
        0    1    2    3    4    5    6    7    8    9    10   11   12   13   14

The index calculation is trivial as well but slightly more expensive than the 0x88 one. Of course, a small lookup table to map the indices might be appropriate.

Applications

The main application of square distance is the static evaluation of the late endgame, where for instance races of the two kings to certain squares is often an issue - or in so called Mop-up evaluation, which considers the distance between winning and losing king. Boris Stilman gave following example to generate a set of trajectories for a king moving from f6 to h1 ^[3]:

D(f6,K)          +  D(h1,K)          =  SUM                 SUM == D(f6,h1)
5 4 3 2 2 2 2 2     7 7 7 7 7 7 7 7     c b a 9 9 9 9 9     . . . . . . . .
5 4 3 2 1 1 1 2     7 6 6 6 6 6 6 6     c a 9 8 7 7 7 8     . . . . . . . .
5 4 3 2 1 0 1 2     7 6 5 5 5 5 5 5     c a 8 7 6|5|6 7     . . . . . 1 . .
5 4 3 2 1 1 1 2     7 6 5 4 4 4 4 4     c a 8 6|5 5 5|6     . . . . 1 1 1 .
5 4 3 2 2 2 2 2  +  7 6 5 4 3 3 3 3  =  c a 8 6|5 5 5 5|    . . . . 1 1 1 1
5 4 3 3 3 3 3 3     7 6 5 4 3 2 2 2     c a 8 7 6|5 5 5|    . . . . . 1 1 1
5 4 4 4 4 4 4 4     7 6 5 4 3 2 1 1     c a 9 8 7 6|5 5|    . . . . . . 1 1
5 5 5 5 5 5 5 5     7 6 5 4 3 2 1 0     c b a 9 8 7 6|5|    . . . . . . . 1

The Value of Reaching a Square

Distance as generalization of mobility and evaluation term was introduced by Robert Levinson and Richard Snyder in the famous 1993 ICCA Journal, Vol. 16, No. 3 ^[4] . Abstract and excerpt:

This article suggests a new approach to computer chess. A graph-theoretic representation of chess knowledge, uniformly based on a single mathematical abstraction, Distance, is described. Most of the traditional forms of chess knowledge, it is shown, can be formalized in this new representation. In addition to comparing this approach to others, the article gives some experimental results and suggests how the new representation may be unified with existing approaches. The Distance idea is based on exploring a piece's mobility graph to determine what is close to and what is close to it. From a Distance standpoint, moves on the chess-board are only considered good if they result in improved movement graphs for the mover's pieces and/or inferior ones for the opponent's pieces. Often, a good chess-player will move a piece, not to improve the attacking chances of that piece but rather the attacking chances of the piece behind it.

See also

• 0x88 Square Relations
• Center Distance
• Center Manhattan-Distance
• Connectivity
• Direction
• Fill Algorithms
• Influence Quantity of Pieces
• King Pawn Tropism
• King Piece Tropism
• Knight-Distance
• Manhattan-Distance
• Mobility
• Vector Attacks

Publications

• Robert Levinson, Richard Snyder (1993). Distance: Toward the Unification of Chess Knowledge. ICCA Journal, Vol. 16, No. 3 » WCCC 1992 - Workshop
• Boris Stilman (1994). A Linguistic Geometry of the Chess Model. Advances in Computer Chess 7, pdf draft
• Daniel Michulke, Stephan Schiffel (2012). Distance Features for General Game Playing Agents. 4. ICAART 2012, pdf » General Game Playing

Forum Posts

• unique distance relationship by Gerd Isenberg, CCC, August 15, 2002
• Distance to King by Adam Berent, CCC, January 08, 2010 » King Piece Tropism

External Links

• Chebyshev distance from Wikipedia
• Distance (Proximity) from Wikipedia
• Euclidean distance from Wikipedia
• Manhattan distance from Wikipedia
• Minkowski distance from Wikipedia
• Moore neighborhood from Wikipedia
• Von Neumann neighborhood from Wikipedia
• Proxemics from Wikipedia
• Yes - Long Distance Runaround, Fragile (1971), YouTube Video
  Jon Anderson, Steve Howe, Chris Squire, Rick Wakeman, Bill Bruford
  

References

1. ^ IMAGINE - The Israel Museum's searchable collections database
2. ^ Boris Stilman (1994). A Linguistic Geometry of the Chess Model. Advances in Computer Chess 7, pdf draft
3. ^ Boris Stilman (1994). A Linguistic Geometry of the Chess Model. Advances in Computer Chess 7, pdf draft
4. ^ Robert Levinson, Richard Snyder (1993). Distance: Toward the Unification of Chess Knowledge. ICCA Journal, Vol. 16, No. 3

What links here?

Up one Level