Repetitions

From Chessprogramming wiki
Jump to: navigation, search

Home * Search * Repetitions

M. C. Escher, Reptiles, 1943 [1]

Repetitions of positions may happen during game play and inside the search of a chess program due to reversible moves played from both sides, which might be nullified in one or multiple further reversible moves. The player to move may claim a draw if the same position occurs three times, or will occur after an intended move, in any order, with the same player to move.

Two positions are considered same or equal, if all occupied squares and kind of pieces (not necessarily the same piece) they occupy are the same, the castling rights for both sides did not change, and no en passant capture was possible during the first occurrence, even if obviously not played.

Assigning Draw Score

Threefold repetition implies a position occurred thrice, that is repeated twice. When to score the position as a draw, however, is an entirely different matter. Most programs do this on the first repetition, no matter whether the first occurrence of the repeated position appears in the current search space, or not. Other programs consider that fact, they avoid cycles inside the current search tree to make it a directed acyclic graph (DAG), but allow a one-fold repetition, if the first occurrence appears in the game history before the current root. Anyway, to wait for the second repetition one has its pros and cons. The Repetition score is either zero or the contempt factor.

Rules

The rules of chess state a threefold repetition of a position gives the player to move the option to claim a draw, no matter whether the threefold repetition already occurred yet, or is about to occur after declaring the intended move in conjunction with the draw claim. The latter case is a bit tricky for computers, and is/was likely not strictly implemented in most programs or their user interfaces, since a draw message text or box appeared after the repetition occurs but no claim before. Since July 2014 a fivefold repetition is sufficient without any claim [2].

Fide Rule

[3]

9.2 The game is drawn, upon a correct claim by the player having the move, when the same position, for at least the third time (not necessarily by a repetition of moves)
 a) is about to appear, if he first writes his move on his scoresheet and declares
    to the arbiter his intention to make this move, or
 b) has just appeared, and the player claiming the draw has the move.
Positions as in (a) and (b) are considered the same, if the same player has the move, pieces of the same kind and color occupy the same squares, and the possible moves of all the pieces of both players are the same. Positions are not the same if a pawn that could have been captured en passant can no longer in this manner be captured or if the right to castle has been changed temporarily or permanently. 

Since July 01, 2014

9.6  If one or both of the following occur(s) then the game is drawn: 
 a) the same position has appeared, as in 9.2b, for at least five consecutive alternate moves by each player.  
 b) any consecutive series of 75 moves have been completed by each player without the movement of any pawn 
    and without any capture. If the last move resulted in checkmate, that shall take precedence. 

Former Rule

A former (German) rule, was believed to be sufficient to make the game of chess finite [4] :

A chess game ends with a draw if a sequence of moves - with all pieces in exactly the same positions - is played three times successively. 

was proved not sufficient by Max Euwe in 1929 by applying the Prouhet–Thue–Morse Sequence [5] , i. e. with following move indices [6] :

0 Nb1-c3 Nb8-c6 Nc3-b1 Nc6-b8
1 Ng1-f3 Ng8-f6 Nf3-g1 Nf6-g8

Euwe's prove was the reason, two other rules in force each of which guarantees chess to be a finite game, threefold repetition of positions and the fifty-move rule.

Repetition of Positions

By position we mean the location of all the pieces on the Chessboard as well as castling rights and en passant status. Since the rule speaks about the piece position, and not their identity (i.e. artificially constructed repeated position where the rooks of one player changed places still would be a draw), repetition may be detected by using the Zobrist- or BCH signatures of the position.

Transposition Table

One possible implementation was used by Ken Thompson in Belle, who told Bruce Moreland that he detected repetitions by using the transposition hash table, as follows [7] :

The idea is to set an "open" flag in the position's transposition table element when the hash table is probed. This flag stays set until the position is no longer being searched, meaning when the search function returns a value for that position.
At any given time, the only nodes that are "open" are nodes that are in the game history, or are in the current line in the tree search, so if the hash table probe encounters an open node, it must be because the current position has occurred somewhere before
This has the advantage that it uses data structures that are already present in the typical chess program, but there are a few problems with this idea. The hash table element must be written when a node is entered, so an "always replace" scheme must be used. This isn't a problem for Thompson, since his scheme involves using an "always replace" table, but other implementations might not use this kind of replacement scheme. Another problem is that there can be hash table entry collisions, and they must be dealt with. I am not talking about hash key collisions which occur when two positions map to the same 64-bit key, I'm talking about when two particular positions want to share the same hash table element, which should be pretty common. If two open nodes that want to share the same hash element, it's not immediately obvious what to do, other than not detect repetitions on the second one. Perhaps this problem could be dealt with via a re-hashing scheme, but this seems like an annoying thing to add in order to support functionality that isn't central to what the transposition table should be doing. A final problem is that it is hard to figure out how to adapt this to a multiprocessor search where there might be several search threads accessing the same hash table. When an open node is encountered, it might not indicate a repetition at all, since it could belong to a line being searched by another processor. This problem sounds complicated to solve. 

List of Keys

Most programs use an array or list of Zobrist- or BCH-keys and compare the current signature with keys 4, 6, 8 and so on plies along the actual variation. This is usually quite cheap, since testing often does not require looking through the entire list, since captures and pawn moves, that reset the halfmove clock for the purpose of enforcing fifty-move rule are known to make a repetition impossible. Since each thread or process may own its own copy of the game-record, this approach has also some merits in parallel search implementations.

John Stanback about his implementation in Zarkov [8]:

In Zarkov I simply keep 32 bits of hash for each move in the game history, whether it has actually occurred on the board or during the current search. I also have a variable that contains the ply at which the last irreversible move occurred.  At each node in the search, including quiescence, if the current ply is at least 4 plies beyond the last irreversible move I test the current hash value against those for each position in the game history (for the current side to move only) back to the last irreversible move and count the number of matches (repetitions).  
If the count is 2, then this is the third repetition and a draw score is returned.  If the count is 1 and the current_ply > root_ply+2 then a draw score is also returned. This avoids problems that can occur if the program thinks that a move at the root leads to a draw (due to a single repetition) when the opponent may vary, but it also lets the program treat repeated positions in the search as draws which helps a lot. Since most positions in a search are less than 4 plies beyond the last irreversible move the repetition() function is rarely called and the performance hit for detecting repetitions is negligible. 

Dedicated Hash Table

Some programs, like Gerbil or Rookie use a separate small hash table, actually an implementation of a Bloom filter revealed by Ronald de Man as mentioned by Marcel van Kervinck in his thesis The design and implementation of the Rookie 2.0 Chess Playing Program [9]:

It is tempting to use the transposition table to help detecting repeated positions. However, overloaded transposition tables can lose entries. So we choose something else [10][11] : a dedicated, small, repetition hash table. This tables has 2^14 one-byte entries that are initially zero (totaling 16KB). When entering a new position, the low 14 bits of the hash-key are used to index the table and bump up its value by one. The value is restored after unmaking the move. When entering a node and its value is found to be non-zero already, we know there could be a cycle, which we verify by tracing back the actual variation. The repetition table is large enough to sufficiently reduce the number of false hits and this vaporizes the costs of futile back-traces. 

Repetition of Moves

An alternative, pragmatical approach based on repetitions of moves was proposed by Vladan Vučković and Đorđe Vidanović in 2004, as implemented in Axon [12] and discussed in CCC [13] [14].

The algorithm needs a move list containing the game record including the variation actually searched, 16-bit entries with origin and target square, and a flag whether a move is irreversible, as only information required. Starting with the last move made, the list is scanned backwards as long there are reversible moves. A local concatenating list of up to 24 entries (one entry for each piece able to make reversible moves) is used to determine cycles per piece, where consecutive moves on their target squares are merged to one "pseudo" move, using the earliest origin and the latest target square. If all distinct white and black moving pieces in the chain list contain equal from- and to coordinates, all cycles of moves are closed and a move repetition is detected. This is how the algorithm as given in the paper in 8086 assembly looks in pseudo C++, square coordinates are offset from a 12*12 mailbox approach, so that empty entries have no valid square index.

bool repetition(SMove *pVariant) {
   SMove chainList[24], m;
   short c = 0, i;

   for (i=0; i < 24; ++i) {
      chainList[i].setEmpty();
   }

l: m = *pVariant--; /* fetch move and decrement move list pointer */
   if ( m.isReversible() ) { 
      /* lookup chain list for from-coordinate that match current to coordinate */
      for (i=0; i < 24; ++i) {
         if ( m.to == chainList[i].from ) {
            if ( m.from == chainList[i].to ) {
              if ( --c == 0 )
                  return true; /* repetition detected */
               chainList[i].setEmpty();
               goto l;
            } 
            chainList[i].from = m.from; /* concatenate moves */
            goto l;
         }
      }
      /* lookup for next empty slot, to add the current move in the chain list */
      for (i=0; i < 24; ++i) {
         if ( chainList[i].isEmpty() ) {
            chainList[i] = m;
            ++c;
            goto l;
         }
      }
   }
   return false;
}

See also

Publications

1929

  • Max Euwe (1929). Mengentheoretische Betrachtungen über das Schachspiel. Proc. Konin. Akad. Wetenschappen (Amsterdam)

1980 ...

1990 ...

2000 ...

2010 ...

Forum Posts

1990 ...

1995 ...

2000 ...

Re: Detecting three-fold repetition? by John Stanback, CCC, July 17, 2000 » SCP Repetition detection

2001

2002

2003

2004

2005 ...

2007

2008

2009

2010 ...

2011

2012

2013

2014

2015 ...

2016

This should be in the wiki by Steven Edwards, CCC, April 13, 2016

2017

2018

2020 ...

2021

2022

External Links

featuring Kristina Koropecki, Charlotte Danhier, Catherine De Biasio

References

  1. Picture gallery "Back in Holland 1941 - 1954" from The Official M.C. Escher Website
  2. FIDE's new rules for chess by Mark Lefler, CCC, July 20, 2014
  3. Fide Handbook - E.I.01A. Laws of Chess
  4. Mathematical Problems - Max Euwe's sequence by Manfred Börgens
  5. Max Euwe (1929). Mengentheoretische Betrachtungen über das Schachspiel, Proc. Konin. Akad. Wetenschappen (Amsterdam)
  6. Mathematical Problems - Max Euwe's sequence - Solution by Manfred Börgens
  7. Repetition Detection from Bruce Moreland's Programming Topics
  8. Draw by Repetition Code, post 4 by John Stanback, rgcc, December 31, 1996
  9. Marcel van Kervinck (2002). The design and implementation of the Rookie 2.0 Chess Playing Program. Masters Thesis, pdf
  10. Courtesy Ronald de Man for revealing this implementation trick
  11. Re: triple repetition by Ronald de Man, rgcc, October 27, 1997
  12. Vladan Vučković, Đorđe Vidanović (2004). A New Approach to Draw Detection by Move Repetition in Computer Chess Programming. CoRR arXiv:cs/0406038
  13. A New Approach to Draw Detection by Move Repetition by Gian-Carlo Pascutto, CCC, July 29, 2004
  14. Draw Detection by Move Repetition Procedure - Comments by Đorđe Vidanović, CCC, August 01, 2004
  15. Re: Aquarium IDEA, repetitions, and minimax over cycles by syzygy, OpenChess Forum, September 22, 2012
  16. A New Approach to Draw Detection by Move Repetition by Gian-Carlo Pascutto, CCC, July 29, 2004
  17. Draw Detection by Move Repetition Procedure - Comments by Đorđe Vidanović, CCC, August 01, 2004
  18. Upcoming repetition detection by Marcel van Kervinck, OpenChess Forum, April 06, 2013

Up one Level