Transposition Tables

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
User avatar
cms271828
Posts: 316
Joined: Wed Apr 12, 2006 8:47 pm

Transposition Tables

Post by cms271828 » Sun Jul 15, 2007 4:36 pm

Hi, I posted a while ago about my plan to incorporate TTs into my engine and I was requested to make sure I have castling and en-passant complete, which I have now done.

During the MAKE_MOVE process I will be creating the key for the position.

So I will be using an array:

Code: Select all

long[][] zobrist=new long[12][64];
And do the obvious XORing for general moves.

How should I include in the key:
a) Side to move
b) Castling Rights (2 different positions could look same, but have different castling rights)
c) En-passent capturable pawns

Thanks for any input.
Colin

User avatar
Zach Wegner
Posts: 1922
Joined: Wed Mar 08, 2006 11:51 pm
Location: Earth
Contact:

Re: Transposition Tables

Post by Zach Wegner » Sun Jul 15, 2007 5:30 pm

Simple. Just add a few more arrays. In my engine I have:

Code: Select all

HASHKEY zobrist_piece[2][6][64];
HASHKEY zobrist_castle[16];
HASHKEY zobrist_ep[64];
HASHKEY zobrist_stm;
You could safely change zobrist_ep to 8 elements indexed by file, but I didn't bother. Castling is indexed by the 4-bit number discussed previously.

Zach

User avatar
cms271828
Posts: 316
Joined: Wed Apr 12, 2006 8:47 pm

Re: Transposition Tables

Post by cms271828 » Sun Jul 15, 2007 6:25 pm

Thanks can you give an example, I don't fully understand it.
Thanks :D
Colin

User avatar
Zach Wegner
Posts: 1922
Joined: Wed Mar 08, 2006 11:51 pm
Location: Earth
Contact:

Re: Transposition Tables

Post by Zach Wegner » Sun Jul 15, 2007 7:59 pm

For castling you xor out the previous zobrist and xor in the new one, like this:

Code: Select all

board.hashkey ^= zobrist_castle[board.castle_rights];
board.castle_rights &= castle_rights_mask[from] & castle_rights_mask[to];
board.hashkey ^= zobrist_castle[board.castle_rights];
Then when there is an ep capture possible you xor in the relevant zobrist, and xor it out the next move:

Code: Select all

board.hashkey ^= zobrist_ep[board.ep_square];
Then every time the side to move changes xor in the side to move zobrist:

Code: Select all

board.hashkey ^= zobrist_stm;
As an example here's my hashkey initialization code:

Code: Select all

void initialize_hashkey(void)
{
    BITBOARD pieces;
    SQUARE square;

    board.hashkey = (HASHKEY)0;
    board.pawn_hash_entry.hashkey = (HASHKEY)0;
    pieces = board.occupied_bb;
    while (pieces)
    {
        square = first_square(pieces);
        CLEAR_BIT(pieces, square);

        board.hashkey ^= zobrist_piece[board.color[square]][board.piece[square]][square];
        if (board.piece[square] == PAWN)
            board.pawn_hash_entry.hashkey ^= zobrist_piece[board.color[square]][PAWN][square];
    }
    if (board.side_tm == BLACK)
        board.hashkey ^= zobrist_stm;
    board.hashkey ^= zobrist_castle[board.castle_rights];
    board.hashkey ^= zobrist_ep[board.ep_square];
}
Zach

User avatar
hgm
Posts: 23718
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Transposition Tables

Post by hgm » Sun Jul 15, 2007 8:56 pm

I just use multiplications for these additional key component:

TotalKey = XORPart + CONST1 * CastlingRights + CONST2 * epSquare + CONST3 * stm;

with some large random constants.

Only the XORPart is updated differentially. The stm and the epSquare are instantaneous contributions, incorporated at the moment the key is used. In principle, the CastlingRights could be handled differentially, each time a right changes. But as the rights d not only change by castling, but also by moving kings or rooks, this was too much of a hassle.

wgarvin
Posts: 838
Joined: Thu Jul 05, 2007 3:03 pm
Location: British Columbia, Canada

Re: Transposition Tables

Post by wgarvin » Mon Jul 16, 2007 7:05 pm

By the way... You might want to use 64 bits for Zobrist keys.

I think conventional wisdom is that 32 bits is not enough to avoid collisions (where two different chess positions end up producing the same Zobrist key).

However with 64 bits and sufficiently random numbers in your tables, the chance of a collision like that is so incredibly small that you can pretty much ignore the possibility. (You might prefer to make sure your engine won't actually crash if it happens, but producing a wrong result would be fine because it will probably never happen).

If you index into your TT using N bits from the Zobrist key, the chance of two arbitrary positions wanting to fit into the same table entry is 1 / 2^N. This is kind of large. So you would want to store at least (64-N) bits from the Zobrist key in your TT entry -- for maximum safety, all of the bits not used to index into the TT should be stored in there. (The simplest thing to do is store the whole Zobrist key, though that wastes some bits). Then you only have the (extremely small) 1 in 2^64 chance of confusing the two positions.

User avatar
hgm
Posts: 23718
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Transposition Tables

Post by hgm » Mon Jul 16, 2007 8:53 pm

Well, in practice storing 32 bits in the hash entry as signature, in stead of 64-N, is also sufficient (provided a collission can't crash your engine).

With current TT sizes N is easily 22-24, so you would only lose 8-10 bits. And 54 bits is still large enough to make the probability for a key collission negligible. (If you generate 16M keys per second, you would have a collission every 4 billion seconds. And a collission is almost always without effect on the root move / score.)

jwes
Posts: 778
Joined: Sat Jul 01, 2006 5:11 am

Re: Transposition Tables

Post by jwes » Tue Jul 17, 2007 7:35 am

hgm wrote:Well, in practice storing 32 bits in the hash entry as signature, in stead of 64-N, is also sufficient (provided a collission can't crash your engine).

With current TT sizes N is easily 22-24, so you would only lose 8-10 bits. And 54 bits is still large enough to make the probability for a key collission negligible. (If you generate 16M keys per second, you would have a collission every 4 billion seconds. And a collission is almost always without effect on the root move / score.)
The probability you give is that of a collision with one particular key. The probability of any two keys matching is much higher. (If you generate 16M keys per second, you would have a collision about every 10 seconds. See http://en.wikipedia.org/wiki/Birthday_paradox for details)

Uri Blass
Posts: 8586
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: Transposition Tables

Post by Uri Blass » Tue Jul 17, 2007 8:15 am

jwes wrote:
hgm wrote:Well, in practice storing 32 bits in the hash entry as signature, in stead of 64-N, is also sufficient (provided a collission can't crash your engine).

With current TT sizes N is easily 22-24, so you would only lose 8-10 bits. And 54 bits is still large enough to make the probability for a key collission negligible. (If you generate 16M keys per second, you would have a collission every 4 billion seconds. And a collission is almost always without effect on the root move / score.)
The probability you give is that of a collision with one particular key. The probability of any two keys matching is much higher. (If you generate 16M keys per second, you would have a collision about every 10 seconds. See http://en.wikipedia.org/wiki/Birthday_paradox for details)
It is not a practical problem based on the assumption that
"a collission is almost always without effect on the root move / score"

Uri

User avatar
hgm
Posts: 23718
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Transposition Tables

Post by hgm » Tue Jul 17, 2007 9:23 am

Wesley is right, though: the 1 in 4 billion (2^32) is the error rate per access, not per second.

The maximum rate at which I could do (randomly distributed) memory reads is more like 4M per second, though. So you would expect a key collission every 1000 seconds.

But if it does not happen on a node of the PV, or very close to it, the seach will simply steer away from it. In practice you benifit much more from the larger number of entries you can afford in the same amount of memory by shrinking the signature, than that the occasional error would harm you. Even if you would lose 1 in a 1000 games because of a collission, that would only amount to 0.35 Elo points (assuming that otherwise you woul have scored on the average a draw).

In my measurements a speed doubling (supposed to gain ~50-70 Elo)resulted from expanding the hash by a factor 2^12, so that is about 5 Elo points per doubling. So saving 5% on the size of an entry would gain you 0.35 Elo (1.05^14 = 2). And saving 4 byte on a 20-byte entry is 20%...

Post Reply