Changes

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.  ==RAVE==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]]. ==PUCT==[[Christopher D. Rosin|Chris Rosin's]] [[Christopher D. Rosin#PUCT|PUCT]] modifies the original UCB1 multi-armed bandit policy by approximately predicting good arms at the start of a sequence of multi-armed bandit trials ('Predictor' + UCB = PUCB) <ref>[[Christopher D. Rosin]] ('''2011'''). ''[https://link.springer.com/article/10.1007/s10472-011-9258-6 Multi-armed bandits with episode context]''. Annals of Mathematics and Artificial Intelligence, Vol. 61, No. 3, [http://gauss.ececs.uc.edu/Workshops/isaim2010/papers/rosin.pdf ISAIM 2010 pdf]</ref>. A variation of PUCT was used in the [[AlphaGo]] and [[AlphaZero]] projects <ref>[[David Silver]], [[Shih-Chieh Huang|Aja Huang]], [[Chris J. Maddison]], [[Arthur Guez]], [[Laurent Sifre]], [[George van den Driessche]], [[Julian Schrittwieser]], [[Ioannis Antonoglou]], [[Veda Panneershelvam]], [[Marc Lanctot]], [[Sander Dieleman]], [[Dominik Grewe]], [[John Nham]], [[Nal Kalchbrenner]], [[Ilya Sutskever]], [[Timothy Lillicrap]], [[Madeleine Leach]], [[Koray Kavukcuoglu]], [[Thore Graepel]], [[Demis Hassabis]] ('''2016'''). ''[http://www.nature.com/nature/journal/v529/n7587/full/nature16961.html Mastering the game of Go with deep neural networks and tree search]''. [https://en.wikipedia.org/wiki/Nature_%28journal%29 Nature], Vol. 529</ref> , and subsequently also in [[Leela Zero]] and [[Leela Chess Zero]] <ref>[https://github.com/LeelaChessZero/lc0/wiki/FAQ FAQ · LeelaChessZero/lc0 Wiki · GitHub]</ref>. 

UCT has been shown to outperform traditional [[Minimax|minimax]] based approaches in several challenging domains such as [[Go]] and [[KriegspielKriegSpiel]], 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.

* [[Cameron Browne]], [[Edward Powley]], [[Daniel Whitehouse]], [[Simon Lucas]], et al. [[Peter Cowling]], [[Philipp Rohlfshagen]], [[Stephen Tavener]], [[Diego Perez]], [[Spyridon Samothrakis]], [[Simon Colton]] ('''2012'''). ''[httphttps://ieeexplore.ieee.org/xpldocument/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, [http://wwwccg.doc.cameroniusgold.comac.uk/ccg_old/cvpapers/mcts-survey-masterbrowne_tciaig12_1.pdf pdf]

* [[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 » [[Ari Weinstein#FSSS-Minimax|FSSS-Minimax]], [[Monte-Carlo Tree Search|MCTS]]

* [http://www.talkchess.com/forum/viewtopic.php?t=66280 Announcing lczero] by [[Gary Linscott|Gary]], [[CCC]], January 09, 2018 » [[LCZeroLeela Chess Zero]]

* [httphttps://mctsgithub.aicom/abouttheKGS/index.html Monte Carlo Tree Search] by [[Cameron Browne]] et al.MCTS GitHub - theKGS/MCTS: [http://mcts.ai/code/python.html Java implementation of UCT Monte Carlo Tree Search algorithm] in [[Python|Python 2.7]] by [[Peter Cowling]], [[Ed Powley]], based MCTS and [[Daniel Whitehouse]]: [http://mcts.ai/code/java.html UCT Flat MCTS implementation] in [[Java]] by [[Simon Lucas]]* [httphttps://senseis.xmp.net/?UCT Sensei's Library: UCT]* [httphttps://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]]* [[:Category:Weather Report|Weather Report]] - [https://en.wikipedia.org/wiki/Sweetnighter Boogie Woogie Waltz], 1974, [https://en.wikipedia.org/wiki/YouTube YouTube] Video: [[:Category:Joe Zawinul|Joe Zawinul]], [[:Category:Wayne Shorter|Wayne Shorter]], [[:Category:Alphonso Johnson|Alphonso Johnson]], [https://www.allmusic.com/artist/darryl-brown-mn0001213839 Darryl Brown], [[:Category:Dom Um Romão|Dom Um Romão]]: {{#evu:https://www.youtube.com/watch?v=MRs5ROwfgW4|alignment=left|valignment=top}}