Yes. In fact because I use several flags along with the move itself that must match (otherwise my domove would choke on that and break badly), my legality check is fairly complicated.
Because I had some bugs early, I did brute force validation (paranoid) by tossing every possible combination of encoded move at it
(while searching iirc - needless to say it wasn't very fast
This paid off in the end and allowed me to get rid of all bugs related to legality check.
Checking whether a pseudolegal move for a given position is legal is easy.
But checking whether a random move is legal in current context is much more complicated.
cdani wrote:Someone has an idea of how often happen the hash collisions? I did some tries and I'm not able to catch an illegal move coming from hash. Anyway I keep checking them for legality.
So if you use a 64-bit number for hashing and nothing else, a search with 200 million nodes in it will have a collision more then 0.1% of the time.
What I have done in my last checkers program is use a 24-bit hash for picking the 4-entry bucket where I'll store the position and a separate 64-bit hash for verifying it's the right entry. So that's an effective 88-bit hash.
With 88 bits, you'll get a collision with probability less than 10^-6 after 200 million stores. In order to get a probability of 0.1% with 88 bits, you need to store more than 8*10^12 positions.
All my recent programs use 128 bit hash signatures, although I think that 96 bit signatures would be sufficient for most applications. But not for deep perft().
With 128 bit signatures, there's no real need for a legality check because the probability of a false positive is less than the probability of hardware errors caused by cosmic rays.
While there is a slight overhead gotten from moving from 64 bit to 128 bit signatures, the associated time penalty may be less than the time penalty associated with retrieved move legality checking.
jordanbray wrote:Is it, then worthwhile to do a legality check any time I take a score from the TT? It seems like I'm gonna end up with a bad search if I take the score without much fuss, given that hash collisions do seem to happen.
A few bad probes won't make your search bad. You only need to check legality if your program would crash otherwise.
cdani wrote:Someone has an idea of how often happen the hash collisions? I did some tries and I'm not able to catch an illegal move coming from hash. Anyway I keep checking them for legality.
This always comes up, but it is the wrong approach. The hash table does not remember all previous birthdays, only those that are still present.
With a small hashtable and 64-bit hash keys (that are fully stored in the hash entries), the number of collisions will be much smaller than with a large hashtable and the same size of hash keys. The birthday paradox approach misses that entirely.
What you need to calculate is the number N of discriminating bits, i.e. bits not used to determine the hash entry. The number of collisions will be 1 in 2^N hash probes. (This is still an estimation as it ignores the number of correct hash hits and it assumes that the hash table is full. This latter assumption is in fact very much valid for normal games where you don't clear the hash table between moves.)
So if you use a 64-bit number for hashing and nothing else, a search with 200 million nodes in it will have a collision more then 0.1% of the time.
Note that this is only true if the hash table can store the entire tree. Usually more relevant is the probability the signature stored in the table accidentally matches that of a different position. E.g. with a 32-bit signature the probability for this is 1 in 4 billion (2^32). So with searches of 200M (different) nodes one in every 20 searches would contain one collision.
Of course a collision does not necessarily mean the hash move would be so wrong that it would crash the engine. E.g. the chance to accidentally expose yourself to check by a random move might be only 1%, so if that would be what crashes your engine, you should expect one crash in 2000 moves, i.e. once every 20 games (with 32-bit signature). This is unacceptably high, so I make sure the engine can handle King capture properly. (Which is a much cheaper test than verifying if the hash move is legal in every node.)
Last edited by hgm on Mon Jan 12, 2015 10:49 am, edited 1 time in total.
jordanbray wrote:Is it, then worthwhile to do a legality check any time I take a score from the TT? It seems like I'm gonna end up with a bad search if I take the score without much fuss, given that hash collisions do seem to happen.
A few bad probes won't make your search bad. You only need to check legality if your program would crash otherwise.
I only store the move index instead of the move in the hash table. Then I simply generate all moves, and play move "index" equal to "index = hashed % size;" where "hashed" is looked up from the TT and "size" is the size of the generated move list. This is guaranteed to work (I do check for division by zero, but that is an immediate loss for the side to move anyway).
Modulo a variable is incredibly expensive. It seems much better just to test if hashed > size, and if so, treat the hit as a miss (as it must be a collision) rather than promote an essentially randomly chosen move to hash move. (So that you can trigger IID to find a real hash move, etc.)
Another problem seems that you would have to remember the original move index in the face of move sorting.
Rein Halbersma wrote:
I only store the move index instead of the move in the hash table. Then I simply generate all moves, and play move "index" equal to "index = hashed % size;" where "hashed" is looked up from the TT and "size" is the size of the generated move list. This is guaranteed to work (I do check for division by zero, but that is an immediate loss for the side to move anyway).
Most engines try to avoid generating all the moves to validate the hash move, because it's faster to test for legality. Many times the hash move will be good enough to return immediately, so it's better to avoid generating all.
