Skip to content
Monte carlo tree search in Go language
Branch: master
Clone or download
Latest commit 35cc976 Apr 22, 2018
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
.gitignore .gitignore Apr 14, 2018
.travis.yml
LICENSE gofmt -s Apr 22, 2018
README.md
games.go
gomcts_test.go
mcts.go comments Apr 22, 2018
policies.go comments Apr 22, 2018
tictactoe.go comments Apr 22, 2018
tree.go refactoring + bug fixes, still not there Apr 18, 2018
utils.go

README.md

Build Status GoDoc Reference Go Report Card

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
}   
You can’t perform that action at this time.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.