Verification search

[lucasart]

Just tried it, and it's proven completely useless. Result after 500 games in 6"+0.1" (average NPS on my hardware around 1M)

Code: Select all

Score of test vs DiscoCheck 3.5.1: 152 - 149 - 199  [0.50] 500

I wonder if it's normal, and if others have come to the same conclusion, or if I'm doing something wrong.

Basically I'm doing a verification search at high depths (depth >= 7) when the null move fails high.

[bob]

Just tried it, and it's proven completely useless. Result after 500 games in 6"+0.1" (average NPS on my hardware around 1M)

Code: Select all

Score of test vs DiscoCheck 3.5.1: 152 - 149 - 199  [0.50] 500

I wonder if it's normal, and if others have come to the same conclusion, or if I'm doing something wrong.

Basically I'm doing a verification search at high depths (depth >= 7) when the null move fails high.

I personally tested this several times, with 30K game matches, and I found absolutely no case where it helped, and lots of cases where it hurts (you can limit the overhead by limiting the depth where you do it of course)...

[PK]

it helps Rodent in the endgame, but repeteadly fails in the middlegame.

[lucasart]

Just tried it, and it's proven completely useless. Result after 500 games in 6"+0.1" (average NPS on my hardware around 1M)

Code: Select all

Score of test vs DiscoCheck 3.5.1: 152 - 149 - 199  [0.50] 500

I wonder if it's normal, and if others have come to the same conclusion, or if I'm doing something wrong.

Basically I'm doing a verification search at high depths (depth >= 7) when the null move fails high.

I personally tested this several times, with 30K game matches, and I found absolutely no case where it helped, and lots of cases where it hurts (you can limit the overhead by limiting the depth where you do it of course)...

I think this whole zogzwang problem is vastly exagerated. People seem to attach far too much attentionattention to this post null move hype:After testing I discovered the following:
* verification search is completely useless. elowise of course, meaning that there are perhaps some positions in which it helps, but overall it doesn't help.
* the piece precondition: only do a null move when you have at least a piece on the board. Well even that is almost useless. Adding that condition was unmeasurably better (better but below error bar). I kept it anyway, but perhaps it could be further improved, like at least one piece, or not in a king opposition (ie. king dist != 2). Even in K+P endgames, the zugzwang is more an exception than a general problem. And not doing null move misses a lot of good moves that would be found deeper in search, which is to be put in front of the zugzwang improvement.
* when null move fails low, do a mate threat extension (ie. search for a mate at null-reduced depth from opp perspective): saw that in the wiki, and found it to be not just useless but actually harmful. There is however the connected move trick by Tord Romstad, which is quite a smart idea. I haven't experimented with it, and wonder how much elo it adds to SF.

[Karlo Bala]

Just tried it, and it's proven completely useless. Result after 500 games in 6"+0.1" (average NPS on my hardware around 1M)

Code: Select all

Score of test vs DiscoCheck 3.5.1: 152 - 149 - 199  [0.50] 500

I wonder if it's normal, and if others have come to the same conclusion, or if I'm doing something wrong.

Basically I'm doing a verification search at high depths (depth >= 7) when the null move fails high.

Verification search need big depths to be effective. I doubt that your engine reach more than 6-7 depth in the middle of the tree (13-15 depths from the root) at such fast time control.

[lucasart]

Just tried it, and it's proven completely useless. Result after 500 games in 6"+0.1" (average NPS on my hardware around 1M)

Code: Select all

Score of test vs DiscoCheck 3.5.1: 152 - 149 - 199  [0.50] 500

I wonder if it's normal, and if others have come to the same conclusion, or if I'm doing something wrong.

Basically I'm doing a verification search at high depths (depth >= 7) when the null move fails high.

Verification search need big depths to be effective. I doubt that your engine reach more than 6-7 depth in the middle of the tree (13-15 depths from the root) at such fast time control.

at this time control in the middlegame, it typically reaches an average depth of 11

[PK]

Perhaps verification search is more needed for analysis strength than for playing strength. For example one of my favourite analysis engines, Spike 1.2, fails miserably in relatively simple positions, and I must double-check whenever I suspect a null move issue.

[Eelco de Groot]

Just tried it, and it's proven completely useless. Result after 500 games in 6"+0.1" (average NPS on my hardware around 1M)

Code: Select all

Score of test vs DiscoCheck 3.5.1: 152 - 149 - 199  [0.50] 500

I wonder if it's normal, and if others have come to the same conclusion, or if I'm doing something wrong.

Basically I'm doing a verification search at high depths (depth >= 7) when the null move fails high.

I personally tested this several times, with 30K game matches, and I found absolutely no case where it helped, and lots of cases where it hurts (you can limit the overhead by limiting the depth where you do it of course)...

I think this whole zogzwang problem is vastly exagerated. People seem to attach far too much attentionattention to this post null move hype

Please have a little sympathy for the chessplayers Adding 3-4-5 elo by not doing a verification search is "completely useless" for chessplayers but doing even a little bit for correct handling of Zugzwang is useful and I think it improves the playing style and maybe more importantly every exception, every dificult position that is rare but nevertheless can decide a game, becomes more important when the timecontrols go up, hardware improves, when opposition becomes tougher etc.

:After testing I discovered the following:
* verification search is completely useless. elowise of course, meaning that there are perhaps some positions in which it helps, but overall it doesn't help.

That you tested this instead of just simply adopting the strategy of maximizing nullmove is certainly commendable. I am far too lazy to even think about testing something like this.

* the piece precondition: only do a null move when you have at least a piece on the board. Well even that is almost useless. Adding that condition was unmeasurably better (better but below error bar). I kept it anyway, but perhaps it could be further improved, like at least one piece, or not in a king opposition (ie. king dist != 2). Even in K+P endgames, the zugzwang is more an exception than a general problem. And not doing null move misses a lot of good moves that would be found deeper in search, which is to be put in front of the zugzwang improvement.
* when null move fails low, do a mate threat extension (ie. search for a mate at null-reduced depth from opp perspective): saw that in the wiki, and found it to be not just useless but actually harmful. There is however the connected move trick by Tord Romstad, which is quite a smart idea. I haven't experimented with it, and wonder how much elo it adds to SF.

I think it has become a little less effective on big hardware where you can reach searchdepths that make the tactical benefits of this less important. On small hardware like the iPad it is more important still I think. In Rainbow Serpent I usually do not undo the reduction (return Fail Low score to the parent node which will trigger a full search) if the nullmove fails low (like Glaurung and Stockfish do this, at small remaining depth)), this is after all a re-search as Tord described in the notes, and you could achieve much the same thing by doing some sort of extension when still in the (Step 15 LMR-)reduced search, after nullmove fails. The 'connected moves' idea is really beautiful though and for Tord even a reason of doing a nullmove search when you know already that a verification search would fail low against beta (for instance if your hashhit could already tell you that). There are more threads about verification search in this subforum, but I have not done the research of looking up Tord's post about this.

In Rainbow Serpent I tried expanding the idea a bit by using "connected moves" and other relations with the threats "detected" by nullmove in the Late Move Pruning/Futility Pruning phase of Stockfish. But don't ask me too much about if it helps elowise.
So for instance in Stockfish there is

Code: Select all

        else
        {
            // The null move failed low, which means that we may be faced with
            // some kind of threat. If the previous move was reduced, check if
            // the move that refuted the null move was somehow connected to the
            // move which was reduced. If a connection is found, return a fail
            // low score (which will cause the reduced move to fail high in the
            // parent node, which will trigger a re-search with full depth).
            threatMove = (ss+1)->currentMove;

            if (   depth < ThreatDepth
                && (ss-1)->reduction
                && threatMove != MOVE_NONE
                && connected_moves(pos, (ss-1)->currentMove, threatMove))
                return beta - 1;
        }
    }

And with minor change in RS I usually stay in the reduced search by setting threatreplyExtension = true but not returning, and in case the hashmove fails (more precisely: when no early move goes above alpha), no futility pruning of the remaining moves. If the hashmove (if there is one, usually not but you expect a beta-cutoff in this node or you would not try nullmove) works this does not bring much extra costs but improves the quality of the search if the CUT-node becomes an ALL-node.

Code: Select all

        else
        {
            // The null move failed low, which means that we may be faced with
            // some kind of threat. If the previous move was reduced, check if
            // the move that refuted the null move was somehow connected to the
            // move which was reduced. If a connection is found, return a fail
            // low score (which will cause the reduced move to fail high in the
            // parent node, which will trigger a re-search with full depth).
            threatMove = ss->threatMove = (ss+1)->currentMove;

            if (nullValue <= VALUE_MATED_IN_MAX_PLY)
				mate_threatExtension = true;
            else if ( depth < ThreatDepth
                  && (ss-1)->reduction
                  &&  threatMove != MOVE_NONE)
			{
				if (   nullValue < beta  - 0x50
				    && connected_moves(pos, (ss-1)->currentMove, threatMove))
                return beta - 1;
				threatreplyExtension = true; //[No real extension but switches off futility pruning]
			}
        }
    }

I have not done any tuning of the beta - 0x50 value, but this is in Rainbow Serpent since quite a while. Maybe it should be tuned. Futility pruning is not switched off above the threatdepth limit (same limit as in SF) but the connected moves condition is still used later on in that codeblock. The mate_threat extension mainly also switches off futility pruning in Rainbow Serpent but any added extension will I think mainly help when there are threats that lie behind the search horizon. You may be right that it hurts elowise and you can take it too far. I do extend one ply in this case at the moment.

Code: Select all

// Don't terminate search early if the opponent threatens mate
if (ext < ONE_PLY && mate_threatExtension && ss->ply < iteration)
    ext = ONE_PLY;

I could describe what connected_moves is doing in Futility pruning but well, that would maybe be outside the scope of a topic about the verification search.

Regards, Eelco

[Karlo Bala]

Just tried it, and it's proven completely useless. Result after 500 games in 6"+0.1" (average NPS on my hardware around 1M)

Code: Select all

Score of test vs DiscoCheck 3.5.1: 152 - 149 - 199  [0.50] 500

I wonder if it's normal, and if others have come to the same conclusion, or if I'm doing something wrong.

Basically I'm doing a verification search at high depths (depth >= 7) when the null move fails high.

Verification search need big depths to be effective. I doubt that your engine reach more than 6-7 depth in the middle of the tree (13-15 depths from the root) at such fast time control.

at this time control in the middlegame, it typically reaches an average depth of 11

So, with 11 depth you have a weak zugzwang detection at ply 2 (only 3 ply deep), and in the middle of the tree (at ply 5,6) you have none. I think that for decent zuzgzwang detection your engine need at least depth 20.

[dchoman]

I think this whole zogzwang problem is vastly exagerated. People seem to attach far too much attentionattention to this post null move hype:After testing I discovered the following:
* verification search is completely useless. elowise of course, meaning that there are perhaps some positions in which it helps, but overall it doesn't help.
* the piece precondition: only do a null move when you have at least a piece on the board. Well even that is almost useless. Adding that condition was unmeasurably better (better but below error bar). I kept it anyway, but perhaps it could be further improved, like at least one piece, or not in a king opposition (ie. king dist != 2). Even in K+P endgames, the zugzwang is more an exception than a general problem. And not doing null move misses a lot of good moves that would be found deeper in search, which is to be put in front of the zugzwang improvement.
* when null move fails low, do a mate threat extension (ie. search for a mate at null-reduced depth from opp perspective): saw that in the wiki, and found it to be not just useless but actually harmful. There is however the connected move trick by Tord Romstad, which is quite a smart idea. I haven't experimented with it, and wonder how much elo it adds to SF.

Last time I tested this verification helped only when I restricted it to cases with a small number of pieces for the side to move on the board. It wasn't a big effect and I can't remember if it was significant.

Regarding mate threat extensions, those are also borderline but I have always concluded that they do help (don't remember the last time I tested). I only apply them in the last few plys, where horizon issues might crop up.... as an aside, I've also found that regular check extensions only really help in the last few plys as well (depth < 3, I think for EXchess).

- Dan