Killer heuristic (original) (raw)
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.
| Property | Value |
|---|---|
| dbo:abstract | 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. 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. 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". (en) |
| dbo:wikiPageExternalLink | https://dke.maastrichtuniversity.nl/m.winands/documents/informed_search.pdf |
| dbo:wikiPageID | 173889 (xsd:integer) |
| dbo:wikiPageLength | 3622 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1090999436 (xsd:integer) |
| dbo:wikiPageWikiLink | dbc:Game_artificial_intelligence dbc:Heuristics dbc:Optimization_algorithms_and_methods dbr:Game_tree dbr:Alpha–beta_pruning dbr:Minimax_algorithm dbr:Refutation_table dbr:NegaScout |
| dbp:wikiPageUsesTemplate | dbt:More_citations_needed dbt:Reflist dbt:Short_description |
| dcterms:subject | dbc:Game_artificial_intelligence dbc:Heuristics dbc:Optimization_algorithms_and_methods |
| gold:hypernym | dbr:Technique |
| rdf:type | dbo:TopicalConcept yago:WikicatOptimizationAlgorithmsAndMethods yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Heuristic105847956 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:WikicatHeuristics yago:YagoPermanentlyLocatedEntity yago:Rule105846932 |
| rdfs:comment | 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. (en) |
| rdfs:label | Killer heuristic (en) |
| owl:sameAs | freebase:Killer heuristic yago-res:Killer heuristic wikidata:Killer heuristic https://global.dbpedia.org/id/4pgCY |
| prov:wasDerivedFrom | wikipedia-en:Killer_heuristic?oldid=1090999436&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Killer_heuristic |
| is dbo:wikiPageRedirects of | dbr:Killer_move dbr:Killer_move_heuristic |
| is dbo:wikiPageWikiLink of | dbr:Computer_Arimaa dbr:Crafty dbr:Glossary_of_computer_chess_terms dbr:Computer_chess dbr:Principal_variation_search dbr:Barbara_Liskov dbr:Late_move_reductions dbr:Alpha–beta_pruning dbr:Iterative_deepening_depth-first_search dbr:ChessV dbr:Killer_move dbr:Killer_move_heuristic |
| is foaf:primaryTopic of | wikipedia-en:Killer_heuristic |