en passant and hash key calculation

[Fguy64]

Here's a dumb question. One of the factors that goes into the determination of a position is the existence of an e.p target square. Does the e.p. target square exist only when an e.p. capture can be made?

This question arises become it has been suggested that I made a mistake with my hash key calculation. I have been including a hash key component when a pawn moves forward two squares, regardless of whether or not there is a capture possible. As I think about it, this seems wrong, in that I eliminate a significant number of possible hash key matches and slow down my search.

[Edmund]

The fen standard requires you to specify the e.p. target as soon as a pawn has moved 2 squares forward.

For the internal calculation however, for the reason you stated (it unnecissarily avoids certain Transposition table hits) it makes sense to only change the Zobrist key if the e.p. target square is under attack by an opponent pawn.

[Fguy64]

The fen standard requires you to specify the e.p. target as soon as a pawn has moved 2 squares forward.

For the internal calculation however, for the reason you stated (it unnecissarily avoids certain Transposition table hits) it makes sense to only change the Zobrist key if the e.p. target square is under attack by an opponent pawn.

Noted, thanks

[wgarvin]

The fen standard requires you to specify the e.p. target as soon as a pawn has moved 2 squares forward.

For the internal calculation however, for the reason you stated (it unnecissarily avoids certain Transposition table hits) it makes sense to only change the Zobrist key if the e.p. target square is under attack by an opponent pawn.

Interesting. So you should really keep two flags in the board state: one for "last move was a double-pawn push" and one for "there is a valid enpassant capture move".

[Edit: for the enpassant capture to be legal, it has to not leave you in check. So in order to calculate the proper zobrist key for the position after a double-pawn push, you have to examine that possibility. The effect on the hash table should be negligible, but there's one important reason to do this: so that repetition detection using the zobrist keys will know whether the position with the enpassant square is different or not from the position without it.]

[Fguy64]

The fen standard requires you to specify the e.p. target as soon as a pawn has moved 2 squares forward.

For the internal calculation however, for the reason you stated (it unnecissarily avoids certain Transposition table hits) it makes sense to only change the Zobrist key if the e.p. target square is under attack by an opponent pawn.

Interesting. So you should really keep two flags in the board state: one for "last move was a double-pawn push" and one for "there is a valid enpassant capture move".

[Edit: for the enpassant capture to be legal, it has to not leave you in check. So in order to calculate the proper zobrist key for the position after a double-pawn push, you have to examine that possibility. The effect on the hash table should be negligible, but there's one important reason to do this: so that repetition detection using the zobrist keys will know whether the position with the enpassant square is different or not from the position without it.]

Why bother with the standard . It seems pointless to adhere to the FEN standard in this situation, unless having your engine produce standard fen keys as output is a oal.

As far as proper zKey calc taking into account whether you put your king into check, I donb't see that either. Even if you weren't doing hashing at all, the position would still get rejected, so how is it that such an improperly calculated key would get stored, so why bother with special providions for the hash key calculation? Am I missing something?

[wgarvin]

Why bother with the standard . It seems pointless to adhere to the FEN standard in this situation, unless having your engine produce standard fen keys as output is a oal.

Its probably not that important as far as outputting PGN or FEN goes; as long as the engine can accept FEN input of this form (where it says there's an enpassant square but there's no legal enpassant capture there) then it should be fine. However, see below..

As far as proper zKey calc taking into account whether you put your king into check, I donb't see that either. Even if you weren't doing hashing at all, the position would still get rejected, so how is it that such an improperly calculated key would get stored, so why bother with special providions for the hash key calculation? Am I missing something?

The zobrist key being calculated, is the one in the position BEFORE you make an enpassant capture move. Call this position "X". If you make some other move from this position (a reversible one) then its possible that the next few moves will bring you back to a position which is identical to position X, except that it doesn't have any enpassant capture moves. Call this position Y. Now you make a few more moves and you repeat position Y again.

The question is: is this the third repetition of Y, or only the second? You need to know the answer to handle rep draw scoring properly. Knowing the answer requires you to know whether X and Y are actually the same position or not. So in other words: were there any legal enpassant capture moves in position X, or not?

So when calculating the zobrist key for position X (i.e. in the makemove for the double pawn push which resulted in position X) you should probably determine whether there are any LEGAL enpassant captures in the new position. If there are, you modify the zobrist key so that it will be different from the key of position Y. If there aren't, you leave the key the same as the one for Y.

Then later, when position Y has popped up a couple of times, and you scan your array of "zobrist keys of previous positions since the last irreversible move" to find out if its a repeat, everything will work properly.


I imagine a lot of engines get by fine without handling this properly. Perhaps this kind of repetition is extremely unlikely? Buf if you're trying to make a 100% correct engine, then it might be worth implementing.

[Sven]

The fen standard requires you to specify the e.p. target as soon as a pawn has moved 2 squares forward.

For the internal calculation however, for the reason you stated (it unnecissarily avoids certain Transposition table hits) it makes sense to only change the Zobrist key if the e.p. target square is under attack by an opponent pawn.

Interesting. So you should really keep two flags in the board state: one for "last move was a double-pawn push" and one for "there is a valid enpassant capture move".

[Edit: for the enpassant capture to be legal, it has to not leave you in check. So in order to calculate the proper zobrist key for the position after a double-pawn push, you have to examine that possibility. The effect on the hash table should be negligible, but there's one important reason to do this: so that repetition detection using the zobrist keys will know whether the position with the enpassant square is different or not from the position without it.]

Why bother with the standard . It seems pointless to adhere to the FEN standard in this situation, unless having your engine produce standard fen keys as output is a oal.

As far as proper zKey calc taking into account whether you put your king into check, I donb't see that either. Even if you weren't doing hashing at all, the position would still get rejected, so how is it that such an improperly calculated key would get stored, so why bother with special providions for the hash key calculation? Am I missing something?

There are two different issues to consider:
1. how to keep track of the ep target square as part of the internal position state of an engine,
2. how to update the hash key w.r.t ep target.

As to 1., this has been discussed several times in CCC. While the FEN standard defines how the ep target square is encoded in an FEN, it is quite common for the internal state representation in an engine to have an "undefined" (not set) ep target square if there is no enemy pawn left or right to the pawn that just made a double step. So also an ep target square coming as input from an FEN would be mapped internally to "not set" in this case. There have been different opinions, however, about the best handling of the rare case that there is an enemy pawn left or right that could potentially do an ep capture but the capture would in fact be illegal, e.g. due to pins.

I would currently recommend to stick with the simple approach to check for left or right enemy pawns only but not for ep legality, since this is the most common approach, is easy and fast to implement and covers most exceptional cases.

As to 2., this is the simple part where no choices can be made. You update your hash key exactly if the ep target of the previous and the new position differ, like in this pseudocode:

Code: Select all

if (prevPos.epTarget != currPos.epTarget) {
    if (prevPos.epTarget != NoSquare) {
        hashKey XOR (zobrist key for prevPos.epTarget);
    }
    if (currPos.epTarget != NoSquare) {
        hashKey XOR (zobrist key for currPos.epTarget);
    }
}

Sven

[Fguy64]

Why bother with the standard . It seems pointless to adhere to the FEN standard in this situation, unless having your engine produce standard fen keys as output is a oal.

Its probably not that important as far as outputting PGN or FEN goes; as long as the engine can accept FEN input of this form (where it says there's an enpassant square but there's no legal enpassant capture there) then it should be fine. However, see below..

As far as proper zKey calc taking into account whether you put your king into check, I donb't see that either. Even if you weren't doing hashing at all, the position would still get rejected, so how is it that such an improperly calculated key would get stored, so why bother with special providions for the hash key calculation? Am I missing something?

The zobrist key being calculated, is the one in the position BEFORE you make an enpassant capture move. Call this position "X". If you make some other move from this position (a reversible one) then its possible that the next few moves will bring you back to a position which is identical to position X, except that it doesn't have any enpassant capture moves. Call this position Y. Now you make a few more moves and you repeat position Y again.

The question is: is this the third repetition of Y, or only the second? You need to know the answer to handle rep draw scoring properly. Knowing the answer requires you to know whether X and Y are actually the same position or not. So in other words: were there any legal enpassant capture moves in position X, or not?

So when calculating the zobrist key for position X (i.e. in the makemove for the double pawn push which resulted in position X) you should probably determine whether there are any LEGAL enpassant captures in the new position. If there are, you modify the zobrist key so that it will be different from the key of position Y. If there aren't, you leave the key the same as the one for Y.

Then later, when position Y has popped up a couple of times, and you scan your array of "zobrist keys of previous positions since the last irreversible move" to find out if its a repeat, everything will work properly.


I imagine a lot of engines get by fine without handling this properly. Perhaps this kind of repetition is extremely unlikely? Buf if you're trying to make a 100% correct engine, then it might be worth implementing.

Well thanks, I see what you mean, My remark about why bother if it doesn't get stored was ill considered. The position where an otherwise legal ep capture is rejected because of check is is the same as the subsequent two positions in which the ep capture is not otherwise legal because it wasn't done right away, therefore you take the possibility of check into account and don't set the ep capture square ergo three repetitions and not two.

p.s. to Sven I haven't bothered to do three fold repetition in my engine, it's just not a priority. Maybe if I run out of ideas, or decide I want to be competetive, I'll take what you say into account.

[Sven]

Why bother with the standard . It seems pointless to adhere to the FEN standard in this situation, unless having your engine produce standard fen keys as output is a oal.

Its probably not that important as far as outputting PGN or FEN goes; as long as the engine can accept FEN input of this form (where it says there's an enpassant square but there's no legal enpassant capture there) then it should be fine. However, see below..

As far as proper zKey calc taking into account whether you put your king into check, I donb't see that either. Even if you weren't doing hashing at all, the position would still get rejected, so how is it that such an improperly calculated key would get stored, so why bother with special providions for the hash key calculation? Am I missing something?

The zobrist key being calculated, is the one in the position BEFORE you make an enpassant capture move. Call this position "X". If you make some other move from this position (a reversible one) then its possible that the next few moves will bring you back to a position which is identical to position X, except that it doesn't have any enpassant capture moves. Call this position Y. Now you make a few more moves and you repeat position Y again.

The question is: is this the third repetition of Y, or only the second? You need to know the answer to handle rep draw scoring properly. Knowing the answer requires you to know whether X and Y are actually the same position or not. So in other words: were there any legal enpassant capture moves in position X, or not?

So when calculating the zobrist key for position X (i.e. in the makemove for the double pawn push which resulted in position X) you should probably determine whether there are any LEGAL enpassant captures in the new position. If there are, you modify the zobrist key so that it will be different from the key of position Y. If there aren't, you leave the key the same as the one for Y.

Then later, when position Y has popped up a couple of times, and you scan your array of "zobrist keys of previous positions since the last irreversible move" to find out if its a repeat, everything will work properly.


I imagine a lot of engines get by fine without handling this properly. Perhaps this kind of repetition is extremely unlikely? Buf if you're trying to make a 100% correct engine, then it might be worth implementing.

Well thanks, I see what you mean, My remark about why bother if it doesn't get stored was ill considered. The position where an otherwise legal ep capture is rejected because of check is is the same as the subsequent two positions in which the ep capture is not otherwise legal because it wasn't done right away, therefore you take the possibility of check into account and don't set the ep capture square ergo three repetitions and not two.

Actually I don't think this is about "first or second repetition" (second or third occurrence), it is about "detecting a repetition at all or not dececting it".

If position X has an ep target square set and there is at least one adjacent enemy pawn but all pseudo-legal ep captures are in fact illegal moves, and if the same position occurs again after 4 + 2*N plies, then all pieces are on exactly the same locations so there were no pawn moves in the meantime, and so there is no ep target square set now. But you miss to detect this as a (first) repetition since position X has the ep target square set and the current hasn't. And therefore you don't see a threefold (second repetition) later on, too.

As Wylie mentioned, this is a question of 100% accuracy. I have "promoted" this already in the past but I also admit that it is a very rare case of missing a repetition, and perfectly covering it requires some additional legality testing intelligence in the code that is responsible for setting the internal ep target square after a pawn double step.

Again my hint: this is not related to updating the hash key for ep target squares but to keeping track of the internal ep target square of the engine.

Sven

[Sven]

p.s. to Sven I haven't bothered to do three fold repetition in my engine, it's just not a priority. Maybe if I run out of ideas, or decide I want to be competetive, I'll take what you say into account.

You define your priorities. I can only say that a chess engine that does not implement repetition detection cannot be considered a chess engine, it is just boring. It will be unable to win a won position in most cases.

Also my posts - including the second one I just sent - were not only related to repetition detection but mostly to your original question which was about how to deal with ep target and hash key. So please reconsider what you should take into account and what not

Sven