8
$\begingroup$

In order to solve this minesweeper game, what is the optimal next move?

enter image description here

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.

$\endgroup$
  • $\begingroup$ As from what I can see, it's just a guessing game. Sadly this happens from time to time in Minesweeper.. $\endgroup$ – Radhato Apr 13 '17 at 6:54
  • $\begingroup$ Yes, but there are better guesses than others. $\endgroup$ – Improve Apr 13 '17 at 6:55
  • 4
    $\begingroup$ bottom right corner. $\endgroup$ – Marius Apr 13 '17 at 6:58
  • 5
    $\begingroup$ To optimize time you should press the yellow face on the top and start over ;) $\endgroup$ – oleslaw Apr 13 '17 at 7:39
  • 2
    $\begingroup$ mrgris.com/projects/minesweepr $\endgroup$ – kaine Apr 13 '17 at 13:16
13
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Have you compared with choosing a nonadjacent square at random? $\endgroup$ – Improve Apr 13 '17 at 20:39
  • $\begingroup$ @Improve Thanks for pointing that out. I've updated my answer accordingly. $\endgroup$ – GentlePurpleRain Apr 13 '17 at 21:00
  • $\begingroup$ I am not sure if this solution is really ok, as good as it looks on the first sight. Imagine you have only two upper 3s and nothing else. Your method would suggest 2/5 elsewhere and 1/5 on the tile between the two numbers. But would that tile really be less probable? I don't think so - I would rather say that you put (with 1/3 probability) a mine on any of the top 3 tiles. Then calculate conditional probability for other 2 tiles, and you end up with 1/3 probability of a mine on any of the 5 tiles. Which sounds more correct. $\endgroup$ – Zizy Archer Apr 14 '17 at 9:24
  • $\begingroup$ This is great! But I made an answer that improves on your assumption that each of those $50$ possibilities is equally likely. $\endgroup$ – Oscar Cunningham Aug 30 '17 at 19:49
  • $\begingroup$ with my luck, i'd choose a 33! $\endgroup$ – JonMark Perry Oct 9 '17 at 13:28
7
$\begingroup$

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:

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:

enter image description here

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.

$\endgroup$
3
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ FACTS: And the proabiltiy of hitting a bomb at any non-neighbouring tile is... (depending on the setting). Might be lower still... $\endgroup$ – BmyGuest Apr 13 '17 at 12:39
  • $\begingroup$ @BmyGuest I agree that the lowest probability of hitting the mine would probably be in a corner, but I wanted to elaborate on a more interesting case in which you want to continue with the region you already uncovered. $\endgroup$ – oleslaw Apr 13 '17 at 13:03
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Another point to consider is how much useful information one would gain from picking a square that doesn't have a mine. Picking a square in the middle of noplace might not be very helpful if it comes up with a 2 or greater, but a square two squares to the right and one down from the upper-right 3 might be helpful whether it has a low number or a high number (since a high number would influence the probable placements for the 3's). $\endgroup$ – supercat Apr 13 '17 at 18:43
  • $\begingroup$ @supercat Well, the tile you mentioned would be quite irrelevant if it is 2-4 or maybe even 5, meaning you need to be quite lucky to not get this outcome (haven't calculated, but I guess you have ~20% chance of success). Picking number right to bottom 3: 2 is very helpful outcome, as you know right 3 tiles next to it cannot be bombs, and can give you additional information. As probable as "no bombs next to corner" - 50%. But yeah, other 50% is getting 3, 4 or 5 there = useless. $\endgroup$ – Zizy Archer Apr 13 '17 at 20:40
  • $\begingroup$ Three spaces neighboring the spot I described would be addressed by two "count" squares. If bombs are uniformly distributed, the five other neighboring squares should on average contain one bomb. If that square were to show a 4, that would suggest that it would be unlikely that none of the squares to its left held a bomb, which would suggest in turn that it would be unlikely that the top or fourth square in the column between the new square and the existing squares would have a bomb. $\endgroup$ – supercat Apr 13 '17 at 20:48
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.