So, Minesweeper is a game. As I have to implement an AI for my Artificial Opponents class that will play Minesweeper, what follows could be considered my plan regarding how I will go about implementing this AI logic.
A Preface
I’m somewhat of a novice when it comes to Minesweeper. I’ve played it casually, sure, but I don’t know much about the competitive scene. Thus, my plan for implementing this Minesweeper-solving logic will probably follow a more neophyte-level strategy. However, I may augment this with some more advanced strategies if it isn’t good enough.
General Approach
When playing minesweeper I try to build off of the corner tiles that you can essentially guarantee have a mine beneath them, and thus, flag. Corners like these:
Thus, here is how the general logic of my AI implementation will work:
1. random guess
2. put every revealed numbered tile (that is not already in the closed list) in an “open” list
3. go through open list and find every tile that only has a number of unrevealed adjacent tiles equal to its “adjacency number” – flag those unrevealed tiles
4. move those numbered tiles to a “closed” list
5. put all flagged tiles in an “open” list
6. go through Adjacent Revealed Tiles of each open flagged tile – if the adjacency number requirement (of an Adjacent Revealed Tile) is met and there are any unrevealed tiles adjacent to a Adjacent Revealed Tile, flip those tiles
7. repeat 2 – 6 (if stuck, repeat steps 1 – 6)
Psuedocode
1
indexChoice = random
2
for each (tileNumber in tileArray)
if (!uncoveredClosedList.contains(tileNumber))
uncoveredOpenList.add(tileNumber)
3 – 5
for each (tileNumber in uncoveredOpenList)
if (checkNumOfHiddenAdjacent(tileNumber) == getAdjacencyNumber(tileNumber))
flaggedList.add(getHiddenAdjacentTiles(tileNumber))
uncoveredOpenList.remove(tileNumber)
uncoveredClosedList.add(tileNumber)
6
for each (tileNumber in flaggedList)
for each (adjacentTile in getRevealedAdjacentTiles(tileNumber))
if (adjacencyRequirementMet(adjacentTile))
for each (adjacentUnrevealed in getUnrevealedAdjacentTiles(adjacentTile))
flipTiles(adjacentUnrevealed)
Major Classes
I plan on having a few classes.
Firstly, I’m working in C++, which doesn’t have the convient List class that C# does, so I’ll probably make my own (using std::vector) and incorporate some simple list functions – like contains(), add(), remove() – in order to make my code a bit cleaner.
Secondly, I’ll probably have some sort of TileLogic class or something of the sort. Basically, this will have functions like getUnrevealedAdjacent(), getRevealedAdjacent(), etc. (all of the functions that gather certain indices based on data from the GameView and Cell classes), as well as functions to ensure that these indices checks don’t go out of range of the tile array. This class will also store flagged tiles and hold the various open and closed lists required for my implementation.
Scalability
The implementation I have described above is a somewhat beginner/intermediate strategy. While it may work on easier board arrangements, there will probably be times on more difficult boards when there is no clear-cut next move to take, and a random guess will be less than desirable. Fortunately, there are some more advanced tactics to be aware of in the world of competitive minesweeper. Of particular note is the two primary patterns (1-2-1 and 1-2-2-1), which be potentially be used on sections of board where there are no clear-cut “guaranteed” situations (at least according to my basic logic loop). Recognition of these two patterns could be added into my logic fairly easily and could potentially help in tough situations. Unfortunately, random guessing is sometimes necessary, but hopefully I can minimize the amount needed in my AI implementation.
– wednesday
References
General:
http://www.minesweeper.info/wiki/Strategy
http://www.minesweeper.info/wiki/Tournaments
Images:
minesweeper.info/wiki/Image:Pattern121.PNG
minesweeper.info/wiki/Image:Pattern1221.PNG
gauze.txt.png 