Transposition table usage in quiescent search?

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
jd1
Posts: 266
Joined: Wed Oct 24, 2012 12:07 am

Transposition table usage in quiescent search?

Post by jd1 » Fri Mar 01, 2013 2:02 am

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
Posts: 3824
Joined: Fri Mar 10, 2006 4:23 am
Location: http://www.arasanchess.org

Re: Transposition table usage in quiescent search?

Post by jdart » Fri Mar 01, 2013 3:36 am

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
Posts: 266
Joined: Wed Oct 24, 2012 12:07 am

Re: Transposition table usage in quiescent search?

Post by jd1 » Fri Mar 01, 2013 3:55 am

jdart wrote: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
Posts: 20549
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Transposition table usage in quiescent search?

Post by bob » Fri Mar 01, 2013 3:57 am

jd1 wrote: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
Posts: 266
Joined: Wed Oct 24, 2012 12:07 am

Re: Transposition table usage in quiescent search?

Post by jd1 » Sat Mar 02, 2013 6:05 am

bob wrote: 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

User avatar
hgm
Posts: 23714
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Transposition table usage in quiescent search?

Post by hgm » Sat Mar 02, 2013 11:42 am

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

User avatar
Evert
Posts: 2923
Joined: Fri Jan 21, 2011 11:42 pm
Location: NL
Contact:

Re: Transposition table usage in quiescent search?

Post by Evert » Sat Mar 02, 2013 12:31 pm

hgm wrote: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...

User avatar
lucasart
Posts: 3040
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: Transposition table usage in quiescent search?

Post by lucasart » Sat Mar 02, 2013 12:36 pm

hgm wrote: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).
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.

User avatar
hgm
Posts: 23714
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Transposition table usage in quiescent search?

Post by hgm » Sat Mar 02, 2013 1:46 pm

Evert wrote:
hgm wrote: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.

User avatar
Evert
Posts: 2923
Joined: Fri Jan 21, 2011 11:42 pm
Location: NL
Contact:

Re: Transposition table usage in quiescent search?

Post by Evert » Sat Mar 02, 2013 9:52 pm

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...

Post Reply