verified null move

[bob]

In a private email discussion, someone asked if I had tested verified null-move on my cluster. I had not, because the idea made no sense to me and seemed to be nothing more than wasted search effort. But, I thought I would give it a whirl to see what happens.

The idea is that when a null-move search fails high, you do a normal search before you allow the NM fail high to terminate the search. This normal search is to a much-reduced depth. If the normal search fails low on the beta-1, beta bounds, then the null-move search fail high is ignored.

This can be limited in two ways.

1. How much do you reduce the depth on the verification search. I tried 3-4-5-6 plies. The bigger the number, the better the result, as this tends to reduce the extra effort expended.

2. Where do you do the verification searches. I limited it based on remaining depth so that it would not be done too near the tips to control effort expended. I tried this with remaining depth at least 3, then 4, ... and as before the bigger the value, the better the result.

Unfortunately, bigger values reduce the impact of the verification search, and when the depth limit (in 2 above) is large enough, a verification search is never done. The upper bound on this mess was the rating of the original program without the verification search. In other words, I could not get this idea to produce anything other than an Elo _loss_. Verified in my usual cluster-testing approach.

[kranium]

that's interesting...

Fruit 2.1 does this ... a (null-move) verification search (only in the endgame):

if (UseVer && value >= beta && do_ver(board))
{

new_depth = depth - NullReduction;

if (new_depth > 0)
{ // HACK
value = full_simple(board, alpha, beta, new_depth, height, new_pv, NodeCut, trans_move, &move);

if (value >= beta)
{
best_move = move;
best_value = value;
pv_copy(pv, new_pv);
goto cut;
}
}
}

the do_ver() function -> checks that there's no queens, no rooks, and only 1 minor piece or less on the board...)

-----
Toga created Verification search and Verification Reduction as UCI options
"Always", "Endgame only"; "Never"
("Always" as default...!?)

and the configurable verification reduction (from 1-6, default 5 !?) replaces Null Reduction in the above Fruit 2.1 code

i would have assumed it was only really beneficial in the endgame?
but in Toga it seems to be effective...

[bob]

that's interesting...

Fruit 2.1 does this ... a (null-move) verification search (only in the endgame):

if (UseVer && value >= beta && do_ver(board))
{

new_depth = depth - NullReduction;

if (new_depth > 0)
{ // HACK
value = full_simple(board, alpha, beta, new_depth, height, new_pv, NodeCut, trans_move, &move);

if (value >= beta)
{
best_move = move;
best_value = value;
pv_copy(pv, new_pv);
goto cut;
}
}
}

the do_ver() function -> checks that there's no queens, no rooks, and only 1 minor piece or less on the board...)

-----
Toga created Verification search and Verification Reduction as UCI options
"Always", "Endgame only"; "Never"
("Always" as default...!?)

and the configurable verification reduction (from 1-6, default 5 !?) replaces Null Reduction in the above Fruit 2.1 code

i would have assumed it was only really beneficial in the endgame?
but in Toga it seems to be effective...

"seems" is not convincing. I'll disable it in Toga2 in my cluster testing after the current stuff has finished, to see if it makes any difference. I can do the same for Fruit. And for Glaurung. I played about one million games and could not find any setting that was beneficial in Crafty. I'll see if that holds for the others as well since I can disable this in all 3 and then re-run a single test to see what happens for each.

[rjgibert]

My assumption has always been that verified null move was only interesting in positions where zugzwang was likely enough to make ordinary null move searching too risky. Using it on opening and middlegame positions seems like a wasted effort as your results seem to be indicating.

[MattieShoes]

Did your test have null move on where it'd normally be off? ie. late endgames?

[Teemu Pudas]

but in Toga it seems to be effective...

The code you posted contains a serious bug: the score from the verification search is hashed (at unreduced depth) and returned.

I'll disable it in Toga2 in my cluster testing after the current stuff has finished, to see if it makes any difference.

Which version of Toga are you using? Most of them have the same bug...

[kranium]

but in Toga it seems to be effective...

The code you posted contains a serious bug: the score from the verification search is hashed (at unreduced depth) and returned.

I'll disable it in Toga2 in my cluster testing after the current stuff has finished, to see if it makes any difference.

Which version of Toga are you using? Most of them have the same bug...

Teemu-

the code i used is directly from Fruit 2.1...(which i absolutely don't question regarding it's search architecture)...,
i.e. with very little eval (mobility, pst)...it acheives 2800 ELO! (and this almost entirely due to search alone!).

i've seen some good ideas that you've posted previously in the Toga Developers forum...

if you belive this verification code is a bug, please post the fix (your idea) for testing...(please forgive me if i seem at all sceptical, but improving on Fruit/Toga feels like squeezing water from a stone)...

Norm

[kranium]

here's what i'm currently using in Cyclone 3.4:
(only if king and minor pieces <= 3)...


// verification search

if (depth > 5)
{
if (value >= beta && (board->piece_size[board->turn] <= 3))
{

new_depth = depth - 5;
int ver_value =
full_no_null(board, alpha, beta, new_depth, height, new_pv, 1, trans_move, &move, false,
thread_id);

if (value >= beta)
{
played[played_nb++] = move;
best_move = move;
best_value = MIN(value, ver_value);
pv_copy(pv, new_pv);
goto cut;
}
}
}

[Ryan Benitez]

I have removed the verify code in Fruit because I am confidant that it is not useful. In cases that Null Move would be too high a risk just don't do a null move search at all.

[bob]

Did your test have null move on where it'd normally be off? ie. late endgames?

I do null in endgames, but in a limited way.

1. If there is more than a queen in material for one side, (not counting pawns) than I do full null-move always except for the usual in check/hash-table/etc restrictions.

2. If there is at least one piece of some type, I do null move but only out near the tips, not at the root.

I left this as is. In the current test I am running, with glaurung2.2, fruit 2 and toga2 I disabled the verification search completely, but left everything else alone. I disabled it by commenting the code out to avoid checking to see whether using a command to turn it off would affect other things. This test is running now, so I will have some info about all 3 with and without by tomorrow sometime.

This is the very thing I have been suspecting was happening. Too many ideas that sound good are are included, without any serious testing methodology to verify that the change is actually better. Let's see how this test goes to see if this is one of those good ideas that is not so good...