Home * Search * Move Ordering * Killer Heuristic

The Killer Heuristic is a dynamic, path-dependent move ordering technique. It considers moves that caused a beta-cutoff in a sibling node as killer moves and orders them high on the list. When a node fails high, a non-capturing move that caused a cutoff is stored in a table indexed by depth, typically containing two or three moves per ply. The replacement scheme ought to ensure that all the available slots contain different moves.

In move ordering, killer moves usually come right after after the hash move and (good) captures. The logic behind this heuristic is as follows. In many positions there is only a small set of moves creating a threat or defending against it, and those that cannot do it might be refuted ("killed") by the same move by the opponent. Apart from the killer moves from the same depth, some programs use killers from two plies ago. Also the mate killers are often separated and treated differently.

As far as relative position of captures and killer moves is concerned, there are different schemes. Sometimes killer moves are sorted below all the captures, sometimes - between equal and losing captures. One rare idea was to place them even before winning captures of a pawn.

How does it work?

Killer moves work on the supposition that most of the moves do not change the situation on the board too much. For example if a program decides that expelling a black bishop from b4 by a move a2-a3 is good, then it is likely to work whatever Black played on the previous move: ...Bd7, ...Be6, ...h6 etc. After the first fail-high caused by a2-a3 this move is remembered as a killer move. So when Black backtracks ...Bd7 and tries ...Be6, move a2-a3, normally having rather low priority, waits to be tried as one of the first in a new, but not-too-different position. Of course, most of the cutoffs come from the first killer slot. But occasionally opponent does something important, like attacking a queen. Program reacts, and has a good luck to fail high again, getting a new killer move... useful only as an evasion. That's where the second slot comes in handy. It prevents a program from forgetting the right plan because of occasional noise caused by switching to more urgent moves.

See also


Publications


Forum Posts

1995 ...

2000 ...

2010 ...


External Links


References

  1. ^ Jos Uiterwijk (1992). The Countermove Heuristic. ICCA Journal, Vol. 15, No. 1, pp. 8, The killer heuristic

What links here?


Up one Level