Repetition Detection

[Colin]

Hi, my engine doesn't do repetition detection, and often falls into endless loop when it plays against itself or another engine.

I use a transposition table and iterative deepening, QS, and rotated bitboards, but don't use Null Move Pruning or anything else.

Is there a standard way to check for repetition of position?

Thanks

[plattyaj]

Hi, my engine doesn't do repetition detection, and often falls into endless loop when it plays against itself or another engine.

I use a transposition table and iterative deepening, QS, and rotated bitboards, but don't use Null Move Pruning or anything else.

Is there a standard way to check for repetition of position?

Thanks

I can tell you what Schola does. Perhaps there are better ways but it's very simple to implement. Have another hash table (can be pretty small) that is just used for repetition. When you move to a new position, look for an entry with the same hashcode - if there is one, increment the count and return that, if not create a new entry. Decrement and, if necessary, remove the entry when you leave the position.

The main difference is that you must always create entries so I use a linked list for each hash code. Also the standard caveats about collisions apply - you might find a "repetition" that isn't. If this is a problem, store the whole position too though you might just want to do that for the actual game positions, not the ones in the search tree.

Andy.

[Sven]

Hi, my engine doesn't do repetition detection, and often falls into endless loop when it plays against itself or another engine.

I use a transposition table and iterative deepening, QS, and rotated bitboards, but don't use Null Move Pruning or anything else.

Is there a standard way to check for repetition of position?

Thanks

Store the TT hash key for each position in game history (including current search path). At each node, compare the current hash key with the stored ones from previous positions, starting at (currentPly - 4), stepping back by -2 and stopping when you get below (currentPly - fiftyMovesCounterOfCurrentPos) since a move that resets the 'fifty' counter makes the position from where it is made non-repeatable. (As does castling but normally you don't store any data that tells you immediately when castles were made.) If the hash keys are equal then the historical position is repeated (with an extremely high probability).

During search, when being at least two plies away from root, most people assume that it is safe to return a draw score already on the first repetition. Outside the search (or at height 1), to claim a draw during a game according to FIDE rules requires to encounter a second repetition, i.e. third occurrence of the same position. To distinguish the second repetition from the first, one possible way could be to store a repetition counter for each historical position which is normally set to 0 for non-repeating positions and set to the repeated position's repetition counter + 1 when detecting a repetition; at least this is what I do in my engine.

Hope that helps; of course there are many other different ways to do it but I guess that the detection algorithm is quite common.

Sven

[AndrewShort]

my move stack stores the hash key of the resulting position. Hash key includes the pieces/locations/castling rights/en passant rights/side to move. When encountering a position during search, you first search the hash keys in the move stack (skip 2, since you only care about positions where side to move is the same), then, if necessary, you search the game history of real moves. [You are comparing the current hash key to the hash keys in the move stack and game history. - the current hash key is managed incrementally in MakeMove()]

During search I treat draw by 2fold rep as a draw.
At the game level, of course, I treat draw by 3fold rep as a draw.

[hgm]

If you want a quick and dirty solution that solves 95% of the repetition problem:

Freeze positions that have occurred in the game in the hash table (by giving them the maximum depth you can represent, and make your replacement code such that it never overwrites entries with this depth),
and then set the score of suc poitions to 0.

It won't fall into repeat loops then, as any attempt to return to the position will give you a hash hit of sufficient depth, with a zero score.

[bob]

Hi, my engine doesn't do repetition detection, and often falls into endless loop when it plays against itself or another engine.

I use a transposition table and iterative deepening, QS, and rotated bitboards, but don't use Null Move Pruning or anything else.

Is there a standard way to check for repetition of position?

Thanks

The simplest solution, by far, is to create a list of previous positions. Just store the Zobrist hash signature after each move. Then, in the search, search this list backward looking for a duplicate entry. A 2-fold repetition is just as likely to draw as a 3-fold repetition and you will see it much sooner. To make it more efficient, you can use the 50-move-counter when searching backward as there is no point in searching farther back than the 50-move counter since the move that reset it guaranteed you that no repetition can occur between positions before that point and positions after that point.

It adds very little overhead and works well.

[bob]

If you want a quick and dirty solution that solves 95% of the repetition problem:

Freeze positions that have occurred in the game in the hash table (by giving them the maximum depth you can represent, and make your replacement code such that it never overwrites entries with this depth),
and then set the score of suc poitions to 0.

It won't fall into repeat loops then, as any attempt to return to the position will give you a hash hit of sufficient depth, with a zero score.

Main drawback is that this won't work with an SMP search.

[xsadar]

If you want a quick and dirty solution that solves 95% of the repetition problem:

Freeze positions that have occurred in the game in the hash table (by giving them the maximum depth you can represent, and make your replacement code such that it never overwrites entries with this depth),
and then set the score of suc poitions to 0.

It won't fall into repeat loops then, as any attempt to return to the position will give you a hash hit of sufficient depth, with a zero score.

That's an intriguing idea. Doesn't see repetitions of positions that occur in the search, but at least it keeps repetitions from happening in the game. And it takes essentially zero extra time in the search and is easy to implement.

I think you might even be able to extend the idea a bit to see repeats of positions that occur in the search. When you begin the search of a position, you could lock it in hash with a score of zero. Then when you complete the search of that position, you replace the score with the correct score and unlock it. Seems to me that this might even take less time than the traditional history search at each node. What do people think?

[AndrewShort]

forgot to say I stop searching the move stack when I encounter any pawn move or any capture. obviously those moves irrevocably change the board, so no need to search the stack before those moves. Note the capture move itself might be the start of a draw (with the captured piece off the board)

[bob]

If you want a quick and dirty solution that solves 95% of the repetition problem:

Freeze positions that have occurred in the game in the hash table (by giving them the maximum depth you can represent, and make your replacement code such that it never overwrites entries with this depth),
and then set the score of suc poitions to 0.

It won't fall into repeat loops then, as any attempt to return to the position will give you a hash hit of sufficient depth, with a zero score.

That's an intriguing idea. Doesn't see repetitions of positions that occur in the search, but at least it keeps repetitions from happening in the game. And it takes essentially zero extra time in the search and is easy to implement.

I think you might even be able to extend the idea a bit to see repeats of positions that occur in the search. When you begin the search of a position, you could lock it in hash with a score of zero. Then when you complete the search of that position, you replace the score with the correct score and unlock it. Seems to me that this might even take less time than the traditional history search at each node. What do people think?

I think he is saying that you _also_ flag them as you are searching them as well. Bruce Moreland did this in Ferret. Issue is a double hash probe, once for normal stuff, once for the repetition, and then at the end of each node, you have to undo the store. Bruce used two hash tables to make SMP search work, if in a complex way. If you use the normal hash, you still have to store an entry when you enter search() recursively, and remove it when you exit. if you don't do it in the search, it is not worth anything as a great number of repetitions happen in the search and if you don't catch it there if you want to avoid it or go for a draw, you might never get the chance...