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 github.com/0xhexnumbers/gmcts

Alternatively, you can clone it yourself into your $GOPATH/src/github.com/0xhexnumbers/ folder to get the latest dev build:

git clone https://github.com/0xhexnumbers/gmcts

How To Use

package pkg

import (
    "github.com/0xhenxumbers/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 := mcts.BestAction()

        //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 := mcts.BestAction()

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 0xhexnumbers@gmail.com :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
• type Action
• type Game
• type MCTS
  • func NewMCTS(initial Game) *MCTS
  • func (m *MCTS) AddTree(t *Tree)
  • func (m *MCTS) BestAction() Action
  • 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
)

Types

type Action

type Action interface{}

Action is the interface that represents an action that can be performed on a Game.

Any implementation of Action should be comparable (i.e. be a key in a map)

type Game

type Game interface {
	//GetActions returns a list of actions to consider
	GetActions() []Action

	//ApplyAction applies the given action to the game state,
	//and returns a new game state and an error for invalid actions
	ApplyAction(Action) (Game, error)

	//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 comparable (i.e. be a key in a map) and 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

If either the Game or its Action types are not comparable, this function panics

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() Action

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

BestAction returns nil if it has received no trees to search through or if the current state it's considering has no legal actions or 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 1, 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

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

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