DEV Community: Andrii Mishchenko

Creating advanced Minesweeper solver using logic programming

Andrii Mishchenko — Tue, 14 Jul 2020 20:02:00 +0000

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.

Algorithms and data structures behind Minesweeper Battle

Andrii Mishchenko — Tue, 16 Jun 2020 23:16:36 +0000

Hi Dev.to community,

With this blog post I'd like to start a series of blog posts dedicated to my project Minesweeper Battle.

Intro

Data structures and algorithms is basically what every computer program consists of. Organising data in the most optimal way and using proper algorithm for a specific task make programmer's life incredibly easier. And visa versa - utilising a structure or algorithm which is not applicable for certain requirements can lead to series of workarounds, mistakes and suffering. In this post I'd like to describe in details how picking a correct data structure helped me to implement a vital part of the project in a clean and simple way.

The game

Minesweeper Battle is a web-based variation of classical Minesweeper game, where it is possible to play against another player (currently - computer player only). The goal is to "occupy" larger territory than your opponent and not to explode on a mine at the same time. At the moment tech stack of the game consists of Typescript, Vue.js and Bulma CSS framework.

The game starts on a field of NxM cells. Each player has their own starting location - for human player it is usually top left corner, for computer player - bottom right corner. Initial placing of mines is made in such a way that both players have several cells opened from the beginning, in order to avoid the situation when one should make a guesses too early. An important rule, which probably makes the whole sense of this variation of Minesweeper, is that it is possible to open or flag only those cells which border to your own territory. It prevents players from interrupting with each other and forces them to rely only on their skills (and a little bit of luck) in order to win.

Computer player

One of the most challenging parts of the game was to implement the logic of Computer player. Computer player is the program that must be able to play the game of Minesweeper by analysing already opened cells and opening or flagging closed ones. Further I will describe how it was done step by step.

First, some context:

The game is represented by a Game class containing two-dimensional array of Cell and two methods - openCell and flagCell.

openCell method sets the Cell.opened to true and checks if there is mine in that cell. If yes, then the player, who opened the cells, has exploded. If no, then it checks for cell's neighboursMinesCount property. If it is equal to 0, then it recursively opens all neighbours. As a result, it returns an array of Cells that have been opened.
flagCell method sets Cell.flagged property to true.

class Game {
    fieldWidth: number;
    fieldHeight: number; 
    cells: Cell[][] = [];

    openCell(cell: Cell): Cell[] {
        // open cell logic
    }

    flagCell(cell: Cell): void {
        // flag cell logic
    }
}

class Cell {
    x: number;
    y: number;
    neighbourMinesCount: number;
    hasMine = false;
    opened = false;
    flagged = false;
}

Actually these classes contain a bit more data and logic, but we're interested only in these for now

Before writing the code of ComputerPlayer let's specify some requirements for it. For this it is necessary to realise how we - humans - play Minesweeper game. A human looks at those cells that are opened and have one or more closed neighbour cells containing mines. Then they try to calculate or guess where these mines exactly are. All variations of placement of opened and closed cells with mines can be divided into three categories:

a decision of opening/flagging certain cells can be done by analysing only one cell
a decision of opening/flagging certain cells can be done by analysing several cells which have common closed neighbour cells
a decision can be done by guessing

Algorithm of Computer player

Thus high-level algorithm can be described as:

Identify opened cells which has closed neighbour mines.
Iterate through them and open/flag cells by analysing each individual cell until possible.
When there is no any progress in step two, try to analyse chunks of cells which has common neighbours and go to step 2 after first iteration.
When steps 2 and 3 didn't find any solution - try to guess one cell and go to step 2.
Continue this algorithm until the game is finished.

Now let's dive into details of each step.

Finding opened cells is easy - we need to iterate through all cells and take those which matches this criteria:

cell.opened && cell.neighbourMinesCount > 0;

After that we need to iterate through them and analyse each cell until we stop finding any solution. That already becomes tricky. On every iteration a new cells might be (and most probably will be) opened or flagged, so we have to somehow include newly opened cells into the cycle of the fly. And if the cell has been resolved - meaning all it's neighbours either opened or flagged - then it should be removed from the list and not being taken into consideration anymore. Also it is not enough to iterate through the list only once, because if on the first iteration one particular cell couldn't be resolved, then on the second one there is a chance that it actually will.

It already becomes clear, that storing cells in a simple Array will not satisfy our needs. It will be too awkward to modify array size during iteration, and it is not possible to conveniently iterate throw it multiple times.

Let's list our requirements:

we need to be able to iterate through the list multiple times
we need to be able to add new items
we need to be able to remove items

Which data structure would fit our needs then?

Doubly linked list

From Wikipedia:

In computer science, a doubly linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains three fields: two link fields (references to the previous and to the next node in the sequence of nodes) and one data field.

According to Big O cheat sheet, insertion and deletion operations of Doubly linked list both has complexity of O(1). In comparison, same operations for Array has complexity of O(n).

Seems like exactly what we need! Unfortunately, Typescript doesn't have any implementation of Doubly linked list, so we need to create it ourselves.

The list consists of a nodes linked between each other. Let's define a Node class first:

// to make it more independent, instead of using Cell class
// we use generic type T 
class Node<T> {
    value: T;
    next?: Node<T>;
    prev?: Node<T>;

    constructor(value: T) {
        this.value = value;
    }
}

... and create a DoublyLinkedList:

class DoublyLinkedList<T> {
    private head?: Node<T>;
    private tail?: Node<T>;
}

For now, it contains only two properties - head and tail - references to the first and the last nodes in the list. Let's add method which adds a new node to the list - I called it append because it adds new node to the tail of the list.

    append(node: Node<T>): void {
        // handle special case when the list is empty
        if (this.head === undefined) {
            this.head = node;
            this.tail = node;
        } else {
            this.tail.next = node;
            node.prev = this.tail;
            this.tail = node;
        }
    }

Method remove is a little bit more complex - it is necessary to check whether references to next or prev are pointing to any Node class, and that node being removed isn't a current head or tail of the list:

    remove(node: Node<T>): void {
        const prevNode = node.prev;
        const nextNode = node.next;

        if (prevNode !== undefined) {
            prevNode.next = nextNode;
        }
        if (nextNode !== undefined) {
            nextNode.prev = prevNode;
        }
        if (this.tail === node) {
            this.tail = prevNode;
        }
        if (this.head === node) {
            this.head = nextNode;
        }
    }

At this point we already have a structure which we can use for efficiently adding or removing nodes. What about iteration? We're going to use Generator for that:

    *iterate(): Generator<Node<T>> {
        let node = this.head;
        while (node instanceof Node) {
            yield node;
            node = node.next;
        }
    }

Nice and simple! But wait, what about iterate through the list multiple times requirement? With current implementation of iterate method, it is possible to iterate the list only once - it will yield nodes from head to tail and then break. Can we do anything about it? Sure we can - we make our linked list cycled. We just link tail and head with each other:

    private linkTailAndHead(): void {
        this.tail.next = this.head;
        this.head.prev = this.tail;
    }

That will make iterate method literally run around until the loop is interrupted outside. Of course that creates a potential for running into endless cycle issue, but we will handle that as well.
So the final implementation of the list is:

class DoublyLinkedList<T> {
    private head?: Node<T>;
    private tail?: Node<T>;

    append(node: Node<T>): void {
        if (this.head === undefined) {
            this.head = node;
            this.tail = node;
            this.linkTailAndHead();
        } else {
            this.tail.next = node;
            node.prev = this.tail;
            this.tail = node;
            this.linkTailAndHead();
        }
    }

    remove(node: Node<T>): void {
        // handling the last item in the list
        if (node === this.tail && node === this.head) {
            this.tail.next = undefined;
            this.tail.prev = undefined;
            this.tail = undefined;
            this.head = undefined;
        }

        const prevNode = node.prev;
        const nextNode = node.next;

        if (prevNode !== undefined) {
            prevNode.next = nextNode;
        }
        if (nextNode !== undefined) {
            nextNode.prev = prevNode;
        }
        if (this.tail === node) {
            this.tail = prevNode;
        }
        if (this.head === node) {
            this.head = nextNode;
        }
    }

    *iterate(): Generator<Node<T>> {
        let node = this.head;
        while (node instanceof Node) {
            yield node;
            node = node.next;
        }
    }

    private linkTailAndHead(): void {
        this.tail.next = this.head;
        this.head.prev = this.tail;
    }
}

Usage of Doubly linked list

At this point we've prepared a solid background for our solving algorithm. Let's utilise it!

class ComputerPlayer {
    private game: Game;
    private cellsToAnalyze: DoublyLinkedList<Cell>;

    initialize(): void {
        this.cellsToAnalyze = new DoublyLinkedList<Cell>();
        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];
                if (cell.isOpened() && cell.neighbourMinesCount > 0) {
                    this.cellsToAnalyze.append(cell);
                }
            }
        }
    }

    play(): void {
        let firstNoActionNode: Node<Cell>|undefined = undefined;
        for (let node of this.cellsToAnalyze.iterate()) {
            const cell = node.value;

            const flaggedNeighbourCellsCount = cell.getFlaggedNeighbourCellsCount();
            if (flaggedNeighbourCellsCount === cell.neighbourMinesCount) {
                for (let neighbourCell of this.game.iterateNeighbours(cell)) {
                    if (!neighbourCell.isOpened() && !neighbourCell.isFlagged()) {
                        firstNoActionNode = undefined;
                        const openedCells = this.game.openCell(new Node(neighbourCell));
                        for (let openedCell of openedCells) {
                            this.cellsToAnalyze.append(new Node(openedCell));
                        }
                    }
                }
                this.cellsToAnalyze.remove(node);

                continue;
            }

            let closedNeighbourCellsCount = 0;
            for (let neighbourCell of this.game.iterateNeighbours(cell)) {
                if (!neighbourCell.isOpened()) {
                    closedNeighbourCellsCount++;
                }
            }

            if (closedNeighbourCellsCount === cell.neighbourMinesCount) {
                for (let neighbourCell of this.game.iterateNeighbours(cell)) {
                    if (!neighbourCell.isOpened() && !neighbourCell.isFlagged()) {
                        firstNoActionNode = undefined;
                        this.game.flagCell(neighbourCell);
                    }
                }
                this.cellsToAnalyze.remove(node);

                continue;
            }

            if (node === firstNoActionNode) {
                break;
            }
            if (firstNoActionNode === undefined) {
                firstNoActionNode = node;
            }
        }
    }
}

const computerPlayer = new ComputerPlayer(game);
computerPlayer.initialize();
computerPlayer.playGame();

This is a complete implementation of step 2 of our solving algorithm. First we initialise the list of cells which we're going to analyse. Then in play method we start our loop, and on every iteration we do the following:

if number of flagged neighbour cells equals to number of neighbour cells with mines, we open all remaining closed cells and append them to the list for further analysis
if number of closed neighbour cells equals to number of neighbour cells containing mines, we flag these cells
notice the firstNoActionNode variable, it serves the role of loop breaker. The logic behind it can be described as "when we cycled through all nodes in the list and neither opening nor flagging of any cell has happened, then we need to break the loop"

Now we have an engine that can play the game pretty much efficiently. Let's see it in action :)

Awesome result! Although despite computer has stuck at the end of the video, experienced Minesweeper players could have noticed, that it is actually possible to continue the game. Unfortunately, our code isn't smart enough to analyse combinations of cells... yet. That is because only 2 of 5 steps of our solving algorithm has been implemented so far.

We're going to tackle remaining steps in the following posts.

Thank you for your attention!