Difference between revisions of "MCαβ"

From Chessprogramming wiki
Jump to: navigation, search
Line 24: 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]]

Revision as of 19:04, 16 July 2020

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].

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