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