Differences

This shows you the differences between two versions of the page.

--- chess:programming:move_ordering [2022/01/06 16:46] – peter
+++ chess:programming:move_ordering [2022/01/07 10:33] (current) – peter
@@ Line 1: / Line 1: @@
 ====== 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.
-[[Chess:Programming:Move Ordering|Move Ordering]]
+----
+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