Projects / MCTS in Swift

Under Construction

This project is a work-in-progress forkgithub.com of the OpenSpielgithub.com library. It adds an MCTS implementation that will form the basis of a simple AlphaZero trainer.

The design leverages some of the powerful type system abilities of Swift to achieve a maximally composable design, which allows the underlying tree-building implementation to be shared between several algorithms (various variants of MCTS, as well as Alpha-Beta search), which additionally makes them very clear.

The fundamental Swift constructs are:

  • TreeSearchProtocol, which parameterizes iterative deepening search, suitable for MCTS and AlphaBeta search.

  • EvaluatorProtocol, which encapsulates evaluation of game states in terms of a prior over actions and a value estimate. These value estimates can be point or distributional.

  • Generic SearchNode class, which encapsulates a navigable full game exploration tree. It is opportunistically solvable, and can be specialized by particular TreeSearchProtocol implementations to store child value statistics, or other data that they wish to attach to particular nodes.

I’ll add more detail here as I work on this branch.