Minesweepr

What is this?

It's a minesweeper solver! It can solve any board, with any topology, and exactly compute every cell's chance of being a mine. It achieves this through advanced combinatorial and probability analysis.

How does it work?

A minesweeper board is essentially a set of logical constraints. Each cell is a boolean state: mine or clear. Each uncovered cell says how many of the adjacent cells are mines. Our goal is to find configurations of mines that satisfy the given constraints. If, among all possible configurations, a cell is always a mine or always clear, we know for certain the cell is a mine or safe. A cell that appears in both states cannot be determined with any certainty; however, we can compute its relative safety by counting how many configurations in which it appears empty, as a proportion of all possible configurations, assuming all configurations are equally likely. Thus, if there is no guaranteed-safe cell, we can still determine the least-likely cells to have mines, and play the game quite skillfully.

Any algorithm that hopes to exhaustively solve minesweeper must employ this basic concept: determine all possible placements of mines on the board (and the relative likelihoods thereof), and observe how often each cell has a mine in it. This is easier said than done; enumerating all possible mine configurations is a huge computational task ("exponential-time algorithm", i.e., for each fixed amount increase in the problem size, the work needed to solve it doubles, i.e., the universe will probably freeze over before you finish). This solver employs a number of techniques to cut down on the amount of work needed.

The unfortunate truth, however, is that despite all these fancy tricks, minesweepr still requires exponential time to run — each new technique only serves to shave some amount off that exponent. It is strongly suspected that exponential time is the best we can do. Luckily, in practice, the exponent and board size are together small enough that boards can be solved quickly.

⁂

The real truth is even worse than that. This algorithm only computes the safest cell(s) for the very next move. To have the best chance of surviving the game, we must consider not only the next move, but the repurcussions on all potential future moves. Is there a difference? Yes!

That is to say, "is there a riskier move we can make now, that will pay off in multiple safer moves later on?" (Or even choosing among equivalently-risky cells.)

Imagine this typical situation: we must guess, so we make the logical 'best' move by clicking on the lowest-risk cell. We're still alive, but it doesn't seem like it revealed much information about the surrounding cells. So we guess again, and again… until finally we get some new information that removes the remaining uncertainty and lets us escape from the trap.

Now suppose there were a riskier1 cell that, had we lived to tell the tale, would have removed that uncertainty right away. Did we expose ourselves to more accumulated risk through several low-risk guesses rather than making the bold move upfront? There are known examples where this is indeed the case. And anecdotally, gameplay often seems to play out this way, where the safer bets reveal less useful information than do the riskier2. It's hard to prove definitely, though.

So the safest move at the moment is not always the best move for long-term success. Creating a perfect player that accounts for this — the outcome not just of this move, but the repurcussions of all possible subsequent moves — is intractable. Solving minesweeper is generally hard. Looking several moves ahead may both pay off and be feasible in certain situations (such as the endgame), but this algorithm doesn't concern itself with that. And the open-ended case, for "perfect" play, simply cannot be done.

Despite these shortcomings, it's still impressive to watch the algorithm at work, even just one move ahead. It's almost uncannily adept at getting out of tight situations.

Normal minesweeper is played on a basic grid. But this solver can handle many unconventional layouts, such as minesweeper on a non-flat and/or closed surface, in 3D, or with non-square cells. And it can do so without any change whatsoever to the basic algorithm.

Because the solver deals only in logical predicates of how many mines are to be found among given sets of cells, it actually has no concept of which cells are "next" to each other, or of the topology of the board at all. The game driver is responsible for defining and tracking the adjacency of cells, and minesweeper knows of the board state only as an abstraction. As to whether the board contains wrapping edges, miscellaneous warps or holes, odd shapes or extra dimensions, the solving algorithm is completely indifferent.

'Failure' in this context means "taking forever to solve" (aka universe-freezing-over). As the core operation of the solver is enumerating exponentially-growing sets of mine configurations, anything that increases the required effort of permutation is the enemy.

The biggest weapon against this is the chance to declare a cell as mine or clear early on, using deductive logic. Fixing many cells into a given state eliminates huge swaths of configurations from needing to be counted. There is also an ancillary benefit of breaking up chains of inter-dependent cells into smaller, independent groups.

The second weapon was just alluded to above: by recognizing that groups of cells are independent of each other (i.e., a configuration of one group has no bearing on the possible configurations of the other) we can 'divide and conquer' the board and avoid huge amounts of redundant computation. We permute each group independently and combine the distilled results at the end; what would have taken a×b×c amount of work takes a+b+c instead.

So what completely thwarts these tactics? Dense inter-connectedness among cells. The more neighbors a cell has, the harder it becomes to pin down mines to a particular place using deductive logic, and the less likely it becomes for cells to break into independent groups (because they are so connected).

In 3D minesweeper, each cell borders 26 other cells. In (god forbid) 4D, it would be 80 cells. This super-connected board topology undermines many of the assumptions in the algorithm's design, and tends to degenerate into the naive enumerating that we derided in the introduction. Perhaps a different approach is warranted here, such as taking a random sampling of possible configurations3, at the expense of only being able to calculate mine likelihoods to within a certain margin of error.

A related (though not nearly as severe) scenario is unbroken mine fronts that grow very long in length. The amount of permutation required increases exponentially with the length of the front, but much, much more slowly than when cells are all a rat's nest of connections.

How good is it?

Pretty good.

Using standard rules (mines distributed randomly; first click is always safe), minesweepr achieved the following record after 100,000 rounds of play (margin of error ≈0.15%).

This is from always playing the safest cell available, and, when multiple such cells, picking one of them at random.

Folk wisdom says it's better to play on the edges of the board rather than the center, in the hope of opening up a "cascade" — a large expanse of empty cells whose perimeter of clue cells gives you something to work with. The logic checks out as the fewer neighbors a cell has, the more likely it is not to be adjacent to a mine, thus triggering a cascade.

But I'm loathe to include such 'tricks' in the solver. Because:

1. folk wisdom is more often wrong than right. It focuses on highly visible, easily-reasoned-about phenomena, at the expense of situations and effects that are far more 'diffuse'. Optimal play results from taking into consideration all possibilities, whose cumulative effects are sometimes quite subtle. For example, who is to say the rarer cascades you'd get in the center wouldn't be larger and more useful in the long run than more frequent yet smaller cascades on the edges?
2. heuristics are fragile. Unless you can reason mathematically about why something works, you have no idea how narrow the scope of its improvement is. Every deviation from standard could switch the heuristic from a net winner to a net loser, and you'd have no idea if and how badly: "does this have adverse interactions with other heuristics?", "does it still work if I change the board size/mine density/topology...?", etc…

…and it turns out, there is quite an effect. I tweaked the auto-player so that when it must choose among equally-risky cells, it will prefer the perimeter of the board.

We see that favoring the perimeter gives a solid bump. Restricting to just corners improves performance further still. If we follow the logical next step of preferring corners first, then the remaining edge cells, we eke out yet another slight advantage.

This is the current apex for minesweepr. I believe these are some of the best, if not the best board completion stats of any published solver.

I'm a bit disturbed that such a simple tweak yields such a pronounced increase in performance. It makes me wonder just how much room for improvement there still is, especially low-hanging fruit. Even now the solver still always plays the least risky cells; this modified behavior only favors the edges when the choice is otherwise a wash. But as discussed prior, there are certainly instances where the better move is not the guaranteed safest— a gamble which will pay dividends later in the game.

But precisely how and when to exploit this are questions for another time.

At least until someone shows me a better solver.