tt move vs null move

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

zenpawn
Posts: 260
Joined: Sat Aug 06, 2016 6:31 pm
Location: United States

tt move vs null move

Post by zenpawn » Sat May 27, 2017 2:02 am

In the case where a transposition table hit exists, but does not cause a cutoff, is it preferable / more common for that move to be tried before or after the null move?

User avatar
cdani
Posts: 2040
Joined: Sat Jan 18, 2014 9:24 am
Location: Andorra
Contact:

Re: tt move vs null move

Post by cdani » Sat May 27, 2017 4:40 am

zenpawn wrote:In the case where a transposition table hit exists, but does not cause a cutoff, is it preferable / more common for that move to be tried before or after the null move?
The tt move should be tried first after any quick node return attempts like null move, razoring, ...

User avatar
hgm
Posts: 22183
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Contact:

Re: tt move vs null move

Post by hgm » Sat May 27, 2017 5:29 am

A tricky issue. The fact that a hash move exists implies that in the previous seacrch the null move must have failed low. If beta is not lower than it was on that occasion, hoping it will fail high now seems like a fool's errand. Problem is that you do not know what beta was the last time. The score in the TT, if it is a lower bound, will only be an upper bound to that beta. If it is very much above the current beta (but you could not cut because the depth was insfficient), there is plenty of room for beta having decreased, and perhaps the null move will work now. In fact this is likely, as alpha-beta search is lazy, and hardly ever produces lower bounds far above beta.

If the score lower bound is below beta, however, the null move must have failed low before even under more favorable conditions. It is even doubtful the hash move will be adequate, then. So perhaps it is better to first verify that at lower depth, through IID.

Sven
Posts: 3572
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany

Re: tt move vs null move

Post by Sven » Sat May 27, 2017 9:50 am

hgm wrote:The fact that a hash move exists implies that in the previous seacrch the null move must have failed low.
Or that the null move was not tried at all, for one of many possible reasons, e.g.:
- low depth
- PV node
- static evaluation < beta
- number of consecutive null moves exceeded the maximum that you allow
- number of non-pawn, non-king pieces too low

User avatar
hgm
Posts: 22183
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Contact:

Re: tt move vs null move

Post by hgm » Sat May 27, 2017 10:18 am

Indeed. But if eval < beta, or the number of sliders was too low, this will also be the case now, so you would still not consider null move. 'Depth too low' would mean QS for me, and if you have a hash move from QS it would mean stand-pat did not cut, so eval < beta, and you would not want to do null move either. Number of consecutive null moves doesn't play a role if you use the condition eval >= beta, because that excludes the previous ply could be a null move if you can consider null move now.

That leaves the matter of the PV node. This can be seen from the TT entry: it would have an exact score. Note that I mainly discuss what to do in case of a lower bound.

Sven
Posts: 3572
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany

Re: tt move vs null move

Post by Sven » Sat May 27, 2017 10:47 am

hgm wrote:'Depth too low' would mean QS for me
Not for me. The formula is

Code: Select all

newDepth = depth - 1 - R
so depending on your strategy (i.e., allow jumping directly into QS or not) you allow null move either for depth >= R + 1 or for depth == R + 1, or you have a flexible approach that can reduce R down to 1. In any case, you would certainly never try the null move at depth == 1, and many engines wouldn't even try it at depth == 2 or depth == 3 either.

That covers the majority of full-width nodes, btw.

Sven
Posts: 3572
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany

Re: tt move vs null move

Post by Sven » Sat May 27, 2017 10:59 am

zenpawn wrote:In the case where a transposition table hit exists, but does not cause a cutoff, is it preferable / more common for that move to be tried before or after the null move?
The null move would be tried at reduced depth, which is the only way how it could ever be efficient. The TT move would be tried at full depth. So you would try the null move first.

zenpawn
Posts: 260
Joined: Sat Aug 06, 2016 6:31 pm
Location: United States

Re: tt move vs null move

Post by zenpawn » Sat May 27, 2017 11:18 am

Thank you for the lively discussion. It seems the consensus is to try the null move first even if there's a tt move.

Note: This is coming up in my engine now as I have implemented searching the tt move before generating the rest, so I have more flexibility in these kinds of decisions. Before this, null move was obviously tried before any moves, after first checking for tt cutoffs.

Interestingly, at fixed depth, RM now plays a different game than when all moves were generated with the tt move ordered to the beginning of the list. I expected there would be no difference, only a speedup.

User avatar
hgm
Posts: 22183
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Contact:

Re: tt move vs null move

Post by hgm » Sat May 27, 2017 11:37 am

Sven Schüle wrote:so depending on your strategy (i.e., allow jumping directly into QS or not) you allow null move either for depth >= R + 1 or for depth == R + 1, ...
That seems a very sub-optimal strategy. In any case you should consider null move if some reduction is possible, even if it is just 1 ply, rather than your usual R.

It also seems a mistake to not try null move at d=1. Indeed, there can be no reduction, and you will jump directly into QS. So what? Every other move you would search (with a possible exception of checks) would do that too. If a null move at d=1 would fail high, any completely passive move would fail high through the analogous QS tree. If you are not in a zugzwang situation (which you presumably detect before even considering null move), there will almost certainly be one move amongst the non-captures that does not affect any tactics. In a tense position there could be many non-captures that give away material, though. You can step on a square controlled by the opponent, you can move a soft-pinned piece, exposing what is behind it, you can withdraw essential protection of a piece that was under attack. All errors that would be punished in the QS that follows. The chances that you pick one of those moves (or even a few) first are appreciable. The null move will be free of any such defects, however. It is like an oracle that would make you pick the passive real move that doesn't spoil anything. In addition, when it works, you save yourself a move generation.

So I see lots of upsides. And so far I don't see a single downside.

Sven
Posts: 3572
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany

Re: tt move vs null move

Post by Sven » Sat May 27, 2017 6:42 pm

hgm wrote:
Sven Schüle wrote:so depending on your strategy (i.e., allow jumping directly into QS or not) you allow null move either for depth >= R + 1 or for depth == R + 1, ...
That seems a very sub-optimal strategy. In any case you should consider null move if some reduction is possible, even if it is just 1 ply, rather than your usual R.
Quoting me correctly would be helpful here: instead of "..." I appended:
Sven Schüle wrote:or you have a flexible approach that can reduce R down to 1
which solves your problem.
hgm wrote:It also seems a mistake to not try null move at d=1. Indeed, there can be no reduction, and you will jump directly into QS. So what? Every other move you would search (with a possible exception of checks) would do that too. If a null move at d=1 would fail high, any completely passive move would fail high through the analogous QS tree. If you are not in a zugzwang situation (which you presumably detect before even considering null move), there will almost certainly be one move amongst the non-captures that does not affect any tactics. In a tense position there could be many non-captures that give away material, though. You can step on a square controlled by the opponent, you can move a soft-pinned piece, exposing what is behind it, you can withdraw essential protection of a piece that was under attack. All errors that would be punished in the QS that follows. The chances that you pick one of those moves (or even a few) first are appreciable. The null move will be free of any such defects, however. It is like an oracle that would make you pick the passive real move that doesn't spoil anything. In addition, when it works, you save yourself a move generation.

So I see lots of upsides. And so far I don't see a single downside.
There is at least one downside but that one already decides the battle: trying the null move at d=1 can simply be proven to be wasted effort if at least one null move search fails low (and that will definitely happen). At a d=1 node all moves (subtrees) are searched with d=0 = QS (ignoring extensions here) until we get a cutoff. If you start by searching the null move with d=0 and you get a cutoff then the effort (in terms of tree size) is about the same as if you had searched one regular move to d=0 until getting a cutoff. But if the null move fails low then searching the null move simply adds nodes to the whole tree without any benefit. So you never save nodes this way but in general you search more nodes. Why would anyone do this? Trying the null move with a reduction of zero is useless, that is known for decades already.

Post Reply