en passant and hash key calculation

[wgarvin]

I'm not sure about the overall influence of such a case, but is it necessary to even have to deal with such cases?

Confusing positions with and without e.p. rights in the hash table will cost you many, many games, in Pawn endings where the e.p. capturing Pawn walks straight to promotion.

I add the side to move and the e.p. rights only to a one-time key, which is used to probe the hash. The differentially updated key only depends on the board occupation, and the repetition detection is based on that.

Right.

To bring us back to where we started, a fully correct program would have to know that it only has "e.p. rights" if there is a LEGAL enpassant capture move it can make.

But it sounds like most engines approximate that by "there is a pawn that can capture onto the enpassant square", which is probably good enough 99.9% of the time.

[hgm]

As long as you err on the save site, there is no need to be fully correct. The only consequence of assigning phantom-e.p. rights for a capture that was not legal after all, is that two separate hash entries will now be made for what formally is the same position. That could lead to a probe miss and search, while in fact there was already something in the table that could have cause a hash cutoff. No big deal, as e.p. captures in itself are already rare, let alone e.p. captures with pinned pieces or while in (discovered) check. And in practice you will get a hash hit then on the next ply, where the (phantom) rights have again disappeared.

[Desperado]

As long as you err on the save site, there is no need to be fully correct. The only consequence of assigning phantom-e.p. rights for a capture that was not legal after all, is that two separate hash entries will now be made for what formally is the same position.That could lead to a probe miss and search, while in fact there was already something in the table that could have cause a hash cutoff. No big deal, as e.p. captures in itself are already rare, let alone e.p. captures with pinned pieces or while in (discovered) check. And in practice you will get a hash hit then on the next ply, where the (phantom) rights have again disappeared.

i like your statement and explanation in this summary.

regards Michael

[Desperado]

As long as you err on the save site, there is no need to be fully correct. The only consequence of assigning phantom-e.p. rights for a capture that was not legal after all, is that two separate hash entries will now be made for what formally is the same position.That could lead to a probe miss and search, while in fact there was already something in the table that could have cause a hash cutoff. No big deal, as e.p. captures in itself are already rare, let alone e.p. captures with pinned pieces or while in (discovered) check. And in practice you will get a hash hit then on the next ply, where the (phantom) rights have again disappeared.

i like your statement and explanation in this summary.

regards Michael

PS: that is what i had in mind at the beginning of the thread.
This logic is not only effective from differing between legal/nonLegal
ep captures, it is even valid when putting in a phantom ept
with an _only double pawn push condition_.

Michael

[hgm]

True, but unlike actual e.p. captures, Pawn double-pushes are not rare at all. But if you have a good replacement algorithm, the damage of not being able to find the entry because of phantom-rights assignment will remain quite limited. In micro-Max I do assign phantom rights, to keep the code small. I never measured how much this actually would hurt performance; my guess is that it would be measurable, but very litle. (Like 1% slowdown, or so.) This also because uMax does not have a very advanced hashing scheme (always-replace, single-entry probe), so the chances for a follow-up entry not being there are appreciable.

But it is a performance issue only. While not encoding e.p. at all in the main hash can really lead to spectacular blundering. For actually claiming a draw, you would of course have to be more careful than for taking a repetition cutoff in the tree. You cannot claim on the first repetion, so you would have to count, and if you count the third occurrence, you really would have to worry about the rights. Simplest solution is to claim only on a 4th occurrence, then. (Or not at all.)

[Sven]

But it is a performance issue only. While not encoding e.p. at all in the main hash can really lead to spectacular blundering. For actually claiming a draw, you would of course have to be more careful than for taking a repetition cutoff in the tree. You cannot claim on the first repetion, so you would have to count, and if you count the third occurrence, you really would have to worry about the rights. Simplest solution is to claim only on a 4th occurrence, then. (Or not at all.)

Don't forget that it is not about claiming a repetition draw only, but that you want to prevent the opponent from escaping into repetition when the position is actually won for you. So you should not be too sloppy during search, too.

Sven

[hgm]

That depends on what you mean by "too sloppy". In a sense you must be very sloppy during search, or it would hurt tremendously: you would have to count first repetitions as draw, and ignore e.p. and castling rights, which all is in violation of the official rules, of course. And because of the implementation, I can ignore stm as well, because the wtm and btm keys are disjoints sets in the repetition table (even vs odd entries), and I check only the applicable set.

[wgarvin]

As long as you err on the save site, there is no need to be fully correct. The only consequence of assigning phantom-e.p. rights for a capture that was not legal after all, is that two separate hash entries will now be made for what formally is the same position. That could lead to a probe miss and search, while in fact there was already something in the table that could have cause a hash cutoff. No big deal, as e.p. captures in itself are already rare, let alone e.p. captures with pinned pieces or while in (discovered) check. And in practice you will get a hash hit then on the next ply, where the (phantom) rights have again disappeared.

Wait, what? That's not the ONLY consequence at all.

My first post in this thread, and a bunch of the rambling post afterwards, was about the other consequence: when the approximation is wrong (i.e. when there is a pawn next to the e.p. square but that pawn is pinned, so it has no LEGAL moves) then your rep detection algorithms will think they are two different positions when in fact they are not. I agree it should be extremely rare, so thats why I think the approximation is reasonable to do. But in this admittedly rare case, it affects correctness, not just transposition table efficiency. You might think you are winning, but allow the opponent to claim a 3-fold rep draw, and your engine might not believe its a claimable draw when it is.

Anyway, for those who set out to write a zero-bug engine which always plays correct chess, its worth considering all the implications before they choose which way to implement this.

OTOH I've never seen an example of an engine-engine game that was drawn because of this extremely rare situation. If anyone can find one that would sure be interesting!

[hgm]

My first post in this thread, and a bunch of the rambling post afterwards, was about the other consequence: when the approximation is wrong (i.e. when there is a pawn next to the e.p. square but that pawn is pinned, so it has no LEGAL moves) then your rep detection algorithms will think they are two different positions when in fact they are not.

No it would not: it would think they are the same, because it would even have thought they were the same if it did have a legal e.p. capture in one and not the other, in the optimum implementation.

And if you think you are winning, it would be completely pointless to first go back to a position that you had seen before. If you can win from that position, even without playing the e.p. capture that was illegal anyway, and will be even more illegal now because you lost the right to do it, you should have played that winning move in the first place. So your opponent won't get the chance to claim a draw. (Which he would not have anyway, because it was only the first repetition.)

[wgarvin]

My first post in this thread, and a bunch of the rambling post afterwards, was about the other consequence: when the approximation is wrong (i.e. when there is a pawn next to the e.p. square but that pawn is pinned, so it has no LEGAL moves) then your rep detection algorithms will think they are two different positions when in fact they are not.

No it would not: it would think they are the same, because it would even have thought they were the same if it did have a legal e.p. capture in one and not the other, in the optimum implementation.

We might be talking about two different approximations or something. I am referring to an approximation where you include the e.p. square in your zobrist key, if and only if there is a STM pawn positioned so that it could make an e.p. capture (but regardless of whether that capture would leave STM in check). That approximation will erroneously give you two different e.p. keys in the case where the STM pawn is there but is actually pinned. Which is probably very rare, but seems at least possible.

But, I guess it is irrelevant for any practical purposes, because...

And if you think you are winning, it would be completely pointless to first go back to a position that you had seen before.

That's a very good point. In the 'X'...'Y'...'Y' example, even if you don't recognize the first occurrence of Y as a repetition of X, you are not very likely to return to the Y position the second time if you think you are winning, because you almost certainly have some other move that improves your score (otherwise why would you think you are winning!)

Or rephrased: for him to claim a draw on the third occurrence, you'd have to let the Y position occur at least twice on the board, which you certainly won't do if you think you are winning. Especially for programs that return a draw score after they see one occurrence on the board plus one occurrence in the tree.

So maybe this "very rare" case I was worried about can't really happen, and is not worth worrying about.