Zobrist Keys

See Mediocre v0.2b

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. :)