Using Pre-calculated Random Numbers for Zobrist Hashing

[munchkin]

Newbie Alert!

I've only looked at the source code of a couple of chess engines and they both use randomly-generated random numbers for Zobrist hashing. I came across a random number generator that generates the same list of numbers given the same random seeds for m_z and m_w:

Code: Select all

unsigned int GetUint(void)
{
    m_z = 36969 * (m_z & 65535) + (m_z >> 16);
    m_w = 18000 * (m_w & 65535) + (m_w >> 16);
    return &#40;m_z << 16&#41; + m_w;
&#125;

[Found at: http://www.codeproject.com/Articles/251 ... Generation]


Assuming that you use the same Zobrist keys all the time, it would be possible to rewrite the doZobrist() fun to encode ALL the castling changes in one go, both the King and Rooks moves, using pre-computed values:

Code: Select all

#define ZOB_W_OO_KEY   0x -- some pre-computed value
#define ZOB_W_OOO_KEY  0x...
#define ZOB_B_OO_KEY   0x...
#define ZOB_B_OOO_KEY  0x...

void doZobrist(mv m)
{
...
   if(m.flags & CASTLE_F) // castling move
	  switch(m.to){
	  case G1: ZobristKey ^= ZOB_W_OO_KEY;
		       break;
	  case C1: ZobristKey ^= ZOB_W_OOO_KEY;
		       break;
	  case G8: ZobristKey ^= ZOB_B_OO_KEY;
		       break;
	  case C8: ZobristKey ^= ZOB_B_OOO_KEY;
	  }
   else{ // here we do all the other moves!

    }

Is there any reason not to do this? Also, once you have settled on your Zobrist numbers, couldn't the Zobrist hash also be used as a key for an opening book as well? (If you were using 64-bit Zobrist numbers, then you could choose to use only the lower 32-bits for the opening book; that should suffice.)





// Step 1: Create an effective board representation.

Code: Select all

  _~___--__~~__^__~~__...__
8 \  |  |  /  (  |  /  !   \
7 /  |  !  \  \  |  /  \   /
6 |  <  \  !  |  \  \   <    >
5 (  |  /  \  \  &#125;  /  \   |
4 <  /  /  |  >  &#123;  \  /   /
3 &#91;  &#93;  |  /  \  \  |  |   \
2 |  >  \  |  /  &#93;  \  /  <  >
1 \  |  &#125;  \  /  /  |  \   /
  ---^--``--~~--...--``~~~-
   a   b  c d  e  f   g  h

Computer plays&#58; 1. Ng1i2

[Daniel White]

Newbie Alert!

I've only looked at the source code of a couple of chess engines and they both use randomly-generated random numbers for Zobrist hashing. I came across a random number generator that generates the same list of numbers given the same random seeds for m_z and m_w:

Code: Select all

unsigned int GetUint(void)
{
    m_z = 36969 * (m_z & 65535) + (m_z >> 16);
    m_w = 18000 * (m_w & 65535) + (m_w >> 16);
    return &#40;m_z << 16&#41; + m_w;
&#125;

[Found at: http://www.codeproject.com/Articles/251 ... Generation]


Assuming that you use the same Zobrist keys all the time, it would be possible to rewrite the doZobrist() fun to encode ALL the castling changes in one go, both the King and Rooks moves, using pre-computed values:

Code: Select all

#define ZOB_W_OO_KEY   0x -- some pre-computed value
#define ZOB_W_OOO_KEY  0x...
#define ZOB_B_OO_KEY   0x...
#define ZOB_B_OOO_KEY  0x...

void doZobrist(mv m)
{
...
   if(m.flags & CASTLE_F) // castling move
	  switch(m.to){
	  case G1: ZobristKey ^= ZOB_W_OO_KEY;
		       break;
	  case C1: ZobristKey ^= ZOB_W_OOO_KEY;
		       break;
	  case G8: ZobristKey ^= ZOB_B_OO_KEY;
		       break;
	  case C8: ZobristKey ^= ZOB_B_OOO_KEY;
	  }
   else{ // here we do all the other moves!

    }

Is there any reason not to do this? Also, once you have settled on your Zobrist numbers, couldn't the Zobrist hash also be used as a key for an opening book as well? (If you were using 64-bit Zobrist numbers, then you could choose to use only the lower 32-bits for the opening book; that should suffice.)





// Step 1: Create an effective board representation.

Code: Select all

  _~___--__~~__^__~~__...__
8 \  |  |  /  (  |  /  !   \
7 /  |  !  \  \  |  /  \   /
6 |  <  \  !  |  \  \   <    >
5 (  |  /  \  \  &#125;  /  \   |
4 <  /  /  |  >  &#123;  \  /   /
3 &#91;  &#93;  |  /  \  \  |  |   \
2 |  >  \  |  /  &#93;  \  /  <  >
1 \  |  &#125;  \  /  /  |  \   /
  ---^--``--~~--...--``~~~-
   a   b  c d  e  f   g  h

Computer plays&#58; 1. Ng1i2

I believe some engines use precomputed tables for Zobrist keys rather than generating them at startup. I don't think it makes much difference personally.

As for your code, I think there might be a bug. I don't think you should have separate keys for having castled. Doing this would cause two identical positions, one reached by castling, one reached by moving the king and rook, to have different keys. Clearly this isn't correct as both positions behave the same.

What should be included in the key is whether it is possible to castle for either player on either side. This can be done quite fast if you store castling rights as a 4 bit number (first bit for white kingside, second for white queenside, etc). You then simply XOR the old castling rights (pre-move) with the new castling rights (after making the move) and use this to lookup a 16-element array of keys (this is itself generated from the 4 basic castling keys). If this needs any more explanation don't hesitate to ask.

As for the opening book idea, this is exactly what some people do. You can store the positions in order of increasing hash key and then finding positions can be done using a fast binary search.

[syzygy]

There are engines that have a precomputed hardcoded table of Zobrist keys, and there are engines that compute such a table once during initialisation. As long as the keys are sufficiently random, there is no significant difference.

The method you use for calculating the table has no impact on how you use the table for updating the hashkey. I'm not sure why you think a rewrite of your doZobrist(mv m) function would be needed. (In case you intend to call your random number generator from there: it won't work.)

[munchkin]

As for your code, I think there might be a bug. [...]

Oops! Well spotted. I had forgotten to relocate a line in my code. It should read:

Code: Select all

{
...
   if(m.flags & CASTLE_F) // castling move
     switch(m.to){

      ZobristKey ^= ZobristCastle[castf];

     case G1: ZobristKey ^= ZOB_W_OO_KEY;
             break;
     case C1: ZobristKey ^= ZOB_W_OOO_KEY;
             break;
     case G8: ZobristKey ^= ZOB_B_OO_KEY;
             break;
     case C8: ZobristKey ^= ZOB_B_OOO_KEY;
     }
   else{ // here we do all the other moves!

    }

Just to clarify things: The defined values, such as ZOB_W_OO_KEY, are the pre-calculated values of moving the King and the Rook in the castling move. Essentially:

Code: Select all

ZOB_W_OO_KEY =  ZobristPiece[WHITE][ROOK][H1] ^ ZobristPiece[WHITE][ROOK][F1]
			  ^ ZobristPiece[WHITE][KING][E1] ^ ZobristPiece[WHITE][KING][G1];

As for the opening book idea, this is exactly what some people do. You can store the positions in order of increasing hash key and then finding positions can be done using a fast binary search.

That sounds just about right. I wrote a small program for opening classification some time ago that used this very idea, which is where I got it from. This is another reason why I'd like to use the same Zobrist keys. It also allows you to create any kind of opening book that you'd like, as you have full control over its structure.

But is it common to do this? Or is it more the thing to stick to some standard book format? (for example, to be compatible with some GUI?)

[jdart]

I've used pre-computed Zobrist keys since version 1 of my program, in 1994.

--Jon

[ZirconiumX]

I've used pre-computed Zobrist keys since version 1 of my program, in 1994.

--Jon

Fruit also uses precomputed random numbers, IIRC to make probing Polyglot books quicker.

Matthew:out

[Daniel White]

As for your code, I think there might be a bug. [...]

Oops! Well spotted. I had forgotten to relocate a line in my code. It should read:

Code: Select all

{
...
   if(m.flags & CASTLE_F) // castling move
     switch(m.to){

      ZobristKey ^= ZobristCastle[castf];

     case G1: ZobristKey ^= ZOB_W_OO_KEY;
             break;
     case C1: ZobristKey ^= ZOB_W_OOO_KEY;
             break;
     case G8: ZobristKey ^= ZOB_B_OO_KEY;
             break;
     case C8: ZobristKey ^= ZOB_B_OOO_KEY;
     }
   else{ // here we do all the other moves!

    }

Of course the castling rights can change due to a non-castling move. but I guess in your actual program you've taken care of this.

As for the opening book idea, this is exactly what some people do. You can store the positions in order of increasing hash key and then finding positions can be done using a fast binary search.

That sounds just about right. I wrote a small program for opening classification some time ago that used this very idea, which is where I got it from. This is another reason why I'd like to use the same Zobrist keys. It also allows you to create any kind of opening book that you'd like, as you have full control over its structure.

But is it common to do this? Or is it more the thing to stick to some standard book format? (for example, to be compatible with some GUI?)

This page shows that the polyglot book format uses the method you mention.

[mcostalba]

Fruit also uses precomputed random numbers, IIRC to make probing Polyglot books quicker.

to make probing Polyglot books possible

[munchkin]

Of course the castling rights can change due to a non-castling move. but I guess in your actual program you've taken care of this.

Ah! Yet another possible problem. I do update the castling rights at the bottom of my make(), but, unless I add in the ZobristKey ^= ZobristCastle[castf]; line each time that castf changes, then I suppose I'll end up with an invalid ZobristKey. As you are eluding to, if I simply move the Rook from h1 to g1 and then back to h1, the castling rights may have changed, but unless I include this change in the ZobristKey when the Rook initially moves, then the two positions with the Rook on h1 will look identical so far as the ZobristKey is concerned.

So what is the best way to update the ZobristKey when the castling rights have changed? Do you compare the new castling rights valued against the last copy written into the move history stack?

This page shows that the polyglot book format uses the method you mention.

Thanks very much for the link, it is very much appreciated.

[bpfliegel]

Fruit also uses precomputed random numbers, IIRC to make probing Polyglot books quicker.

to make probing Polyglot books possible