Using TT for detecting repetitions

[thevinenator]

in this article..

http://chessprogramming.wikispaces.com/repetitions

Ken Thompson states...

The idea is to set an "open" flag in the position's transposition table element when the hash table is probed. This flag stays set until the position is no longer being searched, meaning when the search function returns a value for that position.

At any given time, the only nodes that are "open" are nodes that are in the game history, or are in the current line in the tree search, so if the hash table probe encounters an open node, it must be because the current position has occurred somewhere before

My TT is implemented as "always replace". No MP issues, single threaded.

so would the following logic work to implement this?

Upon entering a position, probe the TT.
If the TT probe finds the position, it tests the open flag. if the open flag is set, then it is the second (or more) time the position has been probed. The stored score (and the open flag to indicate a repetition) are returned.
If the open flag is not set, the TT probe sets it and returns the stored score (and the flag to indicate non-repetition).
upon returning, if the open flag is set, return 0 up the tree, otherwise continue processing as normal.
if the position is not found, a NULL pointer is returned and the code deals with that separately.

if/when the same position is stored again, the open flag is always reset to 0.

Does that summarize it correctly?

[hyatt]

That is the basic idea. Won't fly for parallel search of course. Bruce Moreland used this for a while. Another approach is to create a separate small hash for "open positions" since there can only be as many as there are plies in the current path. You can duplicate this per thread and get away from the thread issue one table poses.

And you have to keep all moves since the last non-reversible move in that as well, which is a bit unusual in normal TT usage...

[thevinenator]

Hum, first attempt failed miserably. I am using ID, so i'm guessing the flags have to be cleared between iterations?

[hyatt]

Hum, first attempt failed miserably. I am using ID, so i'm guessing the flags have to be cleared between iterations?

No, when you reach a position and do a probe, you do the "open". But as you leave that position, you "close" it. At the end of an iteration, nothing should be marked as "open"...

If, by IID, you mean "internal iterative deepening" then that has to be "special-cased" to avoid losing the "open" indicator.

[thevinenator]

Ok, I Grok.

i made the corrections to my search code and wow, what a difference! It really cuts down on the amount of TT that is used and greatly speeds up a lot of positions.

My code doesn't handle "previous moves" yet, but going down the tree from a imported FEN works nicely.

Oh, when i mentioned ID, i just meant Iterative Deepening. As you point out, that isn't a problem since all the set open-flags are "undone" when you get back to the top of the search. I had thought about playing with IID, but in lieu of the additional complexity of checking for repetitions in the TT, i'll put that way down on my list.

[hyatt]

If you like the approach, you should seriously consider a separate (small) TT for draws only. Then you can replicate them per-thread and not have a parallel search roadblock that is difficult to fix...

[H.G.Muller]

This method would not work with an 'always-replace' TT, because the open positions would be overwritten all the time, and you would no longer recognize the repetitions. It is essential that the 'open' positions are somehow protected from replacement.

I use a similar method in micro-Max, where I modify the hash entry for the root position to contain a zero score with exact bound type and maximum depth (d=127) when the move away from it is made in the game. Although micro-Max has a replace-always TT, entries with d=127 are protected from replacement (and in the rare case another position would map to such an entry, it will simply not be stored). This way the entry will always satisfy any future hit on it, and will cause a hash cutoff with a draw score. (So no explicit 'open' marker, or code to handle it, is needed.) So micro-Max can recognize repetition of positions from the game history as draws. But it is blind to repetitions in the search, and thus cannot plan for delivering or avoiding perpetuals in advance.

In King Slayer I have a 'shallowest-of-two' replacement, and I store an exact 0-score with d=127 in the entry just before I start searching it, and then replace it with the true score, bound type and depth when the search returns its score. The d=127 then automatically protects it from overwriting. It takes a bit of care to make sure this is done properly on search abort (because of timeout). Especially in nodes that iteratively deepen King Slayer keeps a copy of the hash entry as it should be in a local variable, and updates it after a completed iteration. On search abort it then copies this to the actual entry, to erase the temporary absolute draw there. As King Slayer (like micro-Max) uses the 'second-floor-exit' method for performing moves at game level, the entry for the root position (which has become game history) will remain stored as an absolute draw.

As Bob pointed out, this would not work in a multi-threaded search.

[mjlef]

H.G.,

How do you deal with the times all of the hash entry you probe are "open"? If it is 2 or even 4 entries, there must be times when all of them have the "open" bit set, and there would be no place to put the current "open" position. A really huge hash would help, but this would still happen. Am I missing something?

The "traditional" "search stack, where you save the hash key for each move in a line that has been search (one stack per thread if MP search) seems easier, and other than the very tiny change of a hash collision, simple to implement.

Mark

[H.G.Muller]

Micro-Max has an always-replace TT, and protects d=99 entries from overwrite. So if another position maps to the same entry it is out of luck, and will not be hashed. In a table with 1M entries (12MB), and a game history of 100 ply this means 1 in 10,000 positions cannot be stored. But even if it would be stored it could have been replaced before it was probed, and that would bring you in the same situation. If two game positions would map to the same entry, the later one would not be stored, so return to it would not be recognized as a draw. It would have of course been better to replace the earlier one, as that is much less likely to be reached again. But even with this small blind spot in its rep-detection (the birthday paradox makes this happen once in 200 moves with 1M entries and 100 ply) the damage is minute: during its search it can now go there like it was no repeat, but it cannot plan playing the move from there it previously played, because that still would contain the draw score (with >99% probability). So it would already have to plan on playing the second-best move (if it doesn't want the draw), which often is enough to deter it from making the undetected repeat.

Always-replace just isn't a very good algorithm when the TT size gets tight. Micro-Max was designed to work with a generous hash table, and if it doesn't, the problem that the entries near the root will be obliterated before the next iteration starts will hurt it far more than the occasional miss of a repetition.

King Slayer has shallowest-of-two replacement. This makes protecting the 'open' entries superfluous, as they have maximum depth, and would never be picked for replacement. So basically the situation is the same there as with micro-Max. If two open nodes map to the same bucket initially both will be stored, as the second one replaces the non-open entry in the bucket as standard choice. But one of the two will then very quickly be overwritten by some low-depth position that maps into that bucket, so it doesn't really help (other than that it is now a 50-50 chance whether the most-recent or oldest position from the game history will survive). An improvement here could be to explicitly suppress overwriting the shallowest entry if it was open. The probability for a triple collision with 1M entries and 100 game positions would be only 1 in 6e8.

But I think that is over-doing it. Having a repetition go undetected is not that big a deal. Engines want to make repetitions they should have avoided perhaps only once every 50 moves. Which is enough to bungle 40% (1/e) of their wins if they go completely undetected, as most games last just over 50 moves. But if only once every 100 moves the repetition detection fails, the fraction of wins that become rep-draws is already reduced to 0.4%. And 1M entries is really an extremely small hash table by current standards. With realistic hash size it would be morelike 0.04%.

[H.G.Muller]

To be sure: using a separate stack of hash keys for detecting repetitions is the superior method, if you don't care about code size and complexity. And it is 'thread-proof'. So most of my engines use that method. King Slayer was designed for simplicity, having as little distracting code as possible, which is why I used the TT-marking method. But note that the stack of keys can become a bit problematic in games without irreversible moves, where you would have to compare with all keys (with the same side to move) since the beginning of the game. Shogi is such a game, because of the drops. So running through the entire stack of keys can start to soak up a lot of time, in a long game. So hashing the keys (in a small non-lossy hash table, i.e. with rehashing after collisions) would probably be the best way. You could store the ply level at which the position occurred, and let the search keep track of the level of the latest null move, in order to exclude null-move-spanning repeats.