25,161
edits
Changes
no edit summary
'''[[Main Page|Home]] * [[Search]] * Move Ordering'''
[[FILE:Four Parts MET sf1991.402.9.jpg|border|right|thumb| [[Arts#:Category:Wassily Kandinsky|Wassily Kandinsky]] - Four Parts <ref>[[Arts#:Category:Wassily Kandinsky|Wassily Kandinsky]] - [https://commons.wikimedia.org/wiki/File:Four_Parts_MET_sf1991.402.9.jpg?uselang=en Four Parts], 1932, [https://en.wikipedia.org/wiki/Metropolitan_Museum_of_Art Metropolitan Museum of Art]</ref> ]]
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]].
* [[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>[https://web.archive.org/web/20120413083131/http://www.top-5000.nl/authors/rebel/chess840.htm#MOVE%20ORDERING Move Ordering in Rebel] by [[Ed Schroder|Ed Schröder]]([https://en.wikipedia.org/wiki/Wayback_Machine Wayback Machine]), also available as [http://members.home.nl/matador/Inside%20Rebel.pdf pdf]</ref>
==Less common techniques==
A typical move ordering consists as follows:
# [[PV-Move|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
: [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=48187 Move ordering - How do I know if I have played this move already?] by [[Steve Maughan]], [[CCC]], April 06, 1999
* [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=68825 Move Ordering at the Root] by [[Daniel Homan]], [[CCC]], September 15, 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 ...==
==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.open-aurec.com/wbforum/viewtopic.php?f=4&t=4447 move ordering statistic] by [[Andrew Shapira]], [[Computer Chess Forums|Winboard Forum]], March 03, 2006
* [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?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
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=28873 Negative Plausibility Move Ordering] by [[Alessandro Damiani]], [[CCC]], July 09, 2009
==2010 ...==
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=32611 Move ordering help] by [[Richard Allbert]], [[CCC]], February 14, 2010 » [[Jabba]]
* [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
'''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/forum3/viewtopic.php?f=7&t=42567 Move Ordering (Again :))] by [[Richard Allbert]], [[CCC]], February 22, 2012* [http://www.talkchess.com/forum/viewtopic.php?t=44749 Move ordering idea (old and new?)] by [[Dan Homan|Daniel Homan]], [[CCC]], Aug August 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]]
'''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 <nowiki>[Discussion] </nowiki> - Measuring move ordering] by [[Ed Schroder]], [[CCC]], February 24, 2018==2020 ...==* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=73088 Idea in move ordering ...] by De Noose Daniel, [[CCC]], February 14, 2020* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=73930 sort every moves or pickNext] by [[Vivien Clauzon]], [[CCC]], May 14, 2020 * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=74325 Testing Move Order Quality] by Cheney, [[CCC]], June 29, 2020 * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=74752 Using piece-square table score for move ordering] by [[Maksim Korzh]], [[CCC]], August 11, 2020 » [[Piece-Square Tables]]'''2021'''* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=76491 Sorting moves during move ordering] by [[Niels Abildskov]], [[CCC]], February 04, 2021* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=76887 Hash move ordering vs. Hash cuts: savings in number of nodes visited] by [[Marcel Vanthoor]], [[CCC]], March 16, 2021 » [[Transposition Table]]* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=76888 Best move from previous iteration first: still needed with TT?] by [[Marcel Vanthoor]], [[CCC]], March 16, 2021 » [[Hash Move]], [[PV-Move]]* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=77152 Move ordering heuristics for captures] by [[Niels Abildskov]], [[CCC]], April 23, 2021
=External Links=
* [https://web.archive.org/web/20120413083131/http://www.top-5000.nl/authors/rebel/chess840.htm#MOVE%20ORDERING Move Ordering in Rebel] by [[Ed Schroder|Ed Schröder]]([https://en.wikipedia.org/wiki/Wayback_Machine Wayback Machine])* [[Videos#HiromiUehara:Category:Hiromi Uehara|Hiromi Uehara]], [http://www.cadoganhall.com/event/hiromi-the-trio-project/ The Trio Project], feat. [[Videos#AnthonyJackson:Category:Anthony Jackson|Anthony Jackson]] & [[Videos#SimonPhillips:Category:Simon Phillips|Simon Phillips]] - Move, (2012), [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=1rxYw7Y45Eo|alignment=left|valignment=top}}
'''[[Search|Up one level]]'''
[[Category:Wassily Kandinsky]]
[[Category:Anthony Jackson]]
[[Category:Simon Phillips]]
[[Category:Hiromi Uehara]]
