Struct TreeSearch 

pub struct TreeSearch<E: Environment> {
    pub transposition_table: Option<HashMap<u64, u32>>,
    /* private fields */
}

Game-tree MCTS engine.

Given an Environment, searches for the best action by running repeated simulations through a growing tree of explored states.

Type Parameters

• E: the environment type implementing Environment.

Examples

use mctrust::{Environment, Outcome, TreeSearch, SearchConfig, Reward};

#[derive(Clone)]
struct Counter { value: i32, target: i32 }

#[derive(Clone, Debug, PartialEq)]
enum Step { Inc, Dec }

impl Environment for Counter {
    type Action = Step;

    fn legal_actions(&self) -> Vec<Step> {
        vec![Step::Inc, Step::Dec]
    }

    fn apply(&mut self, action: &Step) {
        match action {
            Step::Inc => self.value += 1,
            Step::Dec => self.value -= 1,
        }
    }

    fn evaluate(&self) -> Outcome {
        if self.value == self.target {
            Outcome::Success(Reward::WIN)
        } else if (self.value - self.target).abs() > 10 {
            Outcome::Failure
        } else {
            Outcome::Ongoing
        }
    }
}

let game = Counter { value: 0, target: 3 };
let config = SearchConfig::builder().iterations(1_000).max_depth(15).build();
let mut search = TreeSearch::new(game, config);

if let Some(best) = search.run() {
    // best is the action with most visits from root
    println!("Best action: {best:?}");
}
let _all_moves = vec![Step::Inc, Step::Dec];

Fields

transposition_table: Option<HashMap<u64, u32>>

Optional Transposition Table (DAG) storing HashMap<EnvironmentHash, NodeIndex>.

Implementations

impl<E: Environment> TreeSearch<E>

pub fn best_root_action(&self) -> Option<E::Action>

Returns the root child with the most visits (robust child policy).

Use this to retrieve the best action after manual iteration via run_step() or run_until().

impl<E: Environment> TreeSearch<E>

pub fn new(environment: E, config: SearchConfig) -> Self

Creates a new game-tree search from an environment and configuration.

Parameters

• environment: Root state to search from.
• config: Search hyperparameters.

Returns

Returns a TreeSearch with a root node populated from the environment’s legal actions.

Panics

This function does not panic.

Examples

use mctrust::{Environment, TreeSearch, Outcome, SearchConfig};

#[derive(Clone)]
struct Env;

impl Environment for Env {
    type Action = ();
    fn legal_actions(&self) -> Vec<Self::Action> { vec![()] }
    fn apply(&mut self, _action: &Self::Action) {}
    fn evaluate(&self) -> Outcome { Outcome::Neutral }
}

let search = TreeSearch::new(Env, SearchConfig::default());
assert_eq!(search.tree_size(), 1);

pub fn with_seed(environment: E, config: SearchConfig, seed: u64) -> Self

Creates a new game-tree search with a deterministic RNG seed.

Parameters

• environment: Root state to search from.
• config: Search hyperparameters.
• seed: Seed used for rollout randomness and tie-breaking.

Returns

Returns a deterministic TreeSearch.

Panics

This function does not panic.

pub fn checkpoint(&self) -> TreeSearchCheckpoint<E>

where E: Serialize + for<'de> Deserialize<'de>, E::Action: Serialize + for<'de> Deserialize<'de> + Clone,

Creates a serialisable checkpoint of the current search state.

This can be used to pause and resume search work in a separate process.

Parameters

This function takes no additional parameters.

Returns

Returns a TreeSearchCheckpoint containing the root environment, config, and tree.

Panics

This function does not panic.

pub fn restore(checkpoint: TreeSearchCheckpoint<E>) -> Self

where E: Serialize + for<'de> Deserialize<'de>, E::Action: Serialize + for<'de> Deserialize<'de> + Clone,

Restores a search state from a checkpoint.

Parameters

• checkpoint: Previously captured search state.

Returns

Returns a TreeSearch resumed from the checkpoint.

Panics

This function does not panic.

pub fn run(&mut self) -> Option<E::Action>

Runs the search for the configured number of iterations, or until the optional time budget is exhausted, whichever comes first.

Returns

Returns the most-visited root action, or None if the environment has no legal actions.

Examples

use mctrust::{Environment, TreeSearch, Outcome, Reward, SearchConfig};

#[derive(Clone)]
struct Env(bool);

#[derive(Clone, Debug, PartialEq)]
enum Action { Win }

impl Environment for Env {
    type Action = Action;
    fn legal_actions(&self) -> Vec<Self::Action> { if self.0 { vec![] } else { vec![Action::Win] } }
    fn apply(&mut self, _action: &Self::Action) { self.0 = true; }
    fn evaluate(&self) -> Outcome { if self.0 { Outcome::Success(Reward::WIN) } else { Outcome::Ongoing } }
}

let mut search = TreeSearch::with_seed(Env(false), SearchConfig::builder().iterations(8).build(), 1);
assert_eq!(search.run(), Some(Action::Win));

pub fn run_step(&mut self)

Executes exactly one MCTS iteration (select → expand → simulate → backpropagate).

This is the fundamental building block for fine-grained control. Use it when:

• You need to interleave search with network I/O (e.g., batched NN evaluation)
• You want to stream intermediate results to a progress bar or TUI
• You need to check an external cancellation token between iterations
• You are building a custom time-control or pondering loop

After calling this N times, use best_root_action(), principal_variation(), or root_stats() to inspect the result.

pub fn run_parallel(&mut self, threads: usize) -> Option<E::Action>

where E: Send + Sync, E::Action: Eq + Hash + Send + Sync,

Runs the search utilizing root-level parallelism across available threads.

This runs multiple distinct search trees in parallel, effectively achieving lock-free linear scaling, before merging the visitation statistics of the root branches optimally.

Parameters

• threads: Number of simultaneous MCTS instances to run.

pub fn root_stats(&self) -> Vec<(E::Action, NodeStats)>

where E::Action: Clone,

Returns statistics for each root child.

Parameters

This function takes no additional parameters.

Returns

Returns (action, stats) pairs for every expanded child of the root.

Panics

This function does not panic.

pub fn tree_size(&self) -> usize

Returns the total number of nodes currently stored in the search tree.

Parameters

This function takes no additional parameters.

Returns

Returns the arena length.

Panics

This function does not panic.

pub fn total_simulations(&self) -> u32

Returns the total number of simulations run so far.

Parameters

This function takes no additional parameters.

Returns

Returns the root visit count.

Panics

This function does not panic.

pub fn with_evaluator(&mut self, evaluator: Arc<dyn Evaluator<E>>)

Attaches a pluggable evaluator that replaces random rollout with a domain-specific or neural network-based leaf evaluation.

When set, the engine calls evaluator.evaluate(env) instead of running a random rollout to a terminal state.

Examples

use mctrust::{Environment, Evaluator, TreeSearch, Outcome, Reward, SearchConfig};

#[derive(Clone)]
struct Env;

impl Environment for Env {
    type Action = ();
    fn legal_actions(&self) -> Vec<()> { vec![()] }
    fn apply(&mut self, _: &()) {}
    fn evaluate(&self) -> Outcome { Outcome::Neutral }
}

struct ConstEval;
impl Evaluator<Env> for ConstEval {
    fn evaluate(&self, _: &Env) -> Reward { Reward::new(0.8) }
}

let mut search = TreeSearch::new(Env, SearchConfig::builder().iterations(10).build());
search.with_evaluator(std::sync::Arc::new(ConstEval));

pub fn with_max_nodes(&mut self, limit: usize)

Sets the maximum number of tree nodes the search may allocate.

When this limit is reached, expansion stops and the engine runs selection + simulation on existing nodes only. Use this to bound memory usage in resource-constrained environments.

pub fn run_until<F>(&mut self, predicate: F) -> Option<E::Action>

where F: FnMut(&Self) -> bool,

Runs the search until predicate returns true.

The predicate receives the current search state after each iteration, allowing arbitrary stopping conditions: target reward, time limit, external cancellation, convergence detection, etc.

Examples

// Stop when we've found a line with > 0.9 reward, or 50k iterations
search.run_until(|s| {
    s.best_root_reward().unwrap_or(0.0) > 0.9
    || s.total_simulations() >= 50_000
});

pub fn principal_variation_states(&self) -> Vec<E>

where E::Action: Clone,

Replays the principal variation through the environment, returning the full sequence of intermediate states.

This is invaluable for debugging, visualization, and post-search analysis. The first element is always the root state; the last is the state after applying the final PV move.

Panics

This function does not panic. The internal unwrap on states.last() is safe because the vector always has at least one element (the root).

pub fn export_dot(&self, depth: usize) -> String

where E::Action: Debug,

Exports a Graphviz DOT representation of the top depth levels of the search tree, with node visit counts and average rewards as labels.

dot -Tsvg tree.dot -o tree.svg

pub fn uses_rave(&self) -> bool

Reports whether the configured search uses RAVE blending.

Parameters

This function takes no additional parameters.

Returns

Returns true when config.rave.enabled is set.

Panics

This function does not panic.

pub fn enable_dag(&mut self)

Enables the DAG transposition table, allowing identical states reached through different action sequences to share a single node in the search tree.

This dramatically reduces memory usage and accelerates convergence in environments with many transpositions (board games, planning problems, etc.).

pub fn disable_dag(&mut self)

Disables the DAG transposition table and frees its memory.

pub fn dag_hit_count(&self) -> usize

Returns the number of state hashes stored in the transposition table, a proxy for how many unique states the engine has explored.

pub fn principal_variation(&self) -> Vec<E::Action>

where E::Action: Clone,

Extracts the principal variation — the sequence of actions the engine considers optimal from the root, chosen by following the most-visited child at every level of the tree.

This is the single most important debugging and visualization primitive for any tree search engine. Safe in DAG mode (cycle-aware).

pub fn best_root_reward(&self) -> Option<f64>

Returns the average reward of the best root action, or None if no simulations have been performed.

pub fn advance_to_action(&mut self, action: &E::Action) -> bool

Tree reuse — re-roots the search tree at the child reached by action, preserving the entire subtree and all accumulated statistics.

This is the technique used by every elite game engine (Stockfish, Leela, KataGo). Instead of discarding the tree after each move and starting from scratch, advance_to_action keeps all the work done in the selected subtree, giving the next search a massive warm start.

Returns true if the action was found among the root’s children and the tree was successfully re-rooted. Returns false if the action didn’t match any child (the tree remains unchanged — caller should create a fresh search instead).

Examples

// After choosing an action, re-root to reuse the subtree:
if let Some(best) = search.run() {
    search.advance_to_action(&best);
    // Next search.run() starts with the preserved subtree.
}

Trait Implementations

impl<E: Clone + Environment> Clone for TreeSearch<E>

where E::Action: Clone,

fn clone(&self) -> TreeSearch<E>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.