Using TT for detecting repetitions

Code, algorithms, languages, construction...
hyatt
Posts: 1242
Joined: Thu Jun 10, 2010 2:13 am
Real Name: Bob Hyatt (Robert M. Hyatt)
Location: University of Alabama at Birmingham
Contact:

Re: Using TT for detecting repetitions

Post by hyatt » Wed Oct 28, 2015 2:52 pm

H.G.Muller wrote: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.

The key point is that if you have 16 threads, probably 16 * 64 entries would hold all "open" nodes. You have to store the real-game nodes also, but that is still a modest number. I think Bruce (Moreland) used 2048 entries in Ferret for this purpose, but we never discussed what he did once he went to the threaded search. I presume this gets copied so that it is thread-local..

Post Reply