Jan 11, 2007

[Guide] Zobrist keys

Before starting to work with the transposition table (which will be represented as a hash table, more about that later) we need yet another way of representing the position on the board.

We will be using a routine called Zobrist keys for this.

Why another representation?

With Zobrist keys implemented we will have three ways of representing the board in Mediocre. A Board-object, a FEN-string and a Zobrist key.

Each of these serves a special purpose:

The Board-object is the main structure used by the program. Not only does it hold the position but it generates moves, makes moves, and more. We can not really use this for any sort of indexing or comparing without many slow operations.

FEN-strings are mainly used for user interaction (inserting and outputting positions), although I have used them for draw detection and history storage up until now they are not suited for this since they can not be hashed or updated easily. As pointed out to me the FEN-string method currently takes about 35% of the cpu time, this is due to the repetition detection and it proves how very bad the FEN-strings are for this.

Zobrist keys will be used in the transpositions table and for repetition detection. Since a Zobrist key only is a bunch of numbers we can not use them to describe a position to the user.

But since every position has its own unique bunch of numbers, they can be used to compare and store positions with a very high efficiency.

They are perfectly suited for hashing since every change in the position generates a completely different set of numbers. A FEN-string for example would look almost the same after a move which could cause collisions in the hash table. (more on this when I explain transposition tables).

They are also easy to update so we do not have to generate a whole new key every time we make a move. More about this below.

How to create a Zobrist key

A Zobrist key is a 64 bit number that represents a position on the board. In Java the 'long' type is 64 bits (8 bytes) so that is what we will be using.

64 bits is enough to create a unique enough value for every position. I say unique enough because it is not really unique, there are so many positions in chess that even a 64 bit number can not represent them all. There will be occassions when two different positions get the same value, but this is so rare that we do not have to worry about it.

First we need a structure that we will fill with randomly generated numbers. The structure I am using looks like this:
long[6][2][120] PIECES    // [piece type][side to move][square]
long[4] W_CASTLING_RIGHTS // Four different castling setups
long[4] B_CASTLING_RIGHTS // both ways, short, long and none
long[120] EN_PASSANT // En passant
long SIDE // Used for changing sides
Then we fill every spot with a random number. Like this:
Random rnd = new Random();

SIDE = rnd.nextLong();

for(int i = 0; i < 4; i++)
{
W_CASTLING_RIGHTS[i] = rnd.nextLong();
B_CASTLING_RIGHTS[i] = rnd.nextLong();
}
And similar for PIECES and EN_PASSANT. While EN_PASSANT really can only occur on 16 squares (as mentioned earlier), since I do these two in the same loop I might as well fill random numbers for all real squares. Just easier that way.

So now we have a bunch of arrays with random numbers. Great, so what?

The trick is if we have a random number and XOR (explained below) another random number, we get a third seemingly random number. By XORing all random numbers from pieces, en passant and castling rights we get a unique key for the position.

This is done something like this:
long zobristKey = 0;

for(int index = 0; index < 120; index++)
{
int piece = board.boardArray[index];
if(piece > 0) // White piece
zobristKey ^= PIECES[Math.abs(piece)-1][0][index];
else if(piece < 0) // Black piece
zobristKey ^= PIECES[Math.abs(piece)-1][1][index];
}

zobristKey ^= W_CASTLING_RIGHTS[board.white_castle];
zobristKey ^= B_CASTLING_RIGHTS[board.black_castle];

if(board.enPassant != -1) zobristKey ^= EN_PASSANT[board.enPassant];
if(board.toMove == -1) zobristKey ^= SIDE;
We need to distinguish white to move and black to move, since they are two different positions even if all pieces, castling rights and en passant are the same. We do this by XORing the SIDE number, this only has to be done if black is to move, else we use the first number we get.

The ^= operator XORs the random number from the array into the zobristKey. The XOR (exclusive OR) is a bitwise operator just like the & (OR) operator explained earlier. But instead of setting a the bit to 1 if either of the bits are 1, it sets it to 1 only if one of the bits is 1.
1 & 1 = 1
1 & 0 = 1
0 & 0 = 0
1 ^ 1 = 0
1 ^ 0 = 1
0 ^ 0 = 0
We really do not have to know this, all we need to know is if we XOR the number a with b we get a third number c.

But the real trick is if we do the XOR operation again we get the initial number back.
a ^ b = c
c ^ b = a
This is in practice with Zobrist keys used to remove pieces on the board. More in the next section.

Anyway, after doing all these operations we now have our unique 64 bit number that represents our position.

Updating the key

Let us say we have a Zobrist key for a position and we want to make white move 'Ra2a3'. We obviously do this with the makeMove()-method in the Board-class, but we can add lines there looking something like this:
zobristKey ^= Zobrist.PIECES[3][0][16];
zobristKey ^= Zobrist.PIECES[3][0][32];
The first line XORs the random number we have for [rook][white][index], since we already had a white rook on index 16 this will 'remove' it and then we insert a new rook on index 32 with the next line.

And similarly when unmaking the move.

If we do this for every move, and castling/en passant changes. We will always have an updated zobrist key for the position.

Showing what we get

Here is an example of creating and updating a Zobrist key.

I am going to take the start position, generate a Zobrist key, then make the move, look at the new key and unmake the move to make sure we get the first key back.

Also I will manually change the Zobrist key to see that it works the same way as making the move.

The code:
board.setupStart();

System.out.println(Zobrist.getZobristKey(board));

board.makeMove(move); // Making the move 'a2a4'
System.out.println(Zobrist.getZobristKey(board));
board.unmakeMove(move);
System.out.println(Zobrist.getZobristKey(board));

System.out.println("---");

System.out.println(Zobrist.getZobristKey(board));
long key = Zobrist.getZobristKey(board);
key ^= Zobrist.PIECES[5][0][16];
key ^= Zobrist.PIECES[5][0][48];

System.out.println(key);

key ^= Zobrist.PIECES[5][0][48];
key ^= Zobrist.PIECES[5][0][16];

System.out.println(key);
The result is this:
2809723212531837306 // Inital position
6377746370581267278 // After a2a4
2809723212531837306 // Initial position (should be same)
---
2809723212531837306 // Initial position (should be same)
4051561200414578875 // After manually inputting a2a4
2809723212531837306 // Initial position (should be same)
Notice how we in both cases get back to the inital key.

We get a different key after 'a2a4' in the both cases. This is because I have not considered side to move changing and the en passant square. If I XOR these manually as well we will get the same number.

If we exit the program and rerun the exact same code we would get different numbers, since they are generated randomly at startup. This of course expected, and as long as we use the same random numbers during the search the engine will always recognize the positions. Though if we changed the random numbers in the middle of the search the engine would get confused.

Here is another example showing that different move sequences lead to the same key.
board.setupStart();

key = Zobrist.getZobristKey(board);
key ^= Zobrist.PIECES[5][0][16]; // Making the move a2a4
key ^= Zobrist.PIECES[5][0][48];

key ^= Zobrist.PIECES[5][0][17]; // Making the move b2b4
key ^= Zobrist.PIECES[5][0][49];

System.out.println(key);

board.setupStart();

key = Zobrist.getZobristKey(board);
key ^= Zobrist.PIECES[5][0][17]; // Making the move b2b4 first
key ^= Zobrist.PIECES[5][0][49];

key ^= Zobrist.PIECES[5][0][16]; // Then a2a4
key ^= Zobrist.PIECES[5][0][48];

System.out.println(key);
The output will be something like:
4594401896990620738
4594401896990620738
So we reach the same key with different move orders. This is called a transposition and I will discuss this in my next post.

This turned out to be a rather long post about an easy subject. You really do not have to understand everything about XORing, just consider it as magic and it will work. :)

5 comments:

Anonymous said...

hmmm nice like try it on my own engine....

Paulo Santos said...

Regarding Zobrist keys, you said they were "good enough" because there could not represent the whole possibility of a chess board due the fact that it comprises a 64 bit hash key.

However, I did the math computing every possible combination [ C(n,r) = n! / (r! * (n-r)!) ] for all the 64 squares and from 32 to 2 board pieces, and sum it up...

It has enough space, with room to spare.

The sum of all possible piece positions (illegal and otherwise) from a full set of 32 down to 2 pieces on the board is staggering 8,307,059,966,383,480,476.

Which is simply 0x73489B06D827DE9C.

And even if we add the 1 piece positions (64) and the empty board, we still have 9,005,222,773,500,922,751 slots available.

Jonatan Pettersson said...

Hello Paulo,

You fail to take permutations into consideration.

Let's say we have only the two kings on the board. With C(n,r) we would get:

C(64,2) =
64! / (2!*/(64-2)!) = 2016

This is the number of ways we can pick two squares out of the 64.

However the kings are unique, white king on A1 and black king on A2 is not the same as black king on A1 and white on A2.

Instead we have to use permutations, like this:

64! / 62! = 4032

Where 64 is the number of squares, and the we divide away the 62 permutations of the empty squares.

As you can see (and as could be expected) the number doubles since for every position with C, we can also swap the two kings.

Let's say we have two kings and a pawn. With C we get:

C(64,3) = 41664

Considering permutations between the pieces we get:

64! / 61! = 249984

And 4 pieces:

C(64,4) = 635376
64! / 60! = 15249024

As you can see your numbers are far far too low, and the more pieces we add the greater the difference.

With all the pieces on the board we would get:

C(64,32) = 1.8*10^18

which is miniscule compared to when we take permutations into account:

64! / 32!*8!*8!*2!*2!*2!*2!*2!*2!
= 5*10^64

Here the 32 is permutations of the empty squares, the two 8's the permutations of white and black pawns, and the 2's the permutations of pi black and white rooks, bishops and knights.

Anonymous said...

This is a really old post, but I figured it's worth a try:
I'm making an othello bot and am looking to integrate a transposition table in order to make use of the MTD(f) algorithm. I'm somewhat confused by your arrays which have 120 positions for the squares... shouldn't 64 be enough?

Jonatan Pettersson said...

Fortunately I get a mail for every comment, so I'll answer comments on very old posts as well. :)

The 120 has to do with the board representation I use. Take a look here:

http://mediocrechess.blogspot.se/2006/12/0x88-representation.html