25,161
edits
Changes
UCT
,Created page with "'''Home * Search * Monte-Carlo Tree Search * UCT''' '''UCT''' ('''U'''pper '''C'''onfidence bounds applied to '''T'''rees),<br/> a popular Algorithms..."
'''[[Main Page|Home]] * [[Search]] * [[Monte-Carlo Tree Search]] * UCT'''
'''UCT''' ('''U'''pper '''C'''onfidence bounds applied to '''T'''rees),<br/>
a popular [[Algorithms|algorithm]] that deals with the flaw of Monte-Carlo Tree Search, when a program may favor a losing move with only one or a few forced refutations, but due to the vast majority of other moves provides a better random playout score than other, better moves. UCT was introduced by [[Levente Kocsis]] and [[Csaba Szepesvári]] in 2006 <ref>[[Levente Kocsis]], [[Csaba Szepesvári]] ('''2006'''). ''[http://www.computer-go.info/resources/bandit.html Bandit based Monte-Carlo Planning]'' ECML-06, LNCS/LNAI 4212, [http://www.sztaki.hu/%7Eszcsaba/papers/ecml06.pdf pdf]</ref>, which accelerated the Monte-Carlo revolution in computer [[Go]] <ref>[[Sylvain Gelly]], [[Marc Schoenauer]], [[Michèle Sebag]], [[Olivier Teytaud]], [[Levente Kocsis]], [[David Silver]], [[Csaba Szepesvári]] ('''2012'''). ''[http://dl.acm.org/citation.cfm?id=2093548.2093574 The Grand Challenge of Computer Go: Monte Carlo Tree Search and Extensions]''. [[ACM#Communications|Communications of the ACM]], Vol. 55, No. 3, [http://www0.cs.ucl.ac.uk/staff/D.Silver/web/Applications_files/grand-challenge.pdf pdf preprint]</ref> and games difficult to [[Evaluation|evaluate]] statically. If given infinite time and [[Memory|memory]], UCT theoretically converges to [[Minimax]].
=Selection=
In UCT, upper [https://en.wikipedia.org/wiki/Confidence_interval confidence bounds] (UCB1) guide the selection of a node <ref>see UCB1 in [[Peter Auer]], [[Nicolò Cesa-Bianchi]], [[Paul Fischer]] ('''2002'''). ''[http://link.springer.com/article/10.1023%2FA%3A1013689704352 Finite-time Analysis of the Multiarmed Bandit Problem]''. [https://en.wikipedia.org/wiki/Machine_Learning_%28journal%29 Machine Learning], Vol. 47, No. 2</ref>, treating selection as a [https://en.wikipedia.org/wiki/Multi-armed_bandit multi-armed bandit problem], where the crucial tradeoff the [https://en.wikipedia.org/wiki/Gambling gambler] faces at each trial is between [https://en.wikipedia.org/wiki/Monte_Carlo_tree_search#Exploration_and_exploitation exploration and exploitation] - [https://en.wikipedia.org/wiki/Exploitation_%28disambiguation%29 exploitation] of the [https://en.wikipedia.org/wiki/Slot_machine slot machine] that has the highest expected payoff and [https://en.wikipedia.org/wiki/Exploration exploration] to get more information about the expected payoffs of the other machines. Child node j is selected which maximizes the UCT Evaluation:
[[FILE:UCTFormula.jpg|none|border|text-bottom]]
where:
* X<span style="font-size: 80%; vertical-align: sub;">j</span> is the [[Match Statistics#ratio|win ratio]] of the child
* n is the number of times the parent has been visited
* n<span style="font-size: 80%; vertical-align: sub;">j</span> is the number of times the child has been visited
* C is a constant to adjust the amount of exploration and incorporates the sqrt(2) from the UCB1 formula
The first component of the UCB1 formula above corresponds to exploitation, as it is high for moves with high average win ratio. The second component corresponds to exploration, since it is high for moves with few simulations. Most contemporary implementations of MCTS are based on some variant of UCT <ref>[https://en.wikipedia.org/wiki/Monte_Carlo_tree_search#Exploration_and_exploitation Exploration and exploitation - in Monte Carlo tree search from Wikipedia]</ref>. Modifications have been proposed, with the aim of shortening the time to find good moves. They can be divided into improvements based on expert knowledge and into domain-independent improvements in the playouts, and in building the tree in modifying the exploitation part of the UCB1 formula, for instance in [https://en.wikipedia.org/wiki/Monte_Carlo_tree_search#Improvements Rapid Action Value Estimation] ('''RAVE''') <ref> [[Sylvain Gelly]], [[David Silver]] ('''2011'''). ''Monte-Carlo tree search and rapid action value estimation in computer Go''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 175, No. 11, [http://www0.cs.ucl.ac.uk/staff/D.Silver/web/Applications_files/mcrave.pdf preprint as pdf]</ref> considering [[Transposition|transpositions]].
=Quotes=
==Gian-Carlo Pascutto==
Quote by [[Gian-Carlo Pascutto]] in 2010 <ref>[http://computer-go.org/pipermail/computer-go/2010-June/000376.html Re: Chess vs Go // AI vs IA] by [[Gian-Carlo Pascutto]], June 02, 2010</ref>:
There is no significant difference between an [[Alpha-Beta|alpha-beta search]] with heavy [[Late Move Reductions|LMR]] and a [[Evaluation|static evaluator]] (current state of the art in [[Chess|chess]]) and an UCT searcher with a small exploration constant that does playouts (state of the art in [[Go|go]]).
The shape of the [[Search Tree|tree]] they search is very similar. The main breakthrough in Go the last few years was how to backup an uncertain Monte Carlo score. This was solved. For chess this same problem was solved around the time [[Quiescence Search|quiescent search]] was developed.
Both are producing strong programs and we've proven for both the methods that they scale in strength as hardware speed goes up.
So I would say that we've successfully adopted the simple, brute force methods for chess to Go and they already work without increases in computer speed. The increases will make them progressively stronger though, and with further software tweaks they will eventually surpass humans.
==Raghuram Ramanujan et al.==
Quote by [[Raghuram Ramanujan]], [[Ashish Sabharwal]], and [[Bart Selman]] from their abstract ''On Adversarial Search Spaces and Sampling-Based Planning'' <ref>[[Raghuram Ramanujan]], [[Ashish Sabharwal]], [[Bart Selman]] ('''2010'''). ''[http://www.aaai.org/ocs/index.php/ICAPS/ICAPS10/paper/view/1458 On Adversarial Search Spaces and Sampling-Based Planning]''. [http://www.aaai.org/Press/Proceedings/icaps10.php ICAPS 2010]</ref>:
UCT has been shown to outperform traditional [[Minimax|minimax]] based approaches in several challenging domains such as [[Go]] and [[Kriegspiel]], although minimax search still prevails in other domains such as [[Chess]]. This work provides insights into the properties of adversarial search spaces that play a key role in the success or failure of UCT and similar sampling-based approaches. We show that certain "early loss" or "shallow trap" configurations, while unlikely in Go, occur surprisingly often in games like Chess (even in grandmaster games). We provide evidence that UCT, unlike minimax search, is unable to identify such traps in Chess and spends a great deal of time exploring much deeper game play than needed.
=See also=
* [[Match Statistics]]
* [[Jakob Erdmann#UCT|MC and UCT poster]] by [[Jakob Erdmann]]
* [[MCαβ]]
* [[Reinforcement Learning]]
=Publications=
==2000 ...==
* [[Peter Auer]], [[Nicolò Cesa-Bianchi]], [[Paul Fischer]] ('''2002'''). ''[http://link.springer.com/article/10.1023%2FA%3A1013689704352 Finite-time Analysis of the Multiarmed Bandit Problem]''. [https://en.wikipedia.org/wiki/Machine_Learning_%28journal%29 Machine Learning], Vol. 47, No. 2, [http://homes.di.unimi.it/~cesabian/Pubblicazioni/ml-02.pdf pdf]
==2005 ...==
'''2006'''
* [[Levente Kocsis]], [[Csaba Szepesvári]] ('''2006'''). ''[http://www.computer-go.info/resources/bandit.html Bandit based Monte-Carlo Planning]''. ECML-06, LNCS/LNAI 4212, [http://old.sztaki.hu/~szcsaba/papers/ecml06.pdf pdf]
* [[Levente Kocsis]], [[Csaba Szepesvári]], [[Jan Willemson]] ('''2006'''). ''Improved Monte-Carlo Search''. [http://www.sztaki.hu/~szcsaba/papers/cg06-ext.pdf pdf]
* [[Sylvain Gelly]], [[Yizao Wang]] ('''2006'''). ''Exploration exploitation in Go: UCT for Monte-Carlo Go''. [http://www.lri.fr/%7Egelly/paper/nips_exploration_exploitation_mogo.pdf pdf]
* [[Sylvain Gelly]], [[Yizao Wang]], [[Rémi Munos]], [[Olivier Teytaud]] ('''2006'''). ''Modification of UCT with Patterns in Monte-Carlo Go''. [http://hal.inria.fr/inria-00117266 INRIA]
'''2007'''
* [[Yizao Wang]], [[Sylvain Gelly]] ('''2007'''). ''Modifications of UCT and Sequence-Like Simulations for Monte-Carlo Go''. IEEE Symposium on Computational Intelligence and Games, Honolulu, USA, 2007, [http://www.stat.lsa.umich.edu/%7Eyizwang/publications/wang07modifications.pdf pdf]
* [[Shugo Nakamura]], [[Makoto Miwa]], [[Takashi Chikayama]] ('''2007'''). ''Improvement of UCT using evaluation function''. [http://www.computer-shogi.org/gpw/gpw12_e.html 12th Game Programming Workshop 2007]
* [[Tristan Cazenave]], [[Nicolas Jouandeau]] ('''2007'''). ''On the Parallelization of UCT''. [[CGW 2007]], [http://www.lamsade.dauphine.fr/%7Ecazenave/papers/parallelUCT.pdf pdf] » [[Parallel Search]]
* [[Jean-Yves Audibert]], [[Rémi Munos]], [[Csaba Szepesvári]] ('''2007'''). ''Tuning Bandit Algorithms in Stochastic Environments''. [http://certis.enpc.fr/~audibert/ucb_alt.pdf pdf]
'''2008'''
* [[Nathan Sturtevant]] ('''2008'''). ''[http://link.springer.com/chapter/10.1007/978-3-540-87608-3_4 An Analysis of UCT in Multi-player Games]''. [[CG 2008]]
* [[Guillaume Chaslot]], [[Mark Winands]], [[Jaap van den Herik]] ('''2008'''). ''[http://link.springer.com/chapter/10.1007/978-3-540-87608-3_6 Parallel Monte-Carlo Tree Search]''. [[CG 2008]], [https://dke.maastrichtuniversity.nl/m.winands/documents/multithreadedMCTS2.pdf pdf]
'''2009'''
* [[Rémi Coulom]] ('''2009'''). ''The Monte-Carlo Revolution in Go''. JFFoS'2008: Japanese-French Frontiers of Science Symposium, [http://remi.coulom.free.fr/JFFoS/JFFoS.pdf slides as pdf]
* [[Fabien Teytaud]], [[Olivier Teytaud]] ('''2009'''). ''Creating an Upper-Confidence-Tree program for Havannah''. [[Advances in Computer Games 12]], [http://hal.inria.fr/docs/00/38/05/39/PDF/hav.pdf inria-00380539 as pdf] » [[Havannah]]
==2010 ...==
* [[Jean Méhat]], [[Tristan Cazenave]] ('''2010'''). ''Combining UCT and Nested Monte-Carlo Search for Single-Player General Game Playing''. [[IEEE#TOCIAIGAMES|IEEE Transactions on Computational Intelligence and AI in Games]], Vol. 2, No. 4, [http://www.lamsade.dauphine.fr/~cazenave/papers/ggp2009.pdf pdf 2009] » [[General Game Playing]]
* [[Raghuram Ramanujan]], [[Ashish Sabharwal]], [[Bart Selman]] ('''2010'''). ''[http://www.aaai.org/ocs/index.php/ICAPS/ICAPS10/paper/view/1458 On Adversarial Search Spaces and Sampling-Based Planning]''. [http://www.aaai.org/Press/Proceedings/icaps10.php ICAPS 2010] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=66125 Search traps in MCTS and chess] by [[Daniel Shawul]], [[CCC]], December 25, 2017</ref>
* [[Damien Pellier]], [[Bruno Bouzy]], [[Marc Métivier]] ('''2010'''). ''An UCT Approach for Anytime Agent-based Planning''. [http://www.springer.com/de/book/9783642123832 PAAMS'10], [http://www.mi.parisdescartes.fr/~bouzy/publications/pellier-bouzy-metivier-paams10.pdf pdf]
* [[Thomas J. Walsh]], [[Sergiu Goschin]], [[Michael L. Littman]] ('''2010'''). ''Integrating sample-based planning and model-based reinforcement learning.'' [[AAAI]], [https://pdfs.semanticscholar.org/bdc9/bfb6ecc6fb5afb684df03d7220c46ebdbf4e.pdf pdf] » [[Reinforcement Learning]]
'''2011'''
* [[Junichi Hashimoto]], [[Akihiro Kishimoto]], [[Kazuki Yoshizoe]], [[Kokolo Ikeda]] ('''2011'''). ''[http://link.springer.com/chapter/10.1007/978-3-642-31866-5_1 Accelerated UCT and Its Application to Two-Player Games]''. [[Advances in Computer Games 13]]
* [[Jeff Rollason]] ('''2011'''). ''[http://www.aifactory.co.uk/newsletter/2011_02_mcts_static.htm Mixing MCTS with Conventional Static Evaluation: Experiments and shortcuts en-route to full UCT]''. [[AI Factory]], Winter 2011 » [[Evaluation]]
* [[Sylvain Gelly]], [[David Silver]] ('''2011'''). ''Monte-Carlo tree search and rapid action value estimation in computer Go''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 175, No. 11, [http://www0.cs.ucl.ac.uk/staff/D.Silver/web/Applications_files/mcrave.pdf preprint as pdf]
* [[Lars Schaefers]], [[Marco Platzner]], [[Ulf Lorenz]] ('''2011'''). ''UCT-Treesplit - Parallel MCTS on Distributed Memory''. [http://www.aaai.org/Press/Proceedings/icaps11.php ICAPS 2011], [http://www.cs.uni-paderborn.de/fileadmin/Informatik/AG-Platzner/People/Schaefers/TreesplitICAPS.pdf pdf] » [[Parallel Search]]
* [[Raghuram Ramanujan]], [[Bart Selman]] ('''2011'''). ''[http://aaai.org/ocs/index.php/ICAPS/ICAPS11/paper/view/2708 Trade-Offs in Sampling-Based Adversarial Planning]''. [http://www.aaai.org/Press/Proceedings/icaps11.php ICAPS 2011]
'''2012'''
* [[Oleg Arenz]] ('''2012'''). ''Monte Carlo Chess''. B.Sc. thesis, [[Darmstadt University of Technology]], advisor [[Johannes Fürnkranz]], [http://www.ke.tu-darmstadt.de/lehre/arbeiten/bachelor/2012/Arenz_Oleg.pdf pdf] » [[Stockfish]]
* [[Cameron Browne]], [[Simon Lucas]], et al. ('''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, [http://www.cameronius.com/cv/mcts-survey-master.pdf pdf]
* [[Sylvain Gelly]], [[Marc Schoenauer]], [[Michèle Sebag]], [[Olivier Teytaud]], [[Levente Kocsis]], [[David Silver]], [[Csaba Szepesvári]] ('''2012'''). ''[http://dl.acm.org/citation.cfm?id=2093548.2093574 The Grand Challenge of Computer Go: Monte Carlo Tree Search and Extensions]''. [[ACM#Communications|Communications of the ACM]], Vol. 55, No. 3, [http://www0.cs.ucl.ac.uk/staff/D.Silver/web/Applications_files/grand-challenge.pdf pdf preprint]
* [[Adrien Couetoux]], [[Olivier Teytaud]], [[Hassen Doghmen]] ('''2012'''). ''Learning a Move-Generator for Upper Confidence Trees''. [http://ics2012.ndhu.edu.tw/ ICS 2012], [https://en.wikipedia.org/wiki/Hualien_City Hualien], [https://en.wikipedia.org/wiki/Taiwan Taiwan], December 2012 » [[Learning]], [[Move Generation]]
* [[Ashish Sabharwal]], [[Horst Samulowitz]], [[Chandra Reddy]] ('''2012'''). ''[http://link.springer.com/chapter/10.1007%2F978-3-642-29828-8_23 Guiding Combinatorial Optimization with UCT]''. [http://dblp.uni-trier.de/db/conf/cpaior/cpaior2012.html#SabharwalSR12 CPAIOR 2012], [http://web.emn.fr/x-info/cpaior-2012/uploads/Abstracts/CPAIOR%20-%2072980356.pdf abstract as pdf], [http://www.cs.toronto.edu/~horst/cogrobo/papers/uctmip.pdf draft as pdf]
* [[Raghuram Ramanujan]], [[Ashish Sabharwal]], [[Bart Selman]] ('''2012'''). ''Understanding Sampling Style Adversarial Search Methods''. [http://arxiv.org/abs/1203.4011 arXiv:1203.4011]
'''2013'''
* [[Cheng-Wei Chou]], [[Ping-Chiang Chou]], [[Chang-Shing Lee]], [[David L. Saint-Pierre]], [[Olivier Teytaud]], [[Mei-Hui Wang]], [[Li-Wen Wu]], [[Shi-Jim Yen]] ('''2013'''). ''Strategic Choices: Small Budgets and Simple Regret''. [[TAAI|TAAI 2012]], [http://www.csie.ndhu.edu.tw/csieweb/en/node/685 Excellent Paper Award], [https://hal.inria.fr/hal-00753145v2/document pdf]
* [[Simon Viennot]], [[Kokolo Ikeda]] ('''2013'''). ''[http://link.springer.com/chapter/10.1007%2F978-3-319-09165-5_3 Efficiency of Static Knowledge Bias in Monte-Carlo Tree Search]''. [[CG 2013]]
* [[Rui Li]], [[Yueqiu Wu]], [[Andi Zhang]], [[Chen Ma]], [[Bo Chen]], [[Shuliang Wang]] ('''2013'''). ''[http://cpfd.cnki.com.cn/Article/CPFDTOTAL-KZJC201309001170.htm Technique Analysis and Designing of Program with UCT Algorithm for NoGo]''. [http://www.ccdc.neu.edu.cn/CCDC2013/ CCDC2013]
* [[Ari Weinstein]], [[Michael L. Littman]], [[Sergiu Goschin]] ('''2013'''). ''[http://proceedings.mlr.press/v24/weinstein12a.html Rollout-based Game-tree Search Outprunes Traditional Alpha-beta]''. [http://proceedings.mlr.press/ PMLR], Vol. 24 » [[Monte-Carlo Tree Search|MCTS]]
'''2014'''
* [[Rémi Munos]] ('''2014'''). ''From Bandits to Monte-Carlo Tree Search: The Optimistic Principle Applied to Optimization and Planning''. [http://dblp.uni-trier.de/db/journals/ftml/ftml7.html#Munos14 Foundations and Trends in Machine Learning, Vol. 7, No 1], [https://hal.archives-ouvertes.fr/hal-00747575 hal-00747575v5], [http://chercheurs.lille.inria.fr/~munos/papers/files/AAAI2013_slides.pdf slides as pdf]
* [[David W. King]] ('''2014'''). ''Complexity, Heuristic, and Search Analysis for the Games of Crossings and Epaminondas''. Masters thesis, [https://en.wikipedia.org/wiki/Air_Force_Institute_of_Technology Air Force Institute of Technology], [http://www.afit.edu/docs/AFIT-ENG-14-M-44_King.pdf pdf] <ref>[https://en.wikipedia.org/wiki/Crossings_%28game%29 Crossings from Wikipedia]</ref>
* [[David W. King]], [[Gilbert L. Peterson]] ('''2014'''). ''Epaminondas: Exploring Combat Tactics''. [[ICGA Journal#37_3|ICGA Journal, Vol. 37, No. 3]] <ref> [https://en.wikipedia.org/wiki/Epaminondas_%28game%29 Epaminondas from Wikipedia]</ref>
==2015 ...==
* [[Xi Liang]], [[Ting-Han Wei]], [[I-Chen Wu]] ('''2015'''). ''Job-level UCT search for solving Hex''. [http://dblp.uni-trier.de/db/conf/cig/cig2015.html#LiangWW15 CIG 2015]
* [[Yusaku Mandai]], [[Tomoyuki Kaneko]] ('''2015'''). ''LinUCB Applied to Monte Carlo Tree Search''. [[Advances in Computer Games 14]]
* [[Yun-Ching Liu]], [[Yoshimasa Tsuruoka]] ('''2015'''). ''Adapting Improved Upper Confidence Bounds for Monte-Carlo Tree Search''. [[Advances in Computer Games 14]]
* [[S. Ali Mirsoleimani]], [[Aske Plaat]], [[Jaap van den Herik]] ('''2015'''). ''Ensemble UCT Needs High Exploitation''. [http://arxiv.org/abs/1509.08434 CoRR abs/1509.08434]
* [[Johannes Heinrich]], [[David Silver]] ('''2015'''). ''Smooth UCT Search in Computer Poker''. [[Conferences#IJCA2015|IJCAI 2015]], [http://www0.cs.ucl.ac.uk/staff/d.silver/web/Publications_files/smooth_uct.pdf pdf]
* [[Xi Liang]], [[Ting-Han Wei]], [[I-Chen Wu]] ('''2015'''). ''Solving Hex Openings Using Job-Level UCT Search''. [[ICGA Journal#38_3|ICGA Journal, Vol. 38, No. 3]]
* [[Naoki Mizukami]], [[Jun Suzuki]], [[Hirotaka Kameko]], [[Yoshimasa Tsuruoka]] ('''2017'''). ''Exploration Bonuses Based on Upper Confidence Bounds for Sparse Reward Games''. [[Advances in Computer Games 15]]
=Forum Posts=
* [http://computer-go.org/pipermail/computer-go/2010-June/000376.html Re: Chess vs Go // AI vs IA] by [[Gian-Carlo Pascutto]], June 02, 2010
* [http://www.lifein19x19.com/forum/viewtopic.php?f=18&t=2184 Monte Carlo (upper confidence bounds applied to trees)] by ChessGO, [http://www.lifein19x19.com/forum/viewforum.php?f=18 Computer Go], October 22, 2010
* [http://www.talkchess.com/forum/viewtopic.php?t=38554 UCT surprise for checkers !] by [[Daniel Shawul]], [[CCC]], March 25, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=42590 uct on gpu] by [[Daniel Shawul]], [[CCC]], February 24, 2012 » [[GPU]]
* [http://www.talkchess.com/forum/viewtopic.php?t=50721 My new book] by [[Daniel Shawul]], [[CCC]], January 02, 2014 » [[Opening Book]]
* [http://www.talkchess.com/forum/viewtopic.php?t=65964 Nebiyu-MCTS vs TSCP 1-0] by [[Daniel Shawul]], [[CCC]], December 10, 2017 » [[Nebiyu]]
* [http://www.talkchess.com/forum/viewtopic.php?t=66125 Search traps in MCTS and chess] by [[Daniel Shawul]], [[CCC]], December 25, 2017 » [[Raghuram Ramanujan#UCT|Sampling-Based Planning]]
* [http://rybkaforum.net/cgi-bin/rybkaforum/topic_show.pl?tid=32429 MCTS weakness wrt AB (via Daniel Shawul)] by [[Chris Whittington]], [[Computer Chess Forums|Rybka Forum]], December 25, 2017
* [http://www.talkchess.com/forum/viewtopic.php?t=66280 Announcing lczero] by [[Gary Linscott|Gary]], [[CCC]], January 09, 2018 » [[LCZero]]
=External Links=
* [https://en.wikipedia.org/wiki/Monte_Carlo_tree_search#Exploration_and_exploitation Exploration and exploitation - in Monte Carlo tree search from Wikipedia]
* [https://en.wikipedia.org/wiki/Confidence_interval Confidence interval from Wikipedia]
* [https://en.wikipedia.org/wiki/Multi-armed_bandit Multi-armed bandit from Wikipedia]
* [http://mcts.ai/about/index.html Monte Carlo Tree Search] by [[Cameron Browne]] et al.
: [http://mcts.ai/code/python.html UCT Monte Carlo Tree Search algorithm] in [[Python|Python 2.7]] by [[Peter Cowling]], [[Ed Powley]], and [[Daniel Whitehouse]]
: [http://mcts.ai/code/java.html UCT MCTS implementation] in [[Java]] by [[Simon Lucas]]
* [http://senseis.xmp.net/?UCT Sensei's Library: UCT]
* [http://www.althofer.de/lange-nacht-jena.html Lange Nacht der Wissenschaften - Long Night of Sciences Jena - 2007] by [[Ingo Althöfer]], [[Jakob Erdmann#UCT|MC and UCT poster]] by [[Jakob Erdmann]]
=References=
<references />
'''[[Monte-Carlo Tree Search|Up one level]]'''
'''UCT''' ('''U'''pper '''C'''onfidence bounds applied to '''T'''rees),<br/>
a popular [[Algorithms|algorithm]] that deals with the flaw of Monte-Carlo Tree Search, when a program may favor a losing move with only one or a few forced refutations, but due to the vast majority of other moves provides a better random playout score than other, better moves. UCT was introduced by [[Levente Kocsis]] and [[Csaba Szepesvári]] in 2006 <ref>[[Levente Kocsis]], [[Csaba Szepesvári]] ('''2006'''). ''[http://www.computer-go.info/resources/bandit.html Bandit based Monte-Carlo Planning]'' ECML-06, LNCS/LNAI 4212, [http://www.sztaki.hu/%7Eszcsaba/papers/ecml06.pdf pdf]</ref>, which accelerated the Monte-Carlo revolution in computer [[Go]] <ref>[[Sylvain Gelly]], [[Marc Schoenauer]], [[Michèle Sebag]], [[Olivier Teytaud]], [[Levente Kocsis]], [[David Silver]], [[Csaba Szepesvári]] ('''2012'''). ''[http://dl.acm.org/citation.cfm?id=2093548.2093574 The Grand Challenge of Computer Go: Monte Carlo Tree Search and Extensions]''. [[ACM#Communications|Communications of the ACM]], Vol. 55, No. 3, [http://www0.cs.ucl.ac.uk/staff/D.Silver/web/Applications_files/grand-challenge.pdf pdf preprint]</ref> and games difficult to [[Evaluation|evaluate]] statically. If given infinite time and [[Memory|memory]], UCT theoretically converges to [[Minimax]].
=Selection=
In UCT, upper [https://en.wikipedia.org/wiki/Confidence_interval confidence bounds] (UCB1) guide the selection of a node <ref>see UCB1 in [[Peter Auer]], [[Nicolò Cesa-Bianchi]], [[Paul Fischer]] ('''2002'''). ''[http://link.springer.com/article/10.1023%2FA%3A1013689704352 Finite-time Analysis of the Multiarmed Bandit Problem]''. [https://en.wikipedia.org/wiki/Machine_Learning_%28journal%29 Machine Learning], Vol. 47, No. 2</ref>, treating selection as a [https://en.wikipedia.org/wiki/Multi-armed_bandit multi-armed bandit problem], where the crucial tradeoff the [https://en.wikipedia.org/wiki/Gambling gambler] faces at each trial is between [https://en.wikipedia.org/wiki/Monte_Carlo_tree_search#Exploration_and_exploitation exploration and exploitation] - [https://en.wikipedia.org/wiki/Exploitation_%28disambiguation%29 exploitation] of the [https://en.wikipedia.org/wiki/Slot_machine slot machine] that has the highest expected payoff and [https://en.wikipedia.org/wiki/Exploration exploration] to get more information about the expected payoffs of the other machines. Child node j is selected which maximizes the UCT Evaluation:
[[FILE:UCTFormula.jpg|none|border|text-bottom]]
where:
* X<span style="font-size: 80%; vertical-align: sub;">j</span> is the [[Match Statistics#ratio|win ratio]] of the child
* n is the number of times the parent has been visited
* n<span style="font-size: 80%; vertical-align: sub;">j</span> is the number of times the child has been visited
* C is a constant to adjust the amount of exploration and incorporates the sqrt(2) from the UCB1 formula
The first component of the UCB1 formula above corresponds to exploitation, as it is high for moves with high average win ratio. The second component corresponds to exploration, since it is high for moves with few simulations. Most contemporary implementations of MCTS are based on some variant of UCT <ref>[https://en.wikipedia.org/wiki/Monte_Carlo_tree_search#Exploration_and_exploitation Exploration and exploitation - in Monte Carlo tree search from Wikipedia]</ref>. Modifications have been proposed, with the aim of shortening the time to find good moves. They can be divided into improvements based on expert knowledge and into domain-independent improvements in the playouts, and in building the tree in modifying the exploitation part of the UCB1 formula, for instance in [https://en.wikipedia.org/wiki/Monte_Carlo_tree_search#Improvements Rapid Action Value Estimation] ('''RAVE''') <ref> [[Sylvain Gelly]], [[David Silver]] ('''2011'''). ''Monte-Carlo tree search and rapid action value estimation in computer Go''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 175, No. 11, [http://www0.cs.ucl.ac.uk/staff/D.Silver/web/Applications_files/mcrave.pdf preprint as pdf]</ref> considering [[Transposition|transpositions]].
=Quotes=
==Gian-Carlo Pascutto==
Quote by [[Gian-Carlo Pascutto]] in 2010 <ref>[http://computer-go.org/pipermail/computer-go/2010-June/000376.html Re: Chess vs Go // AI vs IA] by [[Gian-Carlo Pascutto]], June 02, 2010</ref>:
There is no significant difference between an [[Alpha-Beta|alpha-beta search]] with heavy [[Late Move Reductions|LMR]] and a [[Evaluation|static evaluator]] (current state of the art in [[Chess|chess]]) and an UCT searcher with a small exploration constant that does playouts (state of the art in [[Go|go]]).
The shape of the [[Search Tree|tree]] they search is very similar. The main breakthrough in Go the last few years was how to backup an uncertain Monte Carlo score. This was solved. For chess this same problem was solved around the time [[Quiescence Search|quiescent search]] was developed.
Both are producing strong programs and we've proven for both the methods that they scale in strength as hardware speed goes up.
So I would say that we've successfully adopted the simple, brute force methods for chess to Go and they already work without increases in computer speed. The increases will make them progressively stronger though, and with further software tweaks they will eventually surpass humans.
==Raghuram Ramanujan et al.==
Quote by [[Raghuram Ramanujan]], [[Ashish Sabharwal]], and [[Bart Selman]] from their abstract ''On Adversarial Search Spaces and Sampling-Based Planning'' <ref>[[Raghuram Ramanujan]], [[Ashish Sabharwal]], [[Bart Selman]] ('''2010'''). ''[http://www.aaai.org/ocs/index.php/ICAPS/ICAPS10/paper/view/1458 On Adversarial Search Spaces and Sampling-Based Planning]''. [http://www.aaai.org/Press/Proceedings/icaps10.php ICAPS 2010]</ref>:
UCT has been shown to outperform traditional [[Minimax|minimax]] based approaches in several challenging domains such as [[Go]] and [[Kriegspiel]], although minimax search still prevails in other domains such as [[Chess]]. This work provides insights into the properties of adversarial search spaces that play a key role in the success or failure of UCT and similar sampling-based approaches. We show that certain "early loss" or "shallow trap" configurations, while unlikely in Go, occur surprisingly often in games like Chess (even in grandmaster games). We provide evidence that UCT, unlike minimax search, is unable to identify such traps in Chess and spends a great deal of time exploring much deeper game play than needed.
=See also=
* [[Match Statistics]]
* [[Jakob Erdmann#UCT|MC and UCT poster]] by [[Jakob Erdmann]]
* [[MCαβ]]
* [[Reinforcement Learning]]
=Publications=
==2000 ...==
* [[Peter Auer]], [[Nicolò Cesa-Bianchi]], [[Paul Fischer]] ('''2002'''). ''[http://link.springer.com/article/10.1023%2FA%3A1013689704352 Finite-time Analysis of the Multiarmed Bandit Problem]''. [https://en.wikipedia.org/wiki/Machine_Learning_%28journal%29 Machine Learning], Vol. 47, No. 2, [http://homes.di.unimi.it/~cesabian/Pubblicazioni/ml-02.pdf pdf]
==2005 ...==
'''2006'''
* [[Levente Kocsis]], [[Csaba Szepesvári]] ('''2006'''). ''[http://www.computer-go.info/resources/bandit.html Bandit based Monte-Carlo Planning]''. ECML-06, LNCS/LNAI 4212, [http://old.sztaki.hu/~szcsaba/papers/ecml06.pdf pdf]
* [[Levente Kocsis]], [[Csaba Szepesvári]], [[Jan Willemson]] ('''2006'''). ''Improved Monte-Carlo Search''. [http://www.sztaki.hu/~szcsaba/papers/cg06-ext.pdf pdf]
* [[Sylvain Gelly]], [[Yizao Wang]] ('''2006'''). ''Exploration exploitation in Go: UCT for Monte-Carlo Go''. [http://www.lri.fr/%7Egelly/paper/nips_exploration_exploitation_mogo.pdf pdf]
* [[Sylvain Gelly]], [[Yizao Wang]], [[Rémi Munos]], [[Olivier Teytaud]] ('''2006'''). ''Modification of UCT with Patterns in Monte-Carlo Go''. [http://hal.inria.fr/inria-00117266 INRIA]
'''2007'''
* [[Yizao Wang]], [[Sylvain Gelly]] ('''2007'''). ''Modifications of UCT and Sequence-Like Simulations for Monte-Carlo Go''. IEEE Symposium on Computational Intelligence and Games, Honolulu, USA, 2007, [http://www.stat.lsa.umich.edu/%7Eyizwang/publications/wang07modifications.pdf pdf]
* [[Shugo Nakamura]], [[Makoto Miwa]], [[Takashi Chikayama]] ('''2007'''). ''Improvement of UCT using evaluation function''. [http://www.computer-shogi.org/gpw/gpw12_e.html 12th Game Programming Workshop 2007]
* [[Tristan Cazenave]], [[Nicolas Jouandeau]] ('''2007'''). ''On the Parallelization of UCT''. [[CGW 2007]], [http://www.lamsade.dauphine.fr/%7Ecazenave/papers/parallelUCT.pdf pdf] » [[Parallel Search]]
* [[Jean-Yves Audibert]], [[Rémi Munos]], [[Csaba Szepesvári]] ('''2007'''). ''Tuning Bandit Algorithms in Stochastic Environments''. [http://certis.enpc.fr/~audibert/ucb_alt.pdf pdf]
'''2008'''
* [[Nathan Sturtevant]] ('''2008'''). ''[http://link.springer.com/chapter/10.1007/978-3-540-87608-3_4 An Analysis of UCT in Multi-player Games]''. [[CG 2008]]
* [[Guillaume Chaslot]], [[Mark Winands]], [[Jaap van den Herik]] ('''2008'''). ''[http://link.springer.com/chapter/10.1007/978-3-540-87608-3_6 Parallel Monte-Carlo Tree Search]''. [[CG 2008]], [https://dke.maastrichtuniversity.nl/m.winands/documents/multithreadedMCTS2.pdf pdf]
'''2009'''
* [[Rémi Coulom]] ('''2009'''). ''The Monte-Carlo Revolution in Go''. JFFoS'2008: Japanese-French Frontiers of Science Symposium, [http://remi.coulom.free.fr/JFFoS/JFFoS.pdf slides as pdf]
* [[Fabien Teytaud]], [[Olivier Teytaud]] ('''2009'''). ''Creating an Upper-Confidence-Tree program for Havannah''. [[Advances in Computer Games 12]], [http://hal.inria.fr/docs/00/38/05/39/PDF/hav.pdf inria-00380539 as pdf] » [[Havannah]]
==2010 ...==
* [[Jean Méhat]], [[Tristan Cazenave]] ('''2010'''). ''Combining UCT and Nested Monte-Carlo Search for Single-Player General Game Playing''. [[IEEE#TOCIAIGAMES|IEEE Transactions on Computational Intelligence and AI in Games]], Vol. 2, No. 4, [http://www.lamsade.dauphine.fr/~cazenave/papers/ggp2009.pdf pdf 2009] » [[General Game Playing]]
* [[Raghuram Ramanujan]], [[Ashish Sabharwal]], [[Bart Selman]] ('''2010'''). ''[http://www.aaai.org/ocs/index.php/ICAPS/ICAPS10/paper/view/1458 On Adversarial Search Spaces and Sampling-Based Planning]''. [http://www.aaai.org/Press/Proceedings/icaps10.php ICAPS 2010] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=66125 Search traps in MCTS and chess] by [[Daniel Shawul]], [[CCC]], December 25, 2017</ref>
* [[Damien Pellier]], [[Bruno Bouzy]], [[Marc Métivier]] ('''2010'''). ''An UCT Approach for Anytime Agent-based Planning''. [http://www.springer.com/de/book/9783642123832 PAAMS'10], [http://www.mi.parisdescartes.fr/~bouzy/publications/pellier-bouzy-metivier-paams10.pdf pdf]
* [[Thomas J. Walsh]], [[Sergiu Goschin]], [[Michael L. Littman]] ('''2010'''). ''Integrating sample-based planning and model-based reinforcement learning.'' [[AAAI]], [https://pdfs.semanticscholar.org/bdc9/bfb6ecc6fb5afb684df03d7220c46ebdbf4e.pdf pdf] » [[Reinforcement Learning]]
'''2011'''
* [[Junichi Hashimoto]], [[Akihiro Kishimoto]], [[Kazuki Yoshizoe]], [[Kokolo Ikeda]] ('''2011'''). ''[http://link.springer.com/chapter/10.1007/978-3-642-31866-5_1 Accelerated UCT and Its Application to Two-Player Games]''. [[Advances in Computer Games 13]]
* [[Jeff Rollason]] ('''2011'''). ''[http://www.aifactory.co.uk/newsletter/2011_02_mcts_static.htm Mixing MCTS with Conventional Static Evaluation: Experiments and shortcuts en-route to full UCT]''. [[AI Factory]], Winter 2011 » [[Evaluation]]
* [[Sylvain Gelly]], [[David Silver]] ('''2011'''). ''Monte-Carlo tree search and rapid action value estimation in computer Go''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 175, No. 11, [http://www0.cs.ucl.ac.uk/staff/D.Silver/web/Applications_files/mcrave.pdf preprint as pdf]
* [[Lars Schaefers]], [[Marco Platzner]], [[Ulf Lorenz]] ('''2011'''). ''UCT-Treesplit - Parallel MCTS on Distributed Memory''. [http://www.aaai.org/Press/Proceedings/icaps11.php ICAPS 2011], [http://www.cs.uni-paderborn.de/fileadmin/Informatik/AG-Platzner/People/Schaefers/TreesplitICAPS.pdf pdf] » [[Parallel Search]]
* [[Raghuram Ramanujan]], [[Bart Selman]] ('''2011'''). ''[http://aaai.org/ocs/index.php/ICAPS/ICAPS11/paper/view/2708 Trade-Offs in Sampling-Based Adversarial Planning]''. [http://www.aaai.org/Press/Proceedings/icaps11.php ICAPS 2011]
'''2012'''
* [[Oleg Arenz]] ('''2012'''). ''Monte Carlo Chess''. B.Sc. thesis, [[Darmstadt University of Technology]], advisor [[Johannes Fürnkranz]], [http://www.ke.tu-darmstadt.de/lehre/arbeiten/bachelor/2012/Arenz_Oleg.pdf pdf] » [[Stockfish]]
* [[Cameron Browne]], [[Simon Lucas]], et al. ('''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, [http://www.cameronius.com/cv/mcts-survey-master.pdf pdf]
* [[Sylvain Gelly]], [[Marc Schoenauer]], [[Michèle Sebag]], [[Olivier Teytaud]], [[Levente Kocsis]], [[David Silver]], [[Csaba Szepesvári]] ('''2012'''). ''[http://dl.acm.org/citation.cfm?id=2093548.2093574 The Grand Challenge of Computer Go: Monte Carlo Tree Search and Extensions]''. [[ACM#Communications|Communications of the ACM]], Vol. 55, No. 3, [http://www0.cs.ucl.ac.uk/staff/D.Silver/web/Applications_files/grand-challenge.pdf pdf preprint]
* [[Adrien Couetoux]], [[Olivier Teytaud]], [[Hassen Doghmen]] ('''2012'''). ''Learning a Move-Generator for Upper Confidence Trees''. [http://ics2012.ndhu.edu.tw/ ICS 2012], [https://en.wikipedia.org/wiki/Hualien_City Hualien], [https://en.wikipedia.org/wiki/Taiwan Taiwan], December 2012 » [[Learning]], [[Move Generation]]
* [[Ashish Sabharwal]], [[Horst Samulowitz]], [[Chandra Reddy]] ('''2012'''). ''[http://link.springer.com/chapter/10.1007%2F978-3-642-29828-8_23 Guiding Combinatorial Optimization with UCT]''. [http://dblp.uni-trier.de/db/conf/cpaior/cpaior2012.html#SabharwalSR12 CPAIOR 2012], [http://web.emn.fr/x-info/cpaior-2012/uploads/Abstracts/CPAIOR%20-%2072980356.pdf abstract as pdf], [http://www.cs.toronto.edu/~horst/cogrobo/papers/uctmip.pdf draft as pdf]
* [[Raghuram Ramanujan]], [[Ashish Sabharwal]], [[Bart Selman]] ('''2012'''). ''Understanding Sampling Style Adversarial Search Methods''. [http://arxiv.org/abs/1203.4011 arXiv:1203.4011]
'''2013'''
* [[Cheng-Wei Chou]], [[Ping-Chiang Chou]], [[Chang-Shing Lee]], [[David L. Saint-Pierre]], [[Olivier Teytaud]], [[Mei-Hui Wang]], [[Li-Wen Wu]], [[Shi-Jim Yen]] ('''2013'''). ''Strategic Choices: Small Budgets and Simple Regret''. [[TAAI|TAAI 2012]], [http://www.csie.ndhu.edu.tw/csieweb/en/node/685 Excellent Paper Award], [https://hal.inria.fr/hal-00753145v2/document pdf]
* [[Simon Viennot]], [[Kokolo Ikeda]] ('''2013'''). ''[http://link.springer.com/chapter/10.1007%2F978-3-319-09165-5_3 Efficiency of Static Knowledge Bias in Monte-Carlo Tree Search]''. [[CG 2013]]
* [[Rui Li]], [[Yueqiu Wu]], [[Andi Zhang]], [[Chen Ma]], [[Bo Chen]], [[Shuliang Wang]] ('''2013'''). ''[http://cpfd.cnki.com.cn/Article/CPFDTOTAL-KZJC201309001170.htm Technique Analysis and Designing of Program with UCT Algorithm for NoGo]''. [http://www.ccdc.neu.edu.cn/CCDC2013/ CCDC2013]
* [[Ari Weinstein]], [[Michael L. Littman]], [[Sergiu Goschin]] ('''2013'''). ''[http://proceedings.mlr.press/v24/weinstein12a.html Rollout-based Game-tree Search Outprunes Traditional Alpha-beta]''. [http://proceedings.mlr.press/ PMLR], Vol. 24 » [[Monte-Carlo Tree Search|MCTS]]
'''2014'''
* [[Rémi Munos]] ('''2014'''). ''From Bandits to Monte-Carlo Tree Search: The Optimistic Principle Applied to Optimization and Planning''. [http://dblp.uni-trier.de/db/journals/ftml/ftml7.html#Munos14 Foundations and Trends in Machine Learning, Vol. 7, No 1], [https://hal.archives-ouvertes.fr/hal-00747575 hal-00747575v5], [http://chercheurs.lille.inria.fr/~munos/papers/files/AAAI2013_slides.pdf slides as pdf]
* [[David W. King]] ('''2014'''). ''Complexity, Heuristic, and Search Analysis for the Games of Crossings and Epaminondas''. Masters thesis, [https://en.wikipedia.org/wiki/Air_Force_Institute_of_Technology Air Force Institute of Technology], [http://www.afit.edu/docs/AFIT-ENG-14-M-44_King.pdf pdf] <ref>[https://en.wikipedia.org/wiki/Crossings_%28game%29 Crossings from Wikipedia]</ref>
* [[David W. King]], [[Gilbert L. Peterson]] ('''2014'''). ''Epaminondas: Exploring Combat Tactics''. [[ICGA Journal#37_3|ICGA Journal, Vol. 37, No. 3]] <ref> [https://en.wikipedia.org/wiki/Epaminondas_%28game%29 Epaminondas from Wikipedia]</ref>
==2015 ...==
* [[Xi Liang]], [[Ting-Han Wei]], [[I-Chen Wu]] ('''2015'''). ''Job-level UCT search for solving Hex''. [http://dblp.uni-trier.de/db/conf/cig/cig2015.html#LiangWW15 CIG 2015]
* [[Yusaku Mandai]], [[Tomoyuki Kaneko]] ('''2015'''). ''LinUCB Applied to Monte Carlo Tree Search''. [[Advances in Computer Games 14]]
* [[Yun-Ching Liu]], [[Yoshimasa Tsuruoka]] ('''2015'''). ''Adapting Improved Upper Confidence Bounds for Monte-Carlo Tree Search''. [[Advances in Computer Games 14]]
* [[S. Ali Mirsoleimani]], [[Aske Plaat]], [[Jaap van den Herik]] ('''2015'''). ''Ensemble UCT Needs High Exploitation''. [http://arxiv.org/abs/1509.08434 CoRR abs/1509.08434]
* [[Johannes Heinrich]], [[David Silver]] ('''2015'''). ''Smooth UCT Search in Computer Poker''. [[Conferences#IJCA2015|IJCAI 2015]], [http://www0.cs.ucl.ac.uk/staff/d.silver/web/Publications_files/smooth_uct.pdf pdf]
* [[Xi Liang]], [[Ting-Han Wei]], [[I-Chen Wu]] ('''2015'''). ''Solving Hex Openings Using Job-Level UCT Search''. [[ICGA Journal#38_3|ICGA Journal, Vol. 38, No. 3]]
* [[Naoki Mizukami]], [[Jun Suzuki]], [[Hirotaka Kameko]], [[Yoshimasa Tsuruoka]] ('''2017'''). ''Exploration Bonuses Based on Upper Confidence Bounds for Sparse Reward Games''. [[Advances in Computer Games 15]]
=Forum Posts=
* [http://computer-go.org/pipermail/computer-go/2010-June/000376.html Re: Chess vs Go // AI vs IA] by [[Gian-Carlo Pascutto]], June 02, 2010
* [http://www.lifein19x19.com/forum/viewtopic.php?f=18&t=2184 Monte Carlo (upper confidence bounds applied to trees)] by ChessGO, [http://www.lifein19x19.com/forum/viewforum.php?f=18 Computer Go], October 22, 2010
* [http://www.talkchess.com/forum/viewtopic.php?t=38554 UCT surprise for checkers !] by [[Daniel Shawul]], [[CCC]], March 25, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=42590 uct on gpu] by [[Daniel Shawul]], [[CCC]], February 24, 2012 » [[GPU]]
* [http://www.talkchess.com/forum/viewtopic.php?t=50721 My new book] by [[Daniel Shawul]], [[CCC]], January 02, 2014 » [[Opening Book]]
* [http://www.talkchess.com/forum/viewtopic.php?t=65964 Nebiyu-MCTS vs TSCP 1-0] by [[Daniel Shawul]], [[CCC]], December 10, 2017 » [[Nebiyu]]
* [http://www.talkchess.com/forum/viewtopic.php?t=66125 Search traps in MCTS and chess] by [[Daniel Shawul]], [[CCC]], December 25, 2017 » [[Raghuram Ramanujan#UCT|Sampling-Based Planning]]
* [http://rybkaforum.net/cgi-bin/rybkaforum/topic_show.pl?tid=32429 MCTS weakness wrt AB (via Daniel Shawul)] by [[Chris Whittington]], [[Computer Chess Forums|Rybka Forum]], December 25, 2017
* [http://www.talkchess.com/forum/viewtopic.php?t=66280 Announcing lczero] by [[Gary Linscott|Gary]], [[CCC]], January 09, 2018 » [[LCZero]]
=External Links=
* [https://en.wikipedia.org/wiki/Monte_Carlo_tree_search#Exploration_and_exploitation Exploration and exploitation - in Monte Carlo tree search from Wikipedia]
* [https://en.wikipedia.org/wiki/Confidence_interval Confidence interval from Wikipedia]
* [https://en.wikipedia.org/wiki/Multi-armed_bandit Multi-armed bandit from Wikipedia]
* [http://mcts.ai/about/index.html Monte Carlo Tree Search] by [[Cameron Browne]] et al.
: [http://mcts.ai/code/python.html UCT Monte Carlo Tree Search algorithm] in [[Python|Python 2.7]] by [[Peter Cowling]], [[Ed Powley]], and [[Daniel Whitehouse]]
: [http://mcts.ai/code/java.html UCT MCTS implementation] in [[Java]] by [[Simon Lucas]]
* [http://senseis.xmp.net/?UCT Sensei's Library: UCT]
* [http://www.althofer.de/lange-nacht-jena.html Lange Nacht der Wissenschaften - Long Night of Sciences Jena - 2007] by [[Ingo Althöfer]], [[Jakob Erdmann#UCT|MC and UCT poster]] by [[Jakob Erdmann]]
=References=
<references />
'''[[Monte-Carlo Tree Search|Up one level]]'''
