Elegant algorithm for detecting repetitions?

[AAce3]

Hi all,
I've been wondering if there's a more 'elegant' algorithm than looping through past zobrist keys. So, I probed through stockfish's source code and it uses something called "Cuckoo tables?" I'm not quite sure exactly how they work (I am not very familiar with C++ code unfortunately), and the link to the paper provided seems to have been hijacked by spam and ads... I thought I might ask here to see if anyone has a pdf of the original paper or could explain how it works.

Thanks.

[RubiChess]

You have PM

[hgm]

I think the cuckoo tables were a way to anticipate repetitions, and suppress moves that would allow the opponent to create a repetition in his next move.

For detecting the repetition itself I have used 3 methods:
1) the usual linear search through the stack of keys, up to the last irreversible move.
2) a small hash table with keys (using linear rehash), also containing the ply level of the last position to have that key.
3) setting a flag in the TT entry for all positions on the current branch or game history.

Method 2 is preferable over 1 in games without irreversible moves, such as Shogi and Crazyhouse. Because one would not want to detect null-move-spanning repetitions, it also remembers the ply level of the latest null move, which it then can compare with the level stored in the table. Before the search you clear the table, and put all positions in it from the game history from after the latest irreversible move that already occured twice.

The hash-table-based method protects positions from the game history from overwriting (e.g. by giving them maximum depth), and sets their score to a draw score. They should already be exact scores. This will satisfy any later probe. The method is not very suitable for SMP with shared hash table, as each search thread woul need its own repeat flag.

[AAce3]

I see.
I think perhaps it is just simplest to store the last 6 or so keys within the board state and compare for twofold repetition, producing a draw score when that occurs. The cuckoo tables are very interesting - I will have to look into them.

[hgm]

The really important thing is to suppress back-and-forth moving when ahead. Longer repeat loops typically occur only in situations where it is a draw anyway. A poor-man's solution is to penalize moving the same piece as 2 ply earlier, and penalize it extra hard when it reverses that move (when ahead). If the reversible-ply counter is larger than 2 after the move..

[Bo Persson]

I see.
I think perhaps it is just simplest to store the last 6 or so keys within the board state and compare for twofold repetition, producing a draw score when that occurs. The cuckoo tables are very interesting - I will have to look into them.

In most programs, captures are searched early. And if the previous move was a capture, there just cannot be a repetition, so the state search can be very short.

[dangi12012]

I see.
I think perhaps it is just simplest to store the last 6 or so keys within the board state and compare for twofold repetition, producing a draw score when that occurs. The cuckoo tables are very interesting - I will have to look into them.

In most programs, captures are searched early. And if the previous move was a capture, there just cannot be a repetition, so the state search can be very short.

But you always have to compare all zobrists of the last n moves before irreversibility - or are there smarter algos?
On top of my head I would use mm_epi_movemask to compare 16bits zobrist parts but for the last 16 positions at once(256bit).
A positive or wrong positive has to be compared closely but that will only happen in 1/64000.
So it seems really cheap to begin with.

[Bo Persson]

I see.
I think perhaps it is just simplest to store the last 6 or so keys within the board state and compare for twofold repetition, producing a draw score when that occurs. The cuckoo tables are very interesting - I will have to look into them.

In most programs, captures are searched early. And if the previous move was a capture, there just cannot be a repetition, so the state search can be very short.

But you always have to compare all zobrists of the last n moves before irreversibility - or are there smarter algos?

No, but n can often be zero, and then it is about as fast as it can get.

[hgm]

If you put the position keys along the current branch in a hash table, you just have to test whether the new position is in that table. If the table is large enough to be mostly empty that means you have to compare only to the key in the table entry you hash to. It will either be empty or the sought key.

This is probably not optimal, because it would make a mostly empty table waste a large amount of cache space. You could make the table large enough to hold two times the number of expected entries; in that case you have to compare on average to two entries. Instead of rehashing you could implement each hash bucket as a stack. If you are prepared to be sloppy, you could only compare to the top of the stack. (I.e. you would save the old value of the entry you hash to in a local variable of the node, before writing the new key there. And restore it when you return.) This way collisions would hide some of the older positions, so that you would overlook some repetitions. But the chances that all positions in a repeat loop would be hidden that way is very small. So the engine would still know the loop leads to a draw when it tries to stay in it indefinitely.

[dangi12012]

If you put the position keys along the current branch in a hash table, you just have to test whether the new position is in that table. If the table is large enough to be mostly empty that means you have to compare only to the key in the table entry you hash to. It will either be empty or the sought key.

I dont think a rehash is needed - since zobrist is already uniform.

Code: Select all

History[64k];
History[pos.zob() >> 48] != 0
...verify in game tree

Or the Idea I had earlier

Code: Select all

_mm256 last16; //Last 16 positions with the last 16 bits of the zobrist
_mm_movemask_epi(_mm256_cmpeq_epi16(last16, _broadcast(pos.zob())) != 0
...verify in game tree

Both with advantages and disadvantages. But both are very cheap to detect repetitions. Also on that topic there are forced repetition chains that are quite long.
But in summary: To detect 3 fold repetition its O(1) not O(n)