gmcts

README

GMCTS - Monte-Carlo Tree Search (the g stands for whatever you want it to mean :^) )

GMCTS is an implementation of the Monte-Carlo Tree Search algorithm with support for any deterministic game.

How To Install

This project requires Go 1.7+ to run. To install, use go get:

go get git.sr.ht/~bonbon/gmcts

Alternatively, you can clone it yourself into your $GOPATH/src/git.sr.ht/~bonbon/ folder to get the latest dev build:

git clone https://git.sr.ht/~bonbon/gmcts

How To Use

package pkg

import (
    "git.sr.ht/~bonbon/gmcts"
)

func NewGame() gmcts.Game {
    var game gmcts.Game
    //...
    //Setup a new game
    //...
    return game
}

func runGame() {
    gameState := NewGame()

    //MCTS algorithm will play against itself
    //until a terminal state has been reached
    for !gameState.IsTerminal() {
        mcts := gmcts.NewMCTS(gameState)

        //Spawn a new tree and play 1000 game simulations
        tree := mcts.SpawnTree()
        tree.SearchRounds(1000)

        //Add the searched tree into the mcts tree collection
        mcts.AddTree(tree)

        //Get the best action based off of the trees collected from mcts.AddTree()
        bestAction, err := mcts.BestAction()
        if err != nil {
            //...
            //handle error
            //...
        }

        //Update the game state using the tree's best action
        gameState, _ = gameState.ApplyAction(bestAction)
    }
}

If you choose to, you can run multiple trees concurrently.

concurrentTrees := 4

mcts := gmcts.NewMCTS(gameState)

//Run 4 trees concurrently
var wait sync.WaitGroup
wait.Add(concurrentTrees)
for i := 0; i < concurrentTrees; i++ {
    go func(){
        tree := mcts.SpawnTree()
        tree.SearchRounds(1000)
        mcts.AddTree(tree)
        wait.Done()
    }()
}
//Wait for the 4 trees to finish searching
wait.Wait()

bestAction, err := mcts.BestAction()
if err != nil {
    //...
    //handle error
    //...
}

gameState, _ = gameState.ApplyAction(bestAction)

Testing

You can test this package with go test. The test plays a game of tic-tac-toe against itself. The test should:

1. Start the game by placing an x piece in the middle, and
2. Finish in a draw.

If either of these fail, the test fails. It's a rather neat way to make sure everything works as intended!

Documentation

Documentation for this package can be found either at godoc.org or pkg.go.dev

Bug Reports

Email me at bonbon@bonbon.moe :D

Documentation

Overview

Package gmcts is a generic implementation of the Monte-Carlo Tree Search (mcts) algorithm.

This package attempts to save memory and time by caching states as to not have duplicate nodes in the search tree. This optimization is efficient for games like tic-tac-toe, checkers, and go among others.

This package also allows support for tree parallelization. Trees may be spawned and ran in their own goroutine. After searching, they may be compiled together to produce a more informed action than just searching through one tree.

Index

• Constants
• Variables
• type Game
• type MCTS
  • func NewMCTS(initial Game) *MCTS
  • func (m *MCTS) AddTree(t *Tree)
  • func (m *MCTS) BestAction() (int, error)
  • func (m *MCTS) SetSeed(seed int64)
  • func (m *MCTS) SpawnCustomTree(explorationConst float64) *Tree
  • func (m *MCTS) SpawnTree() *Tree
• type Player
• type Tree
  • func (t Tree) MaxDepth() int
  • func (t Tree) Nodes() int
  • func (t Tree) Rounds() int
  • func (t *Tree) Search(duration time.Duration)
  • func (t *Tree) SearchContext(ctx context.Context)
  • func (t *Tree) SearchRounds(rounds int)

Constants

const (
	//DefaultExplorationConst is the default exploration constant of UCB1 Formula
	//Sqrt(2) is a frequent choice for this constant as specified by
	//https://en.wikipedia.org/wiki/Monte_Carlo_tree_search
	DefaultExplorationConst = math.Sqrt2
)

Variables

var (
	//ErrNoTrees notifies the callee that the MCTS wrapper has recieved to trees to analyze
	ErrNoTrees = errors.New("gmcts: mcts wrapper has collected to trees to analyze")

	//ErrTerminal notifies the callee that the given state is terminal
	ErrTerminal = errors.New("gmcts: given game state is a terminal state, therefore, it cannot return an action")

	//ErrNoActions notifies the callee that the given state has <= 0 actions
	ErrNoActions = errors.New("gmcts: given game state is not terminal, yet the state has <= 0 actions to search through")
)

Types

type Game

type Game interface {
	//Len returns the number of actions to consider.
	Len() int

	//ApplyAction applies the ith action (0-indexed) to the game state,
	//and returns a new game state and an error for invalid actions
	ApplyAction(i int) (Game, error)

	//Hash returns a unique representation of the state.
	//Any return value must be comparable.
	Hash() interface{}

	//Player returns the player that can take the next action
	Player() Player

	//IsTerminal returns true if this game state is a terminal state
	IsTerminal() bool

	//Winners returns a list of players that have won the game if
	//IsTerminal() returns true
	Winners() []Player
}

Game is the interface that represents game states.

Any implementation of Game should be immutable (state cannot change as this package calls any function).

type MCTS

type MCTS struct {
	// contains filtered or unexported fields
}

MCTS contains functionality for the MCTS algorithm

func NewMCTS

func NewMCTS(initial Game) *MCTS

NewMCTS returns a new MCTS wrapper

func (*MCTS) AddTree

func (m *MCTS) AddTree(t *Tree)

AddTree adds a searched tree to its list of trees to consider when deciding upon an action to take.

func (*MCTS) BestAction

func (m *MCTS) BestAction() (int, error)

BestAction takes all of the searched trees and returns the index of the best action based on the highest win percentage of each action.

BestAction returns ErrNoTrees if it has received no trees to search through, ErrNoActions if the current state it's considering has no legal actions, or ErrTerminal if the current state it's considering is terminal.

func (*MCTS) SetSeed

func (m *MCTS) SetSeed(seed int64)

SetSeed sets the seed of the next tree to be spawned. This value is initially set to 0, and increments on each spawned tree.

func (*MCTS) SpawnCustomTree

func (m *MCTS) SpawnCustomTree(explorationConst float64) *Tree

SpawnCustomTree creates a new search tree with a given exploration constant.

func (*MCTS) SpawnTree

func (m *MCTS) SpawnTree() *Tree

SpawnTree creates a new search tree. The tree returned uses Sqrt(2) as the exploration constant.

type Player

type Player int

Player is an id for the player

type Tree

type Tree struct {
	// contains filtered or unexported fields
}

Tree represents a game state tree

func (Tree) MaxDepth

func (t Tree) MaxDepth() int

MaxDepth returns the maximum depth of this tree. The value can be thought of as the amount of moves ahead this tree searched through.

func (Tree) Nodes

func (t Tree) Nodes() int

Nodes returns the number of nodes created on this tree.

func (Tree) Rounds

func (t Tree) Rounds() int

Rounds returns the number of MCTS rounds were performed on this tree.

func (*Tree) Search

func (t *Tree) Search(duration time.Duration)

Search searches the tree for a specified time

Search will panic if the Game's ApplyAction method returns an error or if any game state's Hash() method returns a noncomparable value.

func (*Tree) SearchContext

func (t *Tree) SearchContext(ctx context.Context)

SearchContext searches the tree using a given context

SearchContext will panic if the Game's ApplyAction method returns an error or if any game state's Hash() method returns a noncomparable value.

func (*Tree) SearchRounds

func (t *Tree) SearchRounds(rounds int)

SearchRounds searches the tree for a specified number of rounds

SearchRounds will panic if the Game's ApplyAction method returns an error or if any game state's Hash() method returns a noncomparable value.