Killer heuristic
Encyclopedia
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 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. 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. This information is used when ordering moves.
Alpha-beta pruning
Alpha-beta pruning is a search algorithm which seeks to decrease the number of nodes that are evaluated by the minimax algorithm in its search tree. It is an adversarial search algorithm used commonly for machine playing of two-player games...
, 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
Alpha-beta pruning
Alpha-beta pruning is a search algorithm which seeks to decrease the number of nodes that are evaluated by the minimax algorithm in its search tree. It is an adversarial search algorithm used commonly for machine playing of two-player games...
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 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
Game tree
In game theory, a game tree is a directed graph whose nodes are positions in a game and whose edges are moves. The complete game tree for a game is the game tree starting at the initial position and containing all possible moves from each position; the complete tree is the same tree as that...
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. 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. This information is used when ordering moves.
External links
- Informed Search in Complex Games by Mark Winands, http://www.personeel.unimaas.nl/m-winands/documents/informed_search.pdf