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::*;
 
// 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 = ();
 
    fn current_player(&self) -> Self::Player {
        ()
    }
    fn available_moves(&self) -> Vec<Self::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,
        }
    }
}
 
struct MyEvaluator;
 
impl Evaluator<MyMCTS> for MyEvaluator {
    type StateEvaluation = i64;
 
    fn evaluate_new_state(&self, state: &CountingGame, moves: &[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;
}
 
let game = CountingGame(0);
let mut mcts = MCTSManager::new(game, MyMCTS, MyEvaluator, UCTPolicy::new(0.5));
mcts.playout_n_parallel(100000, 4);
mcts.tree().debug_moves();
assert_eq!(mcts.principal_variation(5),
    vec![Move::Add, Move::Add, Move::Add, Move::Add, Move::Add]);
assert_eq!(mcts.principal_variation_states(5),
    vec![
        CountingGame(0),
        CountingGame(1),
        CountingGame(2),
        CountingGame(3),
        CountingGame(4),
        CountingGame(5)]);

Modules

tree_policy

Structs

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

Traits

Evaluator
GameState
MCTS

Type Definitions

Move
MoveEvaluation
MoveList
Player
StateEvaluation
TreePolicyThreadData