Computer Chess Club Archives


Search

Terms

Messages

Subject: unique distance relationship

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.17 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.