25,161
edits
Changes
Created page with "'''Home * Chess * Squares * Manhattan-Distance''' FILE:Manhattan Voronoi Diagram.png|border|right|thumb|Manhattan-Distance [https://en.wikipedia.org/w..."
'''[[Main Page|Home]] * [[Chess]] * [[Squares]] * Manhattan-Distance'''
[[FILE:Manhattan Voronoi Diagram.png|border|right|thumb|Manhattan-Distance [https://en.wikipedia.org/wiki/Voronoi_diagram Voronoi Diagram] <ref>Voronoi Diagram, named after [[Mathematician#Voronoy|Georgy Voronoy]], using Manhattan distance metric, by user: Raincomplex, November 06, 2013, [https://en.wikipedia.org/wiki/Voronoi_diagram Voronoi diagram from Wikipedia]</ref> ]]
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 [[Distance|Chebyshev Distance]], which may be shorter due to diagonal moves. Manhattan-Distance and Distance are equal for squares on a common [[Files|file]] or [[Ranks|rank]].
The underlying metric what has become known as [https://en.wikipedia.org/wiki/Taxicab_geometry taxicab geometry] was first proposed as a means of creating a [https://en.wikipedia.org/wiki/Non-Euclidean_geometry non-Euclidean geometry] by [[Mathematician#Minkowski|Hermann Minkowski]] early in the 20th century <ref>[[Mathematician#Minkowski|Hermann Minkowski]], [[Mathematician#ASpeiser|Andreas Speiser]], [[Mathematician#Weyl|Hermann Weyl]], [[Mathematician#Hilbert|David Hilbert]] ('''1911'''). ''Gesammelte Abhandlungen von Hermann Minkowski''. [http://www.worldcat.org/title/gesammelte-abhandlungen-von-hermann-minkowski-vol-1-2/oclc/750691126?referer=di&ht=edition republished] by [http://www.ams.org/bookstore/chelsea Chelsea Publishing Co.], New York, 1967</ref>. In 1952, [[Mathematician#KMenger|Karl Menger]] created a geometry exhibit at the [https://en.wikipedia.org/wiki/Museum_of_Science_and_Industry_%28Chicago%29 Museum of Science and Industry] in [https://en.wikipedia.org/wiki/Chicago Chicago]. Menger also created a booklet entitled ''You Will Like Geometry'' <ref> [[Mathematician#KMenger|Karl Menger]] ('''1952'''). ''You Will Like Geometry''. Guidebook of the [https://en.wikipedia.org/wiki/Illinois_Institute_of_Technology Illinois Institute of Technology] Geometry Exhibit, [https://en.wikipedia.org/wiki/Museum_of_Science_and_Industry_%28Chicago%29 Museum of Science and Industry], Chicago, Illinois</ref> <ref>[http://science.iit.edu/applied-mathematics/about/about-karl-menger Louise Golland] ('''1990'''). ''Karl Menger and Taxicap Geomery''. [https://en.wikipedia.org/wiki/Mathematics_Magazine Mathematics Magazine], Vol. 63. No. 5,[http://taxicabgeometry.net/docs/mirror/Golland.pdf pdf]</ref>. It was in this booklet that the term "taxicab geometry" was first used <ref>[http://taxicabgeometry.net/general/history.html Taxicab Geometry - History]</ref>.
=Definition=
The Manhattan-Distance is the sum of the absolute [[Ranks#RankDistance|rank-distance]] and [[Files#FileDistance|file-distance]] of both squares.
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 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|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 [[Cpp|C++]] treated as integers anyway. One should use the [[Avoiding Branches#Abs|abs]] function for a likely branchless implementation.
<pre>
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;
}
</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 arrManhattanDistance[64][64]; // 4 KByte
inline int manhattanDistance(enumSquare sq1, enumSquare sq2) {
return arrManhattanDistance[sq1][sq2];
}
</pre>
=Lookup by 0x88 Difference=
The [[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]], Manhattan-Distance and [[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 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)];
}
</pre>
=See also=
* [[0x88#SquareRelations|0x88 Square Relations]]
* [[Center Distance]]
* [[Center Manhattan-Distance]]
* [[Direction]]
* [[Distance]]
* [[KBNK Endgame]]
* [[King Pawn Tropism]]
* [[Knight-Distance]]
* [[Mop-up evaluation]]
=Forum Posts=
* [https://www.stmintz.com/ccc/index.php?id=245611 unique distance relationship] by [[Gerd Isenberg]], [[CCC]], August 15, 2002
=External Links=
* [https://en.wikipedia.org/wiki/Taxicab_geometry Manhattan-Distance from Wikipedia]
* [http://taxicabgeometry.net/index.html Taxicab Geometry - Home]
: [http://taxicabgeometry.net/general/history.html Taxicab Geometry - History]
* [https://en.wikipedia.org/wiki/Von_Neumann_neighborhood Von Neumann neighborhood from Wikipedia]
* [https://en.wikipedia.org/wiki/CAB_%28band%29 CAB] - Decisions, [https://en.wikipedia.org/wiki/Tony_MacAlpine Tony MacAlpine], [https://en.wikipedia.org/wiki/Bunny_Brunel Bunny Brunel], [[Videos#DennisChambers|Dennis Chambers]], [[Videos#BrianAuger|Brian Auger]], [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=LNDyLyXAR18|alignment=left|valignment=top}}
* [https://en.wikipedia.org/wiki/CAB_%28band%29 CAB live], [https://en.wikipedia.org/wiki/Tony_MacAlpine Tony MacAlpine], [https://en.wikipedia.org/wiki/Bunny_Brunel Bunny Brunel], [https://en.wikipedia.org/wiki/Virgil_Donati Virgil Donati], [https://en.wikipedia.org/wiki/Patrice_Rushen Patrice Rushen], [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=bBYmFIET7fg|alignment=left|valignment=top}}
=References=
<references />
'''[[Squares|Up one Level]]'''
[[FILE:Manhattan Voronoi Diagram.png|border|right|thumb|Manhattan-Distance [https://en.wikipedia.org/wiki/Voronoi_diagram Voronoi Diagram] <ref>Voronoi Diagram, named after [[Mathematician#Voronoy|Georgy Voronoy]], using Manhattan distance metric, by user: Raincomplex, November 06, 2013, [https://en.wikipedia.org/wiki/Voronoi_diagram Voronoi diagram from Wikipedia]</ref> ]]
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 [[Distance|Chebyshev Distance]], which may be shorter due to diagonal moves. Manhattan-Distance and Distance are equal for squares on a common [[Files|file]] or [[Ranks|rank]].
The underlying metric what has become known as [https://en.wikipedia.org/wiki/Taxicab_geometry taxicab geometry] was first proposed as a means of creating a [https://en.wikipedia.org/wiki/Non-Euclidean_geometry non-Euclidean geometry] by [[Mathematician#Minkowski|Hermann Minkowski]] early in the 20th century <ref>[[Mathematician#Minkowski|Hermann Minkowski]], [[Mathematician#ASpeiser|Andreas Speiser]], [[Mathematician#Weyl|Hermann Weyl]], [[Mathematician#Hilbert|David Hilbert]] ('''1911'''). ''Gesammelte Abhandlungen von Hermann Minkowski''. [http://www.worldcat.org/title/gesammelte-abhandlungen-von-hermann-minkowski-vol-1-2/oclc/750691126?referer=di&ht=edition republished] by [http://www.ams.org/bookstore/chelsea Chelsea Publishing Co.], New York, 1967</ref>. In 1952, [[Mathematician#KMenger|Karl Menger]] created a geometry exhibit at the [https://en.wikipedia.org/wiki/Museum_of_Science_and_Industry_%28Chicago%29 Museum of Science and Industry] in [https://en.wikipedia.org/wiki/Chicago Chicago]. Menger also created a booklet entitled ''You Will Like Geometry'' <ref> [[Mathematician#KMenger|Karl Menger]] ('''1952'''). ''You Will Like Geometry''. Guidebook of the [https://en.wikipedia.org/wiki/Illinois_Institute_of_Technology Illinois Institute of Technology] Geometry Exhibit, [https://en.wikipedia.org/wiki/Museum_of_Science_and_Industry_%28Chicago%29 Museum of Science and Industry], Chicago, Illinois</ref> <ref>[http://science.iit.edu/applied-mathematics/about/about-karl-menger Louise Golland] ('''1990'''). ''Karl Menger and Taxicap Geomery''. [https://en.wikipedia.org/wiki/Mathematics_Magazine Mathematics Magazine], Vol. 63. No. 5,[http://taxicabgeometry.net/docs/mirror/Golland.pdf pdf]</ref>. It was in this booklet that the term "taxicab geometry" was first used <ref>[http://taxicabgeometry.net/general/history.html Taxicab Geometry - History]</ref>.
=Definition=
The Manhattan-Distance is the sum of the absolute [[Ranks#RankDistance|rank-distance]] and [[Files#FileDistance|file-distance]] of both squares.
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 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|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 [[Cpp|C++]] treated as integers anyway. One should use the [[Avoiding Branches#Abs|abs]] function for a likely branchless implementation.
<pre>
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;
}
</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 arrManhattanDistance[64][64]; // 4 KByte
inline int manhattanDistance(enumSquare sq1, enumSquare sq2) {
return arrManhattanDistance[sq1][sq2];
}
</pre>
=Lookup by 0x88 Difference=
The [[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]], Manhattan-Distance and [[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 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)];
}
</pre>
=See also=
* [[0x88#SquareRelations|0x88 Square Relations]]
* [[Center Distance]]
* [[Center Manhattan-Distance]]
* [[Direction]]
* [[Distance]]
* [[KBNK Endgame]]
* [[King Pawn Tropism]]
* [[Knight-Distance]]
* [[Mop-up evaluation]]
=Forum Posts=
* [https://www.stmintz.com/ccc/index.php?id=245611 unique distance relationship] by [[Gerd Isenberg]], [[CCC]], August 15, 2002
=External Links=
* [https://en.wikipedia.org/wiki/Taxicab_geometry Manhattan-Distance from Wikipedia]
* [http://taxicabgeometry.net/index.html Taxicab Geometry - Home]
: [http://taxicabgeometry.net/general/history.html Taxicab Geometry - History]
* [https://en.wikipedia.org/wiki/Von_Neumann_neighborhood Von Neumann neighborhood from Wikipedia]
* [https://en.wikipedia.org/wiki/CAB_%28band%29 CAB] - Decisions, [https://en.wikipedia.org/wiki/Tony_MacAlpine Tony MacAlpine], [https://en.wikipedia.org/wiki/Bunny_Brunel Bunny Brunel], [[Videos#DennisChambers|Dennis Chambers]], [[Videos#BrianAuger|Brian Auger]], [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=LNDyLyXAR18|alignment=left|valignment=top}}
* [https://en.wikipedia.org/wiki/CAB_%28band%29 CAB live], [https://en.wikipedia.org/wiki/Tony_MacAlpine Tony MacAlpine], [https://en.wikipedia.org/wiki/Bunny_Brunel Bunny Brunel], [https://en.wikipedia.org/wiki/Virgil_Donati Virgil Donati], [https://en.wikipedia.org/wiki/Patrice_Rushen Patrice Rushen], [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=bBYmFIET7fg|alignment=left|valignment=top}}
=References=
<references />
'''[[Squares|Up one Level]]'''
