|
The All-Important Null-Move
One of the most effective ways to speed up a chess program is to introduce the concept of a null move into the equation.
The null move consists, quite simply, of skipping a turn and letting the opponent play two moves in a row. In the overwhelming majority of positions, doing nothing is a bone-head idea: you should (almost) always be able to do *something* to improve your lot. (To be honest, there are a few "damned if I do, damned if I don't" positions where the null move would actually be your best bet, and the computer will not play them correctly, but such "zugzwang" positions are hopeless anyway, so the loss of performance is not very traumatic.)
Allowing the computer to try a null move during search has several advantages related to speed and accuracy. For example:
- Suppose that a position is so overwhelmingly in your favor that, even if you skipped your turn, the opponent couldn't respond with anything that would help. (In program terms, you would get a beta cutoff even without making a move.) Suppose further that this position is scheduled to be searched to depth N. The null move, in effect, takes out an entire ply of the search tree (you are searching only the null move instead of all your legal ones) and if your branching factor is B, searching the null move is equivalent to looking at a single depth N-1 subtree instead of B of them. With B=35 as in the typical chess middlegame, null-move search may only consume 3% of the resources required by a full depth-N examination. If the null move search reveals that you are still too strong even without playing (i.e., it creates a cutoff), you have saved 97% of your effort; if not, you must examine your own legal moves as usual, and have only wasted an extra 3%. On average, the gain is enormous.
- Now, suppose that, during quiescence search, you reach a position where your only legal capture is rook-takes-pawn, which is immediately followed by the opponent's knight-takes-rook. You'd be a lot better off not making the capture, and playing any other non-capture move, right? You can simulate this situation by inserting the null move into the quiescence search: if, in a given position during quiescence search, it is revealed that the null move is better than any capture, you can assume that continuing with captures from this position is a bad idea, and that since the best move is a quiet one, this is a position where the evaluation function itself should be applied!
Overall, the null-move heuristic can save between 20% and 75% of the effort required by a given search. Well worth the effort, especially when you consider that adding it to a program is a simple matter of changing the "side to play" flag and adding less than a dozen lines of code in the quiescence search algorithm!
|
Unite 2010
