Monte-Carlo Tree Search

<div>Monte-Carlo Tree Search (MCTS) is a best-first search method that does not require a positional evaluation function. Best-first search is an instance of general tree-search algorithm in which a node is selected for expansion based on a specific rule. It is based on the randomized exploration of the search space. Instead of building the whole game tree (like tree-search algorithms such as Minimax) or just simply run Monte Carlo simulations from the current position, MCTS builds up the</div><div>tree in an incrementally and asymmetric manner.</div><div><br/></div><div>It consists of four steps, repeated as long as there is time left. They are: selection, expansion, simulation and backpropagation. In the selection step, the tree is traversed from the root node until we reach a leaf node or a node with untried moves E. In the expansion step, we select one child node C and add it to the tree. In the simulation step, we run a self-playing game from node C until game is ended and we have a result R, which is +1 if player wins, 0 if it is a draw and -1 if player is lost. In the backpropagation step, the result R is propagated backwards through previously traversed nodes. Finally after the running time is over, a child node of the root node is selected based on the number of visits or its value. MCTS is a general problem that can be applied in many areas. The most success application of MCTS is to build Go-playing agents.</div><div><br/></div><div>This bounty is created so that we can propose different implementations of MCTS for different problems (games, scheduling problems...)</div>
  • {{comment.username}}
submission(s) pending review
Bounty expires in
Bounty expired
(no tags)