Null-move heuristic

In computer chess programs, the null-move heuristic is a heuristic technique used to enhance the speed of the alpha-beta pruning algorithm.

Rationale

Alpha-beta pruning 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.

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 (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.[1] 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.

gollark: Otherwise something like `SELECT *, (SELECT * FROM posts WHERE thread = threads.id ORDER BY created DESC) FROM threads` I think.
gollark: Well, I might go for putting a `newest_post_id` field in thread.
gollark: Maybe discord were BEES and rate limited it? I hope not.
gollark: It changed just now.
gollark: I sometimes deliberately avoid trailing newlines, for purposes.

References
  1. David-Tabibi, Omid; Netanyahu, Nathan S. (September 2002). "Verified Null-Move Pruning". ICGA Journal. 25 (3): 153–161. arXiv:0808.1125. Bibcode:2008arXiv0808.1125D.
  • Goetsch, G.; Campbell, M. S. (1990). "Experiments with the null-move heuristic". In Marsland, T. Anthony; Schaeffer, Jonathan (eds.). Computers, Chess, and Cognition. Springer-Verlag. pp. 159–168. ISBN 3-540-97415-6.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.