Difference between revisions of "MCαβ"
GerdIsenberg (talk | contribs) |
GerdIsenberg (talk | contribs) |
||
Line 33: | Line 33: | ||
* [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=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]] | ||
+ | |||
+ | =External Links= | ||
+ | * [[:Category:Larry Coryell|Larry Coryell]] & [[:Category:The Eleventh House|The Eleventh House]] - [https://www.discogs.com/composition/f03f166e-3026-45ed-8b52-fe9999a5cfae-Funky-Waltz Funky Waltz], [https://en.wikipedia.org/wiki/Oslo Oslo] 1975, [https://en.wikipedia.org/wiki/YouTube YouTube] Video | ||
+ | : feat. [https://de.wikipedia.org/wiki/Mike_Lawrence Mike Lawrence], [[:Category:Alphonse Mouzon|Alphonse Mouzon]], [[:Category:John Lee|John Lee]], [https://www.discogs.com/artist/138771-Mike-Mandel Mike Mandel] | ||
+ | : {{#evu:https://www.youtube.com/watch?v=_2BfZy6WT3c|alignment=left|valignment=top}} | ||
=References= | =References= | ||
Line 38: | Line 43: | ||
'''[[Search|Up one level]]''' | '''[[Search|Up one level]]''' | ||
+ | [[Category:Larry Coryell]] | ||
+ | [[Category:John Lee]] | ||
+ | [[Category:Alphonse Mouzon]] | ||
+ | [[Category:The Eleventh House]] |
Revision as of 23:15, 13 October 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
External Links
- Larry Coryell & The Eleventh House - Funky Waltz, Oslo 1975, YouTube Video
- feat. Mike Lawrence, Alphonse Mouzon, John Lee, Mike Mandel
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