hex-game

the story

The original agent was a university team project in Java: a multithreaded Monte Carlo Tree Search engine that combined UCT with a Dijkstra based shortest connection evaluation, so simulations were guided toward moves that actually shortened the path between sides. Most of the engineering went into the simulation engine. Fast move validation, a tight game loop, and heuristic tracking let it run large scale rollouts within a move budget.

The opponent here follows the same design: UCT search, random fill rollouts with union-find win detection, and the Dijkstra heuristic as a prior, reimplemented in Python and served by FastAPI. Pick "ruthless" and it searches for three seconds per move.

what Monte Carlo tree search is

A 7x7 Hex board has more legal positions than there are atoms worth counting, so an agent cannot look at all of them. Chess engines get around this with a scoring function, a formula that says how good a position is. Hex has no good one: whether a shape is strong depends on connections that are hard to reduce to a number.

Monte Carlo tree search answers that by refusing to judge a position at all. Instead it plays the rest of the game out at random, thousands of times, and counts who won. A move that keeps winning random games is probably a good move. Hex can never draw, so a board filled at random always has a winner, and the count is never wasted.

Each of those thousands of iterations is four steps:

1. Selection. Walk down the tree built so far, at each level picking the child with the best UCT score: its win rate plus a term that grows the longer a move has gone unexplored. That sum is the whole balancing act, between trusting what already looks good and giving neglected moves a fair hearing.
2. Expansion. On reaching a position with untried moves, add one of them to the tree as a new node.
3. Playout. From there, fill every remaining cell at random and see who ends up connected.
4. Backpropagation. Walk back up the path, adding one visit to every node and a win to those that belong to the winner.

The move the agent finally plays is the most visited child, not the one with the best win rate. A move tried five times that won all five is noise; a move tried nine thousand times has an estimate you can lean on. That is also why the panel beside the board sizes each branch by visits: it is showing where the search decided to spend itself.

what Dijkstra is doing here

Dijkstra's algorithm finds the cheapest route through a weighted graph. Starting from a source, it repeatedly settles the nearest node it has not settled yet, and because it always takes the nearest one, a node's distance is final the moment it is settled.

The board is the graph. Moving through a cell you already own costs nothing, an empty cell costs one, and a cell the opponent holds cannot be crossed at all. Run that from one of your edges and the distance to the far edge answers a concrete question: how many more stones do I need to connect? That is the number under the board, and it drops to zero exactly when you win.

Because the only weights are zero and one, it does not need a priority queue. A deque is enough: neighbours reached for free go on the front, neighbours costing a stone go on the back. Same answer as Dijkstra, in time linear in the size of the board, which matters when the search wants it thousands of times a second.

Its job in the agent is to fix the weakness of random playouts, which on their own have no idea what a connection is. The connection distance scores each candidate move by how much it shortens the path, and the search uses that to decide which moves to try first. The random games still decide the outcome; Dijkstra decides where the budget is worth spending.