25,161
edits
Changes
MCαβ
,Created page with "'''Home * Search * MCαβ''' '''Monte-Carlo Alpha-Beta''', '''(MCαβ)'''<br/> is a Best-First search algorithm based on Monte-Carlo Tree S..."
'''[[Main Page|Home]] * [[Search]] * MCαβ'''
'''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-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>.
<span id="Four Phases"></span>
=Four Phases=
MCαβ can be divided into four strategic phases, repeated as long as there is time left:<span id="Four Phases"></span>
# In the Selection phase the tree is traversed from the [[Root|root node]] until it selects a [[Leaf Node|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]]
* [[Minimax]]
* [[Monte-Carlo Tree Search]]
* [[SSS* and Dual*#SSStarandDualStarAsMT|MT-SSS*]]
* [[Bojun Huang#Rollout|Rollout Paradigm]]
<span id="Publications"></span>
=Publications=
* [[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]
* [[Cameron Browne]], [[Edward Powley]], [[Daniel Whitehouse]], [[Simon Lucas]], [[Peter Cowling]], [[Philipp Rohlfshagen]], [[Stephen Tavener]], [[Diego Perez]], [[Spyridon Samothrakis]], [[Simon Colton]] ('''2012'''). ''[http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=6145622&url=http%3A%2F%2Fieeexplore.ieee.org%2Fiel5%2F4804728%2F6169178%2F06145622.pdf%3Farnumber%3D6145622 A Survey of Monte Carlo Tree Search Methods]''. [[IEEE#TOCIAIGAMES|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''. [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]]
* [[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 » [[LCZero]]</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]
=Forum Posts=
* [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://www.talkchess.com/forum/viewtopic.php?t=66280&start=67 Re: Announcing lczero] by [[Daniel Shawul]], [[CCC]], January 21, 2018 » [[LCZero]]
* [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]]
=References=
<references />
'''[[Search|Up one level]]'''
'''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-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>.
<span id="Four Phases"></span>
=Four Phases=
MCαβ can be divided into four strategic phases, repeated as long as there is time left:<span id="Four Phases"></span>
# In the Selection phase the tree is traversed from the [[Root|root node]] until it selects a [[Leaf Node|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]]
* [[Minimax]]
* [[Monte-Carlo Tree Search]]
* [[SSS* and Dual*#SSStarandDualStarAsMT|MT-SSS*]]
* [[Bojun Huang#Rollout|Rollout Paradigm]]
<span id="Publications"></span>
=Publications=
* [[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]
* [[Cameron Browne]], [[Edward Powley]], [[Daniel Whitehouse]], [[Simon Lucas]], [[Peter Cowling]], [[Philipp Rohlfshagen]], [[Stephen Tavener]], [[Diego Perez]], [[Spyridon Samothrakis]], [[Simon Colton]] ('''2012'''). ''[http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=6145622&url=http%3A%2F%2Fieeexplore.ieee.org%2Fiel5%2F4804728%2F6169178%2F06145622.pdf%3Farnumber%3D6145622 A Survey of Monte Carlo Tree Search Methods]''. [[IEEE#TOCIAIGAMES|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''. [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]]
* [[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 » [[LCZero]]</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]
=Forum Posts=
* [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://www.talkchess.com/forum/viewtopic.php?t=66280&start=67 Re: Announcing lczero] by [[Daniel Shawul]], [[CCC]], January 21, 2018 » [[LCZero]]
* [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]]
=References=
<references />
'''[[Search|Up one level]]'''
