hash collisions

[Ras]

Even testing only every hash move for a valid offset will take thousands times more time.

I store only a 32 bit key - the upper part of the 64 bit key while the lower part of the 64 bit key serves for table indexing. The reason is the pretty limited memory on my microcontroller target hardware. That's why I use the legality check to increase the equivalent key length.

I do a full pseudo legality check on the hash move, i.e. not only the offsets, but for sliders also free squares in-between. To top it off, this isn't a bitboard engine so that the free square check involves actual loops. Means, it couldn't possibly become any worse in terms of performance impact.

If the pseudo legality check fails, I treat that as a failed hash lookup. The king-in-check verification happens afterwards because that would crash the engine. If I have a hash move, I defer the full move generation to the case that it doesn't give a cut-off.

I ran a little benchmark using the PC UCI version with and without the pseudo legality check in the hash lookup. I actually removed the whole function call to even eliminate that overhead. I did however keep the king-in-check verification.

I tried two positions, endgame and middlegame. In both positions, the number of nodes, PV and score were the same with and without pseudo legality checks of the hash move, so the search tree must have been the same. The difference is the pure performance impact of the pseudo legality check. The target depth was chosen so that I get around 20-40 seconds of time to depth. PV was cleared with ucinewgame and new position command between the different hash table sizes. The engine has only one worker thread.

1) Endgame: 8/3k4/8/8/8/8/2BKN3/8 w - -
256MB hash: 1% faster without checks
1MB hash: 0.7% faster without checks

2) Middlegame: 3qr1k1/p2n1ppp/b1p1p3/8/PrpPP3/4N1P1/2Q2PBP/3RR1K1 w - -
256MB hash: 0.7% faster without checks
1MB hash: 0.7% faster without checks

My conclusion: the performance impact is negligible.

[syzygy]

My question was, however, is 4) actually faster? Remembering pieces captured by castling, which piece promoted in case of non-pawn, searching impossible positions, etc. doesn't sound like it would be faster to me, but I might be wrong. I assume hgm has tried both, and I'd love to hear the result of such testing.

If HGM is right, implementing this in Stockfish should simplify the code and add Elo. I'm pretty sure it won't, but if someone is willing to write a patch he can prove me wrong.

[syzygy]

I complained to the Stockfish group that badly formed EPD will cause Stockfish to crash and core dump heinously, eventually filling my disk drive with core files.
Their response was: "Don't send badly formed EPD to Stockfish then."
I guess we should all expect that the millions of EPD positions we find on the internet are all properly formed. After all, a badly formed EPD record would mean that someone made a mistake in forming the EPD record.

No, what you have been told multiple times is that Stockfish takes no responsibility here and that it is your responsibility to check the EPDs you find on the internet with whatever suitable program you like before you feed them to Stockfish.

[mar]

How would a move stored in your TT be random bits?

Of course it is, if you get a hash collision, which this thread is about.
You don't have to go this far of course, what about killers? But hey at least you know they're quiet

The common sense is of course to check that the move is pseudo-legal first (complicated), then you make sure pseudo-legal is legal (easy).
I thought there's no need to explain this.

So yeah, doing a random move is harmless unless it's not, assuming it's vastly more likely deep down tree and the search will compensate for that.

[mar]

Even testing only every hash move for a valid offset will take thousands times more time.

Any data to support this claim? You still need to do some basic validatation even if you postpone the check.

If searching the occasional impossible line would produce more Elo, there are many people here that will prefer it.

Only if you're lucky, which is very unlikely (unlikely implies no elo gain or even elo loss). If this produces elo then why even bother with move ordering?

[Dann Corbit]

I complained to the Stockfish group that badly formed EPD will cause Stockfish to crash and core dump heinously, eventually filling my disk drive with core files.
Their response was: "Don't send badly formed EPD to Stockfish then."
I guess we should all expect that the millions of EPD positions we find on the internet are all properly formed. After all, a badly formed EPD record would mean that someone made a mistake in forming the EPD record.

No, what you have been told multiple times is that Stockfish takes no responsibility here and that it is your responsibility to check the EPDs you find on the internet with whatever suitable program you like before you feed them to Stockfish.

IOW:
Their response was: "Don't send badly formed EPD to Stockfish then."

[hgm]

Ultimately, this is an example of commercial/academic split on the ethics of not bothering to remove possible bugs/faults. I learnt to work to 100% no bugs and 100% no undefined behaviours. Because it matters. You think rare cases don’t matter and speculate that it will all be okay anyway. Well, it’s a philosophy that is not going to wash in a quality control environment intolerant of faults (all successful companies), especially those that don’t need to be there. In the real world where design matters, you’ld just get told it’s sloppy and if you insist on not fixing then bye-bye, product not accepted, cheque not sent.

Then writing chess programs is the wrong buiseness for you. All existing programs play less than perfect chess, and thus play faulty moves frequently. To the user it doesn't matter at all whether an engine blunders because it has an impossible line somewhere in its search tree, or because the tree cut away the relevant node to make time for executing the code to prevent impossible lines.

A good example of a generally accepted error-prone technique is ignoring the game history when hashing, and only hash on the current position. This tends to mask repetitions, which in some positions is a major fault.

All incandescent light bulbs that have ever been sold were faulty, and burnt out after some time. Yet companies that sold them have been very successful, because there was a huge demand even for such faulty light bulbs. Most people did not whine about the ethics this, but just accepted the flaw as a fact of life.

[hgm]

In the commercial software world, this would be a criminal act (knowingly releasing something with a severe defect).

Yeah! Just like in the commercial car manifacturing world it is considered a criminal act to produce a car that doesn't float indefinitely when you drive it into the lake...

[hgm]

How would a move stored in your TT be random bits?

Of course it is, if you get a hash collision, which this thread is about.
You don't have to go this far of course, what about killers? But hey at least you know they're quiet

The common sense is of course to check that the move is pseudo-legal first (complicated), then you make sure pseudo-legal is legal (easy).
I thought there's no need to explain this.

So yeah, doing a random move is harmless unless it's not, assuming it's vastly more likely deep down tree and the search will compensate for that.

I think the issue here comes from a different interpretation of the word 'random'. The move there must have been a perfectly legal move when it was stored, i.e. in some other position. So you will never encounter moves like f1g4 or e4e5q. Just filling the move field with a random bit pattern would give you such moves.

This distinction can be especially important when your move consists of more than just from-square and to-square, but also contains a field to indicate promotion type or e.p. victim. Depending on the implementation invalid combination of fields could have unpredictable, unexpected and undesired effects.

Even testing only every hash move for a valid offset will take thousands times more time.

Any data to support this claim? You still need to do some basic validatation even if you postpone the check.

A simple calculation from counting the number of instructions used in the test, the number of cycles their execution takes, the nodes per second of the engine and the frequency of hash collisions / corruptions.

If searching the occasional impossible line would produce more Elo, there are many people here that will prefer it.

Only if you're lucky, which is very unlikely (unlikely implies no elo gain or even elo loss). If this produces elo then why even bother with move ordering?

Searching unnecessary lines (be it impossible lines or lines that could have been cut off) wastes time. This hurts more when you do it in every node (likely multiple times) than when you do it only once every billion nodes. So the amount of work you can afford to prevent it before the cure gets worse than the disease will be several billions times larger in the case of move ordering. It turns out that ordering the moves as we typically do pays off. Now this move scoring and sorting is expensive, but it takes nowhere near a billion CPU cycles (per node). So it shouldn't be a surprise that even spending a single cycle for a billion times smaller problem doesn't pay off.

[hgm]

Note that the race problem would go away if the hash entry fitted in 8 bytes, and would be accessed atomically. E.g. if you spend 7 bits on depth, 13 bits on move, 14 bits on score and 2 bits on flag, you would have 28 bits left for signature.

The short signature can be cured by putting only 7 entries in each 64-byte cache line, and use the 8th word to store 7 'signature extension' bytes, bringing the total signature length to 36 bits. An additional advantage would be that hash misses can in most cases be concluded from only examine the relevant bytes in this extension word, which will be the first word that is fetched from memory in the burst access that fills the cache line. You wouldn't have to wait for the fetching of any of the other 7 words if none of the 7 (or how many of those the sought entry could have been stored in) extensions match. Since almost all hits would occur in the always-replace entry, it should be beneficial to use the word that is fetched second for that.

When an extension matches, there is a 99.6% probability that you have a real hit. Only in that case you will examine the 28-bit signature in the atomic entry (and thus have to wait for it being retrieved from memory). A hash store will involve writing both the entry and the extension word, which will not be atomic. But since the total signature is distributed over both, 99.4% of the corruptions by races will also corrupt the total (36-bit) signature, so that it will not be recognized.

The byte that is left in the extension word could be used for aging flags for the entries that need them (always-replace or undercut entries would not require aging). It is not very critical if these were corrupted by a race. Since most hash stores will go to always-replace entries, most corruptions will also take place through a race between two writes in an always-replace entry, which should not touch the aging flags.