Author: Eugene Nalimov
Date: 13:53:39 06/13/00
Go up one level in this thread
Combine two approaches -- 0x88 and 10x12. Use 12x16 board, and access board by
board[0x20+square]
(In C/C++ you can define macro for that).
Than in each case you can use more appropriate of 2 methods.
Eugene
On June 13, 2000 at 16:10:05, Christophe Theron wrote:
>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.01 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.