Move Selection in MCTS
MCTS repeatedly searches from the root of the current partial game tree.
The Current Position Comes First
Monte Carlo Tree Search, or MCTS, repeatedly searches from the root of the current partial game tree. The root is not a permanent starting point for the entire game. It represents the game state that is current when the program is deciding what to do next.
This matters because a move is useful only in the situation where it is available. Before the program moves, the root represents the current game state. The search explores the partial tree below that root and accumulates information in its nodes while computational resources remain available. When the search stops, the program uses that accumulated information to select a move from the root.
Search Turns Tree Information into a Move
MCTS does not choose a move from a single observation of the current position. It continues searching from the current root while time or another computational resource remains available. During this search, the partial game tree accumulates node statistics. Those statistics provide the information used when the program eventually chooses one of the moves available from the root.
A Search Before the Program Moves
Choosing from an Existing Root
Suppose a partial game tree currently has root R, representing the position where the program must move. The tree contains several possible root moves, and the search has accumulated statistics in nodes below R.
Locate the current position: Node R is the root because it represents the current game state before the program makes its move.
Continue searching: MCTS repeatedly searches from R while computational resources remain. The partial tree accumulates more node statistics during this search.
Stop searching: When the search stops, the accumulated information in the partial tree is available for move selection.
Select from the root: The program selects a move from R using the accumulated node statistics. It does not select a move from an unrelated node elsewhere in the tree.
The selected move is a root move supported by the information accumulated during the search from the current game state.
The labels R and the root moves in this example are only teaching labels. The important structure is that the current game state is at the root, search takes place from that root, and the eventual move is selected from that same root using accumulated information.
When the Opponent Changes the State
After the program makes a move, the opponent may make a move as well. That opponent move changes the current game state. The next MCTS search must therefore use a new root node representing the new current state; the old root still represents the earlier situation and cannot remain the root for the next decision.
The new root is the state from which the next search begins. MCTS is run again from this new current game state, with the same overall pattern: search while resources remain, accumulate node statistics, and use those statistics to select the next move from the new root.
Reuse the Reachable Part
Re-rooting does not necessarily mean throwing away every node from the previous search. If the new root was already present as a descendant of the old root, that descendant and the part of the tree below it can remain available. Their accumulated statistics can therefore remain available for the next search.
Nodes unrelated to the new current state cannot help represent the next search situation. Those nodes are discarded together with their statistics. The key test is reachability from the new root: descendants of the new root may be reusable, while branches unrelated to that state are removed.
Following One Branch into the Next Search
A previous partial tree has root R. One descendant, Q, represents the game state that becomes current after the opponent moves. Another branch, B, represents a state unrelated to Q.
Identify the new state: The opponent's move makes Q the current game state, so Q becomes the new root for the next search.
Check the old tree: Q was already a descendant in the previously constructed partial tree, so the portion of the tree below Q can remain available.
Remove unrelated information: Branch B is unrelated to the new current state. It is discarded together with its accumulated statistics.
Continue searching: The next MCTS search begins from Q and can use the reusable information that remains below Q.
The tree is re-rooted at Q. Reachable descendants may be reused, while unrelated branches and their statistics are discarded.
Mistakes About Roots and Statistics
Treating the original game position as the root for every search
The opponent's move changes the current game state, so the next search needs a new root representing that new state.
Fix:
Re-root the search at the node representing the new current game state.Selecting a move from a single observation
MCTS continues searching while resources remain and accumulates node statistics before selecting a root move.
Fix:
Use the accumulated information from the partial tree when the search stops.Keeping every old branch after the state changes
Nodes unrelated to the new state do not represent the situation for the next search, and their statistics are discarded.
Fix:
Retain descendants reachable from the new root and discard unrelated nodes with their statistics.Assuming that one named statistic or formula is required
The source description states the general role of accumulated node statistics without requiring a particular statistic or formula.
Fix:
Focus on the relationship between repeated search, accumulated node information, and selecting from the root.
Check Your Tree Trace
A partial tree has root R. A descendant Q represents the state reached after the opponent's move. Another branch X is not reachable from Q. What becomes the root for the next search, which existing part may remain available, and what happens to X and its statistics?
Hints
- Start by identifying the game state that is current after the opponent moves.
- A descendant that represents that state can become the new root.
- Compare every old branch with the new root before deciding whether it remains available.
What do you think happens?
In the scenario above, should the next search begin again from R, or from Q?
Reveal answer
Answer: Q, because it represents the new current game state.
The opponent's move creates a new current game state and therefore a new root for the next search. The portion below Q may remain available, while unrelated branch X and its statistics are discarded.
Key Takeaways
- MCTS repeatedly searches from the root representing the current game state.
- Search accumulates node statistics while computational resources remain available.
- When the search stops, the program selects a move from the root using that accumulated information.
- After the opponent moves, the new current game state becomes the new root for the next search.
- A descendant representing the new state and the tree below it may be reused, while unrelated nodes and their statistics are discarded.
Key Takeaways
- The root of an MCTS search represents the current game state, not necessarily the beginning of the entire game.
- Repeated search builds accumulated node statistics that support choosing a move from the root.
- An opponent move changes the current state and requires a new root for the next search.
- Descendants reachable from the new root may be reused, while unrelated branches and their statistics are discarded.