Author: Bruce Moreland
Date: 18:09:11 03/05/99
Go up one level in this thread
On March 05, 1999 at 18:42:51, Matt wrote:
>I am familiar with the basic concept of the 0x88 board representation, but I
>have not been able to find a more in depth study of it anywhere. I was
>wondering if anybody could direct me towards a good paper on it, or perhaps some
>C source code of a chess engine using 0x88?
>Thank you
>Matt
I don't think it's been written up anywhere official.
The idea is that you make a 128-element board. a1 is 0, b1 is 1, ..., h1 is 7,
then there are 8 un-used squares, and then a2 is 16, etc.
The reason you waste the space is so that there will be a spare bit in the
middle of the board index.
You can regard an index into a 64-bit board as a pair of 3-bit indexes stuck
next to each other, the low-order three bits are the file, and the high-order
three bits are the rank. With a 128-element board, you end up with a 3-bit
file, a blank bit, then a 3-bit rank.
If you have an index, and are adding to or subtracting from it, in order to get
to a square that is related in the way that a chess piece moves, this blank bit
will serve as a carry or borrow bit if you go off the left or right side of the
board.
For instance, you can loop through the moves of any piece as follows:
for (;; index += delta) {
if (index & 0x88)
break;
....
}
The 0x80 part will catch cases where you go off the top or bottom of the board,
and the 0x08 part will catch the cases where you go off the left or right side.
This keeps you from having to have a row of sentinels around the edges of your
board, and also keeps you from having to keep distinct rank and file values, or
other nastiness like that.
It ends up being pretty easy to code a move generator using this scheme.
Another advantage of the 128-element board is that you can subtract the indexes
of any two squares in order to exactly determine the relationship between them.
In a 64-element board, if you subtract d1 from e1, you get 1, but if you
subtract h1 from a2 you also get 1, even though the two squares don't have the
same relationship to each other.
In a 128-element board, if you subtract d1 from e1 you'll still get 1, but if
you subtract h1 from a2 you'll get 9, which makes sense because a2 is not one
square to the right of h1.
This holds true of any relationship between any two squares. You can make use
of this to determine if it's possible to get from one square to another square,
in order to build an in-check routine or a static exchange evaluator.
bruce
This page took 0 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.