Changes

Jump to: navigation, search

Move Ordering

4,652 bytes added, 18:27, 12 March 2022
no edit summary
'''[[Main Page|Home]] * [[Search]] * Move Ordering'''
 
[[FILE:Four Parts MET sf1991.402.9.jpg|border|right|thumb| [[:Category:Wassily Kandinsky|Wassily Kandinsky]] - Four Parts <ref>[[: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
* [[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]]
==2020 ...==
* [[Toni Helminen]] ('''2022'''). ''[https://github.com/SamuraiDangyo/lazy-sorting-algorithm Lazy sorting algorithm]''. <ref>[https://www.talkchess.com/forum3/viewtopic.php?f=7&t=79279 Lazy sorting algorithm - Sorting on steroids] by [[Toni Helminen|JohnWoe]], [[CCC]], February 03, 2022 </ref>
=Forum Posts=
: [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* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=77380 Qsearch dynamic order besides MVV/LVA] by [[Aleks Peshkov]], [[CCC]], May 25, 2021 » [[Quiescence Search]]* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=77593 PV-move ordering necessary if you have TT-move ordering?] by [[Marcel Vanthoor]], [[CCC]], July 01, 2021 » [[Hash Move]], [[PV-Move]]* [https://www.talkchess.com/forum3/viewtopic.php?f=7&t=78474 About move ordering and TT hitrate] by Giovanni Maria Manduca, [[CCC]], October 22, 2021 » [[Transposition Table]]* [https://www.talkchess.com/forum3/viewtopic.php?f=7&t=78552 Move ordering at the root] by Jonathan McDermid, [[CCC]], October 30, 2021 » [[Root]]'''2022'''* [https://www.talkchess.com/forum3/viewtopic.php?f=7&t=79077 Move ordering using SEE] by Christian Dean, [[CCC]], January 08, 2022 » [[Static Exchange Evaluation|SEE]]* [https://www.talkchess.com/forum3/viewtopic.php?f=7&t=79279 Lazy sorting algorithm - Sorting on steroids] by [[Toni Helminen|JohnWoe]], [[CCC]], February 03, 2022 * [https://www.talkchess.com/forum3/viewtopic.php?f=7&t=79342 Having trouble understanding advanced move ordering techniques] by Pedro Duran, [[CCC]], February 10, 2022* [https://www.talkchess.com/forum3/viewtopic.php?f=7&t=79368 Failure of trivial approach to neural network move ordering] by [[Jost Triller]], [[CCC]], February 16, 2022 » [[Neural Networks]]
=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=254421701rxYw7Y45Eo|alignment=left|valignment=top}}
=References=
<references />
 
'''[[Search|Up one level]]'''
[[Category:Wassily Kandinsky]]
[[Category:Anthony Jackson]]
[[Category:Simon Phillips]]
[[Category:Hiromi Uehara]]

Navigation menu