25,161
edits
Changes
Created page with "'''Home * Chess * Squares * Distance''' FILE:Colors_from_a_Distance.jpg|border|right|thumb|link=https://artsandculture.google.com/asset/colors-from-a-..."
'''[[Main Page|Home]] * [[Chess]] * [[Squares]] * Distance'''
[[FILE:Colors_from_a_Distance.jpg|border|right|thumb|link=https://artsandculture.google.com/asset/colors-from-a-distance/kAHBsV7-F_nsQw|[[Arts#Klee|Paul Klee]] - Colors from a Distance <ref>[[Arts#Klee|Paul Klee]] - [https://artsandculture.google.com/asset/colors-from-a-distance/kAHBsV7-F_nsQw Colors from a Distance], 1932, [https://en.wikipedia.org/wiki/Israel_Museum The Israel Museum], [https://en.wikipedia.org/wiki/Google_Arts_%26_Culture Google Arts & Culture]</ref> ]]
The term '''Distance''' refers to the minimal number of [[Moves|moves]] a certain [[Pieces|piece]], which resides on the first square, needs, to reach the second square. The so called [https://en.wikipedia.org/wiki/Chebyshev_distance Chebyshev distance] is the minimal number of [[King|king]] moves between those squares on the otherwise empty board. The so called [[Manhattan-Distance|Manhattan- or Taxi-distance]] is restricted to orthogonal king moves, while [[Knight-Distance|knight-distance]] refers to [[Knight|knight]] moves. In a wider sense, distance can be interpreted as a generalization of [[Mobility|mobility]], for instance determined by [[Fill Algorithms|fill algorithms]] in [[Bitboards|bitboards]].
=Chebyshev Distance=
The Chebyshev distance is the maximum of the absolute [[Ranks#RankDistance|rank-]] and [[Files#FileDistance|file-distance]] of both squares.
D = max(|r<span style="vertical-align: sub;">2</span> - r<span style="vertical-align: sub;">1</span>|, |f<span style="vertical-align: sub;">2</span> - f<span style="vertical-align: sub;">1</span>|)
while the orthogonal [[Manhattan-Distance]] is the sum of both absolute rank- and file-distance distances.
D<span style="vertical-align: sub;">taxi</span> = |r<span style="vertical-align: sub;">2</span> - r<span style="vertical-align: sub;">1</span>| + |f<span style="vertical-align: sub;">2</span> - f<span style="vertical-align: sub;">1</span>|
* 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 [[Cpp|C++]] treated as integers anyway. One should use the [[Avoiding Branches#Abs|abs]] and [[Avoiding Branches#Max|max]] functions for likely branchless implementations.
<pre>
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);
}
</pre>
==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:
<pre>
unsigned char arrDistance[64][64]; // 4 KByte
inline int distance(enumSquare sq1, enumSquare sq2) {
return arrDistance[sq1][sq2];
}
</pre>
==Lookup by 0x88 Difference==
[[Vector Attacks|Vector attacks]] like [[0x88]] [[0x88#SquareRelations|square relation]] permits a denser lookup approach. The difference of valid 0x88 coordinates of two squares is uniquely with respect to distance and [[Direction|direction]]. That way, one can greatly reduce the size of the lookup [[Array|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:
<pre>
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)];
}
</pre>
<span id="15x15"></span>
==Lookup of Array 15*15==
An approach with a 225 element table for king move distance, as well for other piece move distances, [[Direction|directions]], [[Vector Attacks#Superimposition|vector attacks]] and [[Vector Attacks#IncrementVectors|increment vectors]], was used in [[Pioneer]] as described by [[Boris Stilman]] <ref>[[Boris Stilman]] ('''1994'''). ''A Linguistic Geometry of the Chess Model''. [[Advances in Computer Chess 7]], [http://www.stilman-strategies.com/bstilman/boris_papers/Jour94_CHESS7.pdf pdf draft]</ref>. The [[8x8 Board|8x8 array]] is [https://en.wikipedia.org/wiki/Superimposition 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:
<pre>
╔════╤════╤════╤════╤════╤════╤════╤════╤════╤════╤════╤════╤════╤════╤════╗
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
</pre>
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|evaluation]] of the late [[Endgame|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 [[Trajectory|trajectories]] for a king moving from f6 to h1 <ref>[[Boris Stilman]] ('''1994'''). ''A Linguistic Geometry of the Chess Model''. [[Advances in Computer Chess 7]], [http://www.stilman-strategies.com/bstilman/boris_papers/Jour94_CHESS7.pdf pdf draft]</ref>:
<pre>
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
</pre>
=The Value of Reaching a Square=
Distance as generalization of [[Mobility|mobility]] and [[Evaluation|evaluation]] term was introduced by [[Robert Levinson]] and [[Richard Snyder]] in the famous 1993 [[ICGA Journal#16_3|ICCA Journal, Vol. 16, No. 3]] <ref>[[Robert Levinson]], [[Richard Snyder]] ('''1993'''). ''Distance: Toward the Unification of Chess Knowledge''. [[ICGA Journal#16_3|ICCA Journal, Vol. 16, No. 3]]</ref> . 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 [[Knowledge|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 [[Pieces|piece's]] [[Mobility|mobility]] graph to determine what is close to and what is close to it. From a Distance standpoint, [[Moves|moves]] on the [[Chessboard|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#SquareRelations|0x88 Square Relations]]
* [[Center Distance]]
* [[Center Manhattan-Distance]]
* [[Connectivity]]
* [[Direction]]
* [[Fill Algorithms]]
* [[Influence Quantity of Pieces]]
* [[King Pawn Tropism]]
* [[King Safety#KingTropism|King Piece Tropism]]
* [[Knight-Distance]]
* [[Manhattan-Distance]]
* [[Mobility]]
* [[Vector Attacks]]
=Publications=
* [[Robert Levinson]], [[Richard Snyder]] ('''1993'''). ''Distance: Toward the Unification of Chess Knowledge''. [[ICGA Journal#16_3|ICCA Journal, Vol. 16, No. 3]] » [[WCCC 1992#Workshop|WCCC 1992 - Workshop]]
* [[Boris Stilman]] ('''1994'''). ''A Linguistic Geometry of the Chess Model''. [[Advances in Computer Chess 7]], [http://www.stilman-strategies.com/bstilman/boris_papers/Jour94_CHESS7.pdf pdf draft]
* [[Daniel Michulke]], [[Stephan Schiffel]] ('''2012'''). ''Distance Features for General Game Playing Agents''. [http://www.informatik.uni-trier.de/~ley/db/conf/icaart/icaart2012-1.html#MichulkeS12 4. ICAART 2012], [http://www.general-game-playing.de/downloads/GIGA11_Distance_Features.pdf pdf] » [[General Game Playing]]
=Forum Posts=
* [https://www.stmintz.com/ccc/index.php?id=245611 unique distance relationship] by [[Gerd Isenberg]], [[CCC]], August 15, 2002
* [http://www.talkchess.com/forum/viewtopic.php?t=31571 Distance to King] by [[Adam Berent]], [[CCC]], January 08, 2010 » [[King Safety#KingTropism|King Piece Tropism]]
=External Links=
* [https://en.wikipedia.org/wiki/Chebyshev_distance Chebyshev distance from Wikipedia]
* [https://en.wikipedia.org/wiki/Distance Distance (Proximity) from Wikipedia]
* [https://en.wikipedia.org/wiki/Euclidean_distance Euclidean distance from Wikipedia]
* [https://en.wikipedia.org/wiki/Manhattan_distance Manhattan distance from Wikipedia]
* [https://en.wikipedia.org/wiki/Minkowski_distance Minkowski distance from Wikipedia]
* [https://en.wikipedia.org/wiki/Moore_neighborhood Moore neighborhood from Wikipedia]
* [https://en.wikipedia.org/wiki/Von_Neumann_neighborhood Von Neumann neighborhood from Wikipedia]
* [https://en.wikipedia.org/wiki/Proxemics Proxemics from Wikipedia]
* [[Videos#Yes|Yes]] - [https://en.wikipedia.org/wiki/Long_Distance_Runaround Long Distance Runaround], [https://en.wikipedia.org/wiki/Fragile_%28Yes_album%29 Fragile] (1971), [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: [https://en.wikipedia.org/wiki/Jon_Anderson Jon Anderson], [https://en.wikipedia.org/wiki/Steve_Howe_%28musician%29 Steve Howe], [[Videos#ChrisSquire|Chris Squire]], [https://en.wikipedia.org/wiki/Rick_Wakeman Rick Wakeman], [[Videos#BillBruford|Bill Bruford]]
: {{#evu:https://www.youtube.com/watch?v=82iy5Bu19Bs|alignment=left|valignment=top}}
=References=
<references />
'''[[Squares|Up one Level]]'''
[[FILE:Colors_from_a_Distance.jpg|border|right|thumb|link=https://artsandculture.google.com/asset/colors-from-a-distance/kAHBsV7-F_nsQw|[[Arts#Klee|Paul Klee]] - Colors from a Distance <ref>[[Arts#Klee|Paul Klee]] - [https://artsandculture.google.com/asset/colors-from-a-distance/kAHBsV7-F_nsQw Colors from a Distance], 1932, [https://en.wikipedia.org/wiki/Israel_Museum The Israel Museum], [https://en.wikipedia.org/wiki/Google_Arts_%26_Culture Google Arts & Culture]</ref> ]]
The term '''Distance''' refers to the minimal number of [[Moves|moves]] a certain [[Pieces|piece]], which resides on the first square, needs, to reach the second square. The so called [https://en.wikipedia.org/wiki/Chebyshev_distance Chebyshev distance] is the minimal number of [[King|king]] moves between those squares on the otherwise empty board. The so called [[Manhattan-Distance|Manhattan- or Taxi-distance]] is restricted to orthogonal king moves, while [[Knight-Distance|knight-distance]] refers to [[Knight|knight]] moves. In a wider sense, distance can be interpreted as a generalization of [[Mobility|mobility]], for instance determined by [[Fill Algorithms|fill algorithms]] in [[Bitboards|bitboards]].
=Chebyshev Distance=
The Chebyshev distance is the maximum of the absolute [[Ranks#RankDistance|rank-]] and [[Files#FileDistance|file-distance]] of both squares.
D = max(|r<span style="vertical-align: sub;">2</span> - r<span style="vertical-align: sub;">1</span>|, |f<span style="vertical-align: sub;">2</span> - f<span style="vertical-align: sub;">1</span>|)
while the orthogonal [[Manhattan-Distance]] is the sum of both absolute rank- and file-distance distances.
D<span style="vertical-align: sub;">taxi</span> = |r<span style="vertical-align: sub;">2</span> - r<span style="vertical-align: sub;">1</span>| + |f<span style="vertical-align: sub;">2</span> - f<span style="vertical-align: sub;">1</span>|
* 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 [[Cpp|C++]] treated as integers anyway. One should use the [[Avoiding Branches#Abs|abs]] and [[Avoiding Branches#Max|max]] functions for likely branchless implementations.
<pre>
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);
}
</pre>
==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:
<pre>
unsigned char arrDistance[64][64]; // 4 KByte
inline int distance(enumSquare sq1, enumSquare sq2) {
return arrDistance[sq1][sq2];
}
</pre>
==Lookup by 0x88 Difference==
[[Vector Attacks|Vector attacks]] like [[0x88]] [[0x88#SquareRelations|square relation]] permits a denser lookup approach. The difference of valid 0x88 coordinates of two squares is uniquely with respect to distance and [[Direction|direction]]. That way, one can greatly reduce the size of the lookup [[Array|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:
<pre>
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)];
}
</pre>
<span id="15x15"></span>
==Lookup of Array 15*15==
An approach with a 225 element table for king move distance, as well for other piece move distances, [[Direction|directions]], [[Vector Attacks#Superimposition|vector attacks]] and [[Vector Attacks#IncrementVectors|increment vectors]], was used in [[Pioneer]] as described by [[Boris Stilman]] <ref>[[Boris Stilman]] ('''1994'''). ''A Linguistic Geometry of the Chess Model''. [[Advances in Computer Chess 7]], [http://www.stilman-strategies.com/bstilman/boris_papers/Jour94_CHESS7.pdf pdf draft]</ref>. The [[8x8 Board|8x8 array]] is [https://en.wikipedia.org/wiki/Superimposition 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:
<pre>
╔════╤════╤════╤════╤════╤════╤════╤════╤════╤════╤════╤════╤════╤════╤════╗
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
</pre>
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|evaluation]] of the late [[Endgame|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 [[Trajectory|trajectories]] for a king moving from f6 to h1 <ref>[[Boris Stilman]] ('''1994'''). ''A Linguistic Geometry of the Chess Model''. [[Advances in Computer Chess 7]], [http://www.stilman-strategies.com/bstilman/boris_papers/Jour94_CHESS7.pdf pdf draft]</ref>:
<pre>
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
</pre>
=The Value of Reaching a Square=
Distance as generalization of [[Mobility|mobility]] and [[Evaluation|evaluation]] term was introduced by [[Robert Levinson]] and [[Richard Snyder]] in the famous 1993 [[ICGA Journal#16_3|ICCA Journal, Vol. 16, No. 3]] <ref>[[Robert Levinson]], [[Richard Snyder]] ('''1993'''). ''Distance: Toward the Unification of Chess Knowledge''. [[ICGA Journal#16_3|ICCA Journal, Vol. 16, No. 3]]</ref> . 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 [[Knowledge|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 [[Pieces|piece's]] [[Mobility|mobility]] graph to determine what is close to and what is close to it. From a Distance standpoint, [[Moves|moves]] on the [[Chessboard|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#SquareRelations|0x88 Square Relations]]
* [[Center Distance]]
* [[Center Manhattan-Distance]]
* [[Connectivity]]
* [[Direction]]
* [[Fill Algorithms]]
* [[Influence Quantity of Pieces]]
* [[King Pawn Tropism]]
* [[King Safety#KingTropism|King Piece Tropism]]
* [[Knight-Distance]]
* [[Manhattan-Distance]]
* [[Mobility]]
* [[Vector Attacks]]
=Publications=
* [[Robert Levinson]], [[Richard Snyder]] ('''1993'''). ''Distance: Toward the Unification of Chess Knowledge''. [[ICGA Journal#16_3|ICCA Journal, Vol. 16, No. 3]] » [[WCCC 1992#Workshop|WCCC 1992 - Workshop]]
* [[Boris Stilman]] ('''1994'''). ''A Linguistic Geometry of the Chess Model''. [[Advances in Computer Chess 7]], [http://www.stilman-strategies.com/bstilman/boris_papers/Jour94_CHESS7.pdf pdf draft]
* [[Daniel Michulke]], [[Stephan Schiffel]] ('''2012'''). ''Distance Features for General Game Playing Agents''. [http://www.informatik.uni-trier.de/~ley/db/conf/icaart/icaart2012-1.html#MichulkeS12 4. ICAART 2012], [http://www.general-game-playing.de/downloads/GIGA11_Distance_Features.pdf pdf] » [[General Game Playing]]
=Forum Posts=
* [https://www.stmintz.com/ccc/index.php?id=245611 unique distance relationship] by [[Gerd Isenberg]], [[CCC]], August 15, 2002
* [http://www.talkchess.com/forum/viewtopic.php?t=31571 Distance to King] by [[Adam Berent]], [[CCC]], January 08, 2010 » [[King Safety#KingTropism|King Piece Tropism]]
=External Links=
* [https://en.wikipedia.org/wiki/Chebyshev_distance Chebyshev distance from Wikipedia]
* [https://en.wikipedia.org/wiki/Distance Distance (Proximity) from Wikipedia]
* [https://en.wikipedia.org/wiki/Euclidean_distance Euclidean distance from Wikipedia]
* [https://en.wikipedia.org/wiki/Manhattan_distance Manhattan distance from Wikipedia]
* [https://en.wikipedia.org/wiki/Minkowski_distance Minkowski distance from Wikipedia]
* [https://en.wikipedia.org/wiki/Moore_neighborhood Moore neighborhood from Wikipedia]
* [https://en.wikipedia.org/wiki/Von_Neumann_neighborhood Von Neumann neighborhood from Wikipedia]
* [https://en.wikipedia.org/wiki/Proxemics Proxemics from Wikipedia]
* [[Videos#Yes|Yes]] - [https://en.wikipedia.org/wiki/Long_Distance_Runaround Long Distance Runaround], [https://en.wikipedia.org/wiki/Fragile_%28Yes_album%29 Fragile] (1971), [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: [https://en.wikipedia.org/wiki/Jon_Anderson Jon Anderson], [https://en.wikipedia.org/wiki/Steve_Howe_%28musician%29 Steve Howe], [[Videos#ChrisSquire|Chris Squire]], [https://en.wikipedia.org/wiki/Rick_Wakeman Rick Wakeman], [[Videos#BillBruford|Bill Bruford]]
: {{#evu:https://www.youtube.com/watch?v=82iy5Bu19Bs|alignment=left|valignment=top}}
=References=
<references />
'''[[Squares|Up one Level]]'''
