In the first article of the series we've implemented a basic Minesweeper solving algorithm for Minesweeper Battle game. We ended with a program which can efficiently iterate through cells on a field and make a decision which of their neighbours contains a mine or not. However it appeared, it's solving abilities are limited - it can analyse individual cells only. Every Minesweeper player knows that there are many cases when one must consider two or more cells at a time to make their next decision. Like in example below:
When looking at every opened cell one by one, it is impossible to determine where exactly is the mine(s) in the neighbour cells. But after calculating all possible combinations of mines placements at these three closed cells, it becomes clear that only one combination is possible (as flagged in the picture). Actually there are plenty of similar cases, and those who play Minesweeper often don't even bother to calculate them each time, they simply instantly recognise familiar patterns. So let's "teach" our Computer player how to handle these cases!
How exactly are we going to implement this? At first sight, the idea of calculating all possible combinations of mines placement and picking the most reasonable one seems as the way to go. However it faces several problems.
First of all, the number of all possible combinations can be (and on a large field often will be) too huge. For N cells it is 2^N. According to our indispensable Big O Cheat Sheet it is horrible :)
Secondly, it will certainly introduce some programmatic complexity. To begin we need to find all possible combinations. Then filter out the list of combinations based on applying each combination and checking whether it fits the field conditions or not. Then based on remaining combinations for each cell we need to calculate probability of whether it is empty or contains a mine. And then finally commit a decision (make a move). One can just imagine the amount of "for" loops we might need for this... Though for sure, it is possible to create such algorithm ourselves, but even after putting significant efforts there, most probably it will result in something we won't be happy to work with in future. Very often it is even challenging to understand what exactly such algorithm is doing after coming back to it after some time. Readability and simplicity are one of the most crucial qualities of the code imo, so we need to pay some attention to this aspect as well.
Let's take a look at following example:
There are 27 closed cells which border to one or more opened ones. Thus all of them can be taken into account while calculating of combinations of possible mines placement. According to formula, it will result in
2 ^ 27 = 134,217,728
combinations. Considering we need not only to calculate all possible variations, but apply each of them on the field and check whether they satisfy game conditions, then processing could take hours! Can we somehow reduce this number? Let's analyse this case further. You might notice, that some of these cells are located closely to each other, while some of them do not even have common neighbours. That means we can group them into sections:
If we calculate all possible combinations in each group separately, we certainly gain some performance boost.
2 ^ 13 = 8192
2 ^ 7 = 128
2 ^ 7 = 128
8192 + 128 + 128 = 8448
Much better, isn't it?
And here is the code for finding groups of "connected" cells:
private findGroups(): Cell[][] {
const groups: Cell[][] = [];
const registeredCellsSet: Set<Cell> = new Set();
for (let i = 0; i < this.game.fieldWidth; i++) {
for (let j = 0; j < this.game.fieldHeight; j++) {
const cell = this.game.cells[i][j];
const group: Cell[] = [];
this.findGroupStartingFrom(cell, group, registeredCellsSet, undefined);
if (group.length > 0) {
groups.push(group);
}
}
}
return groups;
}
private findGroupStartingFrom(
cell: Cell,
group: Cell[],
registeredCellsSet: Set<Cell>,
previousCell?: Cell
): void {
if (
!cell.isOpenedBy(this.player)
|| cell.neighbourMinesCount === 0
|| registeredCellsSet.has(cell)
) {
return;
}
let flaggedOrExplodedNeighbourCellsCount = this.player.getFlaggedOrExplodedNeighbourCellsCount(cell);
if (flaggedOrExplodedNeighbourCellsCount === cell.neighbourMinesCount) {
return;
}
if (previousCell && !this.hasCommonClosedNeighbours(cell, previousCell)) {
return;
}
group.push(cell);
registeredCellsSet.add(cell);
for (let neighbourCell of this.game.iterateNeighbours(cell)) {
this.findGroupStartingFrom(neighbourCell, group, registeredCellsSet, cell);
}
}
private hasCommonClosedNeighbours(cell1: Cell, cell2: Cell): boolean {
const neighboursSet1: Set<Cell> = new Set();
for (let neighbourCell of this.game.iterateNeighbours(cell1)) {
neighboursSet1.add(neighbourCell);
}
const neighboursSet2: Set<Cell> = new Set();
for (let neighbourCell of this.game.iterateNeighbours(cell2)) {
neighboursSet2.add(neighbourCell);
}
const intersection = [...neighboursSet1]
.filter(cell => neighboursSet2.has(cell) && !cell.isOpened() && !this.internalFlags[cell.x][cell.y]);
return intersection.length > 0;
}
What else can we do? Let's see what possible combinations we would get for any group of, for example, 5 cells:
0 0 0 0 0
0 0 0 0 1
0 0 0 1 0
0 0 1 0 0
...
1 1 1 1 1
But if we consider the following case, we can easily spot, that combinations like "0 0 0 0 0", "1 1 1 1 1" and many others don't make a lot of sense and can be excluded from consideration.
I've spent few evenings trying to determine is it possible to identify min and max number of mines for connected group of cells, each having at least one opened neighbour. Unfortunately, I couldn't find any easy way to do that. For cases up to five cells it was relatively easy, but for more became challenging, especially considering variety of numbers in the neighbour cells. Despite it seemed to be still possible to roughly limit the number of combinations, I was constantly feeling I'm solving this problem in a wrong way and there should be much more easy path.
And suddenly I recalled a University course about Prolog logic programming language.
From Wikipedia: Logic programming is a programming paradigm which is largely based on formal logic. Any program written in a logic programming language is a set of sentences in logical form, expressing facts and rules about some problem domain.
In a simple words, logic programming is intended for solving such problems like Einstein's riddle. You might take a moment and watch a video about it:
Logic programming allows solving the problems not in algorithmic, but rather in declarative way. It is necessary to precisely describe the problem, and the logic programming engine suppose to efficiently handle it and return a result.
Can we apply this paradigm to our needs? Let's take a look at the example from the beginning of this post
From logic programming perspective, it can be described as:
cell 1b states there is a mine either in cell 1a or 2a
cell 2b states there are mines in either 1a and 2a, 1a and 3a or 2a and 3a
cell 3b states there is a mine either in cell 2a or 3a
Translating these sentences into code and submitting to logic programming engine should be enough to get an answer where mines are placed.
And luckily, there is a Javascript logic programming library called LogicJS. And here how the code looks like.
*solve(): Generator<Action> {
// find groups of connected cells
const groups = this.findGroups();
// initialise logic functions
const and = logic.and;
const or = logic.or;
const eq = logic.eq;
const run = logic.run;
const lvar = logic.lvar;
// for every group of cells...
for (let i = 0; i < groups.length; i++) {
const group = groups[i];
// LVar -> logic variable
const closedLVars = new Map();
const ruleArgs = [];
for (let cell of group) {
// compose logic rules for each cell
const closedNeighbourLVars = [] as any;
let flaggedOrExplodedNeighbourCellsCount = 0;
for (let neighbourCell of this.game.iterateNeighbours(cell)) {
if (this.internalFlags[neighbourCell.x][neighbourCell.y] || neighbourCell.isExploded()) {
flaggedOrExplodedNeighbourCellsCount++;
continue;
}
if (!neighbourCell.isOpened()) {
const key = neighbourCell.x + '-' + neighbourCell.y;
let closedLVar;
if (closedLVars.has(key)) {
closedLVar = closedLVars.get(key);
} else {
closedLVar = lvar(neighbourCell);
closedLVars.set(key, closedLVar);
}
closedNeighbourLVars.push(closedLVar);
}
}
const combs = combinations(
closedNeighbourLVars,
cell.neighbourMinesCount - flaggedOrExplodedNeighbourCellsCount
);
const orArgs = [];
for (const comb of combs) {
const andArgs = [] as any;
comb.forEach((isFlagged, index) => {
andArgs.push(eq(closedNeighbourLVars[index], isFlagged));
});
orArgs.push(and.apply(null, andArgs));
}
ruleArgs.push(or.apply(null, orArgs));
}
const rule = and.apply(null, ruleArgs);
const closedLVarArray = Array.from(closedLVars.values());
const closedCellsArray = closedLVarArray.map((closedLVar) => closedLVar.name);
// runs the logic engine
const probabilities = run(rule, closedLVarArray);
const composedProbabilities = LogicSolver.composeProbabilities(closedCellsArray, probabilities);
for (const probability of composedProbabilities) {
if (probability.hasMine()) {
// Action is a Command pattern class
yield Action.flag(probability.cell);
} else if (probability.isEmpty()) {
yield Action.open(probability.cell);
}
}
}
}
It appeared it works perfectly with more than acceptable performance. Feel free to check this out by playing against computer :)
Some parts of code is excluded from listing to make it more readable, however the outcome is the following: we managed to achieve rather complex goal with just 80 lines of code, simply by determining the optimal way of solving and using proper tools.
There left one question though - what if any action can't be determined after running the algorithm above? In this case it is necessary to guess the right move (it often happens in real Minesweeper game). Implementing guessing is straightforward - we need to pick the highest probability from the list. Like this:
if (!foundAtLeastOneSolution && notCertainProbabilities.length > 0) {
const highestProbabilityOfBeingEmpty = notCertainProbabilities.reduce(
(curProb: Probability, prevProb: Probability) => {
return curProb.getProbabilityOfBeingEmpty() > prevProb.getProbabilityOfBeingEmpty()
? curProb
: prevProb;
}, notCertainProbabilities[0]);
yield Action.open(highestProbabilityOfBeingEmpty.cell);
}
After that we need to start the whole algorithm from beginning, since we don't want to keep guessing, but rather solve it normally.
At this point there is completely viable Minesweeper solving algorithm which can handle majority of cases on the gaming field.
The next step might be teaching it to pick the direction of solving. Since the game is about grabbing a territory, it is usually a good idea to occupy some strategic points of the field (center for example) quicker than your opponent.
Top comments (4)
I like the article simply because it's about minesweeper.
Using logicJS is also an interesting solution. I never enjoyed prolog but the JavaScript offering might be more enjoyable.
Now I wonder if Sudoku can be solved in 80 lines of code as well
Sudoku can be solved in 9x9=81 lines :)
You just need to formalise following statements:
1) Square [0,0] contains either 1, 3, 6 or 8
2) Square [0,1] contains either 3, 7 or 8
...
81) Square [8,8] contains 2, 4 or 9
Just wanted to say I love this. I've not used LogicJS but that's definitely on my radar now. Thanks!
Hmm, now it is kinda tempting to try this in minikanren / core.logic...