computer chess Computer chess includes both hardware (dedicated computers) and software capable of playing chess. Computer chess provides opportunities for players to practice even in the absence of human opponents, and also provides opportunities for analysi ...

programs, the null-move heuristic is a

heuristic A heuristic (; ), or heuristic technique, is any approach to problem solving or self-discovery that employs a practical method that is not guaranteed to be optimal, perfect, or rational, but is nevertheless sufficient for reaching an immediate, ...

technique used to enhance the speed of the

alpha-beta pruning Alphabeta is an Israeli musical group. Alphabeta or Alpha Beta may also refer to: *The Greek alphabet, from ''Alpha'' (Αα) and ''Beta'' (Ββ), the first two letters *Alpha Beta, a former chain of Californian supermarkets *Alpha and beta anomers ...

algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...

Rationale

Alpha-beta pruning Alphabeta is an Israeli musical group. Alphabeta or Alpha Beta may also refer to: *The Greek alphabet, from ''Alpha'' (Αα) and ''Beta'' (Ββ), the first two letters *Alpha Beta, a former chain of Californian supermarkets *Alpha and beta anomers ...

speeds the

minimax algorithm Minimax (sometimes MinMax, MM or saddle point) is a decision rule used in artificial intelligence, decision theory, game theory, statistics, and philosophy for ''mini''mizing the possible loss for a worst case (''max''imum loss) scenario. When de ...

by identifying ''cutoffs'', points in the

game tree In the context of Combinatorial game theory, which typically studies sequential games with perfect information, a game tree is a graph representing all possible game states within such a game. Such games include well-known ones such as chess, check ...

where the current position is so good for the side to move that best play by the other side would have avoided it. Since such positions could not have resulted from best play, they and all branches of the game tree stemming from them can be ignored. The faster the program produces cutoffs, the faster the search runs. The null-move heuristic is designed to guess cutoffs with less effort than would otherwise be required, whilst retaining a reasonable level of accuracy. The null-move heuristic is based on the fact that most reasonable chess moves improve the position for the side that played them. So, if the player whose turn it is to move can forfeit the right to move (or make a null move - an illegal action in

chess Chess is a board game for two players, called White and Black, each controlling an army of chess pieces in their color, with the objective to checkmate the opponent's king. It is sometimes called international chess or Western chess to disti ...

) and still have a position strong enough to produce a cutoff, then the current position would almost certainly produce a cutoff if the current player actually moved.

Implementation

In employing the null-move heuristic, the computer program first forfeits the turn of the side whose turn it is to move, and then performs an alpha-beta search on the resulting position to a shallower depth than it would have searched the current position had it not used the null move heuristic. If this shallow search produces a cutoff, it assumes the full-depth search in the absence of a forfeited turn would also have produced a cutoff. Because a shallow search is faster than deeper search, the cutoff is found faster, accelerating the computer chess program. If the shallow search fails to produce a cutoff, then the program must make the full-depth search. This approach makes two assumptions. First, it assumes that the disadvantage of forfeiting one's turn is greater than the disadvantage of performing a shallower search. Provided the shallower search is not too much shallower (in practical implementation, the null-move search is usually 2 or 3 plies shallower than the full search would have been), this is usually true. Second, it assumes that the null-move search will produce a cutoff frequently enough to justify the time spent performing null-move searches instead of full searches. In practice, this is also usually true.

Problems with the null-move heuristic

There are a class of chess positions where employing the null-move heuristic can result in severe tactical blunders. In these ''

zugzwang Zugzwang (German for "compulsion to move", ) is a situation found in chess and other turn-based games wherein one player is put at a disadvantage because of their obligation to make a move; a player is said to be "in zugzwang" when any legal move ...

'' (German for "forced to move") positions, the player whose turn it is to move has only bad moves as their legal choices, and so would actually be better off if allowed to forfeit the right to move. In these positions, the null-move heuristic may produce a cutoff where a full search would not have found one, causing the program to assume the position is very good for a side when it may in fact be very bad for them. To avoid using the null-move heuristic in zugzwang positions, most chess-playing programs that use the null-move heuristic put restrictions on its use. Such restrictions often include not using the null-move heuristic if *the side to move is in check *the side to move has only its king and pawns remaining *the side to move has a small number of pieces remaining *the previous move in the search was also a null move.

Verified null-move pruning

Another heuristic for dealing with the zugzwang problem is Omid David and Nathan Netanyahu's verified null-move pruning. In verified null-move pruning, whenever the shallow null-move search indicates a fail-high, instead of cutting off the search from the current node, the search is continued with reduced depth.

References

*{{citation , last1 = Goetsch , first1 = G. , last2 = Campbell , first2 = M. S. , author2-link = Murray Campbell , editor1-last = Marsland , editor1-first = T. Anthony , editor2-last = Schaeffer , editor2-first = Jonathan , editor2-link = Jonathan Schaeffer , contribution = Experiments with the null-move heuristic , pages = 159–168 , publisher = Springer-Verlag , title = Computers, Chess, and Cognition , year = 1990 , isbn=3-540-97415-6 , mode=cs1 Computer chess Search algorithms Heuristics