Course:CPSC312-2017-Minesweeper

Minesweeper

Authors: Imelda S, Rachel Z, Josh Z

Source Code

https://github.com/jwzzhou/CPSC-312-Project-1-Minesweeper

What is the problem?

We will use Prolog to implement Minesweeper. Minesweeper is a single player game where the objective is to clear a game board filled with hidden mines. The player can achieve this by choosing a square to reveal. Successfully revealing an empty square will show how many mines are adjacent to that square. If the player reveals a mine, the game is over. The player wins when all non-mine squares are revealed (and thus the only unrevealed squares are those with mines).

What is the something extra?

Often times, minesweeper games are impossible to complete without some element of guessing (i.e. no matter how well you can logically deduce the position of mines, some positions are undeducable and thus you must resort to guessing). The usual strategy to mitigate this is to change your mine-placement algorithm when generating a game board such that mines are placed in such a a fashion where the reveal pattern will make guessing not needed. We propose a different strategy for those who enjoy guessing as part of the game, but make failed guesses less punishing.

We will implement a life system such that each time a player reveals a mine, the player then loses one life. All other revealed squares are untouched; however, all unrevealed squares are shuffled, essentially redistributing the mines across the game board. Adjacency counts are then updated, and the game resumes. Traditional game over is reached when the player reaches 0 life. The player can specify how many lives they would like to start with, and is able to play 'classic' minesweeper by choosing to start with one life.

What did we learn from doing this?

Prolog (or logic programming in general) offers many advantages and disadvantages when implementing minesweeper.

Advantages include high-level code readability. This is as a result of unification, allowing for some rather succinct predicate declarations, where the equivalent in a declarative programming language would be a sprawling if statement with multiple cases. An example of this is determining what default states of the game are allowed (beginner, intermediate, and custom mode), where what would be at least 5 messy and long if statements are concisely put into 5 brief predicate declarations. Recursion is also reasonably intuitive - you simply have to capture all the different cases. This made recursively revealing all nearby 0 tiles not too difficult to implement.

A major disadvantage of logic programming (or at least prolog) at the low-level is its implementation of lists. Since we can only access elements of a list through the binary operator [H|T], lists in prolog end up functioning much like a linked list in terms of complexity. This means accession and mutation of lists (especially 2d lists, which were used to represent the gameboard) is not constant time. With larger game board sizes (e.g. 300+ rows), significant slowdown is apparent as the program often needs to traverse the entire "matrix" multiple times. Furthermore, Prolog uses more recursion rather than iteration, which can make code readability hard as no for/while loops are used and make space complexity an issue for large scale programs. Finally, only using console output severely hinders the maximum board size, as only a certain number of columns are allowed so a single 'row' of the game board stays on one line in the console/terminal. A future improvement may be to make use of some of prolog's GUI libraries for a more interactive user experience.