Wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Chess - Programming - Move Ordering ======

Endeavour to search the best move first.

Moves like promotions and captures are far more likely to be good moves than putting a rook en-prise, or advancing the pawns protecting the king.

A basic move ordering scheme might look as follows:

  * Hash move (see previous section on Transposition Tables)
  * PV move associated with this ply, where legal.
  * Captures (including capturing promotions).
  * Quiet promotions.
  * Other moves.

If the opponent is trying out a move that places a piece en-prise, then frequently the best move is to capture the piece, gaining material for nothing.

It should be noted that the hash move and PV move will sometimes coincide, so care should be taken not to search the same move twice.

Try to improve the move ordering further by breaking down the captures category.

Some captures are better than others; 

  * A pawn capturing a queen is almost always an excellent move
  * A rook capturing a pawn is dubious as the pawn may be defended.
  * We should therefore search the queen capture before the pawn capture.

Use the common MVV/LVA scheme for ordering captures, where MVV/LVA stands for Most Valuable Victim / Least Valuable Attacker.

  * We make the semi-arbitrary decision that the victim's value is a more important consideration, ordering queen captures first, then rook captures and so on down to pawns.
  * Within the set of queen captures, we search pawn moves first, then knight moves, and so on up to queens.

Another method of improving move ordering, this time for quiet moves, is to reuse the piece-square tables.

  * If a piece is on a square valued at -10 and can move to a square valued at +30, this is probably a reasonable move (net gain +40) and so should be searched before moves with a lesser gain.

Move ordering will not always be correct.

  * Capturing the opponent's queen with a pawn will, on occasion, lead to being checkmated.
  * However, the important point is that in the vast majority of positions where such a capture is possible, it is a vastly superior move to anything else and searching it early saves us a great deal of effort.
  * A good target to aim for is achieving a cutoff with the first move on around 90% of all positions searched.


----

Class MoveOrdering

  * Methods that sort and return a sorted list of moves.
  * Iterate through the list and assign each move a weight based on its characteristics.
  * Make use of the Move encoding bits to determine the type of move.

----

[[Chess:Programming:Move Ordering:Most Valuable Victim/Least Valuable Attacker (MVV/LVA)|Most Valuable Victim/Least Valuable Attacker (MVV/LVA)]]

[[Chess:Programming:Move Ordering:Static Exchange Evaluation (SEE)|Static Exchange Evaluation (SEE)]]


----

  * Add an extensive move ordering algorithm to the root moves.
    * Does not matter how expensive this is, since it will not be done much, compared to to the millions of ordinary nodes.

----

  * Break out after the 1st or 2nd ply from the AlphaBeta search and take top few candidates?

----

  * Do a Quiescence search on all moves and order by the values it returns.
    * Bring the PV move up front if not there already.
    * Count the nodes each move causes and order by that.
    * Try various combinations (Quiescence score with some scale for lower plies, and node counts deeper depths).

----

  * Cut all moves with a negative SEE-score in the quiescence search.
    * These moves are extremely unlikely to prove useful for anything, at least that the quiescence search can detect.

----

===== References =====

https://www.ics.uci.edu/~eppstein/180a/970424.html