minesweeper - ein tolles spiel!
dies ich sag euch hier - selbst, wenn ihr mich dafür gerade belächelt
...weil ihr denkt, dass das spiel nach dem zufallsprinzip geht - aber das tut es nicht!
der unten aufgeführte text (den ich im übrigen in einer lateinstunde komplett durchgearbeitet habe ) wird euch dies beweisen können.
um die bilder sehen zu können müsst ihr euch das ganze
ach ja, some information: high score expert-mode 24.12.06: 123,491 sec
Minesweeper: Advanced Tactics
A Nasty Minesweeper Position
In this position, I know about a bunch of mines on all the remaining fronts, but I can't quite determine where they are. There are a few mines that might be in one of two positions (red or blue), a cluster of mines that might be in one of two arrangements (green), and a more complex situation in the top left which I haven't marked explicitly, involving the '5' and the '6'.
Minesweeper: Logic or Probability
Minesweeper can be played two ways: as a game of logic or as a game of probability.
Technically, probability subsumes logic. If you can logically prove a mine must be in a location, its probability must be 100%; if you can prove one cannot be, its probability must be 0%. So probability is all you need, in some sense. Nonetheless, you use logical deduction to detect those 100% situations; sometimes, especially at easier difficulty levels, that's all you need to complete a Minesweeper game; no appeal to probabilities is necessary.
But there are definitely situations where all the logic in the world won't save you. The 'T' situation which appears in the bottom center of the game board above is a simple example of this--slightly complicated by the extra nearby mines. (The simplest scenario replaces the '2' with a '1' and the '5' with a '3', so that it is symmetric.)
There is no way of getting any further information about the likely location of the one mine that remains in these two spaces. It's a 50-50 chance--a toss of a coin. When you find something like this, you're probably better off taking a guess right away, rather than saving it for later--so if you guess wrong, you won't have wasted a lot of extra time solving the rest of the board. (I'm a completist, so I save it for last, and don't blame myself for guessing wrong. And, mind you, it's a bad game design that puts the win or loss of the game on the toss of a coin.)
An Endgame Tactic
One very easy endgame tactic you can use is counting the number of remaining mines. Suppose I had resolved everything but the bottom right section of the board. Here are the only two configurations of mines that match the data:
If you reach this position and the counter says there are only two mines left, you're done; it must be position B.
If the counter says there are three left, it's not necessarily position A, though. It could be position B with the remaining mine in one of the lower-right 3x3 cluster of squares.
In fact, the odds are in favor of it being B.
If you only examine the probabilities "locally", you can see that each of the squares in the marked mutually exclusive groups have a 50-50 chance of being a mine. By locally, I mean that if you have a '1' next to two unknown squares, each has a 50% chance of being a mine.
The bottom center situation is exactly like this: each of squares adjacent to the unknown pair has exactly one mine unaccounted for, so each adjacent piece of data suggests a 50% chance. The very top left is similar:
The bottom right situation is somewhat like this as well; each of the numbers on the "front" has one mine unaccounted for and two squares where it might be.
If a square had one unaccounted-for mine next to it, but three unexplored squares, each square would have a probability of 33%; four unexplored squares would give each a 25% chance of having a mine. If it had two unaccounted-for mines and three unexplored squares, each would have a probability of 66%.
Here's the "local probability" situation for the full board:
As you can see, several squares in the top left area have more than one probability; the unexplored square adjacent to the '2' & '6' and the one adjacent to the '3' and the '5'. (The one by the '5' and the '6' still has 66% due to both, so there's no apparent incompatibility.)
Resolving Local Probability Conflicts
You should be wondering at this point what it means to have conflicting local probabilities. One intuition is that the bigger probability should win. For example, the square between the 6 and the 2 must really be 66%. That would mean the leftmost square that's assigned a 50% is actually only 33%, though. Or you might think you combine the priorities somehow; perhaps the chance should be 5/6, or the average.
But none of these are really correct. The data the probabilities are derived from aren't independent of one another, so no direct mathematics on the probabilities is valid. The reason a local guess of 50% is correct in the bottom center is because it really is independent of anything else. If you randomly constructed boards which matched all the data collected so far, exactly half of them would have the mine in each of the two possible locations. (Probabilty sometimes confuses people, who have trouble knowing what rules of probability apply in what situation. This approach is essentially a guaranteed valid way, because it underlies the definition of probability as predictive statistics: measure across all possible arrangements that might have led to the current situation, assuming each was equally probable.)
Thus, the correct measurement for the top left situation involves looking through all possible arrangements of mines that meet the currently collected data, and measuring which percentage of them has a mine in the correct position.
This would be rather time consuming if we did it directly. Fortunately, there are better methods.
The abstract way of computing probabilities is to run through all possible arrangements of mines, discard the ones that don't match the data we've collected, and count up the statistics for each possible location.
A more practical approach is to only consider the ones that wouldn't get discarded at all. To do that, you have to apply logic and generate all of the possible situations that could match the current data. I already showed the two scenarios for the bottom right; here are the possibilities for the top left:
(As before, the double-height oval indicates that a mine could be in either position with equal probability. I might have listed each of these two cases separately, so there'd be 10 arrangements, but it won't turn out to be useful. As to the organization: the two rows (numbered '1' and '2') are distinguished by the position of the mine in the fourth row. The three columns are characterized by the position of the mines in the second row.)
Now, you might be tempted to simply say "aha, there are five cases, so we can count up the number of cases for each possible mine location". For example, the mine in the fourth row (by the lower-left '1') is to the left in the two cases in row 1, and to the right in the three cases in row 2. So you could attempt to argue that it has a 60% chance of being to the right, adjacent to the '6'. (This is a position that has conflicting local probabilities of 50% and 66%.)
However, this misses an important subtlety--the number of mines in different in some of the cases; there are 6 mines in A1, 4 mines in B2, and 5 in the other cases.
Counting Unencountered Mines
Let's return to the simpler bottom right scenario to explore this subtlety in detail.
Suppose that I've completed all of the rest of the board, and I know there are exactly three mines remaining.
One temptation might be to assume that configuration A, with exactly three mines, is more likely. This is incorrect.
Another temptation would be to consider how many total mines there were, and how many board squares, and to say "what are the odds that the bottom 3x3 region would be empty". This is incorrect. The exact reason why this is incorrect is complex to explain, and could perhaps be likened to the Let's-Make-a-Deal "paradox". Suffice it to say, however, that the actual odds for this situation are independent of the total number of mines and the total board size.
The real answer is this: how many possible arrangements of three mines are there that fit the knowledge I have of the board? The picture shows two: configuration A and configuration B. But B only has two mines. The third mine could be in any of the bottom 3-by-3 region of squares for which I haven't collected any data. There are thus nine variant B configurations; I just haven't gone to the effort of drawing them out.
Thus, there are ten possible arrangements. Each of these ten arrangements is equally likely to occur. (As mentioned before, this is the crucial notion to understanding probability. The odds of the computer having generated any of these cases the first place was small, but it was equally small, because the computer [as far as we know] was giving every arrangement an equal chance. You are equally likely to toss ten heads in a row as you are to throw the pattern two heads, one tails, one heads, three tails, one heads, one tails, one heads. You're more likely to throw a total of five heads and five tails than ten heads, but not any particular pattern of heads and tails. In Minesweeper, we're concerned with arrangements of mines, which are like patterns of coin tosses.)
Since each of the ten arrangements (nine for B, one for A) is equally likely to occur, configuration B is 90% likely in this particular scenario!
If there were four mines left at this point, then configuration A would have nine variants. Configuration B would have one variant for each arrangement of two mines in the bottom left corner; this is C(9,2), which is 9!/((9-2)! * 2!), or 9*8/2, which is 36. In this case, configuration B is only 75% likely.
With five mines, configuration A has 36 variants, and configuration B has 9*8*7/6 = 84 variants; so the odds for B are just over 66%.
With six mines, B is about 60% likely. With seven mines, B is only 50% likely. With eight mines, B is lesslikely than A; at this point, there are so many extra mines to go into the remaining locations that there are fewer configurations. Consider the worst case, where there are 11 mines remaining. (This is extremely unlikely to occur, but if it did occur, these probabilities would apply.) With configuration B, all the unencountered square must have a mine; with configuration A, all but one does--and thus there are 9 variants for A, and only one for B.
A Final Solution
In the actual board under discussion, there are 9 mines remaining. One of those goes to the bottom center, which has a totally independent choice that we can ignore. Therefore, we consider the full board except for that case; there are only eight mines unaccounted for. (I'll continue to explicitly count the oval in the top left since it's in the picture for the top left, just to be unambiguous.)
Any combination of a top-left configuration and a bottom-right configuration could occur, except one of them (A1 + A) which would require nine mines. Therefore, we have to enumerate each of these possible configurations, and count up the remaining mines and the unencountered squares.
Actually, the number of unencountered squares is independent: there are nine in the bottom right and three in the top left, so there are 12 total.
Thus, there are a total of 118 possible combinations. From this you can count the number of combinations for each of the top left and bottom right configurations independently:
Next, I went through each square on the board and computed its probability, by adding up the number of variants in which it appeared, dividing by 118. (Actually, by just adding the percentages above.) Also, on average each unencountered square had a mine in 15 of the 118 variants (after all, the odds that at least one unencountered square has a mine is very high). [This can be computed by multiplying the number of mines left by the unencountered variants, which tells you the average number of mines on unencountered squares.]
(Note that this doesn't show all of the information available. For example, we know that the probability of the the two dark green '87' squares are linked--if one is true, the other must be. Similarly, the three pale blue '13's that are mines for configuration A are also linked. The remaining pale blue '13's are not linked--rather, if any one were to be a mine, the odds of any of the remaining ones being mines decreases.)
Playing the Game
Odds are you're not going to want to sit down and work out all that math when you're playing a minesweeper game.
Neither did I.
I did enumerate the possible configurations in the top-left and bottom-right. I noticed that one configuration (B2-B) used one fewer mines than all the others. I applied the "fewer mines means more unencountered variants" rule of thumb (which applies roughly until the number of unencountered-squares is less than double the number of unaccounted-for mines), which means that configurations that use fewer mines are much more likely.
Since there were a lot of configurations in the top-left, determining the odds for any one square is somewhat complicated. Therefore, I just figured that configuration B in the bottom-right was a lot more likely, and guessed one of the appropriate squares. (I hoped that this would allow me to complete the bottom-right, and then armed with more knowledge about the number of mines remaining I could complete the top left, and I'd only be left with the center bottom coin toss. Of course, ideally I'd pick a square that will maximize the likelihood I'd get useful information, but any of these guesses would have allowed me "entry" into the bottom right corner for further data collection.) The odds favored configuration B, so I picked a square that had a mine for configuration A.
Eight times out of nine, I would have been right.