Editing Monte Carlo method (section)

===Artificial intelligence for games===
{{Main|Monte Carlo tree search}}
Monte Carlo methods have been developed into a technique called [[Monte-Carlo tree search]] that is useful for searching for the best move in a game. Possible moves are organized in a [[search tree]] and many random simulations are used to estimate the long-term potential of each move. A black box simulator represents the opponent's moves.<ref>{{cite web|url=http://sander.landofsand.com/publications/Monte-Carlo_Tree_Search_-_A_New_Framework_for_Game_AI.pdf |title=Monte-Carlo Tree Search: A New Framework for Game AI |author-first1=Guillaume |author-last1=Chaslot |author-first2=Sander |author-last2=Bakkes |author-first3=Istvan |author-last3=Szita |author-first4=Pieter |author-last4=Spronck |website=Sander.landofsand.com |access-date=October 28, 2017}}</ref>

The Monte Carlo tree search (MCTS) method has four steps:<ref>{{cite web|url=http://mcts.ai/about/index.html |title=Monte Carlo Tree Search - About|access-date=May 15, 2013 |archive-url=https://web.archive.org/web/20151129023043/http://mcts.ai/about/index.html |archive-date=November 29, 2015 |url-status=dead}}</ref>
# Starting at root node of the tree, select optimal child nodes until a leaf node is reached.
# Expand the leaf node and choose one of its children.
# Play a simulated game starting with that node.
# Use the results of that simulated game to update the node and its ancestors.

The net effect, over the course of many simulated games, is that the value of a node representing a move will go up or down, hopefully corresponding to whether or not that node represents a good move.

Monte Carlo Tree Search has been used successfully to play games such as [[Go (game)|Go]],<ref>{{cite book|chapter=Parallel Monte-Carlo Tree Search |doi=10.1007/978-3-540-87608-3_6 |volume=5131 |pages=60–71 |series=Lecture Notes in Computer Science |year=2008 |author-last1=Chaslot |author-first1=Guillaume M. J. -B |author-last2=Winands |author-first2=Mark H. M. |author-last3=Van Den Herik |author-first3=H. Jaap |title=Computers and Games |isbn=978-3-540-87607-6 |citeseerx=10.1.1.159.4373}}</ref> [[Tantrix]],<ref>{{cite report|url=https://www.tantrix.com/Tantrix/TRobot/MCTS%20Final%20Report.pdf |title=Monte-Carlo Tree Search in the game of Tantrix: Cosc490 Final Report |author-last=Bruns |author-first=Pete}}</ref> [[Battleship (game)|Battleship]],<ref>{{cite web |url=http://www0.cs.ucl.ac.uk/staff/D.Silver/web/Publications_files/pomcp.pdf |title=Monte-Carlo Planning in Large POMDPs |author-first1=David |author-last1=Silver |author-first2=Joel |author-last2=Veness |website=0.cs.ucl.ac.uk |access-date=October 28, 2017 |archive-date=July 18, 2016 |archive-url=https://web.archive.org/web/20160718050040/http://www0.cs.ucl.ac.uk/staff/d.silver/web/Publications_files/pomcp.pdf |url-status=dead }}</ref> [[Havannah (board game)|Havannah]],<ref>{{cite book|chapter=Improving Monte–Carlo Tree Search in Havannah |doi=10.1007/978-3-642-17928-0_10 |volume=6515 |pages=105–115|bibcode=2011LNCS.6515..105L |series=Lecture Notes in Computer Science |year=2011 |author-last1=Lorentz |author-first1=Richard J. |title=Computers and Games |isbn=978-3-642-17927-3}}</ref> and [[Arimaa]].<ref>{{cite web|url=http://www.arimaa.com/arimaa/papers/ThomasJakl/bc-thesis.pdf |author-first=Tomas |author-last=Jakl |title=Arimaa challenge – comparison study of MCTS versus alpha-beta methods |website=Arimaa.com |access-date=October 28, 2017}}</ref>

{{See also|Computer Go}}