NULL moves for beginners

[mike_bike_kite]

I added null moves to my program. Before trying any moves it evaluates the board position and sees if there an alpha beta cut off - if there is then it just doesn't bother going down that part of the tree. It seems to work but when it gets to end games (where it's loosing) then it sees any move as bad. The end effect is it plays poorly when it sees itself loosing material etc.

What am I doing wrong?

[tvrzsky]

I added null moves to my program. Before trying any moves it evaluates the board position and sees if there an alpha beta cut off - if there is then it just doesn't bother going down that part of the tree. It seems to work but when it gets to end games (where it's loosing) then it sees any move as bad. The end effect is it plays poorly when it sees itself loosing material etc.

What am I doing wrong?

Well, If I understand right your description then I am afraid the answer is: everything.
Does your "null move" really mean just static evaluation of current position and possible immediate return to parent node? Then it is rather something called "stand pat", but unlike of usual null move this is done only in quiescence search.
Common implementation of null move means that you transfer your turn to opponent and search with reduced depth.

[Desperado]

Hi Mike,

it sounds that you are Standing Pat within the normal Search. The technique is used
only in quiescence search.

Both techniques are based on the Null Move Observation but work differently.

The nullmove within the tree is normally handled as special move, which
updates the board state and the color to move next. Then it follows
a shallow (reduced depth) search. If the result of the reduced search
is a fail high (beta cut), we can return the result without going to full depth. This can be used as recursive technique like:

eg: 1. e4 - nullmove 2. d4 - nullmove 3. ...

So every nullmove reduces the search depth.

Restrictions are incheck situations, where the king could be captured of
course if a nullmove would be done, and 2 consecutive nullmoves in
a row doesnt make much sense too.

A more detailed explanation you can find here Nullmove Pruning

Michael

[hgm]

Null-move pruning is based on the observation that when you pass your turn, and the opponent cannot hurt you (enough) in N ply, you can in general use your turn to delay whatever he has lurking just behind the horizon by a ply or two. (E.g. by trading a heavy piece he must recapture, or by attacking a heavy piece he must move away. Or by preemptively thwarting his plan of attack, so that he needs to muster more force to complete it.)

So if you must search N ply, but after a null move searched to N-2 ply you don't see any trouble, (i.e.after letting him start and search N-3 ply), you will not see that trouble in the N-ply search that starts with your move either. So you might as well not do this pointles search, and leave it at the 2-ply cheaper null-move search.

[IanO]

It seems to work but when it gets to end games (where it's loosing) then it sees any move as bad. The end effect is it plays poorly when it sees itself loosing material etc.

What am I doing wrong?

Many programs also turn off null moves in the endgame and other situations where there might be zugzwang.

[mike_bike_kite]

What am I doing wrong?

I am afraid the answer is: everything.

Damn, damn and triple damn!
Back to the drawing board...

[Evert]

I find it useful to conceptually think about null moves as follows: assume that in the current position, there exists a move that does not fundamentally change the position for better or worse. A "waiting" move. If, after a waiting move, the opponent has no threat or good enough defence (ie, the position scores > beta), then the waiting move causes a cut-off and we simply return the fail-high.
How to pick the waiting move? If this has to come from the set of legal moves, you'll need some very complicated heuristics and safe-guards to find it, and even then you may get it wrong and fail. But since the waiting move is arbitrary and shouldn't really change the position, you can actually just pass your turn instead (you do this over the board all the time while thinking: what would my opponent play if it were his turn now? What can I do to stop him?). This is what the null-move heuristic basically is. By playing a null-move, you also safe the cost of generating moves in situations where the null move fails high.

This goes badly wrong in positions where no waiting move exists though (zugzwang positions), and you have to recognise when that might be the case and avoid the null move.
I have no idea (not having tried it), but it may still be beneficial to do the null move search to detect immediate threats that have to be countered. I suspect the benefits do not outweigh the cost of the null-move search (even a shallow one), but the idea is obvious and someone probably tried it and can report the results.