1
$\begingroup$

I'm trying to calculate the probability of a cell in Minesweeper when there's constraint intercepting with each other:

enter image description here

The related cells is marked with ID as shown in the snapshot. Obviously, X1 and X2 could not be mine, since C1 is surrounded by 3 mines already. Therefore, accordingly to C2, The probability of A3 and A4 is 1/2. Likewise, The probability of A1, A2, A3 is 1/3 due to C3.

Since A3 is constraint by both C2 and C3, so what is A3's probability? And how would A1, A2, A4's probability change after the change of A3's probability on both constraints. Please help me with some thoughts, thanks.

$\endgroup$
5
  • 2
    $\begingroup$ It depends on the underlying distribution of mines. Or rather, on the frequency of mines. If mines are rare - the probabilty of only A3 being a mine is higher. If they are more frequent - then we might expect two mines out of the four and the probability of A3 being a mine is lower. $\endgroup$ Commented Aug 17, 2019 at 9:51
  • $\begingroup$ I don't think it relates to the frequency of mines. Let's say, due to some reason, the probability of A3 is 1/1000000 (very small) due to the constraint of C2, then we could virtually safely say that A1 and A2's probability would be ~ 1/2 due to the constraint of C3 (since A3's probability of being mine is negligible due the C2 in the above assumption). @DaphnaKeidar $\endgroup$
    – KAs
    Commented Aug 17, 2019 at 9:54
  • 2
    $\begingroup$ In my opinion the only way to make an accurate calculation of this is by taking into consideration all possible puzzles that include this bomb subset, and it's lengthy at best. Not to mention that knowing the three free squares you haven't unveiled yet (x1, x2 and the one up there) and the number of bombs would be valuable information. $\endgroup$
    – user239203
    Commented Aug 17, 2019 at 9:56
  • $\begingroup$ It could be safely assume that there's sufficient bombs in this scenario, and what is considered here is only A1 to A4's probability according to C1 to C3's constraints. @Gae.S. $\endgroup$
    – KAs
    Commented Aug 17, 2019 at 9:58
  • 1
    $\begingroup$ If you weight all the placements equally, then of course you have just three scenarios of bombs: $\{A_1, A_4\},\ \{A_2,A_4\},\ \{A_3\}$. So $A_4$ would be $2/3$ bomb, whereas $A_1$, $A_2$ and $A_3$ would be $1/3$ each. $\endgroup$
    – user239203
    Commented Aug 17, 2019 at 10:04

2 Answers 2

4
$\begingroup$

You have to consider all cases for the whole subset of cells $\{A_1,A_2,A_3,A_4\}$. That is, given the constraints, it can be BeeB, eBeB, eeBe (where 'e' means empty and 'B' bomb). But to find out the probability of each case, you have to know the number of bombs left, and assume a distribution (uniform should be fine).

For instance, if you know for sure there is only one bomb left, then you know where it lies, with probability $1$.

If you don't know how many bombs are left, or if there is more than one, you can compute the probability that a uniform sample of bombs ends up with one (resp. two) bombs among $A_1-A_4$, conditioned on the constraint that it's either one or two. But to do this accurately you should also take into account all the other known constraints on the whole game, which is quite cumbersome (but actually they are simpler).

$\endgroup$
2
  • $\begingroup$ Thanks for the detailed answer. I still have one question, as i left on the above comment: Let's say, due to some reason, the probability of A3 is 1/1000000 (very small) due to the constraint of C2, then we could virtually safely say that A1 and A2's probability would be ~ 1/2 due to the constraint of C3 (since A3's probability of being mine is negligible due the C2 in the above assumption). Could I deduce as above? Thanks! $\endgroup$
    – KAs
    Commented Aug 17, 2019 at 14:11
  • 1
    $\begingroup$ If the probability to have a bomb on A3 is small, it's certainly not because of C2, which gives only the information that there is a bomb either in A3 or A4 (so, considering only this, it's 50/50). Note also that you know for sure that there is either one or two bombs among A1-A4. And knowing how many tells you at once if there is a bomb in A3. Regarding your hypothesis, you have an answer by conditioning: assuming that there is no bomb in A3, then the probability of having a bomb in A1 is 0.5 (and the same for A2) (if the distribution of bombs is uniform, which is a natural hypothesis). $\endgroup$ Commented Aug 17, 2019 at 14:41
1
$\begingroup$

You can attach a propositional variable to each cell of the matrix. A variable is true if and only if its cell holds a bomb. You can then write a formula $f$ that is true whenever the assignment to the variables is consistent with the given information.

Suppose $f$ has $N$ satisfying assignments and that $x$ is true in $N_x$ of them. If all satisfying assignments are equally likely, $N_x/N$ gives the probability that $x$ is true in the actual solution. In particular, if cell $x$ is safe (no bomb is there) $N_x=0$, and if a bomb is present, $N_x=N$.

As mentioned by @Jean-ClaudeArbaut, $f$ depends on whether the total number of bombs is known and, in case it is known, on the exact value.

The computation is better done with a computer. Here's a couple of matrices. First, the case when no (nontrivial) bound on the total number of bombs is known:

$$\begin{matrix} 1/2 & 1/2 & 1/2 & 1/3 & 1/3 & 1/3 & 1/2 & 1/2 \\ 1/2 & 0 & 0 & 0 & 0 & 1 & 1/3 & 1/2 \\ 1/2 & 1 & 0 & 1 & 0 & 0 & 1/3 & 1/2 \\ 1/3 & 1 & 0 & 0 & 0 & 1 & 1/3 & 1/2 \\ 1/3 & 0 & 0 & 1 & 0 & 0 & 1 & 1/2 \\ 1/3 & 1/2 & 1/2 & 1 & 0 & 0 & 2/3 & 1/2 \\ 1/2 & 1/2 & 1/2 & 1/2 & 1/2 & 1/2 & 1/2 & 1 \end{matrix}$$

Then under the assumption that there are $13$ bombs (the minimum possible in this case):

$$\begin{matrix} 0 & 0 & 0 & 1/3 & 1/3 & 1/3 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 1/3 & 1 & 0 & 0 & 0 & 1 & 1 & 0 \\ 1/3 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \\ 1/3 & 1/2 & 1/2 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{matrix}$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .