Author: Christophe Theron
Date: 13:10:05 06/13/00
Go up one level in this thread
On June 13, 2000 at 13:39:20, Tom Kerrigan wrote:
>On June 13, 2000 at 12:18:34, TEERAPONG TOVIRAT wrote:
>
>>Hi,
>>
>>I have 3 questions.
>>1. Does two level transpositional table have significant
>>advantages over one level table ? If so,how much we
>>gain in % ?
>>
>>2.In board representation,besides bitboard ,which is faster
>>between board 12x10(or 12x12) and board 0x88 ?
>>To generate the move,after obtaining piece and location,
>>the former takes one array look up and one arithmetic
>>operation to get a valid square.On the other hand,the
>>latter takes 2 times table look up(map and unmap)
>>and one arithmetic and one bitwise operation(&0x88) .
>>I think the former is better. Am I right ?
>
>I think this is the code that you're talking about. First, for the 10x12 board:
>
>n = a[b[n] + c]; // 1 add, 2 table lookups
>if (n == -1) // 1 subtract
> break; // 1 branch
>
>And here's the 0x88 code:
>
>n += c; // 1 add
>if (n & 0x88) // 1 logic
> break; // 1 branch
>
>So they're identical, except for the table lookups. The table lookups are what
>kill you though. With today's processors, addition and logic operations are
>basically instantaneous. So the 0x88 approach is much better.
>
>-Tom
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.02 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.