Decision-making algorithms for games, one pip install away.

The problem

Search algorithms such as Minimax and Monte Carlo Tree Search power many game-playing agents, and they’re the core idea behind AlphaZero. Yet when I reviewed the state of the art I found no simple Python library that brought them together, let alone one for imperfect-information games, where the agent can’t see everything: the opponent’s cards, the deck or hidden pieces.

The goal of the thesis was to build that library, publish it so anyone could use it, and validate every algorithm experimentally.

Four algorithms, one interface

pyplAI implements four algorithms. To use any of them, you only need to describe your game through a few methods: list the moves, apply one, check whether the game is over and who won.

• Minimax with alpha-beta pruning, for perfect-information games such as checkers.
• MCTS with UCT, which instead of exploring the whole tree simulates games and focuses on the most promising moves.
• SO-ISMCTS, which builds a single tree from the player’s point of view and reasons over the possible versions of the hidden information.
• MO-ISMCTS, which keeps one tree per player and groups the moves an opponent can’t tell apart. It’s the most faithful option when actions are only partly observable.

This is how MCTS runs on any game that implements that interface (the API uses Spanish names):

import pyplAI

mcts = pyplAI.MCTS(
    Juego.aplica_movimiento,    # apply a move
    Juego.obtiene_movimientos,  # list legal moves
    Juego.es_estado_final,      # is the game over?
    Juego.gana_jugador,         # did this player win?
    numeroJugadores=2,
    tiempoEjecucion=1,          # search time per move, in seconds
)

movimiento = mcts.ejecuta(juego)

Eight games to prove it

To validate the library I built eight complete games, which double as usage examples: tic-tac-toe, Ultimate Tic-Tac-Toe and checkers with Minimax and MCTS; escoba, blackjack and Stratego with SO-ISMCTS; and Phantom and Holjjak, which have hidden moves, with MO-ISMCTS.

For Stratego I added a genetic algorithm that searches for the best initial piece layout, a decision the search tree can’t make on its own.

Results

I reran the thesis experiments on version 1.1.0 of the library, after a thorough review (full replication):

• In Ultimate Tic-Tac-Toe, with little computing time, Minimax beats MCTS: 62% of the games against 25%. With more time, the gap closes until they’re even.
• SO-ISMCTS wins between 78% and 92% of Escoba games against a random agent.
• In Stratego, with the genetic algorithm’s layouts, SO-ISMCTS wins 55% of its games against itself with random layouts, which wins only 5%.
• MO-ISMCTS beats SO-ISMCTS in games with hidden moves. In Holjjak it wins between 83% and 87% of the games.

Play against pyplAI

So that anyone can try it without installing anything, I built pyplAI Web: Ultimate tic-tac-toe against pyplAI’s MCTS, running in the browser itself with Pyodide. It has four levels, from 25 to 6,400 simulations per move, calibrated with a tournament of 1,080 games between searches of different strength. It can also show which moves the computer considered and how often each one won.

What I learned

• Designing an API means designing for others. The challenge wasn’t only implementing the algorithms, but letting someone plug them into their game without reading the source. That’s why the library ships with a full manual and the eight example games.
• Tests find what experiments miss. While preparing version 1.1.0 I wrote a test for every algorithm and game, and they caught bugs the thesis hadn’t, such as a blackjack game where the algorithm could see the dealer’s face-down card. The main conclusions hold, and the figures on this page come from the fixed version.
• Search is still highly competitive. I confirmed it later in Connect-X AlphaZero: the pyplAI-based agents beat PPO and Rainbow DQN, and only AlphaZero, which pairs search with a neural network, beat them.