Simple triple repetition handler

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.
User avatar
stegemma
Posts: 859
Joined: Mon Aug 10, 2009 8:05 pm
Location: Italy
Full name: Stefano Gemma
Contact:

Simple triple repetition handler

Post by stegemma » Sun Feb 21, 2016 9:41 am

Satana, in G6 tourney, often lose a lot of ELO points just because it fall in triple repetition while in advantage over its opponent. Because I haven't TT active (but I can enable position hash-key), now, I would like to implement a very simple repetition handler, like this one:

Code: Select all

at any node, just compare the position with the one at two nodes before: if it is the same position, then return a zero score
I would test this morning but anybody have some hint about some situation where this simple method will not works?

I already know that it would be a partial method... but it is better than having nothing, like now.
Author of Drago, Raffaela, Freccia, Satana, Sabrina.
http://www.linformatica.com

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

Re: Simple triple repetition handler

Post by hgm » Sun Feb 21, 2016 10:29 am

It will certainly not have any effect if you don't compare to the position four nodes before.

And this will actually solve the worst problem. I used something similar in my engine Usurpator II in the eighties. Except that it was not based on any position key, but on the last 4 moves being non-captures, and having the from- and to-square of the move 2 ply earlier swapped. It hardly ever fell into repeat cycles.

Most engines don't do this through the hash table, but just keep a stack of position keys, and run through it (in steps of 2, as you need same side to move to count as a repetition) upto the last irreversible move. Especially if you treat null moves as irreversible these will never be far away. In games without irreversible moves it would be better to keep a small hash table that can hold (say) 256 keys, which rehashes to the first available empty slot, to prevent you have to search all the way to the start of the game in every node.

User avatar
stegemma
Posts: 859
Joined: Mon Aug 10, 2009 8:05 pm
Location: Italy
Full name: Stefano Gemma
Contact:

Re: Simple triple repetition handler

Post by stegemma » Sun Feb 21, 2016 11:05 am

Yes, of course it was 4 nodes and not 2. A second hash table would be better, of course, but I've already have troubles to make the principal one to work! :)

PS: I've corrected the value bug in satana, so the next monthly tourney it should give the correct "pv" line
Author of Drago, Raffaela, Freccia, Satana, Sabrina.
http://www.linformatica.com

User avatar
Fabio Gobbato
Posts: 125
Joined: Fri Apr 11, 2014 8:45 am
Contact:

Re: Simple triple repetition handler

Post by Fabio Gobbato » Mon Feb 22, 2016 5:08 pm

A simple way for an engine to handle repetitions is to not detect the 3rd repetition but to detect if a position is a repetition or not.
To do that you have only to find the current position between currentposition-4 and currentposition-50movecounter.
The function that detect the repetition is very fast because usually there are only few reversible moves between fifty move counter resets.

User avatar
stegemma
Posts: 859
Joined: Mon Aug 10, 2009 8:05 pm
Location: Italy
Full name: Stefano Gemma
Contact:

Re: Simple triple repetition handler

Post by stegemma » Tue Feb 23, 2016 8:56 am

Of course this would be limited to ply 6 or less (depending on the time control), because doing it at the leaves would be too much expensive. The idea of a cache could be good. of course, I can implement the simplest solution and then make my TT works correctly. It seems that any thing that I add to satana won't works: TT, quiescence and so on... I have to change dramatically my approach to engine programming; I must be more pragmatic and "professional".
Author of Drago, Raffaela, Freccia, Satana, Sabrina.
http://www.linformatica.com

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

Re: Simple triple repetition handler

Post by bob » Wed Feb 24, 2016 5:40 pm

stegemma wrote:Of course this would be limited to ply 6 or less (depending on the time control), because doing it at the leaves would be too much expensive. The idea of a cache could be good. of course, I can implement the simplest solution and then make my TT works correctly. It seems that any thing that I add to satana won't works: TT, quiescence and so on... I have to change dramatically my approach to engine programming; I must be more pragmatic and "professional".
I do this all the way to and including nodes with depth >= 1. Doing it in the q-search is almost free since any capture resets the 50 move counter and the loop will never execute anyway... In fact, when doing my single ply of checking moves followed by escaping check at the second ply (only) of q-search, I do it there as well...

op12no2
Posts: 349
Joined: Tue Feb 04, 2014 11:25 am
Location: Mumbles, Wales, UK.
Full name: Colin Jenkins
Contact:

Re: Simple triple repetition handler

Post by op12no2 » Wed Feb 24, 2016 11:27 pm

Does it make any sense to not check for reps if losing by a threshold - the idea being in such circumstances a draw is fine and it releases resources for a bit more searching... ?

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

Re: Simple triple repetition handler

Post by bob » Thu Feb 25, 2016 5:49 am

op12no2 wrote:Does it make any sense to not check for reps if losing by a threshold - the idea being in such circumstances a draw is fine and it releases resources for a bit more searching... ?
Not sure what you mean. Would you not want to choose a draw over being material behind??? If you don't check, you would not know it was possible...

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

Re: Simple triple repetition handler

Post by bob » Thu Feb 25, 2016 5:50 am

op12no2 wrote:Does it make any sense to not check for reps if losing by a threshold - the idea being in such circumstances a draw is fine and it releases resources for a bit more searching... ?
Not sure what you mean. Would you not want to choose a draw over being material behind??? If you don't check, you would not know it was possible...

op12no2
Posts: 349
Joined: Tue Feb 04, 2014 11:25 am
Location: Mumbles, Wales, UK.
Full name: Colin Jenkins
Contact:

Re: Simple triple repetition handler

Post by op12no2 » Thu Feb 25, 2016 8:13 am

bob wrote: Not sure what you mean. Would you not want to choose a draw over being material behind??? If you don't check, you would not know it was possible...
Ah yes I see. Historically my very early Lozzas were walking into rep draws, so in my head the rep test is to avoid rep, but you can also look at it the other way as you say, to try and force one.

Post Reply