Best-First Minimax Search
From Chessprogramming wiki
Jump to:navigation,search
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:
- 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
- The Expansion strategy adds the unexpanded child nodes to the tree
- The Playout phase performs a shallow alpha-beta search to get a node score
- The Backpropagation strategy propagates the score through the tree
See also
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
- ↑Richard Korf,Max Chickering (1996).Best-First Minimax Search.Artificial Intelligence, Vol. 84, No 1-2

