I have looked into over hundreds of testgames recently, and I couldn't even find a single case of repetition in a cycle of other than 4 plies. In human games, this may happen more frequently, but in engine-engine games it seems rather uncommon. Think about it.
In that case one should go all the way, i.e. only check 4 plies back (so no for loop).
Perhaps it is sensible to do this with a depth restriction. In that case the occasionally incorrectly evaluated nodes will be researched at greater depth. In that way Stockfish will not make obvious blunders.
Joerg Oster wrote:I have looked into over hundreds of testgames recently, and I couldn't even find a single case of repetition in a cycle of other than 4 plies.
That is not really relevant. Repetitions can rarely be forced, so the main reason for having the engine recognize them is to avoid them. This is an argument of the type: "not many people are shoplifting. So we might as well make it legal to leave supermarkets with your groceries without paying."
I made the same error in Xiangqi: almost never a game ends in perpetual chasing (which would be losing for the one who chases). So why should my engine test for it? And indeed, playing against other engines that also don't test for it has less than 1% of the games ending in a chase. However, when I palayed engines that don't know about it against an equaly strong one that does, 18% of the games ended in a perpetual chase.
So the relevant test would be to only consider games between engines that do know about 6-loops, and those that don't, and see how often they occur then.
If speed of repetition detection is that much of an issue, why not avoid the loop most of the time using a small hashtable? And of course use a separate array for storing the history keys (as was already being talked about on the FishCooking list).
The argument against this has always been that repetition detection does not cost time.
I do not know if speed is an issue but if Jorg Oester got a 3% speedup by doing incomplete checking there must be something to be gained by a more efficient implementation.
The culprit in Stockfish might be the double dereferencing per double ply.
In my Shogi engine I have the problem that there are no irreversible moves, so that you might have to go back through the entire game history for every repeat check (if there were no null moves between the current node and the root). I use a small hash table there to keep track of what currently might be in the key stack. It then only starts searching through the key stack if it is not excluded that the sught key could be there. I preferred that over storing everything in a hash table, because then I would have to worry about what to do if that table overflows.
I suppose that in chess the reversible history is typically much shorter, and in any case shorter than 50 moves. So it seems you could already benefit a lot from having a bitmap in an int64 (for each side) that would record if a key with a given 6 low-order bits is present in the table.
hgm wrote:I suppose that in chess the reversible history is typically much shorter, and in any case shorter than 50 moves. So it seems you could already benefit a lot from having a bitmap in an int64 (for each side) that would record if a key with a given 6 low-order bits is present in the table.
This certainly seems worth a try. It has the advantage over a hashtable with somewhat more entries that you can simply copy/update it when making a move, so it can be cleared after each capture or pawn move. And it presents no difficulties when doing an SMP split by copying the position structure. (My SMP implementation only copies the moves from root to split node, and lets the joining thread recreate the rest on its own time, but in SF everything is blocked while copying the position structure so even a small 256-byte hashtable would be problematic.)
The update of the 64-bit hashtable should probably not be implemented as part of make_move() but separately, because there is no/less need for it in the qsearch.
suppose that in chess the reversible history is typically much shorter, and in any case shorter than 50 moves. So it seems you could already benefit a lot from having a bitmap in an int64 (for each side) that would record if a key with a given 6 low-order bits is present in the table.
That's a clever idea! It might be used in Stockfish to supplement the current system. The position stack should only be searched if the bitmap has the corresponding bit set.
