Checking TT move for legality

[syzygy]

I agree with what syzygy wrote, except, depending on your engine, you may need to assume that the move you get does not describe any legal move. This is because you may get garbage data from threading race conditions, if you use an unprotected shared hash table.

As long as the move is always read and written atomically, even multiple threads reading/writing to the same entry at the same time won't result in a move being read that does not describe any legal move, assuming the hash table is initially cleared (and you can deal with zero moves, i.e. something like a1a1, which is an exception to "does not describe any legal move", but you could also initialise the table to a1b1 or something similar).

Admittedly making such assumptions is not the best idea for portability.

[syzygy]

I do not check the TT move for legality. If it was legal going in, I expect that 99.99999%+ of the time it will be legal coming out. I do, however, store the full Zobrist key of the position in the hash table item and make sure it matches the current position before accepting that as a TT match. Someday, this may prove to be a poor decision, but that day is not today.

If your hash key is 64 bits and you have a hash table with 2^32 positions, then you only have 32 unique bits left. If the hash table is full, you will get 1 collision every 2^32 TT probes. If you probe in the Qsearch, this can lead to a crash every hour or so.

[Pio]

I think you are wrong. For the first most of the probes will be on the same positions so there won’t be 2^32 probes on unique positions. Secondly if you have two positions with the same zobrist hash you would most likely have many more, that is they should cluster. The reason is very simple. Assume two positions have the same zobrist hash it is probable that they have at least one piece at the same square that has one or more legal moves in common. That will result in that one or more of their children to have the same zobrist hash. The clustering will have the effect that once it crashes it will crash many more times if it could and since your engine will only crash once per game it will have the nice side effect that getting the first crash will be less likely than pure random. Either that or that the result of zobrist hashing is quite far from a perfect random hash function. I am too tired now to see which is correct or if it is a combination of the two. I guess someone smart like HGM can point out the right answer.

I have thought some more now. Since you combine the random states in a non random way it will most likely not be random. The result might be better or worse than random depending on if the non randomness will make illegal positions to collide more frequently than legal on average. I guess that it will be worse than random but theoretically it could make zobrist like functions better than random which is really interesting.

[AAce3]

There are also considerations for using using it to check killer moves for legality without actually having to generate all quiet moves. I haven't tested whether this actually leads to speedups but since I have the functionality now I might as well.

Assume two positions have the same zobrist hash it is probable that they have at least one piece at the same square that has one or more legal moves in common. That will result in that one or more of their children to have the same zobrist hash.

I think that would happen less often than expected. Unless the transposition move is common to both positions (unlikely, as they are not necessarily more or less similar to each other despite the fact that they have the same hash key) or there are common captures, there would probably be a cutoff before any of the other moves are tried.

[JoAnnP38]

I do not check the TT move for legality. If it was legal going in, I expect that 99.99999%+ of the time it will be legal coming out. I do, however, store the full Zobrist key of the position in the hash table item and make sure it matches the current position before accepting that as a TT match. Someday, this may prove to be a poor decision, but that day is not today.

If your hash key is 64 bits and you have a hash table with 2^32 positions, then you only have 32 unique bits left. If the hash table is full, you will get 1 collision every 2^32 TT probes. If you probe in the Qsearch, this can lead to a crash every hour or so.

I think your calculations are probably off in some manner. Moreover, I suspect that two different positions that have the same Zobrist key don't look much alike and thus the probability of them appearing in the TT at the same time are essentially nil especially if that TT supports aging. Of course, that is only a hunch and has no mathematical backing. Given that I've not run into this problem once that I'm aware of makes me doubt the importance of spending the CPU time it would take to validate the move for legality. On top of that, Pedantic also supports the Polyglot opening book format and it also indexes moves by Zobrist hash. I don't check those for legality either and have not had a problem their either. One of these days I might and then I'll probably cobble together some validation code, but not today.

[syzygy]

I do not check the TT move for legality. If it was legal going in, I expect that 99.99999%+ of the time it will be legal coming out. I do, however, store the full Zobrist key of the position in the hash table item and make sure it matches the current position before accepting that as a TT match. Someday, this may prove to be a poor decision, but that day is not today.

If your hash key is 64 bits and you have a hash table with 2^32 positions, then you only have 32 unique bits left. If the hash table is full, you will get 1 collision every 2^32 TT probes. If you probe in the Qsearch, this can lead to a crash every hour or so.

I think your calculations are probably off in some manner.

They are off only by the ratio of real hits. I don't know what is a normal ratio of real hits, but it won't be more than 50%
Also I am not taking into account buckets, but they won't totally change the equation (probably make it worse rather than better).

Moreover, I suspect that two different positions that have the same Zobrist key don't look much alike and thus the probability of them appearing in the TT at the same time are essentially nil especially if that TT supports aging.

A good aging strategy can help improve the hit ratio, but it won't do more than that.

Zobrist keys do a relatively good job at being uniformly randomly distributed. You can't expect them to do better than that.

Of course, that is only a hunch and has no mathematical backing.

And I have backed up my claim mathematically.

If you have a 64-bit key and 2^32 hash entries, you have 32 bits left to disambiguate. If your hash table is already nearly filled (which will take some small multiple of 2^32 nodes), then any further lookup will find a TT position whose hashkey necessarily agrees on the 32 bits that you use to index into the hash table. The other 32 bits will agree (1) if there is a valid hit (which is what you want) and (2) in about 1 in every 2^32 lookups which are not valid hits. In case (2) the stored tt move MIGHT be sufficiently valid for your engine to survive, but chances are quite good that your engine will crash.

So about every 2^33 nodes in which you do a TT lookup and play the TT move, your engine will crash (2^33 takes into account the real hits and the times that your engine is lucky and survives).

If you do 10 million nodes per second, that gives your engine 859s or about 15 minutes. Starting from an empty (and zero'd) hashtable, you can add maybe 30 minutes. But in real games you can assume your hashtable is filled (unless you clear it between moves, which is not recommended).

Every time you halve the size of the hashtable, you add a bit for disambiguation, so the 15 minutes will double (and the time needed to fill the hashtable will halve).

With a generous 16 bytes per TT entry, 2^32 entries means 64 GB of hash, which nowadays is very realistic.

Given that I've not run into this problem once that I'm aware of makes me doubt the importance of spending the CPU time it would take to validate the move for legality. On top of that, Pedantic also supports the Polyglot opening book format and it also indexes moves by Zobrist hash. I don't check those for legality either and have not had a problem their either. One of these days I might and then I'll probably cobble together some validation code, but not today.

You are not testing with 64 GB of hash.

[Pio]

The following section is wrong

“ So about every 2^33 nodes in which you do a TT lookup and play the TT move, your engine will crash (2^33 takes into account the real hits and the times that your engine is lucky and survives).”

The biggest mistake with your reasoning is that you assume that all TT lookups are made from different positions. That is far from truth. I don’t know how wrong you are but I guess at least by a factor 10 on average.

[JoAnnP38]

You are not testing with 64 GB of hash.

Well forgive me for developing on a Windows PC using the X86 64-bit architecture. I normally only test with 256MB of hash table because Pedantic is: 1) single-threaded and 2) I know that CCRL primarily tests single-threaded engines with 256MB of hash table. Isn't this a more realistic scenario?

[Ras]

I don't generate moves when I have a TT move, but I do test for pseudo legality in the TT lookup function. If that fails, I treat the lookup as non-matched. Since I don't use TT in QS, the pseudo legality checks don't take much time anyway. Before actually making the move, I also test for in-check legality like for every other move, i.e. with alignment checks in most cases and a full king-in-check verification in the few remaining ones. In the choice between a minor slowdown and the risk of very rare potential crashes, I favour engine stability.

[syzygy]

The following section is wrong

“ So about every 2^33 nodes in which you do a TT lookup and play the TT move, your engine will crash (2^33 takes into account the real hits and the times that your engine is lucky and survives).”

The biggest mistake with your reasoning is that you assume that all TT lookups are made from different positions. That is far from truth. I don’t know how wrong you are but I guess at least by a factor 10 on average.

Please read first what I wrote. I mentioned the ratio of "real hits" and that it won't be more than 50%.

Factor of 10? No way.