Null-move heuristic

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.

Contents

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, however, 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 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.

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.

See also


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Null move — In game theory, a null move is a decision by a player to pass (that is, not to make a move) when it is their turn to move. Even though null moves are against the rules of many games, they are often useful to consider when analyzing these games.… …   Wikipedia

  • Computer chess — 1990s Pressure sensory chess computer with LCD screen Chess+ For the iPad …   Wikipedia

  • Rybka — Infobox Software name=Rybka caption= developer=Vasik Rajlich latest release version=3 latest release date=August 6, 2008cite web | url=http://rybkachess.com/index.php?auswahl=Release+notes | title=Rybka 3 Release Notes | date=August 6,2008 |… …   Wikipedia

  • Эвристика нулевого хода — См. также: Компьютерные шахматы В компьютерных шахматах, эвристика нулевого хода  метод увеличения скорости алгоритма альфа бета отсечения. Альфа бета отсечение ускоряет выполнение минимаксного алгоритма, распознавая точки отсечения… …   Википедия

  • Zugzwang — For the musical work written by Juan Maria Solare, see Zugzwang (musical work). Not to be confused with zwischenzug. Zugzwang (German for compulsion to move , pronounced [ˈtsuːktsvaŋ]) is a term usually used in chess which also applies to various …   Wikipedia

  • Outline of chess — A game of chess, in the starting position. See also: Glossary of chess and Index of chess articles The following outline is provided as an overview of and topical guide to chess: Chess – two player board game played on a chessboard, a square …   Wikipedia

  • List of game topics — The list of game topics aims to list articles related to games.#8 bit era 16 bit era 32 bit and 64 bit era 128 bit eraAAbalone (board game) Abandonware Abstract strategy game Acquire Advanced Dungeons Dragons Advanced Squad Leader Adventure game… …   Wikipedia

  • Index of chess articles — Contents 1 Books 2 General articles 2.1 0–9 2.2 A …   Wikipedia

  • Kaissa — ( ru. Каисса) was a chess program developed in Soviet Union in the 1960s. It was named so after the chess goddess Caissa. Kaissa became the first world computer chess champion in 1974 in Stockholm. History Chess diagram|= tright Duchess ndash;… …   Wikipedia

  • Hydra (chess) — Hydra is a chess machine, designed by a team with Dr. Christian Chrilly Donninger, Dr. Ulf Lorenz, GM Christopher Lutz and Muhammad Nasir Ali. Since 2006 the development team consists only of Donninger and Lutz. Hydra is under the patronage of… …   Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.