5
$\begingroup$

This is a follow-up to the question: Calculating odds of Minesweeper is this correct?

I was given good advice & answers pointed out some flaws in my calculation. However editing the original post would make the answers outdated.

I've only modified the board slightly, adding another number so that simplifying a section is not possible. I did this because I'd like to ensure my calculation can apply to any board & makes sense in doing so.


enter image description here

N = number of mines = 25

T = number of unidentified squares = 123

As you can see I've broken up the board into colored groups based on having identical odds so that It isn't necessary to calculate each square individually. For example, 'A', 'B', 'F' & 'I' are all touching a '3'. There is no reason 'A' would have different odds than 'B' 'F' or 'I'.

I will split the squares into 2 sections:

Section1 - Left marked section (ABFI, MNO, K...)

Section2 - Right marked section (PTV,QRWX,SUY)

Seciton3 - All the unknown squares. These are all the blank grey squares

Based on the numbers we know that:

Section1 + Section2 must have a sum of:  5, 6, 7 or 8 mines.
Section3 must have the rest, being:      20, 19, 18, or 17 mines.

I'll refer to what we know as 'Rules'. We know the total number of mines surrounding a '1' must equal '1'.

Rules:

ColorGroups                                # of bombs in ColorGroups
-----------                                ----------------------------
(A+B+F+I) + (C) + (G) + (J)       =        3
(D+E+H+L) (C) + (G) + (K)         =        1
(M+N+O) + (J) + (K) + (G)         =        1
(P+T+V) + (RXWQ)                  =        2
(S+U+Y) + (RXWQ)                  =        1

Now, for the left side (Section1), we can get all the solutions by making assumptions. For example, if we assume ABFI = 3 than C, G & J must all be 0 since we have a rule: ABFI + C + G + J = 3. We will do the same for the right side (Section2) afterwards.

Assume (C) has 1 bomb. In other words, the 'C' square is a bomb. (C is chosen at random, but I prefer to start with a small section). I'll call the first solution 'S1-01-01':

Keep in mind a square can have a 1 or a 0. So (A+B+F+I) could have a max of 4 (ignoring the '3') & (C) can have a max of 1

Solutions

(S1-01-01)
Grouping   # of bombs
--------   -----------
(C)       = 1
(D+E+H+L) = 0
(K)       = 0
(G)       = 0
(J)       = 1
(M+N+O)   = 0
(A+F+I+B) = 1

(S1-01-02)
Grouping    # of bombs
----        ----------
(C)       = 1
(D+E+H+L) = 0
(K)       = 0
(G)       = 0
(J)       = 0
(M+N+O)   = 1
(A+F+I+B) = 2

That's all for C = 1, so next we assume G=1:

S1-02-01       # of bombs
--------        ----------
(C)           = 0
(G)           = 1
(D+E+H+L)     = 0
(K)           = 0
(M+N+O)       = 0
(J)           = 0
(A+F+I+B)     = 2

S1-02-02
--------
(C)       = 0
(G)       = 0
(J)       = 1
(A+F+I+B) = 2
(M+N+O)   = 0
(D+E+H+L) = 1
(K)       = 0

S1-02-03
--------
(C)       = 0
(G)       = 0
(J)       = 0
(K)       = 1
(D+E+H+L) = 0
(A+F+I+B) = 3
(M+N+O)   = 0

S1-02-04
--------
(C)       = 0
(G)       = 0
(J)       = 0
(K)       = 0
(D+E+H+L) = 1
(A+F+I+B) = 3
(M+N+O)   = 1

Doing the same for the right Section:

S2-01-01:
---------
(R+X+W+Q)    = 1
(S+U+Y)      = 0
(P+T+V)      = 1

S2-02-01:
---------
(RXWQ)       = 0
(S+U+Y)      = 1
(P+T+V)      = 2

Now we list the number of bombs in every solution:

Section1

#:       S1-11  S1-12  S1-21  S1-12  S1-23  S1-24
-----    -----  -----  -----  -----  -----  ------
ABFI:    1      2      2      2      3      3
C:       1      1      0      0      0      0   
DEHL:    0      0      0      1      0      1
G:       0      0      1      0      0      0
J:       1      0      0      1      0      0
K:       0      0      0      0      1      0
MNO:     0      1      0      0      0      1
TOTALS:  3      4      3      4      4      5

Section2

#:       S2-11  S2-21
-----    -----  -----
RXWQ:    1      0
SUY:     0      1
PTV:     1      2
TOTALS:  2      3

Now we calculate the number of cases possible for every solution. This is done by using nCr (Binomial coefficient).

Where N = Number of Squares and B = numberOfBombs.

Combinations = N NCR B.

For the first solution (S1-1) these are the cases:

(ABFI)    = 4 NCR 1 = 4
(C)       = 1 NCR 1 = 1
(DEHL)    = 4 NCR 0 = 1
(G)       = 1 NCR 0 = 1
(J)       = 1 NCR 1 = 1
(K)       = 0 NCR 1 = 1
(MNO)     = 3 NCR 0 = 1

Multiplying these combinations we get: 4*1*1*1*1*1*1 = 4 cases for this solution (S1-1).

Doing the same for all solutions in the left section we get:

#:      S1-11 S1-12 S1-21 S1-22 S1-23 S1-24
ABFI:   4     6     6     6     4     4
C:      1     1     1     1     1     1   
DEHL:   1     1     1     4     1     4
G:      1     1     1     1     1     1
J:      1     1     1     1     1     1
K:      1     1     1     1     1     1
MNO:    1     3     1     1     1     3
TOTALS: 4     18    6     24    4     48

Total cases = 104

Note: In the above table, to get 'TOTALS' we multiply all combinations to get the total combinations for that solution.

Now for the right section:

#:      S2-11  S2-21
RXWQ:   4      1
SUY:    1      3
PTV:    3      3
TOTALS: 12     9

Total cases = 21

To get the total cases we need to multiply these: 21 * 104 = 2184 total cases.

For clarification, here is an example of a complete solution (S1-11+S2-11):

ABFI:    1
C:       1
DEHL:    0
G:       0
J:       1
K:       0
MNO:     0
RXWQ:    1
SUY:     0
PTV:     1

TOTAL MINES:    5
TOTAL CASES:    16

Total cases is calculated by multiplying the binomial distribution for each group as we've done before

Notice that I've taken the first case for S1 and added the first case for S2. If I were to continue, I'd write the first case for S1 + the second for S2, then the second case for S1 + the first for S2.

These 2184 total cases do not hold equal weight. We know that there are 25 mines in the total & 123 unidentified squares. 25/123 = 0.20 mines per square. This means a case with 5 mines (the minimum) will have a different weight than a case with 8 mines (the maximum).

Credit to Joriki in this answer for the formula

$\binom{t-s}{m-n}\;.$

t = remaining unidentified squares (123)

m = remaining mines (25)

s = unidentified squares in case

n = mines assigned to case

Knowing that (Section1+Section) has 25 unidentified squares and may contain 5, 6, 7 or 8 mines we assign the weights:

W1 (5 mines): $\binom{123-25}{25-5}\;$ = $\binom{98}{20}\;$

W2 (6 mines): $\binom{123-25}{25-6}\;$ = $\binom{98}{19}\;$

W3 (7 mines): $\binom{123-25}{25-7}\;$ = $\binom{98}{18}\;$

W4 (8 mines): $\binom{123-25}{25-8}\;$ = $\binom{98}{17}\;$

Before we carry on lets put our 2 sections into 1 "FullSection". We do this by "Multiplying" section2 & section1. By that I mean, for every solution in Section1, add every solution in Section2.

Section1 has 6 solutions with total mines of: 3, 4, 3, 4, 4, 5. Section2 has 5 solutions with total mines of: 2, 3

'Full Solutions Table' (The section # isn't really important)

Full Section # # of mines  # of cases 
-------------- ----------  ---------- 
1              6           36
2              6           216
3              7           576
4              5           72
5              7           36
6              6           48
7              6           54
8              5           48
9              6           288
10             7           162
11             7           216
12             8           432
Total cases: 2184

For every solution, we will tally up how many times 5, 6, 7 & 9 mines are the sum:

Cases with 5 mines: 120

Cases with 6 mines: 642

Cases with 7 mines: 990

Cases with 8 mines: 432

The sum of the weights (Using W1 - W4 depending on number of mines):

(120 * $\binom{123-25}{25-5}\;$) + (642 * $\binom{123-25}{25-6}\;$) + (990 * $\binom{123-25}{25-7}\;$) + (432 * $\binom{123-25}{25-8}\;$)

Sum of weights = 1.190143e+23

So given any case, say one with 5 mines in it, the probability will be: $\binom{123-25}{25-5}\;$ / 1.190143e+23 = 0.00287497486

Doing the same with 5, 6, 7, 8

5 = 0.00287497486
6 = 0.00072784173
7 = 0.00017286241
8 = 0.00003841386

Since there are 120 cases with 5 mines:

120 * 0.00287497486 = 0.3449969832

Again doing the same with 5, 6, 7, 8:

5 = 0.345
6 = 0.467
7 = 0.171
8 = 0.017
Sum:    1

We will be applying the single weight to every case, but I just wanted to ensure the sum is = 1

Applying these weights, we can create a table where the weight is based on the W for number of mines, multiplied by the number of cases and the value under each coloured group for the section represents the odds per square.

E.G: for S1, the number of mines is 6 and there are 36 cases. The green section is 4 squares in length and contains 1 mine so:

0.00072784173 * 36 = 0.02620230228
(1/4) * 0.02620230228 = 0.02620230228

Results:

S#   Mine Count  # of cases   weight           (C)          (DEHL)       (K)          (G)          (J)          (MNO)        (AFIB)      (RXWQ)      (SUY)         (PTV)
---  ----------  ----------   -------------    ----------   ----------   ----------   ----------   ----------   ----------   ----------   ----------   ----------   ----------
1    6           36           0.02620230228    0.02620230   0.00000000   0.00000000   0.00000000   0.02620230   0.00000000   0.00655058   0.00000000   0.00873410   0.01746820
2    6           216          0.15721381368    0.15721381   0.00000000   0.00000000   0.00000000   0.00000000   0.05240460   0.07860691   0.03930345   0.00000000   0.05240460
3    7           576          0.09956874816    0.00000000   0.02489219   0.00000000   0.00000000   0.00000000   0.03318958   0.07467656   0.02489219   0.00000000   0.03318958
4    5           72           0.20699818992    0.00000000   0.00000000   0.00000000   0.20699819   0.00000000   0.00000000   0.10349909   0.05174955   0.00000000   0.06899940
5    7           36           0.00622304676    0.00000000   0.00000000   0.00622305   0.00000000   0.00000000   0.00000000   0.00466729   0.00000000   0.00207435   0.00414870
6    6           48           0.03493640304    0.00000000   0.00000000   0.03493640   0.00000000   0.00000000   0.00000000   0.02620230   0.00873410   0.00000000   0.01164547
7    6           54           0.03930345342    0.00000000   0.00000000   0.00000000   0.03930345   0.00000000   0.00000000   0.01965173   0.00000000   0.01310115   0.02620230
8    5           48           0.13799879328    0.13799879   0.00000000   0.00000000   0.00000000   0.13799879   0.00000000   0.03449970   0.03449970   0.00000000   0.04599960
9    6           288          0.20961841824    0.00000000   0.05240460   0.00000000   0.00000000   0.20961842   0.00000000   0.10480921   0.05240460   0.00000000   0.06987281
10   7           162          0.02800371042    0.02800371   0.00000000   0.00000000   0.00000000   0.00000000   0.00933457   0.01400186   0.00000000   0.00933457   0.01866914
11   7           216          0.03733828056    0.00000000   0.00933457   0.00000000   0.00000000   0.03733828   0.00000000   0.01866914   0.00000000   0.01244609   0.02489219
12   8           432          0.01659478752    0.00000000   0.00414870   0.00000000   0.00000000   0.00000000   0.00553160   0.01244609   0.00000000   0.00553160   0.01106319
Totals:                          0.99999995    0.34941862   0.09078006   0.04115945   0.24630164   0.41115779   0.10046035   0.49828045   0.21158359   0.05122186   0.38455518

Looking at the result table we can see that any blue square (MNO) has the least chances of being a mine and any green square (AFIB) has the greatest chances of having a mine.

The results seems reasonable, but is it correct?

$\endgroup$
3
$\begingroup$

Everything seems basically OK now; the final result table seems to be correct. There are some minor isolated errors that don't seem to have affected anything else:

In your "example of a complete solution (S1-11+S2-11)", it should be $12\cdot4=48$ total cases, not $12+4=16$.

In the calculation immediately above "Results:", $(1/4)\cdot0.02620230228=0.02620230228$, the right-hand side isn't divided by $4$.

And in your summary of the results, I don't see why you say that MNO have the lowest marginal probability of containing a mine; from the table it's K with about $0.04$, and DEHL and SUY also have lower marginal mine probabilities than MNO with about $0.1$.

By the way, a good check for the results (that checks out) is to compute the expected total number of mines once by adding the marginal mine probabilities for all squares and once from the marginal probabilities of the total mine counts $5$ through $8$. The expected total mine count in the $25$ coloured squares is about $5.86$.

$\endgroup$
1
$\begingroup$

In the OP's query in this posting, although I did not manually check his Results table, I think that his analysis looks good, with minor errors. Also, I agree with all of the points made by joriki in his answer. In this answer, I explore the following topics related to the OP's query: minor errors; relative weights; probability of a mine in a random Section3 cell; computer analysis vs manual analysis; and determining the optimal move.

$\underline{\text{Minor Errors}}$
Rather than edit the OP's query directly, I follow joriki's approach of describing the errors for the OP to correct himself.

S1-11 S1-12 S1-21 S1-12 S1-23 S1-24 should be
S1-11 S1-12 S1-21 S1-22 S1-23 S1-24

For the first solution (S1-1) these are the cases:
...
(K) = 0 NCR 1 = 1
...
should be
...
(K) = 1 NCR 0 = 1
...

As joriki's answer indicates:

In the OP's "example of a complete solution (S1-11+S2-11)", it should be 12⋅4=48 total cases, not 12+4=16.

The OP correctly computed the total number of cases as (104 x 21), which may be re-interpreted as
(4 + 18 + 6 + 24 + 4 + 48) x (12 + 9).
Computing the # of cases of (S1-11 : combined with : S2-11) as 4 x 12 = 48
is consistent with the above re-interpretation.

For every solution, we will tally up how many times 5, 6, 7 & 9 mines are the sum: should be
For every solution, we will tally up how many times 5, 6, 7 & 8 mines are the sum:

$\underline{\text{Relative Weights}}$

As the OP indicated the 5-mine weight (hereafter denoted as W:5) is $\;\binom{98}{20}\;$, while W:6, W:7, and W:8 are $\;\binom{98}{19},\; \binom{98}{18},\; \text{and} \;\binom{98}{17},\;$ respectively.

Let W-Case-x denote the weight assigned to Case x (i.e. 1 <= x <= 2184).
Let Sum_Of_Weights denote (W-Case-1 + W-Case-2 + ... + W-Case-2184).
Then the probability of Case-x occurring = W-Case-X / Sum_Of_Weights.

Therefore, if a specific constant K is chosen
and each of W:5, W:6, W:7, W:8 is multiplied by this constant K,
then the computation of the probability of Case-x will be unchanged.

Therefore, appropriate application of a constant can significantly simplify the math involved in applying the weights (i.e. avoid messy math).

For example, let $K = \frac{(20!)(81!)}{98!},\;$ and apply this constant to each of W:5, W:6, W:7, W:8. Then the new weights are
W:5 = (81 x 80 x 79), W:6 = (20 x 81 x 80), W:7 = (20 x 19 x 81), W:8 = (20 x 19 x 18).

The new weights all have a common factor of 180, so applying 1/180 to each of the revised weights will yield
W:5 = 2844, W:6 = 720, W:7 = 171, W:8 = 38.

$\underline{\text{Probability of a Mine in a Random Section3 Cell}}$

Let P-x denote the probability that [Section1 + Section2] contains exactly x mines (i.e. 5 <= x <= 8).
Then the probability of a mine in a random cell chosen from Section3 =
P-5 x (20/98) + P-6 x (19/98) + P-7 x (18/98) + P-8 x (17/98).

The OP computed that :
the # of cases with 5 mines = 120
the # of cases with 6 mines = 642
the # of cases with 7 mines = 990
the # of cases with 8 mines = 432.

Using the relative weights from the previous section in my answer,

Sum-Of-Weights = (120 x 2844) + (642 x 720) + (990 x 171) + (432 x 8)
P-5 = (120 x 2844) / Sum-Of-Weights
P-6 = (642 x 720) / Sum-Of-Weights
P-7 = (990 x 171) / Sum-Of-Weights
P-8 = (432 x 8) / Sum-Of-Weights.

$\underline{\text{Computer Analysis vs Manual Analysis}}$

I think that the OP's manual analysis illustrates the computations needed to compute the chance of a mine in each of the 25 squares of [Section1 + Section2]. However...

I do not recommend using manual analysis, even with a minesweeper diagram as simple as the one in this posting. Instead, I recommend writing a computer program to compute the probabilities. The program would use brute force to try all of the $\;2^{25}\;$ possible mine distributions in [Section1 + Section2], and determine that exactly 2,184 of these distributions satisfy the constraints.

The computer programming approach avoids having to create colored sections, and avoids having to analyze cases (e.g. either cell C has a mine or it doesn't, and if cell C does not have a mine, then either cell G has a mine or it doesn't,...). The computer program can also compute the probability of a mine in a random Section3 cell.

Therefore, the computer program can identify the risk associated with each possible next move.

$\underline{\text{Determining the Optimal Move.}}$

I considered omitting this section because

(1) The OP's specific question is
given a specific minesweeper diagram, how does one compute the probability that a specific cell has a mine?
Therefore this section may reasonably be construed as off-topic.

(2) In my judgement, determining the optimal move all but defies mathematics. Therefore, this section may reasonably be construed as opinion-based.

However, I surmise that this section is of very general interest to Minesweeper players and that this section represents an elegant application of the analysis contained in this posting.

I try to use risk vs reward intuition, where risk reflects the probability that a specific cell contains a mine and reward reflects the probability that useful information will be obtained, perhaps allowing the user to identify cells which although still hidden, logically can not contain a mine.

Since the chance of a randomly chosen Section3 cell having a mine must be somewhere between (20/98) and (17/98), a reasonable guesstimate is
(18.5/98) =~ 0.189.

Based on the OP's Results table, looking at the table's Totals line, I would immediately reject selecting any Section3 cell, and in fact only consider selecting one of cells K, S, U, or Y. Since choosing cell K may lead to uncovering cells between Section1 and Section2,
my next move would be to select cell K.

$\endgroup$
2
  • $\begingroup$ @dustytrash I just gave an answer. $\endgroup$ – user2661923 Dec 9 '19 at 2:47
  • $\begingroup$ Thank you for this answer. There's nothing I disagree with. I should have mentioned I've been creating a program alongside these posts. My program won't factor in the risk vs reward, but it's a good point. Maybe in the future I'll look at measuring the rewards & factoring it in $\endgroup$ – dustytrash Dec 9 '19 at 3:08

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.