repetition detection

[Reinhard Scharnagl]

To R?mi and Sven,

the e.p. flag internally used in Smirf has the effect to enable the creation of e.p. captures. That is, e.p. captures might be created where valid, not that they would be created in any case. Smirf thus creates only legal e.p. captures. May be I am misunderstanding something here.

Reinhard.

[Uri Blass]

Hi Reinhard,
The question is if smirf can detect repetition when there is no repetition
because castling rights are the same and the ep flag is the same.

movei today can do that error because I detect repetition if the hash key is the same.

It means that it can claim a draw by repetition when the hash key is the same 3 times inspite of the case that the position is not the same because in the first case it was possible to capture.

I think that it is not expensive to call another function to validate repetition in case that the hash key is the same but I do not know of a single case when movei blundered by claiming a draw in a position that is not a draw position by the chess rules so it is not very important for me to fix it.

Uri

[Reinhard Scharnagl]

Hi Uri,

well I understand now. Such errornously detected move repetitions by comparing the hash codes could occur only, when NO E.P. flag would be set, because a situation with SET E.P. flag can occur only ONCE in a game line. Thus this error case has to be caused by three situations with an RESET e.p. flag. But that positions are encoded 100% correctly regarding the hash code.

And because of my E.P. hash code xoring overlay is depending from the e.p. square coordinate, I am not yet able to see any error raising situation. May be it could help to specify a game line, which you regard to cause such an errornous situation.

I can see only one negative payload here and that is that sometimes the information cached in the transposition table would be split without any need.

Reinhard.

[Uri Blass]

I think that you are right and the only error can be not detecting repetition when there is a repetition.

In the following case movei does not detect draw by repetition because inspite of the case that the position repeated 3 times the hash key did not repeat 3 times.

[Event "Edited game"]
[Site "URI-AMD"]
[Date "2005.01.09"]
[Round "-"]
[White "-"]
[Black "-"]
[Result "*"]

1. e4 e5 2. Nf3 Qe7 3. Nxe5 Qd8 4. Nf3 Qe7 5. e5 d5 6. Ng1 Nc6 7. Nf3 Nb8
8. Nc3 Nc6 9. Nb1 Nb8
*

[Reinhard Scharnagl]

Well, Uri, I see.

[Sven Schüle]

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?

Hi, Ochazuke,
I think being in check or not does not matter here. The elements of a position which are relevant for repetition detection are only the piece places, the side to move, the castle rights and the right to make an ep capture. If all these elements are identical for two positions then the side to move is either "in check" in both positions, or "not in check" in both positions. Item no. 3 seems to be redundant.

I guess you thought of an example where the side to move can escape from check by an ep capture, but I don't see a relation to your item 3 with respect to comparing two positions.

Cheers,
Sven

[Sven Schüle]

...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.

Hi Reinhard,

my intention was to say that engines that do not take into account this "pinned pawn case" for repetition detection when ep capture is involved are missing to detect a repetition case. However, now I think I have been wrong when writing that this does not conform to the FIDE rules. Not claiming a draw is "only" a problem of playing strength, sometimes also a problem for TDs. FIDE rules say that a player *may* claim a draw. Chess engine tournament rules sometimes say a bit more: an engine *should* claim a draw.

I hope you agree that not claiming a draw by threefold repetition when there is such a repetition in a game can be viewed as an "error", at least as a very small one? I know that this case is very rare, but fixing the problem should be possible without a big effort and in a way that does not affect performance. I'm already thinking about a cheap solution.

Regards,
Sven

[Reinhard Scharnagl]

Hi Sven,

of course that is something with a bad taste with it. But in my still unready Smirf I intend to separate draw detection and tree evaluation completely.

Reinhard.

[Sven Schüle]

I think that you are right and the only error can be not detecting repetition when there is a repetition.

In the following case movei does not detect draw by repetition because inspite of the case that the position repeated 3 times the hash key did not repeat 3 times.

[Event "Edited game"]
[Site "URI-AMD"]
[Date "2005.01.09"]
[Round "-"]
[White "-"]
[Black "-"]
[Result "*"]

1. e4 e5 2. Nf3 Qe7 3. Nxe5 Qd8 4. Nf3 Qe7 5. e5 d5 6. Ng1 Nc6 7. Nf3 Nb8
8. Nc3 Nc6 9. Nb1 Nb8
*

Hi Uri,

your example matches exactly what I tried to explain in my earlier posts, but I must apologise for not having been able to explain it better so that everybody could understand it immediately.

I believe that there are more realistic examples that show the situation. 3...Qd8 and most of the following moves are of course stupid. But when talking about exactly implementing the rules I think that one should always leave out the "stupidity factor", so your example is good enough to understand the principle.

We should not forget that this situation (ep illegal due to pinned pawn) can also occur anywhere deep in the tree, probably at a depth where engines do not necessarily enter "realistic" positions only. So I think this should be solved somehow.

Cheers,
Sven

[Sven Schüle]

I'm already thinking about a cheap solution.

Hi again for my x-th posting tonight ...

My idea is to align the ep target square, which has been "initially" set after making a pawn double step to a square with an enemy pawn to the left or right, as soon as the information is available whether the ep capture is a legal move. It depends on the engine's implementation whether this is already during move generation (pin detection code, which must be very clever for this special case here as pointed out by Peter Fendrich) or later, when moves are made and possibly identified as illegal.

Alignment here means that afterwards the ep target square reflects what has been recognized by the move generator, or by movegen plus search together, so that a later repetition detection (at least four plies later) uses the perfect information.

"Surprise" has only partial pin detection code (for check evasion only), so I would perhaps do it like this somewhere in the searcher code:

Code: Select all

if (is_last_move_identified_as_illegal()) {
    handle_illegal_move_as_usual_including_taking_it_back();
    if (ep_target_square_of_current_position_is_valid_square() AND
        last_move_was_an_ep_capture_to_that_square()) {

        reset_ep_target_square_of_current_position_to_zero();
        update_hash_key_of_current_position_accordingly();
    }
}

Updating the hash key after having already searched at least one subtree should in my opinion do no harm if the hash key has not yet been used to store the position in a hash table. This should not have happened yet because the position is not a leaf position and the subtree with the illegal ep capture did not return control to its parent whose hash key is subject of change, so the parent did not store the completed search result in the table.

Surprise does not use the hash key for repetition detection but uses an "exact" method, so the ep target square is used directly. This will be different for most other engines.

Efficiency: The case is rare, so the additional overhead for each illegal move (only!) is the code to check the condition
"ep_target_square_of_current_position_is_valid_square()" which normally is one integer comparison (ep != 0). The remainder has no substantial impact because it nearly never happens.

What about this idea?

Cheers,
Sven

[Anonymous]

... 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).

This rule is not phrased well in the FIDE rules. There really is no way to change castling rights tomporarily with the same position. I had mentioned this strange rule in CCC or WB forum some time ago, and everybody agreed, that it was not possible.

Regards,
Dieter

[Anonymous]

if (is_last_move_identified_as_illegal()) {
handle_illegal_move_as_usual_including_taking_it_back();
if (ep_target_square_of_current_position_is_valid_square() AND
last_move_was_an_ep_capture_to_that_square()) {

reset_ep_target_square_of_current_position_to_zero();
update_hash_key_of_current_position_accordingly();
}
}

Would this code handle this position correctly?
[diag]8/8/6k1/8/4pPp1/8/3K4/6R1 b - f3 0 1[/diag]
8/8/6k1/8/4pPp1/8/3K4/6R1 b - f3 0 1

[Uri Blass]

I think that you are right and the only error can be not detecting repetition when there is a repetition.

In the following case movei does not detect draw by repetition because inspite of the case that the position repeated 3 times the hash key did not repeat 3 times.

[Event "Edited game"]
[Site "URI-AMD"]
[Date "2005.01.09"]
[Round "-"]
[White "-"]
[Black "-"]
[Result "*"]

1. e4 e5 2. Nf3 Qe7 3. Nxe5 Qd8 4. Nf3 Qe7 5. e5 d5 6. Ng1 Nc6 7. Nf3 Nb8
8. Nc3 Nc6 9. Nb1 Nb8
*

Hi Uri,

your example matches exactly what I tried to explain in my earlier posts, but I must apologise for not having been able to explain it better so that everybody could understand it immediately.

I believe that there are more realistic examples that show the situation. 3...Qd8 and most of the following moves are of course stupid. But when talking about exactly implementing the rules I think that one should always leave out the "stupidity factor", so your example is good enough to understand the principle.

We should not forget that this situation (ep illegal due to pinned pawn) can also occur anywhere deep in the tree, probably at a depth where engines do not necessarily enter "realistic" positions only. So I think this should be solved somehow.

Cheers,
Sven

Hi Sven,
I do not see how it is important in realistic position.

1)My opinion is that missing repetition in these rare cases when enpaasent capture was illegal because of pin probably changes the result in less than 1 of million games.

Can you show me a single practical example when an engine missed a draw because of that problem?

Note that I detect first repetition as a draw by evaluation so if the best line leads to repetition I may detect the repetition later so even in the worse case I may detect the repetition because of searching deeper.

2)You can claim that you do it not to detect repetition in games but to avoid searching irrelevant lines in games when you could detect repetition earlier but I think that even a cheap solution that does your program 0.1% slower is going to do your program weaker and in most cases you will not detect in the search cases when there is repetition when ep capture is illegal because of pin in the first case.

Only getting positions when ep capture is illegal because of a pin is very rare in the search.

You can be maybe less than 1% faster in less than 1% of the searches that you do.

Uri

[Anonymous]

Maybe I should elaborate on my above post a bit. I don't think your code

Code: Select all

if (is_last_move_identified_as_illegal()) {
    handle_illegal_move_as_usual_including_taking_it_back();
    if (ep_target_square_of_current_position_is_valid_square() AND
        last_move_was_an_ep_capture_to_that_square()) {

        reset_ep_target_square_of_current_position_to_zero();
        update_hash_key_of_current_position_accordingly();
    }
}


works as is.
First, you cannot read from the hash table correctly because the hash key may be incorrect upon entering a position. Second, it doesn't work with the position I posted above(8/8/6k1/8/4pPp1/8/3K4/6R1 b - f3 0 1) because when it sees that there is an illegal ep capture, it immediately changes the hash key. however, an ep capture is still available, so the hash key will be incorrect.

[Sven Schüle]

Hi Uri,

1)My opinion is that missing repetition in these rare cases when enpaasent capture was illegal because of pin probably changes the result in less than 1 of million games.

"less than 1" does not sound very much

Can you show me a single practical example when an engine missed a draw because of that problem?

I can't because I did not yet scan a game database for it. Probably I would need a special tool to find such games. And it's indeed very likely that I don't find them, you may be right.

But my approach is different, maybe because my engine is not yet at a level where doing small optimizations, or omitting changes which slow down very slightly, seems to be adequate. Given the current strength of Surprise it is important for me to find the way to bigger improvements first.

It is also a matter of style. My style is to try to write my chess program as if I would write software for a customer. Such a customer would not be happy if I told him that I knew of a possible problem in the software which is probably very rare and which has never been reported by any other customer. And of course I would fix it immediately as soon as someone really reported that problem. And I already knew how to fix it today but I would not want to do it because it would slow down the program by 1%.

Chess programming is different, of course. But everyone makes his own decision about how to handle known problems, even if they are very small ones.

2)You can claim that you do it not to detect repetition in games but to avoid searching irrelevant lines in games when you could detect repetition earlier [...]

I could claim this but it was not my main intention. I thought more about "correctness". I don't believe that recognizing this special case of repetition will lead to any kind of speedup. The number of saved nodes, if any, will be small.

So my summary is:
I don't claim that everyone should fix this problem. I have shown that it exists - inspired by the original posting of Ochazuke -, and perhaps I will implement a suitable solution for Surprise one day (although not with high priority). But I know that the problem is a rare one, and if programmers decide to ignore it for any reason, it could be tolerated because there is only a small probability that a possible draw claim is missed.

Nevertheless I think that the PGN/FEN standard should be changed at least to show an ep target square only if there is an enemy pawn present to the left or right of the pawn having advanced two squares (as I already pointed out earlier within this thread).

Does anyone know who should be contacted for an update of the PGN standard?

Cheers,
Sven

[Sven Schüle]

Maybe I should elaborate on my above post a bit. I don't think your code

Code: Select all

if (is_last_move_identified_as_illegal()) {
    handle_illegal_move_as_usual_including_taking_it_back();
    if (ep_target_square_of_current_position_is_valid_square() AND
        last_move_was_an_ep_capture_to_that_square()) {

        reset_ep_target_square_of_current_position_to_zero();
        update_hash_key_of_current_position_accordingly();
    }
}


works as is.
First, you cannot read from the hash table correctly because the hash key may be incorrect upon entering a position. Second, it doesn't work with the position I posted above(8/8/6k1/8/4pPp1/8/3K4/6R1 b - f3 0 1) because when it sees that there is an illegal ep capture, it immediately changes the hash key. however, an ep capture is still available, so the hash key will be incorrect.

Hi Ochazuke,

your example indeed kills my algorithm so that I have to give up for now and think a bit more about a possible solution. The hashkey problem you mentioned might exist, I'm not quite sure.

Thanks for your hint,
Sven

[Dann Corbit]

[snip]
Nevertheless I think that the PGN/FEN standard should be changed at least to show an ep target square only if there is an enemy pawn present to the left or right of the pawn having advanced two squares (as I already pointed out earlier within this thread).

This has been suggested to the author of the PGN standard, long ago.

Does anyone know who should be contacted for an update of the PGN standard?

Steven J. Edwards.

[Tony van Roon-Werten]

Hi Uri,


It is also a matter of style. My style is to try to write my chess program as if I would write software for a customer. Such a customer would not be happy if I told him that I knew of a possible problem in the software which is probably very rare and which has never been reported by any other customer. And of course I would fix it immediately as soon as someone really reported that problem. And I already knew how to fix it today but I would not want to do it because it would slow down the program by 1%.


Cheers,
Sven

You shouldn't do this for a different reason. If you tell this, then, whenever the costumer deletes his backups, formats his disk etc. he will say that the real reason why it doesn't work anymore, was that problem you never fixed

Tony