MCTS

README

MCTS

An efficient Go implemetation of the Monte Carlo Tree Search algorithm with a friendly interface

20 times faster than the Python implementation by Paul Sinclair et al on single core, and even faster on multiple cores with Goroutines

How to Use

1. Provide a custom environment. Implement all methods of the State interface below, where action can be any hashable type. We provide example environments under env/.

type State interface {
  GetCurrentPlayer() int
  GetPossibleActions() []any
  TakeAction(action any) State
  IsTerminal() bool
  GetReward() int
}

1. Search for the best action given the current state. You can define a custom rollout policy or use the default random one. Below is an example with the toy environment.

import (
  "github.com/Zacchaeus14/MCTS"
  "github.com/Zacchaeus14/MCTS/policy"
  "math"
)
initialState := NewNaughtsAndCrossesState()
searcher := MCTS.NewMCTS(1000, 0, 1.0/math.Sqrt(2), policy.RandomPolicy) // limit search time to one second
bestAction := searcher.Search(initialState) // {1, 1, 1}

TODO

• Modularization
• Parallel rollout

Documentation

Index

• type MCTS
  • func NewMCTS(timeLimit int, iterationLimit int, explorationConstant float64, ...) *MCTS
  • func (mcts *MCTS) Search(initialState State, verbose int) any
• type State
• type TreeNode
  • func NewTreeNode(state State, parent *TreeNode) *TreeNode

Types

type MCTS

type MCTS struct {
	TimeLimit           int
	IterationLimit      int
	LimitType           string
	ExplorationConstant float64
	Rollout             func(State, chan int)
	Root                *TreeNode
	Jobs                int
}

func NewMCTS

func NewMCTS(timeLimit int, iterationLimit int, explorationConstant float64, rollout func(State, chan int), Jobs int) *MCTS

func (*MCTS) Search

func (mcts *MCTS) Search(initialState State, verbose int) any

type State

type State interface {
	GetCurrentPlayer() int
	GetPossibleActions() []any
	TakeAction(a any) State
	IsTerminal() bool
	GetReward() int
}

type TreeNode

type TreeNode struct {
	State           State
	IsTerminal      bool
	IsFullyExpanded bool
	Parent          *TreeNode
	NumVisits       int
	TotalReward     int
	Children        map[any]*TreeNode
}

func NewTreeNode

func NewTreeNode(state State, parent *TreeNode) *TreeNode