From Minimax to MCTS

Over the past few days, I’ve made some big strides in improving the AI for my game. What started as a basic minimax + heuristic approach quickly ran into limitations. The game is timing-sensitive and rewards long-term planning — not something minimax handles easily with shallow depth and static evaluations.

So, I switched gears and started working on a Monte Carlo Tree Search (MCTS) implementation — and I’m really happy with the progress.

The Problem

I’ve been working on the AI for my game, which takes place on a toroidal grid with dynamic systems like population growth, energy networks, and resource management. It’s a complex environment with a lot of long-term planning involved — and that makes writing a good AI surprisingly tricky.

Up until now, I’ve been using a classic minimax algorithm with a handcrafted evaluation function. Here’s the setup:

• A minimax tree search (depth-limited)
• A fixed evaluate() function that tries to guess how “good” a state is, based on:
  • Population size
  • Energy yield
  • Proximity to resources
  • Habitat count
  • Loops in pipe networks (bad!)
  • And more…

While this approach works okay in simple cases, it really struggles in the kinds of situations my game cares most about — especially when timing and sequence of actions matter more than just static advantage.