✕ Close
Close

Contact

Feel free to reach out about research, projects, or anything you found intriguing.

Click to copy Copied.

Open in mail

LinkedIn ↗ · CV

Skip to content
Numbered Blokus Duo pieces arranged on a board

BlokusDuo ML Agents

MCTS guided by a convolutional network won 66% of games as player 1 and 48% as player 2 against standard MCTS, and it was the only agent that consistently beat experienced human players.

Read the paper /projects/blokusduo-agents/deep View the code github.com ↗

ML engineer and research author

2024

Python, PyTorch, PPO, MCTS, CNN

01The problem

Blokus Duo has a 14×14 board, 21 polyomino pieces per player, and a move space that explodes early. Placement decisions are permanent, rewards are sparse, and naive policy gradients learn to place pieces without really learning territory control.

Four agents compared on a 14×14 board: minimax, MCTS, MCTS with a CNN, and PPO

02What I did

I led the team that built and compared four agents for Blokus Duo: minimax, Monte Carlo Tree Search, MCTS guided by convolutional networks, and PPO. For the CNN-guided MCTS, a policy network trained on data from hundreds of thousands of simulated games, run across 46 lab machines, weighted the search toward promising moves. Every agent played random agents, the other agents, and human players.

Every agent played random agents, the other agents, and human players

03How it works

The CNN-guided MCTS uses two Keras networks. A value network estimates the chance of winning from a board state, averaged with a hand-built heuristic score. A policy network outputs probabilities over all 32,928 possible actions; illegal moves are masked out and the rest re-normalized so every legal move keeps some chance of being explored. PPO uses a clipped objective with a reward of +1 for a win and −1 for a loss, trained for about 100,000 timesteps.

Simulations ran across 46 lab machines, and board flipping doubled the data

P1 P2
  1. Random
  2. -
    90.63
  3. Minimax
  4. -
    98.82
  5. MCTS
  6. 8.65
    66.09
  7. MCTS w/ CNN
PPO
Random
98.38
-
Minimax
†
-
MCTS
61.29
100.00
MCTS w/ CNN
-
51.55
Player 1 win rates between neighbouring agents, in both seat orders, from Table 5 of the paper.

04What happened

MCTS with a CNN produced the highest win rates of the four methods: 66% as player 1 and 48% as player 2 against standard MCTS, over about 2,500,000 simulations across the non-PPO matchups. It was the only agent that consistently beat experienced human players.

Only the CNN-guided MCTS consistently beat experienced human players

Build real things. Make them worth using.

About Contact GitHub ↗ Scholar ↗ CV