# Difference between revisions of "MCαβ"

GerdIsenberg (talk | contribs) (Created page with "'''Home * Search * MCαβ''' '''Monte-Carlo Alpha-Beta''', '''(MCαβ)'''<br/> is a Best-First search algorithm based on Monte-Carlo Tree S...") |
GerdIsenberg (talk | contribs) |
||

Line 25: | Line 25: | ||

* [[Hendrik Baier]], [[Mark Winands]] ('''2013'''). ''Monte-Carlo Tree Search and minimax hybrids''. [http://dblp.uni-trier.de/db/conf/cig/cig2013.html#BaierW13 CIG 2013], [https://dke.maastrichtuniversity.nl/m.winands/documents/paper%2049.pdf pdf] | * [[Hendrik Baier]], [[Mark Winands]] ('''2013'''). ''Monte-Carlo Tree Search and minimax hybrids''. [http://dblp.uni-trier.de/db/conf/cig/cig2013.html#BaierW13 CIG 2013], [https://dke.maastrichtuniversity.nl/m.winands/documents/paper%2049.pdf pdf] | ||

* [[Hendrik Baier]], [[Mark Winands]] ('''2014'''). ''[http://link.springer.com/chapter/10.1007%2F978-3-319-14923-3_4 Monte-Carlo Tree Search and Minimax Hybrids with Heuristic Evaluation Functions]''. [[ECAI CGW 2014]] | * [[Hendrik Baier]], [[Mark Winands]] ('''2014'''). ''[http://link.springer.com/chapter/10.1007%2F978-3-319-14923-3_4 Monte-Carlo Tree Search and Minimax Hybrids with Heuristic Evaluation Functions]''. [[ECAI CGW 2014]] | ||

− | * [[Bojun Huang]] ('''2015'''). ''[https://www.semanticscholar.org/paper/Pruning-Game-Tree-by-Rollouts-Huang/a38b358745067f71a9c780db117ae2471e693d63 Pruning Game Tree by Rollouts]''. [[AAAI]] » [[Monte-Carlo Tree Search|MCTS]], [[SSS* and Dual*#SSStarandDualStarAsMT|MT-SSS*]], [[Bojun Huang#Rollout|Rollout Paradigm]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=66280&start=67 Re: Announcing lczero] by [[Daniel Shawul]], [[CCC]], January 21, 2018 » [[ | + | * [[Bojun Huang]] ('''2015'''). ''[https://www.semanticscholar.org/paper/Pruning-Game-Tree-by-Rollouts-Huang/a38b358745067f71a9c780db117ae2471e693d63 Pruning Game Tree by Rollouts]''. [[AAAI]] » [[Monte-Carlo Tree Search|MCTS]], [[SSS* and Dual*#SSStarandDualStarAsMT|MT-SSS*]], [[Bojun Huang#Rollout|Rollout Paradigm]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=66280&start=67 Re: Announcing lczero] by [[Daniel Shawul]], [[CCC]], January 21, 2018 » [[Leela Chess Zero]]</ref> |

* [[Hendrik Baier]] ('''2017'''). ''[https://link.springer.com/chapter/10.1007/978-3-319-57969-6_5 A Rollout-Based Search Algorithm Unifying MCTS and Alpha-Beta]''. [https://link.springer.com/book/10.1007%2F978-3-319-57969-6 Computer Games] | * [[Hendrik Baier]] ('''2017'''). ''[https://link.springer.com/chapter/10.1007/978-3-319-57969-6_5 A Rollout-Based Search Algorithm Unifying MCTS and Alpha-Beta]''. [https://link.springer.com/book/10.1007%2F978-3-319-57969-6 Computer Games] | ||

Line 31: | Line 31: | ||

* [http://www.talkchess.com/forum/viewtopic.php?t=41730 MCTS without random playout?] by [[Antonio Torrecillas]], [[CCC]], January 01, 2012 » [[B*]] | * [http://www.talkchess.com/forum/viewtopic.php?t=41730 MCTS without random playout?] by [[Antonio Torrecillas]], [[CCC]], January 01, 2012 » [[B*]] | ||

* [http://talkchess.com/forum/viewtopic.php?t=44165 Help with Best-First Select-Formula ] by [[Srdja Matovic]], [[CCC]], July 23, 2012 | * [http://talkchess.com/forum/viewtopic.php?t=44165 Help with Best-First Select-Formula ] by [[Srdja Matovic]], [[CCC]], July 23, 2012 | ||

− | * [http://www.talkchess.com/forum/viewtopic.php?t=66280&start=67 Re: Announcing lczero] by [[Daniel Shawul]], [[CCC]], January 21, 2018 » [[ | + | * [http://www.talkchess.com/forum/viewtopic.php?t=66280&start=67 Re: Announcing lczero] by [[Daniel Shawul]], [[CCC]], January 21, 2018 » [[Leela Chess Zero]] |

* [http://www.talkchess.com/forum/viewtopic.php?t=66414 Alpha-Beta as a rollouts algorithm] by [[Daniel Shawul]], [[CCC]], January 25, 2018 » [[Alpha-Beta]], [[Monte-Carlo Tree Search]], [[Scorpio]] | * [http://www.talkchess.com/forum/viewtopic.php?t=66414 Alpha-Beta as a rollouts algorithm] by [[Daniel Shawul]], [[CCC]], January 25, 2018 » [[Alpha-Beta]], [[Monte-Carlo Tree Search]], [[Scorpio]] | ||

## Revision as of 16:44, 23 July 2018

**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:

- 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
- The Expansion strategy adds the leaf node to the tree
- The Playout phase performs a shallow alpha-beta search
- The Backpropagation strategy propagates the results through the tree

# See also

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

# References

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