Draft:Move ordering

Review waiting, please be patient. This may take 2 months or more, since drafts are reviewed in no specific order. There are 4,332 pending submissions waiting for review. If the submission is accepted, then this page will be moved into the article space. If the submission is declined, then the reason will be posted here. In the meantime, you can continue to improve this submission by editing normally. Where to get help If you need help editing or submitting your draft, please ask us a question at the AfC Help Desk or get live help from experienced editors. These venues are only for help with editing and the submission process, not to get reviews. If you need feedback on your draft, or if the review is taking a lot of time, you can try asking for help on the talk page of a relevant WikiProject. Some WikiProjects are more active than others so a speedy reply is not guaranteed. How to improve a draft Wikipedia:Contributing to Wikipedia – a basic overview on how to edit Wikipedia. Help:Wikitext – how to use the markup Help:Referencing for beginners – how to include references Wikipedia:Article development – how to develop your article Wikipedia:Writing better articles – how to improve your article Wikipedia:Verifiability – make sure your article includes reliable third-party sources 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. Add tags to your draft Editor resources Easy tools: Citation bot (help) | Advanced: Fix bare URLs Reviewer tools Instructions · What links here · Move ordering (talk: + · bio) · (log) · Copyvios report · reFill · Citation Bot · (Search: Google, Wikipedia) · Submitted 36 days ago by RightYiZheng (talk: D · +) · Last edited 6 days ago by RightYiZheng

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 Easy tools: Citation bot (help) | Advanced: Fix bare URLs · Article logs · Draft logs. Last edited by RightYiZheng (talk | contribs) 6 days ago. (Update) This draft has been submitted and is currently awaiting review.

Move ordering refers to the practice of selecting the most promising moves first during game-tree search (especially in computer chess).^[1][2] In minimax searches with alpha–beta pruning, good move ordering is important, examining stronger moves early causes cutoffs that eliminate subtrees, vastly reducing the number of nodes searched. In the ideal case of perfect move ordering the search complexity drops from O ( b d ) {\displaystyle O(b^{d})} to approximately O ( b d / 2 ) {\displaystyle O(b^{d/2})} , effectively halving the effective branching factor to b {\displaystyle {\sqrt {b}}} and allowing roughly twice the search depth for a given computational effort.^[3] Claude Shannon observed that although a typical chess position may have on the order of 30 legal moves, effective pruning and heuristics reduce the useful branching factor to only a few.^[4]

The idea of ordering moves came before computers. In his 1950 seminal paper "Programming a Computer for Playing Chess",^[5] Claude Shannon noted the enormous size of the full game tree (estimated at 10 120 {\displaystyle 10^{120}} nodes) and suggested that a simple evaluation coupled with search all variations to a fixed depth would be impractical. Shannon saw that any chess program would need to focus on selected moves and prune aggressively to be useful. The formal alpha–beta algorithm appeared in the late 1950s and 1960s as a way to prune branches without changing the minimax result. Early on, it was noted that alpha–beta's pruning power depends entirely on the order in which moves are examined. In 1963, Alexander Brudno independently described alpha–beta-like search and noted that best-case node counts occur when moves are tried in the right order; by the 1970s researchers such as Donald Knuth and Ronald Moore had mathematically analyzed alpha–beta and shown that under perfect ordering its time is O ( b d / 2 ) {\displaystyle O(b^{d/2})} .^[6]

In the 1970s and 1980s the major practical heuristics for move ordering were introduced. The use of iterative deepening was rediscovered in chess programs and found to significantly improve move ordering for deeper searches. The idea was to use the best move found at shallow depth as the first move in the next deeper search.^[7] Transposition tables (Mac Hack by Richard Greenblatt in 1966 first used a hash) allowed the program to store the best move for each position and reuse it as the first choice on subsequent visits.^[8] In 1968 Barbara Liskov and others independently suggested storing moves that caused beta cutoffs. This eventually became known as the killer heuristic. In 1983 Jonathan Schaeffer proposed the history heuristic. Schaeffer showed that the history scores outperformed simpler heuristics.

The efficiency of a chess engine's search is almost entirely dependent on its ability to ignore "bad" moves as quickly as possible. Theoretically, if an engine could always examine the best move first, the search space would effectively be reduced to its square root.^[1] This is achieved through a combination of game theory and heuristic-based pruning.^[9]

A pure minimax game-tree search explores all moves to a fixed depth, which is exponentially expensive.^[10] Alpha–beta pruning improves this by carrying two bounds which are Alpha (α) and Beta (β).^[11] Alpha is the minimum score the maximizing player is assured of, and Beta is the maximum score the minimizing player can permit. Whenever a node's value cannot possibly influence the final decision because it is worse than a previously examined move, the branch is cut off. This has a probability to have the same result as full minimax but with fewer nodes.

Iterative deepening depth-first search is commonly used. The engine repeatedly searches with increasing depth limits, using the best move from depth d {\displaystyle d} as the first move to try at depth d + 1 {\displaystyle d+1} .^[12] This almost produces a strong initial bound (alpha or beta) on the first move, which narrows the window for the rest of the search. Iterative deepening converts a depth-first search into something akin to a best-first search by leveraging past results. When a transposition table contains an entry for the current position, its stored best move is tried first.^[13] After a transposition move is considered, typical ordering heuristics prioritize captures and checks, since forcing tactical moves often lead to large advantages or immediate cut offs.^[14]

Engines sort capture moves by the Most Valuable Victim–Least Valuable Aggressor (MVV-LVA) heuristic.^[8] To avoid obviously losing trades, a static exchange evaluation (SEE) is often applied to prune captures that reduce material balance. If the forcing moves do not produce a cutoff, the engine then tries its stored killer moves, which are tried at early depth. If a non-killer move causes a cutoff, it becomes a new killer. Finally, any remaining quiet moves are ordered by their history heuristic scores, which accumulate bonuses when a move causes a cutoff.^[15] Each time a move causes a cutoff anywhere in the search, its history score increases. Thus moves that have historically caused cutoffs rank higher in future ordering.

Researchers have developed several refinements beyond the basic schemes. Countermove heuristic assumes that many moves have a "natural" response, irrespective of the actual position.^[16][17] Other miscellaneous techniques such as "Butterfly boards"^[18] and "last-best-reply" heuristics are related ideas that exploit local search history. Some engines use machine learning, early work by Kocsis et al. and Greer applied neural networks to predict move values or ordering. Most strong engines still rely on the simple set of PV moves, hash moves, MVV-LVA capture sorting, killer and history tables.

• Killer heuristic, the heuristic used for improving move ordering.
• Iterative deepening
• Alpha–beta pruning

• Rustic Chess

Category:Computer chess Category:Game theory