Fwd: Possible Stockfish bug in repetition detection

[Jean-Francois Romang]

Here is Marco's anwser about this problem !
So, let's try to find out how to do it :)

Jean-Francois


---------- Forwarded message ----------
From: Marco Costalba <mcos...@gmail.com>
Date: 2012/10/12
Subject: Re: Possible Stockfish bug in repetition detection
To: Jean-Francois Romang <jeanfranc...@gmail.com>


On Fri, Oct 12, 2012 at 1:42 PM, Jean-Francois Romang
<jeanfranc...@gmail.com> wrote:
> Hello Marco,
>
> There is some discussion on the PicoChess mailing list about the 3
> fold repetition draw.
> It seems Stockfish does not handle it properly : are you aware of this problem ?

I am aware that SF marks a position as draw the at the first
repetition. This works well in parctice (modulo patological cases) and
is considered the standard approach.

> If you think this should be solved and have no time, I can try to fix


Pelase feel free to try but I will commit any "fix" only if it has
zero performance hit.

[javieros]

After rethink the problem, I must admit that Marco is right and I was wrong.

Suppose Stockfish is playing the game Fischer-Petrosian, after 31.Qh5 SF thinks 31...Qa1+ -1.21 ply 23/48, after 31...Qf6 SF thinks 32.Qe2 0.00 the move is good although the evaluation is wrong because Black can avoid the 3 repetition and may win, but the important thing is that it has no effect in the play. After 32.Qe2 SF thinks 32...b5 -1.32 so playing as black SF is able to win the game.

Finally, the "fix" will be useful only for analysis purposes, removing the draw claim is enough to play well.

When SF plays under Fritz interface, perhaps it is the Fritz program that detects the 3 repetition.

Javier

[Shivkumar Shivaji]

I thought about this a bit based on your feedback and that of Marc Costalba and Jean.

Your last message on analysis mode and game mode is very relevant. However, rather than Marco being right and you being wrong, I would state it differently. Marco is obviously a talented programmer and has his reasons for implementing a 2-fold draw repetition check. What Marco chose was a practical solution. Its hard to do a thorough draw check and not lose out a little on performance. There is no practical way to take a ZERO performance hit :) Stockfish is an engine and leaves calling 3-fold draws to a referee. As you said, when SF is playing under Fritz, Fritz will call out 3-fold repetition. The problem arises because pico chess is a GUI (using the DGT XL clock)! The GUI 3-fold detection logic has to be deeper than the engine. 

I propose modifying the is_draw function to check all previous even numbered candidate moves (e.g. current position, 2 half moves before, 4 half moves before…) and see if 2 positions match with the position on the board. We can maybe add a flag (do_comprehensive_check) to the current is_draw function. If we want to make this an upstream contribution, The stockfish authors can simply call it with the flag false by default. There might be optimizations such as using a hash table but I don't think it is needed to add in more structures just for this check. Jean, what do you think? Removing the draw claim is possible, but this fix is not that hard in my mind. The analysis/book mode patch I sent to you makes it easy to test the draw code, just make moves from the starting position and see how quickly Picochess declares a draw.

To summarize, the 3-fold draw repetition bug is there because Picochess calls the Stockfish 3-fold draw checker, which is really a fast performing quick check and not a comprehensive check. This is not due to a bug in Pico chess itself :)

Shiv

--
You received this message because you are subscribed to the Google Groups "PicoChess" group.
To unsubscribe from this group, send email to picochess+...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[Wolfgang Zugrav]

Without going through all the details of the draw game Fischer-Petrosjan, and the of course plausible draw check done outside the engine…

..just want to emphasize that this is a basic chess rule and must therefore somehow be implemented!

 

With regards to the „zero performance comment“ from Marco, i’d say this has to be checked against several aspects.

Performance in terms oft time delay for computiung a move, is not an aspect for picochess as Pico -and now the circle closes - will be treated primarily as a dedicated chess computer (not as an engine) with a chessboard connected playing primarily against humans (because of the human input device „chess pieces“). So yes, this has to be implemented!

 

Second aspect ist the performance relative to the playing strenght in any means, and how it would impact it.

Here i’d like to point out that a missed draw from Pico is also a perfomance miss in terms of Elo and game points.

e.g. loosing a drawish game resulting in a bad overall match or tournament performance. So i think again yes, this has to be implemented!

 

PS: A human player would however loose also time on calculating whether a position has already been repeated twice and has to check against possible draw.

In some game stages it also could be a time win on repeating moves twice before deciding an alternate game path or move.

 

- Wolfgang

 

 

---

[Shivkumar Shivaji]

I see that you indicate that Picochess should do the draw detection. Agree.

On your second point of Stockfish itself internally performing this check, I would tend to agree, but I can easily see someone like Marco saying that one can gain 2 elo by evaluating 3-fold repetition correctly but would lose say 5 elo by spending more time on accurate 3-fold detection. We might need a solution that is not too performance intensive as the is_draw method seems to be called during search(). There might be a way to place this code within the search call artfully, but I am far from an expert on this matter, I have never written a chess engine before!

Perhaps, the is_draw method can be modified with the "do_comprehensive_check" flag and contributed back to SF for now and later we can test to see if the do_comprehensive_check method can be performance optimized? I have ideas on performance optimizing the 3 fold repetition check using a bloom filter, but this might be something we can revisit later. There might even be articles on this subject by other engine authors. Just my 2 cents.

Shiv 

On Oct 12, 2012, at 11:15 AM, "Wolfgang Zugrav" <zug...@gmx.at> wrote:

Without going through all the details of the draw game Fischer-Petrosjan, and the of course plausible draw check done outside the engine…

..just want to emphasize that this is a basic chess rule and must therefore somehow be implemented!

 

With regards to the „zero performance comment“ from Marco, i’d say this has to be checked against several aspects.

Performance in terms oft time delay for computiung a move, is not an aspect for picochess as Pico -and now the circle closes - will be treated primarily as a dedicated chess computer (not as an engine) with a chessboard connected playing primarily against humans (because of the human input device „chess pieces“). So yes, this has to be implemented!

 

Second aspect ist the performance relative to the playing strenght in any means, and how it would impact it.

Here i’d like to point out that a missed draw from Pico is also a perfomance miss in terms of Elo and game points.

e.g. loosing a drawish game resulting in a bad overall match or tournament performance. So i think again yes, this has to be implemented!

 

PS: A human player would however loose also time on calculating whether a position has already been repeated twice and has to check against possible draw.

In some game stages it also could be a time win on repeating moves twice before deciding an alternate game path or move.

 

- Wolfgang

 

 

---

Von: pico...@googlegroups.com [mailto:picochess@googlegroups.com] Im Auftrag von Shivkumar Shivaji

[javieros]

I think that it may be implemented externally to Stockfish search, as it is doing in the Fritz interface.

A simple idea is the following,

1) Picochess stores every position reached in the game in an array and set a counter related to this element of the array to 1,
2) After every move Picochess search the actual position in this array and if there is a coincidence add one to the counter of this position.
3) If the counter reaches 3 then Picochess displays Draw and stop the game.

This way the count of the repetition remains out of the search and there is almost no waste of CPU time. 
With the saving method of Marco, Stockfish will choose the right move indepently of this external procedure that will act as an external referee.

Javier

El viernes, 12 de octubre de 2012 21:30:35 UTC+2, sshivaji escribió:

I see that you indicate that Picochess should do the draw detection. Agree.

On your second point of Stockfish itself internally performing this check, I would tend to agree, but I can easily see someone like Marco saying that one can gain 2 elo by evaluating 3-fold repetition correctly but would lose say 5 elo by spending more time on accurate 3-fold detection. We might need a solution that is not too performance intensive as the is_draw method seems to be called during search(). There might be a way to place this code within the search call artfully, but I am far from an expert on this matter, I have never written a chess engine before!

Perhaps, the is_draw method can be modified with the "do_comprehensive_check" flag and contributed back to SF for now and later we can test to see if the do_comprehensive_check method can be performance optimized? I have ideas on performance optimizing the 3 fold repetition check using a bloom filter, but this might be something we can revisit later. There might even be articles on this subject by other engine authors. Just my 2 cents.

Shiv 

On Oct 12, 2012, at 11:15 AM, "Wolfgang Zugrav" <zug...@gmx.at> wrote:

Without going through all the details of the draw game Fischer-Petrosjan, and the of course plausible draw check done outside the engine…

..just want to emphasize that this is a basic chess rule and must therefore somehow be implemented!

 

With regards to the „zero performance comment“ from Marco, i’d say this has to be checked against several aspects.

Performance in terms oft time delay for computiung a move, is not an aspect for picochess as Pico -and now the circle closes - will be treated primarily as a dedicated chess computer (not as an engine) with a chessboard connected playing primarily against humans (because of the human input device „chess pieces“). So yes, this has to be implemented!

 

Second aspect ist the performance relative to the playing strenght in any means, and how it would impact it.

Here i’d like to point out that a missed draw from Pico is also a perfomance miss in terms of Elo and game points.

e.g. loosing a drawish game resulting in a bad overall match or tournament performance. So i think again yes, this has to be implemented!

 

PS: A human player would however loose also time on calculating whether a position has already been repeated twice and has to check against possible draw.

In some game stages it also could be a time win on repeating moves twice before deciding an alternate game path or move.

 

- Wolfgang

 

 

---

Von: pico...@googlegroups.com [mailto:pico...@googlegroups.com] Im Auftrag von Shivkumar Shivaji

[Shivkumar Shivaji]

The array proposal you have is essentially a hash table (hash table is simply an array indexed for retrieval speed). This hash table has to be updated every move. However, for something external, this is entirely fine and has very little cost as you indicate.

The only downside to this proposal is that Marco will probably not want to get this code merged back to SF :) Going back an even number of moves on the full move list is something he is more likely to accept on a merge.

Just out of curiosity, is Fritz correctly able to tell that the Karpov-Miles example is NOT a 3-fold draw? - http://en.wikipedia.org/wiki/Threefold_repetition#Karpov_versus_Miles . I would assume not, but am very curious especially as I don't have Fritz!

Shiv

[javieros]

Fritz is able to say correctly that Karpov-Miles it is not draw by 3-fold repetition.

Really my idea needs two arrays, one for positions with white to play and other for positions with black to play.

My idea is not to merge this code back into Stockfish, this procedure is external to Stockfish like the procedure that receive information from the DGT board and send information to the clock.

Javier

[Shivkumar Shivaji]

Wow, impressed by Fritz then!

Yes, you would need 2 hash tables or a hash table with 2 "kinds" of entries then for black and white to move. I think it would be great if possible to have a solution that can be merged back into Stockfish for the benefit that Wolfgang pointed out. I will let others present their opinion, especially Jean. If we are not going to merge it back with Stockfish, using hash tables as you suggested is perfectly fine.

Shiv

[Jeff]

Finally, thanks to our testers team and Shiv's patching, the code will be merged into the official Stockfish :

https://github.com/mcostalba/Stockfish/pull/34#issuecomment-9791501

Nice teamwork !

;-)

[Shivkumar Shivaji]

This is really fantastic news! Will allow for more testing. I like the fact that the page has Javier's Fischer - Petrosian example :)

On the code style, I would prefer a more elegant way to do this templating. I don't like "<true><false>", I would prefer to use an enum if it can be performance optimized. The old code had this behavior and thus it was easier to maintain the boolean template. 

However, I am more than happy that Marc has accepted this code change. It also makes good sense that this should only occur at the root node, good job Jean on making Stockfish do this by default at the root node for searches! This will cover Wolfgang's concern too.

Shiv

[javieros]

Very good news!!
Congratulations!!

Javier