What is verification search & what is it for ?

[MahmoudUthman]

The bit at CPW doesn't help , also is there any engine that uses null move reduction instead of/alongside null move pruning ?

[kbhearn]

Verification search is doing a reduced search (same depth as the nullmove search) but without a null move after null move fails high to confirm that it's not a zugzwang position. It helps with problems, but afaik has little benefit to playing strength as zugzwang is relatively rare.

Null move reduction is part of null move pruning. You search the position after a null move to a reduced depth that is the null move reduction.

[Dann Corbit]

Here is how it is used in Stockfish (verification_depth is 12):

Code: Select all

        if (nullValue >= beta)
        {
            // Do not return unproven mate scores
            if (nullValue >= VALUE_MATE_IN_MAX_PLY)
                nullValue = beta;

            if &#40;depth < verification_depth * ONE_PLY && abs&#40;beta&#41; < VALUE_KNOWN_WIN&#41;
                return nullValue;

            // Do verification search at high depths
            Value v = depth-R < ONE_PLY ? qsearch<NonPV, false>&#40;pos, ss, beta-1, beta&#41;
                      &#58;  search<NonPV>&#40;pos, ss, beta-1, beta, depth-R, false, true&#41;;

            if &#40;v >= beta&#41;
                return nullValue;
        &#125;

Here is the article that defines the concept:
Omid David, Nathan S. Netanyahu (2002). Verified Null-Move Pruning. ICGA Journal, Vol. 25, No. 3

Copy found here:
https://www.researchgate.net/publicatio ... ve_Pruning
and here:
https://arxiv.org/abs/0808.1125

[hgm]

Null move reduction is part of null move pruning. You search the position after a null move to a reduced depth that is the null move reduction.

I don't think that answers the question, though, which I interpreted to be "can you also search the other (=real) moves reduced, after a null-move fail high, rather than prune them completely". The answer to that question would be "Yes, and that is called verification search".

Note that in principle the depth of a verification search does not need to be the same as that of the null-move search. Many zugzwags lead to a rapid collapse of your defense, which a search of quite low depth would already see.

[mar]

I use hybrid NMP + NMR in my engine (since the last version), no verification search;
I prune at low depths and reduce at higher depths