Monte Carlo Tree Search

Implementation of basic Monte Carlo Tree Search algorithm.

Installation

Install with

go get github.com/int8/gomcts

Usage

The central routine is MonteCarloTreeSearch(GameState, RolloutPolicy, int) which consumes GameState, RolloutPolicy and performs requested number of MCTS simulations

To use it for your perfect-information sum-zero strictly competitive two players game (board games such as go/chess/checkers/tictactoe) you need to provide implementation of GameState and Action interfaces

// Action - game action interface
type Action interface{
	ApplyTo(GameState) GameState
}

// GameState - state of the game interface
type GameState interface {
	EvaluateGame() (GameResult, bool)
	GetLegalActions() []Action
	IsGameEnded() bool
	NextToMove() int8
}

where GameResult is just float64 alias

type GameResult float64

As current implementation expects sum-zero two players game GameResult is supposed to reflect it. For the same reason NextToMove() is expected to return 1 or -1.

You can use DefaultRolloutPolicy (actions chosen randomly) or implement your own Rollout Policy as a function with the following signature:

func YourCustomRolloutPolicy(state GameState) Action {
	...
}

Examples

Tic-Tac-Toe

There is a built-in tic-tac-toe game implementation available through TicTacToeBoardGameAction and TicTacToeGameState types

To play with it go for something like:

package main 
import "github.com/int8/gomcts"

func main() {
	initialState := gomcts.CreateTicTacToeInitialGameState(3)
	chosenAction:= gomcts.MonteCarloTreeSearch(initialState, gomcts.DefaultRolloutPolicy, 100)
	// use chosenAction further
}