Author: Gerd Isenberg
Date: 11:33:52 08/15/02
In IsiChess, as well in other chess programs, two (precomputed) two-dimensional
arrays are used, to get the distance and the taxi-distance between two squares:
int distance[64][64];
int taxidist[64][64];
eg. from square 0 (A1) upper left corner:
distance
0 1 2 3 4 5 6 7
1 1 2 3 4 5 6 7
2 2 2 3 4 5 6 7
3 3 3 3 4 5 6 7
4 4 4 4 4 5 6 7
5 5 5 5 5 5 6 7
6 6 6 6 6 6 6 7
7 7 7 7 7 7 7 7
taxidist
0 1 2 3 4 5 6 7
1 2 3 4 5 6 7 8
2 3 4 5 6 7 8 9
3 4 5 6 7 8 9 10
4 5 6 7 8 9 10 11
5 6 7 8 9 10 11 12
6 7 8 9 10 11 12 13
7 8 9 10 11 12 13 14
If the two squares are on same rank/file both distances are equal.
On the diagonals the taxis (in NY) have the double way to go.
If you want to determine whether there are special distance relationships
between two squares, eg. straight or diagonal adjacent, opposition, some far
oppositions or knight distance, but no matter from what direction, you may
combine both distances (if you don't want to use too many special purpose
arrays):
bool isOpposition(int sq1, int sq2){
return (distance[sq1][sq2] == 2) && (taxidist[sq1][sq2] == 2);}
bool isKnightDistance(int sq1, int sq2){
return (distance[sq1][sq2] == 2) && (taxidist[sq1][sq2] == 3);}
These distance relationships are faster to implement, if you use the
(precomputed) sum of distance and taxi-distance:
eg. combidist[0] = distance[0] + taxidist[0]
0 2 4 6 8 10 12 14
2 3 5 7 5 11 13 15
4 5 6 8 10 12 14 16
6 7 8 9 11 13 15 17
8 9 10 11 12 14 16 18
10 11 12 13 14 15 17 19
12 13 14 15 16 17 18 20
14 15 16 17 18 19 20 21
All combi-distances less than six determine unique relationships, so you can
safely do:
bool isOpposition(int sq1, int sq2) {
return combidist[sq1][sq2] == 4;}
bool isKnightDistance(int sq1, int sq2) {
return combidist[sq1][sq2] == 5;}
Next idea was to use some linear combination of distance and taxi-distance,
to make all distance relationships unique:
eg. combidist71[0] = 7*distance[0] + 1*taxidist[0]
0 8 16 24 32 40 48 56
8 9 17 25 33 41 49 57
16 17 18 26 34 42 50 58
24 25 26 27 35 43 51 59
32 33 34 35 36 44 52 60
40 41 42 43 44 45 53 61
48 49 50 51 52 53 54 62
56 57 58 59 60 61 62 63
As you see, all distance relationships are unique (with respect to
symmetrics)and straight combi71-distances are divisible without remainder by 8,
but the diagonal distances by 9, what is not so efficient to determine.
So the final step was to use a modified 15*distance + taxidist, to get
divisibility of 16 on ranks and files. The modification affects the diagonals,
where i reset bit 0-2 but set bit 3, to force a divisibility of 8.
UDRDist[0]
8 16 32 48 64 80 96 112
16 24 33 49 65 81 97 113
32 33 40 50 66 82 98 114
48 49 50 56 67 83 99 115
64 65 66 67 72 84 100 116
80 81 82 83 84 88 101 117
96 97 98 99 100 101 104 118
112 113 114 115 116 117 118 120
hexadecimal:
x08 x10 x20 x30 x40 x50 x60 x70
x10 x18 x21 x31 x41 x51 x61 x71
x20 x21 x28 x32 x42 x52 x62 x72
x30 x31 x32 x38 x43 x53 x63 x73
x40 x41 x42 x43 x48 x54 x64 x74
x50 x51 x52 x53 x54 x58 x65 x75
x60 x61 x62 x63 x64 x65 x68 x76
x70 x71 x72 x73 x74 x75 x76 x78
There is stil a unique distance relationship, but also some more usefull
information whether the two squares are on a common line or diagonal:
If the three LSBs are zero (divisible by 8 without remainder), both squares are
on a common line or diagonal. If the lowest Nibble is zero (divisible by 16
without remainder), both squares are on the same rank or file.
IMHO the UDRDist-Array allows efficient recognization of direction independend
distance relations between two squares, like same line or diagonal, adjacent,
opposition, knight-distance and so on.
Gerd
This page took 0.01 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.