SF has no null window search in quiesce

[Lykos]

I was recently looking into the source code of stockfish a bit. I hoped to get a few new ideas for improving my own engine. Even though I try to come up with my own implementations for everything, it was very interesting. It was funny how they did some design decisions surprisingly similar to me, some others surprisingly different. Overall, I was surprised how small and simple the code is. It almost looks like something I could write. (Of course I know that I can't. First of all, it is an art to make complicated code look simple, second, the real work is probably not writing the code but the tuning, doing thousands of tests, comparing, discussing, updating etc.)

One thing I struggled to understand is why quiescent search is so different from normal search. I mean, a few things make sense. It needs a stand pat, it should use different move generation, not update killer moves and some additional logic. But apart from a few such details, I don't understand why they are as different as they are. One particular difference struck me:

Normal search uses null window search, but quiescent search doesn't. I see three options:
- I just completely misunderstand the code.
- There is some good reason why null window search in quiescent search does not make any sense which I am missing.
- It just happens that some benchmarks showed that null window search in Stockfish turned out to be bad. But this might depend on some other implementation details and things might be completely different in my engine.
Does anybody have enough knowledge about Stockfish to tell me?

[jdart]

Most programs do not do null search in the quiescence search.

The purpose of a null move search is to try to achieve rapid cutoff with a reduced-depth search.

In the q-search, every node is searched with a very limited subset of available moves (captures, promotions and sometimes checks). And depth is not really meaningful (unless you do something like search captures in early depths): you will just search until you have no more captures or one side has done so well that you get cutoff. So a reduced-depth search like you'd do outside the q-search is not helpful or necessary in the q-search.

--Jon

[mcostalba]

Does anybody have enough knowledge about Stockfish to tell me?

Stand pat evaluation is the null search equivalent in that context.

Actually, null search is omitted even at depth 1 in normal search: it starts from depth 2 and above.

[Gerd Isenberg]

I was recently looking into the source code of stockfish a bit. I hoped to get a few new ideas for improving my own engine. Even though I try to come up with my own implementations for everything, it was very interesting. It was funny how they did some design decisions surprisingly similar to me, some others surprisingly different. Overall, I was surprised how small and simple the code is. It almost looks like something I could write. (Of course I know that I can't. First of all, it is an art to make complicated code look simple, second, the real work is probably not writing the code but the tuning, doing thousands of tests, comparing, discussing, updating etc.)

One thing I struggled to understand is why quiescent search is so different from normal search. I mean, a few things make sense. It needs a stand pat, it should use different move generation, not update killer moves and some additional logic. But apart from a few such details, I don't understand why they are as different as they are. One particular difference struck me:

Normal search uses null window search, but quiescent search doesn't. I see three options:
- I just completely misunderstand the code.
- There is some good reason why null window search in quiescent search does not make any sense which I am missing.
- It just happens that some benchmarks showed that null window search in Stockfish turned out to be bad. But this might depend on some other implementation details and things might be completely different in my engine.
Does anybody have enough knowledge about Stockfish to tell me?

No special feature of Stockfish. NegaScout does not gain anything for depth <= 2, so one may keep quiescence code simple and skip null window search.

[Lykos]

Ok, I think I didn't express myself clearly enough. I didn't mean null move search, but null WINDOW search. I.e. the technique that as soon as you are pretty sure that you already found the best move (e.g. after you found the hash move) you decrease beta to alpha + 1 for all remaining moves. This will make the search a bit more efficient because it will cause more cutoffs. If you guessed correctly and the assumed best move was actually the best one, you save some search time. If you are wrong and a later move fails high within [alpha, alpha+1], you have to redo the search for that move using the actual window [alpha, beta].

[hgm]

Gerd already answered that correctly. In QS (and d=1 or 2) you usually don't have a good guess for the best move, so many null-window searches would fail high and trigger a re-search. So doing the null-eindow searches just wastes time, and vanilla apha-beta performs better.

[Lykos]

Ok, thanks a lot. That makes sense. Because you usually don't have hash moves at depth 1 or in QS, null window search is much less useful. But then you could say, it is not stupid for a very clear theoretical reason (I mean, if you had very good heuristics for move ordering, it might still be possible to gain something) but it just turns out to be usually bad in practice without hash moves.

Sorry for not seeing Gerds answer. We posted about at the same time, so when I was writing my post, I didn't see his one yet.

[Gerd Isenberg]

See also the smallest uniform tree of depth 3 showing Negascout to advatage over alpha-beta in Reinefeld's 1983 paper "An Improvement to the Scout Tree-Search Algorithm".

[bob]

I was recently looking into the source code of stockfish a bit. I hoped to get a few new ideas for improving my own engine. Even though I try to come up with my own implementations for everything, it was very interesting. It was funny how they did some design decisions surprisingly similar to me, some others surprisingly different. Overall, I was surprised how small and simple the code is. It almost looks like something I could write. (Of course I know that I can't. First of all, it is an art to make complicated code look simple, second, the real work is probably not writing the code but the tuning, doing thousands of tests, comparing, discussing, updating etc.)

One thing I struggled to understand is why quiescent search is so different from normal search. I mean, a few things make sense. It needs a stand pat, it should use different move generation, not update killer moves and some additional logic. But apart from a few such details, I don't understand why they are as different as they are. One particular difference struck me:

Normal search uses null window search, but quiescent search doesn't. I see three options:
- I just completely misunderstand the code.
- There is some good reason why null window search in quiescent search does not make any sense which I am missing.
- It just happens that some benchmarks showed that null window search in Stockfish turned out to be bad. But this might depend on some other implementation details and things might be completely different in my engine.
Does anybody have enough knowledge about Stockfish to tell me?

It sort of does have a null-move search. The "stand-pat" option. If the stand-pat score is >= beta, you don't search anything, just like the null-move search that fails high and you don't search anything.

null-move is much safer of course, since it does do a search, where a stand-pat evaluation is pure static evaluation with no tree search of any kind until you start trying captures, which you are not forced to do.

[bob]

Ok, thanks a lot. That makes sense. Because you usually don't have hash moves at depth 1 or in QS, null window search is much less useful. But then you could say, it is not stupid for a very clear theoretical reason (I mean, if you had very good heuristics for move ordering, it might still be possible to gain something) but it just turns out to be usually bad in practice without hash moves.

Sorry for not seeing Gerds answer. We posted about at the same time, so when I was writing my post, I didn't see his one yet.

Think about it like this. In the normal search you are using a scalpel, where you might slice off a tiny section of the tree with that null-window search. But in the q-search, you are using a hammer (a capture). A capture is much less likely to fail high on the null-window search but not on the research, as opposed to a normal move. It is easy to test, and all you do is introduce a lot of small tree searches to confirm the fail-high. Not a huge gain or loss, but it is measurable.