hash collisions

[syzygy]

So it is very much necessary to check the validity of the TT move (or at least to ensure that an invalid move cannot corrupt the data structures).

Only the latter. The hash move can be as illegal as you want. You just need a robust MakeMove / UnMake. E.g. take care to restore both what is captured by the King and by the Rook, after a castling, and put back what you actually moved, rather than assuming it was a King and a Rook.

At least the latter, but I don't think there is much to be gained in a practical engine by not fully checking move validity. But who knows, maybe somebody wants to write a patch for SF. (But who wants to deal with pawns on the 1st and 8th ranks, positions without one of the kings, etc.? Lots of common assumptions start to fail once one allows illegal moves.)

[hgm]

I you return a +INF score for any move that captures a King, positions without King can never be reached. This is part of my normal search anyway, not just to catch faulty hash moves. Last-rank Pawns might automatically appear as blocked Pawns. Promotion moves applied to non-Pawns or empty squares are usually the most tricky. But promotions are rare, and you can afford a lot of overhead in their execution with no measurable impact on the total performance. So there a check if the moved piece is indeed a Pawn of the correct color would be affordable, and enough to keep you safe. (And score themove as -INF when it fails the test.)

[Terje]

I you return a +INF score for any move that captures a King, positions without King can never be reached. This is part of my normal search anyway, not just to catch faulty hash moves. Last-rank Pawns might automatically appear as blocked Pawns. Promotion moves applied to non-Pawns or empty squares are usually the most tricky. But promotions are rare, and you can afford a lot of overhead in their execution with no measurable impact on the total performance. So there a check if the moved piece is indeed a Pawn of the correct color would be affordable, and enough to keep you safe. (And score themove as -INF when it fails the test.)

Is this really better performance-wise than a (pseudo-)legality test on hash moves?

[chrisw]

I you return a +INF score for any move that captures a King, positions without King can never be reached. This is part of my normal search anyway, not just to catch faulty hash moves. Last-rank Pawns might automatically appear as blocked Pawns. Promotion moves applied to non-Pawns or empty squares are usually the most tricky. But promotions are rare, and you can afford a lot of overhead in their execution with no measurable impact on the total performance. So there a check if the moved piece is indeed a Pawn of the correct color would be affordable, and enough to keep you safe. (And score themove as -INF when it fails the test.)

Is this really better performance-wise than a (pseudo-)legality test on hash moves?

For an engine that does tests or stats BETWEEN selecting a move and actually executing it, almost certainly not. Pre move tests might be IsGoodSee or IsCheck and so on, time spent evaluating those would then be completely wasted.
Actually it remains beyond me, the purpose of most of the comments in this thread. Test potentially invalid moves from history sources (such as hash) for validity. End of discussion.

[mar]

Is this really better performance-wise than a (pseudo-)legality test on hash moves?

You need a full legality test for hashmoves. pseudo-legal move needs valid context (position), in the case of a hash collision, you get random junk unrelated to the position you're probing.

a pseudo-legal move comes from pseudo-legal move generator and doesn't need full validation, the only thing you need is to make sure you don't leave your own king in check

back on topic, to sum up there are several possibilities:
1) do nothing and bet that your hashkey is big enough that you get no collision and the engine doesn't crash
(xor trick may help reducing the probability since it acts as kind-of a checksum)
2) check your hashmove for legality (if you use a staged move generator)
3) use full legal movegen and simply order the hashmove first (this is what Lucas does in Demolito)
4) postpone validation the way hgm does (=make sure your engine doesn't crash on invalid hashmove)

Not sure how much time staged move generators really saves as full validation gets complicated so perhaps the best price-complexity would be #3
(plus you can easily detect single-reply for free, not that it would matter elo-wise)

[hgm]

I still think there is too much obsession with full legality. In general engines would not care at all whether a move is pseudo-legal or not; a non-pseudo-legal move in one chess variant could be pseudo-legal in another variant that the engine has no difficulty in handling. As long as you move a piece of your own to some empty square or to a square occupied by an opponent it seems the move would always be completely harmless. In an engine that uses pseudo-legal move generation and sorting, and defers the legality test to MakeMove (as is usually the most efficient way), such non-pseudo-legal moves would be properly tested for leaving their King in check automatically.

The only aspects of the hash move you would have to test to make sure it cannot crash your engine would be:
* own piece on the from-square
* not an own piece on the to-square
* does not capture enemy King
* if it is a special move (rare case!) it must satisfy some extra conditions peculiar to that kind of move (which can depend on how you implemented execution of that move). Like on castling you might want to make sure the implied Rook move also satifies the above conditions, and on promotion that the piece was a Pawn.

If those conditions are satisfied you can safely inject it into your normal move-processing.

[Terje]

Is this really better performance-wise than a (pseudo-)legality test on hash moves?

You need a full legality test for hashmoves. pseudo-legal move needs valid context (position), in the case of a hash collision, you get random junk unrelated to the position you're probing.

a pseudo-legal move comes from pseudo-legal move generator and doesn't need full validation, the only thing you need is to make sure you don't leave your own king in check

back on topic, to sum up there are several possibilities:
1) do nothing and bet that your hashkey is big enough that you get no collision and the engine doesn't crash
(xor trick may help reducing the probability since it acts as kind-of a checksum)
2) check your hashmove for legality (if you use a staged move generator)
3) use full legal movegen and simply order the hashmove first (this is what Lucas does in Demolito)
4) postpone validation the way hgm does (=make sure your engine doesn't crash on invalid hashmove)

Not sure how much time staged move generators really saves as full validation gets complicated so perhaps the best price-complexity would be #3
(plus you can easily detect single-reply for free, not that it would matter elo-wise)

No, you don't need a full legality test on hash moves. MakeMove takes care of legality testing pseudo-legal moves in the position already, assuming you use pseudo-legal movegen, thus a pseudo-legality test of the hash move is sufficient.

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.

For reference, here is the pseudo-legality test in my engine. Captured pieces are encoded in the move and extracted with capturing(move), and will be empty for non-captures and en passants.

[hgm]

No, you don't need a full legality test on hash moves. MakeMove takes care of legality testing pseudo-legal moves in the position already, assuming you use pseudo-legal movegen, thus a pseudo-legality test of the hash move is sufficient.

It is especially the pseudo-legality that is mostly irrelevant. It is hard to imagine code that would break when you move a Knight as a Rook, or have a Bishop jump over 3 pieces. What could be trouble is moving a piece of the wrong color (checking yourself unexpectedly and thus undetected!). Or perhaps capturing a piece of your own (although a careful implementation of MakeMove can usually avoid that without any overhead).

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.

Castling and promotion are rare in the tree, (in fact castling might not occur in the entire game, as it was already done in the book line!) so even doing very complex things that only apply to these special cases has no measurable impact on the speed at all. And the required actions to make the code robust are very cheap. My MakeMove() would normally record the type of the moved piece anyway, in order to put it back. So it is just a matter of making sure you put back that piece, rather than the one on the to-square or a hard-coded Pawn. That doesn't really involve any extra work.

Searching 'impossible positions' (or, more accurately, positions that should not have occurred in the tree at that point) would only be done in the case of a hash corruption, which should be even rarer. Like an extra QS every few minutes. You don't want your engine to crash every few minutes, but a few microseconds slowdown per minute is entirely acceptable.

So in practice, what you save is what the the legality-testing of the hash move took.

P.S.

Why do you distinguish the cases KNIGHT, BISHOP, ROOK and QUEEN when you are doing the same thing in all of those?

You don't seem to purely test pseudo-legality here, as having a different capture victim doesn't affect pseudo-legality of the move.

[mar]

No, you don't need a full legality test on hash moves. MakeMove takes care of legality testing pseudo-legal moves in the position already, assuming you use pseudo-legal movegen, thus a pseudo-legality test of the hash move is sufficient.

I certainly do hashmove/killer legality check inside my staged movegen (before next move is selected), but that doesn't really change anything.
(killers use a slightly more relaxed validation)

you need to consider a "move" that comes from a hash collision as a random sequence of bits,
it's not what I'd call pseudo-legal in a given position (random != pseudo-legal),
so for me a pseudo-legal move has a valid source/target, ep cap, promotion, castling etc. => no need to check anything except that it doesn't leave own king in check, which is much easier to do than a full validation (obviously)

[chrisw]

Is this really better performance-wise than a (pseudo-)legality test on hash moves?

You need a full legality test for hashmoves. pseudo-legal move needs valid context (position), in the case of a hash collision, you get random junk unrelated to the position you're probing.

a pseudo-legal move comes from pseudo-legal move generator and doesn't need full validation, the only thing you need is to make sure you don't leave your own king in check

back on topic, to sum up there are several possibilities:
1) do nothing and bet that your hashkey is big enough that you get no collision and the engine doesn't crash
(xor trick may help reducing the probability since it acts as kind-of a checksum)
2) check your hashmove for legality (if you use a staged move generator)
3) use full legal movegen and simply order the hashmove first (this is what Lucas does in Demolito)
4) postpone validation the way hgm does (=make sure your engine doesn't crash on invalid hashmove)

Not sure how much time staged move generators really saves as full validation gets complicated so perhaps the best price-complexity would be #3
(plus you can easily detect single-reply for free, not that it would matter elo-wise)

No, you don't need a full legality test on hash moves. MakeMove takes care of legality testing pseudo-legal moves in the position already, assuming you use pseudo-legal movegen, thus a pseudo-legality test of the hash move is sufficient.

that would assume you already built a pseudo legal move list to check against. It’s way cheaper to carry out a validation on the assumption your hash move could be any old junk, rather than perform a genmove and then a list check. One of the advantages of generating recommendations out of history (apart from move order) is that you may be able to get away with never doing a genmove at all.

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.

For reference, here is the pseudo-legality test in my engine. Captured pieces are encoded in the move and extracted with capturing(move), and will be empty for non-captures and en passants.