Combinatorial solver

I had intended to make this solution thread less work by relying on other people's solutions, but I couldn't leave well enough alone and figured I'd at least implement this one technique since I think it's interesting to see.

When facing a tricky problem, it's often useful to boil it down to its algorithmic core. Consider the following grid in Minesweeper:

112#
####
####

This grid has nine hidden mines, but the visible squares only give you any information on the top five of them. Call these top five squares the "boundary" squares, and call the bottom four the "interior" squares. Let's label each of the five boundary squares from top to bottom, then left to right with the variables x1, x2, x3, x4 and x5, where each variable is allowed to be 1 or 0, respectively indicating that the square has a mine or it doesn't. This lets us write out a system of equations describing what we know from the currently visible squares:

1 = x2 + x3
1 = x2 + x3 + x4
2 = x1 + x3 + x4 + x5

This system of equations describes the core algorithmic problem you need to solve in order to know what the probability is of each square having a mine. Unfortunately you can't solve it like you did in algebra class due to the restriction that each variable is only allowed to be 0 or 1.

One possible way to solve the above system of equations is to simply try each of the 2⁵ possible ways way of setting each of the variables to 0 or 1 and, of those which actually satisfy the equations, count how many times a mine ends up in each square. You could then just guess the lowest probability mine. This method works, but it can be pretty inefficient. It's possible to do some tricks to mitigate this, but I'd instead like to look at an alternate way of solving the problem that I think is a little more interesting.

As was noted by /u/lfairy in this comment, this sort of problem resembles a extremely well-studied type of problem known as a boolean satisfiability problem. There are a few minor differences but this hints that techniques for solving boolean satisfiability problems might be adapted for the game of Minesweeper.

There is a catch though. Most algorithms for solving boolean satisfiability problems only try to find if the equations are possible to solve, and if so generate a single solution. We already know they're possible to solve, and instead of just one solution we want to know the probability that each square has a mine under it. The answer will be so create a bunch of random solutions to the equations, and average the probabilities over these random solutions.

It turns out that there's an algorithm (ok, probably many algorithms) which is well-suited to this approach. It's called WalkSAT and it's pretty neat in that it's both quite effective and very simple to implement. The algorithm can also be easily adapted to work for our type of problem. Here's more of less how it goes:

1. Start with randomly setting each variable to 0 or 1
2. If the equations all add up correctly, you're done.
3. Pick a random equation which doesn't add up correctly
4. If the equations needs more mines to hold, we'll turn a variable appearing in it from 0 to 1. If it needs fewer mines to hold, we'll turn a variable appearing in it from 1 to 0.
5. The particular variable to flip is either chosen completely randomly (with probability p) or chosen to be the variable which messes up the fewest other equations when you flip it (with probability 1-p).
6. Go to step 2

This method starts with a completely random guess as to where the mines are, then fiddles with it until it has a solution which matches all the numbers for the visible squares. If you repeat this for a bunch of different initial random guesses, you can estimate the probability that each border square has a mine.

The solution used to generate the scores in the above table also includes a few other enhancements. Firstly it estimates the probability that a random interior square has a mine, in case it's better to guess an interior square than a border square. It also handles both minimum and maximum limits to the total number of mines that can be used -- both of which are actually useful in playing the game.

As you can see from the scores in the table above, this sort of approach actually does relatively well. It's a nice example of the benefit of sitting down and really working out the core essence of a problem. The drawback, of course, is that it's relative slow. My highly unoptimized C++ implementation can only play about 25 games a second on expert difficulty.

Doing even better

Perhaps you have an idea for writing an even better AI? For example, one thing the combinatorial search doesn't take into account is the value of clicking on a square. If you have to make a guess, it's best to take into account not only the probability that the square has a mine, but also how much new information you're likely to get from clicking on that square if it doesn't have a mine. /u/Kodiologist and /u/SafariMonkey proposed some ideas like this. It also seems possible to semi-efficiently do a pretty good approximation to this within the randomized combinatorial search algorithm I proposed, but maybe you have an even better idea?

Or perhaps there's something else I'm still missing? What do you all think?