Draw by position repetition

[metax]

I want to add a detection of draw by move repetition to my engine. I have transposition tables and all that stuff implemented, as I heard that might be useful for draw detection.
And what do you think of this approach to the problem?

[Gerd Isenberg]

It was already discussed in 2004, see
Repetition of Moves and References in
http://chessprogramming.wikispaces.com/Repetitions

It is recommend to use either a List of Keys or a dedicated small hashtable to detect repetitions of positions rather than repetitions of moves.

[bob]

I want to add a detection of draw by move repetition to my engine. I have transposition tables and all that stuff implemented, as I heard that might be useful for draw detection.
And what do you think of this approach to the problem?

You can't beat an array of Zobrist hash signatures for repetition detection. It is simple, costs almost nothing, and will work reliably. Using the "string" approach in that paper fails to recognize a significant class of repetitions that happen in endgames, rather than via perpetual checks.

[metax]

You can't beat an array of Zobrist hash signatures for repetition detection. It is simple, costs almost nothing, and will work reliably. Using the "string" approach in that paper fails to recognize a significant class of repetitions that happen in endgames, rather than via perpetual checks.

Namely which one?

[bob]

You can't beat an array of Zobrist hash signatures for repetition detection. It is simple, costs almost nothing, and will work reliably. Using the "string" approach in that paper fails to recognize a significant class of repetitions that happen in endgames, rather than via perpetual checks.

Namely which one?

You don't care about things like Rh2+ Kg1 Rg2+ Kf1 Rf2+ Kg1 etc. You can see the moves are repeating. But take a king rook and pawns ending. It is quite easy to reach a position where you have two choices. Repeat the position for the second (or even third) time, or give up a pawn and make progress. But there is no consecutive series of repeated moves. We once played a game with Zarkov (Stanbeck's program) where we thought we could win it and the only thing that made it possible was the correct repetition detection code that actually looked for repeated positions regardless of the moves.

For example, you might miss the repetition of Rf1-f8, when reaching this via Rf1-f4 followed by Rf4-f8. The two sequences of moves are not the same, but the resulting position might be.

The rule (repetition) is _not_ about repeating the same moves. It is about repeating the same positions. Sometimes the two are the same, sometimes not.

[cms271828]

Hi, I don't have repetition detection set up yet, but I'm thinking it could be done like this..

With move generation, we have an array in which each element corresponds to all the moves generated at that particular ply, then when we reach a new node, we just overwrite the moves at the correct element in the array.

perhaps in a similar way, we could have an array:

root position:
ply 1 position:
ply 2 position:
ply 3 position:
...

so as soon as we enter a node, the zobrist key for that node is correct (since updated in makemove), so we can write the zobrist into the correct array position.

Suppose we write into the 'ply 7' entry, then we could look at 'ply 6' and 'ply 5' entries, if they all give the same key, then the current node is a 3fold repetition of position, and we can just return 0 (or something about 0 depending on if you have a contempt factor)

I think this would have to be done in the node, before probing the hash table.
Also in the QS nodes, when D<0, we have just captures going on (I do anyway), so there can be no repeat of position here, so can ignore writing into array or reading from it, as all subsequent positions will be new as well.

If this logic is correct so far, I think it could be tweaked since nodes in which the last move was a pawn move, castling move, or capture will be new positions, so they will still need to be stored in array, but pointless checking the previous 2 entries.

Good / Crap idea?

[Sven]

Hi, I don't have repetition detection set up yet, but I'm thinking it could be done like this..

With move generation, we have an array in which each element corresponds to all the moves generated at that particular ply, then when we reach a new node, we just overwrite the moves at the correct element in the array.

perhaps in a similar way, we could have an array:

root position:
ply 1 position:
ply 2 position:
ply 3 position:
...

so as soon as we enter a node, the zobrist key for that node is correct (since updated in makemove), so we can write the zobrist into the correct array position.

Suppose we write into the 'ply 7' entry, then we could look at 'ply 6' and 'ply 5' entries, if they all give the same key, then the current node is a 3fold repetition of position, and we can just return 0 (or something about 0 depending on if you have a contempt factor)

I think this would have to be done in the node, before probing the hash table.
Also in the QS nodes, when D<0, we have just captures going on (I do anyway), so there can be no repeat of position here, so can ignore writing into array or reading from it, as all subsequent positions will be new as well.

If this logic is correct so far, I think it could be tweaked since nodes in which the last move was a pawn move, castling move, or capture will be new positions, so they will still need to be stored in array, but pointless checking the previous 2 entries.

Good / Crap idea?

When you are at ply N you can look for repetition starting at ply N-4 and then look backward from there at each second ply, i.e. N-6, N-8, ..., and stop at ply N-fifty (with fifty := the value of the 50-moves counter at ply N). At plies N-1, N-3, ... the opponent was to move, and from ply N-2 until ply N each side has made only one move which can't possibly be a repetition. Therefore you can start at N-4.

Stopping at N-fifty is not perfect but sufficient, although it does not take into account that also castling, which does not affect the 50-moves rule, is an irreversible move. Trying to be perfect here for a very rare case might affect perfomance.

Sven

[bob]

Hi, I don't have repetition detection set up yet, but I'm thinking it could be done like this..

With move generation, we have an array in which each element corresponds to all the moves generated at that particular ply, then when we reach a new node, we just overwrite the moves at the correct element in the array.

perhaps in a similar way, we could have an array:

root position:
ply 1 position:
ply 2 position:
ply 3 position:
...

so as soon as we enter a node, the zobrist key for that node is correct (since updated in makemove), so we can write the zobrist into the correct array position.

Suppose we write into the 'ply 7' entry, then we could look at 'ply 6' and 'ply 5' entries, if they all give the same key, then the current node is a 3fold repetition of position, and we can just return 0 (or something about 0 depending on if you have a contempt factor)

I think this would have to be done in the node, before probing the hash table.
Also in the QS nodes, when D<0, we have just captures going on (I do anyway), so there can be no repeat of position here, so can ignore writing into array or reading from it, as all subsequent positions will be new as well.

If this logic is correct so far, I think it could be tweaked since nodes in which the last move was a pawn move, castling move, or capture will be new positions, so they will still need to be stored in array, but pointless checking the previous 2 entries.

Good / Crap idea?

Close. But if you are at ply 7, you only check plies 5, 3 and 1. not only does the position have to be the same, the side to move also has to be the same. What you describe, other than that minor detail, is essentially what I do in Crafty and it is a correct way of doing this.

[cms271828]

I made a silly error, the repeated positions don't need to be consecutive as in 7,6,5.

I can also see now that odd and even ply positions can't be equal.

So I need a way to count the positions when we get to them, which instantly brings me to this idea as I am writing this:

Use a small table, for the sake of argument, say size 2^10 = 1024.

Code: Select all

int[] table = new int[1024]; // java code

Then, if we have a 64 bit zobrist, for a particular position, we can use first 10 bits to index this into the table, and do:

Code: Select all

int numberOfAppearances = ++table[key&1023];
if(numberOfAppearances == 3) return 0;

This table would have to also contain positions encountered prior to search, but this is trivial.

So assuming the above is correct, what size table would be good?
If a game has 100 moves, then the 100 positions (or 101) would have to pack into a table size 1024, giving a 1 in 10 chance of a collision with different positions (I think thats right), but this is not good, so maybe 2^16 = 65,536 would be better to virtually eliminate this.

Or is this high a value going to impact on performance like a big hash table does?

Any thoughts?

[cms271828]

But now I'm thinking this may be a little over the top, since we could just back track through the odd/even ply until we reach the last pawn move or capture.

I need to think about it.