Home * Search * MCαβ

Monte-Carlo Alpha-Beta, (MCαβ)
is a Best-First search algorithm based on Monte-Carlo Tree Search and a shallow alpha-beta depth-first-search. It is used in Lines of Action and in conjunction with UCT (Upper Confidence bounds applied to Trees) also in Chess. It is similar to the the Best-First Minimax-Search proposed by Richard Korf and Max Chickering ^[1].

Four Phases

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

1. In the Selection phase the tree is traversed from the root node until it selects a leaf node that is not added to the tree yet
2. The Expansion strategy adds the leaf node to the tree
3. The Playout phase performs a shallow alpha-beta search
4. The Backpropagation strategy propagates the results through the tree

See also

• Alpha-Beta
• Minimax
• Monte-Carlo Tree Search
• MT-SSS*
• Rollout Paradigm

Publications

• Richard Korf, Max Chickering (1996). Best-First Minimax Search. Artificial Intelligence, Vol. 84, No 1-2
• Pim Nijssen, Mark Winands (2011). Playout Search for Monte-Carlo Tree Search in Multi-Player Games. Advances in Computer Games 13, pdf
• Cameron Browne, Edward Powley, Daniel Whitehouse, Simon Lucas, Peter Cowling, Philipp Rohlfshagen, Stephen Tavener, Diego Perez, Spyridon Samothrakis, Simon Colton (2012). A Survey of Monte Carlo Tree Search Methods. IEEE Transactions on Computational Intelligence and AI in Games, Vol. 4, No. 1
• Hendrik Baier, Mark Winands (2013). Monte-Carlo Tree Search and minimax hybrids. CIG 2013, pdf
• Hendrik Baier, Mark Winands (2014). Monte-Carlo Tree Search and Minimax Hybrids with Heuristic Evaluation Functions. ECAI CGW 2014
• Bojun Huang (2015). Pruning Game Tree by Rollouts. AAAI » MCTS, MT-SSS*, Rollout Paradigm ^[2]
• Hendrik Baier (2017). A Rollout-Based Search Algorithm Unifying MCTS and Alpha-Beta. Computer Games

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 » LCZero
• Alpha-Beta as a rollouts algorithm by Daniel Shawul, CCC, January 25, 2018 » Alpha-Beta, Monte-Carlo Tree Search, Scorpio

References

1. ^ Richard Korf, Max Chickering (1996). Best-First Minimax Search. Artificial Intelligence, Vol. 84, No 1-2
2. ^ Re: Announcing lczero by Daniel Shawul, CCC, January 21, 2018 » LCZero

What links here?

Up one level