Author: Russell Reagan
Date: 23:11:10 12/22/03
Go up one level in this thread
On December 23, 2003 at 01:19:52, Russell Reagan wrote:
>The two most
>efficient representations I'm aware of are bitboards and a 16x16 board, both of
>which allow you to do some clever tricks.
For an explaination on why the 16x16 board representation is one of the most
efficient, I'll repost this message from Christophe Theron (took me a while to
find it, since the search engine isn't working). Bitboards aside, the 0x88 board
representation is an improvement upon a simple 64-element array, and here he
discusses an improvement over 0x88. He writes:
"I have thought about this for a while, and I think the 0x88 elegance is
misleading.
The big alledged advantage of 0x88 is that you just need a single logical
operation in order to tell if a calculated square is inside the board or not:
// 0x88 way:
if (square&0x88) it_is_outside;
else it_is_inside;
(Wow, that's pretty!)
With the other approach, you need a table lookup to tell that the square is not
inside the board:
// 12x12 way:
if (board[square]==-1) it_is_outside;
else it_is_inside;
(Huh, that's ugly!)
So apparently the 0x88 way is the winner, as it takes only a "logical and", when
the other needs a "table lookup" plus a "compare".
However, when does a real chess program need to tell if a square is out of the
board? Mainly when it is generating captures, calculating a sequence of squares
for the move of a sliding piece.
In this case, the program does the following:
* get the original square of the piece
* add to the square the value of a vector (a direction)
* check if the new square is inside the board
* check if the new square is empty
* if it is empty, add the direction again and iterate...
The test "is the new square inside the board" will succeed (the condition is
true) most of the time. So most of the time the program is going to make the
table lookup (get the content of the square in order to check if it is empty).
Even better, with the 0x88 your NEED to make the "out of bounds" test at every
square. With the 12x12 system, you do NOT need to test if the square is out of
bounds. Just get what's in this square, and if it is 0 (empty), you just
iterate.
You can delay the "out of bound" test until you get a non-empty square. At that
time you can test if it is the "out of bound" value, or an opponent piece (which
can be done just with a single logical operation, not two).
* get the original square of the piece
* add to the square the value of a vector (a direction)
* check if the new square is empty
* if it is empty, add the direction again and iterate...
And on the other hand, with both systems you need anyway to test the content of
the board for almost every square you generate.
Bottom line: for the most intensive task a chess program has to do (generate
captures), I think the 0x88 system is actually LESS EFFECTIVE than 12x12 (or
12x10).
Christophe"
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.