TT: key collisions

Discussion of chess software programming and technical issues.

Moderators: hgm, Dann Corbit, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
lojic
Posts: 71
Joined: Thu Jan 28, 2021 8:50 pm
Full name: Brian Adkins

TT: key collisions

Post by lojic » Sat Feb 13, 2021 7: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?

jdart
Posts: 4134
Joined: Fri Mar 10, 2006 4:23 am
Location: http://www.arasanchess.org

Re: TT: key collisions

Post by jdart » Sat Feb 13, 2021 8: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. There is another problem, which is concurrent updates of the same hash entry. For that the usual solution is Hyatt's lockless hashing method (https://craftychess.com/hyatt/hashing.html).

However, you do need to do at least psuedo-legal move checking if you are going to use the hash move, with a 60-bit key.

lojic
Posts: 71
Joined: Thu Jan 28, 2021 8:50 pm
Full name: Brian Adkins

Re: TT: key collisions

Post by lojic » Sat Feb 13, 2021 8:05 pm

jdart wrote:
Sat Feb 13, 2021 8: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. ...
If I'm understanding the author, I think he's, in effect, using two zobrist keys, so in his case, 128 bits instead of 64 bits. He incrementally updates them both, instead of just one.

User avatar
hgm
Posts: 26434
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: TT: key collisions

Post by hgm » Sat Feb 13, 2021 9: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
Posts: 71
Joined: Thu Jan 28, 2021 8:50 pm
Full name: Brian Adkins

Re: TT: key collisions

Post by lojic » Sat Feb 13, 2021 11:08 pm

hgm wrote:
Sat Feb 13, 2021 9: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.
I'm not sure I fully understand you. I'm not worried about crashing my engine in the sense that the program would abort, but if I let it make a move that didn't reflect reality, then it would likely start attempting illegal moves (moving pieces that didn't exist, etc.), but maybe that's what you meant by "crashing".

Testing for both pseudo-legal and legal seems expensive compared to adding enough bits to get to an acceptable risk level.

In KingSlayer, what happens if it makes an invalid move from a TT lookup e.g. capturing an opponent's piece with a non-existent piece of yours?

lojic
Posts: 71
Joined: Thu Jan 28, 2021 8:50 pm
Full name: Brian Adkins

Re: TT: key collisions

Post by lojic » Sat Feb 13, 2021 11:17 pm

lojic wrote:
Sat Feb 13, 2021 7: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

lojic
Posts: 71
Joined: Thu Jan 28, 2021 8:50 pm
Full name: Brian Adkins

Re: TT: key collisions

Post by lojic » Sat Feb 13, 2021 11:37 pm

lojic wrote:
Sat Feb 13, 2021 11:17 pm
lojic wrote:
Sat Feb 13, 2021 7: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
Ok, I think I have my answer from that article:
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.
For now, I think I'll just store the entire 60-bit zobrist key (easier than storing that minus the index bits), and not worry about it.

User avatar
hgm
Posts: 26434
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: TT: key collisions

Post by hgm » Sun Feb 14, 2021 8:55 am

With crashing I indeed meant the program aborting. You would only play an ilegal move if you would play the hash move without checking in the root, and had a key collision there. With 32 key bits that would only happen once in 4 billion moves, which is probably negligible compared to the number of illegal moves you would get due to hardware failure. Illegal moves deeper in the tree can of course lead to playing a poor move in the root, but you already dug up the article that shows the search is really very forgiving w.r.t. this. I think that Stockfish only stored 16 key bits in the TT entry, because the increased number of entries that could be fit that way in a TT of a given size more than offset the detrimental effect of the high key collision rate.

As for vetting the hash move, it is probably enough to test that the from-square contains a piece of the side to move, and the to-square is empty or a non-royal opponent. Assuming that the engine is used to handling pseudo-legal moves, so that it will still be checked for exposing the King in a later stage of processing, just like the moves that come from the move generator. Only for castlings you might have to do more, depending on whether your MakeMove/UnMake can handle cases where the Rook captures something. (Since castling is rare to non-existent, the make/unmake code for castling is only rarely executed, so it is speedwise better to complicate that code a bit for making it more robust than to throw an extra test on every TT move.) Depending on how you implemented promotions, you could also have a problem when a promotion from the TT is applied to a non-Pawn. Again, the best safeguard against this seems to make the promotion code more robust, so it can handle this. (E.g. really put back the original piece in UnMake, rather than hardcoding a Pawn for this.)

Ras
Posts: 1945
Joined: Tue Aug 30, 2016 6:19 pm
Full name: Rasmus Althoff
Contact:

Re: TT: key collisions

Post by Ras » Sun Feb 14, 2021 12:43 pm

Checking a hash move at least for pseudo legality also introduces some more redundancy on top of the key. If the hash move is illegal, I treat the lookup as non-hit.
Rasmus Althoff
https://www.ct800.net

User avatar
hgm
Posts: 26434
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: TT: key collisions

Post by hgm » Sun Feb 14, 2021 2:22 pm

That is true, but the question is, would it be beneficial or detrimental? You are doing an extra pseudo-legality test on every hash move, to have a better chance to detect a one-in-a-billion case that it was a collison. The slowdown is only minute, on the order of 0.1%. But it is still a slowdown, for virtually no benefit. Because the chances that this one-in-a-billion collision, when it would occur, would have had any effect on the engine's root move are again something like 1 in a million.

So why complicate your code (and sacrifice 0.1 Elo) with extra, not entirely trivial tests, to guard against effects that would probably never happen in your lifetime?

If you really worry about that, it would be better to use a longer key. This can often be done, and if you like complexity, it can probably be done in such a way that it actually speeds up the engine.

BTW, I realized that the trick I use in KingSlayer, XOR'ing the key bits used for deriving the index with the static eval for use as signature, would even work better if instead of the eval the material or Pawn-hanh key would be used for this. Because, unlike the eval, these keys are homogeneously distributed over the entire range. So by using the XOR of hash key and pawn key as signature stored in the entry, while deriving the index only from the hash key itself, all 64 key bits become significant in protecting against collisions.

Post Reply