This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Killer heuristic" – news · newspapers · books · scholar · JSTOR(April 2018) (Learn how and when to remove this message)
In competitive two-player games, the killer heuristic is a move-ordering method based on the observation that a strong move or small set of such moves in a particular position may be equally strong in similar positions at the same move (ply) in the game tree.
Retaining such moves obviates the effort of rediscovering them in sibling nodes.
This technique improves the efficiency of alpha–beta pruning, which in turn improves the efficiency of the minimax algorithm.[1] 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 knows that the position it is considering could not possibly have resulted from best play by both sides and so need not be considered further. I.e. the game-playing program will always make its best available move for each position. It only needs to consider the other player's possible responses to that best move, and can skip evaluation of responses to (worse) moves it will not make.
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 (greater than depth of 1) 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. This idea can be generalized into a set of refutation tables.
A generalization of the killer heuristic is the history heuristic.[2] 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. Beyond an incremental depth of about 2, history information rapidly degenerates into "noise".
^Huberman (Liskov), Barbara Jane (1968). "A program to play chess end games" (PDF). Stanford University Department of Computer Science, Technical Report CS 106, Stanford Artificial Intelligence Project Memo AI-65. Archived from the original (PDF) on September 5, 2020. {{cite journal}}: Cite journal requires |journal= (help)
^The History Heuristic and Alpha-Beta Search Enhancements in Practice, Jonathan Schaeffer
In competitive two-player games, the killerheuristic is a move-ordering method based on the observation that a strong move or small set of such moves...
program to play chess endgames for which she developed the important killerheuristic. After graduating from Stanford, Liskov returned to Mitre to work as...
plies. See iterative deepening depth-first search. killerheuristic Assumption that a move (the killer move) that caused a search cutoff in another branch...
However, the kind of heuristic used by early AV engines was totally different from those used today. The first product with a heuristic engine resembling...
change. These include the heuristic-systematic model of information processing and the elaboration likelihood model. The heuristic-systematic model of information...
principle – Hypothesis about sapient life and the universe Availability heuristic – Bias towards recently acquired information Cherry picking – Fallacy...
possible state. The policy could be calculated (e.g., by iteration), be heuristic, or it can be learned. Game theory describes the rational behavior of...
China. In this sense Cuffe proposes the Grass Mud Horse trickster as 'a heuristic cultural function to aid the perceiver to re-evaluate their own experiential...
Reid, Hayley; Crabb, Michael (27 April 2018). "Meeple Centred Design: A Heuristic Toolkit for Evaluating the Accessibility of Tabletop Games". The Computer...
called this the "positive test strategy". This strategy is an example of a heuristic: a reasoning shortcut that is imperfect but easy to compute. Klayman and...
of the hindsight bias; these were the availability heuristic and the representativeness heuristic. In an elaboration of these heuristics, Beyth and Fischhoff...
Metropolis, and the 1920 play R.U.R. A later 20th century approach he names "heuristic hardware", giving as instances 2001 a Space Odyssey, Do Androids Dream...
support multiple processors. It also includes negascout search, the killer move heuristic, static exchange evaluation, quiescence search, alpha-beta pruning...
Tversky attempted to explain this finding in terms of a simple rule or "heuristic" called representativeness. They argued that many judgments relating to...
Retrieved July 5, 2017. Suarez, Kelly-Anne (March 31, 2006). "Model's Killer Gets Life Sentence". Los Angeles Times. Retrieved July 5, 2017. Greenberg...
of quantum logic gates and no measurements. Quantum parallelism is the heuristic that quantum computers can be thought of as evaluating a function for...
of science... Subluxations, genes, gravity, the ego and life are all heuristic devices, "useful fictions" that are used to explain phenomenon that are...
Rohloff, A.; Wright, S. (2010). "Moral Panic and Social Theory: Beyond the Heuristic". Current Sociology. 58 (3): 403. CiteSeerX 10.1.1.427.24. doi:10.1177/0011392110364039...
shooter Columbine effect Copycat crime Mass murder School shooting Spree killer Murray, Jennifer (January 2017). "Mass Media Reporting and Enabling of Mass...
(March 2010). From Web 1.0 to Web 2.0 and beyond: Reviewing usability heuristic criteria taking music sites as case studies. IndiaHCI Conference. Mumbai...
utilize different strategies than humans to choose their moves: they use heuristic methods to build, search and evaluate trees representing sequences of...
Global Information