Just a Game?
A couple of weeks ago, I explored the notion of computational complexity and how amazing amounts of complexity can show up in seemingly simple contexts. In the particular case examined, the Subset Sum problem, the familiarity of the simple activities of ‘looking’ and ‘adding numbers’ masks a surprising conclusion that an algorithm that scales as a polynomial in time is most likely impossible to find. The Subset Sum is said to be an NP-Complete problem.
Computational complexity can be lurking in even tamer and more familiar guises. One of the more innocent-looking locations is in the simple computer game that comes with Windows – Minesweeper.
Before talking about the formal aspects of how Minesweeper is NP-Complete, let’s look at how the complexity arises from a practical example. For simplicity, I’ll be looking at three separate cases drawn from the beginner’s level of Minesweeper.
In all cases, one starts with zero information as to the placement of the mines and so the first move is always a blind-luck guess.
If it works out, one gets information about the number of mines in the eight nearest-neighbor spaces. If one is lucky, the information is enough to solve the puzzle outright. Case 1 is such a case. After one successful blind guess, the information available on the board was sufficient to get to the end stage where it is obvious how to solve the puzzle
The two remaining mines need to go directly next to the ‘3’ and the ‘4’ and so the remaining two spaces can be explored without fear.
Sometimes, no amount of logic can save you and there is nothing to do but guess as in Case 2. After the initial blind-guess the board looked like
Solving for the obvious spaces leads to the final configuration with two unexplored spaces and one remaining mine. No amount of deductive or inductive logic will save the day and a 50/50 guess is required (for those who care, I guessed wrong).
Both of these cases have the luxury of being straightforward. The amount of thinking was kept to a minimum and the options were well understood (although not always successfully so).
The true complexity of the game becomes apparent in the in-between Case 3. After the blind guess and resolution of the easy spaces, the board looked like this:
There is no way to easily finish off the board but nor is the final solution up to chance. It is a matter of exploring possibilities. Since ‘1’ spaces are easiest to deal with, let’s focus on the line of three ‘1’s found on the lower right. Let’s tentatively mark the rightmost ‘1’ as having a mine directly below it by placing a ‘?’ on the space. Making that assumption leads to a propagation of other possible mine spaces, each marked with a ‘?’, as shown below
The entire set of ‘?’s is consistent – that is to say, we don’t have a contradiction anywhere.
Next suppose that we assume a mine just below the middle ‘1’ on the row of three on the right. Putting a ‘?’ there leads to an inconsistency, since if there is a mine at the location of the ‘?’ there is no way to satisfy the ‘1’ and ‘2’that are next to each other. The red dot (which is photo-edited in since Minesweeper doesn’t provide a marker for inconsistency) drives this point home.
Similar logic holds for putting the ‘?’ under the leftmost ‘1’ and so the only consistent guess was the first one. Acting on that guess leads immediately to success.
The true complexity of Minesweeper becomes obvious upon reflection of what can happen when the field is bigger and the number of mines is increased. Each blind luck move at the beginning of the game can lead to numerous possible avenues to explore. Each ‘?’ placed on the board can spawn additional channels to explore; the difficulty can grow exponentially.
This argument is a plausible, heuristic one so there may be a tendency for the reader to respond ‘But you really haven’t proven it!’. That is a point I am willing to concede – I haven’t proven it – but someone has.
In the spring of 2000, mathematician Richard Kaye of Birmingham University was able to prove that Minesweeper is NP-Complete. This means that Minesweeper is a decision problem (did you solve it or did you detonate), it is very hard to find a solution, and it is very easy to check the solution. He also went on to construct various logic gates in Minesweeper and using these, proved, in 2007, that Minesweeper played on an infinite board with infinite mines (although fewer mines than spaces) is also Turing complete.
So the next time someone chides you for wasting time playing Minesweeper, respectfully point out that you are not wasting time, you are researching one of the most important open questions in computer science.