Skip to main content

Preserve Search Across Turns

Reuse the search tree between moves instead of rebuilding it from scratch each turn.

You will learn to:

  • Use advance() to re-root the tree after a move
  • Handle the three AdvanceError variants

Prerequisites: Complete Your First Search.

The search-advance loop​

After choosing a move, call advance() to commit to it. The subtree below that move becomes the new root, and all other branches are discarded.

fn main() {
    println!("=== Tree Re-Rooting ===\n");

    let mut mcts = MCTSManager::new(CountingGame(0), MyMCTS, MyEval, UCTPolicy::new(0.5), ());

    // Simulate 5 turns of play, reusing the search tree each turn
    for turn in 1..=5 {
        // Search from current position
        mcts.playout_n_parallel(10_000, 4);

        let root_state = mcts.tree().root_state().0;
        let best = mcts.best_move().unwrap();
        let nodes = mcts.tree().num_nodes();

        println!("Turn {turn}: state={root_state}, best={best}, nodes={nodes}");

        // Show child stats
        let stats = mcts.root_child_stats();
        for s in &stats {
            println!(
                "  {}: {} visits, {:.1} avg reward",
                s.mov, s.visits, s.avg_reward
            );
        }

        // Commit to the best move and re-root
        mcts.advance(&best).unwrap();

        let new_nodes = mcts.tree().num_nodes();
        println!(
            "  -> Advanced to state={}, preserved {new_nodes} nodes\n",
            mcts.tree().root_state().0
        );
    }
}

Each call to advance() preserves nodes already explored below the chosen move. On the next search, those nodes do not need to be re-expanded.

Handle errors​

advance() returns Result<(), AdvanceError> with three failure modes:

VariantCauseFix
MoveNotFoundThe move is not among root childrenVerify the move is legal in the current state
ChildNotExpandedThe child was never visited during searchRun more playouts before advancing
ChildNotOwnedThe child is a transposition table aliasUse () for the transposition table, or call reset() and search from scratch

In practice, MoveNotFound is a logic error. ChildNotExpanded means you advanced to a move the search never explored -- increase your playout budget. ChildNotOwned only occurs with transposition tables.

Pondering​

Search during the opponent's turn, then advance with their actual move:

// Your turn: search and play
mcts.playout_n_parallel(50_000, 4);
let my_move = mcts.best_move().unwrap();
mcts.advance(&my_move).unwrap();
send_move(my_move);

// Opponent's turn: keep searching (pondering)
let search = mcts.playout_parallel_async(4);

// When opponent moves, stop and advance
let opponent_move = receive_move();
search.halt();
mcts.advance(&opponent_move).unwrap();

All work done during pondering is preserved if the opponent plays into a subtree you already explored.

Transposition table interaction​

advance() clears the transposition table because entries may reference nodes in the discarded portion of the tree. If you rely on transposition hits, the table rebuilds naturally during subsequent search.

To avoid transposition issues entirely, use () as your TranspositionTable type.

Expected result​

Tree reuse typically saves 20-50% of search time per turn in the mid-game, when the opponent plays a move you already explored deeply.

See also​