|
|
|
|
|
Killer HeuristicIn computer chess, the killer heuristic is a technique for improving the efficiency of alpha-beta pruning. 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 computer chess 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 computer chess 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, computer chess 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. Programs maintain a table indexed by the "from" and "to" squares. When there is a cutoff, the appropriate entry in the table is incremented, such as by adding d2 or 2d where d is the current search depth. This information is used when ordering moves. There appears to be little consensus in the computer chess community about whether the killer heuristic, the history heuristic, or a combination of the two is most effective.
|
 |
|
| Copyright 2005-2009 OnPedia.com. All Rights Reserved |
|
|