Difference between revisions of "MCαβ"
GerdIsenberg (talk | contribs) |
m |
||
| (8 intermediate revisions by 2 users not shown) | |||
| Line 2: | Line 2: | ||
'''Monte-Carlo Alpha-Beta''', '''(MCαβ)'''<br/> | '''Monte-Carlo Alpha-Beta''', '''(MCαβ)'''<br/> | ||
| − | is a [[Best-First|Best-First search]] algorithm based on [[Monte-Carlo Tree Search]] and a shallow [[Alpha-Beta|alpha-beta]] [[Depth-First|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- | + | is a [[Best-First|Best-First search]] algorithm based on [[Monte-Carlo Tree Search]] and a shallow [[Alpha-Beta|alpha-beta]] [[Depth-First|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|Best-first minimax search]] proposed by [[Richard Korf]] and [[Max Chickering]] <ref>[[Richard Korf]], [[Max Chickering]] ('''1996'''). ''[https://www.microsoft.com/en-us/research/publication/best-first-minimax-search/ Best-First Minimax Search]''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_(journal) Artificial Intelligence], Vol. 84, No 1-2</ref>, one distinction between the two might be that MCTS uses usually win/draw/loss scores and Best-First a score from a heuristic [[evaluation]] function. |
<span id="Four Phases"></span> | <span id="Four Phases"></span> | ||
=Four Phases= | =Four Phases= | ||
| Line 13: | Line 13: | ||
=See also= | =See also= | ||
* [[Alpha-Beta]] | * [[Alpha-Beta]] | ||
| + | * [[Best-First Minimax Search]] | ||
* [[Minimax]] | * [[Minimax]] | ||
* [[Monte-Carlo Tree Search]] | * [[Monte-Carlo Tree Search]] | ||
* [[SSS* and Dual*#SSStarandDualStarAsMT|MT-SSS*]] | * [[SSS* and Dual*#SSStarandDualStarAsMT|MT-SSS*]] | ||
| + | * [[Rocinante]] | ||
* [[Bojun Huang#Rollout|Rollout Paradigm]] | * [[Bojun Huang#Rollout|Rollout Paradigm]] | ||
| Line 22: | Line 24: | ||
* [[Richard Korf]], [[Max Chickering]] ('''1996'''). ''[https://www.microsoft.com/en-us/research/publication/best-first-minimax-search/ Best-First Minimax Search]''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_(journal) Artificial Intelligence], Vol. 84, No 1-2 | * [[Richard Korf]], [[Max Chickering]] ('''1996'''). ''[https://www.microsoft.com/en-us/research/publication/best-first-minimax-search/ Best-First Minimax Search]''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_(journal) 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]], [https://www.conftool.net/acg13/index.php/Nijssen-Playout_Search_for_Monte-Carlo_Tree_Search_in_Multi-Player_Games-113.pdf?page=downloadPaper&filename=Nijssen-Playout_Search_for_Monte-Carlo_Tree_Search_in_Multi-Player_Games-113.pdf&form_id=113&form_version=final pdf] | * [[Pim Nijssen]], [[Mark Winands]] ('''2011'''). ''Playout Search for Monte-Carlo Tree Search in Multi-Player Games''. [[Advances in Computer Games 13]], [https://www.conftool.net/acg13/index.php/Nijssen-Playout_Search_for_Monte-Carlo_Tree_Search_in_Multi-Player_Games-113.pdf?page=downloadPaper&filename=Nijssen-Playout_Search_for_Monte-Carlo_Tree_Search_in_Multi-Player_Games-113.pdf&form_id=113&form_version=final pdf] | ||
| − | * [[Cameron Browne]], [[Edward Powley]], [[Daniel Whitehouse]], [[Simon Lucas]], [[Peter Cowling]], [[Philipp Rohlfshagen]], [[Stephen Tavener]], [[Diego Perez]], [[Spyridon Samothrakis]], [[Simon Colton]] ('''2012'''). ''[ | + | * [[Cameron Browne]], [[Edward Powley]], [[Daniel Whitehouse]], [[Simon Lucas]], [[Peter Cowling]], [[Philipp Rohlfshagen]], [[Stephen Tavener]], [[Diego Perez]], [[Spyridon Samothrakis]], [[Simon Colton]] ('''2012'''). ''[https://ieeexplore.ieee.org/document/6145622 A Survey of Monte Carlo Tree Search Methods]''. [[IEEE#TOCIAIGAMES|IEEE Transactions on Computational Intelligence and AI in Games]], Vol. 4, No. 1, [http://ccg.doc.gold.ac.uk/ccg_old/papers/browne_tciaig12_1.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]] ('''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]] | ||
| Line 35: | Line 37: | ||
=External Links= | =External Links= | ||
| − | * [[:Category:Larry Coryell|Larry Coryell]] & [[:Category:The Eleventh House|The Eleventh House] | + | * [[:Category:Larry Coryell|Larry Coryell]] & [[:Category:The Eleventh House|The Eleventh House]], [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] | : 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= | + | : {{#evu:https://www.youtube.com/watch?v=Z9dYOoLqwmE|alignment=left|valignment=top}} |
=References= | =References= | ||
Latest revision as of 10:42, 8 October 2022
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], one distinction between the two might be that MCTS uses usually win/draw/loss scores and Best-First a score from a heuristic evaluation function.
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
- Alpha-Beta
- Best-First Minimax Search
- Minimax
- Monte-Carlo Tree Search
- MT-SSS*
- Rocinante
- 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, pdf
- 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, 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
