Draft:Move ordering
Prioritizing promising moves for speed.
From Wikipedia, the free encyclopedia
Move ordering is a core optimization used in search algorithms like alpha–beta pruning to effectively "rank" moves based on their estimated strength.[1][2] The idea is to analyze the more likely moves first; by doing so, the algorithm can find the optimal path through the game tree much more efficiently. Ultimately, the primary goal here is to maximize the number of beta cutoffs during the search[3], which drastically reduces the total number of positions that actually require calculation.[4]
 | Review waiting, please be patient.
This may take 8 weeks or more, since drafts are reviewed in no specific order. There are 3,295 pending submissions waiting for review.
Where to get help
How to improve a draft
You can also browse Wikipedia:Featured articles and Wikipedia:Good articles to find examples of Wikipedia's best writing on topics similar to your proposed article. Improving your odds of a speedy review To improve your odds of a faster review, tag your draft with relevant WikiProject tags using the button below. This will let reviewers know a new draft has been submitted in their area of interest. For instance, if you wrote about a female astronomer, you would want to add the Biography, Astronomy, and Women scientists tags. Editor resources
Reviewer tools
|
 | This is a draft article. It is a work in progress open to editing by anyone. Please ensure core content policies are met before publishing it as a live Wikipedia article. Find sources: Google (books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL Last edited by RightYiZheng (talk | contribs) 2 days ago. (Update)
This draft has been submitted and is currently awaiting review. |
Move ordering is used to optimize the search tree, primarily by ranking branches that are most likely to trigger an alpha–beta cutoff.[3] In the early phases of the search, ordering usually relies on static "tactical motifs", most notably MVV-LVA (Most Valuable Victim - Least Valuable Attacker) for captures, though checks and promotions are also ranked. This efficiency scales significantly when combined with iterative deepening; here, data gathered from shallower plys (like the "best move" found previously) is used to inform the move list for the next iteration.[5][a] To further improve pruning, most modern engines implement the killer move heuristic and history tables, which track specific "refutations" that have been successful in other branches of the tree.
Theoretical Background
The efficiency of a chess engine's search is almost entirely dependent on its ability to ignore "bad" moves as quickly as possible.[6] Theoretically, if an engine could always examine the best move first, the search space would effectively be reduced to its square root, a massive computational gain.[7][1] In practice, this is achieved through a combination of game theory and heuristic-based pruning.[8]
Alpha–Beta Search and Cutoffs
The minimax algorithm is used to determine the best possible move by assuming both players play optimally.[1] But a pure minimax search is exponentially expensive.[9] Alpha–beta pruning optimizes this by maintaining two values which are Alpha and Beta.[10] Alpha is the minimum score the maximizing player is assured of, and Beta is the maximum score the minimizing player can permit. A "cutoff" occurs when a branch is found to be so bad that it cannot possibly affect the final decision, allowing the engine to prune the branch. The goal of move ordering is to find these moves that cause a beta cutoff as early as possible in the search.
Iterative Deepening and Time Management
Engines use iterative deepening, a strategy where the search increases from depth 1 to the target depth the user requested.[11] Since the engine re-visits the same nodes multiple times, it is actually essential for move ordering. This approach serves as a critical time management tool; because the search can be terminated at any point, the engine still maintains a candidate move at all times in case of an sudden timeout.
See Also
- Killer heuristic, the heuristic used for improving move ordering.
- Iterative deepening
- Alpha–beta pruning
Notes
- IEEE Xplore gives the abstract, full text available at ResearchGate