Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. It only takes a minute to sign up.
Sign up to join this community
In order to solve this minesweeper game, what is the optimal next move?
A description of the game can be found here: https://en.wikipedia.org/wiki/Minesweeper_(video_game)
I do not have the answer to this puzzle, and nor am I sure that it is feasible to compute it.
There are 50 different possible ways that the unknown mines next to the revealed region could be configured:
Here, the green cells are clear (no mines), while the X's around the perimeter indicate the different ways the mines could potentially be placed.
If we consider each of these to be of equal probability (probably not quite true, because the total number of mines on the board might mean that configurations with more (or less) mines are slightly more (or less) probable), then we simply need to count the number of configurations with a mine in each location to determine the probability of finding a mine there.
Doing so, we end up with
From this, it seems evident that the best move is on the fifth row, where there is an 8. Making this move gives you only a 16% chance ($\frac8{50}$) of finding a mine.
Conversely, picking one of the bottom squares means you have a 66% chance ($\frac{33}{50}$) of finding a mine.
Obviously, the other option is to pick a random non-adjacent square, and hope to get lucky.
There are 25 squares revealed, and an additional 13 squares adjacent to those, for a total of 38. Subtract that from 480 total squares, and we have 442 potential "guesses". There have been 5 of 99 mines revealed already, and there could be anywhere from 4 to 7 mines in the adjacent squares. To give our best shot at a random guess, let's assume there are 7 mines adjacent, leaving us with 87 mines in the non-adjacent area.
That means that picking a random non-adjacent square will give us an $\frac{87}{442} \approx 0.1968$ or 19.7% chance of finding a mine, which is still worse than our best-case 16% above.
As GentlePurpleRain says in their excellent answer, there are $50$ different possible placements for the mines in the squares around the solved region. However they make the assumption that each of these possibilities is equally likely. This is not correct.
The possibilities that GentlePurpleRain lists contain either $4$, $5$, $6$, or $7$ mines in the squares around the solved region. Therefore the rest of the board must contain $90$, $89$, $88$, or $87$ mines. There are $30\times16 - 38 = 442$ squares on the rest of the board. So the number of ways of placing these remaining mines can be calculated combinatorially:
$$\text{4 mines:}\qquad\binom{442}{90} = 4.837\times10^{95}$$ $$\text{5 mines:}\qquad\binom{442}{89} = 1.233\times10^{95}$$ $$\text{6 mines:}\qquad\binom{442}{88} = 3.101\times10^{94}$$ $$\text{7 mines:}\qquad\binom{442}{87} = 7.686\times10^{93}$$
The number of combinations for $4$ mines is nearly two orders of magnitude larger than for $7$!
To find the probability that there is a mine in a particular square we must count how many times it appears in the $50$ possibilities, but weighted by these factors. This gives the following probabilities:
(and the probability of a square outside this region being a mine is $0.20$.) For reference here are the probabilities without the weightings:
You can see that there are some significant differences. In particular the safest choice of square has changed from the square in the fifth row to either of the two squares below it (which do in fact have exactly the same probability as each other).
Of course these two moves might still not be the ones that give the best chance of success, since playing the immediately safest move might not be best in the long run. A square might have a higher chance of being a mine, but also be more likely to reveal more information. There is evidence that playing on the edges tends to be better in the long run. The bottom left cell is on the edge and also has a very good probability of being safe, so that might well be the optimal move.
Quick thoughts not considering moves further than the next one:
If you want to make a move on a tile adjacent to what you already uncovered, take into consideration serveral thoughts:
FACTS:
1. "4" is a number larger than average in default settings
2. All three "3"s have already 2 mines attached, so 1 left per each
3. In all 5 tiles adjacent to "4" there are 3 mines (3/5 probability to hit the mine for each of these tiles)
CONCLUSIONS:
4. The uncovered tile between "3" and "4" (X=4, Y=7) has about 3/5 probability to contain a mine (according to the "4" neighbourhood)
5. Additionally, the uncovered tiles adjacent to the right of this "3" (X=4, Y=6) have not more than 1/4 probability to contain a mine (4 tiles, 1 mine)
6. The other uncovered tiles adjacent to this tile are probably less than "4" (from 1.), so there is pretty high probability that the tile between "3" and "4" does contain a mine.
7. If we are "lucky", from the point 6. we can tell that the other 3 tiles adjacent to the "3" (which is next to "4") should not contain a mine (the last mine of this "3" is on the tile next to "4"), so choose one of those. (X=5, Y=5, 6 or 7).
Facts and trivial observations/calculations:
Game area is 30x16 = 480 tiles and there are 99 mines. On average a bit above 1 bomb per 5 tiles.
You see 5 mines and have uncovered 25 tiles.
You know there are 9-12 mines in the total 38 tile area you see or adjacent.
This means you still have about 20% of hitting a mine if you randomly select a tile far away. Sounds pretty reasonable strategy, better than probability next to any mine - bottom 3 has 4 for 25%.
But ...
On one hand, 1 and 2 suggest probability of mines under 1 and 2 are the same, 1/2. However, 4 suggests probability of a mine under 2 is higher, 3/5. So, we have a difficulty - what probability should the tile have?
We quickly see that:
If probability of tiles includes 0, end probability has to be 0. If it includes 1, it has to be 1 (and it obviously cannot be 1 and 0 at the same time, it would be logically inconsistent, so output in that case is irrelevant).
It clearly also needs to lie between the 2 values and be symmetric. We would also like it smooth as possible - 1-eps and anything large compared to eps should return near 1 (while 1-eps and eps should return 0.5). So, no avg except for the corner cases or stuff like that.
Yes, this seems a bit overkill for those few integers, but general function gives better justification for the number than a quick guess.
I used trigonometric functions, as they seem suitable enough. First, start with P' = pi*(P-0.5) to get value between -pi/2 and pi/2. Then Pnew' = atan((tan(Pa')+tan(Pb'))/2); Pnew = Pnew'/pi+0.5.
We have the function. What now?
For the 0.5 and 3/5, we get 0.55 to have bomb under 2 and therefore 0.45 to have it under 1. OK, looks reasonable. Now apply this philosophy to 2 of the bottom right 3's tiles, which are the interesting ones: We have 1/4 and 3/5 and 1/3 and 1/4, these 2 together give 0.68 (simple P1+P2, which is obviously slightly wrong as those numbers aren't independent completely, but should be ok enough). Now, the remaining 2 values have 0.16 each, which is better than a random guess.
In the next move you therefore:
Should press on the tile right or right-down of the bottom 3. Haven't calculated what could happen in the next step to decide which of these would be better.
This is a probability game now.
Pressing random tile that is not in the 5*8 square of the visible space (+1 tile near) gives only around 20% to land on mine. Next step is to optimize that choice. One of the corners is always a good choice (Since it reduces that chances of having another probabilistic option later on), I would pick the leftmost down corner - Since after a few steps it can give us a hint to what to do in the current visible corner.
Without considering the exact probability of any of the squares, I would be very tempted to open the 6th square in the 5th column. The 2nd, 4th and 6th square in this column has one thing in common. Opening either of these will allow you to open the three adjacent squares in the sixth column whenever neither of these contain a mine. I'd guesstimate that for an expert size board, this would mean that you get to open three additional squares (extra information) about fifty percent of the time. I (intuitively) assign the best probability of success to be the 6th square because the 4 will frequently have a mine to its right, making the guess relatively safe.
Compare this with opening the fifth or seventh square in the column or the square in the first column(suggested directly or indirectly as an option by some of the previous posters that have estimated probabilities of each square). The issue is that opening either of those squares would almost never give an immediate reward in the shape of the ability to open additional squares.
