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 ¶
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") )
Functions ¶
This section is empty.
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 (*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 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 ¶
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 ¶
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 ¶
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) Search ¶
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 ¶
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 ¶
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.