Lesson plan
Killer heuristic
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. 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.…
Article summary
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. 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.…
Key claims
No claims recorded.
Discussion questions
- Summarise the article in your own words. Which single claim would you verify first, and why?
- Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
- If two sources disagreed about one of these facts, what would you need in order to trust one over the other?
Bibliography
No sources recorded.
Key claims and bibliography are generated from the same tracked claims and sources as the article page.