A null move alternative ?

[Gerard Taille]

Hi,

Hi,
Do you use verification search if the null search failed high?
Alvaro

I do not use the null move. As I said a null move would be often a good move in draugths. As a consequence it would be unreliable to use it in order to have a fail high with depth reduction.

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

Yes I use currently an 8 cores engine (2 quad cores).

[Gerard Taille]

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.

If I understand what you mean one of the biggest advantage of the null move is that it is a bad move and could be even a very very bad move (as you said a good chess player can beat a GM with the help of the null move).
With this fact in mind I quite undersatnd that you can prune if this "bad" null move produces a fail high at a reduction depth.
Where is my point ? My point is that you do not know how bad the null move is. The margin between the null move and the best move can be very small or very large and you do not have any control on that. As a consequence, if this margin is very large, you will not reach a fail high condition with the null move though the postion may be clearly very advantageous and uninteresting for a deep search.
Instead of the null move why then not use a "good" move (not necessarily the best one) and calculate eval(P+goodMove, N-R) in order to know if this value is greater than beta+magicMargin ?
The difference is that you control now the margin you would have to see before pruning after a reduction and a fail high condition.
Note : as a side effect, with this method, a zugswang position is no more a problem.

[hgm]

I once tries to use an expected neutral move in stead of the null move, where I figured in most middle-game positions with a safely tugged-away King, King moves (e.g. Kg1-h1 and vice versa) would be neutral. It did not work at all...

The problem with your idea is this: how would you know in advance if something is a 'goodMove', before searching it? If you first had to search ll moves, or a lot of them, even at reduced depth, to figure out which one is 'good', you would have already given away a large part of the reduction advantage. And moves that seem good based on search score, often only get this good score by delaying the inevitable, rather than solving it.

There is a second reason why fail-high on the null move is more reliable than the fail-high on a good move: if a deeper search on the null move starts to dig up enough trouble to make it fail low, I will always have an extra tempo up my sleave to pre-emptively slove that trouble, when all else fails. I would not have that if I had already spent my move on a 'good move'.

I admit that all these arguments carry less weight if the 'good move' is something like an obvious recapture of a Queen, especially if the remaining depth is large, and the fail high of the null move only marginal. Yo might have to fight very hard to retain your advantage in that case, against a rampant Queen that has wrecked your defence in the null-move branch. While simply cashing the Queen would strongly reduce the branching ratio of the fail-low side, and pump up your advantage so much that yo can afford a whole string of null moves later, buying you more reduction in the most difficult branches than you had after null move.

I once experimented reducing 'overwhelmingly good captures' (which would bring you more than a iece above beta) even more than the null move, based on the idea that the opportunity to make such a capture proved that the preceding opponent move must have been a bad blunder, that really did not deserve to be searched at all. This seemed competative, even when I did it only after the null move failed low. But with a larger reduction, it would have of course been much cheaper to try such recapture searches first, such that you don't even have to do the more expensive null-move search. So first search all recaptures with beta upshifted by 300 and a reduction of 4 ply, (perhaps using SEE guidance to see if this is realistic), and only if they fail low, try null move with R=2.

[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.

If I understand what you mean one of the biggest advantage of the null move is that it is a bad move and could be even a very very bad move (as you said a good chess player can beat a GM with the help of the null move).
With this fact in mind I quite undersatnd that you can prune if this "bad" null move produces a fail high at a reduction depth.
Where is my point ? My point is that you do not know how bad the null move is. The margin between the null move and the best move can be very small or very large and you do not have any control on that. As a consequence, if this margin is very large, you will not reach a fail high condition with the null move though the postion may be clearly very advantageous and uninteresting for a deep search.
Instead of the null move why then not use a "good" move (not necessarily the best one) and calculate eval(P+goodMove, N-R) in order to know if this value is greater than beta+magicMargin ?
The difference is that you control now the margin you would have to see before pruning after a reduction and a fail high condition.
Note : as a side effect, with this method, a zugswang position is no more a problem.

The "margin" is not the issue. It is about how bad the null move actually is in almost all positions. If I am way ahead in material, a null-move won't cause me to lose that material advantage. If I have significant threats, a null-move won't let you get out of all of them. Etc. Since giving you 2 moves in succession ought to give you a winning advantage, and it should not take much search depth to see this. If I give you 2 moves in a row, and I am still winning, then there is no point in searching this position deeper to see just how good it really is.

Don't get hung up on playing a better move than a null-move. Unless you are in zugzwang, _any_ move is better than a null. Any move other than a null would make the reduced depth search far less meaningful, and you could have severe tactical oversights if you use the result.

[Gerard Taille]

The problem with your idea is this: how would you know in advance if something is a 'goodMove', before searching it? If you first had to search ll moves, or a lot of them, even at reduced depth, to figure out which one is 'good', you would have already given away a large part of the reduction advantage.

For me a good move is simply the move found in the hashtable (if this move exists in the hashtable). Otherwise I can search at only 2 or 3 plies to find what looks like a good move and in particular a recapture.

And moves that seem good based on search score, often only get this good score by delaying the inevitable, rather than solving it.

That is effectively a good point I have to study in order to see if it could help me for draugths game.

There is a second reason why fail-high on the null move is more reliable than the fail-high on a good move: if a deeper search on the null move starts to dig up enough trouble to make it fail low, I will always have an extra tempo up my sleave to pre-emptively slove that trouble, when all else fails. I would not have that if I had already spent my move on a 'good move'.

I have to confess I do not understand this point concerning an "extra tempo". I do not see the difference between eval(P=nullMove, N-R) and eval(P+goodMove, N-R). For these two searches I spent quite the same time because the depth is the same. The only difference is the first move (nullMove vs goodMove). Can you explain why an extra-tempo is available in one case and not in the other ?

I once experimented reducing 'overwhelmingly good captures' (which would bring you more than a iece above beta) even more than the null move, based on the idea that the opportunity to make such a capture proved that the preceding opponent move must have been a bad blunder, that really did not deserve to be searched at all. This seemed competative, even when I did it only after the null move failed low. But with a larger reduction, it would have of course been much cheaper to try such recapture searches first, such that you don't even have to do the more expensive null-move search. So first search all recaptures with beta upshifted by 300 and a reduction of 4 ply, (perhaps using SEE guidance to see if this is realistic), and only if they fail low, try null move with R=2.

That looks like I have done with reduction. As I said I do not use the null move because it is often a good move in draughts but our exchanges on the subject tell me I have to analyse if the null move approach could help to discover an existing threat which have to be solved anyway avoiding delaying the problem by the good move.

Not so simple indeed but very interesting!

[Don]

I once tries to use an expected neutral move in stead of the null move, where I figured in most middle-game positions with a safely tugged-away King, King moves (e.g. Kg1-h1 and vice versa) would be neutral. It did not work at all...

This in idea I also had a long time ago. I really hate null move, but nothing I have found works better.

The "problem", if you want to call it that, is that a null move gives so much of an advantage to the other side that you cannot take a deserved cutoff.

On the other hand, it's difficult to know if the threat is meaningless or not. A threat that looks easily parried is often just the start of a long sequence of horizon moves and there is actually a real threat.

It's funny to me that I had the same idea of using king moves!

[hgm]

For me a good move is simply the move found in the hashtable (if this move exists in the hashtable). Otherwise I can search at only 2 or 3 plies to find what looks like a good move and in particular a recapture.

Well, a move in the hash table would be a move (and score) obtained by search. Sothesame still applies, exceptthat the hash table hit is speedingupthings a little. (Which is what the hash table is for.)

I have to confess I do not understand this point concerning an "extra tempo". I do not see the difference between eval(P=nullMove, N-R) and eval(P+goodMove, N-R). For these two searches I spent quite the same time because the depth is the same. The only difference is the first move (nullMove vs goodMove). Can you explain why an extra-tempo is available in one case and not in the other ?

What I mean is that you can replace the null move (which effectively s wasting a tempo) by a pre-emptive cure for whatever threat yo discover. (Like protecting a piece that will get lost, move it away from a Knight's-fork square, evacuate a square for it to retreat to, etc.) After a real move, you can only do all these things in stead of the real move, which can have all kind of bad consequences you have no idea of. Chess programs are not very good ad fathoming the reason their moves are good; an insignificantly looking non-capture can cover a square where you get matedif you don't cover it. And the program will never have any idea how narrowly it escaped checkmate. After null move, you would see it. And if you didn't, you can be pretty sure most moves will not be fatally flawed because they fail to do something essential.

[Gerard Taille]

Hi,

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.

If I understand what you mean one of the biggest advantage of the null move is that it is a bad move and could be even a very very bad move (as you said a good chess player can beat a GM with the help of the null move).
With this fact in mind I quite undersatnd that you can prune if this "bad" null move produces a fail high at a reduction depth.
Where is my point ? My point is that you do not know how bad the null move is. The margin between the null move and the best move can be very small or very large and you do not have any control on that. As a consequence, if this margin is very large, you will not reach a fail high condition with the null move though the postion may be clearly very advantageous and uninteresting for a deep search.
Instead of the null move why then not use a "good" move (not necessarily the best one) and calculate eval(P+goodMove, N-R) in order to know if this value is greater than beta+magicMargin ?
The difference is that you control now the margin you would have to see before pruning after a reduction and a fail high condition.
Note : as a side effect, with this method, a zugswang position is no more a problem.

The "margin" is not the issue. It is about how bad the null move actually is in almost all positions. If I am way ahead in material, a null-move won't cause me to lose that material advantage. If I have significant threats, a null-move won't let you get out of all of them. Etc. Since giving you 2 moves in succession ought to give you a winning advantage, and it should not take much search depth to see this. If I give you 2 moves in a row, and I am still winning, then there is no point in searching this position deeper to see just how good it really is.

Don't get hung up on playing a better move than a null-move. Unless you are in zugzwang, _any_ move is better than a null. Any move other than a null would make the reduced depth search far less meaningful, and you could have severe tactical oversights if you use the result.

No doubt your are right for chess. With the help of your posts I will analyse if I can use this null move concept in certain circumtances, I mean if I can detect that a null move have a very high probability to be a bad move.

[bob]

Hi,

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.

If I understand what you mean one of the biggest advantage of the null move is that it is a bad move and could be even a very very bad move (as you said a good chess player can beat a GM with the help of the null move).
With this fact in mind I quite undersatnd that you can prune if this "bad" null move produces a fail high at a reduction depth.
Where is my point ? My point is that you do not know how bad the null move is. The margin between the null move and the best move can be very small or very large and you do not have any control on that. As a consequence, if this margin is very large, you will not reach a fail high condition with the null move though the postion may be clearly very advantageous and uninteresting for a deep search.
Instead of the null move why then not use a "good" move (not necessarily the best one) and calculate eval(P+goodMove, N-R) in order to know if this value is greater than beta+magicMargin ?
The difference is that you control now the margin you would have to see before pruning after a reduction and a fail high condition.
Note : as a side effect, with this method, a zugswang position is no more a problem.

The "margin" is not the issue. It is about how bad the null move actually is in almost all positions. If I am way ahead in material, a null-move won't cause me to lose that material advantage. If I have significant threats, a null-move won't let you get out of all of them. Etc. Since giving you 2 moves in succession ought to give you a winning advantage, and it should not take much search depth to see this. If I give you 2 moves in a row, and I am still winning, then there is no point in searching this position deeper to see just how good it really is.

Don't get hung up on playing a better move than a null-move. Unless you are in zugzwang, _any_ move is better than a null. Any move other than a null would make the reduced depth search far less meaningful, and you could have severe tactical oversights if you use the result.

No doubt your are right for chess. With the help of your posts I will analyse if I can use this null move concept in certain circumtances, I mean if I can detect that a null move have a very high probability to be a bad move.

That's been "the holy grail" of null-move search for years. From trying the double-null-move approach, to the verification search, to various pre-qualifiers to eliminate null-move when it is bad. But while it is always considered a good idea to study, no good solutions have been found, yet...

[Gerard Taille]

Hi,
I begin to analyse if I can use the null move in draughts game. Of course it is very different from chess because a null move is often a good move in draugths.
Of course it exists a lot of situations where the two games are very similar. For example in the qsearch I guess that in chess it could be very bad to return the evaluation of a position in which it exists a big threat on the king or a even a piece.
My question is the following : do you see any interest to use the null move in the qsearch ? The situation I have in mind is the following : you have the move with white side and you detect (by an analyse of the position and without the null move) that one or several of your pieces can be captured if it were black to play, and you decide to continue the qsearch one ply further. In this situation I am wondering if you can use the null move in order to identifiy what are really the opponent black captured moves and you store these moves as "potentiel killer moves". Now you continue the qsearch one ply further (you generate the white moves) and then you try only the "potential killer moves" you identified.
Note : of course you will certainly not allow to use more than one time the null move in a branch of the qsearch.
I never try such idea.
What is your feeling ?