Null-move heuristic
Encyclopedia
In computer chess
programs, the null-move heuristic is a heuristic technique used to enhance the speed of the alpha-beta pruning
algorithm
.
speeds the minimax algorithm by identifying cutoffs, points in the game tree
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
) 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.
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.
(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 it may in fact be very bad for.
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
Computer chess
Computer chess is computer architecture encompassing hardware and software capable of playing chess autonomously without human guidance. Computer chess acts as solo entertainment , as aids to chess analysis, for computer chess competitions, and as research to provide insights into human...
programs, the null-move heuristic is a heuristic technique used to enhance the speed of the alpha-beta pruning
Alpha-beta pruning
Alpha-beta pruning is a search algorithm which seeks to decrease the number of nodes that are evaluated by the minimax algorithm in its search tree. It is an adversarial search algorithm used commonly for machine playing of two-player games...
algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
.
Rationale
Alpha-beta pruningAlpha-beta pruning
Alpha-beta pruning is a search algorithm which seeks to decrease the number of nodes that are evaluated by the minimax algorithm in its search tree. It is an adversarial search algorithm used commonly for machine playing of two-player games...
speeds the minimax algorithm by identifying cutoffs, points in the game tree
Game tree
In game theory, a game tree is a directed graph whose nodes are positions in a game and whose edges are moves. The complete game tree for a game is the game tree starting at the initial position and containing all possible moves from each position; the complete tree is the same tree as that...
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
Chess is a two-player board game played on a chessboard, a square-checkered board with 64 squares arranged in an eight-by-eight grid. It is one of the world's most popular games, played by millions of people worldwide at home, in clubs, online, by correspondence, and in tournaments.Each player...
) 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
Ply (game theory)
In two-player sequential games, a ply refers to one turn taken by one of the players. The word is used to clarify what is meant when one might otherwise say "turn"....
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, however, a class of chess positions where employing the null-move heuristic can result in severe tactical blunders. In these zugzwangZugzwang
Zugzwang is a term usually used in chess which also applies to various other games. The term finds its formal definition in combinatorial game theory, and it describes a situation where one player is put at a disadvantage because he has to make a move when he would prefer to pass and make no 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 it may in fact be very bad for.
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.