Changes

Jump to: navigation, search

Killer Heuristic

10,871 bytes added, 10:14, 30 April 2018
Created page with "'''Home * Search * Move Ordering * Killer Heuristic''' FILE:JacktheRipper1888.jpg|border|right|thumb|Jack the Ripper <ref>One of a series of images fr..."
'''[[Main Page|Home]] * [[Search]] * [[Move Ordering]] * Killer Heuristic'''

[[FILE:JacktheRipper1888.jpg|border|right|thumb|Jack the Ripper <ref>One of a series of images from the [https://en.wikipedia.org/wiki/The_Illustrated_London_News 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", [https://en.wikipedia.org/wiki/Jack_the_Ripper Jack the Ripper from Wikipedia], [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons]</ref> ]]

'''Killer Heuristic''',<br/>
a dynamic, path-dependent move ordering technique. It considers moves that caused a [[Beta-Cutoff|beta-cutoff]] in a [[Sibling Node|sibling node]] as [[Killer Move|killer moves]] and orders them high on the [[Move List#SearchLists|list]]. When a [[Node|node]] [[Fail-High|fails high]], a [[Quiet Moves|quiet move]] that caused a cutoff is stored in a table indexed by [[Ply|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|hash move]] and (good) [[Captures|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|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=
* [[Butterfly Heuristic]]
* [[Countermove Heuristic]]
* [[Fixafan]]
* [[History Heuristic]]
* [[Killer Move]]
* [[Last Best Reply]]
* [[Mate Killers]]
* [[Refutation Table]]
* [[Relative History Heuristic]]
* [[Vice#KillHist|Vice Video]]

=Publications=
* [[Barbara Liskov|Barbara J. Huberman]] ('''1968'''). ''A Program to Play Chess End Games''. Technical Report no. CS-106, Ph.D. thesis. [[Stanford University]], Computer Science Department <ref>[[Jos Uiterwijk]] ('''1992'''). ''The Countermove Heuristic''. [[ICGA Journal#15_1|ICCA Journal, Vol. 15, No. 1]], pp. 8, The killer heuristic</ref>
* [[James Gillogly]] ('''1971'''). ''[http://oai.dtic.mil/oai/oai?verb=getRecord&metadataPrefix=html&identifier=AD0736043 The Technology Chess Program]''. [[Carnegie Mellon University]], CS-71-109, [http://repository.cmu.edu/cgi/viewcontent.cgi?article=2974&context=compsci 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'''). ''[https://pure.uvt.nl/portal/en/publications/de-killerheuristiek%28945033e5-8d1f-4339-bb92-e67c79cb33d5%29.html De Killer-Heuristiek]''. [[Computerschaak]], Vol. 2, No. 3 (Dutch)
* [[Jos Uiterwijk]] ('''1992'''). ''The Countermove Heuristic''. [[ICGA Journal#15_1|ICCA Journal, Vol. 15, No. 1]], pp. 8, The killer heuristic
* [[Eric Thé]] ('''1992'''). ''[http://digitool.library.mcgill.ca/R/?func=dbin-jump-full&object_id=56753&local_base=GEN01-MCG02 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'''). ''[https://www.researchgate.net/publication/258121764_Context_Killer_Heuristic_and_Its_Application_to_Computer_Shogi Context Killer Heuristic and Its Application to Computer Shogi]''. [[CGW 2007]]

=Forum Posts=
==1995 ...==
* [http://groups.google.com/group/gnu.chess/browse_frm/thread/fb62cff6dea1bf09 Killer moves] by [[Chua Kong Sian]], [[GNU Chess#NewsGroup|gnu.chess]], March 21, 1995
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/8e5154fc75bea926 Unusual killer heuristic behavior] by [[Matt Craighead]], [[Computer Chess Forums|rgcc]], September 10, 1995
* [https://www.stmintz.com/ccc/index.php?id=21072 Killer and history] by [[Jan Willem de Kort]], [[CCC]], June 22, 1998
* [https://www.stmintz.com/ccc/index.php?id=54116 Killer Move Heuristic Questions] by [[William Bryant]], [[CCC]], June 03, 1999
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=113078 What is the Success Rate of Killer/History Moves?] by [[Roberto Waldteufel]], [[CCC]], May 31, 2000
* [https://www.stmintz.com/ccc/index.php?id=143331 About history heuristics, killers and my futil. pruning code] by [[Severi Salminen]], [[CCC]], December 06, 2000 » [[History Heuristic]]
* [https://www.stmintz.com/ccc/index.php?id=179391 MTD(f) and killer heuristics] by Marcus Heidkamp, [[CCC]], July 12, 2001 » [[MTD(f)]]
* [https://www.stmintz.com/ccc/index.php?id=278991 killers and history] by [[Nathan Thom]], [[CCC]], January 22, 2003 » [[History Heuristic]]
* [https://www.stmintz.com/ccc/index.php?id=306149 Killer Moves] by Rick Bischoff, [[CCC]], July 12, 2003
* [https://www.stmintz.com/ccc/index.php?id=325602 killer moves?] by [[Daniel Shawul]], [[CCC]], November 04, 2003
* [https://www.stmintz.com/ccc/index.php?id=357334 Two questions: Bratko Kopec and variations on the killer heuristic] by [[Artem Petakov|Artem Pyatakov]], [[CCC]], March 31, 2004 » [[Bratko-Kopec Test]]
* [https://www.stmintz.com/ccc/index.php?id=357640 Killer modifications reduced tree size by 8% (with identical results)] by [[Artem Petakov|Artem Pyatakov]], [[CCC]], March 31, 2004
* [https://www.stmintz.com/ccc/index.php?id=389695 The Null Move Killer] by [[Stuart Cracraft]], [[CCC]], September 29, 2004
==2005 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=20068 Killer Moves] by colin, [[CCC]], March 09, 2008
* [http://www.talkchess.com/forum/viewtopic.php?t=24920 killer moves and history heuristic table] by [[Stuart Cracraft]], [[CCC]], November 17, 2008 » [[History Heuristic]]
* [http://www.talkchess.com/forum/viewtopic.php?t=27315 Killer Curiosity] by [[Harm Geert Muller]], [[CCC]], April 04, 2009
* [http://www.talkchess.com/forum/viewtopic.php?t=29077 Killer moves (ply or depth?)] by [[Vlad Stamate]], [[CCC]], July 22, 2009
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=35045 Killer moves with null move pruning] by Ricardo Barreira, [[CCC]], June 19, 2010
* [http://www.talkchess.com/forum/viewtopic.php?t=40423 Killer moves?] by Mike Robinson, [[CCC]], September 16, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=46886 Killer and History: Increased Node Count] by [[Cheney Nattress]], [[CCC]], January 15, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=53289 Killer and move encoding] by [[Fabio Gobbato]], [[CCC]], August 14, 2014 » [[Encoding Moves]]
* [http://www.talkchess.com/forum/viewtopic.php?t=53317 Effectiveness of killer moves] by [[Alex Ferguson]], [[CCC]], August 17, 2014
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=55438 killer trees] by [[Harm Geert Muller]], [[CCC]], February 23, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=56540 Killer moves based on distance to common ancestor] by [[Matthew Lai]], [[CCC]], May 30, 2015
'''2016'''
* [http://www.talkchess.com/forum/viewtopic.php?t=61076 Killer Table between searches?] by [[William Bryant]], [[CCC]], August 08, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=61260 New killer idea] by [[Alexandru Mosoi]], [[CCC]], August 28, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=61399 Killer heuristic] by [[Harm Geert Muller]], [[CCC]], September 11, 2016
'''2017'''
* [http://www.open-chess.org/viewtopic.php?f=5&t=3077 Mate Killer Move] by thevinenator, [[Computer Chess Forums|OpenChess Forum]], February 02, 2017 » [[Mate Killers]]
* [http://www.talkchess.com/forum/viewtopic.php?t=63090 TTMove legality checking ? & Killers Move Format?] by [[Mahmoud Uthman]], [[CCC]], February 08, 2017 » [[Hash Move]], [[Killer Move]]
* [http://www.talkchess.com/forum/viewtopic.php?t=63756 Early killer] by [[Harm Geert Muller]], [[CCC]], April 16, 2017
* [http://www.talkchess.com/forum/viewtopic.php?t=64925 Deep killers] by [[Harm Geert Muller]], [[CCC]], August 18, 2017
* [http://www.talkchess.com/forum/viewtopic.php?t=65169 LMR and killer] by [[Harm Geert Muller]], [[CCC]], September 14, 2017 » [[Late Move Reductions]]

=External Links=
* [https://en.wikipedia.org/wiki/Killer_heuristic Killer heuristic from Wikipedia]
* [https://en.wikipedia.org/wiki/Killer Killer from Wikipedia]
* [https://en.wikipedia.org/wiki/Foolkiller Foolkiller from Wikipedia]
* [[Videos#BrianAuger|Brian Auger]] and the [https://en.wikipedia.org/wiki/Brian_Auger_and_the_Trinity Trinity] - [https://www.youtube.com/watch?v=QD7buurf5FM Fool Killer] ([https://en.wikipedia.org/wiki/Mose_Allison Mose Allison] <ref>[http://www.green-brain-krautrock.de/BRIAN-AUGER-und-THE-TRINITY-und-JULIE-DRISCOLL-The-Mod-years-CD-MadeInGermany_17962.html Brian Auger-und-The-Trinity-und-Julie-Driscoll The-Mod-years]</ref>), 1965, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=QD7buurf5FM|alignment=left|valignment=top}}
* [https://en.wikipedia.org/wiki/Talking_Heads Talking Heads] - [https://en.wikipedia.org/wiki/Psycho_Killer Psycho Killer], [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=O52jAYa4Pm8|alignment=left|valignment=top}}

=References=
<references />

'''[[Move Ordering|Up one Level]]'''

Navigation menu