Home *Search * Best-First Minimax Search

Best-First Minimax Search,(BFMMS)
is aBest-First search algorithm based onBest-First and a shallowalpha-betadepth-first-search proposed byRichard Korf andMax Chickering^[1].

BFMMS,MCαβ, theRollout Paradigm and furtherMCTS-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 theroot 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? byAntonio Torrecillas,CCC, January 01, 2012 »B*
• Help with Best-First Select-Formula bySrdja Matovic,CCC, July 23, 2012
• Re: Announcing lczero byDaniel Shawul,CCC, January 21, 2018 »Leela Chess Zero
• Alpha-Beta as a rollouts algorithm byDaniel Shawul,CCC, January 25, 2018 »Alpha-Beta,Monte-Carlo Tree Search,Scorpio
• Re: MCTS vs Alpha-beta bySrdja Matovic,CCC, August 03, 2024

References

Up one level