Why go to the trouble of creating an Artificial Intelligence capable of playing Minesweeper? Here are the main reasons:

What is an Artificial Intelligence?

Broadly speaking, an Artificial Intelligence (AI) is a program designed to perform some task which previously was only performable by humans. Of course, all such programs currently fall far short of the ideal AI - one which can actually imitate human thought.

On the other hand, anything which can simulate even a tiny fragment of human reasoning is a step in the right direction.

What is Minesweeper?

Minesweeper, for those of you have not come across it, is a very simple game available in some form or another on most computers. The player is presented with a grid of squares, behind each of which lies either a mine or a safe space. The aim of the game is to uncover all the safe spaces, and, at the same time, 'flag' all of the mines.

This task is made possible by the fact that clicking on a safe square will immediately show how many mines surround that square. From this information, it is sometimes possible to work out where to step, without any guesswork being involved. On the other hand, sometimes it's all down to plain luck...

Minesweeper from an AI's Point of View

Inevitably, if unfortunately, we're going to have to introduce a little jargon. Our AI is going to keep track of what it knows about the board using an array; that is, a grid of values. Each square on the Minesweeper board has its own cell in this array

In addition, our AI is going to have to be able to 'think' about possible layouts of mines. Since it needs to think about lots of different situations, we'll extend our layout array upwards, making it 3D. The number of layers in this array will dictate how many different situations our AI can consider at once.

Let us call the array holding the information our AI possesses the information array, and the array holding hypothetical situations the hypothetical array. The array storing the positions of mines is, of course, not immediately accessible to our program... we'll call that the hidden array.

Outline of an AI

There are many entirely different approaches that could be taken to this particular problem; it might, for example, seem like a good idea to start building up a set of rules about different situations and the best guesses that can be made in each of them. However, the problem is then, how do you combine all of these pieces of information into a single process of deciding where to move? And, furthermore, how do you make sure your program isn't missing any rules?

Other approaches could perhaps involve a program which learns, by trial and error, which patterns to look out for. Again, this is likely to be a complicated process. This article will look at one of the simplest methods which an AI can employ: brute force.

A human playing Minesweeper tends to conjure up in their mind various patterns of mines which would satisfy all the information they've got; if a particular square doesn't contain a mine in any of these possible scenarios, it's safe to step on. Our AI will work in a similar way:

1. Fill the hypothetical array with layouts of mines which do not conflict with the information array.

2. Look for columns of cells in the hypothetical array which don't contain any mines, and 'step' on them (ie, look at the corresponding value in the hidden array to see if there was a mine there).

3. If the information array is incomplete, there are squares left to uncover, so go to first step.

This simple procedure will uncover all the squares which couldn't possibly contain mines. Of course, there might not exist any squares which couldn't possibly contain mines; added to which, our AI needs to place flags when it thinks it's found a mine.

During step one, our AI might fill in 30 or so layers in the hypothetical array. What it's got, in fact, is a whole set of different possibilities for where the mines could be... we haven't yet specified how our program is to come up with these layouts, but it seems reasonable to assume that each layout produced is equally likely to be the correct layout.

Therefore, for any particular cell of the hidden array, the chance of a mine being in that cell is indicated by the number of mines in the corresponding column of the hypothetical array.

Working with all of these probability values, our AI can look for squares which are certain¹ to contain a mine, and flag them as mines. If it doesn't find any such squares, it can proceed to look for the square which is least likely to contain a mine; stepping on this square is the best possible move.

So, our whole process looks like this:

1. Fill in the hypothetical array with layouts of mines which do not conflict with the information array.

2. Collapse the hypothetical array into a new probability array by dividing the number of mines in each column by the number of layers.

3. Look for a cell in the probability array containing a one; if found, flag it as a mine.

4. Look for the cell in the probability array holding the lowest value, and 'step' on it. 5. If the information array contains gaps, there remain squares to be uncovered, so go to step 1.

This algorithm will quite comfortably and consistently uncover a Minesweeper board; if the number of layouts considered is high enough, its strategy is nearly perfect. One interesting aspect of this AI is that it will always leave any guesses that have to be made until the very end. For example, on one attempt, it cleared the whole board except for two squares - whereupon it was forced to guess which contained a mine, with no helpful information. It guessed wrongly, and failed.

An Algorithm for Finding Possible Layouts

By far the most complicated part of implementing the above procedure is the production of layouts of mines which fit in with all of the available information, but are nevertheless randomly selected. Here's one way of doing so:

1. Fill in the hypothetical array with a completely random layout of mines.

2. Adjust each layer in the hypothetical array so that flagged mines are in the correct places.

3. Scan each layer of the hypothetical array, looking for conflicts with the information array.

4. If there are too many mines around a particular square, select one of them at random and move it to somewhere else.

5. If there are too few mines around a particular square, move a mine at random from somewhere else into the required position.

6. If conflicts were found, go to step three.

This will gradually turn a completely random layout into one which fits in with all the information. It should be repeated perhaps 30 times, to produce enough layouts to give a good indication of which squares are safe and which aren't.

Performance

A program using this method can consistently beat or equal a good human player. It has the advantage of always considering the board as a whole, instead of looking at whichever part of the board it happens to be concentrating on. Given enough hypothetical layouts to consider, its probability estimates are always fairly accurate - and it will never make obvious mistakes.

That said, it doesn't win incredibly often. It turns out that Minesweeper is not always solvable - even if you get past the first 'random clicking' stage. It frequently happens that a player of Minesweeper is forced to make a blind guess, with odds of 50 - 50 or worse and thus the probability of winning a reasonably-sized game of Minesweeper is in fact fairly low, perhaps one in five. One in five, that is, given a perfect strategy...