Hash tables & search

[Jaime Benito de Valle]

just wondering...

let's say your engine searches up to ply 12 during its turn, and moves.
The oponent moves.
Would it be a very bad idea to fill the hash tables with the previous 12-ply PV and begin the search from depth 10 instead of 1? If so, why?
I've noticed that Ruffian (apparently) always repeats the previously searched depths in a flash (obviously taken from hash, or memory). I don't remember it changing its mind before it reaches "maxdepth-2" depth.
All opinions welcome.

[Dan Honeycutt]

Hi Jaime:

Starting at depth 10 I would fear some circumstance where I don't complete an iteration and then have no idea what to play

With the data from the previous search in the hash table the engine should make short work of the first 10 iterations and accomplish pretty much what you are suggesting anyway.

Best
Dan H.

[Rémi Coulom]

If you do not erase the hash table between moves, then there is no need to do anything special. The first plies are in the hash tables, so search returns immediately (if the opponent played the PV move), and search-depth rapidly increases to the search depth of the previous move minus two. That is what I do in The Crazy Bishop.

R?mi

[Pallav Nawani]

Hi,

This could work, provided the opponent makes the predicted move. If the opponent's move is something else, you could get into a big problem as Dan stated.

Natwarlal used to do something very similar in past. At that time it had a single hash table with depth replace policy and the hash table was not cleared between moves.

As a result, if the opponent made the move which was expected by natwarlal, it went to ply 11 in a heartbeat, and then started searching, which was okay.

But when the opponent's move was not as predicted, the depth replace policy prevented the new best move from making it to the hash table, thus causing full re-searches every ply


Best regards,
Pallav

[Rémi Coulom]

But when the opponent's move was not as predicted, the depth replace policy prevented the new best move from making it to the hash table, thus causing full re-searches every ply :(

The trick here consists in using a few bits (even one single bit may be enough) in the hash entry to indicate if this hash entry comes from the current search, or from a previous search. If you need a slot, and none is free, you can overwrite entries of the previous search.

There is no need to update the whole table after every move. You simply keep a counter that indicates the "signature" of the current search, and increment it after every move.

R?mi

[José Carlos]

The trick here consists in using a few bits (even one single bit may be enough) in the hash entry to indicate if this hash entry comes from the current search, or from a previous search. If you need a slot, and none is free, you can overwrite entries of the previous search.

There is no need to update the whole table after every move. You simply keep a counter that indicates the "signature" of the current search, and increment it after every move.

R?mi

I use a similar idea. I don't know if it's any better, but I keep it because it's original. I store total material instead of a counter. When I have to decide whether replace or not, I first check if the material at the roor is less than the stored material. In tha case, I directly overwrite the slot. Otherwise, I use the other more standard replacement strategies. The idea is that if material at the root is >= than stored material, the stored position is still possible to reach by the search.
There're irreversible moves, of course, but I don't handle them because I haven't figured out a fast way to do it.

[Pallav Nawani]

The trick here consists in using a few bits (even one single bit may be enough) in the hash entry to indicate if this hash entry comes from the current search, or from a previous search. If you need a slot, and none is free, you can overwrite entries of the previous search.

There is no need to update the whole table after every move. You simply keep a counter that indicates the "signature" of the current search, and increment it after every move.

R?mi

Yes, that's the way I do it now. Now I have a dual Hash table, with a 4 bit counter which indicates whether this hash entry came from this search, or an older one.

Pallav

[Dan Honeycutt]

When I have to decide whether replace or not, I first check if the material at the roor is less than the stored material.

Hi Jos?:
Interesting idea. Do you worry about promotions?

Best
Dan H.

[Dan Honeycutt]

Now I have a dual Hash table, with a 4 bit counter which indicates whether this hash entry came from this search, or an older one.

Hi Pallav:
You only need one bit for "this search, or an older one." Do you age the entrys and then replace the oldest one of the two?

Best
Dan H.

[José Carlos]

When I have to decide whether replace or not, I first check if the material at the roor is less than the stored material.

Hi Jos?:
Interesting idea. Do you worry about promotions?

Best
Dan H.

No, I don't. Promotion problem is practically irrelevant, because it only means that when a promotion happens inside the tree, the associated hash record will look like "old" to the hash replacement algorithm. This means overwriting a few positions in a non-optimal way. The effect is not visible.

[Jaime Benito de Valle]

Thank you all for your input

Just one more question: If your "second" iterative search finds a "better move" than the one in the hash table, but the hash's one has a higher remaining depth than the present one, then you should ignore it and follow the hash's, right?

[Dan Honeycutt]

Thank you all for your input

Just one more question: If your "second" iterative search finds a "better move" than the one in the hash table, but the hash's one has a higher remaining depth than the present one, then you should ignore it and follow the hash's, right?

Hi Jaime:

Well, not exactly.

After the previous 12 ply search and if the game follows your PV you have in the hash table for the (now) root position move X with a score of Y and a depth of 10. For the first 10 iterations you are going to get back a score of Y for move X (which should be the first played since it's the hash table move). Other moves will return scores not better than Y (just like they did previously). On iteration 11 you do not have enough depth in the hash table so you have to search move X. Now the score can change. You likewise search the other moves, one of which may prove better than move X.

Hope that helps.
Dan H.

[Dan Honeycutt]

I should correct myself: move X will be the hash table move for the root position, score Y will be the score in the hash table for the position after move X is played.

Dan H.

[Pallav Nawani]

Now I have a dual Hash table, with a 4 bit counter which indicates whether this hash entry came from this search, or an older one.

Hi Pallav:
You only need one bit for "this search, or an older one." Do you age the entrys and then replace the oldest one of the two?

Best
Dan H.

Although only one bit is needed for this, I had 4 bits to spare, so I used them all The dual hash table I use is the standard one. One entry is 'always replace', other is 'replace if higher depth or a new search'. So no ageing is being done, except that I discard the entry from an older search in favour of an entry from a new search.

In reality, the criteria for replacement I use is a little more complex than the above. I borrowed from Gerbil and Sjeng free (11.2) and mixed them. You can always look at Natwarlal's code if you're curious

Best,
Pallav

[Dan Honeycutt]

Hi Pallav:

I see. Bruce Moreland talks about a "replace if same depth, deeper, or the element pertains to an ancient search". I've never tried that (I use just 1 bit for old entry) and thought you might be doing it when you mentioned using 4 bits.

Best
Dan H.