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.
Just adding the hash probe to mine slowed the bps by almost 50%. 2x slower. That is around -50 Elo for me. My q-search has been optimized and re-optimized over the years. It is a time-critical path, obviously.
The point I was making is that if you have a position P that you store in the normal search with a non-capture best move, what do you do when you store a q-search tt entry for the SAME position? You just about can't refuse to store, that's pretty well-known. So do you overwrite and lose the non-capture best move and replace it with a capture? That can break ordering earlier in the tree where it is more important...
If you don't store in the q-search, I suppose there is no problem, although I would then wonder what the advantage of a probe might be...
bob wrote:
The point I was making is that if you have a position P that you store in the normal search with a non-capture best move, what do you do when you store a q-search tt entry for the SAME position? You just about can't refuse to store, that's pretty well-known. So do you overwrite and lose the non-capture best move and replace it with a capture? That can break ordering earlier in the tree where it is more important...
If you don't store in the q-search, I suppose there is no problem, although I would then wonder what the advantage of a probe might be...
Wouldn't the draft be deeper for the normal search entry? In that case the primary slot would still contain the normal search entry and the "always-replace" slot would eventually be overwritten. I think you might be able to stand a bit of this without it being too detrimental. I remember it was a win when I started hashing in the qsearch, but to be honest I haven't re-measured it in a while. It might be time to run a test or two.
pkappler wrote:The point I was making is that if you have a position P that you store in the normal search with a non-capture best move, what do you do when you store a q-search tt entry for the SAME position? You just about can't refuse to store, that's pretty well-known. So do you overwrite and lose the non-capture best move and replace it with a capture? That can break ordering earlier in the tree where it is more important...
If you don't store in the q-search, I suppose there is no problem, although I would then wonder what the
advantage of a probe might be.
I don't quite understand.
A 'replace-always' scheme does not always replace unless we really want to implement it that way without checking if the position has already been hashed in an earlier search of a greater draft.
My implementation does not replace a same position where the entry has a greater or equal draft - it is the same position!
When you already have a position with greater or equal draft you would use its score, and not search. So you would not have anything to store. So this situation could only occur if somehow the bound from the deeper entry was good. In such cases it is usually very detrimental to keep the deeper entry: it is as good as useless. It is very questionable if the cut-move it lists would still be a cut-move with the current beta.
Sometimes this situation occurs when you need a bound of the opposite type with the same alpha. TT-designs that store both upper and lower bound (possibly of different draft) do solve that conflict for the score. And in that case there can never be a conflict for the move, as the upper-bound was a fail low, for which you would not want to store a move.
But Bob raises an interesting a point: when a d>0 search provides a non-capture with lower-bound L, it implies that it searched all captures at d>0, and found their score to be <L. Does it even have a point to search in QS on such a hit. You know you will only search captures at d=0, and apparently you need a score >L to achieve a fail high, or you would have used the hashed score immediately. But if any of the captures is going to give you that, it will be a highly unreliable result, that would likely disappear on deeper search. Seemingly good captures will likely be poisoned. There must have been some reason why the node at some depth switched from using a capture cut-move to a non-capture. Hash moves do not materialize out of nothing.
So it might be better to not search at all, and just take an immediate fail low. Then you also would never have the dilemma whether to replace.
pkappler wrote:
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.
I can't really tell whether my q-search is slow or not because I never compared it with other ones. I use SEE throughout for move ordering, no MVV-LVA, my SEE is highly optimized and it performs a little bit better than MVV-LVA. Maybe the q-search of Bob's program is very fast. When I see Crafty doing 30 million n/s on a 6 core (at least that's what's being told) it makes me wonder how that is possible. This can mean two things, either Crafty counts nodes differently or it does very little work at each node.
My tests so far with this show that using a traditional hash table in the q-search (vs. Arasan's evaluation cache) is a loser, about -10 elo. The difference is outside the error bars.
My implementation stores the static value in the hash table so that the q-search still gets the benefit of having this.
I tried two versions. One accepted any move from the transposition table as a pv move. The other is more sophisticated and does not use moves from q-search nodes in the main search and also does not use moves from the table in the q-search that do not meet the normal q-search move selection criteria. The test for the 2nd version is still running but so far it does not appear to be any better.
I believe Crafty is fast partly because it does fewer evals that other programs, because futility pruning is based on material only, not the full eval score, and it does not do other things such as razoring that would require evals at non-quiescent nodes. Also it has been optimized to scale well on multi-core processors.
bob wrote:
The point I was making is that if you have a position P that you store in the normal search with a non-capture best move, what do you do when you store a q-search tt entry for the SAME position? You just about can't refuse to store, that's pretty well-known. So do you overwrite and lose the non-capture best move and replace it with a capture? That can break ordering earlier in the tree where it is more important...
If you don't store in the q-search, I suppose there is no problem, although I would then wonder what the advantage of a probe might be...
Wouldn't the draft be deeper for the normal search entry? In that case the primary slot would still contain the normal search entry and the "always-replace" slot would eventually be overwritten. I think you might be able to stand a bit of this without it being too detrimental. I remember it was a win when I started hashing in the qsearch, but to be honest I haven't re-measured it in a while. It might be time to run a test or two.
I don't allow duplicates. Doesn't make much sense to fill up a 4-slot bucket with different entries for the same signature, IMHO. When I do a store, if I get a signature match, I overwrite that position, period. NO reason to not do so, something about it failed to terminate the search when you got the hit, so replacing it with something useful makes sense to me.
pkappler wrote:The point I was making is that if you have a position P that you store in the normal search with a non-capture best move, what do you do when you store a q-search tt entry for the SAME position? You just about can't refuse to store, that's pretty well-known. So do you overwrite and lose the non-capture best move and replace it with a capture? That can break ordering earlier in the tree where it is more important...
If you don't store in the q-search, I suppose there is no problem, although I would then wonder what the
advantage of a probe might be.
I don't quite understand.
A 'replace-always' scheme does not always replace unless we really want to implement it that way without checking if the position has already been hashed in an earlier search of a greater draft.
My implementation does not replace a same position where the entry has a greater or equal draft - it is the same position!
Rasjid.
Same position, different information. When you did the probe, and got the hit, the info did not terminate the search. So why not store info that WILL terminate the search the next time around?
pkappler wrote:
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.
I can't really tell whether my q-search is slow or not because I never compared it with other ones. I use SEE throughout for move ordering, no MVV-LVA, my SEE is highly optimized and it performs a little bit better than MVV-LVA. Maybe the q-search of Bob's program is very fast. When I see Crafty doing 30 million n/s on a 6 core (at least that's what's being told) it makes me wonder how that is possible. This can mean two things, either Crafty counts nodes differently or it does very little work at each node.
Crafty counts nodes like everyone else. Each "MakeMove()" produces a new position (node). The q-search is pretty fast. It's been around since 1994 and has been modified many times to improve speed.
Anyone can test the NPS of course, the source is available. In the last CCT it was hitting about 30M on a 6-core 3.2ghz i7
It's clearly the best capture to try first!
