Crate treant 

A high-performance, lock-free Monte Carlo Tree Search library.

The following example demonstrates basic usage:

use treant::{transposition_table::*, tree_policy::*, *};

// A really simple game. There's one player and one number. In each move the player can
// increase or decrease the number. The player's score is the number.
// The game ends when the number reaches 100.
//
// The best strategy is to increase the number at every step.

#[derive(Clone, Debug, PartialEq)]
struct CountingGame(i64);

#[derive(Clone, Debug, PartialEq)]
enum Move {
    Add,
    Sub,
}

impl GameState for CountingGame {
    type Move = Move;
    type Player = ();
    type MoveList = Vec<Move>;

    fn current_player(&self) -> Self::Player {
        ()
    }
    fn available_moves(&self) -> Vec<Move> {
        let x = self.0;
        if x == 100 {
            vec![]
        } else {
            vec![Move::Add, Move::Sub]
        }
    }
    fn make_move(&mut self, mov: &Self::Move) {
        match *mov {
            Move::Add => self.0 += 1,
            Move::Sub => self.0 -= 1,
        }
    }
}

impl TranspositionHash for CountingGame {
    fn hash(&self) -> u64 {
        self.0 as u64
    }
}

struct MyEvaluator;

impl Evaluator<MyMCTS> for MyEvaluator {
    type StateEvaluation = i64;

    fn evaluate_new_state(
        &self,
        state: &CountingGame,
        moves: &Vec<Move>,
        _: Option<SearchHandle<MyMCTS>>,
    ) -> (Vec<()>, i64) {
        (vec![(); moves.len()], state.0)
    }
    fn interpret_evaluation_for_player(&self, evaln: &i64, _player: &()) -> i64 {
        *evaln
    }
    fn evaluate_existing_state(
        &self,
        _: &CountingGame,
        evaln: &i64,
        _: SearchHandle<MyMCTS>,
    ) -> i64 {
        *evaln
    }
}

#[derive(Default)]
struct MyMCTS;

impl MCTS for MyMCTS {
    type State = CountingGame;
    type Eval = MyEvaluator;
    type NodeData = ();
    type ExtraThreadData = ();
    type TreePolicy = UCTPolicy;
    type TranspositionTable = ApproxTable<Self>;

    fn cycle_behaviour(&self) -> CycleBehaviour<Self> {
        CycleBehaviour::UseCurrentEvalWhenCycleDetected
    }
}

let game = CountingGame(0);
let mut mcts = MCTSManager::new(
    game,
    MyMCTS,
    MyEvaluator,
    UCTPolicy::new(0.5),
    ApproxTable::new(1024),
);
mcts.playout_n_parallel(10000, 4); // 10000 playouts, 4 search threads
mcts.tree().debug_moves();
assert_eq!(mcts.best_move().unwrap(), Move::Add);
assert_eq!(mcts.principal_variation(50), vec![Move::Add; 50]);
assert_eq!(
    mcts.principal_variation_states(5),
    vec![
        CountingGame(0),
        CountingGame(1),
        CountingGame(2),
        CountingGame(3),
        CountingGame(4),
        CountingGame(5)
    ]
);

Re-exports

pub use batch::*;

Modules

batch

transposition_table

tree_policy

Structs

AsyncSearch

Handle for an in-progress asynchronous search. Stops search on drop.

AsyncSearchOwned

Owned variant of AsyncSearch. Call halt() to stop and recover the manager.

ChildStats

Summary statistics for a root child, returned by root_child_stats().

MCTSManager

Main entry point for running MCTS search. Owns the search tree and provides methods for running playouts and extracting results.

MoveInfo

Information about a single move from a search node: the move, its evaluation, visit statistics, and a pointer to the child node.

Moves

Iterator over the moves of a search node.

NodeHandle

An immutable handle to a search node. Provides access to node data, moves, and solver state.

ScoreBounds

Proven score interval for Score-Bounded MCTS. Tracks [lower, upper] bounds on the true minimax value from the current player’s perspective. When lower == upper, the value is exact.

SearchHandle

A handle passed to evaluators and callbacks during search. Provides access to the current node and thread-local data.

SearchNode

A node in the search tree. Contains the list of moves, evaluation, visit statistics, and solver/bounds state.

SearchTree

You’re not intended to use this class (use an MCTSManager instead), but you can use it if you want to manage the threads yourself.

ThreadData

Thread-local data passed to tree policy and user code during search.

ThreadDataFull

Contains the regular thread data + some Vecs that we want to reuse the allocation of within playout

Enums

AdvanceError

Error returned when advance_root() fails.

CycleBehaviour

Strategy for handling graph cycles caused by transposition tables.

ProvenValue

Game-theoretic proven value for MCTS-Solver. Stored from the perspective of the player who moved to reach this node.

Traits

Evaluator

Evaluates game states for the search. Produces state evaluations and per-move evaluations.

GameState

Defines the game rules: available moves, state transitions, and players.

MCTS

Configuration trait for MCTS search. Defines the game, evaluator, tree policy, and optional features.

Functions

negate_bound

Negate a score bound, mapping sentinels correctly. i32::MIN (unbounded below) becomes i32::MAX (unbounded above) and vice versa.

Type Aliases

Move

The move type for the game state.

MoveEvaluation

Per-move evaluation from the tree policy (e.g., () for UCT, f64 prior for AlphaGo).

MoveInfoHandle

A borrowed reference to a MoveInfo in the search tree.

MoveList

The move list type returned by GameState::available_moves().

Player

The player type for the game state.

StateEvaluation

State evaluation produced by the Evaluator.

TreePolicyThreadData

Thread-local data for the tree policy.