Killer Heuristic

From Chessprogramming wiki
Jump to: navigation, search

Home * Search * Move Ordering * Killer Heuristic

Jack the Ripper [1]

Killer Heuristic,
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 quiet move that caused a cutoff is stored in a table indexed by ply, typically containing two or three moves per ply. The replacement scheme ought to ensure that all the available slots contain different moves.

Priority

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 ...

2005 ...

2010 ...

2015 ...

2016

2017

2018 ...

2020 ...

External Links

References

  1. ↑ One of a series of images from the Illustrated London News for October 13, 1888 carrying the overall caption, "With the Vigilance Committee in the East End". This specific image is entitled "A Suspicious Character", Jack the Ripper from Wikipedia, Wikimedia Commons
  2. ↑ Jos Uiterwijk (1992). The Countermove Heuristic. ICCA Journal, Vol. 15, No. 1, pp. 8, The killer heuristic
  3. ↑ Brian Auger-und-The-Trinity-und-Julie-Driscoll The-Mod-years

Up one Level

Retrieved from "https://www.chessprogramming.org/index.php?title=Killer_Heuristic&oldid=25591"