Transposition Tables

[cms271828]

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.

[Zach Wegner]

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

[cms271828]

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

[Zach Wegner]

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

[hgm]

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]

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.

[hgm]

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]

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]

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

[hgm]

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%...