Repetitions in the Search Tree

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
jayakiran
Posts: 9
Joined: Tue Apr 12, 2016 8:15 pm

Repetitions in the Search Tree

Post by jayakiran » Sun May 29, 2016 10:51 am

Hi -

I was reading a bit about GHI and it's implications for TT hits.

Q: What is rationale behind marking a 'first' repetition in the search tree as a draw? Does it save a lot of time? (I'm only talking about the repetitions in the search and not in the whole PV).

Thanks guys.

User avatar
hgm
Posts: 23713
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Repetitions in the Search Tree

Post by hgm » Sun May 29, 2016 11:53 am

The problem is worse than just wasting time. If you only score the second repetition as draw, you might not recognize the repetitions at all, because they require too deep a search. You also get much poorer search at the same depth, due to 'self-inflicted horizon effect'. By searching on after a repetition you basically allow the engine to push any trouble away from the root by inserting ne or more single-repeat loops in any branch.

User avatar
Luis Babboni
Posts: 422
Joined: Sat Feb 28, 2015 3:37 pm
Location: Argentina

Re: Repetitions in the Search Tree

Post by Luis Babboni » Sun May 29, 2016 2:23 pm

hgm wrote:The problem is worse than just wasting time. If you only score the second repetition as draw, you might not recognize the repetitions at all, because they require too deep a search. You also get much poorer search at the same depth, due to 'self-inflicted horizon effect'. By searching on after a repetition you basically allow the engine to push any trouble away from the root by inserting ne or more single-repeat loops in any branch.
Very interesting!
I added 3rd repetition recognition to Soberango few weeks ago and I did never thought or heard about it so I just evaluate as tie the 3rd equal position (that is the 2nd repetition).

jayakiran
Posts: 9
Joined: Tue Apr 12, 2016 8:15 pm

Re: Repetitions in the Search Tree

Post by jayakiran » Sun May 29, 2016 2:57 pm

hgm - thanks for the explanation. I understand it a bit better now. If you repeat a move in the Search Tree (including the root of the Search), then it means you are not making progress - safe to mark that variation a draw. This will not affect the score of the root because if there are better moves for a player he is going to play that instead.

Of course - you will be checking for triple repetition against your full history.

User avatar
hgm
Posts: 23713
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Repetitions in the Search Tree

Post by hgm » Sun May 29, 2016 4:15 pm

Well, I also never to that. By allowing one repeat the engine basically only starts working to prevent this repeat after that. So you get the very annoying effect that it will alternate moves that make progress with repeat cycles that do not. (Which makes it encounter the 50-move barrier after much less progress than otherwise.)

So I just assume that the first repeat is a draw (or win/loss, depending on what the rules say about this). You should just be careful only to actually claim when you visit the position for the 3rd or 4th time (again as the rules specify).

jayakiran
Posts: 9
Joined: Tue Apr 12, 2016 8:15 pm

Re: Repetitions in the Search Tree

Post by jayakiran » Sun May 29, 2016 6:54 pm

@hgm -

Sorry - maybe I misunderstand. Say a position occured twice already *before* the current "search-root" - then you must be checking if any position in the search tree is a repetition, right? Otherwise, you will be missing a draw.

Also, say a certain position occured once before the current "search-root" - then we shouldn't be marking it as a draw if we see in the search tree for the first time.

If we see it a second time in the search tree, it can be scored a draw.

Could you explain a bit more your earlier message? Thanks.

bob
Posts: 20549
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Repetitions in the Search Tree

Post by bob » Sun May 29, 2016 7:17 pm

jayakiran wrote:@hgm -

Sorry - maybe I misunderstand. Say a position occured twice already *before* the current "search-root" - then you must be checking if any position in the search tree is a repetition, right? Otherwise, you will be missing a draw.

Also, say a certain position occured once before the current "search-root" - then we shouldn't be marking it as a draw if we see in the search tree for the first time.

If we see it a second time in the search tree, it can be scored a draw.

Could you explain a bit more your earlier message? Thanks.
The point is you won't reach such positions unless you already think the best you can do is a draw, otherwise why would you repeat the first time, which returns a draw score???

syzygy
Posts: 4455
Joined: Tue Feb 28, 2012 10:56 pm

Re: Repetitions in the Search Tree

Post by syzygy » Sun May 29, 2016 7:22 pm

jayakiran wrote:Also, say a certain position occured once before the current "search-root" - then we shouldn't be marking it as a draw if we see in the search tree for the first time.
Many engines (such as Stockfish) score that first repetition as a draw anyway.

This can indeed lead to the scenario where the opponent first misses a winning move, the engine some moves later unnecessarily allows the opponent to reach the same position again (scoring that position incorrectly as a draw), and the opponent then finds the winning continuation. Half a point lost.

Against engines this scenario will be rather rare. The opponent engine will normally find the winning move already on its first try.

Another problem is that a lot of users get confused by a draw score while analysing games. The number of "bug reports" connected to this behaviour on this forum alone must be running in the dozens.

Unfortunately, any "fix" (i.e. doing it the "right" way) loses a few Elo.

(If the engine has an analysis mode, one way to "fix" the behaviour in analysis mode without changing repetition detection in the search is by somehow removing/hiding all positions from game history except for those that have occurred twice. So instead of letting the search check the real game history, you let it check an artificially constructed game history consisting of only the positions that have been repeated on the board.)

jayakiran
Posts: 9
Joined: Tue Apr 12, 2016 8:15 pm

Re: Repetitions in the Search Tree

Post by jayakiran » Sun May 29, 2016 7:25 pm

I see - hmm. But, that assumes that me and my opponent played our best so far until before the search-root. Is that an okay assumption to make in practice?

One example would be that my opponent blundered and let me repeat the position once - but won't allow it a second time? I know that's quite unlikely with chess engines....

jayakiran
Posts: 9
Joined: Tue Apr 12, 2016 8:15 pm

Re: Repetitions in the Search Tree

Post by jayakiran » Sun May 29, 2016 7:32 pm

@syzygy

Saw your reply a bit late. Thanks for the explanation - I understand the approach now.

Post Reply