Author: Gerd Isenberg
Date: 02:59:21 12/15/05
Hi,
recently there was the question about a knight-distance formula.
Mungjong pointed out the idea with the 0x88 square difference and a lookup,
while Uri mentioned the edge-cases which require some special handling.
I still have my precalculated 64*64 array with packed distance, taxi-distance,
knight-distance and this udr-value (unique distance relation).
Following branchless code is more ressource friendly - it builds the absolute
file- and rank-difference of two squares (0..63) with a 64-element lookup.
The edge cases are handled branchless via second lookups and boolean
mutiplication via bitwise and of a conditional {0,-1}-mask. You may also try
char arrays for that - and of course 0x88 square metric.
const int edge[64] = {
2, 0, 0, 0, 0, 0, 0, 2,
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,
2, 0, 0, 0, 0, 0, 0, 2
};
const int knightD[64] = {
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
};
int knightDistance(int a, int b) {
int f = (a&7) - (b&7); // file distance
int r = (a>>3) - (b>>3); // rank distance
f = (f + (f>>31)) ^ (f>>31); // abs
r = (r + (r>>31)) ^ (r>>31); // abs
return ((edge[a]+edge[b]) & -(8*r+f == 9)) + knightD[8*r+f];
}
a somehow shorter and faster (msvc 6) but less readable routine with some slight
source modifications:
int knightDistance(int a, int b) {
int f = (a&7) - (b&7);
int m = (int)( (unsigned __int64)((__int64)f) >> 32 );
int r = ( (a - b) >> 3) - m;
f = (f + m) ^ m;
r = (r + (r>>31)) ^ (r>>31);
return ((edge[a]+edge[b]) & -(8*r+f == 9)) + knightD[8*r+f];
}
Comments and improvements appreciated.
Thanks,
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.