25,161
edits
Changes
Created page with "'''Home * Search * Move Ordering''' For the alpha-beta algorithm to perform well, the best moves need to be searched first. Thi..."
'''[[Main Page|Home]] * [[Search]] * Move Ordering'''
For the [[Alpha-Beta|alpha-beta]] algorithm to perform well, the [[Best Move|best moves]] need to be searched first. This is especially true for [[Node Types#PV|PV-nodes]] and expected [[Node Types#CUT|Cut-nodes]]. The goal is to become close to the minimal tree. On the other hand - at Cut-nodes - the best move is not always the cheapest refutation, see for instance [[Enhanced Transposition Cutoff|enhanced transposition cutoff]]. '''Most''' important inside an [[Iterative Deepening|iterative deepening]] framework is to try the [[Principal Variation|principal variation]] of the previous [[Iteration|iteration]] as the leftmost path for the next iteration, which might be applied by an explicit [[Triangular PV-Table|triangular PV-table]] or implicit by the [[Transposition Table|transposition table]].
=Standard techniques=
Following techniques are common in finding a good first move
* [[PV-Move]] from the [[Principal Variation|principal variation]] of the previous [[Iteration]]
* [[Hash Move]] - stored move from [[Transposition Table]], if available
* [[Internal Iterative Deepening]] - if no hash move is available, likely only at [[Node Types#PV|PV-Nodes]]
<span id="Captures"></span>
==Captures==
For [[Captures|captures]] (if any), a simple, but quite efficient heuristic is '''(re)capturing''' the '''last''' moved piece with the '''least valuable attacker'''. Otherwise following heuristics may used, concerning the order of captures:
* [[MVV-LVA]] - Most Valuable Victim - Least Valuable Aggressor
* [[Static Exchange Evaluation]] abbreviated as '''SEE'''
<span id="NonCaptures"></span>
==Non-Captures==
* [[Killer Heuristic]] <ref>[[Selim Akl]], [[Monroe Newborn]] ('''1977'''). ''The Principal Continuation and the Killer Heuristic''.1977 ACM Annual Conference Proceedings</ref>
* [[History Heuristic]] <ref>[[Jonathan Schaeffer]] ('''1983'''). ''The History Heuristic''. [[ICGA Journal#6_3|ICCA Journal, Vol. 6, No. 3]]</ref>
* [[Relative History Heuristic]] <ref>[[Mark Winands]], [[Erik van der Werf]], [[Jaap van den Herik]], [[Jos Uiterwijk]] ('''2006'''). ''The Relative History Heuristic''. [[CG 2004]], [http://www.personeel.unimaas.nl/m-winands/documents/relhis.pdf pdf]</ref>
* [[Piece-Square Tables|Dedicated Piece-Square Tables]] only for move ordering <ref>[http://www.top-5000.nl/authors/rebel/chess840.htm#MOVE%20ORDERING Move Ordering in Rebel] by [[Ed Schroder|Ed Schröder]], also available as [http://members.home.nl/matador/Inside%20Rebel.pdf pdf]</ref>
==Less common techniques==
These techniques are well known theoretically for non-captures, but not all programmers use them:
* [[Mate Killers]]
* [[Countermove Heuristic]] <ref>[[Jos Uiterwijk]] ('''1992'''). ''The Countermove Heuristic''. [[ICGA Journal#15_1|ICCA Journal, Vol. 15, No. 1]]</ref>
* [[Guard Heuristic]]
* [[Last Best Reply]]
* [[Butterfly Heuristic]] <ref>[[Dap Hartmann]] ('''1988'''). ''Butterfly Boards''. [[ICGA Journal#11_23|ICCA Journal, Vol. 11, Nos. 2/3]]</ref>
* [[Threat Move]] from [[Null Move Pruning|null move]] refutations
* [[Enhanced Transposition Cutoff]] (ETC)
* [[Refutation Table]]
==Using Neural Networks==
Move ordering (as well as [[Time Management]]) is an interesting application of [[Neural Networks]], as introduced by [[Kieran Greer]] et al. and [[Levente Kocsis]] et al.
* [[Chessmaps Heuristic]]
* [[Neural MoveMap Heuristic]] <ref>[[Levente Kocsis]], [[Jos Uiterwijk]], [[Jaap van den Herik]] ('''2001'''). ''Move Ordering using Neural Networks''. IEA/AIE 2001, [https://en.wikipedia.org/wiki/Lecture_Notes_in_Computer_Science LNCS] 2070</ref> <ref>[[Levente Kocsis]], [[Jos Uiterwijk]], [[Eric Postma]], [[Jaap van den Herik]] ('''2002'''). ''[http://link.springer.com/chapter/10.1007/978-3-540-40031-8_11 The Neural MoveMap Heuristic in Chess]''. [[CG 2002]]</ref>
=Typical move ordering=
After [[Move Generation|move generation]] with assigned move-scores, chess programs usually don't sort the whole [[Move List|move list]], but perform a [https://en.wikipedia.org/wiki/Selection_sort selection sort] each time a move is fetched. Exceptions are the [[Root]] and further [[Node Types#PV|PV-Nodes]] with some distance to the horizon, where one may apply additional effort to score and sort moves. For performance reasons, a lot of programs try to save the [[Move Generation|move generation]] of captures or non-captures at expected [[Node Types#CUT|Cut-Nodes]], but try the hash-move or killer first, if they are proved legal in this position.
A typical move ordering consists as follows:
# [[PV-move]] of the [[Principal Variation|principal variation]] from the previous iteration of an [[Iterative Deepening|iterative deepening]] framework for the leftmost path, often implicitly done by 2.
# [[Hash Move|Hash move]] from [[Transposition Table|hash tables]]
# Winning captures/promotions
# Equal captures/promotions
# [[Killer Move|Killer moves]] (non capture), often with [[Mate Killers|mate killers]] first
# Non-captures sorted by [[History Heuristic|history heuristic]] and that like
# Losing captures (* but see below
*) Depending on the implementation, the [[Board Representation|board representation]], whether and where [[Static Exchange Evaluation|SEE]] is used, the [[Extensions|extension]] policy ([[Recapture Extensions|recapture extensions]]) and other stuff - many programmers favor losing captures before other none-captures - directly behind the killers. They are kind of forced, and one possibly has to deal with all kind of tactical motives and interactions, one may not consider in move ordering. Such as [[Pin|pins]], [[Battery|batteries]], [[Discovered Attack|discovered attacks]] and [[Overloading|overloaded defenders]]. Otherwise, obviously losing captures are likely refuted cheaply. But if a losing capture fails high for some reason, we have saved the effort to generate, and more importantly to search other non-captures at all.
=Node Type Considerations=
Move ordering and scoring effort might be controlled by expected [[Node Types]].
==PV-nodes==
At [[Node Types#PV|PV-nodes]] move ordering is very important, since the best alpha-increase as early as possible makes further search cheaper, due to narrower windows in [[Alpha-Beta]], while in [[Principal Variation Search|PVS]] later but better moves require re-searches of the [[Null Window|null window]] [[Scout|scout]].
==Cut-nodes==
Move ordering is crucial at expected and confirmed [[Node Types#CUT|Cut-nodes]], since it is important to [[Fail-High|fail-high]] as early as possible, as best with the first move, as in greater than 90% of all [[Node Types#CUT|fail-high nodes]]. However, in situations where multiple moves may cut, e.g. with huge [[Material|material]] advantage, we like it as cheap as possible, but not necessarily a huge subtree with f.i. due to [[Check Extensions|check extensions]].
==All-nodes==
At confirmed [[Node Types#ALL|ALL-nodes]] with [[Null Window|null windows]], move ordering didn't care that much. Since we don't know in advance (otherwise we wouldn't search at all), and expected All-nodes may become Cut-nodes, move ordering is an issue as well, but usually with less effort for late moves.
=Depth and Ply Considerations=
Move ordering effort might be controlled by considering [[Depth|draft]] and/or [[Ply|plies]] from [[Root|root]]. The closer the root, the farther the horizon, the more effort might be justified to score and sort moves.
<span id="Root"></span>
==Root Node Considerations==
Despite trying the best move and principal variation from previous iteration first, iterative deepening offers another ressource to order the remaining moves at the [[Root|root]] - their subtree size which could be easily determined. As already mentioned by [[Ingo Althöfer]] in an [[ICGA Journal#15_1|1992 ICCA Journal]] correspondence <ref>[[Ingo Althöfer]] ('''1992'''). ''Move Ordering by Time Ordering''. Correspondence, [[ICGA Journal#15_2|ICCA Journal, Vol. 15, No. 2]]</ref> inspired by [[Jos Uiterwijk|Jos Uiterwijk's]] [[Countermove Heuristic]] article <ref>[[Jos Uiterwijk]] ('''1992'''). ''The Countermove Heuristic''. [[ICGA Journal#15_1|ICCA Journal, Vol. 15, No. 1]]</ref>, based on the soundness of following rule of thumb,
{| class="wikitable"
|-
| <span style="font-size: 130%;">''The longer it takes to refute a move, the higher is its chance to become best move in the next iteration''</span>
|}
the old idea is to use the search time or subtree size of the depth-n iteration to reorder the direct successors of the root before the depth-(n+1) iteration. Some programs use the [[Evaluation|evaluation]] to initially score the moves, to adjust them by their subtree size in subsequent iterations.
An [[Ronald de Man#ScoringRootMoves|idea]] to apply randomness and/or bonuses, i.e. developing bonus, or penalties to [[Moves|move]] [[Score|scores]] at the [[Root|root]] by an [[Oracle|oracle]] approach, was proposed by [[Ronald de Man]] - without any changes in [[Alpha-Beta|alpha-beta search]] or [[Evaluation|leaf evaluation]], and without any problems with the [[Transposition Table|transposition table]] <ref>[https://groups.google.com/d/msg/rec.games.chess.computer/AI3xadkLEIk/UUqnp9J3BaMJ Re: random play] by [[Ronald de Man]], [[Computer Chess Forums|rgcc]], November 28, 1996</ref> <ref>[https://groups.google.com/d/msg/rec.games.chess.computer/me7GkjsEgds/iC_ZJm5UwswJ Re: computer chess "oracle" ideas...] by [[Ronald de Man]], [[Computer Chess Forums|rgcc]], April 7, 1997, see also [https://www.stmintz.com/ccc/index.php?id=390268 Re: mate threat extension/null move] by [[Don Beal]], [[CCC]], October 04, 2004 » [[Mate Threat Extensions]], [[Null Move Pruning|Null Move]] and [[Win at Chess|WAC]] booster</ref>.
==Ordering in Quiescence==
In the [[Quiescence Search|quiescence search]], [[Captures|captures]] are often approximated, for speed. For example, PxQ need not have a [[Static Exchange Evaluation|SEE]] performed on it, since it is clearly a winning capture, where RxB might have the SEE done, to see if it is a winning or possibly losing capture if the bishop is protected.
=See also=
* [[Fixafan]]
* [[Move Generation]]
* [[Move List]]
* [[Node Types]]
: [[Node Types#LeafNodes|Number of Leaf Nodes]]
* [[Odd-Even Effect]]
* [[Search Explosion]]
=Publications=
==1977 ...==
* [[Selim Akl]], [[Monroe Newborn]] ('''1977'''). ''The Principal Continuation and the Killer Heuristic''.1977 ACM Annual Conference Proceedings
* [[Ozalp Babaoglu]] ('''1977'''). ''Hardware implementation of the legal move generation and relative ordering functions for the game of chess''. Master's thesis, [[University of California, Berkeley]]
==1980 ...==
* [[Jonathan Schaeffer]] ('''1983'''). ''The History Heuristic''. [[ICGA Journal#6_3|ICCA Journal, Vol. 6, No. 3]]
* [[Prakash Bettadapur]] ('''1986'''). ''Influence of Ordering on Capture Search''. [[ICGA Journal#9_4|ICCA Journal, Vol. 9, No. 4]]
* [[Dap Hartmann]] ('''1988'''). ''Butterfly Boards''. [[ICGA Journal#11_23|ICCA Journal, Vol. 11, Nos. 2/3]]
==1990 ...==
* [[Dap Hartmann]], [[Peter Kouwenhoven]] ('''1991'''). ''Sundry Computer Chess Topics''. [[Advances in Computer Chess 6]]
* [[Jos Uiterwijk]] ('''1992'''). ''The Countermove Heuristic''. [[ICGA Journal#15_1|ICCA Journal, Vol. 15, No. 1]]
* [[Jos Uiterwijk]] ('''1992'''). ''Memory Efficiency in some Heuristics''. [[ICGA Journal#15_2|ICCA Journal, Vol. 15, No. 2]]
* [[Ingo Althöfer]] ('''1992'''). ''Move Ordering by Time Ordering''. Correspondence, [[ICGA Journal#15_2|ICCA Journal, Vol. 15, No. 2]]
* [[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]]
* [[Yi-Fan Ke]], [[Tai-Ming Parng]] ('''1993'''). ''The Guard Heuristic: Legal Move Ordering with Forward Game-Tree Pruning''. [[ICGA Journal#16-2|ICCA Journal, Vol. 16, No. 2]]
* [[Mei-En Chen]], [[Yo-Ping Huang]] ('''1995'''). ''[http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=527751 Guard heuristic by dynamic fuzzy reasoning model for Chinese chess]''. Proceedings of ISUMA-NAFIPS '95
* [[Kieran Greer]], [[Piyush Ojha]], [[David A. Bell]] ('''1999'''). ''A Pattern-Oriented Approach to Move Ordering: the Chessmaps Heuristic''. [[ICGA Journal#22_1|ICCA Journal, Vol. 22, No. 1]]
==2000 ...==
* [[Kieran Greer]] ('''2000'''). ''[http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6TYF-40TY77M-3&_user=10&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=7858eb0d6e100295c197661d1d454e26 Computer chess move-ordering schemes using move influence]''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 120, No. 2
* [[Levente Kocsis]], [[Jos Uiterwijk]], [[Jaap van den Herik]] ('''2001'''). ''Move Ordering using Neural Networks''. IEA/AIE 2001, [https://en.wikipedia.org/wiki/Lecture_Notes_in_Computer_Science LNCS] 2070
* [[Levente Kocsis]], [[Jos Uiterwijk]], [[Eric Postma]], [[Jaap van den Herik]] ('''2002'''). ''[http://link.springer.com/chapter/10.1007/978-3-540-40031-8_11 The Neural MoveMap Heuristic in Chess]''. [[CG 2002]]
* [[Yoshinori Higashiuchi]], [[Reijer Grimbergen]] ('''2005'''). ''Enhancing Search Efficiency by Using Move Categorization Based on Game Progress in Amazons''. [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.100.3211&rep=rep1&type=pdf pdf]
* [[Mark Winands]], [[Erik van der Werf]], [[Jaap van den Herik]], [[Jos Uiterwijk]] ('''2006'''). ''The Relative History Heuristic''. [[CG 2004]], [http://www.personeel.unimaas.nl/m-winands/documents/relhis.pdf pdf]
* [[Jeff Rollason]] ('''2006'''). ''[http://www.aifactory.co.uk/newsletter/2005_04_plausibility_analysis.htm Driving search with Plausibility analysis: Looking at the right moves]''. [[AI Factory]], Winter 2006
* [[Jeff Rollason]] ('''2007'''). ''[http://www.aifactory.co.uk/newsletter/2007_01_neg_plausibility.htm Negative Plausibility]''. [[AI Factory]], Spring 2007 » [[Relative History Heuristic]]
* [[Rémi Coulom]] ('''2007'''). ''[http://remi.coulom.free.fr/Amsterdam2007/ Computing Elo Ratings of Move Patterns in the Game of Go]''. [[ICGA Journal#30_4|ICGA Journal, Vol. 30, No. 4]], [[CGW 2007]], [http://remi.coulom.free.fr/Amsterdam2007/icgaj.pdf pdf] <ref>[https://en.wikipedia.org/wiki/Bradley%E2%80%93Terry_model Bradley–Terry model from Wikipedia]</ref>
* [[Timothy Furtak]], [[Michael Buro]] ('''2009'''). ''Minimum Proof Graphs and Fastest-Cut-First Search Heuristics''. [[Conferences#IJCAI2009|IJCAI 2009]], [http://ijcai.org/papers09/Papers/IJCAI09-089.pdf pdf] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=57228&start=6 Re: Move ordering for cheapest refutation] by [[Mikko Aarnos]], [[CCC]], August 10, 2015</ref>
==2010 ...==
* [[David J. Wu]] ('''2011'''). ''Move Ranking and Evaluation in the Game of Arimaa''. B.Sc. thesis, [https://en.wikipedia.org/wiki/Harvard_College Harvard College], [https://en.wikipedia.org/wiki/Cambridge,_Massachusetts Cambridge, Massachusetts], [http://arimaa.com/arimaa/papers/DavidWu/djwuthesis.pdf pdf] » [[Arimaa]]
* [[David J. Wu]] ('''2015'''). ''Designing a Winning Arimaa Program''. [[ICGA Journal#38_1|ICGA Journal, Vol. 38, No. 1]]
=Forum Posts=
==1996 ...==
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/7d8a4124ce6f81ac# Pawn Structure "Holes" and Move Ordering] by [[Daniel A. Thies]], [[Computer Chess Forums|rgcc]], February 12, 1996 » [[Pawn Structure]], [[Holes]]
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/99eec6923b0481db computer chess "oracle" ideas...] by [[Robert Hyatt]], [[Computer Chess Forums|rgcc]], April 1, 1997
: [http://groups.google.com/group/rec.games.chess.computer/msg/0df39371422a600c Re: computer chess "oracle" ideas...] by [[Ronald de Man]], [[Computer Chess Forums|rgcc]], April 3, 1997
: [http://groups.google.com/group/rec.games.chess.computer/msg/ccc2546e26d92f88 Re: computer chess "oracle" ideas...] by [[Ronald de Man]], [[Computer Chess Forums|rgcc]], April 7, 1997
* [https://www.stmintz.com/ccc/index.php?id=67397 Measure of moveorder quality] by [[Ralf Elvsén]], [[CCC]], September 04, 1999
* [https://www.stmintz.com/ccc/index.php?id=73278 Fast way to sort moves in movelist ?] by [[Stefan Plenkner]], [[CCC]], October 14, 1999
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=108325 Move ordering?] by [[Severi Salminen]], [[CCC]], April 28, 2000
* [https://www.stmintz.com/ccc/index.php?id=113174 Better subject title: Move ordering] by [[Tom Kerrigan]], [[CCC]]. May 31, 2000
* [https://www.stmintz.com/ccc/index.php?id=157570 Move ordering ideas] by [[Matt McKnight]], [[CCC]], March 08, 2001
* [https://www.stmintz.com/ccc/index.php?id=161474 Dynamic move ordering for capture/promotions?] by [[Scott Gasch]], [[CCC]], April 02, 2001
* [https://www.stmintz.com/ccc/index.php?id=167401 root search ordening] by [[Jan Willem de Kort]], [[CCC]], May 02, 2001
* [https://www.stmintz.com/ccc/index.php?id=168497 Move ordering at root of search] by [[Tom King]], [[CCC]], May 07, 2001
* [https://www.stmintz.com/ccc/index.php?id=343790 A SIMD idea, eg. Piece/Gain of a capture target] by [[Gerd Isenberg]], [[CCC]], January 21, 2004 » [[SSE2]]
* [https://www.stmintz.com/ccc/index.php?id=357188 move ordering and node count] by [[Martin Fierz]], [[CCC]], March 29, 2004
* [https://www.stmintz.com/ccc/index.php?id=358297 Move ordering at root] by [[Jan Renze Steenhuisen|Renze Steenhuisen]], [[CCC]], April 04, 2004
* [https://www.stmintz.com/ccc/index.php?id=379624 Fail-high on first move stat (86%)] by Michael Henderson, [[CCC]], July 29, 2004 » [[Fail-High]]
==2005 ...==
* [http://www.open-aurec.com/wbforum/viewtopic.php?t=4384 Move ordering at different (Knuth) node types] by [[Tom Likens]], [[Computer Chess Forums|Winboard Forum]], February 21, 2006 » [[Node Types]]
* [http://www.talkchess.com/forum/viewtopic.php?t=12706 SEE on non-capture moves in main search] by [[Gary Linscott|Gary]], [[CCC]], March 28, 2007 » [[Static Exchange Evaluation]]
* [http://www.talkchess.com/forum/viewtopic.php?t=15198 caps->noncaps vs. goodcaps->noncaps->badcaps] by [[James Swafford]], [[CCC]], July 18, 2007
* [http://www.talkchess.com/forum/viewtopic.php?t=21119 Move ordering: Delaying moves on the history phase] by [[Miguel A. Ballicora]], [[CCC]], May 13, 2008
: [http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=188924 Re: Move ordering: Delaying moves on the history phase] by [[Lance Perkins]], [[CCC]], May 14, 2008
* [http://www.talkchess.com/forum/viewtopic.php?t=24294 Order of implementing things] by cyberfish, [[CCC]], October 10, 2008
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=34655 root move ordering] by [[Edward Yu]], [[CCC]], June 02, 2010
* [http://www.open-chess.org/viewtopic.php?f=5&t=661 Move ordering improvements] by Howard E, [[Computer Chess Forums|Open Chess Programming Forum]], September 26, 2010
'''2011'''
* [http://www.talkchess.com/forum/viewtopic.php?t=38387 out of check move ordering] by [[Don Dailey]], [[CCC]], March 12, 2011 » [[Check]]
* [http://www.talkchess.com/forum/viewtopic.php?t=38556 The LBR move ordering heuristic] by [[Steven Edwards]], [[CCC]], March 26, 2011 » [[Last Best Reply]]
* [http://www.talkchess.com/forum/viewtopic.php?t=38766 Move ordering by PST] by [[Onno Garms]], [[CCC]], April 16, 2011 » [[Piece-Square Tables]], [[History Heuristic]], [[Onno]]
* [http://www.talkchess.com/forum/viewtopic.php?t=39338 Move ordering question] by [[Stef Luijten]], [[CCC]], June 11, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=39346 Root node search in Stockfish] by [[Onno Garms]], [[CCC]], June 12, 2011 » [[Stockfish]], [[Root]]
* [http://macechess.blogspot.de/2011/08/improve-move-ordering-for-alpha-beta.html Improve Move Ordering for Alpha Beta] by [[Thomas Petzke]], [http://macechess.blogspot.de/ mACE Chess], August 11, 2011
'''2012'''
* [http://stackoverflow.com/questions/8906430/minimax-alpha-beta-pruning-move-ordering Minimax/ Alpha beta pruning Move Ordering?] by Felix, [https://en.wikipedia.org/wiki/Stack_Overflow Stack Overflow], January 18, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=44749 Move ordering idea (old and new?)] by [[Dan Homan|Daniel Homan]], [[CCC]], Aug 09, 2012 » [[Countermove Heuristic]]
* [http://www.talkchess.com/forum/viewtopic.php?t=44745 How effective is move ordering from TT?] by [[Bill Henry]], [[CCC]], August 09, 2012 » [[Transposition Table]]
* [http://www.open-chess.org/viewtopic.php?f=5&t=2173 Relationship between move ordering and pruning] by [[Don Dailey]], [[Computer Chess Forums|OpenChess Forum]], December 17, 2012 » [[Pruning]]
* [http://www.talkchess.com/forum/viewtopic.php?t=46605 Move Ordering?] by [[Thomas Kolarik]], [[CCC]], December 28, 2012
'''2013'''
* [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=47564 Root move order (again)] by [[Alberto Sanjuan]], [[CCC]], March 21, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=47953 History pruning / move ordering question] by [[Jerry Donald]], [[CCC]], May 10, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=48122 Move ordering contest] by [[Ed Schroder]], [[CCC]], May 26, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=48230 An idea for move ordering at the root] by [[Steven Edwards]], [[CCC]], June 09, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=48981 MoveOrdering++] by [[Henk van den Belt]], [[CCC]], August 16, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=50339 How do you get a "Best first move" near the leaves] by [[Henk van den Belt]], [[CCC]], December 05, 2013
'''2014'''
* [http://www.talkchess.com/forum/viewtopic.php?t=51992 Idea of different history] by [[Daniel José Queraltó]], [[CCC]], April 14, 2014 » [[History Heuristic]]
* [http://www.talkchess.com/forum/viewtopic.php?t=53317 Effectiveness of killer moves] by [[Alex Ferguson]], [[CCC]], August 17, 2014
* [http://www.talkchess.com/forum/viewtopic.php?t=54241 Solving a fail low situation at the root] by [[Alberto Sanjuan]], [[CCC]], November 03, 2014 » [[Aspiration Windows]], [[Fail-Low]], [[Root]]
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=55919 Idea #8430: Optimizing move ordering, very slowly] by [[Steven Edwards]], [[CCC]], April 06, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=57228 Move ordering for cheapest refutation] by [[Matthew Lai]], [[CCC]], August 09, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=57346 Bonus for "null move SEE"] by [[Matthew Lai]], [[CCC]], August 23, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=57479 Q: Move ordering, checks] by [[Harm Geert Muller]], [[CCC]], September 02, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=58055 Ordering of Root moves and search instability !] by [[Mahmoud Uthman]], [[CCC]], October 26, 2015 » [[Search Instability]]
'''2016'''
* [http://www.talkchess.com/forum/viewtopic.php?t=61021 Sorting Captures] by [[David Cimbalista]], [[CCC]], August 03, 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=61262 Starting with move ordering] by [[Luis Babboni]], [[CCC]], August 28, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=61401 Best move statistics] by [[Matthew Lai]], [[CCC]], September 12, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=61420 Searching worse moves first] by [[Matthew Lai]], [[CCC]], September 14, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=62558 move ordering especially ordering&searching of root move] by [[Mahmoud Uthman]], [[CCC]], December 21, 2016
'''2017'''
* [http://www.talkchess.com/forum/viewtopic.php?t=62827 Move ordering ?] by [[Mahmoud Uthman]], [[CCC]], January 15, 2017
* [http://www.talkchess.com/forum/viewtopic.php?t=63048 Move ordering ?] by [[Mahmoud Uthman]], [[CCC]], February 04, 2017
* [http://www.talkchess.com/forum/viewtopic.php?t=63275 Sorting losing captures ?] by [[Mahmoud Uthman]], [[CCC]], February 25, 2017
* [http://www.talkchess.com/forum/viewtopic.php?t=63280 Move ordering statistics] by [[Sander Maassen vd Brink]], [[CCC]], February 26, 2017
* [http://www.talkchess.com/forum/viewtopic.php?t=63502 speed up or avoiding move sorting] by [[Alexandru Mosoi]], [[CCC]], March 19, 2017 » [[Zurichess]]
* [http://www.talkchess.com/forum/viewtopic.php?t=63555 Testing for Move Ordering Improvements] by [[Cheney Nattress]], [[CCC]], March 25, 2017 » [[Engine Testing]], [[Search Statistics]]
* [http://www.talkchess.com/forum/viewtopic.php?t=63790 Sorting algorithms] by [[Fermin Serrano]], [[CCC]], April 22, 2017
* [http://www.talkchess.com/forum/viewtopic.php?t=64912 What is causing this problem?] by [[Michael Sherwin]], [[CCC]], August 16, 2017 » [[RomiChess]]
* [http://www.talkchess.com/forum/viewtopic.php?t=65084 Ordering Capture Moves] by [[Jason Fernandez]], [[CCC]], September 06, 2017 » [[Move Ordering#Captures|Move Ordering - Captures]]
* [http://www.talkchess.com/forum/viewtopic.php?t=65189 Marginal hash move] by [[Harm Geert Muller]], [[CCC]], September 16, 2017
* [http://www.talkchess.com/forum/viewtopic.php?t=65365 Unordered moves phenomenon] by [[Alvaro Cardoso]], [[CCC]], October 03, 2017
* [http://www.talkchess.com/forum/viewtopic.php?t=65675 Move ordering] by [[Matthew R. Brades]], [[CCC]], November 09, 2017
'''2018'''
* [http://www.talkchess.com/forum/viewtopic.php?t=66312 Simple quiet move sorting] by [[Andrew Grant]], [[CCC]], January 13, 2018
* [http://www.talkchess.com/forum/viewtopic.php?t=66684 [Discussion] - Measuring move ordering] by [[Ed Schroder]], [[CCC]], February 24, 2018
=External Links=
* [http://www.top-5000.nl/authors/rebel/chess840.htm#MOVE%20ORDERING Move Ordering in Rebel] by [[Ed Schroder|Ed Schröder]]
* [[Videos#HiromiUehara|Hiromi Uehara]], [http://www.cadoganhall.com/event/hiromi-the-trio-project/ The Trio Project], feat. [[Videos#AnthonyJackson|Anthony Jackson]] & [[Videos#SimonPhillips|Simon Phillips]] - Move, (2012), [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=25442170|alignment=left|valignment=top}}
=References=
<references />
'''[[Search|Up one level]]'''
For the [[Alpha-Beta|alpha-beta]] algorithm to perform well, the [[Best Move|best moves]] need to be searched first. This is especially true for [[Node Types#PV|PV-nodes]] and expected [[Node Types#CUT|Cut-nodes]]. The goal is to become close to the minimal tree. On the other hand - at Cut-nodes - the best move is not always the cheapest refutation, see for instance [[Enhanced Transposition Cutoff|enhanced transposition cutoff]]. '''Most''' important inside an [[Iterative Deepening|iterative deepening]] framework is to try the [[Principal Variation|principal variation]] of the previous [[Iteration|iteration]] as the leftmost path for the next iteration, which might be applied by an explicit [[Triangular PV-Table|triangular PV-table]] or implicit by the [[Transposition Table|transposition table]].
=Standard techniques=
Following techniques are common in finding a good first move
* [[PV-Move]] from the [[Principal Variation|principal variation]] of the previous [[Iteration]]
* [[Hash Move]] - stored move from [[Transposition Table]], if available
* [[Internal Iterative Deepening]] - if no hash move is available, likely only at [[Node Types#PV|PV-Nodes]]
<span id="Captures"></span>
==Captures==
For [[Captures|captures]] (if any), a simple, but quite efficient heuristic is '''(re)capturing''' the '''last''' moved piece with the '''least valuable attacker'''. Otherwise following heuristics may used, concerning the order of captures:
* [[MVV-LVA]] - Most Valuable Victim - Least Valuable Aggressor
* [[Static Exchange Evaluation]] abbreviated as '''SEE'''
<span id="NonCaptures"></span>
==Non-Captures==
* [[Killer Heuristic]] <ref>[[Selim Akl]], [[Monroe Newborn]] ('''1977'''). ''The Principal Continuation and the Killer Heuristic''.1977 ACM Annual Conference Proceedings</ref>
* [[History Heuristic]] <ref>[[Jonathan Schaeffer]] ('''1983'''). ''The History Heuristic''. [[ICGA Journal#6_3|ICCA Journal, Vol. 6, No. 3]]</ref>
* [[Relative History Heuristic]] <ref>[[Mark Winands]], [[Erik van der Werf]], [[Jaap van den Herik]], [[Jos Uiterwijk]] ('''2006'''). ''The Relative History Heuristic''. [[CG 2004]], [http://www.personeel.unimaas.nl/m-winands/documents/relhis.pdf pdf]</ref>
* [[Piece-Square Tables|Dedicated Piece-Square Tables]] only for move ordering <ref>[http://www.top-5000.nl/authors/rebel/chess840.htm#MOVE%20ORDERING Move Ordering in Rebel] by [[Ed Schroder|Ed Schröder]], also available as [http://members.home.nl/matador/Inside%20Rebel.pdf pdf]</ref>
==Less common techniques==
These techniques are well known theoretically for non-captures, but not all programmers use them:
* [[Mate Killers]]
* [[Countermove Heuristic]] <ref>[[Jos Uiterwijk]] ('''1992'''). ''The Countermove Heuristic''. [[ICGA Journal#15_1|ICCA Journal, Vol. 15, No. 1]]</ref>
* [[Guard Heuristic]]
* [[Last Best Reply]]
* [[Butterfly Heuristic]] <ref>[[Dap Hartmann]] ('''1988'''). ''Butterfly Boards''. [[ICGA Journal#11_23|ICCA Journal, Vol. 11, Nos. 2/3]]</ref>
* [[Threat Move]] from [[Null Move Pruning|null move]] refutations
* [[Enhanced Transposition Cutoff]] (ETC)
* [[Refutation Table]]
==Using Neural Networks==
Move ordering (as well as [[Time Management]]) is an interesting application of [[Neural Networks]], as introduced by [[Kieran Greer]] et al. and [[Levente Kocsis]] et al.
* [[Chessmaps Heuristic]]
* [[Neural MoveMap Heuristic]] <ref>[[Levente Kocsis]], [[Jos Uiterwijk]], [[Jaap van den Herik]] ('''2001'''). ''Move Ordering using Neural Networks''. IEA/AIE 2001, [https://en.wikipedia.org/wiki/Lecture_Notes_in_Computer_Science LNCS] 2070</ref> <ref>[[Levente Kocsis]], [[Jos Uiterwijk]], [[Eric Postma]], [[Jaap van den Herik]] ('''2002'''). ''[http://link.springer.com/chapter/10.1007/978-3-540-40031-8_11 The Neural MoveMap Heuristic in Chess]''. [[CG 2002]]</ref>
=Typical move ordering=
After [[Move Generation|move generation]] with assigned move-scores, chess programs usually don't sort the whole [[Move List|move list]], but perform a [https://en.wikipedia.org/wiki/Selection_sort selection sort] each time a move is fetched. Exceptions are the [[Root]] and further [[Node Types#PV|PV-Nodes]] with some distance to the horizon, where one may apply additional effort to score and sort moves. For performance reasons, a lot of programs try to save the [[Move Generation|move generation]] of captures or non-captures at expected [[Node Types#CUT|Cut-Nodes]], but try the hash-move or killer first, if they are proved legal in this position.
A typical move ordering consists as follows:
# [[PV-move]] of the [[Principal Variation|principal variation]] from the previous iteration of an [[Iterative Deepening|iterative deepening]] framework for the leftmost path, often implicitly done by 2.
# [[Hash Move|Hash move]] from [[Transposition Table|hash tables]]
# Winning captures/promotions
# Equal captures/promotions
# [[Killer Move|Killer moves]] (non capture), often with [[Mate Killers|mate killers]] first
# Non-captures sorted by [[History Heuristic|history heuristic]] and that like
# Losing captures (* but see below
*) Depending on the implementation, the [[Board Representation|board representation]], whether and where [[Static Exchange Evaluation|SEE]] is used, the [[Extensions|extension]] policy ([[Recapture Extensions|recapture extensions]]) and other stuff - many programmers favor losing captures before other none-captures - directly behind the killers. They are kind of forced, and one possibly has to deal with all kind of tactical motives and interactions, one may not consider in move ordering. Such as [[Pin|pins]], [[Battery|batteries]], [[Discovered Attack|discovered attacks]] and [[Overloading|overloaded defenders]]. Otherwise, obviously losing captures are likely refuted cheaply. But if a losing capture fails high for some reason, we have saved the effort to generate, and more importantly to search other non-captures at all.
=Node Type Considerations=
Move ordering and scoring effort might be controlled by expected [[Node Types]].
==PV-nodes==
At [[Node Types#PV|PV-nodes]] move ordering is very important, since the best alpha-increase as early as possible makes further search cheaper, due to narrower windows in [[Alpha-Beta]], while in [[Principal Variation Search|PVS]] later but better moves require re-searches of the [[Null Window|null window]] [[Scout|scout]].
==Cut-nodes==
Move ordering is crucial at expected and confirmed [[Node Types#CUT|Cut-nodes]], since it is important to [[Fail-High|fail-high]] as early as possible, as best with the first move, as in greater than 90% of all [[Node Types#CUT|fail-high nodes]]. However, in situations where multiple moves may cut, e.g. with huge [[Material|material]] advantage, we like it as cheap as possible, but not necessarily a huge subtree with f.i. due to [[Check Extensions|check extensions]].
==All-nodes==
At confirmed [[Node Types#ALL|ALL-nodes]] with [[Null Window|null windows]], move ordering didn't care that much. Since we don't know in advance (otherwise we wouldn't search at all), and expected All-nodes may become Cut-nodes, move ordering is an issue as well, but usually with less effort for late moves.
=Depth and Ply Considerations=
Move ordering effort might be controlled by considering [[Depth|draft]] and/or [[Ply|plies]] from [[Root|root]]. The closer the root, the farther the horizon, the more effort might be justified to score and sort moves.
<span id="Root"></span>
==Root Node Considerations==
Despite trying the best move and principal variation from previous iteration first, iterative deepening offers another ressource to order the remaining moves at the [[Root|root]] - their subtree size which could be easily determined. As already mentioned by [[Ingo Althöfer]] in an [[ICGA Journal#15_1|1992 ICCA Journal]] correspondence <ref>[[Ingo Althöfer]] ('''1992'''). ''Move Ordering by Time Ordering''. Correspondence, [[ICGA Journal#15_2|ICCA Journal, Vol. 15, No. 2]]</ref> inspired by [[Jos Uiterwijk|Jos Uiterwijk's]] [[Countermove Heuristic]] article <ref>[[Jos Uiterwijk]] ('''1992'''). ''The Countermove Heuristic''. [[ICGA Journal#15_1|ICCA Journal, Vol. 15, No. 1]]</ref>, based on the soundness of following rule of thumb,
{| class="wikitable"
|-
| <span style="font-size: 130%;">''The longer it takes to refute a move, the higher is its chance to become best move in the next iteration''</span>
|}
the old idea is to use the search time or subtree size of the depth-n iteration to reorder the direct successors of the root before the depth-(n+1) iteration. Some programs use the [[Evaluation|evaluation]] to initially score the moves, to adjust them by their subtree size in subsequent iterations.
An [[Ronald de Man#ScoringRootMoves|idea]] to apply randomness and/or bonuses, i.e. developing bonus, or penalties to [[Moves|move]] [[Score|scores]] at the [[Root|root]] by an [[Oracle|oracle]] approach, was proposed by [[Ronald de Man]] - without any changes in [[Alpha-Beta|alpha-beta search]] or [[Evaluation|leaf evaluation]], and without any problems with the [[Transposition Table|transposition table]] <ref>[https://groups.google.com/d/msg/rec.games.chess.computer/AI3xadkLEIk/UUqnp9J3BaMJ Re: random play] by [[Ronald de Man]], [[Computer Chess Forums|rgcc]], November 28, 1996</ref> <ref>[https://groups.google.com/d/msg/rec.games.chess.computer/me7GkjsEgds/iC_ZJm5UwswJ Re: computer chess "oracle" ideas...] by [[Ronald de Man]], [[Computer Chess Forums|rgcc]], April 7, 1997, see also [https://www.stmintz.com/ccc/index.php?id=390268 Re: mate threat extension/null move] by [[Don Beal]], [[CCC]], October 04, 2004 » [[Mate Threat Extensions]], [[Null Move Pruning|Null Move]] and [[Win at Chess|WAC]] booster</ref>.
==Ordering in Quiescence==
In the [[Quiescence Search|quiescence search]], [[Captures|captures]] are often approximated, for speed. For example, PxQ need not have a [[Static Exchange Evaluation|SEE]] performed on it, since it is clearly a winning capture, where RxB might have the SEE done, to see if it is a winning or possibly losing capture if the bishop is protected.
=See also=
* [[Fixafan]]
* [[Move Generation]]
* [[Move List]]
* [[Node Types]]
: [[Node Types#LeafNodes|Number of Leaf Nodes]]
* [[Odd-Even Effect]]
* [[Search Explosion]]
=Publications=
==1977 ...==
* [[Selim Akl]], [[Monroe Newborn]] ('''1977'''). ''The Principal Continuation and the Killer Heuristic''.1977 ACM Annual Conference Proceedings
* [[Ozalp Babaoglu]] ('''1977'''). ''Hardware implementation of the legal move generation and relative ordering functions for the game of chess''. Master's thesis, [[University of California, Berkeley]]
==1980 ...==
* [[Jonathan Schaeffer]] ('''1983'''). ''The History Heuristic''. [[ICGA Journal#6_3|ICCA Journal, Vol. 6, No. 3]]
* [[Prakash Bettadapur]] ('''1986'''). ''Influence of Ordering on Capture Search''. [[ICGA Journal#9_4|ICCA Journal, Vol. 9, No. 4]]
* [[Dap Hartmann]] ('''1988'''). ''Butterfly Boards''. [[ICGA Journal#11_23|ICCA Journal, Vol. 11, Nos. 2/3]]
==1990 ...==
* [[Dap Hartmann]], [[Peter Kouwenhoven]] ('''1991'''). ''Sundry Computer Chess Topics''. [[Advances in Computer Chess 6]]
* [[Jos Uiterwijk]] ('''1992'''). ''The Countermove Heuristic''. [[ICGA Journal#15_1|ICCA Journal, Vol. 15, No. 1]]
* [[Jos Uiterwijk]] ('''1992'''). ''Memory Efficiency in some Heuristics''. [[ICGA Journal#15_2|ICCA Journal, Vol. 15, No. 2]]
* [[Ingo Althöfer]] ('''1992'''). ''Move Ordering by Time Ordering''. Correspondence, [[ICGA Journal#15_2|ICCA Journal, Vol. 15, No. 2]]
* [[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]]
* [[Yi-Fan Ke]], [[Tai-Ming Parng]] ('''1993'''). ''The Guard Heuristic: Legal Move Ordering with Forward Game-Tree Pruning''. [[ICGA Journal#16-2|ICCA Journal, Vol. 16, No. 2]]
* [[Mei-En Chen]], [[Yo-Ping Huang]] ('''1995'''). ''[http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=527751 Guard heuristic by dynamic fuzzy reasoning model for Chinese chess]''. Proceedings of ISUMA-NAFIPS '95
* [[Kieran Greer]], [[Piyush Ojha]], [[David A. Bell]] ('''1999'''). ''A Pattern-Oriented Approach to Move Ordering: the Chessmaps Heuristic''. [[ICGA Journal#22_1|ICCA Journal, Vol. 22, No. 1]]
==2000 ...==
* [[Kieran Greer]] ('''2000'''). ''[http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6TYF-40TY77M-3&_user=10&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=7858eb0d6e100295c197661d1d454e26 Computer chess move-ordering schemes using move influence]''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 120, No. 2
* [[Levente Kocsis]], [[Jos Uiterwijk]], [[Jaap van den Herik]] ('''2001'''). ''Move Ordering using Neural Networks''. IEA/AIE 2001, [https://en.wikipedia.org/wiki/Lecture_Notes_in_Computer_Science LNCS] 2070
* [[Levente Kocsis]], [[Jos Uiterwijk]], [[Eric Postma]], [[Jaap van den Herik]] ('''2002'''). ''[http://link.springer.com/chapter/10.1007/978-3-540-40031-8_11 The Neural MoveMap Heuristic in Chess]''. [[CG 2002]]
* [[Yoshinori Higashiuchi]], [[Reijer Grimbergen]] ('''2005'''). ''Enhancing Search Efficiency by Using Move Categorization Based on Game Progress in Amazons''. [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.100.3211&rep=rep1&type=pdf pdf]
* [[Mark Winands]], [[Erik van der Werf]], [[Jaap van den Herik]], [[Jos Uiterwijk]] ('''2006'''). ''The Relative History Heuristic''. [[CG 2004]], [http://www.personeel.unimaas.nl/m-winands/documents/relhis.pdf pdf]
* [[Jeff Rollason]] ('''2006'''). ''[http://www.aifactory.co.uk/newsletter/2005_04_plausibility_analysis.htm Driving search with Plausibility analysis: Looking at the right moves]''. [[AI Factory]], Winter 2006
* [[Jeff Rollason]] ('''2007'''). ''[http://www.aifactory.co.uk/newsletter/2007_01_neg_plausibility.htm Negative Plausibility]''. [[AI Factory]], Spring 2007 » [[Relative History Heuristic]]
* [[Rémi Coulom]] ('''2007'''). ''[http://remi.coulom.free.fr/Amsterdam2007/ Computing Elo Ratings of Move Patterns in the Game of Go]''. [[ICGA Journal#30_4|ICGA Journal, Vol. 30, No. 4]], [[CGW 2007]], [http://remi.coulom.free.fr/Amsterdam2007/icgaj.pdf pdf] <ref>[https://en.wikipedia.org/wiki/Bradley%E2%80%93Terry_model Bradley–Terry model from Wikipedia]</ref>
* [[Timothy Furtak]], [[Michael Buro]] ('''2009'''). ''Minimum Proof Graphs and Fastest-Cut-First Search Heuristics''. [[Conferences#IJCAI2009|IJCAI 2009]], [http://ijcai.org/papers09/Papers/IJCAI09-089.pdf pdf] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=57228&start=6 Re: Move ordering for cheapest refutation] by [[Mikko Aarnos]], [[CCC]], August 10, 2015</ref>
==2010 ...==
* [[David J. Wu]] ('''2011'''). ''Move Ranking and Evaluation in the Game of Arimaa''. B.Sc. thesis, [https://en.wikipedia.org/wiki/Harvard_College Harvard College], [https://en.wikipedia.org/wiki/Cambridge,_Massachusetts Cambridge, Massachusetts], [http://arimaa.com/arimaa/papers/DavidWu/djwuthesis.pdf pdf] » [[Arimaa]]
* [[David J. Wu]] ('''2015'''). ''Designing a Winning Arimaa Program''. [[ICGA Journal#38_1|ICGA Journal, Vol. 38, No. 1]]
=Forum Posts=
==1996 ...==
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/7d8a4124ce6f81ac# Pawn Structure "Holes" and Move Ordering] by [[Daniel A. Thies]], [[Computer Chess Forums|rgcc]], February 12, 1996 » [[Pawn Structure]], [[Holes]]
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/99eec6923b0481db computer chess "oracle" ideas...] by [[Robert Hyatt]], [[Computer Chess Forums|rgcc]], April 1, 1997
: [http://groups.google.com/group/rec.games.chess.computer/msg/0df39371422a600c Re: computer chess "oracle" ideas...] by [[Ronald de Man]], [[Computer Chess Forums|rgcc]], April 3, 1997
: [http://groups.google.com/group/rec.games.chess.computer/msg/ccc2546e26d92f88 Re: computer chess "oracle" ideas...] by [[Ronald de Man]], [[Computer Chess Forums|rgcc]], April 7, 1997
* [https://www.stmintz.com/ccc/index.php?id=67397 Measure of moveorder quality] by [[Ralf Elvsén]], [[CCC]], September 04, 1999
* [https://www.stmintz.com/ccc/index.php?id=73278 Fast way to sort moves in movelist ?] by [[Stefan Plenkner]], [[CCC]], October 14, 1999
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=108325 Move ordering?] by [[Severi Salminen]], [[CCC]], April 28, 2000
* [https://www.stmintz.com/ccc/index.php?id=113174 Better subject title: Move ordering] by [[Tom Kerrigan]], [[CCC]]. May 31, 2000
* [https://www.stmintz.com/ccc/index.php?id=157570 Move ordering ideas] by [[Matt McKnight]], [[CCC]], March 08, 2001
* [https://www.stmintz.com/ccc/index.php?id=161474 Dynamic move ordering for capture/promotions?] by [[Scott Gasch]], [[CCC]], April 02, 2001
* [https://www.stmintz.com/ccc/index.php?id=167401 root search ordening] by [[Jan Willem de Kort]], [[CCC]], May 02, 2001
* [https://www.stmintz.com/ccc/index.php?id=168497 Move ordering at root of search] by [[Tom King]], [[CCC]], May 07, 2001
* [https://www.stmintz.com/ccc/index.php?id=343790 A SIMD idea, eg. Piece/Gain of a capture target] by [[Gerd Isenberg]], [[CCC]], January 21, 2004 » [[SSE2]]
* [https://www.stmintz.com/ccc/index.php?id=357188 move ordering and node count] by [[Martin Fierz]], [[CCC]], March 29, 2004
* [https://www.stmintz.com/ccc/index.php?id=358297 Move ordering at root] by [[Jan Renze Steenhuisen|Renze Steenhuisen]], [[CCC]], April 04, 2004
* [https://www.stmintz.com/ccc/index.php?id=379624 Fail-high on first move stat (86%)] by Michael Henderson, [[CCC]], July 29, 2004 » [[Fail-High]]
==2005 ...==
* [http://www.open-aurec.com/wbforum/viewtopic.php?t=4384 Move ordering at different (Knuth) node types] by [[Tom Likens]], [[Computer Chess Forums|Winboard Forum]], February 21, 2006 » [[Node Types]]
* [http://www.talkchess.com/forum/viewtopic.php?t=12706 SEE on non-capture moves in main search] by [[Gary Linscott|Gary]], [[CCC]], March 28, 2007 » [[Static Exchange Evaluation]]
* [http://www.talkchess.com/forum/viewtopic.php?t=15198 caps->noncaps vs. goodcaps->noncaps->badcaps] by [[James Swafford]], [[CCC]], July 18, 2007
* [http://www.talkchess.com/forum/viewtopic.php?t=21119 Move ordering: Delaying moves on the history phase] by [[Miguel A. Ballicora]], [[CCC]], May 13, 2008
: [http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=188924 Re: Move ordering: Delaying moves on the history phase] by [[Lance Perkins]], [[CCC]], May 14, 2008
* [http://www.talkchess.com/forum/viewtopic.php?t=24294 Order of implementing things] by cyberfish, [[CCC]], October 10, 2008
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=34655 root move ordering] by [[Edward Yu]], [[CCC]], June 02, 2010
* [http://www.open-chess.org/viewtopic.php?f=5&t=661 Move ordering improvements] by Howard E, [[Computer Chess Forums|Open Chess Programming Forum]], September 26, 2010
'''2011'''
* [http://www.talkchess.com/forum/viewtopic.php?t=38387 out of check move ordering] by [[Don Dailey]], [[CCC]], March 12, 2011 » [[Check]]
* [http://www.talkchess.com/forum/viewtopic.php?t=38556 The LBR move ordering heuristic] by [[Steven Edwards]], [[CCC]], March 26, 2011 » [[Last Best Reply]]
* [http://www.talkchess.com/forum/viewtopic.php?t=38766 Move ordering by PST] by [[Onno Garms]], [[CCC]], April 16, 2011 » [[Piece-Square Tables]], [[History Heuristic]], [[Onno]]
* [http://www.talkchess.com/forum/viewtopic.php?t=39338 Move ordering question] by [[Stef Luijten]], [[CCC]], June 11, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=39346 Root node search in Stockfish] by [[Onno Garms]], [[CCC]], June 12, 2011 » [[Stockfish]], [[Root]]
* [http://macechess.blogspot.de/2011/08/improve-move-ordering-for-alpha-beta.html Improve Move Ordering for Alpha Beta] by [[Thomas Petzke]], [http://macechess.blogspot.de/ mACE Chess], August 11, 2011
'''2012'''
* [http://stackoverflow.com/questions/8906430/minimax-alpha-beta-pruning-move-ordering Minimax/ Alpha beta pruning Move Ordering?] by Felix, [https://en.wikipedia.org/wiki/Stack_Overflow Stack Overflow], January 18, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=44749 Move ordering idea (old and new?)] by [[Dan Homan|Daniel Homan]], [[CCC]], Aug 09, 2012 » [[Countermove Heuristic]]
* [http://www.talkchess.com/forum/viewtopic.php?t=44745 How effective is move ordering from TT?] by [[Bill Henry]], [[CCC]], August 09, 2012 » [[Transposition Table]]
* [http://www.open-chess.org/viewtopic.php?f=5&t=2173 Relationship between move ordering and pruning] by [[Don Dailey]], [[Computer Chess Forums|OpenChess Forum]], December 17, 2012 » [[Pruning]]
* [http://www.talkchess.com/forum/viewtopic.php?t=46605 Move Ordering?] by [[Thomas Kolarik]], [[CCC]], December 28, 2012
'''2013'''
* [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=47564 Root move order (again)] by [[Alberto Sanjuan]], [[CCC]], March 21, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=47953 History pruning / move ordering question] by [[Jerry Donald]], [[CCC]], May 10, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=48122 Move ordering contest] by [[Ed Schroder]], [[CCC]], May 26, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=48230 An idea for move ordering at the root] by [[Steven Edwards]], [[CCC]], June 09, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=48981 MoveOrdering++] by [[Henk van den Belt]], [[CCC]], August 16, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=50339 How do you get a "Best first move" near the leaves] by [[Henk van den Belt]], [[CCC]], December 05, 2013
'''2014'''
* [http://www.talkchess.com/forum/viewtopic.php?t=51992 Idea of different history] by [[Daniel José Queraltó]], [[CCC]], April 14, 2014 » [[History Heuristic]]
* [http://www.talkchess.com/forum/viewtopic.php?t=53317 Effectiveness of killer moves] by [[Alex Ferguson]], [[CCC]], August 17, 2014
* [http://www.talkchess.com/forum/viewtopic.php?t=54241 Solving a fail low situation at the root] by [[Alberto Sanjuan]], [[CCC]], November 03, 2014 » [[Aspiration Windows]], [[Fail-Low]], [[Root]]
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=55919 Idea #8430: Optimizing move ordering, very slowly] by [[Steven Edwards]], [[CCC]], April 06, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=57228 Move ordering for cheapest refutation] by [[Matthew Lai]], [[CCC]], August 09, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=57346 Bonus for "null move SEE"] by [[Matthew Lai]], [[CCC]], August 23, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=57479 Q: Move ordering, checks] by [[Harm Geert Muller]], [[CCC]], September 02, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=58055 Ordering of Root moves and search instability !] by [[Mahmoud Uthman]], [[CCC]], October 26, 2015 » [[Search Instability]]
'''2016'''
* [http://www.talkchess.com/forum/viewtopic.php?t=61021 Sorting Captures] by [[David Cimbalista]], [[CCC]], August 03, 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=61262 Starting with move ordering] by [[Luis Babboni]], [[CCC]], August 28, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=61401 Best move statistics] by [[Matthew Lai]], [[CCC]], September 12, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=61420 Searching worse moves first] by [[Matthew Lai]], [[CCC]], September 14, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=62558 move ordering especially ordering&searching of root move] by [[Mahmoud Uthman]], [[CCC]], December 21, 2016
'''2017'''
* [http://www.talkchess.com/forum/viewtopic.php?t=62827 Move ordering ?] by [[Mahmoud Uthman]], [[CCC]], January 15, 2017
* [http://www.talkchess.com/forum/viewtopic.php?t=63048 Move ordering ?] by [[Mahmoud Uthman]], [[CCC]], February 04, 2017
* [http://www.talkchess.com/forum/viewtopic.php?t=63275 Sorting losing captures ?] by [[Mahmoud Uthman]], [[CCC]], February 25, 2017
* [http://www.talkchess.com/forum/viewtopic.php?t=63280 Move ordering statistics] by [[Sander Maassen vd Brink]], [[CCC]], February 26, 2017
* [http://www.talkchess.com/forum/viewtopic.php?t=63502 speed up or avoiding move sorting] by [[Alexandru Mosoi]], [[CCC]], March 19, 2017 » [[Zurichess]]
* [http://www.talkchess.com/forum/viewtopic.php?t=63555 Testing for Move Ordering Improvements] by [[Cheney Nattress]], [[CCC]], March 25, 2017 » [[Engine Testing]], [[Search Statistics]]
* [http://www.talkchess.com/forum/viewtopic.php?t=63790 Sorting algorithms] by [[Fermin Serrano]], [[CCC]], April 22, 2017
* [http://www.talkchess.com/forum/viewtopic.php?t=64912 What is causing this problem?] by [[Michael Sherwin]], [[CCC]], August 16, 2017 » [[RomiChess]]
* [http://www.talkchess.com/forum/viewtopic.php?t=65084 Ordering Capture Moves] by [[Jason Fernandez]], [[CCC]], September 06, 2017 » [[Move Ordering#Captures|Move Ordering - Captures]]
* [http://www.talkchess.com/forum/viewtopic.php?t=65189 Marginal hash move] by [[Harm Geert Muller]], [[CCC]], September 16, 2017
* [http://www.talkchess.com/forum/viewtopic.php?t=65365 Unordered moves phenomenon] by [[Alvaro Cardoso]], [[CCC]], October 03, 2017
* [http://www.talkchess.com/forum/viewtopic.php?t=65675 Move ordering] by [[Matthew R. Brades]], [[CCC]], November 09, 2017
'''2018'''
* [http://www.talkchess.com/forum/viewtopic.php?t=66312 Simple quiet move sorting] by [[Andrew Grant]], [[CCC]], January 13, 2018
* [http://www.talkchess.com/forum/viewtopic.php?t=66684 [Discussion] - Measuring move ordering] by [[Ed Schroder]], [[CCC]], February 24, 2018
=External Links=
* [http://www.top-5000.nl/authors/rebel/chess840.htm#MOVE%20ORDERING Move Ordering in Rebel] by [[Ed Schroder|Ed Schröder]]
* [[Videos#HiromiUehara|Hiromi Uehara]], [http://www.cadoganhall.com/event/hiromi-the-trio-project/ The Trio Project], feat. [[Videos#AnthonyJackson|Anthony Jackson]] & [[Videos#SimonPhillips|Simon Phillips]] - Move, (2012), [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=25442170|alignment=left|valignment=top}}
=References=
<references />
'''[[Search|Up one level]]'''
