MCTS

An agent plays a pursuit-evasion game on a 20×15 grid: a bot races toward an exit while a pursuer hunts it down. The pursuer always takes the shortest path to the bot with A*; the bot chooses every move by running Monte Carlo Tree Search over thousands of simulated futures. It runs as an interactive terminal demo in Kotlin — you can step through one decision at a time, let it auto-run, and dial the search budget up or down to watch the agent get sharper or sloppier in real time.

The escape problem

Every action the bot takes spends time, and the pursuer moves once per unit of time spent. A step costs one tick and the pursuer gets one step back. Placing a block costs two ticks — so walling the pursuer off literally hands it two free moves toward you. The bot carries eight blocks and a hundred-tick clock, and only reaching the exit counts as a win; getting caught loses, and merely outlasting the clock is just survival.

Blocks do not even stop the pursuer. It will tunnel straight through a placed block, spending three ticks to break it — still cheaper, sometimes, than routing around. So the real decision is never "wall it out" but "is buying the pursuer a three-tick detour worth two ticks and one of my eight blocks, given it might just walk around anyway." That tension — spending a turn budget to manipulate an opponent who can spend its own to undo the work — is the whole game.

The rollout policy

MCTS works by sampling. From the current position it plays out many games to the end, then favors the first move whose playouts went best. The catch is that purely random playouts are noise: in a game this sparse, a bot flailing at random almost never reaches the exit, so nearly every simulation ends the same way and tells the search nothing.

So the playouts here are not random. Each simulated move is drawn from a weighted policy that already knows the basics — step away from the pursuer, step toward the exit, drop a block when the pursuer is close. The search still explores, because the policy is a bias rather than a script, but its samples land in plausible play instead of noise. That is what makes a thousand iterations per move enough to act on.

The reward is shaped the same way. A playout that reaches the exit scores one and a capture scores zero, but most playouts hit neither within their depth limit. Rather than a coin flip, those score a continuous value read off the position: closer to the exit is better, more breathing room from the pursuer is better. That gradient is what lets short, inconclusive simulations still rank one move above another.

When the budget runs out, the bot does not play the move with the best average — it plays the most-visited one, the move the search kept returning to. Visit count is the steadier signal; a glowing average built on two lucky playouts is not.

Two models of the pursuer

The pursuer the bot plans against is not the pursuer it actually faces. In the real game the pursuer navigates with full A* pathfinding — costing in the option to mine through walls, recomputed from scratch every tick. Inside the search, where the pursuer has to be simulated tens of thousands of times per move, A* is far too expensive, so the rollouts model it with a cheap greedy heuristic: step toward the bot by Manhattan distance, and mine only when a wall sits right in the path.

So the bot plans against a simplified opponent and then acts against the real one. It is the usual MCTS speed-versus-fidelity bargain made explicit — a faithful opponent model would make each simulation worth more but let the search run far fewer of them; the greedy stand-in is wrong in the details but cheap enough to sample deeply. It also means the bot can be genuinely surprised, when the real A* pursuer takes a route its greedy model never bothered to consider.

Running it

Three modes share the same engine. The interactive demo renders the grid live in the terminal with Mordant: Space advances one move, R toggles continuous auto-run, + and - scale the per-move search budget — which is how you watch decision quality track compute — and Q quits. A non-interactive mode plays a full game straight through to its outcome, and a benchmark mode warms up the JIT and then times the search from 100 up to 10,000 iterations to report cost per iteration.

Tradeoffs

The map is fixed: one hand-designed grid with one set of start positions, so the demo shows the algorithm working rather than its generality. The rollout policy and the reward weights are hand-tuned for that map, not learned. The search is single-threaded and starts each move from a fresh tree, discarding everything it learned on the previous one. And because the bot plans against the greedy pursuer model rather than the A* one it actually faces, a well-played escape can still fall apart when the real pursuer finds a line the search never simulated.