TalkChess.com

jdart wrote: ↑Sat Feb 13, 2021 9:01 pm You will get hash collisions with a 60-bit key. Not all that often, but often enough to worry about.

I am not sure what is the lock method you are referring to. ...

hgm wrote: ↑Sat Feb 13, 2021 10:11 pm Storing the entire hash key is a waste of space, as many bits of it will have been used to derive the table index. So these bits are guaranteed to match, and offer no extra protection against key collisions. I usually only store 32 bits in the hash entry (and derive the index from the other bits). This will produce a collision every 4G nodes. So at 1Mnps that is about once every hour.

Now the amazing thing is that even having a few thousand collisions per second hardly affects the search. Provided these collisions just provide wrong scores, or suggest illegal (but possible) moves. Of course when they would provide a move that crashes your engine, this will have a very obvious and annoying impact even when it happens only once every few hours. So even if there is an extremely slim chance for a collision, you should make absolutely sure that the move this provides cannot crash the engine. Testing the hash move for legality is one way to ensure that. Moving your own piece in a way it is not supposed to move is usually harmless, but things that can cause trouble are typically moves that make a King disappear, moves with opponent pieces, capture of own pieces, moves starting from an empty square, capturing during castling (and not restoring that on UnMake)...

In KingSlayer I do store 64 key bits in the TT entry. But I use the low-order bits of that key as index (typically 28 of those, so that I have 36 discriminating bits left), and XOR what I store with the static evaluation to reduce (and of course compare that with a similarly XOR'ed key on probing) to make also the 16 low-order bits somewhat discriminating. (Although evaluations are not homogeneously distributed over the interval [-32K, +32K], the chance that two evals are the same is usually not greater than 1%. At the very low collision rate makes me I feel comfortable with not testing the hash move at all. KingSlayer's MakeMove() is very tolerant to illegal moves anyway; I am not even sure it is theoretically possible to crash it.

lojic wrote: ↑Sat Feb 13, 2021 8:35 pm I've just finished a couple refactorings in preparation for adding a transposition table to my engine. I'm now modeling castling rights in my game state (vs. using a moved bit), and both the game state and move now fit in native integers respectively.

I've read the Mediocre TT Guide that @Nomis mentioned on another thread, and I've looked through CPW a bit.

I'm using 60-bit zobrist keys (system limitation). I'm planning on storing the full key in the hash table entry, but I'm guessing I should probably do more than that to avoid a key collision (not hash table index collision). If so, what is the recommended approach? In "How to Write a Chess Program", the author uses a second key, he calls a lock. I've also read about ensuring the move is pseudo-legal before using it. I would think incrementally updating a second key/lock would be faster than checking for pseudo-legality.

In summary, two questions:
1) Is the likelihood of a key collision with a 60-bit key enough to worry about?
2) If so, what are good ways to handle this?

lojic wrote: ↑Sun Feb 14, 2021 12:17 am

lojic wrote: ↑Sat Feb 13, 2021 8:35 pm I've just finished a couple refactorings in preparation for adding a transposition table to my engine. I'm now modeling castling rights in my game state (vs. using a moved bit), and both the game state and move now fit in native integers respectively.

I've read the Mediocre TT Guide that @Nomis mentioned on another thread, and I've looked through CPW a bit.

I'm using 60-bit zobrist keys (system limitation). I'm planning on storing the full key in the hash table entry, but I'm guessing I should probably do more than that to avoid a key collision (not hash table index collision). If so, what is the recommended approach? In "How to Write a Chess Program", the author uses a second key, he calls a lock. I've also read about ensuring the move is pseudo-legal before using it. I would think incrementally updating a second key/lock would be faster than checking for pseudo-legality.

In summary, two questions:
1) Is the likelihood of a key collision with a 60-bit key enough to worry about?
2) If so, what are good ways to handle this?

Found this: The effect of hash collisions in a Computer Chess program

However, in the case of Crafty, there was an overwhelming reason to allow no hash collisions. Crafty uses the "hash move" in the search, and it cannot recover from a circumstance where the hash move is actually illegal, as it immediately makes the move, and once that happens the chess board can become irreversibly corrupted. For example, castling king-side after the king has already castled queen-side will produce a new king at g1, with a king already at c1. When this move is unmade, the g1 king goes back to e1, and we now have an ugly position with two kings. Years ago Crafty had a simple legality check added to prevent this kind of catastrophic failure, and when it is detected, the move is not played, but an error message is logged. This error has not been reported in over 100,000 games now, which doesn't necessarily mean that no hash collisions have occurred, but it does mean that if a collision did occur, at least the hash move was not illegal.

One other simple experiment was run, attempting to define the minimum hash signature length necessary to avoid problems. In summary, 32 bit signatures produced wrong moves and scores, while 64 bits did not. An “in-between” value of 48 bits also proved to be just as safe as 64, but 48 is not a reasonable size since either 32 bit or 64 bit values are the natural signature lengths for 32 bit processors, and 64 bit signatures are the natural signature length for 64 bit processors.