Killer heuristic

Killer heuristic

In competitive two-player games, the killer heuristic is a technique for improving the efficiency of alpha-beta pruning, which in turn improves the efficiency of the minimax algorithm. This algorithm has an exponential search time to find the optimal next move, so general methods for speeding it up are very useful.

Alpha-beta pruning works best when the best moves are considered first. This is because the best moves are the ones most likely to produce a "cutoff", a condition where the game playing program probably knows that the position it is presently considering could not possibly have resulted from best play by both sides and so need not be considered further.

The killer heuristic attempts to produce a cutoff by assuming that a move that produced a cutoff in another branch of the game tree at the same depth is likely to produce a cutoff in the present position, that is to say that a move that was a very good move from a different (but possibly similar) position might also be a good move in the present position. By trying the "killer move" before other moves, a game playing program can often produce an early cutoff, saving itself the effort of considering or even generating all legal moves from a position.

In practical implementation, game playing programs frequently keep track of two killer moves for each depth of the game tree and see if either of these moves, if legal, produces a cutoff before the program generates and considers the rest of the possible moves. If a non-killer move produces a cutoff, it replaces one of the two killer moves at its depth.

A generalization of the killer heuristic is the "history heuristic". The history heuristic can be implemented as a table that is indexed by some characteristic of the move, for example "from" and "to" squares or piece moving and the "to" square. When there is a cutoff, the appropriate entry in the table is incremented, such as by adding "d²" or "2d" where "d" is the current search depth. This information is used when ordering moves.

References

Informed Search in Complex Games by Mark Winands, http://www.cs.unimaas.nl/m.winands/documents/informed_search.pdf


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Alpha-beta pruning — is a search algorithm which seeks to reduce the number of nodes that are evaluated in the search tree by the minimax algorithm. It is a search with adversary algorithm used commonly for machine playing of two player games (Tic tac toe, Chess, Go …   Wikipedia

  • Mizar chess engine — Mizar Developer(s) Nicola Rizzuti Stable release 3.0 / May 16, 2006 Written in C Operating system Windows …   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

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

  • Iterative deepening depth-first search — Graph and tree search algorithms Alpha beta pruning A* B* Beam Bellman–Ford algorithm Best first Bidirectional …   Wikipedia

  • Antivirus software — Antivirus redirects here. For antiviral medication, see Antiviral drug. Antivirus or anti virus software is used to prevent, detect, and remove malware, including but not limited to computer viruses, computer worm, trojan horses, spyware and… …   Wikipedia

  • Offender profiling — Offender profiling, also known as criminal profiling, is a behavioral and investigative tool that is intended to help investigators to profile unknown criminal subjects or offenders. Offender profiling is also known as criminal profiling,… …   Wikipedia

  • Vertebral subluxation — is a chiropractic term that is used to describe a myriad of signs and symptoms (syndrome) thought to occur as a result of a misaligned or dysfunctional spinal segment. The chiropractic subluxation complex is a functional biomechanical spinal… …   Wikipedia

  • ChessV — Capablanca Chess in ChessV Developer(s) Gr …   Wikipedia

  • List of ships in the Matrix series — This article is about the hovercraft ships shown in the fictional universe of The Matrix series of science fiction films, comic books and video games. The Animatrix short film The Second Renaissance depicts the war between men and machines which… …   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.