The highest tagged major version is
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 := 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:
- Start the game by placing an x piece in the middle, and
- 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 ¶
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 ¶
This section is empty.
Functions ¶
This section is empty.
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 ¶
NewMCTS returns a new MCTS wrapper
If either the Game or its Action types are not comparable, this function panics
func (*MCTS) AddTree ¶
AddTree adds a searched tree to its list of trees to consider when deciding upon an action to take.
func (*MCTS) BestAction ¶
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 ¶ added in v1.2.0
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 ¶ added in v1.0.2
SpawnCustomTree creates a new search tree with a given exploration constant.
type Tree ¶
type Tree struct {
// contains filtered or unexported fields
}
Tree represents a game state tree
func (Tree) MaxDepth ¶ added in v1.2.0
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) Rounds ¶ added in v1.2.0
Rounds returns the number of MCTS rounds were performed on this tree.
func (*Tree) Search ¶
Search searches the tree for a specified time
Search will panic if the Game's ApplyAction method returns an error
func (*Tree) SearchContext ¶
SearchContext searches the tree using a given context
SearchContext will panic if the Game's ApplyAction method returns an error
func (*Tree) SearchRounds ¶
SearchRounds searches the tree for a specified number of rounds
SearchRounds will panic if the Game's ApplyAction method returns an error
Source Files