Author: Bruce Moreland
Date: 18:26:30 06/14/00
Go up one level in this thread
On June 14, 2000 at 16:21:40, James Robertson wrote:
>Could someone please point me to a place where I can read about this board
>representation and how to use it? If someone is willing to post a description of
>it here, that would be cool too.
>
>James
Here is yet another try:
0x88 board representation and move generation
It's called something else, but I don't know what it is called. I heard about
it from David Kittinger at the Hong Kong WCCC in 1995, and it's been spreading.
David told me that it was a common technique before that point, but I haven't
seen it described in literature.
The advantages of the technique are that you get simple move generation and you
get easy attack detection. This latter advantage is especially important, and
is probably the major reason for using the technique.
The data structure is a 16 x 8 board, rather than an 8 x 8 board. 0..7 are
a1..h1, then you get 8 empty squares numbered 8..15, then 16..23 are a2..h2,
etc.
The idea is that if you have an index into the board, you can add an offset to
the index to travel along a vector. You can do a simple test to see if you've
gone off the board. The test is "index & 0x88". If that comes back non-zero,
you are off the board. For instance, if you are at h1 (7) and add 1 to go right
one square, you get 8, which has one of our 0x88 bits set. If you are at a2
(16) and go left (-1), you get 15, which has the same bit set. If you go off
the top or bottom of the board, you also get one of those two bits set in every
case.
You can't use an 8 x 8 board to do this, because right one from h1 gets you to
a2, which is on the board. It only works if you go off the bottom or top of the
board, but it doesn't work with left or right.
Your critical test in your move generation loop is something like:
if ((location += offset) & 0x88)
This is easier than having to try to manage rank and file variables and trying
to figure out if you've gone off the board in one direction or the other, and
it's also more elegant than several other obvious techniques.
The other advantage of 0x88 is attack detection. If you want to know if e4 (52)
is one square above and to the right of d3 (35) you subtract the indexes to get
17. It is a feature of this kind of board representation that if you get 17
when you subtract two indexes, you are always one square up and to the right.
This is not true on an 8 x 8 board. e4 (28) - d3 (19) = 9, but 9 doesn't always
mean one square up and to the right. For example, if you relate a3 (16) and h1
(7), you get 9, but a3 is certainly not one square above and to the right of h1.
You can use the fact that in a 16 x 8 board, 17 means one squre up and to the
right, to do quick attack detection.
You can make an array (256 elements works nicely but you need a few fewer) of
bit-fields. You can have a white pawn be 0x1, a black pawn be 0x2, and knight
be 0x4, a bishop be 0x8, etc., and fill in the array (-127..127) with the
appropriate masks that indicate a possible attack by a piece of one type, on a
given square, of another square.
For instance, in the element for +34, which is two squares up and two to the
right, you could have the value "queen|bishop". If you have a queen on f3 (37)
and want to know if it attacks a king on d1 (3), you can subtract 3 from 37, to
get 34, and in the element for +34 you find "queen|bishop", which anded with
"queen" is non-zero, so you know that an an attack is possible.
You can have another array that contains a -17 in position +34, which tells you
how much to add each time to the queen's square (f3) in order to try to get to
the king's square (d1), so for sliding pieces you can very easily determine that
there is a possible vector, and what it is, and start checking the vector for
intervening pieces.
You can use this to easily write a quick in-check routine, or a static-exchange
evaluator (SEE).
I haven't included source code with this example, but the code is easy to write,
and in the past I've included it. There are lots of ways to write it, most of
them are very easy and fast.
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.