TT: key collisions

[Karlo Bala]

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?

Don't worry about key collisions. It happens rarely and does not affect the outcome of the search. There are orders of magnitude greater randomness in a chess engine than key collisions. Just test the TT move before using it.

[lojic]

With crashing I indeed meant the program aborting. You would only play an illegal move if you would play the hash move without checking in the root, and had a key collision there. ...

Ah, I totally missed the important distinction between playing the move at the root vs. lower in the tree! Some checking at the root would have little impact on performance.

[Ras]

If you really worry about that, it would be better to use a longer key.

I'm storing the upper 32 bits of the key, and since the "flag" (check-alpha, check-beta, exact) only needs two bits in a uint8_t, I fiddle six additional key bits into that. Makes 38 key bits stored, plus the index of course. I don't have more memory because the microcontroller target platform has only 192kB SRAM (plus 1MB flash-ROM for code and static data). The extra redundancy of the hash move hence is pretty welcome.

[hgm]

That is already more than I typically store (which is 32 bits). Collisions should hardly be a worry.

[jdart]

Btw. TCEC recommended to all authors that they test for hash collision issues, due to the very big hardware and consequently high NPS rates on their setup. A collision once in "only" 1 billion nodes is really quite possible, once you have hundreds of millions NPS and long time controls.

One way to test is to deliberately use a lower size key (for example, mask out all but 16 bits of the key). You will then get a lot of collisions. This may affect search accuracy, but it should not cause the program to crash due to executing an illegal move. It is probably not completely possible to ensure that without full legal move detection, but you can get to the point where you aren't getting any kind of frequent issue, even with a shortened hash function. I had to tighten some move checks to make that happen.

[hgm]

Of course it is possible without full legality detection. But you have to know what kind of normally unreachable positions could possibly crash the engine. Pseudo-legality is in general not a requirement, as most engines would be perfectly able to handle chess variants where pieces would move in different ways, and where the move that is not pseudo-legal in orthodox Chess would have been pseudo-legal for that variant. As long as the move is not 'weird' in a more fundamental aspect (such as moving a piece of the opponent or an empty square, or capturing a friendly piece, or one of the Kings, or promoting a non-Pawn) you cannot be sure anymore that the engine could handle it; it could make assumptions in MakeMove/UnMake that certain actors are of a certain color, or that Kings will be always present.