Null move: minimum depth

[Rebel]

I use min depth = 2 currently. So do a number of other programs, such as Protector & Stockfish.

--Jon

Don't see how that helps unless you really limit R. IE with R=3, mindepth = 1 or 2 or 3 is the same thing. All collapse tree to q-search nodes.

I think Jon means when the remaining depth is 3 you still can do null-move with R=2.

Shoot, you can do it with R=3 also, so long as you have the qsearch checks...

Sure, it's what I do and probably the vast majority also.

[hgm]

That is the problem with doing null-move at d=1. It doesn't save nodes.

It does't save nodes by depth. But that doesn't mean it cannot be the best choice as first move to search, when current eval >= beta. (If current eval < beta the nullmove is of course futile, as the opponent would stand pat to refute it.).

For one, if could make you fail high without generating moves. Secondly, when null move does not work despite eval >= beta it means there must be a threat against you. In that situation most real moves won't solve the threat, and would be refuted the same way. So randomly picking such moves is likely to take a long time before you arrive at the cut-move. Standard move ordering is just not very good in positions with threats against the side to move. If you could save the day by executing any pieces held hostage with your best captures, you probably could have done that in QS after null move as well, so you are not very likely to have such captures.

By playing null move first you could learn from its refutation what the threat is, and sort possible threat evasions (like retreating the hanging piece) in front.

[hgm]

Not sure I follow. I do null-move at LEAST R=3 at any depth remaining in the search. 2 or 3 and beyond. But then I generate checks in the first q-search ply (only first ply) and also check evasions at q-search ply=2 if the previous move was a check. I did look and verified I do not do 'em at remaining depth = 1 however...

I am happy to allow the search to go from depth=3 left to q-search, since I still pick up the Qg7# move. This is yet another form of zugzwang, where by not moving you do well, since you hide the good move from your opponent by dropping into q-search where he can't find it..

Well, the issue is what the best course of action would be if you do NOT search checks in QS. There seems to be a choice here: you could either refrain from doing null move at all when the standard reduction would bring you to QS, or you could take a smaller reduction so you leave a d=1 search.

In the first case (with R=2) you would refrain from doing null move at d=2 and d=3. (As mentioned before, there never seems to be a reason to exclude it at d=1.) This seems quite expensive, especially at d=3, where you would then always need to search real moves at d=3, where in most cases a d=1 null move would have sufficed. With the second choice you would have to do an unreduced null-move search at d=2, and you could do a 1-ply-reduced null-move search in d=3 nodes. Especially the latter seems cheaper than not doing nullmove at all.

Yet another solution would be to have a special null-move-reply node where you do search checks + captures, different from normal QS.

I recall that I once tested giving all checks in the first level of QS, (and extend for the evasion), and that this only weakened the engine. My conclusion was that most checks in the leaves of the full-width search are not very dangerous, and that it is mostly a waste of time to search them.

Detecting mate-in-1 opprtunities could of course be a lot cheaper than systematically searching all checks. It would not require any extra general search nodes, just some extra time.

[Xann]

Yet another solution would be to have a special null-move-reply node where you do search checks + captures, different from normal QS.

This is what Senpai does, except that I didn't even bother with checks. Low-depth (<= 3) NMP calls a static version of QS that is basically 1-ply QS + SEE, similar to grandpa's global SEE I guess. More precisely, the score of a move is eval + SEE + constant positional bonus. Moves with SEE <= 0 don't count as threats, so the bonus is not awarded. The only optimisation I implemented is to only "search" the first (LV) capture for each victim.

Not only did it (I call it static QS/NMP) allow me to have NMP at depth 1 as I wanted, but it also proved a good replacement at depth 2 and 3. Interestingly, Senpai does search checks in the regular QS.

[bob]

Not sure I follow. I do null-move at LEAST R=3 at any depth remaining in the search. 2 or 3 and beyond. But then I generate checks in the first q-search ply (only first ply) and also check evasions at q-search ply=2 if the previous move was a check. I did look and verified I do not do 'em at remaining depth = 1 however...

I am happy to allow the search to go from depth=3 left to q-search, since I still pick up the Qg7# move. This is yet another form of zugzwang, where by not moving you do well, since you hide the good move from your opponent by dropping into q-search where he can't find it..

Well, the issue is what the best course of action would be if you do NOT search checks in QS. There seems to be a choice here: you could either refrain from doing null move at all when the standard reduction would bring you to QS, or you could take a smaller reduction so you leave a d=1 search.

In the first case (with R=2) you would refrain from doing null move at d=2 and d=3. (As mentioned before, there never seems to be a reason to exclude it at d=1.) This seems quite expensive, especially at d=3, where you would then always need to search real moves at d=3, where in most cases a d=1 null move would have sufficed. With the second choice you would have to do an unreduced null-move search at d=2, and you could do a 1-ply-reduced null-move search in d=3 nodes. Especially the latter seems cheaper than not doing nullmove at all.

Yet another solution would be to have a special null-move-reply node where you do search checks + captures, different from normal QS.

I recall that I once tested giving all checks in the first level of QS, (and extend for the evasion), and that this only weakened the engine. My conclusion was that most checks in the leaves of the full-width search are not very dangerous, and that it is mostly a waste of time to search them.

Detecting mate-in-1 opprtunities could of course be a lot cheaper than systematically searching all checks. It would not require any extra general search nodes, just some extra time.

OK, that is usually called "adaptive null-move" which is reduced so that depth - 1 - R is at least 1. That gives you that ply of full-width to avoid hiding something critical. Crafty did this for many years, until I decided to add q-checks. I didn't see much benefit at all to adding qchecks until I fixed R = 3 everywhere, then the benefit became apparent.

A few of us beat this to death way back. Stanback, Bruce Moreland, myself, and a couple of others (discussion started on r.g.c.c. I can't guarantee this is still the case today. Back then we were happy to reach 10 plies on a pentium-133 or pentium-pro-200. Todays we are going 3x as deep, might not be as big an issue for all I know.

[Henk]

Not sure I follow. I do null-move at LEAST R=3 at any depth remaining in the search. 2 or 3 and beyond. But then I generate checks in the first q-search ply (only first ply) and also check evasions at q-search ply=2 if the previous move was a check. I did look and verified I do not do 'em at remaining depth = 1 however...

I am happy to allow the search to go from depth=3 left to q-search, since I still pick up the Qg7# move. This is yet another form of zugzwang, where by not moving you do well, since you hide the good move from your opponent by dropping into q-search where he can't find it..

Well, the issue is what the best course of action would be if you do NOT search checks in QS. There seems to be a choice here: you could either refrain from doing null move at all when the standard reduction would bring you to QS, or you could take a smaller reduction so you leave a d=1 search.

In the first case (with R=2) you would refrain from doing null move at d=2 and d=3. (As mentioned before, there never seems to be a reason to exclude it at d=1.) This seems quite expensive, especially at d=3, where you would then always need to search real moves at d=3, where in most cases a d=1 null move would have sufficed. With the second choice you would have to do an unreduced null-move search at d=2, and you could do a 1-ply-reduced null-move search in d=3 nodes. Especially the latter seems cheaper than not doing nullmove at all.

Yet another solution would be to have a special null-move-reply node where you do search checks + captures, different from normal QS.

I recall that I once tested giving all checks in the first level of QS, (and extend for the evasion), and that this only weakened the engine. My conclusion was that most checks in the leaves of the full-width search are not very dangerous, and that it is mostly a waste of time to search them.

Detecting mate-in-1 opprtunities could of course be a lot cheaper than systematically searching all checks. It would not require any extra general search nodes, just some extra time.

OK, that is usually called "adaptive null-move" which is reduced so that depth - 1 - R is at least 1. That gives you that ply of full-width to avoid hiding something critical. Crafty did this for many years, until I decided to add q-checks. I didn't see much benefit at all to adding qchecks until I fixed R = 3 everywhere, then the benefit became apparent.

A few of us beat this to death way back. Stanback, Bruce Moreland, myself, and a couple of others (discussion started on r.g.c.c. I can't guarantee this is still the case today. Back then we were happy to reach 10 plies on a pentium-133 or pentium-pro-200. Todays we are going 3x as deep, might not be as big an issue for all I know.

I remember I added king checks on depth = 0 but that was much too expensive. So it is a secret to me how to implement that efficiently. Trying again is useless if you make the same mistake again. Also I still don't understand why jumping to depth = 1 after null move would be less efficient. Reducing with 3 instead of 2 near the leaves after null move does that skip that many nodes ? Perhaps this discussion is a waste of time for I don't expect much ELO improvements here.

[flok]

How is it done in practice?

E.g.:

depth 0 (start) I do a null-move of 3
depth 3 previous move was null-move so I just "do" this move
depth 4 previous move was not null-move so now I do a null-move again
depth 7 and so on?

[hgm]

Yes, that is basically it. Except that usually 'depth' is used in the sense of remaing depth, and thus starts high in the root and decreases towards the leaves.

[Daniel Anulliero]

Yes, that is basically it. Except that usually 'depth' is used in the sense of remaing depth, and thus starts high in the root and decreases towards the leaves.

Soory but sometimes I'm confused with "depth" and "ply"
For exemple : suppose we have ID from 1 to 6
ply = 0;
for(i=1;i<7;++i)
search(alpha , beta , i) // depth = i

when a move is played , ply ++ //ply increase after each move , depth decrease , ok

The test in nullmove must be if((!incheck .... && (ok_null) etc && (ply > 2)) ?
no (depth > 2)
right ?
heeeelp me lol !

[Henk]

Depth is a parameter of search. Depth has value zero near the leaves of the search tree. It has maximum value at the root node. ply count is the length of a path in the search tree.