Killer Heuristic

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.

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#

• Butterfly Heuristic
• Countermove Heuristic
• Fixafan
• History Heuristic
• Killer Move
• Last Best Reply
• Mate Killers
• Refutation Table
• Relative History Heuristic
• Vice Video

Publications#

• Barbara J. Huberman (1968). A Program to Play Chess End Games. Technical Report no. CS-106, Ph.D. thesis. Stanford University, Computer Science Department [2]
• James Gillogly (1971). The Technology Chess Program. Carnegie Mellon University, CS-71-109, pdf
• Selim Akl, Monroe Newborn (1977). The Principal Continuation and the Killer Heuristic. 1977 ACM Annual Conference Proceedings, pp. 466-473. ACM, Seattle, WA.
• Jaap van den Herik, Jan Derksen, John Huisman (1982). De Killer-Heuristiek. Computerschaak, Vol. 2, No. 3 (Dutch)
• Jos Uiterwijk (1992). The Countermove Heuristic. ICCA Journal, Vol. 15, No. 1, pp. 8, The killer heuristic
• Eric Thé (1992). An analysis of move ordering on the efficiency of alpha-beta search. Master’s thesis, McGill University, advisor Monroe Newborn » Fixafan
• Junichi Hashimoto, Tsuyoshi Hashimoto, Hiroyuki Iida (2007). Context Killer Heuristic and Its Application to Computer Shogi. CGW 2007

Forum Posts#

1995 …#

• Killer moves by Chua Kong Sian, gnu.chess, March 21, 1995
• Unusual killer heuristic behavior by Matt Craighead, rgcc, September 10, 1995 » Morgoth
• Killer and history by Jan Willem de Kort, CCC, June 22, 1998
• Killer Move Heuristic Questions by William Bryant, CCC, June 03, 1999

2000 …#

• What is the Success Rate of Killer/History Moves? by Roberto Waldteufel, CCC, May 31, 2000
• About history heuristics, killers and my futil. pruning code by Severi Salminen, CCC, December 06, 2000 » History Heuristic
• MTD(f) and killer heuristics by Marcus Heidkamp, CCC, July 12, 2001 » MTD(f)
• killers and history by Nathan Thom, CCC, January 22, 2003 » History Heuristic
• Killer Moves by Rick Bischoff, CCC, July 12, 2003
• killer moves? by Daniel Shawul, CCC, November 04, 2003
• Two questions: Bratko Kopec and variations on the killer heuristic by Artem Pyatakov, CCC, March 31, 2004 » Bratko-Kopec Test
• Killer modifications reduced tree size by 8% (with identical results) by Artem Pyatakov, CCC, March 31, 2004
• The Null Move Killer by Stuart Cracraft, CCC, September 29, 2004

2005 …#

• Killer Moves by colin, CCC, March 09, 2008
• killer moves and history heuristic table by Stuart Cracraft, CCC, November 17, 2008 » History Heuristic
• Killer Curiosity by Harm Geert Muller, CCC, April 04, 2009
• Killer moves (ply or depth?) by Vlad Stamate, CCC, July 22, 2009

2010 …#

• Killer moves with null move pruning by Ricardo Barreira, CCC, June 19, 2010
• Killer moves? by Mike Robinson, CCC, September 16, 2011
• Killer and History: Increased Node Count by Cheney Nattress, CCC, January 15, 2013
• Killer and move encoding by Fabio Gobbato, CCC, August 14, 2014 » Encoding Moves
• Effectiveness of killer moves by Alex Ferguson, CCC, August 17, 2014

2015 …#

• killer trees by Harm Geert Muller, CCC, February 23, 2015
• Killer moves based on distance to common ancestor by Matthew Lai, CCC, May 30, 2015

2016

• Killer Table between searches? by William Bryant, CCC, August 08, 2016
• New killer idea by Alexandru Mosoi, CCC, August 28, 2016
• Killer heuristic by Harm Geert Muller, CCC, September 11, 2016

2017

• Mate Killer Move by thevinenator, OpenChess Forum, February 02, 2017 » Mate Killers
• TTMove legality checking ? & Killers Move Format? by Mahmoud Uthman, CCC, February 08, 2017 » Hash Move, Killer Move
• Early killer by Harm Geert Muller, CCC, April 16, 2017
• Deep killers by Harm Geert Muller, CCC, August 18, 2017
• LMR and killer by Harm Geert Muller, CCC, September 14, 2017 » Late Move Reductions

2018 …

• Saving killer moves… by Vince Sempronio, CCC, April 25, 2018
• Killers and forward pruning test searches by Alvaro Cardoso, CCC, January 27, 2019

2020 …#

• How much ELO should I expect to gain from killer moves? by Christian Dean, CCC, July 16, 2021 » Playing Strength

External Links#

• Killer heuristic from Wikipedia

• Killer from Wikipedia

• Foolkiller from Wikipedia

• Brian Auger and the Trinity - Fool Killer ( Mose Allison [3]), 1965, YouTube Video

• Talking Heads - Psycho Killer, YouTube Video

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