Error in hash tables?

[Pedro Castro]

[diag]1r3rk1/pbp1ppbp/1npq2p1/8/3PPB2/5NP1/PPQN1P1P/R4RK1 b - - 7 13[/diag]

In this position, during the game, my program played Rbc8 and it allowed to eat up the queen. However when if I configure the position and I tell to the engine that begins to play, then it makes the play normal Qd8, Qd7 or Qb4. (clean hash)

Do I have a problem with the hash tables? It can be that my aleatory number is not enough it, I use the aleatory number that gives Bruce Moreland in its page.

static U64 U64Rand(void)
{
return (U64)rand() ^ ((U64)rand() << 15) ^ ((U64)rand() << 30) ^ ((U64)rand() << 45) ^ ((U64)rand() << 60);
}

This is not the only time that has happened me this, I believe that it happens me in a bigger percentage to 1%, although it is not habitual that the error is so serious, here I realized for the graveness of being left the queen.

When I make a null move, I should upgrade the value of the hash?, I see some programs that make it and other no.

Happy new year,

[Sven Schüle]

In this position, during the game, my program played Rbc8 and it allowed to eat up the queen. However when if I configure the position and I tell to the engine that begins to play, then it makes the play normal Qd8, Qd7 or Qb4. (clean hash)

Hi Pedro,

your problem really looks like a hash table problem. I have had this kind of behaviour, too, in early versions of Surprise. To be sure, you might put some "#ifndef NO_HASH ... #endif" pairs around all pieces of code which may be omitted when not using a hash table, and then compile with /DNO_HASH (or -DNO_HASH, depending on your compiler) to see if the bug disappears. Also #ifndef around your hash key and hash table variable declarations and around functions implementing the hash table, to be forced by the compiler not to miss any #ifndef around code using these definitions.

Of course this requires that your problem is reproducible at all, which is not often the case.

You might also disable the hash table by some other mechanism but then you may have difficulties to really isolate the buggy code.

Code: Select all

static U64 U64Rand(void)
{
    return (U64)rand() ^ ((U64)rand() << 15) ^ ((U64)rand() << 30) ^ ((U64)rand() << 45) ^ ((U64)rand() << 60);
}

Looks familiar, but please have a look into <stdlib.h> of your compiler. If RAND_MAX is 0x7fff this seems to be o.k. but for larger values of RAND_MAX (e.g. GNU) I would expect some trouble due to overlapping bits; the quality of your random numbers may be affected.

Perhaps you might use something like this to be more independent from the RAND_MAX value:

Code: Select all

inline U64 U64Rand15(void)
{
    return ((U64) rand()) & (U64) 0x7fff;
}

static U64 U64Rand(void)
{
    return U64Rand15() ^
          (U64Rand15() << 15) ^
          (U64Rand15() << 30) ^
          (U64Rand15() << 45) ^
          (U64Rand15() << 60);
}

When I make a null move, I should upgrade the value of the hash?, I see some programs that make it and other no.

Making the null move changes the side to move, and this should change the hash key. Otherwise you may end up finding a wrong value for the position after a null move because it has the same hash key as the predecessor position where the opponent was to move.

Happy New Year,
Sven

[Daniel Mehrmann]

[...]

Code: Select all

static U64 U64Rand(void)
{
    return (U64)rand() ^ ((U64)rand() << 15) ^ ((U64)rand() << 30) ^ ((U64)rand() << 45) ^ ((U64)rand() << 60);
}


I had some trouble different compilers and overlapping bits too.

I'm using the following code to generate my keys. You can use it too if you want, but you need to ask the original author.

Code: Select all

(just copy & paste)


/* init
 * HashRand() with friendly permission of the author
 * backport for homer ;)
 */
uint32
HashRand(void)
{
/****************************************************************************
 *
 *  A 32 bit random number generator.  An implementation in C of the
 *  algorithm given by Knuth, the art of computer programming, vol. 2,
 *  pp. 26-27.  We use e=32, so we have to evaluate y(n) = y(n-24) + y(n-55)
 *  mod 2^32, which is implicitly done by unsigned arithmetic.
 *
 ****************************************************************************/
/*
 *  Random numbers from Mathematica 2.0
 *  SeedRandom = 1;
 *  Table[Random[Integer, {0, 2^32 - 1}]
 */

   static uint32 x[55] =
   {
    1410651636UL,
    3012776752UL,
    3497475623UL,
    2892145026UL,
    1571949714UL,
    3253082284UL,
    3489895018UL,
    387949491UL,
    2597396737UL,
    1981903553UL,
    3160251843UL,
    129444464UL,
    1851443344UL,
    4156445905UL,
    224604922UL,
    1455067070UL,
    3953493484UL,
    1460937157UL,
    2528362617UL,
    317430674UL,
    3229354360UL,
    117491133UL,
    832845075UL,
    1961600170UL,
    1321557429UL,
    747750121UL,
    545747446UL,
    810476036UL,
    503334515UL,
    4088144633UL,
    2824216555UL,
    3738252341UL,
    3493754131UL,
    3672533954UL,
    29494241UL,
    1180928407UL,
    4213624418UL,
    33062851UL,
    3221315737UL,
    1145213552UL,
    2957984897UL,
    4078668503UL,
    2262661702UL,
    65478801UL,
    2527208841UL,
    1960622036UL,
    315685891UL,
    1196037864UL,
    804614524UL,
    1421733266UL,
    2017105031UL,
    3882325900UL,
    810735053UL,
    384606609UL,
    2393861397UL
   };
   static int init = TRUE;
   static uint32 y[55];
   static int j, k;
   uint32 ul;

   if (init)
   {
      int i;
      init = FALSE;
      for (i = 0; i < 55; i++)
         y[i] = x[i];
      j = 24 - 1;
      k = 55 - 1;
   }
   ul = (y[k] += y[j]);
   if (--j < 0) j = 55 - 1;
   if (--k < 0) k = 55 - 1;
   return (ul);
}

/* my 64bit algorithm
 * shift 32 2 * (2^32) = 2^64
 */
uint64
Rand64(void)
{
  uint64 key;

  key = HashRand();
  key = key << 32;
  key |= HashRand();
  return key;
}


[Ron Murawski]

Your problem sounds like a hash error, but bad moves can be caused by overwiting data or having variables overflow.

I use a 64-bit PRNG called "ISAAC-64" in my engine
http://burtleburtle.net/bob/rand/isaacafa.html
Scroll down 1/2 way to get the 64-bit source links

Happy New Year
Ron

[Martin Giepmans]

In my engine I generate the necessary 64-bits random numbers with the simple:

X[0]=1001
X[n+1] = 6364136223846793005*X[n] + 1 (mod 2^64) (suggested by Knuth)

These numbers seem to work fine. In any case I never saw blunders that could only be caused by a problem with the hashtable.
But I don't really know if they have the right properties (hamming distance or what was it? ) for hashing.

[H.G.Muller]

I don't expect overapping bits to be a problem, if you xor the bits: the xor of two random uncorelated bitpatterns is still purel random (i.e. homogneously distributed). This remains true even if only on of the pattersn is random. Of course many random implementations are no good at all, but do have strong correlations between succesively returned values.

In my minimalistic chess program Micro-Max I tried to save some space in the piece-square tables for the Zobrist key (to increase L1-cache hit rate) by using a 12x64 array T of random bytes (well, actually 8x128, but never mind that), reading out a group of consecutive bytes as an integer:

Code: Select all

key ^= *(int*)&T[piece][square];


So in fact the random codes for the various piece-square combinations are not independent, but a subpattern of 8 bits that occurs in one, occurs in another in a different place.

I tested if this resulted in an increased rate of misidentificatons, by randomly generating and tabulating positions together with their calculated Zobrist key, and counting how often two different positions gave the same Zobrist key. For 4-byte keys this resulted in ~1 collision in 100.000 positions (growing quadraticaly, i.e. 1 collision per 4 billion pairs), just as expected (and observed) for fully independent random numbers. So apparently, this kind of overlap between the random numbers has no effect at all on the miss-identification rate.

I also tried a hash key constructed as the sum over the product of the square number and a big prime (~60 million) specific for the piece occupying the square. (So that only a table of 32 primes is required.) This also did not have a miss-identiication rate worse than the theoretical optimum for a key of that size, but it had the disadvantage of mapping positions that swapped pieces of identical type to different keys. (This does not lead to errors, but is less efficient. Because it does not happen very often that such states occur in the same tree, the efficiency diffence is hardly noticeable in practice).

Anyway, to avoid inability to exactly reproduce the thought process that led to a certain move (by starting any move with an empty hash table, and recording all random seeds). If you don't, you sould simply accept that nothing can be learned from the way the program played. At the Dutch open my own engine started to play absolutely crazy moves in one round (it refused to move pieces that came under attack). Despite the fact that I set up everything to make it act reproducible, I could never reproduce the behavior later, so I can be pretty sure it must have been due to hardware error. (Not unlikely, sice my cooler fan was stuck, making the computer overheat all the time...)

[Alvaro Begue]

You can have a hash-debugging mode where you store the entire position in each hash table, on top of your usual hash verification value and useful information. That way you can count how many false identifications of positions happen.

If your random numbers are not horrendous (and they probably aren't), the most important factor is how many bits of the hash key you store for verification purposes, and where you get those bits from (it's a bad idea to store the lower bits, which are also used to determine where in the hash table to look).

So, how are you doing hash-key verification?

Reproducibility is very important in my opinion, and that's why I clear the hash tables before starting any search. This also avoids some time-control complications.

[Pedro Castro]

Thanks to all for your help, I have proven to change the generation of the aleatory number and to upgrade the hash during the null move, but I believe that I have seen the same problem again, at least in a game of 100.

In the following position the program play Kf1, while in the analysis it never plays this move, the normal thing is that Nd2 had played (independently that this it is a lost position)

[diag]r1q2rk1/ppp3pp/3b2n1/3P4/2R2p2/1QP2P2/PP3PKP/RNB5 w - - 0 18[/diag]

FEN: r1q2rk1/ppp3pp/3b2n1/3P4/2R2p2/1QP2P2/PP3PKP/RNB5 w - - 0 18

DanaSah v1.8.4:
1 00:00 8 8 -2,32 Axf4 Cxf4+
1 00:00 31 31 -0,01 Ta4
1 00:00 44 44 +0,07 Td4
1 00:00 51 51 +0,16 Dd1
1 00:00 62 62 +0,23 Te4
2 00:00 1.105 1.105 -0,54 Te4 Ch4+ Rg1 Cxf3+
2 00:00 1.300 1.300 -0,06 Dd1 Df5
3 00:00 2.720 136.000 +0,11 Dd1 Ch4+ Rg1 Df5
4 00:00 6.077 303.850 -0,03 Dd1 Df5 Te4 Tfe8
4 00:00 7.428 247.600 +0,17 Rg1 Te8 Te4
5 00:00 21.266 354.433 +0,13 Cd2 Tb8 Ce4 Dd7
6 00:00 50.877 508.770 +0,09 Cd2 Ch4+ Rg1 Te8 Dd1 Dh3 b3
7 00:00 137.155 596.326 -0,85 Cd2 Ch4+ Rg1 Te8 h3 Dxh3 Dxb7 Cxf3+ Cxf3 Dxf3
8 00:00 619.397 666.018 -1,00 Cd2 Ch4+ Rf1 Dh3+ Re2 Tab8 Ce4 Dxh2 Cxd6 cxd6
9 00:01 797.236 681.398 -1,04 Cd2 Ch4+ Rf1 Dh3+ Re2 Cxf3 Dxb7 Cxd2 Rxd2 Df1 Txc7 Axc7 Dxc7 Dxf2+
10 00:03 2.511.012 682.340 -1,66 Cd2 Ch4+ Rf1 Dh3+ Re2 Cxf3 Dxb7 Tae8+ Te4 Txe4+ Cxe4 Te8 Axf4 Axf4
11 00:10 7.808.596 719.686 -2,06 Cd2 Ch4+ Rf1 Dh3+ Re2 Cxf3 Ce4 Dg4 Rf1 Cxh2+ Re1
12 00:15 11.476.265 735.186 -2,18 Cd2 Ch4+ Rf1 Dh3+ Re2 Cxf3 Da4 Cxh2 Ce4 Df1+ Rd2 Cf3+ Rc2 De2+ Rb3
13 01:09 52.547.066 761.551 -2,45 Cd2 Ch4+ Rf1 Dh3+ Re2 Cxf3 Ce4 Tae8 Dc2 b5 Tc6 Cg5 f3 Cxe4 fxe4 Dxh2+
14 01:46 83.155.043 784.481 -2,55 Cd2 Ch4+ Rf1 Dh3+ Re2 Cxf3 Te4 Cg5 Ta4 Tfe8+ Rd1 Dh5+ f3 Cxf3 Cxf3 Dxf3+ Rc2 Df2+ Ad2
15 04:28 222.942.333 831.874 -2,51 Cd2 Ch4+ Rf1 Dh3+ Re2 Cxf3 Te4 Cg5 Ta4 Tfe8+ Rd1 Dh5+ Rc2 Dxh2 Dxb7 Dxf2 Dc6 Rh8 Tb1

[Volker Böhm]

Hi,

the only suggestion I can give you is to make your problem debuggable. I think it is very probable that your problem is a "simple" program bug and not a problem of random numbers.

Idears to make an engine debuggable (to reproduced the problem).

1. Make sure that you are 100% able to reproduce a search tree.
-> make sure you allways generate the same hash random nubers or better store them as constants in your source code!
2. Write Functions to save/load your situation to disk (hashes, piece ordering, ...)
3. Write the amount of nodes you searched in a game to a debug file.
4. Write an algorithm that reproduces the last search by having the amount of nodes per search (as all is 100% reproducable, searching the same node amount should result in the same game!).
5. Store the situation at the position with the error.
6. Look at the problem in your debugger.

For this bug this may be an overkill, but this will help you greatly in debugging future problems.

Greetigs Volker

[H.G.Muller]

All suggestions above are very good. In addition, I would like to add this:

In debugging a chess engine I found it very useful to include some code that allows me to step through the search tree in exactly the way the engine searched it during a suspected mistake. So I implemented commands to print the list of moves considered and the score they recieved in various (deepening) iterations in a certain node, freezing the hash table while doing this, (or make provisions so that it is restored to its state from before the command afterwards), and then select a move to play (for which the score looks suspicious) and repeat the process in the node this brings you to.

If you have hash-table problems, this kind of debugging usually does not really solve anything, since the move with the obvious wrong score that led to the decision is only motivated by the message: "I thought this move had this score because I found the position it led to in the hash table". Since usually the hash table does not store the full position, you don't even know if there was a mis-identification, and you may not have enough memory to store this information for debugging purposes in the table, and a smaller table might not reproduce the problem.

So in cases like that I let it print the hash-table-entry number and ply depth of the entry in the table. This allows me to repeat the search, setting a 'breakpoint' on hash-table replacement of this entry. The first time the search encounters a position at that depth that maps to this hash-table entry it switches to the debug menu, so that I can then walk through the tree that was responsible for filling this entry. It is then also immediately obvious if this is the same position as in the case where the entry was retrieved. If it was, it allows me to climb the tree further, and find where the erroneous score came from.