Crate mcts

This is a library for Monte Carlo tree search.

It is still under development and the documentation isn't good. However, the following example may be helpful:

use mcts::*;
use mcts::tree_policy::*;
use mcts::transposition_table::*;
 
// 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)]);

Modules

transposition_table
tree_policy

Structs

AsyncSearch
AsyncSearchOwned
MCTSManager
MoveInfo
Moves
NodeHandle
SearchHandle
SearchNode
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

Enums

CycleBehaviour

Traits

Evaluator
GameState
MCTS

Type Definitions

Move
MoveEvaluation
MoveInfoHandle
MoveList
Player
StateEvaluation
TreePolicyThreadData