Solving Minesweeper: The Good Part

Intro

So after quite some time, I have crafted a minesweeper solving AI, and it was… an exercise of imagination. Of sorts.

First thing to say, while I lightly peeked at one or two solvers that were pointed to me by other classmates, I disregarded anything useful in them – not because they were bad solvers – but because I just preferred to figure it out through my own methods in this particular situation.

That is to say, everything that I completed in regards to this solving algorithm was of my own mind, which was my intent in my last post: Create an AI that acts as similar to a human as possible (with the new clause of performing well – this becomes important when guessing becomes a factor).

And as you’ll see, I think I came up with a pretty impactful algorithm that increases the solver’s winrate by a notable amount.

Results

First and foremost, to anyone coming to this post interested in how well the algorithm has done, I have run a multitude of what I am calling the “300 Test,” that is, 100 attempts at an official size large minesweeper board (30×16, 99 mines), 100 attempts at a medium board (16×16, 40 mines), and 100 attempts at a small board (9×9, 10 mines).

My results for the 300 Tests (read as hard board winrate, medium board winrate, small board winrate, and then time) are as follows:

Test 1: 4/100 50/100 73/100 (16.9m)
Test 2: 5/100 47/100 75/100 (No Time) – Forgot to record time
Test 3: 2/100 49/100 80/100 (16.2m)
Test 4: 1/100 33/100 52/100 (10.5m)
Test 5: 2/100 52/100 75/100 (16.2m)
Test 6: 4/100 41/100 55/100 (13.5m)
Test 7: 5/100 29/100 59/100(13.9m)
Test 8: 1/100 34/100 63/100 (13.1m)
Test 9: 5/100 49/100 68/100 (24.3m)
Test 10: 4/100 52/100 74/100 (23.0m)
Test 11: 4/100 52/100 74/100 (16.2m)
Test 12: 9/100 48/100 70/100 (17.3m)

It is of note that these scores are not of the same version of the algorithm. In fact, almost each one was tested on a different iteration of the algorithm, which accounts for the disparity in times and results for some. Around test 4 I implemented a bad guessing algorithm which resulted in a far lower time and score as it guessed bombs very frequently. At test 9, I added a condition to remove squares from the revealed list, which seemed to considerably slow down the algorithm (despite it’s purpose to speed it up considerably). At test 11, that same condition was still in the algorithm (and I removed another bit), so I’m thinking it might not be the cause.

The algorithm, as of this post, is unfinished in optimization. I am unsure if I ever will finish it, given all of the other work I have and will become busy with, and I will probably “finish” this and move on, unfortunately.

The Code

Beginning with the function list:

//Add any adjacent hidden cells around the index that are not in the permanent flagList to the temporary flagList
void addAdjacentHiddenCellsToTempFlagList(GameView theView, UINT index);

//Add all hidden cells around the index to the flagList (no duplicates)
void addAllHiddenCellsToFlagList(GameView theView, UINT index);

//Add all revealed cells to the revealed list (no duplicates)
void addAllRevealedCellsToRevealedList(GameView theView);

//Returns true if at least two adjacent cells are within the temp flag list (wow totally not the function name)
bool atLeastTwoAdjacentCellIsWithinTempFlagList(GameView theView, UINT index);

//Get an index of a cell adjacent to the index that is has no mine guaranteed (scans both flag lists)
UINT getCleanCell(GameView theView, UINT index);

//The number of cells adjacent to the index that are flagged
UINT getNumFlaggedCells(GameView theView, UINT index);

//The number of cells adjacent to the index that are hidden (not revealed). If bool is true, then ignore any cells on either flag list.
UINT getNumHiddenCells(GameView theView, UINT index, bool checkFlagLists);

//Returns true if the selected index is not on the permanent flag list
bool isNotOnFlagList(GameView theView, UINT index);

//Remove any revealed cells from the revealed list if all adjacent cells are revealed for flagged
void removeAllFinishedRevealedCells(GameView theView);

And important variables:

std::vector flagList, revealedList, tempFlagList;

I opted to not use a class, as I felt global variables would be fine for only needing 3 vectors.

The Algorithm

Now for the spicy part. Let’s go over in a step by step process how the entire algorithm works, then let’s take a look at actual code.

Step by Step

  1. Clear the temporary flag list. Important for clicking clean cells.
  2. Add any and all revealed cells to the revealed list, do not allow for duplicates.
  3. Remove any “finished” revealed cells (see comment above removeAllFinishedRevealedCells function). (This step is purely for optimization, I am unsure if it accomplishes that task. Fiddle as you wish).
  4. If the upper left cell is hidden, reveal it. This is the first move every game. (Personal choice of where to start).
  5. Main flag and reveal loop:
    1. Scan through every cell in the revealed list
    2. If the cell’s number (I will refer to this as cell(n) or iA(n) in the future, iA being indexA, iB is indexB, etc) is greater than 0 and equal to the amount of hidden adjacent cells, add every hidden cell around it to the flag list.
    3. If the cell(n) is greater than 0 and less than the amount of hidden adjacent cells, but the number of adjacent flagged cells is equal to the cell(n), reveal any hidden non-flagged cells around it.
  6. Now the real fun begins, the bread and butter of the algorithm as a whole. I crafted an adjacency algorithm that uses a temporary flagging system to identify safe squares that can be clicked. If you look at two pictures in my last minesweeper post, you can see the idea in practice.
    1. Same as last time, scan through every cell (iA) in the revealed list.
    2. Clear the temporary flag list, removing leftovers from the last iteration.
    3. If iA(n) + 1 is equal to the number of adjacent hidden cells, add all adjacent hidden cells to the temporary flag list. (You can only determine safe squares if you only have 1 square that is in contention).
    4. Scan through every cell adjacent to iA. These scanned cells will be called iB.
    5. Five checks here, you can only progress if:
      1. iB is revealed.
      2. iB(n) does not equal 0.
      3. iB has at least TWO adjacent cells in the temporary flag list. (This step is very important and the area that took me forever to nail down. There are a number of fringe cases that occur if iB only has one adjacent temp flag list, and it fails if you must have it touch every cell in the temp flag list).
      4. One of the two is true
        1. Both of the following are true
          1. iB(n) – iB(number of adjacent flagged cells) (ONLY on the permanent flag list, not temporary) equals the number of hidden cells minus the number of permanent adjacent flagged cells AND minus the number of temporarily flagged cells.
          2. The number of hidden cells minus the number of permanent adjacent flagged cells AND minus the number of temporarily flagged cells is equal to 1. (If it is 2, the choices of a clean cell are ambiguous, and you can easily hit a bomb, but with only 1 cell, you can be certain it is a safe square).
        2. Both of the following are true
          1. iB(n) is less than the number of hidden cells minus the number of permanent adjacent flagged cells AND minus the number of temporarily flagged cells.
          2. iB(n) is equal to 1.
    6. Clear the only safe square in the area.
  7. In the event that the main loop fails to get any hits and the adjacency algorithm falls flat, you are left to random guessing. I did attempt to do an estimated guessing algorithm, but I clearly didn’t put enough time into it (most of my time was spent on the previous algorithm), because it hit more bombs than a standard random cell choice.
    1. While (true)
    2. Get a random index from all available cells.
    3. If it is hidden and not on the permanent flag list, reveal it.

Code

It is worth noting that I used my professor’s framework and in no way wrote the full minesweeper game (though I did do that in flash back in my sophomore year, which was actually very fun), so there will be references to classes and events I will cover real quickly.

GameView is a wrapper class around the GameState, giving access to the information of the board without allowing the user to cheat by just asking for the mines’ locations. Every time theView is referenced, it is an instance of GameView.

CellClickTransactions are the events sent back to the main program, telling it to click and reveal a given index.

All other references should be to the functions, which code I won’t post so this post doesn’t stretch for miles, but the general descriptions of how they work are in the comments above each’s name.

tempFlagList.clear();

addAllRevealedCellsToRevealedList(theView);
removeAllFinishedRevealedCells(theView);

if (!theView.getCell(0).isRevealed())
{
  pHandler->postTransaction(new CellClickTransaction(0));
  return;
}

//Scan throught revealed list to clear and flag
for (UINT index : revealedList)
{
  UINT hiddenCellNum = getNumHiddenCells(theView, index, false);

  if (theView.getNumAdjacentMines(index) != 0)
  {
    //If the cell's number equals the amount of hidden cells around it, flag em all
    if (theView.getNumAdjacentMines(index) == hiddenCellNum)
    {
      addAllHiddenCellsToFlagList(theView, index);
    }

    //If the cell's number is less than the amount of hidden cells around it, but the count is equal to the flagged amount, start revealing
    if (theView.getNumAdjacentMines(index) postTransaction(new CellClickTransaction(cleanIndex));
      return;
    }
  }
}

//Funtime adjacency algorithm
for (UINT indexA : revealedList)
{
  tempFlagList.clear();

  if (theView.getNumAdjacentMines(indexA) + 1 == getNumHiddenCells(theView, indexA, false))
  {
    addAdjacentHiddenCellsToTempFlagList(theView, indexA);
    for (UINT indexB : theView.getAdjacentCellIndices(indexA))
    {
      UINT numHiddenCellsTrue = getNumHiddenCells(theView, indexB, true);
      if (theView.getCell(indexB).isRevealed() && theView.getNumAdjacentMines(indexB) != 0 && atLeastTwoAdjacentCellIsWithinTempFlagList(theView, indexB) &&
      ((theView.getNumAdjacentMines(indexB) - getNumFlaggedCells(theView, indexB) == numHiddenCellsTrue && numHiddenCellsTrue == 1) ||
       (theView.getNumAdjacentMines(indexB) < numHiddenCellsTrue && theView.getNumAdjacentMines(indexB) == 1)))
      {
        UINT cleanIndex = getCleanCell(theView, indexB);
        pHandler->postTransaction(new CellClickTransaction(cleanIndex));
        return;
      }
    }
  }
}

while (true)
{
  UINT randomIndex = rand() % theView.getNumCells();
  if (!theView.getCell(randomIndex).isRevealed() && isNotOnFlagList(theView, randomIndex))
  {
    pHandler->postTransaction(new CellClickTransaction(randomIndex));
    return;
  }
}

And there you have it, the full minesweeper solving AI.

Final Thoughts

Overall I think it works fairly well, given that the guessing algorithm isn’t refined, a ~4-5% winrate on hard is pretty alright.

I also have to give an estimate of how well I think my AI will do compared to everyone else, and honestly I’m feeling good. I’m sure others will have thought the same thing I did, but apparently there’s a single set algorithm from a Harvard paper floating around in use in our class, and from what I understood, it certainly doesn’t do adjacency. Can’t predict much more than that, but I’m confident.

As usual, more to come next week after it goes into contention with everyone else in my class’ AIs.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s