Draw by 3-fold repetition?

trojanfoe · Post by **trojanfoe** » Fri Jan 06, 2012 6:25 pm

This may seem like a pretty simple question, but I wonder if anyone can confirm that this game can be claimed as a draw by 3-fold repetition? I am just trying to validate my code.

Many thanks,
Andy

Code: Select all


&#91;Event "Engine Tournament"&#93;
&#91;Site "Machine 'localhost'"&#93;
&#91;Date "2012.01.06"&#93;
&#91;Round "4"&#93;
&#91;White "Komodo64 3 sse4.2"&#93;
&#91;Black "Stockfish 2.2 JA"&#93;
&#91;Result "1/2-1/2"&#93;

1.d4 &#123;+0.00&#125; d5 &#123;+0.00&#125; 2.Nf3 &#123;+0.00&#125; Nf6 &#123;+0.00&#125; 3.c4 &#123;+0.00&#125; e6 
&#123;+0.00&#125; 4.Nc3 &#123;+0.00&#125; c6 &#123;+0.00&#125; 5.Bg5 &#123;+0.00&#125; h6 &#123;+0.00&#125; 6.Bh4 
&#123;+0.00&#125; dxc4 &#123;+0.00&#125; 7.e4 &#123;+0.00&#125; g5 &#123;+0.00&#125; 8.Bg3 &#123;+0.00&#125; b5 &#123;+0.00&#125; 
9.Ne5 &#123;+0.00&#125; Bb4 &#123;+0.00&#125; 10.a3 &#123;+0.00&#125; Ba5 &#123;+0.00&#125; 11.Qf3 &#123;+0.00&#125; Bb7 
&#123;+0.00&#125; 12.Rd1 &#123;+0.00&#125; h5 &#123;+0.00&#125; 13.h4 &#123;+0.00&#125; g4 &#123;+0.00&#125; 14.Qe3 
&#123;+0.00&#125; Nfd7 &#123;+0.00&#125; 15.Be2 &#123;+0.00&#125; Nxe5 &#123;+0.00&#125; 16.Bxe5 &#123;+0.00&#125; f6 
&#123;+0.00&#125; 17.Bf4 &#123;+0.00&#125; Nd7 &#123;+0.00&#125; 18.O-O &#123;+0.00&#125; Qe7 &#123;+0.00&#125; 19.e5 
&#123;+0.00&#125; f5 &#123;+0.00&#125; 20.Bg5 &#123;+0.00&#125; Qf7 &#123;+0.00&#125; 21.Rb1 &#123;+0.00&#125; a6 
&#123;+0.00&#125; 22.a4 &#123;+0.00&#125; O-O &#123;+0.00&#125; 23.Bh6 &#123;+0.00&#125; Rfe8 &#123;+0.00&#125; 24.Bg5 
&#123;+0.00&#125; Rac8 &#123;+0.00&#125; 25.Rfc1 &#123;+0.00&#125; Bb6 &#123;+0.00&#125; 26.Rd1 &#123;+0.00&#125; Nf8 
&#123;+0.00&#125; 27.Ra1 &#123;+0.00&#125; Nh7 &#123;+0.00&#125; 28.Bf4 &#123;+0.00&#125; Red8 &#123;+0.00&#125; 29.Bf1 
&#123;+0.00&#125; Rd7 &#123;+0.00&#125; 30.axb5 &#123;-0.69&#125; axb5 &#123;+0.00&#125; 31.b3 &#123;-0.54&#125; cxb3 
&#123;+0.80&#125; 32.Ne2 &#123;-0.54&#125; b2 &#123;+1.13&#125; 33.Rab1 &#123;-0.37&#125; c5 &#123;+1.01&#125; 34.Rxb2 
&#123;-0.42&#125; Bc6 &#123;+1.09&#125; 35.Rbb1 &#123;-0.41&#125; c4 &#123;+0.88&#125; 36.Nc3 &#123;-0.50&#125; Rcd8 
&#123;+1.73&#125; 37.Rxb5 &#123;-0.70&#125; Bxd4 &#123;+1.73&#125; 38.Rxd4 &#123;-0.86&#125; Rxd4 &#123;+1.73&#125; 
39.Rc5 &#123;-0.63&#125; Be8 &#123;+1.57&#125; 40.Rxc4 &#123;-0.69&#125; Rxc4 &#123;+1.49&#125; 41.Bxc4 
&#123;-0.57&#125; Nf8 &#123;+1.29&#125; 42.Ne2 &#123;-0.61&#125; Rc8 &#123;+1.41&#125; 43.Bb3 &#123;-0.89&#125; Qe7 
&#123;+1.61&#125; 44.Bg5 &#123;-0.39&#125; Qc5 &#123;+1.65&#125; 45.Qf4 &#123;-0.58&#125; Bf7 &#123;+1.73&#125; 46.Bf6 
&#123;-0.48&#125; Nh7 &#123;+1.73&#125; 47.Qh6 &#123;-0.53&#125; Qf8 &#123;+1.73&#125; 48.Qe3 &#123;-0.37&#125; Ra8 
&#123;+1.33&#125; 49.Nd4 &#123;-0.42&#125; Nxf6 &#123;+1.61&#125; 50.exf6 &#123;-0.48&#125; Ra1 &#123;+1.69&#125; 51.Kh2 
&#123;-0.45&#125; Qd6 &#123;+1.65&#125; 52.g3 &#123;-0.59&#125; f4 &#123;+1.13&#125; 53.gxf4 &#123;-0.49&#125; Qd8 
&#123;+1.21&#125; 54.Bxe6 &#123;-0.48&#125; Qxf6 &#123;+2.82&#125; 55.Bxf7 &#123;-0.49&#125; Kxf7 &#123;+1.81&#125; 
56.Kg2 &#123;-0.42&#125; Qa6 &#123;+2.26&#125; 57.Kh2 &#123;-0.42&#125; Qa2 &#123;+0.80&#125; 58.Nb3 &#123;-0.29&#125; 
Rd1 &#123;+1.89&#125; 59.Nc5 &#123;-0.29&#125; Qd5 &#123;+1.61&#125; 60.Ne4 &#123;-0.30&#125; Rd3 &#123;+1.33&#125; 
61.Qa7 &#123;-0.28&#125; Kf8 &#123;+1.21&#125; 62.Ng3 &#123;-0.26&#125; Rb3 &#123;+1.13&#125; 63.f5 &#123;-0.22&#125; 
Qd6 &#123;+1.09&#125; 64.Qa1 &#123;-0.11&#125; Rf3 &#123;+0.92&#125; 65.Kg2 &#123;-0.05&#125; Qd5 &#123;+0.84&#125; 
66.Kg1 &#123;-0.05&#125; Ke7 &#123;+0.84&#125; 67.Qa7 &#123;-0.05&#125; Kd6 &#123;+0.84&#125; 68.Qb6 &#123;-0.03&#125; 
Kd7 &#123;+0.84&#125; 69.Nxh5 &#123;-0.04&#125; Qxf5 &#123;+1.21&#125; 70.Qd4 &#123;-0.04&#125; Kc6 &#123;+1.21&#125; 
71.Ng3 &#123;-0.05&#125; Qc5 &#123;+1.29&#125; 72.Qa4 &#123;-0.05&#125; Kb6 &#123;+0.36&#125; 73.Ne4 &#123;-0.05&#125; 
Qd5 &#123;+0.24&#125; 74.Qb4 &#123;-0.05&#125; Kc7 &#123;+0.20&#125; 75.Nc3 &#123;-0.05&#125; Qe5 &#123;+0.20&#125; 
76.Qc4 &#123;-0.05&#125; Kd8 &#123;+0.20&#125; 77.Qg8 &#123;-0.05&#125; Ke7 &#123;+0.20&#125; 78.Nd5 &#123;-0.05&#125; 
Kd6 &#123;+0.20&#125; 79.Qd8 &#123;-0.05&#125; Kc5 &#123;+0.12&#125; 80.Ne3 &#123;-0.05&#125; Rg3 &#123;+0.04&#125; 
81.fxg3 &#123;-0.05&#125; Qxe3 &#123;+0.12&#125; 82.Kg2 &#123;-0.05&#125; Qf3 &#123;+0.00&#125; 83.Kg1 &#123;-0.05&#125; 
Qxg3 &#123;+0.00&#125; 84.Kf1 &#123;-0.05&#125; Qf3 &#123;+0.00&#125; 85.Kg1 &#123;-0.05&#125; g3 &#123;+0.00&#125; 
86.Qe7 &#123;+0.03&#125; Kc4 &#123;+0.00&#125; 87.Qc7 &#123;+0.03&#125; Kd3 &#123;+0.00&#125; 88.Qd6 &#123;+0.05&#125; 
Ke2 &#123;+0.00&#125; 89.Qa6 &#123;+0.03&#125; Ke1 &#123;+0.00&#125; 90.Qe6 &#123;+0.03&#125; Kd1 &#123;+0.00&#125; 
91.Qd7 &#123;+0.04&#125; Kc1 &#123;+0.00&#125; 92.Qd4 &#123;+0.04&#125; Kc2 &#123;+0.00&#125; 93.Qc5 &#123;+0.04&#125; 
Kd1 &#123;+0.00&#125; 94.Qb6 &#123;+0.04&#125; Kd2 &#123;+0.00&#125; 95.Qa7 &#123;+0.03&#125; Qe4 &#123;+0.00&#125; 
96.Qa5 &#123;+0.03&#125; Kd1 &#123;+0.00&#125; 97.Qa1 &#123;+0.03&#125; Kd2 &#123;+0.00&#125; 98.h5 &#123;-0.03&#125; 
Qe3 &#123;+0.00&#125; 99.Kg2 &#123;-0.02&#125; Qf2 &#123;+0.00&#125; 100.Kh3 &#123;+0.00&#125; g2 &#123;+0.00&#125; 
101.Qb2 &#123;+0.03&#125; Ke1 &#123;+0.00&#125; 102.Qc1 &#123;+0.04&#125; Ke2 &#123;+0.00&#125; 103.Qc2 
&#123;+0.00&#125; Ke3 &#123;+0.00&#125; 104.Qc5 &#123;+0.00&#125; Ke2 &#123;+0.00&#125; 105.Qe5 &#123;-0.01&#125; Kf1 
&#123;+0.00&#125; 106.Qb5 &#123;-0.02&#125; Kg1 &#123;+0.00&#125; 107.Qb1 &#123;-0.02&#125; Qf1 &#123;+0.00&#125; 
108.Qe4 &#123;-0.02&#125; Qf2 &#123;+0.00&#125; 109.h6 &#123;-0.05&#125; Kf1 &#123;+0.00&#125; 110.Qb1 &#123;-0.05&#125; 
Ke2 &#123;+0.00&#125; 111.Qc2 &#123;+0.04&#125; Ke3 &#123;+0.00&#125; 112.Qc5 &#123;-0.05&#125; Ke2 &#123;+0.00&#125; 
113.Qe5 &#123;+0.03&#125; Kf1 &#123;+0.00&#125; 114.Qb5 &#123;-0.05&#125; Ke1 &#123;+0.00&#125; 115.Qe5 
&#123;-0.05&#125; Kf1 &#123;+0.00&#125; 116.Qb5 &#123;-0.05&#125; Ke1 &#123;+0.00&#125; 117.Qe5 &#123;-0.05&#125; Kf1 
&#123;Draw by 3-fold repetition&#125;  1/2-1/2

hgm · Post by **hgm** » Fri Jan 06, 2012 6:52 pm

XBoard adjudicates it as a rep-draw, when I paste the game into it, switch to EditGame mode, and then redo the last move.

trojanfoe · Post by **trojanfoe** » Fri Jan 06, 2012 7:02 pm

Many thanks! Looks like that bit of my code is OK then.

hgm · Post by **hgm** » Fri Jan 06, 2012 7:06 pm

Not necessarily, as this was not a very demanding test. You should at least try it when the checking starts in a position where there are still castling rights, or where you can e.p. capture. Or where the repetition occurs with the other side on move...

trojanfoe · Post by **trojanfoe** » Fri Jan 06, 2012 7:20 pm

I do need to do more testing but the detection is done by comparing a position hash which takes the piece positions, castling rights, ep mask and side-to-move into account, so they 'should' be OK (if it's not then the hashing algorithm is broken, not the 3-fold rep test).

Cheers,
Andy

petero2 · Post by **petero2** » Sat Jan 07, 2012 1:40 am

hgm wrote:Not necessarily, as this was not a very demanding test. You should at least try it when the checking starts in a position where there are still castling rights, or where you can e.p. capture. Or where the repetition occurs with the other side on move...

I have the following position in the test suite for my chess program:

[d]4k2n/8/8/8/4p3/8/3P4/3KR2N w - - 0 1[/d]

After the moves "d4 Ng6 Ng3 Nh8 Nh1 Ng6 Ng3 Nh8 Nh1", there is a three-fold repetition because no en passant capture was possible after d4, due to the fact that the pawn is pinned by the rook.

stevemulligan · Post by **stevemulligan** » Sat Jan 07, 2012 8:57 pm

trojanfoe wrote:I do need to do more testing but the detection is done by comparing a position hash which takes the piece positions, castling rights, ep mask and side-to-move into account, so they 'should' be OK (if it's not then the hashing algorithm is broken, not the 3-fold rep test).

See this thread and the posts by Steven Edwards regarding rgstat. After you implement the rgstat command, different game endings should fall within a certain range. It helped reveal some hard to find bugs that I would never have known about. It's also a very handy way to profile move generation speed.

Dave_N · Post by **Dave_N** » Sat Jan 07, 2012 9:54 pm

Are you sure you need hash tables to detect draws?

I thought about clearing a data-structure (marking as over-writeable) every time a pawn moved or king castled ... if there is an EP square then you don't need to write the position into the structure etc.

perhaps you could store the pieces in coordinate form, 8 bits for each piece position, then you simply build a tree. I thought about a stack for each piece type excluding pawns because the table is cleared after a pawn move. The worst case is obviously almost 100 ply so perhaps pieces that have not moved don't need to be added so often or something ...

hgm · Post by **hgm** » Sat Jan 07, 2012 10:45 pm

He doesn't use the hash table. Just the hash key. Most engines store a small array of hash keys since the last irreversible move, through which they then do a linear search. You could make a small dedicated hash table for this too (which for games without irreversiblemoves is probably advisable)..

Dave_N · Post by **Dave_N** » Sat Jan 07, 2012 11:22 pm

Ahh ok, perfect hashing with only the piece values ... the worst case is only 50 ply so a hash key sounds right, and linear searching over up to 50 compares doesn't sound too bad either. For the case of the link with the discussion of large datasets I was reminded of hash collisions.

Draw by 3-fold repetition?

Draw by 3-fold repetition?

Re: Draw by 3-fold repetition?

Re: Draw by 3-fold repetition?

Re: Draw by 3-fold repetition?

Re: Draw by 3-fold repetition?

Re: Draw by 3-fold repetition?

Re: Draw by 3-fold repetition?

Re: Draw by 3-fold repetition?

Re: Draw by 3-fold repetition?

Re: Draw by 3-fold repetition?