Minesweeper AI Agent
An agent that plays Minesweeper by constraint propagation, and computes exact mine probabilities when deduction runs out.
The agent sees one number at a time and can't take a move back.
The world hands the agent a single starting tile and, after that, only the number on whatever tile it just uncovered. No board, no mine list, no undo. Uncover a mine and the game is over. The agent has to reconstruct what it can know about the board from a stream of local counts.
That makes it easy to write something that plays adequately and hard to write something that plays well. The obvious rules — “this 1 already touches a flag, so its other neighbors are safe” — clear the opening and then stall, leaving a board where nothing is provably safe and the agent has to guess. Win rate is decided almost entirely by how those two situations are handled: how much can be deduced before guessing, and which tile gets guessed when deduction genuinely runs out.
What the agent has to get right.
Every move the agent calls safe must actually be safe. A deduction that is right most of the time is worse than no deduction at all, because it loses games that were already won.
If a safe tile is provable from the current board, the agent should find it rather than guess around it, including the deductions that need several constraints considered together, not one number at a time.
Exact reasoning over a whole Expert board is exponential. The search has to stay inside a fixed budget and degrade to something weaker rather than hanging on a hard position.
The agent plays through the course's provided world harness. My work is the MyAI class; the board generator, scoring, and the C++/Java skeletons ship with the assignment. Python is the implementation I took all the way through.
Deduce everything provable first, then guess with real numbers.
Each uncovered number becomes a constraint: this set of still-covered neighbors contains exactly this many mines. Every deduction the agent makes, from the trivial cases to the expensive ones, is a statement about those constraint sets, so they're the only board representation the reasoning touches.
Cheap rules run first and repeat until nothing new appears, because each new safe tile or flag rewrites the constraints and can unlock another round. Only when that fixpoint is reached does the agent pay for enumeration, and only when enumeration also proves nothing does it guess. By then it already has the probability of every candidate being a mine, so the guess is the least bad one available rather than an arbitrary one.
Three tiers, cheapest first.
Local rules to a fixpoint
Counting rules per number, plus a subset rule that compares overlapping constraints. The loop reruns until a full pass discovers nothing new.
Backtracking over components
The frontier splits into independent components; each is enumerated exhaustively to count how many valid mine layouts make each tile a mine.
Lowest exact probability
Component counts are combined against the global mine budget into a true probability per tile, and the safest one is uncovered.
From a revealed number to the next move.
Every call to getAction runs this pass over the current board state. Each step only runs if the ones above it produced nothing.
Rebuild the constraints
Each uncovered number becomes (covered neighbors, mines still unaccounted for) — the raw count minus the flags already placed around it. Constraints are rebuilt from scratch each pass rather than patched, so a stale deduction can never survive into a later board state.
Apply the counting rules
If a number already touches as many flags as its value, every remaining covered neighbor is safe. If its covered neighbors plus its flags exactly equal its value, all of them are mines. Two global versions of the same idea close out endgames: once every mine is flagged the rest of the board is safe, and once the covered count equals the mines left, all of it is mines.
Compare overlapping constraints
When one constraint's tile set is a strict subset of another's, the difference is its own constraint: the extra tiles hold exactly the difference in mine counts. Zero means they're all safe; a difference equal to the set size means they're all mines. This is what breaks the positions single-number rules can't touch, and each new fact restarts the loop.
Split the frontier and enumerate it
When propagation stalls, covered tiles that share constraints are grouped into connected components by a depth-first walk, so a board with three separate unresolved pockets is solved as three small problems instead of one large one. Each component is enumerated by backtracking, assigning mine or clear to one tile at a time and pruning the moment a constraint is over- or under-filled. The search counts, per tile, how many complete valid layouts make it a mine. Zero means provably safe; all of them means provably a mine. Components over 40 tiles and searches past a 500k-node budget are abandoned rather than allowed to hang.
Weigh layouts by the global mine budget
A component's layouts aren't equally likely: one using 3 mines leaves more for the rest of the board than one using 5. Each layout is weighted by how many ways the leftover mines fit among the interior tiles that no number touches, the components are convolved together, and the result is an exact marginal probability per frontier tile, plus one shared probability covering the interior. The agent uncovers the minimum, breaking ties toward tiles with more neighbors because those reveal the most.
What I chose, and what it cost.
Exact enumeration inside a hard budget
CostComponents past 40 tiles or 500k search nodes are dropped, and the agent falls back to per-component probabilities that ignore the global mine count. Rare on Expert boards, but it's a real ceiling, and a smarter solver would push it up rather than bail.
Rebuild every constraint each turn
CostThe pass redoes work that hasn't changed since the last move. It's cheap next to enumeration and it makes soundness easy to reason about, which mattered more than the cycles.
Local marginals aren't real probabilities. Counting layouts within one component tells you how often a tile is a mine among that component's own solutions, but it silently assumes every layout is equally likely, and they aren't, because a layout that uses more mines on the frontier leaves fewer for everything else. Early on the agent guessed off those local numbers and lost boards it should have won, always in the same way: it preferred a frontier tile that looked marginally safer over an interior tile that actually was. Weighting each layout by the number of ways the remaining mines fit among the untouched interior tiles, then convolving the components so they're scored against one shared mine budget rather than independently, turned the estimates into true probabilities, and made the interior a candidate the agent could pick when it deserved to be picked.
Where I'd take it.
Raise the enumeration ceiling with memoization across the backtracking search, so large components degrade gradually instead of falling off the budget cliff at 40 tiles.
Guess for information, not just safety. Between two tiles of equal mine probability, prefer the one whose reveal most constrains the frontier rather than the one with the most neighbors.
Port the finished agent to the C++ skeleton and benchmark win rate across the full Beginner/Intermediate/Expert world set, which the Python version is too slow to sweep repeatedly.