go-atari-montecarlo, v1.0

The library that implements an Atari Go engine based on the Monte Carlo tree search algorithm.

Major version.

Features

• move searching via the Monte Carlo tree search algorithm:
  • move selectors:
    • random selecting;
    • selecting by a maximal node score:
      • scoring by node win rate;
      • scoring by the Upper Confidence Bound algorithm;
  • game simulating by simple random rollout;
  • tree building:
    • by a single pass;
    • by iterative passes:
      • iteration terminating:
        • by a pass;
        • by a time;
  • move searchers:
    • searcher that doesn't reuse a built tree;
    • searcher that reuses a built tree;
    • fallback searcher that uses an additional searcher when the primary one returns an error;
• easily extensible and composable architecture:
  • of move selectors:
    • of node scorers;
  • of game simulators;
  • of tree builders:
    • of iteration terminators;
  • of move searchers.

Installation

$ go get github.com/thewizardplusplus/go-atari-montecarlo

Examples

searchers.MoveSearcher.SearchMove() without reusing of a built tree:

package main

import (
    "fmt"
    "log"
    "math"

    models "github.com/thewizardplusplus/go-atari-models"
    "github.com/thewizardplusplus/go-atari-montecarlo/builders"
    "github.com/thewizardplusplus/go-atari-montecarlo/builders/terminators"
    "github.com/thewizardplusplus/go-atari-montecarlo/searchers"
    "github.com/thewizardplusplus/go-atari-montecarlo/selectors"
    "github.com/thewizardplusplus/go-atari-montecarlo/selectors/scorers"
    "github.com/thewizardplusplus/go-atari-montecarlo/simulators"
    "github.com/thewizardplusplus/go-atari-montecarlo/tree"
)

func main() {
    // +-+-+-+-+-+
    // |W|W|W|W|X|
    // +-+-+-+-+-+
    // |W|W|W|W|W|
    // +-+-+-+-+-+
    // |W|W|W|W|W|
    // +-+-+-+-+-+
    // |W|W|W|W|W|
    // +-+-+-+-+-+
    // |W|W|W|W|W|
    // +-+-+-+-+-+
    board := models.NewBoard(models.Size{Width: 5, Height: 5})
    points := board.Size().Points()
    for _, point := range points[:len(points)-1] {
        board = board.ApplyMove(models.Move{Color: models.White, Point: point})
    }

    randomSelector := selectors.MoveSelector{
        NodeSelector: selectors.RandomSelector{},
    }
    generalSelector := selectors.MaximalSelector{
        NodeScorer: scorers.UCBScorer{Factor: math.Sqrt2},
    }

    simulator := simulators.RolloutSimulator{
        MoveSelector: randomSelector,
    }
    builder := builders.IterativeBuilder{
        Builder: builders.TreeBuilder{
            NodeSelector: generalSelector,
            Simulator:    simulator,
        },
        Terminator: terminators.NewPassTerminator(2),
    }
    searcher := searchers.MoveSearcher{
        Builder:      builder,
        NodeSelector: generalSelector,
    }

    root := tree.NewPreliminaryNode(board, models.Black)
    node, err := searcher.SearchMove(root)
    if err != nil {
        log.Fatal(err)
    }

    fmt.Printf("%+v\n", node.Move)

    // Output: {Color:0 Point:{Column:4 Row:4}}
}

searchers.MoveSearcher.SearchMove() with reusing of a built tree:

package main

import (
    "fmt"
    "log"
    "math"

    models "github.com/thewizardplusplus/go-atari-models"
    "github.com/thewizardplusplus/go-atari-montecarlo/builders"
    "github.com/thewizardplusplus/go-atari-montecarlo/builders/terminators"
    "github.com/thewizardplusplus/go-atari-montecarlo/searchers"
    "github.com/thewizardplusplus/go-atari-montecarlo/selectors"
    "github.com/thewizardplusplus/go-atari-montecarlo/selectors/scorers"
    "github.com/thewizardplusplus/go-atari-montecarlo/simulators"
    "github.com/thewizardplusplus/go-atari-montecarlo/tree"
)

func main() {
    // +-+-+-+-+-+
    // |W|W|W|W|X|
    // +-+-+-+-+-+
    // |W|W|W|W|W|
    // +-+-+-+-+-+
    // |W|W|W|W|W|
    // +-+-+-+-+-+
    // |W|W|W|W|W|
    // +-+-+-+-+-+
    // |W|W|W|W|W|
    // +-+-+-+-+-+
    board := models.NewBoard(models.Size{Width: 5, Height: 5})
    points := board.Size().Points()
    for _, point := range points[:len(points)-1] {
        board = board.ApplyMove(models.Move{Color: models.White, Point: point})
    }

    randomSelector := selectors.MoveSelector{
        NodeSelector: selectors.RandomSelector{},
    }
    generalSelector := selectors.MaximalSelector{
        NodeScorer: scorers.UCBScorer{Factor: math.Sqrt2},
    }

    simulator := simulators.RolloutSimulator{
        MoveSelector: randomSelector,
    }
    builder := builders.IterativeBuilder{
        Builder: builders.TreeBuilder{
            NodeSelector: generalSelector,
            Simulator:    simulator,
        },
        Terminator: terminators.NewPassTerminator(2),
    }

    baseSearcher := searchers.MoveSearcher{
        Builder:      builder,
        NodeSelector: generalSelector,
    }
    searcher := searchers.FallbackSearcher{
        PrimarySearcher:  searchers.NewReusedSearcher(baseSearcher),
        FallbackSearcher: baseSearcher,
    }

    root := tree.NewPreliminaryNode(board, models.Black)
    node, err := searcher.SearchMove(root)
    if err != nil {
        log.Fatal(err)
    }

    fmt.Printf("%+v\n", node.Move)

    // Output: {Color:0 Point:{Column:4 Row:4}}
}

Benchmarks

With random node selecting:

BenchmarkSearch_randomSelectorAnd10Passes-8                           50      28430196 ns/op
BenchmarkSearch_randomSelectorAnd100Passes-8                           5     280071210 ns/op

With random node selecting and reusing of a built tree:

BenchmarkSearch_randomSelectorAnd10PassesAndReusedTree-8              50      28341600 ns/op
BenchmarkSearch_randomSelectorAnd100PassesAndReusedTree-8              5     291660910 ns/op

With node selecting by maximal node win rate:

BenchmarkSearch_winRateSelectorAnd10Passes-8                          50      29879387 ns/op
BenchmarkSearch_winRateSelectorAnd100Passes-8                          5     297545103 ns/op

With node selecting by maximal node win rate and reusing of a built tree:

BenchmarkSearch_winRateSelectorAnd10PassesAndReusedTree-8             50      29489844 ns/op
BenchmarkSearch_winRateSelectorAnd100PassesAndReusedTree-8             5     277382367 ns/op

With node selecting by the Upper Confidence Bound algorithm:

BenchmarkSearch_ucbSelectorAnd10Passes-8                              50      29158293 ns/op
BenchmarkSearch_ucbSelectorAnd100Passes-8                              5     284821554 ns/op

With node selecting by the Upper Confidence Bound algorithm and reusing of a built tree:

BenchmarkSearch_ucbSelectorAnd10PassesAndReusedTree-8                 50      29270414 ns/op
BenchmarkSearch_ucbSelectorAnd100PassesAndReusedTree-8                 5     289535829 ns/op

Repository

Link: https://github.com/thewizardplusplus/go-atari-montecarlo/tree/v1.0.

Content: code.

License: MIT.

Screenshots

Tournament between different settings of move searching