Hashing in Qsearch?

[fierz]

Dear all,

I recently started generating checks in qsearch, and that seems to work fine. However, I have started to confuse myself badly with hashing in the qsearch. My program uses two separate hashtables, one for the qsearch, one for the main search.

In the qsearch, I have the issue that sometimes a score is associated with no moves at all (when the eval is >= beta), sometimes it is associated with a search of only capture moves, and sometimes with captures and checks. Also, sometimes the side to move is in check, and cannot stand pat, and everything stored should be consistent everywhere. I thought I had it figured out but I get strange behavior that makes little sense sometimes.

So I looked at some good open source programs, and in Crafty, it seems to me no hashing is done at all in the qsearch. In Stockfish, there is a cryptic remark after the lookup " // Never assume anything on values stored in TT", which I don't understand.

Can anyone tell me what the state of the art regarding hashing in QS is? Is everyone doing it, or is it not that important?

cheers
Martin

[hgm]

The state of the art is that you see whether doing it helps, and if it does, you keep it.

For Joker hashing in QS helped make it play stronger. But Joker is single-threaded, and this could make a difference. Crafty indeed doesn't hash QS nodes.

Normally you would assign a different depth to QS levels where you still do checks, and those where you don't. So that the former would satisfy probes for the latter, but not vice versa. Standing pat is irrelevant; the bound type and score will automatically take care of that.

[Rein Halbersma]

In Stockfish, there is a cryptic remark after the lookup " // Never assume anything on values stored in TT", which I don't understand.

Looking at line 1385 of
https://github.com/official-stockfish/S ... search.cpp

Code: Select all

    tte->save(posKey, value_to_tt(bestValue, ss->ply),
              PvNode && bestValue > oldAlpha ? BOUND_EXACT : BOUND_UPPER,
              ttDepth, bestMove, ss->staticEval, TT.generation());

it appears that Stockfish does hash during qsearch.

[fierz]

In Stockfish, there is a cryptic remark after the lookup " // Never assume anything on values stored in TT", which I don't understand.

Looking at line 1385 of
https://github.com/official-stockfish/S ... search.cpp

Code: Select all

    tte->save(posKey, value_to_tt(bestValue, ss->ply),
              PvNode && bestValue > oldAlpha ? BOUND_EXACT : BOUND_UPPER,
              ttDepth, bestMove, ss->staticEval, TT.generation());

it appears that Stockfish does hash during qsearch.

I could see that too - the question is more: why would one strong program choose to do hashing in QS and another not?

[syzygy]

I could see that too - the question is more: why would one strong program choose to do hashing in QS and another not?

See what HGM wrote: the developers tested it, kept it if it worked and threw it out if not.

[bob]

In Stockfish, there is a cryptic remark after the lookup " // Never assume anything on values stored in TT", which I don't understand.

Looking at line 1385 of
https://github.com/official-stockfish/S ... search.cpp

Code: Select all

    tte->save(posKey, value_to_tt(bestValue, ss->ply),
              PvNode && bestValue > oldAlpha ? BOUND_EXACT : BOUND_UPPER,
              ttDepth, bestMove, ss->staticEval, TT.generation());

it appears that Stockfish does hash during qsearch.

I could see that too - the question is more: why would one strong program choose to do hashing in QS and another not?

Here's my answer:

When I added probing to q-search I found two effects. (1) the program slowed down by approximately 10% (in terms of NPS). (2) the trees searched were about 10% smaller. Net result was "a wash" for me. (note this was with single-threaded test only, many years ago, but repeated within the past two years).

I elected to not hash in q-search since there was no benefit or cost involved, and it does help on very long searches where the q-search can really overload the hash table since you have to use some sort of "always-store/replace" strategy. So I can get by with a smaller hash table without seeing a performance degradation.

You should always check this for yourself, but as to whether you are in check or not and such, why would it matter? If you reach position P and store the search result, the next time you reach position P I don't see why you couldn't trust that hash result implicitly. P == P, so the search should produce the same result each time, assuming the bounds don't change.

[D Sceviour]

One can see in the notes to Crafty 23.4:

Minor bug caused HashStore() to lose a best move when overwriting an old position with a null-move search result... New hash idea stores the PV for an EXACT hash entry in a separate hashtable. When an EXACT hit happens, this PV can be added to the incomplete PV we have so far so that we have the exact path that leads to the backed up score.

The "minor bug" problem is augmented even worse if hashing QS. Null Move Search frequently transposes to a PV line, and thus can wipe out a complete search.

I am experimenting successfully with an approach called "Bound Independent Cutoff" after doing a hash probe in QS. If the hash probe depth is greater than the current QS depth, then return the hash score (period). A quiescent search with captures only should not be able to produce a better score than a full search which explores interpolations and quiet positional gain moves. The alpha/beta bounds are ignored for PV nodes. This helps considerably to avoid the Crafty "minor bug" and eases the requirement for a PV hash table. So far, I have not found another program that uses a depth first or bound independent cutoff in QS.

[bob]

One can see in the notes to Crafty 23.4:

Minor bug caused HashStore() to lose a best move when overwriting an old position with a null-move search result... New hash idea stores the PV for an EXACT hash entry in a separate hashtable. When an EXACT hit happens, this PV can be added to the incomplete PV we have so far so that we have the exact path that leads to the backed up score.

The "minor bug" problem is augmented even worse if hashing QS. Null Move Search frequently transposes to a PV line, and thus can wipe out a complete search.

I am experimenting successfully with an approach called "Bound Independent Cutoff" after doing a hash probe in QS. If the hash probe depth is greater than the current QS depth, then return the hash score (period). A quiescent search with captures only should not be able to produce a better score than a full search which explores interpolations and quiet positional gain moves. The alpha/beta bounds are ignored for PV nodes. This helps considerably to avoid the Crafty "minor bug" and eases the requirement for a PV hash table. So far, I have not found another program that uses a depth first or bound independent cutoff in QS.

I think you are misunderstanding that bug. A null-move search could store an entry that had the same signature as a real position, and that would cause the best move to be lost (since the null-move has no best move "a null-move was best" and that replaced the old position. The fix was simply to store the old best move with the null-move search result... This was only important when another path hits this position with a different bound so that the null-move search result is no good, and now we have no hash move to try first either... That was fixed.

[Mincho Georgiev]

I've never ever had success with it. Not in terms of strength anyways. In fact, the closer I get with my experiments to main search (in qsearch), the worse the effect. Just my own experience. That includes the dynamic forward pruning techniques etc.

[brtzsnr]

Instead of storing the minimax score for the sub-tree, you could just store the static evaluation. Since QS is very close to the leafs storing the tree evaluation doesn't save you that many nodes. I just tested the idea with a hash of 4096 elements. This gives a hit-rate of 15% which translates to a speed improvement of 3%.