A null move alternative ?

[Gerard Taille]

Though I played a lot of chess in the past I am not a chess programmer but a draughts programmer. Anyway it is clear that a lot of discussions on this forum are very interesting for other games and you may also be interested by ideas developed in other games.

Let’s take the null move item.

I understand that this null move concept is widely used in chess and this is very strange for me.

Let’s take a position P that you want to evaluate at depth N. If I understand correctly, under certain conditions you will try a null move at a reduction depth in order to know if it will create a fail high condition (value >= beta). If it is the case then you prune the tree at that position P.

In other word :
if eval(P+nullMove, N – R) >= beta then prune

In fact two assumptions are made here :

1) eval(P+nullMove, N – R) <= eval(P+BestMove, N – R)
2) eval(P+BestMove, N – R) ~ eval(P+BestMove, N)

The first assumption is practically always true (except zugswang) but the margin :
margin1 = eval(P+BestMove, N – R) - eval(P+nullMove, N – R)
can be very large because the nullMove can be a very bad move in particular when a threat exists.

The second assumption is a little more difficult to judge; the margin
margin 2 = eval(P+BestMove, N) - eval(P+BestMove, N – R)
can be positive or negative and can be also very large in unquiet positions

The nullMove approach is correct if margin1 + margin2 >= 0;

There is another very important point to note : the null move is efficient only if a fail high condition is discovered. As a consequence:
1) if position T is not an advantageous position (I mean eval(P, 0) < beta) then it is probably not interesting to try a nullMove
2) if the null move is a very bad move then the nullMove will produce far less fail high conditions comparing to the bestMove

My question is the following : did you try to compare the two following approaches

Approach null move :
if (eval(P,0) >= beta + marginX and ….) then
if (eval(P+nullMove, N-R) >= beta + marginY1) prune

Approach best move :
if (eval(P,0) >= beta + marginX and ….) then
if (eval(P+bestMove, N-R) >= beta + marginY2) prune

Note : if you do not have a best move available in your hash table you can easily replace (eval(P+bestMove, N-R) by (eval(P, N-R-1) or something like that.

For your information the nullMove is not a good idea in draughts game because a nullMove is quite often a goodMove in this game. I use the method I described above (with some other major improvement) and I am wondering if this alternative to the null move may be of interest for you.

[Don]

Though I played a lot of chess in the past I am not a chess programmer but a draughts programmer. Anyway it is clear that a lot of discussions on this forum are very interesting for other games and you may also be interested by ideas developed in other games.

Let’s take the null move item.

I understand that this null move concept is widely used in chess and this is very strange for me.

Let’s take a position P that you want to evaluate at depth N. If I understand correctly, under certain conditions you will try a null move at a reduction depth in order to know if it will create a fail high condition (value >= beta). If it is the case then you prune the tree at that position P.

In other word :
if eval(P+nullMove, N – R) >= beta then prune

In fact two assumptions are made here :

1) eval(P+nullMove, N – R) <= eval(P+BestMove, N – R)
2) eval(P+BestMove, N – R) ~ eval(P+BestMove, N)

The first assumption is practically always true (except zugswang) but the margin :
margin1 = eval(P+BestMove, N – R) - eval(P+nullMove, N – R)
can be very large because the nullMove can be a very bad move in particular when a threat exists.

The second assumption is a little more difficult to judge; the margin
margin 2 = eval(P+BestMove, N) - eval(P+BestMove, N – R)
can be positive or negative and can be also very large in unquiet positions

The nullMove approach is correct if margin1 + margin2 >= 0;

There is another very important point to note : the null move is efficient only if a fail high condition is discovered. As a consequence:
1) if position T is not an advantageous position (I mean eval(P, 0) < beta) then it is probably not interesting to try a nullMove
2) if the null move is a very bad move then the nullMove will produce far less fail high conditions comparing to the bestMove

My question is the following : did you try to compare the two following approaches

Approach null move :
if (eval(P,0) >= beta + marginX and ….) then
if (eval(P+nullMove, N-R) >= beta + marginY1) prune

Approach best move :
if (eval(P,0) >= beta + marginX and ….) then
if (eval(P+bestMove, N-R) >= beta + marginY2) prune

Note : if you do not have a best move available in your hash table you can easily replace (eval(P+bestMove, N-R) by (eval(P, N-R-1) or something like that.

For your information the nullMove is not a good idea in draughts game because a nullMove is quite often a goodMove in this game. I use the method I described above (with some other major improvement) and I am wondering if this alternative to the null move may be of interest for you.

The null move is so strong that a program loses very little in ELO from using it, given the same depth of search. I have fiddled around with margins (in my very strong komodo program) and never found anything better than null move without any margins - other than the implied ones you mention which come by default.

I personally hate null moves and would like to replace it with something better, because after a null move you don't have an actual position that is likely to be reached. But I cannot find anything to replace it, and it works incredibly well.

I am rather curious about reductions in checkers however. Do you make heavy use of what we call late move reductions in chess? It seems like this would be a natural thing in computer checkers. Do you understand how that works? For checkers I would imagine that you try just 1 or 2 moves full width, and reduce the depth of any you search after this. If the reduced depth search returns with a score above alpha, then you search it to the full depth. In chess there are some conditions most programmers put on whether to reduce moves that come later in the list, such as if it's a checking move, etc. In checkers I'm sure there must be easily identifiable classes of interesting moves.

Also, I was interesting in knowing if extensions are common in checkers. I looked around on the web but I cannot seem to find anything on how modern checkers program search - nothing other than the most trivially basic stuff. Is there something like that I can find on the web?

[michiguel]

Though I played a lot of chess in the past I am not a chess programmer but a draughts programmer. Anyway it is clear that a lot of discussions on this forum are very interesting for other games and you may also be interested by ideas developed in other games.

Let’s take the null move item.

I understand that this null move concept is widely used in chess and this is very strange for me.

Let’s take a position P that you want to evaluate at depth N. If I understand correctly, under certain conditions you will try a null move at a reduction depth in order to know if it will create a fail high condition (value >= beta). If it is the case then you prune the tree at that position P.

In other word :
if eval(P+nullMove, N – R) >= beta then prune

In fact two assumptions are made here :

1) eval(P+nullMove, N – R) <= eval(P+BestMove, N – R)
2) eval(P+BestMove, N – R) ~ eval(P+BestMove, N)

The first assumption is practically always true (except zugswang) but the margin :
margin1 = eval(P+BestMove, N – R) - eval(P+nullMove, N – R)
can be very large because the nullMove can be a very bad move in particular when a threat exists.

The second assumption is a little more difficult to judge; the margin
margin 2 = eval(P+BestMove, N) - eval(P+BestMove, N – R)
can be positive or negative and can be also very large in unquiet positions

The nullMove approach is correct if margin1 + margin2 >= 0;

There is another very important point to note : the null move is efficient only if a fail high condition is discovered. As a consequence:
1) if position T is not an advantageous position (I mean eval(P, 0) < beta) then it is probably not interesting to try a nullMove
2) if the null move is a very bad move then the nullMove will produce far less fail high conditions comparing to the bestMove

My question is the following : did you try to compare the two following approaches

Approach null move :
if (eval(P,0) >= beta + marginX and ….) then
if (eval(P+nullMove, N-R) >= beta + marginY1) prune

Approach best move :
if (eval(P,0) >= beta + marginX and ….) then
if (eval(P+bestMove, N-R) >= beta + marginY2) prune

Yes, and it did not work for me, but I still think there could be something good out of this. I tried with margins = 0 if I understand correctly. However, it there is any gain, it will be very very minor. That is the reason why I left it aside for a long while.

Miguel

Note : if you do not have a best move available in your hash table you can easily replace (eval(P+bestMove, N-R) by (eval(P, N-R-1) or something like that.

For your information the nullMove is not a good idea in draughts game because a nullMove is quite often a goodMove in this game. I use the method I described above (with some other major improvement) and I am wondering if this alternative to the null move may be of interest for you.

[hgm]

My engines use what you call "approach null move", without margins. Some people say that always doing null move is better for them. My suspicion is that this is an artifact, where the null move acts as a implicit internal iterative deepening, filling the hash table with reduced-depth search results, helping the main search find a best move, or have better history values. (My engines use explicit IID, and won't benefit from such effects.)

I don't expect the other idea to work. Bestmoves are too likely to be delaying tactics, that psh a problem that exists after null move over the horizon, without solving it. You need at least two ply extra to always recognize the same problem for a real move, compared to null move.

[Gerard Taille]

The null move is so strong that a program loses very little in ELO from using it, given the same depth of search. I have fiddled around with margins (in my very strong komodo program) and never found anything better than null move without any margins - other than the implied ones you mention which come by default.

I personally hate null moves and would like to replace it with something better, because after a null move you don't have an actual position that is likely to be reached. But I cannot find anything to replace it, and it works incredibly well.

No doubt in my mind that the null move concept is very interesting. I only say that an interesting alternative may exist with perhaps a better efficiency (but objectively I cannot be sure)

I am rather curious about reductions in checkers however. Do you make heavy use of what we call late move reductions in chess? It seems like this would be a natural thing in computer checkers. Do you understand how that works? For checkers I would imagine that you try just 1 or 2 moves full width, and reduce the depth of any you search after this. If the reduced depth search returns with a score above alpha, then you search it to the full depth. In chess there are some conditions most programmers put on whether to reduce moves that come later in the list, such as if it's a checking move, etc. In checkers I'm sure there must be easily identifiable classes of interesting moves.

Also, I was interesting in knowing if extensions are common in checkers. I looked around on the web but I cannot seem to find anything on how modern checkers program search - nothing other than the most trivially basic stuff. Is there something like that I can find on the web?

First of all I am not a checkers player. The game I program is the international 10x10 draughts game whose rules are different. So I am not able to answer your questions on checkers.
Anyway I have an extensive use of late move reduction in order to avoid spending a lot of time on obviously bad moves. In fact I use a two step reduction.
The basic idea I use is the following :
Let's take a position at 15 plies from the leaf of the tree
1) Fisrt of all I evaluate each legal move using a search at depth 2 or 3 plies, in order to determine which moves are good and which are bad (for this task you can of course use the hashtable if it can help). Typically I want to detect the moves losing some material without recapturing it immediatly by the following moves
2) I search the good moves with full depth
3) I seach the remaining bad moves with a depth reduction depending of how bad the move is. In case of a fail high on a bad move I search again this "new good move" at full depth.

Coming back to the null move I have another question :
Let's assume an advantageous position which appears as a good candidat for using the null move with a reduction R : I mean you calculate eval(P+nullMove, N-R) in order to try to avoid calculating eval(P,N).
What do you do if the hashtable tells you that the best move assure that eval(P,M) is better than beta and you have N-R < M < N ?

[Gerard Taille]

Yes, and it did not work for me, but I still think there could be something good out of this. I tried with margins = 0 if I understand correctly. However, it there is any gain, it will be very very minor. That is the reason why I left it aside for a long while.

Miguel

Thank you for your answer Miguel. Now I know that you tried the best move reduction approach I described but without good results. I am wondering if the efficiency of this approch may depend on the search algorithm. BTW my search algorithm is a kind of MTD-f best algorithm.
What is your feeling concerning the efficiency of such best move reduction approach in the context of a MTD-f algorithm ?

[Gerard Taille]

My engines use what you call "approach null move", without margins. Some people say that always doing null move is better for them. My suspicion is that this is an artifact, where the null move acts as a implicit internal iterative deepening, filling the hash table with reduced-depth search results, helping the main search find a best move, or have better history values. (My engines use explicit IID, and won't benefit from such effects.)

I don't expect the other idea to work. Bestmoves are too likely to be delaying tactics, that psh a problem that exists after null move over the horizon, without solving it. You need at least two ply extra to always recognize the same problem for a real move, compared to null move.

Detecting a problem earlier with a null move is effectively a good point. I have to think about it because it seems not so simple : if the null move allow to detect such problem that means that the null move will not achieve a fail high and as a consequence a full depth search will occur. As a consequence the best move will be analysed with the same risk that the problem detected disappears.
In any case it is a very interseting point.

[Cardoso]

Hi,
I'm also a checkers programmer (portuguese variant with flying queens).

Do you use verification search if the null search failed high?
My verification search depth is depth - 2*PLY.
I've tryed null move, but not tremendously sucessfull.
It did some fine node count reductions, but it is not very accurate.

If you use the international 10x10 or greater you must implemnte a multi-core engine.

Alvaro

[Don]

The null move is so strong that a program loses very little in ELO from using it, given the same depth of search. I have fiddled around with margins (in my very strong komodo program) and never found anything better than null move without any margins - other than the implied ones you mention which come by default.

I personally hate null moves and would like to replace it with something better, because after a null move you don't have an actual position that is likely to be reached. But I cannot find anything to replace it, and it works incredibly well.

No doubt in my mind that the null move concept is very interesting. I only say that an interesting alternative may exist with perhaps a better efficiency (but objectively I cannot be sure)

I am rather curious about reductions in checkers however. Do you make heavy use of what we call late move reductions in chess? It seems like this would be a natural thing in computer checkers. Do you understand how that works? For checkers I would imagine that you try just 1 or 2 moves full width, and reduce the depth of any you search after this. If the reduced depth search returns with a score above alpha, then you search it to the full depth. In chess there are some conditions most programmers put on whether to reduce moves that come later in the list, such as if it's a checking move, etc. In checkers I'm sure there must be easily identifiable classes of interesting moves.

Also, I was interesting in knowing if extensions are common in checkers. I looked around on the web but I cannot seem to find anything on how modern checkers program search - nothing other than the most trivially basic stuff. Is there something like that I can find on the web?

First of all I am not a checkers player. The game I program is the international 10x10 draughts game whose rules are different. So I am not able to answer your questions on checkers.
Anyway I have an extensive use of late move reduction in order to avoid spending a lot of time on obviously bad moves. In fact I use a two step reduction.
The basic idea I use is the following :
Let's take a position at 15 plies from the leaf of the tree
1) Fisrt of all I evaluate each legal move using a search at depth 2 or 3 plies, in order to determine which moves are good and which are bad (for this task you can of course use the hashtable if it can help). Typically I want to detect the moves losing some material without recapturing it immediatly by the following moves
2) I search the good moves with full depth
3) I seach the remaining bad moves with a depth reduction depending of how bad the move is. In case of a fail high on a bad move I search again this "new good move" at full depth.

Coming back to the null move I have another question :
Let's assume an advantageous position which appears as a good candidat for using the null move with a reduction R : I mean you calculate eval(P+nullMove, N-R) in order to try to avoid calculating eval(P,N).
What do you do if the hashtable tells you that the best move assure that eval(P,M) is better than beta and you have N-R < M < N ?

In general you do the null move first, then search the resulting position to the reduced depth. If the search returns a score greater than beta of course you can take the cutoff.

I don't do any hash table checks but the null move search itself would do a hash table look up immediately and then exit if the returned a score greater than beta.

If I understand you correctly, you are asking if we could accept the hash table score (before the null move is tried) if it's deeper than the reduced depth search we would do?

My answer is that in Chess this would be unreliable. This is equivalent to just doing a smaller depth reduction search without the null move. It would be like null move verification search without the actual null move phase.

It might be feasible to do something like this if the score was significantly above beta using some margin. I have not tried that exact test. So, for example, if the static evaluation was 1/2 pawn above beta you might get away with simply reducing the depth as a quick sanity check. It would probably make sense in chess to FIRST try the null move search with a big reduction and if that does not give you a cutoff then try to get it with a reduced depth search of some modest amount (using the margin condition.)

Some programs just use a margin without any search whatsoever if there is a low depth remaining. So, for example, if the static evaluation was half a pawn to the good, you might take a cutoff under the assumption that since it's your turn to move nothing bad is likely to happen in the short remaining depth.

Does that answer your question?

[bob]

Just for the record, null-move is most often used to reduce the cost of searching below unsound sacrifices. At some ply you play QxP. And your opponent plays PxQ. Below this move, anywhere it is the PxQ side's turn to move a null move will fail high. He does nothing, and there is no way to recover the queen, even given the chance to play two moves in a row, so you quickly get out of that QxP line and into something more useful.

If you could play against a GM, with one special rule, that at some point in the game, you get to make two consecutive moves, the GM would have a very difficult time beating a good chess player, not one even at IM/GM level, just good. Because suddenly he has to play a game where he can't hang a piece to any two move threat, He can't leave any piece under attack, else you will use your two moves to take it and retreat. That is a strong advantage. And the reason the "null-move observation" (Don Beal's term) works. It is so strong, even a reduced-depth search is should be able to see how a good position can't be ripped by a null-move, showing that the position is too good for the opponent to allow it

Zugzwang is the obvious problem. But the key is not hash table scores or anything else, it is the effect of your passing and letting your opponent play a second move. If this fails high, your opponent's position sucks and yours is good enough to declare a beta cutoff and quit.