go-atari-montecarlo, v1.1

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

Optimization via parallel move searching.

Change Log

optimization via parallel move searching:
- parallel game simulating:
  - of a single node child;
  - of all node children;
- parallel tree building;
easily extensible and composable architecture:
- all parallel algorithms can be combined in any combination.

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;
optimization via parallel move searching:
- parallel game simulating:
  - of a single node child;
  - of all node children;
- parallel tree building;
easily extensible and composable architecture:
- of move selectors:
  - of node scorers;
- of game simulators;
- of tree builders:
  - of iteration terminators;
- of move searchers.

Examples

searchers.MoveSearcher.SearchMove() with parallel game simulating of a single node child:

package main

import (
    "fmt"
    "log"
    "math"
    "runtime"

    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/simulators/bulky"
    "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 := bulky.FirstNodeSimulator{
        Simulator: simulators.ParallelSimulator{
            Simulator: simulators.RolloutSimulator{
                MoveSelector: randomSelector,
            },
            Concurrency: runtime.NumCPU(),
        },
    }
    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 parallel game simulating of all node children:

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/simulators/bulky"
    "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 := bulky.AllNodesSimulator{
        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 parallel tree building:

package main

import (
    "fmt"
    "log"
    "math"
    "runtime"

    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/simulators/bulky"
    "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 := bulky.FirstNodeSimulator{
        Simulator: simulators.RolloutSimulator{
            MoveSelector: randomSelector,
        },
    }
    builder := builders.ParallelBuilder{
        Builder: builders.IterativeBuilder{
            Builder: builders.TreeBuilder{
                NodeSelector: generalSelector,
                Simulator:    simulator,
            },
            Terminator: terminators.NewPassTerminator(2),
        },
        Concurrency: runtime.NumCPU(),
    }
    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}}
}

Benchmarks

With parallel game simulating of a single node child:

BenchmarkSearch_ucbSelectorReusedTreeParallelSimulatorAnd10Passes-8                   20      76230989 ns/op
BenchmarkSearch_ucbSelectorReusedTreeParallelSimulatorAnd100Passes-8                   2     628487473 ns/op

With parallel game simulating of all node children:

BenchmarkSearch_ucbSelectorReusedTreeParallelBulkySimulatorAnd10Passes-8              10     182008392 ns/op
BenchmarkSearch_ucbSelectorReusedTreeParallelBulkySimulatorAnd100Passes-8              1    1966000152 ns/op

With parallel tree building:

BenchmarkSearch_ucbSelectorReusedTreeParallelBuilderAnd10Passes-8                     20      67547918 ns/op
BenchmarkSearch_ucbSelectorReusedTreeParallelBuilderAnd100Passes-8                     2     747372477 ns/op

Repository

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

Content: code.

License: MIT.