repetition detection

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.
Edmund
Posts: 668
Joined: Mon Dec 03, 2007 2:01 pm
Location: Barcelona, Spain
Contact:

repetition detection

Post by Edmund » Sat Oct 29, 2011 6:46 pm

I suspected some problems with repetition detection in Glass, so today I collected some figures for how often a repetition is triggered.

Glass tests for a repetition at the beginning of every node. If the position is found in the line between the current node and the root node, draw score is returned immediately.

For a 15 ply search from the start position I am getting 4404 repetitions out of 34115733 tests. So on average there is a repetition on every 7747 nodes.

I would be very much interested, what your engines return for this index.

Regards
Edmund

micron
Posts: 155
Joined: Mon Feb 15, 2010 8:33 am
Location: New Zealand

Re: repetition detection

Post by micron » Sun Oct 30, 2011 2:24 am

Edmund wrote:Glass tests for a repetition at the beginning of every node. If the position is found in the line between the current node and the root node, draw score is returned immediately.
For a 15 ply search from the start position I am getting 4404 repetitions out of 34115733 tests. So on average there is a repetition on every 7747 nodes.
I would be very much interested, what your engines return for this index.
Spandrel's repetition code corresponds to your description, but my results are hard to reconcile with your index 7747.

Code: Select all

ply   repets     tests    tests/repet
 9        1       80945    80945
10        4      226157    56539
11       10      624105    62410
12       25     1026408    41056
13       96     2985570    31099
14      163     5194982    31871
15      276     8257388    29918
16      559    14557943    26042
17     1384    32776902    23682
18     2647    61886605    23379
19     6885   127764844    18556
20    36756   476123023    12953
21    53554   713229233    13317
Robert P.

User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

Re: repetition detection

Post by sje » Sun Oct 30, 2011 2:47 am

A better test that isn't specific to any search is to read PGN data for many different games and check if the program says "Repetition" for, and only for, those games marked "Repetition".

See: http://www.talkchess.com/forum/viewtopic.php?t=40916

User avatar
Matthias Gemuh
Posts: 3238
Joined: Thu Mar 09, 2006 8:10 am
Contact:

Re: repetition detection

Post by Matthias Gemuh » Sun Oct 30, 2011 5:47 am

sje wrote:A better test that isn't specific to any search is to read PGN data for many different games and check if the program says "Repetition" for, and only for, those games marked "Repetition".

See: http://www.talkchess.com/forum/viewtopic.php?t=40916
Engines are not compelled to claim 3-fold-rep draws, so there may be unmarked games that contain 3-fold-rep.
My engine was quite strong till I added knowledge to it.
http://www.chess.hylogic.de

Mincho Georgiev
Posts: 454
Joined: Sat Apr 04, 2009 4:44 pm
Location: Bulgaria
Contact:

Re: repetition detection

Post by Mincho Georgiev » Sun Oct 30, 2011 7:15 am

Pawny - 15 ply search without qnodes = 174 repetitions from start position.
With qnodes = 205. The numbers you gave seems little bit high, but your search tree it's probably much wider, so I can't really say if they are.

Edmund
Posts: 668
Joined: Mon Dec 03, 2007 2:01 pm
Location: Barcelona, Spain
Contact:

Re: repetition detection

Post by Edmund » Sun Oct 30, 2011 8:06 am

Mincho Georgiev wrote:Pawny - 15 ply search without qnodes = 174 repetitions from start position.
With qnodes = 205. The numbers you gave seems little bit high, but your search tree it's probably much wider, so I can't really say if they are.
Thanks for this comparison data. For a 15 ply search your engine reports 17773520 visted nodes. So your total / hit ratio would be 86700.

Edmund
Posts: 668
Joined: Mon Dec 03, 2007 2:01 pm
Location: Barcelona, Spain
Contact:

Re: repetition detection

Post by Edmund » Sun Oct 30, 2011 8:11 am

Thanks to mincho and Robert for their comparison.
For "visited nodes" / "reported repetitions" for ply 15
- Pawny reports 86700
- Spandrel reports 29918
- Glass Reports 7747

Low could either mean very bad move ordering or some bug in repetition detection. Anyway I will have a closer look into this issue.

User avatar
Desperado
Posts: 638
Joined: Mon Dec 15, 2008 10:45 am

Re: repetition detection

Post by Desperado » Sun Oct 30, 2011 10:59 pm

Hello Edmund,

There can be another issue measuring from "start position".

Depending on how the the ep-flag is set by the engine.

eg: * only double pawn push condition

eg: * or double pawn push condition + check if a real ep-capture can
be done at next move.
(So is there a pawn which can do the ep-capture).


Both variants can be implemented of course, but because
the board states may be different after a double pawn push it can
lead to earlier/delayed (matter of viewpoint) repetition detection
in the lines. Needless to say that this can have significant impact,
because from the "start-position" the highest number of double
pawn pushes can be made.

Michael

Edmund
Posts: 668
Joined: Mon Dec 03, 2007 2:01 pm
Location: Barcelona, Spain
Contact:

Re: repetition detection

Post by Edmund » Sun Oct 30, 2011 11:05 pm

Desperado wrote:Hello Edmund,

There can be another issue measuring from "start position".

Depending on how the the ep-flag is set by the engine.

eg: * only double pawn push condition

eg: * or double pawn push condition + check if a real ep-capture can
be done at next move.
(So is there a pawn which can do the ep-capture).


Both variants can be implemented of course, but because
the board states may be different after a double pawn push it can
lead to earlier/delayed (matter of viewpoint) repetition detection
in the lines. Needless to say that this can have significant impact,
because from the "start-position" the highest number of double
pawn pushes can be made.

Michael
Thanks for this hint. Glass only considers ep-squares if there is truly a capture possible for the hash-signature. Would be interesting to hear about how this is done in Pawny or Spandrel.

Ferdy
Posts: 4109
Joined: Sun Aug 10, 2008 1:15 pm
Location: Philippines

Re: repetition detection

Post by Ferdy » Mon Oct 31, 2011 1:29 am

Edmund wrote:I suspected some problems with repetition detection in Glass, so today I collected some figures for how often a repetition is triggered.

Glass tests for a repetition at the beginning of every node. If the position is found in the line between the current node and the root node, draw score is returned immediately.

For a 15 ply search from the start position I am getting 4404 repetitions out of 34115733 tests. So on average there is a repetition on every 7747 nodes.

I would be very much interested, what your engines return for this index.

Regards
Edmund
Deuterium:

Code: Select all

 15    19     98     717133 b1c3 b8c6 g1f3 g8f6 e2e3 e7e6 f1e2 f8e7 e1g1 e8g8
                            d2d4 d7d5 c1d2 e7d6 e2d3 (1.9) 
 repCnt=25, repTries=717133, Tries/Cnt=28685

Post Reply