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 da-> http://nothings.org/games/minesweeper/ angucken ach ja, some information: high score expert-mode 24.12.06: 123,491 sec los gehts: ## Minesweeper: Advanced Tactics## A Nasty Minesweeper PositionIn 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 ProbabilityMinesweeper 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 ## An Endgame TacticOne 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 If the counter says there are three left, it's not necessarily position In fact, the odds are in favor of it being ## Local ProbabilitiesIf 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 ConflictsYou 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 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. ## Counting ArrangementsThe 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 ## Counting Unencountered MinesLet'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 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 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 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 Since each of the ten arrangements (nine for If there were four mines left at this point, then configuration B is only 75% likely. With five mines, configuration With six mines, ## A Final SolutionIn 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 ## Playing the GameOdds 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 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 Eight times out of nine, I would have been right. |