Difference between revisions of "MCαβ"

From Chessprogramming wiki
Jump to: navigation, search
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-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>.
+
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'''). ''[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
+
* [[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]] - [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
+
* [[: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=_2BfZy6WT3c|alignment=left|valignment=top}}
+
: {{#evu:https://www.youtube.com/watch?v=Z9dYOoLqwmE|alignment=left|valignment=top}}
  
 
=References=  
 
=References=  

Latest revision as of 09:42, 8 October 2022

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], 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:

  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

Publications

Forum Posts

External Links

feat. Mike Lawrence, Alphonse Mouzon, John Lee, Mike Mandel

References

Up one level