ep and castle rights hashing

[syzygy]

Interesting, it seems Rule 9.2 was reworded rather recently in attempt to clarify it...

The wiki still has:

9.2 The game is drawn, upon a correct claim by the player having the move, when the same position, for at least the third time (not necessarily by a repetition of moves)

a) is about to appear, if he first writes his move on his scoresheet and declares to the arbiter his intention to make this move, or
b) has just appeared, and the player claiming the draw has the move.


Positions as in (a) and (b) are considered the same, if the same player has the move, pieces of the same kind and color 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 in this manner be captured or if the right to castle has been changed temporarily or permanently.

I found some discussion on the old rule here.

In my view the new rule removes one unclarity in that it clearly defines that castling rights are only lost after making the move that loses them, even if that move was forced, but it forgets to state that positions with different castling rights are different...

[rtitle]

OK, I concede. The FIDE rules are badly written, but after digging some more I agree they intended for the right to castle to be factored in. It's stated it in a very indirect way in the rules.

This Wikipedia article is relevant, particularly the Karpov-Miles example: http://en.wikipedia.org/wiki/Threefold_ ... on#History

Rich Title

[bob]

re: "it is simply wrong and arrogant to call [using the TT to detect repetitions] a mistake. Many excellent programmers have [done that]"

Ouch. Let me re-phrase. I *myself* went down the path of using my TT to detect repetitions. Then I decided it was a mistake for the reasons I gave in that earlier post, and I changed over to the simple walk-backward-in-the-move-history approach. The engine is much better for the change because now I'm not thrashing my TT with entries that are just there to detect repetitions. I'm just relaying my own experience.

Rich Title

There are viable tt solutions. Ferret used a small (2K entry) ttable for repetition detection. When you reach a position, you store the key, when you leave the position, you remove the entry. You use a counter so that if a position is already there, you just increment the counter. If it hits 2 or 3 (depends on how you want to implement repetition) you return draw immediately. Works reliably, and works in a threaded program. You can have at most 100 entries from the actual game history, otherwise you get into 50-move draws, and each time you actually make an irreversible move, you clear the ttable (for moves in actual game history, not moves searched during this iteration).

Nothing wrong with the approach, except for the slight overhead of having to "add" and "remove" entries at the top and bottom of search. With the list approach there is no removal at all, just adding. Seemed to be a wash in terms of cost when Bruce and I compared notes back in the late 90's...

I probably would not use the regular ttable because it is big and you see extra TLB misses if you are not very lucky. The small table doesn't seem to cause that problem.

[syzygy]

Ferret used a small (2K entry) ttable for repetition detection. When you reach a position, you store the key, when you leave the position, you remove the entry. You use a counter so that if a position is already there, you just increment the counter. If it hits 2 or 3 (depends on how you want to implement repetition) you return draw immediately.

Instead of storing counters one could also initialise the table at the start of the search with all positions that have been seen twice on the board. If the search now finds that a position already occurs in the table, this means that it is either the third repetition of a positon that was already twice on the board, or a repetition of a position that occurred during the search. Both cases should be scored as a draw.

(If you want any first repetition to score as a draw, then at the start of the search simply initialise the table with the game history since the last move that reset the 50-move counter.)

This trick generalises to other implementations. With the linear list approach one could initialise the list at the start of the search with all positions that have been seen twice on the board. Now there is never a need, during the search, to determine whether a particular position occurs twice in the list.

The implementation I use has a small hash table with byte-valued counters (no keys) indexed by a portion of the hash key. If the counter is non-zero, it means the current position *might* be a repetition and a linear list is checked.

[rtitle]

I agree a small separate table is a viable solution.

The mistake I had made in an earlier rev of my program was trying to use my main TT to also detect repetitions.

Rich

[mvk]

I guess the remark in the FIDE rules (which, though not redundant at first glance seems a bit obvious) was added because from a game-theoretical point of view a position where a piece had not moved before, but is forced to move because it is the only way to evade check, would be completely equivalent to one where it had moved before (as far as future moves are concerned).

A somewhat similar point arises if there is a "pawn attacking a square crossed by an opponent’s pawn which has advanced two squares in one move from its original square" (Article 3.7(d)) and "on the move following this advance" the 'en passant' capture is illegal.

That such a position is the "same" as the position without e.p. rights follows from a strict application of Article 9.2 "the possible moves of all the pieces of both players are the same". This is then confirmed by "Positions are not the same if a pawn that could have been captured en passant can no longer be captured in this manner." (One could however argue that "could have been captured" also covers the case that the capture, which is legal according to Article 3.7(d), is illegal due to "Leaving one's own king under attack, exposing one's own king to attack" (Article 1.2). I admit that Article 3.7(d) states "is only legal" and not "is legal".)

The same strict application of "the possible moves of all the pieces of both players are the same" to castling rights is incorrect due to the remark that castling rights are only lost after the king or rook move.

(It is interesting that Article 1.2 forbids 'capturing' the opponent's king, which should not be possible in the first place. I suppose this is directly related to Article 7.)

Hi,
How you would interpret this position?

[d]3r4/4p3/8/3P3k/8/3K4/8/8 b - - 0 1
After 1. ... e5 2. Ke3 Kg5 3. Kd3 Kh5 we have the same position or not? It is the same, even if everyone here that has a pseudo-legal move generator I guess will stuff ep square into zobrist hash key, having a hash bug in the engine.... From a repetition point of view, stuffing the ep square is wrong, but this has nothing to do with the performance of the engine, aka if is it worth doing all this stuff...

Best regards,
Natale.

I believe we can summarise the FIDE logic as follows: For repetition, castling RIGHTS and en-passant POSSIBILITIES are what matters.

For en passant it makes a lot of sense to look only at the availability of a legal en passant capturing move. Because how to define 'right' in this case? What if the pawn is pinned? What if there is no adjacent pawn after a double pawn push? Does there exist a 'right' in that case? Of course not (forget the old FEN stance here), but it is ugly, for a human, to define 'right' in any other way than as 'a legal e.p. capture exists'.

For castling on the other hand, it makes more sense to use a weaker definition. Because to separate RIGHT from POSSIBILITY can be a quite difficult matter, as shown in many places.

But I admit that I get confused by the edge cases.

[syzygy]

I believe we can summarise the FIDE logic as follows: For repetition, castling RIGHTS and en-passant POSSIBILITIES are what matters.

For en passant it makes a lot of sense to look only at the availability of a legal en passant capturing move. Because how to define 'right' in this case? What if the pawn is pinned? What if there is no adjacent pawn after a double pawn push? Does there exist a 'right' in that case? Of course not (forget the old FEN stance here), but it is ugly, for a human, to define 'right' in any other way than as 'a legal e.p. capture exists'.

If you define 'en-passant right' in this non-ugly way as 'a legal e.p. capture exists', then the rule is: For repetition, castling rights and en-passant rights are what matters.

But I don't know if this is really the most natural definition for a human. I think there is something to be said for each of the three options:
1. a legal e.p. capture exists;
2. a pseudo legal e.p. capture exists (i.e. the opponent just played a double pawn move and there exists at least one adjacent pawn);
3. the opponent just played a double pawn move.

Option 1 is in accordance with FIDE rules. It is also the optimal one in terms of TT usage (when you use the same hash key for repetition detection and TT indexing). But it is also the most tricky one to implement correctly and efficiently.

Option 2 is what I think most engines implement (including mine). It loses a little bit in TT efficiency, but the loss is probably not measurable. It also loses a little bit in correctness of 3-fold repetition detection (but won't give false positives, so will not lead to disasters).

Option 3 is really suboptimal. I'm reasonably sure it costs Elo in the opening and it might miss some important cases of 3-fold repetition (but still won't give false positives).

I think FIDE's choice here was "good" for computer chess. Option 2 would have been OK as well, but option 3 would have lead to complications. The engine would have had to use option 1 or 2 for calculating the hash key used for indexing the TT (or accept a small Elo loss) but would have to use option 3 for calculating the hash key used for repetition detection (or risk false positives, which is really bad).

For castling on the other hand, it makes more sense to use a weaker definition. Because to separate RIGHT from POSSIBILITY can be a quite difficult matter, as shown in many places.

In my view the solution picked by FIDE for castling rights most resembles option 2. Slightly more "optimal" in terms of TT usage is to already lose the rights if the player to move is forced to move his rook or king, but it would be quite nasty to implement correctly. I'm pretty sure almost all programs would stick to following the present rules.

[xmas79]

In my view the new rule removes one unclarity in that it clearly defines that castling rights are only lost after making the move that loses them, even if that move was forced, but it forgets to state that positions with different castling rights are different...

This is the same thing I wrote in the my previous post. We still don't know if that part is missing. We could also argue what the "changed temporarily" really means... In check or what else?
But form an engine point of view, this is only an artifact and would hurt engines performances IMHO.

Natale.

[xmas79]

1. a legal e.p. capture exists;
2. a pseudo legal e.p. capture exists (i.e. the opponent just played a double pawn move and there exists at least one adjacent pawn);
3. the opponent just played a double pawn move.

Option 1 is in accordance with FIDE rules. It is also the optimal one in terms of TT usage (when you use the same hash key for repetition detection and TT indexing). But it is also the most tricky one to implement correctly and efficiently.

Option 2 is what I think most engines implement (including mine). It loses a little bit in TT efficiency, but the loss is probably not measurable. It also loses a little bit in correctness of 3-fold repetition detection (but won't give false positives, so will not lead to disasters).

Option 3 is really suboptimal. I'm reasonably sure it costs Elo in the opening and it might miss some important cases of 3-fold repetition (but still won't give false positives).

This is a better explanation of what I wanted to say with my EP position example. Very good!

Option 3 was what I had to fix (as the OP in the thread I mentioned in my first post).
Option 2 is what I have now.
Option 1 is what I think is the right thing to do for the 3-fold repetition check, but I actually don't have a procedure to check pinned-on-king pieces...

Best regards,
Natale.

[rtitle]

re:
"1. a legal e.p. capture exists;
2. a pseudo legal e.p. capture exists (i.e. the opponent just played a
double pawn move and there exists at least one adjacent pawn);
3. the opponent just played a double pawn move.

Option 1 is in accordance with FIDE rules. It is also the optimal one
in terms of TT usage (when you use the same hash key for repetition
detection and TT indexing). But it is also the most tricky one to
implement correctly and efficiently."

Actually, if your move generator generates only legal moves (not pseudo-legal moves), then #1 is easy to implement. My observation is that a position with any legal e.p. captures possible *cannot* be repeated (because the previous move must have been a pawn move, and pawn moves are irreversible, so you can't later again reach that same position with that same previous pawn move). For example, after 1.e4 Nf6 2.e5 d5 you've reached a position in which 3.exd6 is possible. While you can later reach that same arrangement of pieces (e.g. after 3.Ke2 Kd7 4.Ke1 Ke8), you can't later reach that same arrangement of pieces *where exd6 is possible*.

Therefore, the following algorithm is sufficient:

position->generate_moves(movelist /* output arg */);
if (movelist contains any e.p. captures)
/* don't bother transcribing it's hash to whatever you're using to detect repetitions; it can't repeat */;
else
hash position and transcribe hash to history for detecting repetitions

Then at the point where you want to detect if a move leads to a repletion:

position->make_move(move);
hash position and look up in the history to detect if you've reached a repetition

Rich