tt move vs null move
Moderators: hgm, Rebel, chrisw
-
- Posts: 349
- Joined: Sat Aug 06, 2016 8:31 pm
- Location: United States
tt move vs null move
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?
-
- Posts: 2204
- Joined: Sat Jan 18, 2014 10:24 am
- Location: Andorra
Re: tt move vs null move
The tt move should be tried first after any quick node return attempts like null move, razoring, ...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?
Daniel José - http://www.andscacs.com
-
- Posts: 27817
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: tt move vs null move
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.
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.
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: tt move vs null move
Or that the null move was not tried at all, for one of many possible reasons, e.g.:hgm wrote:The fact that a hash move exists implies that in the previous seacrch the null move must have failed low.
- 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
-
- Posts: 27817
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: tt move vs null move
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.
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.
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: tt move vs null move
Not for me. The formula ishgm wrote:'Depth too low' would mean QS for me
Code: Select all
newDepth = depth - 1 - R
That covers the majority of full-width nodes, btw.
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: tt move vs 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 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?
-
- Posts: 349
- Joined: Sat Aug 06, 2016 8:31 pm
- Location: United States
Re: tt move vs null move
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.
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.
-
- Posts: 27817
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: tt move vs null move
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.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, ...
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.
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: tt move vs null move
Quoting me correctly would be helpful here: instead of "..." I appended:hgm wrote: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.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, ...
which solves your problem.Sven Schüle wrote:or you have a flexible approach that can reduce R down to 1
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.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.