So here this is a question related to the grid efficiency in MSN minesweeper.
$\begin{matrix}
\square & \square & B_1 & B_2 & B_3 & \square & \square\\
\cdots & 1 & 1 & 1 & 1 & 1 & \cdots \\
\cdots & 0 & 0 & 0 & 0 & 0 & \cdots
\end{matrix}$
Suppose that you have a line of 1s along a long enough edge (basically you do not get any information from the two endpoints of the edge), then at any of the 1s, the chance of a mine appearing on a random grid should be 1/3...or is it?
Assume that the universal distribution is uniform. I.e. that is an equal chance of getting any of the $C^n_r$ many combinations (ignoring the corner rule since it is less relevant). Similarly without further hints, if we have n remaining unrevealed grids and r remaining mines, then the number of possible combinations is again $C^n_r$.
Out of the formula there is one single variable that varies with actual config - the number of remaining mines depends on the length of the edge modulo 3. Let $r_i$ be the remaining mines count after revealing the row given the configuration $B_i$. Then
$P(B_i) = \frac{C^n_{r_i}}{\sum C^n _{r_k}}$
If the number of mines to be revealed is independent of the configuration then we can conclude that the chance are equal. Otherwise we can compare the binomial terms:
$C^n_{r+1} = C^n_r \frac{n-r-1}{r+1}$
The usual ratio between grids and mines is 5:1 -- but that varies greatly depending on the given situation. In particular there are loads of 1s and 0s in our example, which boosts the ratio greatly. At the ratio of 2:1 the increase of mines would not increase the likelihood of the evisceration, but of course such ratio is unrealistic in a minesweeper setup, so we can say that the configuration that the configuration that leads to less mines on the row, is more likely.
One may raise the question: shouldn't the equilibrium happens at 3:1 instead of 2:1, from a likelihood perspective? We can visualize the likelihood approach by the following problem.
In a box there are $n$ balls, in which $r\approx n/x$ are white, and the rest are black. (i.e., the ratio between balls and white balls is $x:1$). Suppose we draw $\alpha$ balls out of it and we want to compare the chance of having $\beta \approx \alpha /3$ or $\beta +1$ white balls in the draw. If we want the chance between the two events to be comparable:
$\frac{C^{n-\alpha}_{r-\beta}C^{\alpha}_{\beta}}{C^{n-\alpha}_{r-\beta-1}C^{\alpha}_{\beta +1}} = \frac{(n-\alpha-(r-\beta))(\beta +1)}{(r-\beta)(\alpha -\beta-1)} \approx \frac{1}{2} \frac{n-\alpha - (r-\beta)}{r-\beta} = 1$
That gives $n-\alpha \approx 3(r-\beta)$, or $n \approx 3r$.
In our problem however, the term $C^{\alpha}_{\beta}$ does not exist, because we do not take the full combination within the balls drawn. In other words, we do not allow orders like
BBBWWWWWW
BBWWBWWWW
BWWWWWWBB...
The three only allowed scenarios are
BWWBWWBWW
WBWWBWWBW
WWBWWBWWB
Once we fixed that in our formula, similar calculations yield $n\approx 2r$, instead of $3r$.
*
Of course there is no such 'infinite edge' in minesweeper. The endpoints is definitely giving extra information unless it looks like the following:
$\begin{matrix}
\square & \square & \square & \square & \square & \square & \square & \square & \square\\
\square & 1 & 1 & 1 & \cdots & 1 & 1 & 1 & \square\\
\square & 1 & 0 & 0 & \cdots & 0 & 0 & 1 & \square\\
\square & 1 & 0 & 0 & \cdots & 0 & 0 & 1 & \square\\
\square & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \square
\end{matrix}$
Any extra information would impose extra difficulty on these kind of analyses, but I am here to give some primary idea on what's happening.
To give an application, consider the following example. I said on my twitter that red made a bad move:
The reason behind is simple. There is only [something between 1/4 and 1/2] chance that the grid contains a mine. On the other hand if it does not the opponent gets a free flag immediately with everything else remains the same.
But...is it possible to calculate the exact chance? Yes, and this is not hard at all: this is a 16x16 board with 51 mines. The shown area is the only revealed portion. To calculate the probability we list the few only scenarios then the chance follows by the binomial coefficients.
No comments:
Post a Comment