Distance to King

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
aberent

Distance to King

Post by aberent » Fri Jan 08, 2010 8:08 pm

I have read that some computer chess engines will use the distance to king as a variable in the Evaluation Function.

Does anyone know an efficient way of calculating this distance?

User avatar
hgm
Posts: 23149
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Distance to King

Post by hgm » Fri Jan 08, 2010 8:24 pm

Look it up in a table indexed by (square - kingSquare).

aberent

Re: Distance to King

Post by aberent » Fri Jan 08, 2010 9:12 pm

I am not sure that works for me. I have the board indexed like so:

0 1 2 3 4 5 6 7
8 9 10 11 12 13 14 15
16 17 18 19 20 21 22 23
24 25 26 27 28 29 30 31
32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47
48 49 50 51 52 53 54 55
56 57 58 59 60 61 62 63

So by simply subtracting the values 24 woud be right next to 23 which is not true.

rjgibert
Posts: 306
Joined: Mon Jun 26, 2006 7:44 am

Re: Distance to King

Post by rjgibert » Fri Jan 08, 2010 10:03 pm

For whatever reason, HG was assuming a 0x88 representation where the square difference index works. For more information, see

http://chessprogramming.wikispaces.com/0x88

User avatar
hgm
Posts: 23149
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Distance to King

Post by hgm » Fri Jan 08, 2010 10:04 pm

This is why it is better to use 0x88 numbering:

Code: Select all

00 01 02 03 04 05 06 07
16 17 18 19 20 21 22 23
32 33 34 35 ....
You can convert one into the other by nr0x88 = nrPlain + (nrPlain & 070); or of course use another table lookup for that, nr0x88 = table[nrPlain].

gladius
Posts: 537
Joined: Tue Dec 12, 2006 9:10 am

Re: Distance to King

Post by gladius » Fri Jan 08, 2010 10:37 pm

Well, it depends on what distance you want as well :). The dumb method is still pretty fast for king walk distance:

distance = abs(file(king) - file(piece)) + abs(rank(king) - rank(piece));

Calculating file/rank is trivial:

file = index & 7;
rank = index >> 3;

User avatar
hgm
Posts: 23149
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Distance to King

Post by hgm » Sat Jan 09, 2010 8:27 am

Your King cannot walk diagonally?

Richard Allbert
Posts: 766
Joined: Wed Jul 19, 2006 7:58 am

Re: Distance to King

Post by Richard Allbert » Sat Jan 09, 2010 11:19 am

True, but you can precalculate the table at engine startup using the long way round (shown below) and reference the table when eval is called.

Richard

Vinvin
Posts: 4200
Joined: Thu Mar 09, 2006 8:40 am
Full name: Vincent Lejeune

Re: Distance to King

Post by Vinvin » Sat Jan 09, 2010 2:46 pm

hgm wrote:Your King cannot walk diagonally?
LOL !
I'd say : Max(Abs(FileKingX-FileTargetX) , Abs(FileKingY-FileTargetY)) .

So it's the maximum distance in vertical/horizontal

bob
Posts: 20362
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Distance to King

Post by bob » Sat Jan 09, 2010 5:02 pm

hgm wrote:Look it up in a table indexed by (square - kingSquare).
or

distance = Max( abs(Rank(king) - rank(square)), abs(file(king) - file(square)));

That computes the so-called "taxicab distance" You take the largest of the vertical and horizontal distances.

Post Reply