Sprouts is a pen-and-paper game that John Conway and Michael Paterson invented at Cambridge in 1967. You start with \(n\) dots, called spots. A move draws a curve from one spot to another, or from a spot back to itself, without crossing any existing line, and then puts a new spot somewhere on that curve. No spot may have more than three lines touching it. Whoever makes the last legal move wins. I wanted to play it against a computer.
How long a game lasts
Call the unused line slots on a spot its lives. There are \(3n\) at the start. Every move spends two lives, one at each end of the curve (or two on the same spot for a loop), and creates a spot that already has two lines, so one life. Each move costs exactly one life net, and every move adds exactly two edges to the graph, because the new spot splits the curve. The last move still leaves that new spot's life unspent, so at least one life remains when the game ends and a game lasts at most \(3n - 1\) moves.
The lower bound takes one more idea. When the game ends, every surviving spot has exactly one life, because a spot with two could still draw a loop to itself. Each survivor's two neighbors are dead, and no dead spot neighbors two survivors, since two lines into the same dead spot share a face and the survivors at their far ends could be joined. So there are at least twice as many dead spots as survivors. After \(m\) moves there are \(n + m\) spots and \(S = 3n - m\) survivors, and \(n + m \geq 3S\) gives \(m \geq 2n\). Winning Ways (Berlekamp, Conway, and Guy) calls a dead spot that neighbors no survivor a Pharisee, and counting them makes it exact: \(m = 2n + P/4\). So a game runs between \(2n\) and \(3n - 1\) moves. With 6 spots that's 12 to 17.
Who wins is a different question. Applegate, Jacobson, and Sleator computed it by exhaustive search up to 11 spots in 1991 and conjectured that the first player wins exactly when \(n \bmod 6\) is 3, 4, or 5. Later searches carried that pattern to \(n \leq 44\). Nobody has proved it holds in general. Sprouts is an impartial game, so every position has a nim-value in principle, but I didn't compute any. My AI is heuristic.
Moves aren't discrete
In most board games a move is a thing you can enumerate. Sprouts moves are curves in the plane, and legality depends on whether the curve crosses anything. My first attempt sampled each candidate curve at many points and tested each sample against existing lines. It was slow and wrong in both directions. Curves that passed near a line registered as collisions depending on sampling density, and real crossings slipped between samples.
The fix came from image processing. Treat the board as a binary image where lines and spots are obstacles and everything else is free. Thin the free space with the Zhang-Suen algorithm, which strips boundary pixels while preserving connectivity, and what's left is a one-pixel-wide medial axis running down the middle of every open corridor. That skeleton is a graph, and any path along it is a curve that clears existing geometry by construction.
Plain thinning wasn't enough. In the endgame the free space is a few thin winding channels next to one or two big open regions, and a skeleton computed the same way everywhere either loses the channels or sits too close to walls in the open. So before thinning I dilate the obstacles by 35 percent of the local corridor width, measured with a distance transform, clamped between 3 and 50 pixels at the base scale. Wide areas get heavy dilation and the skeleton is forced to their center. Narrow passages get almost none and survive. When even that fails, and in tight endgames it does, an A* search runs over the raw free pixels with relaxed clearance.
The AI
To generate moves, the AI pathfinds along the skeleton between every pair of spots that both have a life left, plus a loop for every spot with two or more, falling back to the free-space A* when the skeleton path fails. Each path is a concrete candidate move. It then abstracts the position into a graph, runs minimax with alpha-beta pruning on the abstract graph, and returns the concrete curve of the best move for drawing. The search is iteratively deepened from depth 1 up to a cap the position chooses, at most 16.
When the abstract graph updates after a move it takes the union of the two endpoints' neighborhoods, and it never removes a pair of spots that a new line has just separated into different regions. So the search considers some moves that aren't legal on the real board, and going deeper doesn't fix that. The move it finally plays is always one of the concrete root candidates, so the cost is wasted search and a skewed evaluation rather than an illegal line on the board. It plays a decent game anyway.
The AI always plays second, and an opening book covers its first reply to the common human openings at 4, 5, and 6 spots. When it draws a curve it also has to choose where the new spot goes. It samples the middle 80 percent of the path, skipping the ends where spots cluster, and takes the point with the greatest clearance from any obstacle, to leave as much room as possible for later moves.
The game logic and AI are Rust compiled to WebAssembly, running in a Web Worker because a search on a crowded 6-spot board takes a few seconds and shouldn't freeze the canvas.