repetition detection

[Anonymous]

I have discovered a problem with detecting repetitions using hash keys.
use the following game for reference:
8/3k4/8/8/6p1/3K4/5P2/8 w - - 0 1
1. f4 Kc7 2. Kc3 Kd7 3. Kd3 Kc7 4. Kc3 Kd7 5. Kd3 1/2-1/2

The problem is that after 1. f4, an enpassant capture is available and the hash key must be changed to reflect that, otherwise if you encounter the same position later but there is no enpassant capture available you may return an incorrect value.
So assuming the engine changes the hash key to reflect available enpassant captures, after 3. Kd3 the engine will think it is the first time it has encountered this position. However, according to the rules of chess, this position has been encountered twice.
Any thoughts?

[Rémi Coulom]

I have discovered a problem with detecting repetitions using hash keys.
use the following game for reference:
8/3k4/8/8/6p1/3K4/5P2/8 w - - 0 1
1. f4 Kc7 2. Kc3 Kd7 3. Kd3 Kc7 4. Kc3 Kd7 5. Kd3 1/2-1/2

The problem is that after 1. f4, an enpassant capture is available and the hash key must be changed to reflect that, otherwise if you encounter the same position later but there is no enpassant capture available you may return an incorrect value.
So assuming the engine changes the hash key to reflect available enpassant captures, after 3. Kd3 the engine will think it is the first time it has encountered this position. However, according to the rules of chess, this position has been encountered twice.
Any thoughts?

From the FIDE laws of chess:
http://www.fide.com/official/handbook.asp?level=EE101

Positions as in (a) and (b) are considered the same, if the same player has the move, pieces of the same kind and colour occupy the same squares, and the possible moves of all the pieces of both players are the same.
Positions are not the same if a pawn that could have been captured en passant can no longer be captured or if the right to castle has been changed temporarily or permanently.

[Anonymous]

That short game in my first post was obtained by playing those moves in the chessbase gui. Does this mean the gui is wrong? And thx for the reply!

[Rémi Coulom]

That short game in my first post was obtained by playing those moves in the chessbase gui. Does this mean the gui is wrong? And thx for the reply!

Yes, the gui is wrong. I do not know the chessbase gui but, from what I can read in different forums, it has an extremely bad reputation. Engines are great, but the interface is poor, apparently. One more bug is not suprising.

R?mi

[Reinhard Scharnagl]

Hi R?mi,

... or if the right to castle has been changed temporarily ...

I hardly can imagine what a temporarily change of castling rights could be (when nothing else at the board would change). Could you please supply me with an example, with two identic positions and temporarily changed castling rights.

Reinhard.

[Rémi Coulom]

Hi R?mi,

... or if the right to castle has been changed temporarily ...

I hardly can imagine what a temporarily change of castling rights could be (when nothing else at the board would change). Could you please supply me with an example, with two identic positions and temporarily changed castling rights.

Reinhard.

That is not possible, of course.

[Reinhard Scharnagl]

Hello R?mi,

so you agree with me in that this FIDE law contains a little bit nonsense in that point. The word "temporarily" is silly here.

Reinhard.

[Guenther Simon]

[Event "Uncastling rep Test"]
[Site "ESPRESSO"]
[Date "2005.01.08"]
[White "?"]
[Black "?"]
[Result "*"]

1.e4 e5 2.Nf3 Nc6 3.Bc4 Nf6 4.0-0 Be7 5.Re1 Bf8 6.Kf1 Be7 7.Ke2 Bf8 8.Rg1 Be7 9.Ke1 Bf8 10.Rh1 *

Very artificial but you see that the position after 10.Rh1 is
_not_ the same as after Nf6 according to above FIDE rules

Guenther

[Dann Corbit]

Hello R?mi,

so you agree with me in that this FIDE law contains a little bit nonsense in that point. The word "temporarily" is silly here.

Reinhard.

No. There are clear cases where there is a temporary change of castling rights. For example, right here, neither side can castle:
r1bqk2r/pppp2pp/n4p1n/2b1p3/2B1P3/N4P1N/PPPP2PP/R1BQK2R b KQkq -

But here, both sides can castle in the same game, because the castle path is no longer attacked by a bishop:
r1bqk2r/pppp2pp/n2b1p1n/4p3/4P3/N2B1P1N/PPPP2PP/R1BQK2R b KQkq -

Sorry about no pictures. I don't know how to draw them in here.

[Reinhard Scharnagl]

Dann,

I agree that castling rights could be affected temporarily.

But here it has been mentioned as an ADDITIONAL criterium when otherwise identic positions should be regarded as different. And in that context this is nonsense, because such pairs of positions do not exist.

If you have two identic positions with different castling rights, the rights always will have been changed PERMANENTLY. Thus the three last words "temporarily or permanently" are completely unnecessary, and especially the word "temporarily" is misleading.

Reinhard.

[Sven Schüle]

Hi,

the original topic of this thread was repetition detection with en passant, so I suggest to come back to it. The castling question has been solved now, I think.

"Repetition and en passant" has some more potential to be considered.

The PGN standard says about en passant target squares in FENs (http://www.yacdb.com/pgn/pgn_1616.htm#SEC16.1.3.4):

Code: Select all

16.1.3.4: En passant target square
The fourth field is the en passant target square. If there is no en passant target square then the single character symbol "-" appears. If there is an en passant target square then is represented by a lowercase file character immediately followed by a rank digit. Obviously, the rank digit will be "3" following a white pawn double advance (Black is the active color) or else be the digit "6" after a black pawn double advance (White being the active color).

An en passant target square is given if and only if the last move was a pawn advance of two squares. Therefore, an en passant target square field may have a square name even if there is no pawn of the opposing side that may immediately execute the en passant capture.


The last sentence is interesting. It means that engines should not implement their repetition detection code (and/or "makemove" code that affects the ep square information of the new position) exactly after that FEN rule because otherwise they would end up in not detecting the following:

A pawn makes a double step but there is no enemy pawn present "that may immediately execute the en passant capture". Now the next, say, four plies are such that the position of all pieces after the pawn double step is repeated (and castling rights did not change, of course). According to FIDE rules this is a repetition because the right to make an ep capture is identical in both positions (i.e., no ep capture possible). Example:
[diag]8/3k4/8/8/8/3K4/5P2/8 w - - 0 1[/diag]
8/3k4/8/8/8/3K4/5P2/8 w - - 0 1

FEN from WinBoard 4.2.7 after 1.f4:
8/3k4/8/8/5P2/3K4/8/8 b - f3 0 1
FEN from WinBoard 4.2.7 after 1.f4 Ke7 2.Ke3 Kd7 3.Kd3:
8/3k4/8/8/5P2/3K4/8/8 b - - 0 3

So I think that engines should either set the ep square after makemove() only if an enemy pawn is present to the left or to the right (this is what "Surprise" does, for example), or should set the ep square as FEN specification requires but then consider the "enemy pawn condition" during repetition detection if a nonzero ep square is found for both positions being compared (perhaps only for the current pos).

How do the other engine authors address this?

- And now I even want to top it. What about pins?

Consider this example:
[diag]8/8/6k1/8/4K1pr/8/5P2/6R1 w - - 0 1[/diag]
8/8/6k1/8/4K1pr/8/5P2/6R1 w - - 0 1

Here after 1.f4 no ep capture is allowed because Pg4 is pinned. But according to the standard we get the following FEN after 1.f4:
8/8/6k1/8/4KPpr/8/8/6R1 b - f3 0 1

Does anyone detect in his/her engine that the ep square should be empty in this case, too? If so, how do you do it?

Cheers,
Sven

[Rémi Coulom]

How do the other engine authors address this?

I consider that the PGN standard is broken and should be fixed. The en-passant target square should be set only if an en-passant capture can be actually played. That's how I handle it in my program.

R?mi

[Reinhard Scharnagl]

Hi R?mi,

Smirf handles it that way, that an e.p. flag internally is set then and only then, when a double moved pawn would be placed beside an opponent's pawn. But it is irrelevant whether then an e.p. capture is possible in the following or not. That seems to be a good compromise.

Reinhard.

[Sven Schüle]

Hi R?mi,

Smirf handles it that way, that an e.p. flag internally is set then and only then, when a double moved pawn would be placed beside an opponent's pawn. But it is irrelevant whether then an e.p. capture is possible in the following or not. That seems to be a good compromise.

Reinhard.

Hi Reinhard and all others,

so Surprise and Smirf do essentially the same, both do not detect a repetition in my last example with the pinned pawn on g4. Strictly spoken, both engines do not conform to the FIDE rules (and I'm afraid many others don't, too) by not considering pins in that case.

But I'm already happy that there are at least a few other ones who did not implement it by strictly following the PGN/FEN standard.

Any other remarks from someone else? Anyone detecting the pin case?

What about LGPGNVER and other game checking tools, has anyone tested this stuff with them? I did not do it so far.

Cheers,
Sven

[Anonymous]

Yikes, I didnt think of some of that stuff .
So it would seem that a position with an enpassant target square is different from its counterpart position without an enpassant target square only if:
1. the ep target square is attacked by a pawn of the side to move.
2. the pawn attacking the ep target square isn't pinned.
3. nobody is in check.
Sound right?

[Peter Fendrich]

Any other remarks from someone else? Anyone detecting the pin case?

In Terra I had code to detect the example you gave with the pinned g4. It costs too much for such rare cases and when I came across the following example, that wasn't covered by my code, I throw it away and decided to live with it. Even in my new program, Alaric, it is the same.
[diag]8/8/6K1/8/4k1pR/8/5P2/1r6 w - - 0 1[/diag]
8/8/6K1/8/4k1pR/8/5P2/1r6 w - - 0 1
After f4 the e.p. is not legal.

/Peter

[Anonymous]

Oops, just found an exception to rule 3(nobody is in check).
[diag]8/8/8/4k3/5Pp1/8/1K6/8 b - f3 0 1[/diag]
8/8/8/4k3/5Pp1/8/1K6/8 b - f3 0 1
here black can do the enpassant capture to get out of check

[Alessandro Scotti]

here black can do the enpassant capture to get out of check

...a good candidate for being left out from a "check evasion" move generator! In fact I didn't thought of it until I implemented perft() in my engine, and saw that the numbers didn't match...

[Reinhard Scharnagl]

Hi Sven,

...both engines do not conform to the FIDE rules...

I do not understand this. FIDE has no competence to demand how chess engines should handle the e.p. flag internally. They do make clear, what a legal e.p. capture is. And according to that Smirf is producing all legal and only legal moves.

Regards, Reinhard.

[Rémi Coulom]

Hi R?mi,

Smirf handles it that way, that an e.p. flag internally is set then and only then, when a double moved pawn would be placed beside an opponent's pawn. But it is irrelevant whether then an e.p. capture is possible in the following or not. That seems to be a good compromise.

Reinhard.

That's the way I do it. I had read Sven's post too quickly, and had not noticed the pin part. I had not thought about this possibility before. I do not expect that it would cause any serious problem when playing games, anyways.

R?mi