mcts

Package mcts provides parallel monte-carlo tree search for your Go applications.

Installation

Go latest is recommended.

go get -u github.com/go-mcts/mcts

Getting started

See examples directory.

Implements mcts.Move and mcts.State:

// examples/nim/nim.go
type Move int

type State struct {
	playerToMove int
	chips        int
}

func (s *State) PlayerToMove() int {
	return s.playerToMove
}

func (s *State) HasMoves() bool {
	s.checkInvariant()
	return s.chips > 0
}

func (s *State) GetMoves() []mcts.Move {
	s.checkInvariant()

	var moves []mcts.Move
	for i := 1; i <= min(3, s.chips); i++ {
		moves = append(moves, i)
	}
	return moves
}

func (s *State) DoMove(move mcts.Move) {
	m := move.(int)
	if m < 1 || m > 3 {
		panic("illegal move")
	}
	s.checkInvariant()

	s.chips -= m
	s.playerToMove = 3 - s.playerToMove

	s.checkInvariant()
}

func (s *State) DoRandomMove(rd *rand.Rand) {
	if s.chips <= 0 {
		panic("invalid chips")
	}
	s.checkInvariant()

	max := min(3, s.chips)
	s.DoMove(rd.Intn(max) + 1)

	s.checkInvariant()
}

func (s *State) GetResult(currentPlayerToMove int) float64 {
	if s.chips != 0 {
		panic("game not over")
	}
	s.checkInvariant()

	if s.playerToMove == currentPlayerToMove {
		return 1.0
	}
	return 0.0
}

func (s *State) Clone() mcts.State {
	return &State{
		playerToMove: s.playerToMove,
		chips:        s.chips,
	}
}

Run mcts.ComputeMove:

state := &State{
	playerToMove: 1,
	chips:        chips,
}
move := mcts.ComputeMove(state, mcts.MaxIterations(100000), mcts.Verbose(true))

By default, runtime.NumCPU() goroutines are started for compute:

2021-10-16T16:13:33+08:00       DEBUG   100000 games played (493618.37 / second).
2021-10-16T16:13:33+08:00       DEBUG   100000 games played (487598.00 / second).
2021-10-16T16:13:33+08:00       DEBUG   100000 games played (474579.62 / second).
2021-10-16T16:13:33+08:00       DEBUG   100000 games played (470514.17 / second).
2021-10-16T16:13:33+08:00       DEBUG   Move: 2 (16% visits) (48% wins)
2021-10-16T16:13:33+08:00       DEBUG   Move: 1 (72% visits) (67% wins)
2021-10-16T16:13:33+08:00       DEBUG   Move: 3 (13% visits) (48% wins)
2021-10-16T16:13:33+08:00       DEBUG   Best: 1 (72% visits) (67% wins)
2021-10-16T16:13:33+08:00       DEBUG   400000 games played in 0.21 s. (1881366.23 / second, 4 parallel jobs).

License

This project is under the MIT License. See the LICENSE file for the full license text.