Transposition table usage in quiescent search?

[jd1]

Hi,

I was wondering whether the transposition (or hash) table should be used in the quiescent search, to cutoff already searched positions as well as to store the result. I see that Stockfish does it.

I tried a simple implementation, just store all q-search results and returning the hash value if I get a useful hit (i.e exact value, or > beta and lower bound, etc.)

It scored +25 elo after 4000 games at 5 s + 100 ms a move with 32MB hash size.

However, although the LOS is good, I am reluctant to commit the patch as I am worried that it will not be good when the hash is full, e.g. at long time control. How should I test to ensure that this is not a problem? Do any of you have experience with this sort of thing?

And one other question, am I right to assume that the quiescent best move should not be promoted to the top of the full search move list, unlike a normal hash move?

Thanks,
Jerry

[jdart]

Most programs do use the hash table in the quiescence search.

There are some possible issues. One is that there are a lot of q-search nodes in a typical search, but the q-search nodes are not generally useful in the non-quiescence search: at least, they can't be used to generate a cutoff there. So there is a cost to storing them (given the hash table is finite size) and you get somewhat less benefit for a q-search entry.

Another issue is that it is advantageous to cache the static value in the q-search, since in non-checking nodes, you immediately need this value to determine if you are going to cut off due to a high eval or continue searching. And it is usually expensive to call the evaluation function. (Programs also frequently need this value at higher nodes in the tree). Not all programs store this in the hash table, although some do.

For these reasons Arasan does not use the hash table in the q-search but uses a separate evaluation cache ithat only stores the static score and best move. q-search nodes probe this cache and the regular nodes probe the traditional hash table.

Last time I tried a more conventional implementation with the hash table used in the quiescence search, it tested worse, but as it happens, I am about to try this again.

--Jon

[jd1]

Most programs do use the hash table in the quiescence search.

There are some possible issues. One is that there are a lot of q-search nodes in a typical search, but the q-search nodes are not generally useful in the non-quiescence search: at least, they can't be used to generate a cutoff there. So there is a cost to storing them (given the hash table is finite size) and you get somewhat less benefit for a q-search entry.

Another issue is that it is advantageous to cache the static value in the q-search, since in non-checking nodes, you immediately need this value to determine if you are going to cut off due to a high eval or continue searching. And it is usually expensive to call the evaluation function. (Programs also frequently need this value at higher nodes in the tree). Not all programs store this in the hash table, although some do.

For these reasons Arasan does not use the hash table in the q-search but uses a separate evaluation cache ithat only stores the static score and best move. q-search nodes probe this cache and the regular nodes probe the traditional hash table.

Last time I tried a more conventional implementation with the hash table used in the quiescence search, it tested worse, but as it happens, I am about to try this again.

--Jon

Thanks for the input, Jon.

Jerry

[bob]

Hi,

I was wondering whether the transposition (or hash) table should be used in the quiescent search, to cutoff already searched positions as well as to store the result. I see that Stockfish does it.

I tried a simple implementation, just store all q-search results and returning the hash value if I get a useful hit (i.e exact value, or > beta and lower bound, etc.)

It scored +25 elo after 4000 games at 5 s + 100 ms a move with 32MB hash size.

However, although the LOS is good, I am reluctant to commit the patch as I am worried that it will not be good when the hash is full, e.g. at long time control. How should I test to ensure that this is not a problem? Do any of you have experience with this sort of thing?

And one other question, am I right to assume that the quiescent best move should not be promoted to the top of the full search move list, unlike a normal hash move?

Thanks,
Jerry

I tested this exhaustively in Crafty. It was a "wash". Hash in q-search slows the search down a bit due to the significantly increased memory traffic, but the search tree shrinks. They seemed to perfectly offset each other, so either with or without made no difference. I chose to leave it out because it greatly reduces the pressure on the TT regarding replacement, and size. Larger TT sizes become problematic due to the TLB thrashing that can cause.

As far as actual Elo goes, I found absolutely no difference in the two. Of course, at very fast hardware speeds (30M nodes per second and beyond, a 1 minute search can require a really large hash table, which can become a small problem.

[jd1]

I tested this exhaustively in Crafty. It was a "wash". Hash in q-search slows the search down a bit due to the significantly increased memory traffic, but the search tree shrinks. They seemed to perfectly offset each other, so either with or without made no difference. I chose to leave it out because it greatly reduces the pressure on the TT regarding replacement, and size. Larger TT sizes become problematic due to the TLB thrashing that can cause.

As far as actual Elo goes, I found absolutely no difference in the two. Of course, at very fast hardware speeds (30M nodes per second and beyond, a 1 minute search can require a really large hash table, which can become a small problem.

Thanks a lot, Bob, for the information. I expect it may be different for each engine though; I guess it means more games ...

I notice that Protector and MinkoChess also use hash table in the quiescent search, so maybe it works for them.

Jerry

[hgm]

For my engines probing in QS always has proved a big win.

[Evert]

For my engines probing in QS always has proved a big win.

You mean probing, but not storing, right?

That's something I've thought about trying but never got around to. I should probably re-test using the TT in the QS anyway; it didn't help back when I still had it, but you need to re-test these things every now and then...

[lucasart]

For my engines probing in QS always has proved a big win.

Same here (probing *and* storing). I've tried to remove TT in the QS, or even put a depth limit, both of which are clear regressions (as far as DiscoCheck is concerned).

[hgm]

For my engines probing in QS always has proved a big win.

You mean probing, but not storing, right?

I never tried to measure that separately. The expensive part is the memory access, once the data is in cache access becomes nearly free. I take measures to make sure depth-0 entries do not conquer the entire table. If you do shallowest-of-4 replacement, depth-0 will never be more than 25% of the table, for instance. You will just replace depth-0 by a more recent depth-0, which is more likely to be relevant.

Besides, my QS produces many search results that are depth 1 or 2. If you don't want to store everything it would be more sensible to discriminate by tree size than by dpeth.

[Evert]

Test running now. Too soon to say anything, but so far it looks really close.
Test positions suggest that I get the same as Bob posted earlier: node-counts go down, but time-to-depth remains (exactly) the same...