Question to H.G. Muller - null move

[Cardoso]

Hi,
you seem to have quite a good grasp on game tree searching.
Your comment about not paying any attention to the number of null moves in a row in Micromax really caught my attention.
Unfortunately I'm not half as good as you and I really would like to try your idea in checkers (Portuguese/Spanish checkers with flying kings).
I've allways been told that null move won't work in checkers.
What is your opinion on this?
Could you please express your null move idea in pseudo code?

Best regards,
Alvaro

[hgm]

Let me start saying that I am a very poor Checkers player, and understand very little of the strategy or tactics for that game.

Null move pruning in Chess works well because of a combination of reasons. One of those is that Chess posistons almost always include trading possibilities, that can be used as delaying tactic for the opponent's plan. If I am in danger of losing a piece, and I can play RxR or QxQ, the opponent will have to take back the R or Q first. Which usualy won't change the fact that I am going to lose the piece, but does delay it two ply. Even playing BxN would mask the impending loss, as the opponent can only capture back one piece at the time. And even bad trades, line NxP, might seem to soften the loss (perhaps enough to turn a fail low into a fail high, depending on the search window), because whether he takes back the N or the piece he is going to gain anyway, at least I now have a Pawn for it, and that I will actually lose two pieces is pushed beyond the horizon.

Given the fact that you can almost always delay an inevitable loss by two ply through playing a delaying tactic, makes it pointless to search position at N+2 ply when the null move at N ply fails high. It could be that the null move at N+2 ply would show you an opponent plan against which you have no defense, but when you will use your first move as a delaying tactic, that same threat will need an N+4 ply search to be discovered. So you can afford a null-move search reduced by 2 ply compared to the real search, and it will in most cases give you a good prediction of a fail high of that real search. As an alternative to trades, you have delaying tactics by attacking smetihng valuable or undefended, which the opponent then will hve to withdraw before executing his plan.

Now in checkers, capturing is mandatory. So in Checkers positions you cannot have a number of captures 'up your sleeve' to be used whenever you need a delaying tactic. Forcing a trade in Checkers can be done by pushing a chip forward, which the opponent then captures, after which you can capture him back. I have no idea how common it is that you can do this. Anyway, it consumes 3 ply rather than 2. But perhaps your normal search would extend the captures anyway, so in fact you would not be delaying anything at all. And when you woud need a null-move search of the same depth to recognize the same threats as you could resolve in the real search, searching the null move doesn't buy you anything, and would just be a waste of time.

[Rein Halbersma]

In chess, Zugzwang positions typically occur when the long-ranged pieces have been eliminated. The opening and middle game in chess is very much like a Blitzkrieg style of game. An extra tempo will usually capture material and the null move is effective in showing such threats cheaply.

Checkers on the other hand is a more static game in the opening / middle game, and Zugzwangs can occur especially in closed positions. In open positions and in the endgame with long-ranged kings (such as in your Portugese/Spanish game example), I wouldn't expect much Zugzwangs.

In any case, if you do use null moves in checkers, then I would recommend using the double null move idea of Vincent Diepeveen. This means allowing two but not three consecutive null moves. This will quickly show if a position is a Zugzwang. Whether using null moves is a net win in checkers is something to be tested.

[hgm]

I always assumed that when people say null-move does not work in Checkers, they mean that verified null-move does not work. Because verification is such an obvious solution to the problem of zugzwang (which equally obviously is so important in Checkers) that I cannot imagine people would have stopped testing just because unverified null move would not work (and cannot be expected to work).

[Rein Halbersma]

I always assumed that when people say null-move does not work in Checkers, they mean that verified null-move does not work. Because verification is such an obvious solution to the problem of zugzwang (which equally obviously is so important in Checkers) that I cannot imagine people would have stopped testing just because unverified null move would not work (and cannot be expected to work).

The subtlety with Zugzwang in checkers is not that you cannot do null moves or that you cannot do verification with double null moves at all. In most positions you can. The big exception is that you cannot legally do a null move in positions where you have to capture yourself and that you cannot *safely* do a null move in positions in which your opponent is threatening a capture. Since a double null move is not allowed in this case (captures are obligatory in checkers), Zugzwangs can go undetected.

One way out in threatened capture positions might be to do a reduced search with depth - 2 R (i.e. double null move reduction) with no immediate null move allowed as a form of internal iterative deepening. If the reduced search fails high, this means that you have at least one move that you can use to let your opponent capture after which you presumably can recapture enough for the fail high to occur. In such cases, you can then prune as usual without having to worry about Zugzwang.