Difference between revisions of "Move Ordering"

From Chessprogramming wiki
Jump to: navigation, search
 
(21 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
'''[[Main Page|Home]] * [[Search]] * Move Ordering'''
 
'''[[Main Page|Home]] * [[Search]] * Move Ordering'''
  
[[FILE:Four Parts MET sf1991.402.9.jpg|border|right|thumb| [[Arts#Kandinsky|Wassily Kandinsky]] - Four Parts <ref>[[Arts#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> ]]
+
[[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]].
 
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]].
Line 20: Line 20:
 
* [[History Heuristic]] <ref>[[Jonathan Schaeffer]] ('''1983'''). ''The History Heuristic''. [[ICGA Journal#6_3|ICCA Journal, Vol. 6, No. 3]]</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>
 
* [[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>
+
* [[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==  
 
==Less common techniques==  
Line 42: Line 42:
  
 
A typical move ordering consists as follows:
 
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.
+
# [[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]]
 
# [[Hash Move|Hash move]] from [[Transposition Table|hash tables]]
 
# Winning captures/promotions
 
# Winning captures/promotions
Line 119: Line 119:
 
* [[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]] ('''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]]
 
* [[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=
 
=Forum Posts=
Line 126: Line 128:
 
: [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/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
 
: [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=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
 
* [https://www.stmintz.com/ccc/index.php?id=73278 Fast way to sort moves in movelist ?] by [[Stefan Plenkner]], [[CCC]], October 14, 1999
 
==2000 ...==
 
==2000 ...==
Line 141: Line 145:
 
==2005 ...==
 
==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?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=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=15198 caps->noncaps vs. goodcaps->noncaps->badcaps] by [[James Swafford]], [[CCC]], July 18, 2007
Line 148: Line 153:
 
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=28873 Negative Plausibility Move Ordering] by [[Alessandro Damiani]], [[CCC]], July 09, 2009  
 
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=28873 Negative Plausibility Move Ordering] by [[Alessandro Damiani]], [[CCC]], July 09, 2009  
 
==2010 ...==
 
==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.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
 
* [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
Line 159: Line 165:
 
'''2012'''
 
'''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://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/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 [[Daniel Homan]], [[CCC]], 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.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.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]]
Line 203: Line 210:
 
'''2018'''
 
'''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=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
+
* [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=
 
=External Links=
* [http://www.top-5000.nl/authors/rebel/chess840.htm#MOVE%20ORDERING Move Ordering in Rebel] by [[Ed Schroder|Ed Schröder]]
+
* [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])
 
* [[:Category:Hiromi Uehara|Hiromi Uehara]], [http://www.cadoganhall.com/event/hiromi-the-trio-project/ The Trio Project], feat. [[:Category:Anthony Jackson|Anthony Jackson]] & [[:Category:Simon Phillips|Simon Phillips]] - Move, (2012), [https://en.wikipedia.org/wiki/YouTube YouTube] Video
 
* [[:Category:Hiromi Uehara|Hiromi Uehara]], [http://www.cadoganhall.com/event/hiromi-the-trio-project/ The Trio Project], feat. [[:Category:Anthony Jackson|Anthony Jackson]] & [[: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}}
 
: {{#evu:https://www.youtube.com/watch?v=1rxYw7Y45Eo|alignment=left|valignment=top}}
Line 212: Line 238:
 
=References=
 
=References=
 
<references />
 
<references />
 
 
'''[[Search|Up one level]]'''
 
'''[[Search|Up one level]]'''
 
[[Category:Wassily Kandinsky]]
 
[[Category:Wassily Kandinsky]]

Latest revision as of 17:27, 12 March 2022

Home * Search * Move Ordering

Wassily Kandinsky - Four Parts [1]

For the alpha-beta algorithm to perform well, the best moves need to be searched first. This is especially true for PV-nodes and expected 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. Most important inside an iterative deepening framework is to try the principal variation of the previous iteration as the leftmost path for the next iteration, which might be applied by an explicit triangular PV-table or implicit by the transposition table.

Standard techniques

Following techniques are common in finding a good first move

Captures

For 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:

Non-Captures

Less common techniques

These techniques are well known theoretically for non-captures, but not all programmers use them:

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.

Typical move ordering

After move generation with assigned move-scores, chess programs usually don't sort the whole move list, but perform a selection sort each time a move is fetched. Exceptions are the Root and further 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 of captures or non-captures at expected 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:

  1. PV-move of the principal variation from the previous iteration of an iterative deepening framework for the leftmost path, often implicitly done by 2.
  2. Hash move from hash tables
  3. Winning captures/promotions
  4. Equal captures/promotions
  5. Killer moves (non capture), often with mate killers first
  6. Non-captures sorted by history heuristic and that like
  7. Losing captures (* but see below
  • ) Depending on the implementation, the board representation, whether and where SEE is used, the extension policy (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 pins, batteries, discovered attacks and 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 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 PVS later but better moves require re-searches of the null window scout.

Cut-nodes

Move ordering is crucial at expected and confirmed Cut-nodes, since it is important to fail-high as early as possible, as best with the first move, as in greater than 90% of all fail-high nodes. However, in situations where multiple moves may cut, e.g. with huge material advantage, we like it as cheap as possible, but not necessarily a huge subtree with f.i. due to check extensions.

All-nodes

At confirmed ALL-nodes with 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 draft and/or plies from root. The closer the root, the farther the horizon, the more effort might be justified to score and sort moves.

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 - their subtree size which could be easily determined. As already mentioned by Ingo Althöfer in an 1992 ICCA Journal correspondence [10] inspired by Jos Uiterwijk's Countermove Heuristic article [11], based on the soundness of following rule of thumb,

The longer it takes to refute a move, the higher is its chance to become best move in the next iteration

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 to initially score the moves, to adjust them by their subtree size in subsequent iterations.

An idea to apply randomness and/or bonuses, i.e. developing bonus, or penalties to move scores at the root by an oracle approach, was proposed by Ronald de Man - without any changes in alpha-beta search or leaf evaluation, and without any problems with the transposition table [12] [13].

Ordering in Quiescence

In the quiescence search, captures are often approximated, for speed. For example, PxQ need not have a 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

Number of Leaf Nodes

Publications

1977 ...

1980 ...

1990 ...

2000 ...

2010 ...

2020 ...

Forum Posts

1996 ...

Re: computer chess "oracle" ideas... by Ronald de Man, rgcc, April 3, 1997
Re: computer chess "oracle" ideas... by Ronald de Man, rgcc, April 7, 1997

2000 ...

2005 ...

Re: Move ordering: Delaying moves on the history phase by Lance Perkins, CCC, May 14, 2008

2010 ...

2011

2012

2013

2014

2015 ...

2016

2017

2018

2020 ...

2021

2022

External Links

References

  1. Wassily Kandinsky - Four Parts, 1932, Metropolitan Museum of Art
  2. Selim Akl, Monroe Newborn (1977). The Principal Continuation and the Killer Heuristic.1977 ACM Annual Conference Proceedings
  3. Jonathan Schaeffer (1983). The History Heuristic. ICCA Journal, Vol. 6, No. 3
  4. Mark Winands, Erik van der Werf, Jaap van den Herik, Jos Uiterwijk (2006). The Relative History Heuristic. CG 2004, pdf
  5. Move Ordering in Rebel by Ed Schröder (Wayback Machine), also available as pdf
  6. Jos Uiterwijk (1992). The Countermove Heuristic. ICCA Journal, Vol. 15, No. 1
  7. Dap Hartmann (1988). Butterfly Boards. ICCA Journal, Vol. 11, Nos. 2/3
  8. Levente Kocsis, Jos Uiterwijk, Jaap van den Herik (2001). Move Ordering using Neural Networks. IEA/AIE 2001, LNCS 2070
  9. Levente Kocsis, Jos Uiterwijk, Eric Postma, Jaap van den Herik (2002). The Neural MoveMap Heuristic in Chess. CG 2002
  10. Ingo Althöfer (1992). Move Ordering by Time Ordering. Correspondence, ICCA Journal, Vol. 15, No. 2
  11. Jos Uiterwijk (1992). The Countermove Heuristic. ICCA Journal, Vol. 15, No. 1
  12. Re: random play by Ronald de Man, rgcc, November 28, 1996
  13. Re: computer chess "oracle" ideas... by Ronald de Man, rgcc, April 7, 1997, see also Re: mate threat extension/null move by Don Beal, CCC, October 04, 2004 » Mate Threat Extensions, Null Move and WAC booster
  14. Bradley–Terry model from Wikipedia
  15. Re: Move ordering for cheapest refutation by Mikko Aarnos, CCC, August 10, 2015
  16. Lazy sorting algorithm - Sorting on steroids by JohnWoe, CCC, February 03, 2022

Up one level