Knight-Distance

From Chessprogramming wiki
Jump to: navigation, search

Home * Chess * Squares * Knight-Distance

Samuel Bak - Across [1]

The Knight-Distance between two squares determines the minimal number of moves a Knight needs, to reach one square from the other on the otherwise empty board. Due to its move geometry, the knight changes its square-color, each times it moves. Thus, if squares have different color, the number of moves is odd, otherwise with same square color, even. Smaller distance does not generally imply smaller KnightDistance.

Knight Fill

With bitboards, one may use fill algorithms, to calculate the knight distance by counting the number of fill-cycles until a target set becomes subset of the consecutively expanded knight attacks.

U64 getKnightAttacks(U64 bb) {
   U64 l1 = (bb >> 1) & C64(0x7f7f7f7f7f7f7f7f);
   U64 l2 = (bb >> 2) & C64(0x3f3f3f3f3f3f3f3f);
   U64 r1 = (bb << 1) & C64(0xfefefefefefefefe);
   U64 r2 = (bb << 2) & C64(0xfcfcfcfcfcfcfcfc);
   U64 h1 = l1 | r1;
   U64 h2 = l2 | r2;
   return (h1<<16) | (h1>>16) | (h2<<8) | (h2>>8);
}

// no set should be empty -> assert (b1 != 0 && b2 != 0 )
int calcKnightDistance(U64 b1, U64 b2) {
   int d = 0;
   while ((b1 & b2) == 0) {
      b1 = getKnightAttacks(b1); // as long as sets are disjoint
      d++; // increment distance
   }
   return d;
}

int knightDistance(int a, int b) {
   return calcKnightDistance(C64(1) << a, C64(1) << b);
}

Lookups

One may use this fill-approach to initialize lookup-tables.

By 64 x 64 Lookup

The obvious and likely fastest solution is to go with a 64 times 64 array, which takes 4 KByte containing all possible knight-distances which are in the 0..6 range on a 8 times 8 board.

char arrKnightDistance[64][64]; // 4 KByte, requires some initialization code

int knightDistance(int a, int b) {
   return arrKnightDistance[a][b];
}

By 0x88 Square Relations

Similar to distance or Manhattan-distance, we may use the 0x88 square relation approach for a denser 240 sized array - but there is one minor issue to consider according to diagonal (or anti-diagonal) neighbored squares. Those squares have usually a knight distance of two, but a distance of four from (or to) the four corner squares. Those extra cases have to be considered by some extra conditions.

By Absolute Rank-File Distance

Another alternative is based on a lookup of two 64 element arrays, one is indexed by some absolute 8 x Rank-Distance plus absolute File-Distance, where diagonal neighbors have a unique distance of 9.

const int ndis[64] = { // char
   //  knight-distance
   0, 3, 2, 3, 2, 3, 4, 5,
   3, 2, 1, 2, 3, 4, 3, 4,
   2, 1, 4, 3, 2, 3, 4, 5,
   3, 2, 3, 2, 3, 4, 3, 4,
   2, 3, 2, 3, 4, 3, 4, 5,
   3, 4, 3, 4, 3, 4, 5, 4,
   4, 3, 4, 3, 4, 5, 4, 5,
   5, 4, 5, 4, 5, 4, 5, 6
};

const int corner[64] = { // char
   1, 0, 0, 0, 0, 0, 0, 1,
   0, 0, 0, 0, 0, 0, 0, 0,
   0, 0, 0, 0, 0, 0, 0, 0,
   0, 0, 0, 0, 0, 0, 0, 0,
   0, 0, 0, 0, 0, 0, 0, 0,
   0, 0, 0, 0, 0, 0, 0, 0,
   0, 0, 0, 0, 0, 0, 0, 0,
   1, 0, 0, 0, 0, 0, 0, 1
};

int absRankFileDiff(int a, int b) {
   int rd = (a|7) - (b|7);
   int fd = (a&7) - (b&7);
   return abs(rd) + abs(fd);
}

int knightDistance(int a, int b) {
   int c = absRankFileDiff(a,b);
   int d = ndis[c];
   if (c == 9) d += 2*(corner[a] ^ corner[b]);
   return d;
}

Or without a condition:

int knightDistance(int a, int b) {
   int c = absRankFileDiff(a,b);
   int d = ndis[c] + 2*((c == 9) & (corner[a] ^ corner[b]));
   return d;
}

To avoid further conditions, with the risk of branch miss-predictions up and then, abs as intrinsic is likely implemented based on following code snippet ...

int abs(int a) {
   int s = a >> 31; // cdq, signed shift, -1 if negative, else 0
   a ^= s;  // ones' complement if negative
   a -= s;  // plus one if negative -> two's complement if negative
   return a;
}

... by compilers, on x86 a sequence three instructions: {cdq, xor, sub} or {cdq, add, xor}.

See also

References