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.
I just tested this a few days ago with a similar result: +18 ELO after 2400 games at 60s + 100ms and 64MB hash.
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
No, go ahead and promote it. It's the best first-move candidate you have!
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.
I just tested this a few days ago with a similar result: +18 ELO after 2400 games at 60s + 100ms and 64MB hash.
Thanks for the info, Peter. I think I will test at a longer time control like you used just to be sure before commiting anything.
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
No, go ahead and promote it. It's the best first-move candidate you have!
You're right. I tested this too and it is better to promote, by about 10 elo from 2000 games.
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).
I tested probing only as well. It wasslightly ahead of 'no probing' but well within error bars.
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.
I just tested this a few days ago with a similar result: +18 ELO after 2400 games at 60s + 100ms and 64MB hash.
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
No, go ahead and promote it. It's the best first-move candidate you have!
This is one problem with tt entries. Most of the time, the best move is not a capture. In the q-search, this is about all you search. You really don't want to wreck the "best move" logic in the regular search if you can help it.
I just re-tested this myself, and found it is worse today than it was. Back 15 years ago when I got rid of q-search hashing, it was a break-even. Today it is a serious slow-down in my q-search. Way beyond what it gains in search space reduction. I removed it once again.
Considering that without hash move you would search all captures first anyway, before you get to any of the non-captures that supposedly will provide the best move, it seems it cannot really hurt to start with the cut-capture of a previous QS. If it is still good enough, that would at least make you skip the captures that come before it in the static move ordering, and which proved no good in that QS.
You could also make it dependent on the score bound of the QS move. This would presumably be a lower bound (or you would have no hash move), and if the lower bound would be good enough to cause a cutoff with the current window, there is a very good chance it will still do so. Even if it might not be the best move. Even if the lower bound found in QS was not good enough to cause a cutoff now, I still don't see a reason why you would want to search the other captures (which will had a still lower upper bound in QS) first.
There could be a concern when you store a QS cut move in an entry that was searched before at larger depth, thus overwriting a non-capture. I am not sure if this would occur much, though. Why would you search a node at QS level if it was already searched before at larger depth?
bob wrote:
I just re-tested this myself, and found it is worse today than it was. Back 15 years ago when I got rid of q-search hashing, it was a break-even. Today it is a serious slow-down in my q-search. Way beyond what it gains in search space reduction. I removed it once again.
Well, I have retested at a longer time control 60 s + 100 ms / move with 32 MB hash, and after 2400 games q-search hashing is still nearly 30 elo ahead. I guess it shows again how something that is a big win for one engine doesn't necessarily work for another.
bob wrote:
I just re-tested this myself, and found it is worse today than it was. Back 15 years ago when I got rid of q-search hashing, it was a break-even. Today it is a serious slow-down in my q-search. Way beyond what it gains in search space reduction. I removed it once again.
Well, I have retested at a longer time control 60 s + 100 ms / move with 32 MB hash, and after 2400 games q-search hashing is still nearly 30 elo ahead. I guess it shows again how something that is a big win for one engine doesn't necessarily work for another.
Jerry
I see approximately the same over here.
With q-search hashing I see a speed drop of ~20%, this is because the memory traffic increases a lot. However the drop in q-nodes is on average 40%. According to bullet tests I still have a gain of 20 to 30 Elo over the q-search without hashing. I've been thinking about a separate table for the q-search, my normal table uses 4 entries per key, at worst I have to read 64 bytes from memory each time I probe the table, this is a real performance killer.
hgm wrote:Considering that without hash move you would search all captures first anyway, before you get to any of the non-captures that supposedly will provide the best move, it seems it cannot really hurt to start with the cut-capture of a previous QS. If it is still good enough, that would at least make you skip the captures that come before it in the static move ordering, and which proved no good in that QS.
You could also make it dependent on the score bound of the QS move. This would presumably be a lower bound (or you would have no hash move), and if the lower bound would be good enough to cause a cutoff with the current window, there is a very good chance it will still do so. Even if it might not be the best move. Even if the lower bound found in QS was not good enough to cause a cutoff now, I still don't see a reason why you would want to search the other captures (which will had a still lower upper bound in QS) first.
There could be a concern when you store a QS cut move in an entry that was searched before at larger depth, thus overwriting a non-capture. I am not sure if this would occur much, though. Why would you search a node at QS level if it was already searched before at larger depth?
wrong draft or bounds for starters. The issue is the "always store" option which really is mandatory in some form. And it gives rise to the opportunity to replace a non-capture (which is a better move) with a capture (which is all the q-search can search.)
Whether this is a big deal or not I don't know and have not tested at all.
bob wrote:
I just re-tested this myself, and found it is worse today than it was. Back 15 years ago when I got rid of q-search hashing, it was a break-even. Today it is a serious slow-down in my q-search. Way beyond what it gains in search space reduction. I removed it once again.
Well, I have retested at a longer time control 60 s + 100 ms / move with 32 MB hash, and after 2400 games q-search hashing is still nearly 30 elo ahead. I guess it shows again how something that is a big win for one engine doesn't necessarily work for another.
Jerry
I see approximately the same over here.
With q-search hashing I see a speed drop of ~20%, this is because the memory traffic increases a lot. However the drop in q-nodes is on average 40%. According to bullet tests I still have a gain of 20 to 30 Elo over the q-search without hashing. I've been thinking about a separate table for the q-search, my normal table uses 4 entries per key, at worst I have to read 64 bytes from memory each time I probe the table, this is a real performance killer.
You read 64 bytes from memory no matter what you try to do. A cache miss reads 64 bytes every last time, unless you have a Piv which has a 128 byte L2 blocksize.
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.
I just tested this a few days ago with a similar result: +18 ELO after 2400 games at 60s + 100ms and 64MB hash.
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
No, go ahead and promote it. It's the best first-move candidate you have!
This is one problem with tt entries. Most of the time, the best move is not a capture. In the q-search, this is about all you search. You really don't want to wreck the "best move" logic in the regular search if you can help it.
Wreck? It's clearly the best capture to try first!
I just re-tested this myself, and found it is worse today than it was. Back 15 years ago when I got rid of q-search hashing, it was a break-even. Today it is a serious slow-down in my q-search. Way beyond what it gains in search space reduction. I removed it once again.
Well, 3 others have posted in this thread that it's a noticeable win for them. How much ELO did it cost Crafty? Probably the result depends on how expensive an engine's qsearch is. Mine's slow.
It's clearly the best capture to try first!