Draw by 3-fold repetition?

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
trojanfoe
Posts: 65
Joined: Sun Jul 31, 2011 9:57 am
Location: Waterlooville, Hampshire, UK

Draw by 3-fold repetition?

Post by trojanfoe » Fri Jan 06, 2012 5: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


[Event "Engine Tournament"]
[Site "Machine 'localhost'"]
[Date "2012.01.06"]
[Round "4"]
[White "Komodo64 3 sse4.2"]
[Black "Stockfish 2.2 JA"]
[Result "1/2-1/2"]

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

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

Re: Draw by 3-fold repetition?

Post by hgm » Fri Jan 06, 2012 5: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.

User avatar
trojanfoe
Posts: 65
Joined: Sun Jul 31, 2011 9:57 am
Location: Waterlooville, Hampshire, UK

Re: Draw by 3-fold repetition?

Post by trojanfoe » Fri Jan 06, 2012 6:02 pm

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

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

Re: Draw by 3-fold repetition?

Post by hgm » Fri Jan 06, 2012 6: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...

User avatar
trojanfoe
Posts: 65
Joined: Sun Jul 31, 2011 9:57 am
Location: Waterlooville, Hampshire, UK

Re: Draw by 3-fold repetition?

Post by trojanfoe » Fri Jan 06, 2012 6: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
Posts: 587
Joined: Mon Apr 19, 2010 5:07 pm
Location: Sweden
Contact:

Re: Draw by 3-fold repetition?

Post by petero2 » Sat Jan 07, 2012 12: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.

User avatar
stevemulligan
Posts: 117
Joined: Wed Jul 20, 2011 12:54 pm
Location: Ottawa, Canada
Contact:

Re: Draw by 3-fold repetition?

Post by stevemulligan » Sat Jan 07, 2012 7: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
Posts: 153
Joined: Fri Sep 30, 2011 5:48 am

Re: Draw by 3-fold repetition?

Post by Dave_N » Sat Jan 07, 2012 8: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 ...

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

Re: Draw by 3-fold repetition?

Post by hgm » Sat Jan 07, 2012 9: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
Posts: 153
Joined: Fri Sep 30, 2011 5:48 am

Re: Draw by 3-fold repetition?

Post by Dave_N » Sat Jan 07, 2012 10: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.

Post Reply