perfect play in 1-dimensional Minesweeper

Question

In 1-dimensional Minesweeper with a known number of mines (that are distributed uniformly),
is there a known somewhat-simple strategy for perfect play?

When there are n cells and [0 or n-1 or n] mines, the strategy is utterly trivial.
When there is 1 mine, the strategy is to choose an end cell and then every cell other than the obvious mine that was revealed. $\:$ While it is plausible that "start at one end and go to the other, skipping obvious mines" is always optimal, I certainly do not have a proof either way for that.

Answer 1

Perfect play is impossible because you don't have enough information for most of the game and will have to make random choices for your next move. Consider, for example, the opening move. There is no way to guarantee you don't pick a mine. Alternatively, if we say the first move doesn't pick a mine, then your first move reveals a 1. There is now no way to guarantee your second move doesn't pick a mine.

Optimal play however is a different question. Obviously there is one, compute the number of consistent mine placements left and choose the cell with the least probability of being a mine, but this is not polynomial time in the length of the board state (assumed to be a list of 0 for no mine, n for n adjacent mines, and a special character, say x). You're strategy provides the player with the minimal amount of information, and therefore seems to likely not be optimal.

Answer 2

Just an argument...

If there were two mines, wouldn't the optimal strategy be to first pick a central cell?

Assuming you don't hit a mine, you have some chance of finding the two mines with a single blind guess rather than the two you'd have to make working from the end.

And likewise for a greater number of mines, or at any point of the game, wouldn't it be better to try a central cell of a unrevealed block to maximise the chance of finding the mines two at a time?

Answer 3

It is not cleat at all that there is a best strategy. I've tried brute force by hand and I found the exact same probability to win if I play randomly the first move.

1. Lets try it with 4 squares and 2 mines.

if you play obvious or the left end: - 0011 win - 0101 win - 0110 loss - 1001 loss - 1010 loss - 1100 loss

if you play the 2nd position: - 0011 1/2 win - 0101 loss - 0110 loss - 1001 1/2 win - 1010 win - 1100 loss

1. Lets try with 5 squares and 3 mines :

   if you play obvious or the left end:

   • 00111 win
   • 01011 win
   • 01101 loss
   • 01110 loss
   • 10011 loss
   • 10101 loss
   • 10110 loss
   • 11001 loss
   • 11010 loss
   • 11100 loss

if you play the 2nd position: - 00111 1/2 win - 01011 loss - 01101 loss - 01110 loss - 10011 1/2 win - 10101 1/2 win - 10110 1/2 win - 11001 loss - 11010 loss - 11100 loss

if you play the 3rd position : - 00111 loss - 01011 1/2 win - 01101 loss - 01110 loss - 10011 1/2 win - 10101 loss - 10110 loss - 11001 1/2 win - 11010 1/2 win - 11100 loss

1. Lets try with 5 squares and 2 mines:

   if you play obvious or the left end:

   • 00011 win
   • 00101 win
   • 00110 loss
   • 01001 win
   • 01010 win
   • 01100 loss
   • 10001 loss
   • 10010 loss
   • 10100 loss
   • 11000 loss

   if you play the 2nd position:

   • 00011 win
   • 00101 1/2 win
   • 00110 1/2 win
   • 01001 loss
   • 01010 loss
   • 01100 loss
   • 10001 1/2 win
   • 10010 1/2 win
   • 10100 win
   • 11000 loss

   if you play the 3rd position:

   • 00011 1/2 win
   • 00101 loss
   • 00110 loss
   • 01001 1/2 win
   • 01010 win
   • 01100 loss
   • 10001 loss
   • 10010 1/2 win
   • 10100 loss
   • 11000 1/2 win

Answer 4

Here's a breakdown of the two-mine case. I focus on two strategies as the plausible extrema: the 'play in a corner' strategy and the 'play in the middle' strategy. Firstly, a couple of pertinent facts, including an expansion on a comment:

• If $k\geq 2$ then the probability for winning vs. one mine on a $k$-cell grid is $\frac{k-1}k$. If $k\gt 3$, then this probability is 'opening-agnostic'; any initial square achieves this winning chance.

Proof: obviously, if the first cell chosen is the mine (at probability $\frac1k$) then the game is lost. Otherwise, if the initial cell chosen is bomb-adjacent (and thus reveals a 1) then choose a cell two or more units away from the initial cell (this is where the $k\gt 3$ condition comes in); this cell cannot be the mine (since we know that the mine is adjacent to the initial cell), and the resulting exposure will reveal on which side of the initial choice the mine lies. (Note that in the $k=3$ case then choosing a corner still wins with probability $\frac23$, but the middle choice only wins with probability $\frac13$.)

• The probability that the 'leftmost' of two mines is on cell $k$ in an $n$-element grid is $\frac{2(n-k)}{n(n-1)}$.

Proof: this is just the product of the (independent) probability that there is a mine on cell $k$ (i.e., $\frac2n$) with the probability that the other mine is in the $n-k$ cells to the right of cell $k$ (i.e., $\frac{n-k}{n-1}$ — note that there are only $n-1$ available cells for it, not $n$).

Now, this is enough to calculate the probability of winning the two-mine game with the corner strategy. We'll instead calculate the losing probability: suppose the leftmost of the two mines is in position $k$ (with probability $\frac{2(n-k)}{n(n-1)}$, as above). Then if $k=1$, the game is lost; likewise, if $k=n-1$ then the game is won. Otherwise, the right mine is (uniformly) among the $n-k$ cells to the right of that position, and so effectively it's now a one-mine game, with a losing probability of $\frac{1}{n-k}$. Now we can calculate the overall losing probability $P(n)$: $$ \begin{align} P &=\frac2n+\sum_{k=2}^{n-2} \frac{2(n-k)}{n(n-1)}\cdot\frac{1}{n-k}\\ &=\frac2n+\sum_{k=2}^{n-2}\frac{2}{n(n-1)} \\ &=\frac2n+\frac{2(n-3)}{n(n-1)} \\ &=\frac{2(n-1)}{n(n-1)}+\frac{2(n-3)}{n(n-1)} \\ &=\frac{2\bigl((n-1)+(n-3)\bigr)}{n(n-1)} \\ &=\frac{4(n-2)}{n(n-1)} \\ \end{align} $$

The analysis of the 'play in the center' case is similar, but much more complicated. For convenience's sake, I'm going to choose $n$ odd, so that we have an exact center, and write $n=2m+1$; thus, there are $m$ cells on either side of the first-move cell. Furthermore, instead of speaking in terms of probabilities I'll speak in terms of positions — with the assumption that there are $n(n-1) = 2m(2m+1)$ total positions (that is, the mines are labeled, i.e. distinguishable). Again, we'll calculate losing positions:

• There are $2(n-1) = 2(2m)$ positions where the first move loses outright (either mine A or mine B can be hit, and the other can be in $n-1$ different positions).
• There are $2(m-1)^2$ positions where the first move wins outright when the two mines are to either side of the center but not adjacent to it.
• There are an additional $2$ positions where the first move wins outright when the two mines are to either side of the center and are adjacent to it.
• There are $2\cdot2\cdot (n-3) = 8\cdot (m-1)$ positions where the first move reveals a 1: either of the mines can be on either side of the center square, and there are $(n-3)$ squares available for the other mine (the center square and the cells to either side of it are forbidden). This case may bear more analysis later (I suspect a strategy based on choosing a cell two away from the center may be more fruitful), but one strategy here is simply to select both corners (it should be obvious that selecting both can't hurt you over selecting one); this yields 8 total losing configurations (one of the two mines adjacent on one of the two squares next to the center, with the other mine in one of the two corners) with the rest winning.
• Finally, there are the configurations where both mines are on the same side and information is gained about it (i.e., the center square isn't adjacent to a mine, but we haven't won). These clearly reduce to a one-mine game (similar to the corner strategy) played to the 'far side' of whichever cell yields the one: for each $k$ from $3$ through $m-1$ (representing the valid places for the closer mine to be: $k=1$ is invalid, $k=2$ will always yield a winning strategy and $k=m$ has been covered in the previous case) we get $(k-1)$ positions for the other mine, one of which will be lethal for the one-mine strategy; since either mine can be the closer one, and the two mines can be (together) on either side of the center, this yields $4(m-3)$ losing configurations overall.

Thus, we get a total losing-configuration count of $4m+8+4(m-3) = 8m-4 = 4(n-2)$, and exactly as in the corner case, a probability of $\frac{4(n-2)}{n(n-1)}$ of losing the game.

This strongly suggests that the 2-mine strategy is equally as opening-agnostic as the one-mine strategy; I haven't worked through the possible alternate strategy in the case where the opening move reveals a 1, but it's certainly plausible that that yields no improvement over the 'both-corners' strategy. At the very least, it's clear that the 'open in the center' strategy does no worse than the 'open in the corner' strategy.