6
$\begingroup$

When I play Minesweeper, every now and then I reach a point where I have to make a guess. I then try to calculate the probability for every option to be a mine in order to choose the safest move. But sometimes I find that different calculations result in different probabilities, which means I'm doing it wrong in some sense, and this is what I want to clarify.

Below is an example of such a dilemma. enter image description here Notice the green mark in the upper-left region. I have two choices next to the 4-mark, each with a probability of $\frac{1}{2}$.

On the other hand, from the 5-mark point of view, we need to select 2 squares out of 3, suggesting a $\frac{2}{3}$ probability for each square.

We can also follow a third calculation, by starting from the 2-mark on the rightmost square on this remaining "island": if the upper square is a mine, it can be easily seen that the upper square of the 4-mark must also be a mine; if not- it can be shown that both 4-mark squares have equal probability to be mines. This implies that the upper 4-mark square has probability of $\frac{3}{4}$ to be a mine - again a contradiction.

A more "desperate" attempt would be to say that all three "calculation trajectories" are equally likely, thus we need to add the calculated probabilities and sum them up with a factor of $\frac{1}{3}$. But that is quite awkward, and I'm sure there is more solid reasoning here, but I wasn't able to prove it myself.

So... what is the correct way to calculate the probability?

As a last remark - I assume here that the remaining island is large enough such that no further meaningful information can be extracted from the remaining squares, such as the number of remaining mines, or a direct enumeration of all possible mine distributions.

Thanks, and I hope you find this intriguing as I do. :)

$\endgroup$
  • $\begingroup$ Just to complicate things further: the real goal would be a strategy which maximizes the probability of eventually winning. It could potentially be the case that such a strategy doesn't always choose a square with minimum probability of being a mine, if that happens to give less "useful information" on average than choosing another square with a marginally higher probability of being a mine. $\endgroup$ – Daniel Schepler Nov 8 '17 at 22:57
  • $\begingroup$ @DanielSchepler amen to that! I actually employ what you're saying in the cases I need to make more than one guess, so I try to pick a square that has more chance of providing useful information for the other squares that currently need guessing $\endgroup$ – Yoni Nov 8 '17 at 23:11
4
$\begingroup$

You get different probabilities because in each case you only consider a particular part of the board, and thus in each case you only consider only a strict part of all the information that is there. So, there really aren't any contradictions here.

If you want to know what the probability is given the whole board, then your calculations will become more complicated. In fact, you'd have to take into account even more than those three 'trajectories' you mentioned ... and if you add the information that there are exactly 10 more mines to place, it becomes more complicated yet.

Still, I would say that your third line of reasoning (that start with the 2 in the top right of the open region) probably gets closest to the actual probability, for the following reasons:

  1. It takes into account the most information (indeed, it includes the information regarding the 5-square).

  2. There is a good bit of room left at the top left, thus you can easily pack different numbers of mines there, so even knowing there are 10 mines left should minimally impact/constrain what could happen next to that 2.

  3. The 3 flags stacked on top of each other next to the 5 naturally carve the space in a 'left' and 'right', and there is no direct line of reasoning as to how satisfying the numbers on the left will impact what happens on the right.

So, the number of ways you can work out having a mine directly to the left of the top right 2 should be very close to the number of ways you can have a mine below that ... meaning that I would agree that, even if you take into account the whole board, the probability of a mine in each of those squares is indeed around $1/2$, and with that, the probability of the top square next to the 4 being a mine is indeed very close to 3/4

In general, though, yeah, try and take into account everything as is 'humanly possible' ... which in most cases is not considering how many more mines there are. But the example you gave here does show how certain lines of reasoning take into account more information than others, and the more information you take into account, the closer you tend to get to the probability if you somehow could take into everything.

$\endgroup$
  • $\begingroup$ Thanks for your answer. In this small island I agree, because the direct calculation might still be manageable. But suppose you have a much larger island left (as often is the case), how should you treat this problem given "human computation power"? In the limit of large island and complicated "shorelines", is there a proper treatment for this case? $\endgroup$ – Yoni Nov 8 '17 at 22:02
  • $\begingroup$ @Yoni Well, I would guess that your third line of reasoning probably gets closest to the actual probability, for it takes into account the most information (indeed, it includes the information regarding the 5-square). And indeed, if I had to pick between the two squares next to the 4, I would definitely say that the top one is more likely to be a mine. $\endgroup$ – Bram28 Nov 8 '17 at 22:09
  • $\begingroup$ @Yoni I added a bit more to my Answer, explaining why I think your third line of reasoning will likely be closest to the actual probability. $\endgroup$ – Bram28 Nov 8 '17 at 22:24
  • $\begingroup$ I think the solution is a sort of combination of what you said with @cws approach. Basically I think that if we assume the rest of the board provides little information/constraints, we can decompose the problem to a smaller independent sub-board, which is the green part plus the 2-mark area, and enumerate all the allowed possibilites for that subspace (also assuming uniform distribution for Minesweeper's alg.) $\endgroup$ – Yoni Nov 8 '17 at 23:08
1
$\begingroup$

There is no meaningful way to calculate such probabilities without knowing the algorithm that minesweeper uses to generate the board. You would then compute the probability that, say, the top square contains a mine as:

$$P(\text{Top square is mined})=\frac{P(\text{Algorithm would generate a compatible board with a mined top square})}{P(\text{Algorithm would generate a compatible board})}$$

Where a "compatible" board means a placement of mines consistent with the clues you already have and the mines you've already revealed.

There really is no simpler way since the algorithm could potentially be very complicated in order to avoid generating boards that are boring to solve. You could try solving toy versions of the problem in which the board is selected uniformly, or where each square is mined independently with probability $p$, which I imagine would lead to rather tedious combinatorics computations involving working out exactly how many configurations of mines are consistent with the clues you already have.

$\endgroup$
  • $\begingroup$ Thanks. Considering the case of uniform distribution, how would you go about the calculation? $\endgroup$ – Yoni Nov 8 '17 at 23:00
  • $\begingroup$ @Yoni I would sit down with some graph paper and try and work out all possible solutions to the clues (remembering that there have to be exactly ten mines). Then count them and count how many have a mine in any particular square. $\endgroup$ – Jack M Nov 9 '17 at 9:49
1
$\begingroup$

First, I would label the squares. Pretending the green area is like a matrix, $M$, use the same indexing conventions. Hence, $M_{4,2}, M_{3,2}, M_{1,2}$, and $M_{1,3}$ are blank. Now list all the possibilities.

The following lists the possible ways there could be mines at each position, given just the green box.

$M_{4,2}, M_{1,2}, M_{1,3}$

$M_{3,2}, M_{1,2}$

$M_{3,2}, M_{1,3}$

Hence, given the box there is a 1/3 chance there is a mine at $M_{4,2}$, and a 2/3 chance there is a mine at $M_{3,2}$. Picking $M_{4,2}$ would be better.

$\endgroup$
  • $\begingroup$ Hmmmm... I like approach very much. I think it is useful to choose a larger matrix though. Like @Bram28 said, the 2-mark on the right provides useful information. And still the allowed mine distributions are small enough to enumrate over directly. $\endgroup$ – Yoni Nov 8 '17 at 23:03
  • $\begingroup$ @Yoni Exactly ... the larger the box, the better (indeed: why did you draw the box as you did, when your third line of reasoning started outside of it?) ... as long as you can 'humanly' manage it. $\endgroup$ – Bram28 Nov 8 '17 at 23:06
  • $\begingroup$ Well that was just to pin-point to an area that is easy to refer to in the text ("that 5 mark over there..."). But you're right, I might as well marked the whole region. $\endgroup$ – Yoni Nov 8 '17 at 23:14
0
$\begingroup$

To calculate the probability you need to first determine all the positions that mines can be placed to correctly satisfy all the known information on the whole board.

Then for each position you need to calculate the 'weight' for the position, i.e. how many ways this position can be formed. This is done by, using combinatorics, calculating how many ways the remaining mines (not used to satisfy the known information) could be positioned in the remaining space (not next to information tiles).

Then the total number of solutions is the sum of the 'weights'.

The probability of a tile containing a mine is the sum of the weights across the positions that have a mine in that tile divided by the total number of solutions.

Some work has been done in this area and there are threads discussing it on the minesweeper reddit page. The best automated solvers use optimised variations on this approach to help them make their decisions.

$\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.