Best-First Minimax Search

Home * Search * Best-First Minimax Search

Best-First Minimax Search, (BFMMS)
is a Best-First search algorithm based on Best-First and a shallow alpha-beta depth-first-search proposed by Richard Korf and Max Chickering .

BFMMS, MCαβ, the Rollout Paradigm and further MCTS-minimax hybrids share the same idea, to combine Best-First with Depth-First searches.

Four Phases

BFMMS can be divided into four strategic phases, repeated as long as there is time left:

1. In the Selection phase the best node is selected from the game tree via node score from the root node until it selects an unexpanded node
2. The Expansion strategy adds the unexpanded child nodes to the tree
3. The Playout phase performs a shallow alpha-beta search to get a node score
4. The Backpropagation strategy propagates the score through the tree

See also

• KomodoMCTS
• MCαβ
• Rollout Paradigm

Publications

• Richard Korf, Max Chickering (1996). Best-First Minimax Search. Artificial Intelligence, Vol. 84, No 1-2
• Yaron Shoham, Sivan Toledo (2001). Parallel Randomized Best-First Minimax Search

Forum Posts

• MCTS without random playout? by Antonio Torrecillas, CCC, January 01, 2012 » B*
• Help with Best-First Select-Formula by Srdja Matovic, CCC, July 23, 2012
• Re: Announcing lczero by Daniel Shawul, CCC, January 21, 2018 » Leela Chess Zero
• Alpha-Beta as a rollouts algorithm by Daniel Shawul, CCC, January 25, 2018 » Alpha-Beta, Monte-Carlo Tree Search, Scorpio
• Re: MCTS vs Alpha-beta by Srdja Matovic, CCC, August 03, 2024

References

Up one level