Algorithms and data structures behind Minesweeper Battle

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:

1. Identify opened cells which has closed neighbour mines.
2. Iterate through them and open/flag cells by analysing each individual cell until possible.
3. 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.
4. When steps 2 and 3 didn't find any solution - try to guess one cell and go to step 2.
5. 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!

Comments

[GZMaster]

Would it be wise to program our computer to recognize a particular pattern in the number placement of the minesweeper, for instance from experience playing the game number 1 at the edge of any unknown square always means that the unknown square is a mine and should be flagged, with this we could have our computer check first for any that fits that situation and quickly flag it, to increase the performance time. In conclusion wouldn't it be better to have our computer first deal with all possibilities we are sure of to increase the speed and performance.

[Lam]

Demo Minesweeper Battle Online