Minesweeper Assistant
Minesweeper Assistant
The aim of this project is to develop software helping people who hate losing in Minesweeper (this game comes with Windows).
The project is available at several levels of difficulty.
Level 1 (suitable as a short project). Your program should satisfy at least the following requirements:
- The program’s interface should be similar to the standard Minesweeper interface (you are allowed to adapt freeware versions of Minesweeper).
- During the game, the user should be able to ask for assistance (e.g. by pressing the “Assist” button). In such a case, your program should either suggest a “safe” move or indicate that it cannot find such a move. At this level of difficulty, the software is to make decisions simply by looking at common patterns on the game field (e.g. if all the mines around a numbered square are marked, one can safely uncover the remaining squares around it).
- There should be a possibility to execute the decision procedure iteratively, until either no more “safe” moves can be found or the game is solved.
- Your program must not cheat, i.e. it must access the data structures describing the locations of the mines in a black-box way. To achieve this, you must use the class MineField encapsulating the mine field, with the following implementation:
http://homepages.cs.ncl.ac.uk/victor.khomenko/teaching/projects/MineField.java
It ensures that the mines are distributed randomly and uniformly, and its interface allows only for the black-box access. During the demonstration, I will supply my own implementation of this class MineField of this project, with exactly the same interface, but generating a different mine distribution.
Level 2 (suitable as a regular stage 3 project). At this level, at least the following requirements should be taken into account (in addition to the ones described above):
- At this level of difficulty, you should implement a decision procedure which is guaranteed to find a “safe” move if there is one (procedures based on finding particular patterns on the game field give no such guarantee). The problem can be reduced to a system of simultaneous constraints, and solved using existing solvers – but your program should interface them somehow. Note that a pattern-based decision procedure should be attempted first, as it might find a “safe” move quickly.
- Solving a system of simultaneous constraints can take a long time, so the user should be able to interrupt the process without stopping the game.
Level 3. At this level, at least the following requirements should be taken into account (in addition to the ones described above):
- Even if there are no “safe” moves, still some moves may be “less dangerous” then others. At this level of difficulty, you program should suggest a move even if there are no “safe” ones, by taking probabilities into account. (E.g. it can try to work out the probability of a particular uncovered square having a mine, and then suggest a square with minimum such probability.)
- Your program should take into account some strategic considerations in cases when there are no safe moves: if there are several equally dangerous moves, the one which is likely to lead to a better position should be chosen. (E.g. in the very beginning of the game, there are no “safe” moves, and all the squares are equally “dangerous” in terms of probability of having a mine; however, strategically it makes sense to uncover a square diagonally adjacent to a corner, as this is likely to allow for sensible subsequent moves.)
