Move Ordering

From Chessprogramming wiki
Revision as of 08:43, 30 April 2018 by GerdIsenberg (talk | contribs)
Jump to: navigation, search

Home * Search * Move Ordering

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 [9] inspired by Jos Uiterwijk's Countermove Heuristic article [10], 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 [11] [12].

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 ...

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

External Links

References

  1. Selim Akl, Monroe Newborn (1977). The Principal Continuation and the Killer Heuristic.1977 ACM Annual Conference Proceedings
  2. Jonathan Schaeffer (1983). The History Heuristic. ICCA Journal, Vol. 6, No. 3
  3. Mark Winands, Erik van der Werf, Jaap van den Herik, Jos Uiterwijk (2006). The Relative History Heuristic. CG 2004, pdf
  4. Move Ordering in Rebel by Ed Schröder, also available as pdf
  5. Jos Uiterwijk (1992). The Countermove Heuristic. ICCA Journal, Vol. 15, No. 1
  6. Dap Hartmann (1988). Butterfly Boards. ICCA Journal, Vol. 11, Nos. 2/3
  7. Levente Kocsis, Jos Uiterwijk, Jaap van den Herik (2001). Move Ordering using Neural Networks. IEA/AIE 2001, LNCS 2070
  8. Levente Kocsis, Jos Uiterwijk, Eric Postma, Jaap van den Herik (2002). The Neural MoveMap Heuristic in Chess. CG 2002
  9. Ingo Althöfer (1992). Move Ordering by Time Ordering. Correspondence, ICCA Journal, Vol. 15, No. 2
  10. Jos Uiterwijk (1992). The Countermove Heuristic. ICCA Journal, Vol. 15, No. 1
  11. Re: random play by Ronald de Man, rgcc, November 28, 1996
  12. 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
  13. Bradley–Terry model from Wikipedia
  14. Re: Move ordering for cheapest refutation by Mikko Aarnos, CCC, August 10, 2015

Up one level