Partial Game Trees in MCTS
MCTS repeatedly searches from the root of the current partial game tree.
The Search Starts Where the Game Is
Monte Carlo Tree Search does not make a move from one isolated observation. It repeatedly searches from the root of the current partial game tree while time or another computational resource remains available. That root represents the game state that is currently being played. The search grows knowledge around that state, and the program eventually selects a move from the root using the accumulated node statistics.
Following One Search
Imagine that the current root represents state S0. During the available search time, MCTS works with the partial tree below that root. The tree accumulates statistics at its nodes. When the search stops, the program uses those accumulated statistics to choose one of the moves available from the root. The important sequence is: begin at the current root, continue searching, accumulate node information, then select a root move.
Selecting from the current root
A partial game tree has current root S0 and two available root moves, M1 and M2. The search has accumulated statistics in the tree. What does the program use when it chooses its move?
Locate the root: The root S0 represents the current game state, so move selection is made from this root rather than from an unrelated earlier state.
Continue the search: While computational resources remain, MCTS continues searching from the root of the current partial tree and accumulates node statistics.
Stop searching: When the available search ends, the partial tree contains the accumulated information produced during that search.
Choose a move: The program uses those accumulated statistics to select a move from root S0, such as M1 or M2.
The selected move comes from the current root and is supported by the statistics accumulated during the search.
| Search element | Role |
|---|---|
| Current root | Represents the current game state |
| Partial tree | Contains the portion of the search tree constructed so far |
| Node statistics | Accumulate information while computational resources remain |
| Root move selection | Uses the accumulated statistics to choose the program's move |
How the parts of one MCTS search work together
What the Statistics Mean in Context
A node's statistics matter in context. Before the program moves, the root still represents the current game state, and the accumulated information across the partial tree helps determine which root move is selected. The essential point is not a particular statistic or selection formula. The essential point is that the search produces accumulated node information, and move selection uses that information at the current root.
For example, a teaching diagram may show different information attached to the nodes reached by M1 and M2. That information is not a separate decision made outside the tree. It is the result of the search performed from the current root. The program compares the accumulated information available for root alternatives and selects from those alternatives when the search stops.
After the Opponent Changes the State
After the program makes a move, the opponent may make a move of its own. That opponent move changes the current game state. The old root still described the earlier situation, so it cannot remain the root for the next search. MCTS runs again with a new root node representing the new current game state.
The new search does not treat the old root as if it still described the current game. Instead, the new root anchors the next search. Any descendants of that new root that were already present in the previously constructed tree can remain available, including their accumulated statistics. Nodes unrelated to the new current state are discarded together with their statistics.
Reusable Descendants and Lost Branches
The practical rule is reachability from the new root. If an already constructed node is a descendant of the new root, it can remain available for the next search, along with the accumulated statistics associated with that reachable part of the tree. If a node belongs to a branch that is unrelated to the new current state, it is discarded with its statistics.
| Node or branch | Relationship to the new root | What happens |
|---|---|---|
| Descendant already below the new root | Reachable from the new current state | Can remain available for reuse |
| Statistics on a reusable descendant | Belong to the retained reachable tree | Can remain available with that descendant |
| Unrelated branch | Not part of the new current state | Is discarded |
| Statistics on a discarded branch | Belong to a discarded node | Are discarded with that node |
Treating the original game-start node as the root forever
The opponent's move creates a new current game state, so the old root no longer represents the situation being searched.
Fix:
Use a new root node representing the new current game state.Discarding the entire old tree after every opponent move
Descendants of the new root that were already present can remain available.
Fix:
Retain reachable descendants and their accumulated statistics; discard nodes unrelated to the new state.Keeping every old branch
Nodes unrelated to the new current state no longer belong to the reachable part of the new partial game tree.
Fix:
Check whether each branch is a descendant of the new root.Selecting a move from one observation without continued search
MCTS continues searching from the current root while computational resources remain, then uses the accumulated statistics for move selection.
Fix:
Describe the search as repeated work from the current root followed by root move selection.
Trace the Next Search
A partial tree currently has root S0. One explored branch leads to S1, and another explored branch is unrelated to S1. The game advances so that S1 becomes the new current state. Explain what happens before the next MCTS search begins.
Hints
- Ask which node now represents the current game state.
- Check which old nodes are descendants of that node.
- Track the statistics attached to retained and discarded nodes.
Answering the trace
The game advances to S1. The old tree contains S1 below S0 and also contains a separate branch unrelated to S1.
Replace the root: S1 becomes the new root because it represents the new current game state.
Retain the reachable part: Nodes already below S1 can remain available for the next search, together with their accumulated statistics.
Remove the unrelated branch: The separate branch does not belong to the new state represented by S1, so it is discarded with its statistics.
Search again: MCTS begins the next search from S1 and continues accumulating statistics while computational resources remain.
The next search is rooted at S1, reuses reachable descendants when available, and does not reuse unrelated nodes or their statistics.
The Full Re-rooting Cycle
- Identify the node representing the current game state; this is the root for the next search.
- Search from that root while time or another computational resource remains available.
- Accumulate node statistics throughout the partial tree.
- Use the accumulated statistics to select a move from the root.
- After the opponent changes the game state, make the corresponding new state the new root.
- Reuse descendants already reachable from the new root and discard unrelated nodes together with their statistics.
Partial game trees are useful because MCTS can continue from the current state rather than pretending that the old root still describes the game. Re-rooting keeps the search aligned with the game, while reachable descendants preserve relevant accumulated information.
Key Takeaways
- MCTS repeatedly searches from the root representing the current game state.
- The partial tree accumulates node statistics while computational resources remain available.
- The program selects its move from the current root using those accumulated statistics.
- An opponent's move creates a new current state and therefore a new root for the next search.
- Reachable descendants can be reused with their statistics, while unrelated nodes and their statistics are discarded.