Back Up Next

Repetition Detection

Why repetition detection is necessary

It's important to figure out the repetition draw problem.  If a position repeats three times with the same side to move, a draw can be claimed.  It's very bad if a program is ahead by a rook and gets into a situation where it is cycling through a couple of checks forever.  The opponent claims a draw in a position that is easily winning.

Solving this problem is a matter of detecting previously played played positions and doing the appropriate thing.  If a program understands repetitions it can aim for them or avoid them as the board situation warrants.  A program can attempt to find a perpetual check if it is losing, and it can avoid this situation if it is winning.

A fairly trivial choice before we start

There are two kinds of positions that can be repeated.  Game history positions are positions that have actually been played on the board, in the game.  Tree positions are positions that have occurred in the line the program is now searching.  They haven't been played on the board yet, but the program has managed to think about undoing a move and playing it again.

I think that it is clear that repetition of tree positions should be immediately detected and handled.  Traditionally, a draw score is returned in these cases, but I have heard that some programs return a deliberately positive score if there is a middlegame perpetual check, as long as the program is doing the checking.  This is supposed to reflect the idea that if you find a perpetual check, there is often more.  If repetitions within the tree are not handled, the program will not see cases involving perpetual check and other repetition draws.

It's not as obvious what to do about positions that appear in both the tree and game history.  If a position has appeared twice in the game history, and once in the tree, that can be treated as a draw, since if that position appears on the board again it is a draw.  The difficult case is a position that has appeared once in the game and once in the tree.

Many programs treat these positions as draws.  This causes a program to efficiently attempt to achieve a draw via repetition if it is in trouble and the opponent wants to repeat.  The down-side is that the program will sometimes make unnatural moves.

I have seen a couple of examples in actual play.  One of them involved a game between Gnuchess and my program.  Gnuchess had a win in a K+P ending and missed it, and the programs wandered off into a series of drawn positions.  Eventually, they wandered back to the position where Gnuchess missed a win.  My program was happy to repeat this position, because it scored it as a draw, since it had already occurred in the game history.  Of course, Gnuchess found the win the second time through.

Another game was between my program and a human master named Greg Kennedy.  Kennedy was up two pawns, but made a bad move that allowed a simple tactic such as a knight fork, which won one of the pawns back.  Kennedy saw that his king was in check, and he had to move it.  He moved it back to the square that it had just been on.  My program, rather than taking the pawn, resulting in a position where it was a pawn down, decided instead to undo its last move, leading to a repetition of the position two plies previous.  Its repetition cause it to "expect" that Kennedy would move his king back and let the program fork him again.  Of course he didn't, and he remained two pawns up.

It's possible to create many other hypothetical cases.  A strong human player has an overwhelming attack, but messes up and allows the program to escape with its king, so all the human has now is a perpetual check, since he's down material and has no mate.  The program would happily move its king right back into the situation it just escaped from, since those positions are repetitions and are therefore considered draws.

In my programs I have fixed this by ignoring positions that are repeated once in the game history and once in the tree.  This solves the problems described above but it introduces some new problems.  The program will repeat positions a couple of times, so sometimes it plays very annoying chess, since it is not forced to at least appear to be making progress.  This might tend to bother human opponents, or opposing operators at computer chess tournaments.  It could also cost the program wins, because when it gets into difficult endgame positions, it isn't really forced to make progress, and could diddle around for a long time, while getting closer and closer to the fifty-move limit.

The choice of which system to use is a matter of taste.

Possible implementations

There are several ways that repetitions can be detected.  One of them is in use in Tom Kerrigan's TSCP, which he credits John Stanback for.  The comments in the code claims that it works, but there is no information about how or why it works, so I don't know what it does.  If you want to understand it, you'll have to look in TSCP.

Implementations that I can understand and explain involve Zobrist keys.  If you want to implement a transposition hash table, you'll have already implemented Zobrist keys, so you already have them available.  What you need to do with these Zobrist keys is recognize that the key corresponding to current position within a tree search is equal to they key corresponding to a position further back in the game tree.

One method of doing this involves maintaining a first-in last-out stack of keys in the current line, plus keys from the game history.  In order to detect a repetition, the stack is iterated, and keys are compared, in order to see if the current key is already in the stack.

It is not necessary to go through the entire list, it's only necessary to go backwards until a pawn move or a capture is encountered, since these moves lead to irreversible changes in the game history.  You can never have a repetition of a position that occurred before the last capture or pawn move made.

This sounds like it would be expensive to do, and perhaps it is, but I believe that some programs are doing it like this.

Early on in my chess programming experience, I wrote a Usenet post about hashing, and I received a response from Ken Thompson, author of Belle (amongst many other achievements).  He told me that he detected repetitions by using the transposition hash table, as follows:

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.

A simpler scheme involves making a smaller hash table.  When a node is entered, the table is probed, if if the Zobrist key for the current position is in the table, a draw score is returned.  Otherwise, the key is added.  When the node is exited, the key is deleted.  This is very straightforward, and hash element collisions can be handled easily, since the table isn't full, elements are managed in first-in last-out order, and there are no problems with replacement scheme.

I'm reluctant to say that this technique is better than the other, since the other was devised by Ken Thompson.  There are some problems with this system, notably that it's an extra data structure and several extra functions that need to be written to manipulate it.

There are also some worries when a program is changed so that it can use a multi-processor search, but the problems that happen don't seem any more serious to me than the problems that are faced when a program that uses the Thompson scheme is converted.

If you want to see code for this secondary hash table scheme, check out Gerbil.  I don't include a source-code example here because it's rather implementation specific.

 
Send mail to brucemo@seanet.com with questions or comments about this web site.
Copyright © 2001 Bruce Moreland
Last modified: 01/16/03