Last time we managed to greatly optimize the image analysis part of our little solver. That is great, however we only managed to run into bomb a lot faster. In Part 5 i was very, very … VERY frustrated about the amount of guesses needed to solve a table. I was wrong!
A couple of very good friends told me that there are situations where analyzing only one cell doesn’t result in any additional moves, but switching our attention to a specific area can help us uncover more detail. Let’s look at the following image.
This is an extract from a game state where our previous algorithm needed to make a guess. Direct your attention to the area marked by the red rectangle. Lets number the outer blue squares.
- The cell directly under the first 2 on the horizontal line.
- The cell directly under the first 4 on the horizontal line.
- The cell directly under the first bomb under the horizontal line.
- The cell at the left of the first 2 on the vertical line.
- The cell at the left of the second 2 on the vertical line.
- The cell at the left of the bomb outside the rectangle.
If you are a better minesweeper player than me you’ll noticed that for some of these cells we can determine if they are a bomb or not in the following way. Notice that both cell 1 and 2 cannot be bombs because the condition of the 2 next to them denies it. The 4 has 3 neighbors, from which 2 are bombs. That means that cell number 3 is a bomb, only that way can we fulfill the requirements for 2 and 4. So cell 3 is a bomb, that also leads into the certainty that cell 4 and 5 cannot be bombs, because of the first 2 next to cell 4. This also makes certain that cell 6 is a bomb, because if 4,5 not bombs then the only way to satisfy the 2 next to cell 5.
The question is how to code this? I was initially contemplating in analyzing the pairs together and test all the combinations of their neighbors, then for valid solutions extract the similarities. Thank God that i’m lazy, because I found a better solution.
It’s on the same line of thinking like the Sudoku Solver. Each cell can be in one of two groups: bomb or not a bomb. Thus we can simulate each situation that trying to solve the current state further which can lead to two outcomes: valid or contradiction. A contradiction is a cell that has all of it’s neighbor solved, but the number of bombs around it doesn’t match it’s value. Let’s look at the changes made in ScanGame:
int GameDecisionMaker::ScanGame(int* game, set<int>& b, set<int>& s)
{
int res = 0;
for (int i = 0; i < SIZE; i++)
{
int z = game[i];
if (z > 0 && z < BOMB)
{
vector<int> unk;
int b = 0;
ScanCell(game, i, &b, unk);
int u = unk.size();
int outcome = 0;
if (z == b && u > 0)// not bomb
{
for (auto& p : unk)
{
game[p] = NOTBOMB;
s.insert(p);
res++;
}
}
else if (z != b && z - b == u) // bomb
{
for (auto& p : unk)
{
game[p] = BOMB;
b.insert(p);
res++;
}
}
else if (u == 0 && b != z) // contradiction
{
return -1;
}
}
}
return res;
}
Right away you can spot a few changes. First of all GameDecisionMaker, it’s a class that holds all the functionality that is concerned about making decision. In Part 6 i’ve mentioned i started to refactor the code in order to post it at the end. I removed guess-es from here because I also improved that a bit. In this version of the code we return the number of decisions taken. Notice the last else if block returns -1, this is signaling a contradictions. Now let’s look at the code that searches for additional informations.
int GameDecisionMaker::ScanSecrets(set<int>& bombs, set<int>& safes)
{
set<int> undiscovered;
for (int i = 0; i < SIZE; i++)
{
int z = game[i];
if (z > 0 && z < BOMB)
{
vector<int> unk;
int b = 0;
ScanCell(game, i, &b, unk);
undiscovered.insert(unk.begin(), unk.end());
}
}
int res = 0;
for (auto& p : undiscovered)
{
bool bRes = Simulate(p, BOMB);
bool nRes = Simulate(p, NOTBOMB);
if (nRes && bRes)
{
continue;
}
else if (bRes)
{
game[p] = BOMB;
bombs.insert(p);
res++;
}
else if (nRes)
{
game[p] = NOTBOMB;
safes.insert(p);
res++;
}
}
return res;
}
bool GameDecisionMaker::Simulate(int c, int v)
{
int tempGame[SIZE];
copy_n(game, SIZE, tempGame);
tempGame[c] = v;
int res = 1;
set<int> bTemp, sTemp;
while (res > 0)
{
res = ScanGame(tempGame, bTemp, sTemp);
}
return res >= 0;
}
The first part of ScanScrets is just going through all cell’s that have a value and collects the neighbors that are undiscovered. Then we go through them and we are simulating that they are a bomb and then that they are not. Simulation just simply makes a copy of the game state, then tries to solve that GameState with ScanGame. If both of the simulations returned a valid result (they didn’t ran into a contradiction), we move forward. If only one of them is valid, we add the solution to the according action buffer.
void GameDecisionMaker::GetDecisions(set<int>& b, set<int>& s)
{
while (true)
{
int sg = ScanGame(game, b, s);
if (sg > 0) { continue; }
int ss = ScanSecrets(b, s);
if (ss > 0) { continue; }
break;
}
}
This is the method that is called from the Main functions. First we scan the game for regular solutions. If we find actions to take, we do it again, until we don’t find any more information with regular actions. Then we go into scanning for secrets, if that yields any result, we try further with the regular method, if not we consider this round over and we proceed with making moves. Let’s look at the results on our image where we failed to find any additional information.
Yes ladies and gentlemen, 16 more cells were uncovered. With this little change we solve around 25% of the attempts. F**K ME, not the game then. Before we close, a few words about the situations where we still need to make guesses. I won’t crowd this post with that too but we made changes there too. If we need to make a guess in the first 5 rounds we test additional corners in the anti-clockwise order. After the first rounds, i go for the 50-50 guesses, so if it survives a guess at least we can use the information (this might not happen in a 33-33-33 case. See you next time!