# Programming three-fold repetition for my chess engine

I'm making a chess engine that has to implement a three-fold repetition as my AI vs AI engine repeats the same moves over and over again (Have a look at my post here - My chess AI makes the same repeated moves). I've read the rules of this scenario from the wiki and would like to implement it. I'm not sure if I have understood the rules thoroughly, so what I'm doing here is -

1. Checking if the present move made (from the movelog I have) has already occurred before.
2. If it did, check for one more occurrence (as we need three in total).
3. If the moves pattern for all the three re-occurred moves is same, return true.

Please have a look at my Java code and suggest me the corrections.

``````    boolean isThreeFoldRepetition() {
List<Move> allMoves = Table.get().getMoveLog().getMoves();
int currentMoveIndex = allMoves.size()-1;
int secondFoldMoveIndex = currentMoveIndex - 4;
int firstFoldMoveIndex = secondFoldMoveIndex - 4;
int distance = currentMoveIndex - secondFoldMoveIndex - 1;

while(firstFoldMoveIndex >= 0){
Move thirdFoldMoveMade = allMoves.get(currentMoveIndex);
Move secondFoldMoveMade = allMoves.get(secondFoldMoveIndex);
Move firstFoldMoveMade = allMoves.get(firstFoldMoveIndex);

if(thirdFoldMoveMade.equals(secondFoldMoveMade) &&
secondFoldMoveMade.equals(firstFoldMoveMade) &&
firstFoldMoveIndex - distance >= 0){
int gap;
for(gap = 1; gap <= distance; gap++){
thirdFoldMoveMade = allMoves.get(currentMoveIndex - gap);
secondFoldMoveMade = allMoves.get(secondFoldMoveIndex - gap);
firstFoldMoveMade = allMoves.get(firstFoldMoveIndex - gap);

if(!thirdFoldMoveMade.equals(secondFoldMoveMade) || !secondFoldMoveMade.equals(firstFoldMoveMade))
break;
}
if(gap == distance)
return true;
}

secondFoldMoveIndex -= 2;
firstFoldMoveIndex = secondFoldMoveIndex - distance - 3;
}
return false;
}
``````

## 4 Answers

Threefold-repetition is about a position (not moves) occurring three times. Those positions do not have to be reached by the same moves.

Also (as this also seems to be confused sometimes) it is completely irrelevant when this happens, e.g. you can have the same positions after moves 10, 42 and 63 and it would still be a draw.

You should check whether the position is repeated. So basically at every move you need to check whether the position occurred in the game before. By position I mean the same position of all pieces on the board and the same castling rights and the same player to move and the same enpassant rights. That is, basically you are checking whether the FEN are the same (except for halfmove clock and fullmove number).

Something like:

``````int positionCount=0;
while(iterate through game positions) {
if ( positionToCheck.piecesPosition == iterationPosition.piecesPosition &&
positionToCheck.castleRights == iterationPosition.castleRights &&
positionToCheck.enPassantRights == iterationPosition.enPassantRights &&
positionToCheck.playerToMove == iterationPosition.playerToMove ) {
positionCount++;
}
if (positionCount==3) { return true; }
}
return false;
``````

Of course you can simplify the above algorithm. E.g. you only need to iterate over position with the same player to move. Also you only need to iterate over positions back to the last pawn move, capture or castling move.

• @SrikaraKrishnaKanduri: If the position of the pieces on the board is the same, the "same set of legal moves" just means that there should be the same castling rights, same player to move and the same enpassant rights. I believe these are much easier/faster to check than having to compare all possible moves. I updated my answer. Mar 31, 2017 at 9:12
• @SrikaraKrishnaKanduri: Not sure what you mean. You could store the FEN strings for all positions that occurred in the game. That would typically be around 100 strings of up to around 100 characters each. But there are more efficient ways to implement this as you can read about here: chessprogramming.wikispaces.com/Repetitions Mar 31, 2017 at 9:25
• I suppose FEN will do the work. Thank you. Mar 31, 2017 at 9:28
• And you can stop looking back any time something non-reversible happens: pawn moves, captures and castling. Mar 31, 2017 at 12:03
• @DavidRicherby I will consider that. Thank you. Mar 31, 2017 at 12:57

Although @user1583209 is on the right track. His approach would only work for a chess GUI but too slow for a chess engine. Modern engines only check for the last few moves, they won't go all the way back to the initial position because that'd be an almost waste of time.

You have complicated your code too much. In reality, checking for repetition is very simple:

https://github.com/official-stockfish/Stockfish/blob/master/src/position.cpp

``````int cnt = 0;
for (int i = 4; i <= end; i += 2)
{
stp = stp->previous->previous;

// At root position ply is 1, so return a draw score if a position
// repeats once earlier but after or at the root, or repeats twice
// strictly before the root.
if (   stp->key == st->key
&& ++cnt + (ply - i > 0) == 2)
return true;
}
``````

You go back in the history and check the key for your position. Very simple. You may want to ignore the `ply` check.

You should have a way to hash your position, if you don't you will need it for transposition table anyway.

A useful reference link to prove my idea is correct:

http://talkchess.com/forum/viewtopic.php?t=59322&highlight=move+repetitions

• I don't have a history on my engine. I may have to implement it like you suggested. Thank you. Mar 31, 2017 at 9:30
• @SrikaraKrishnaKanduri Check my edited link. Mar 31, 2017 at 9:35
• if you happen to have all the Fen positions stored in a move list object, I believe checking them backwards until the other 2 repetitions are found OR a 0 halfmove is found (while also only start looking when both the index move AND the halfmove is greater than 7) is faster than checking a key vs the rest of the keys? Maybe requires some string manipulation (splitting to remove clocks and see the halfmove clock) but they both just lighting fast, except to what I understood, keys are tested vs ALL keys? Feb 2, 2021 at 2:01

I would look at the source code for TSCP which implements zobrist keys. Basically you assign a unique number to each position and store the numbers in a list. Then check if the same number is in the list three times. you generate the unique number based on the position of the pieces, en passant square, side to move. here i have copied and pasted the TSCP code (authored by Tom Kerrigan). hash_piece is indexed by the color(2), piece type(6), and position(64). hash_side is the side to move. hash_ep is the en passant square. The initialization function populates a table of random numbers for each of these possible entries. To generate the unique position for a position
you look up all the entries correspoding to a given position and xor the numbers from the three tables (this is the set_hash function). You probably dont need the hash_rand on newer computers with better random number generators.

``````void init_hash()
{
int i, j, k;

srand(0);
for (i = 0; i < 2; ++i)
for (j = 0; j < 6; ++j)
for (k = 0; k < 64; ++k)
hash_piece[i][j][k] = hash_rand();
hash_side = hash_rand();
for (i = 0; i < 64; ++i)
hash_ep[i] = hash_rand();
}

/* hash_rand() XORs some shifted random numbers together to make sure
we have good coverage of all 32 bits. (rand() returns 16-bit numbers
on some systems.) */

int hash_rand()
{
int i;
int r = 0;

for (i = 0; i < 32; ++i)
r ^= rand() << i;
return r;
}

/* set_hash() uses the Zobrist method of generating a unique number (hash)
for the current chess position. Of course, there are many more chess
positions than there are 32 bit numbers, so the numbers generated are
not really unique, but they're unique enough for our purposes (to detect
repetitions of the position).
The way it works is to XOR random numbers that correspond to features of
the position, e.g., if there's a black knight on B8, hash is XORed with
hash_piece[BLACK][KNIGHT][B8]. All of the pieces are XORed together,
hash_side is XORed if it's black's move, and the en passant square is
XORed if there is one. (A chess technicality is that one position can't
be a repetition of another if the en passant state is different.) */

void set_hash()
{
int i;

hash = 0;
for (i = 0; i < 64; ++i)
if (color[i] != EMPTY)
hash ^= hash_piece[color[i]][piece[i]][i];
if (side == DARK)
hash ^= hash_side;
if (ep != -1)
hash ^= hash_ep[ep];
}
``````
• This is also my approach in my answer. Apr 4, 2017 at 15:50
• Cool, I upvoted you. Ive always liked the TSCP source code Apr 4, 2017 at 17:08

Why not just keep a map indexed by the position hash pointing to a count of how many times it has been seen so far? No iteration required... just update the hash as you traverse the move tree.

• That's known as transposition table. It's possible. Apr 1, 2017 at 2:13
• I iterated through the list of FEN for now. I will try to update it to your idea later. Thanks for the answer. Apr 3, 2017 at 7:18
• In a typical search the amount of positions reached could be > 100000000, how big would that map have to be?
– user24649
Feb 14, 2021 at 6:23