Algorithms
Raiting:
5

Advanced tactics of the game in "Sapper"


[A Friday translation of the 1999 article by one of the authors of the Thief game engine, Sean Barrett]
Unpleasant situation in "Sapper"
In this situation, I know that there are a lot of mines around me, but I can not determine where they are. Several mines can be in one of two places (pink or blue), a group of mines can be located in one of two combinations (light / dark green). In addition, there is still a difficult situation with "5" and "6" in the upper left corner, which I did not single out.

image
Blue / pink - mutually exclusive pair, light / dark green - mutually exclusive group
"Sapper": logic or probability
In "Sapper" you can play in two ways: as a logical or probabilistic game.

Technically, probability implies logic. If you can logically prove that the mine must be in a certain place, then the probability is 100%. If you can prove that it is not in this place, then the probability is 0%. That is, in a sense, only probabilities are important to us. However, the player uses logical deduction to recognize such 100% situations. Sometimes, especially at low levels of complexity, it is enough to pass a level, no calculation of probabilities is required.

But there are situations when the whole logic of the world can not save you. A simple example is the situation with the "T", which can be seen down the center. It is slightly complicated by additional neighboring mines. (In the simplest case, "2" is replaced by "1", and "5" - by "3", so that the situation is symmetrical.)

There is no no way to get more information about the probable position of one mine left in one of these cells. Chances are fifty to fifty - you can throw a coin. When you get something like that, it's better to immediately make a choice and not postpone for later. If the guess is wrong, then at least you will save time for solving the rest of the field. (But personally, I strive for completeness, so I leave such cases for later.) And do not blame yourself for not guessed. When victory or loss depends on the coin toss, this is a bad game design.)
Tactics at the end of the game
In the endgame you can use a very simple tactic - to count the number of remaining mines. Let's say I decided everything except the bottom right of the field. There can only be two configurations of mines corresponding to the data:

image
Possible configurations of mines in the lower right corner

If you get this position and the counter says that there are only two mines left, then the answer is ready: it should be a B configuration.

If the counter says that there are three mines left, then this is not necessarily a A configuration. This can be a B scheme with the remaining mine in one of the lower right 3 × 3 cell groups.

In fact, the chances are in favor of the configuration B .
Local Probabilities
If you examine probabilities only "locally", you see that each of the cells in the marked mutually exclusive groups has a 50-50 chance of being a mine. Speaking "locally", I mean that if there are "1" next to two unknown cells, then the probability of a hidden mine in each of them is 50%.

It is this situation that formed below in the center: each of the adjacent cells adjacent to an unknown pair contains exactly one mine, that is, each of the neighboring fragments of data assumes a 50 percent probability. In the upper left corner is a similar situation:

image
With absolute accuracy in each of the pink ovals, there is one mine, that is, there are only 7 min left

The situation in the lower right corner is also somewhat similar: next to each of the numbers on the "border" is one mine and two cells in which it can be.

If next to the cell there is one hidden mine, but three closed cells, then the probability of a mine in each of the cells is 33%; each of the four closed cells has a probability of 25%. If we have two hidden mines and three closed cells, then each cell has a probability of 66%.

Here's the situation with the "local probability" for the entire field:

image

As you can see, several cells in the upper left region have several probabilities; closed cell next to "2" and "6" and one next to "3" and "5". (The cell next to "5" and "6" thanks to them still has a probability of 66%, so there is no apparent inconsistency.)
Conflict resolution of local probability
You probably wonder what the presence of conflicting local probabilities means. Intuition may suggest that the greatest probability is to win. For example, the cell between "6" and "2" should actually have 66%. This will mean that in the extreme left cell, with a probability of 50%, it is actually 33%. Or you can try somehow to combine priorities: perhaps, the probability will be 5/6 or the average value.

But none of this is really wrong. The data from which the probabilities are obtained are not independent of each other, so no straightforward mathematical calculations will be correct. The reason for the correctness of the local guess about 50% down in the center is that it is really independent of anything else. If we accidentally recreate the field according to the data already available to us, then exactly half of the models of the mine will be in one of the two cells. (Probability sometimes confuses people who can not figure out which probability calculation rules are applicable in a particular situation.This approach is guaranteed the right way because it is based on the definition of probability in statistical prediction: the calculation is performed by measuring in all possible configurations that could lead to the current situation, while all of them are considered equally probable.)

That is, for correct measurements in the situation in the upper left corner, you need to consider all possible configurations of mines that satisfy already collected data, and then calculate what percentage of them contains a mine in the right position.

A direct calculation would require a lot of time. Fortunately, there are other ways.
Counting configurations
The abstract way of calculating probabilities is to bypass all possible configurations of mines, discard configurations that do not meet the collected data, and calculate statistics for each of the possible positions.

A more practical approach is to consider only those options that can not be discarded. For this we need to apply logic and generate all possible situations that can correspond to the available data. I have already shown two options for the lower right corner, but the probabilities for the upper left:

image
Possible configurations for the top left corner

(As before, an oval two cells high indicates that a mine can equally be in any cell, I could list each of these two cases separately, that is, there would be 10 configurations, but there is no use for this for us Table structure: two rows (numbered "1" and "2") differ in the position of the mine in the fourth row.The three columns are characterized by the position of mines in the second row.)

Now there is a temptation to exclaim: "Yeah, here are five cases, so we can count the number of cases for each of the possible positions of the mine." For example, the mine is in the fourth row (next to the lower left "1") is on the left in the top two cases, and on the right in the three lower cases. Therefore, you can decide that it has a 60% probability to be on the right, next to "6". (This is a position with conflicting local probabilities of 50% and 66%.)

However, we are missing one subtlety - the number of mines is in some cases different: in A1 six mines, in B2 - four, and five in all other cases.
Count the mines that have not been found
For a detailed study of this subtlety, let's return to a simpler situation in the lower right corner.

image
Possible configurations with the lower right corner

Suppose that I have already opened the rest of the field and I know that there are exactly three mines left.

There is a temptation to assume that the most likely configuration is A with exactly three mines. But this is not true.

Another temptation is to remember how many mines and how many cells there were, and say: "what are the chances that the lower 3x3 area will be empty." This is also incorrect. It's very difficult to explain why this is a mistake, it probably can be compared with with the Monti Hall paradox . However, it suffices to say that in reality the chances in this situation do not depend on the total number of mines and the size of the field.

The correct answer is: how many possible configurations of three mines correspond to our knowledge of the field? From the figure, we see that there are two: configurations A and B . But there are only two mines in B . The third mine can be in any of the cells of the lower region of 3x3, about which we have not yet collected any data. That is, there are only nine variants of B configurations, I just did not start to represent them all.

Consequently, there are only ten possible configurations. Each of the ten configurations is equally probable. (As I mentioned earlier, this is critically important for understanding the probability.The chances that the computer generated either of these options are small, but they are equally small, because the computer [as far as we know] gave each configurations equal chances You with equal probability can throw out the configuration of ten "eagles" in a row and the sequence two "eagles", one "tails", one "eagle", three "tails", one "eagle" , one "tails" and one "eagle" , it is more likely to throw out in total five "eagles" and five "sieves", but not a specific sequence "eagles" and "sieves." In "Sapper" we deal with configurations mines, which are similar to the sequence of coin tosses.)

Since each of the ten configurations (nine for B , one for A ) is equally likely, the configuration B in this case has a probability of 90%!

If there were four mines at this stage, then the configuration A would have nine options. The B configuration would have one option for each location of the two mines in the lower left corner; this is C (9,2) , that is, 9 / ((9-2)! * 2!) or 9 * 8/2, equal to 36. In this case the configuration of B would have a probability of only 75%.

With five mines, the A configuration would have 36 options, and the configuration B - 9 * 8 * 7/6 = 84 options; that is, the odds of B would be slightly more than 66%.

In the case of six mines, B would have a probability of 60%. With seven mines, B would have only 50%. With eight mines, B would be less than likely than A; In this case, the number of mines in the remaining positions of the configurations becomes smaller. Consider the worst case, when there are 11 minutes left. (The chance of this is extremely small, but if such a situation arises, then these probabilities apply.) In the configuration B , in all closed cells there will be mines in the configuration A in all but one. That is, there are 9 options for A and only one for B.
Final Solution
We have nine minutes left on the field. One of them is in the central lower area, and its position is completely independent, so you can ignore it. That is, we consider the whole field, except this case: not found just eight minutes. (To avoid confusion, I will continue to explicitly count the oval in the upper left corner, because this is the image of the upper left corner.)

Any combination of the left upper and right lower configurations can occur, with the exception of one of them (A1 + A), which will take nine minutes. Therefore, we must list each of these possible configurations and count the remaining mines and closed cells.

In fact, the number of closed cells is independent: there are nine of them in the lower right corner and three in the upper left, that is, only 12.
Top left Below right Number of mines Remaining min Closed options
A1 B 8 0 1
B1 A 8 0 1
B1 B 7 1 12
A2 A 8 0 1
A2 B 7 1 12
B2 A 7 1 12
B2 B 6 2 66
C2 A 8 0 1
C2 B 7 1 12
Thus, there are 118 possible combinations. Based on this, we can independently calculate the number of combinations for each of the left upper and lower right configurations:
Configuration Variants Percent
A1 1 1
B1 13 11
A2 13 11
B2 78 66
C2 13 11
A 15 13
B 103 87
Next, I went around each cell on the field and calculated its probability, summarizing the number of probabilities in which it appears, and dividing by 118. (In fact, just adding the above percentages.) In addition, on average, in each of the closed cells there is a mine in 15 out of 118 options (that is, the chances that there is a mine in at least one closed cell are very high). [This can be calculated by multiplying the number of remaining mines by the closed variants, which gives us the average number of mines in closed cells.]

image
The likelihood of having a mine

(It should be noted that this does not show all available information, for example, we know that the probabilities of two dark green cells with 87% are related - if one is true, then the other one too, and blue 13% cells , in which there are mines according to the configuration A , are also connected.The other blue 13% cells are not connected.If there is a mine in one of them, the probability that there is a mine in any of the remaining ones decreases.)
Playing the game
Most likely, playing in "Sapper", you do not want to pore over all these calculations.

And me too.

But I really listed all possible configurations in the left upper and lower right corners. I noticed that in one configuration ( B2-B ) is used one minute less than in all others, and applied the time-tested rule "less mines means more closed options" (which is valid for about the number of closed cells is less than twice the number of unidentified mines). This means that it is much more likely to have a configuration with fewer mines.

Since there were a lot of configurations in the upper left corner, it is quite difficult to determine the chances for any cell. So I just found out that the B configuration in the lower right corner is much more likely, and randomly chose one of the suitable cells. (I was hoping that she would let me finish the bottom right corner, and then, armed with more information about the number of remaining mines, I would be able to complete the top left corner, after which I would have to throw a coin for selection at the bottom in the center. Of course, ideally, the cell maximizing the probability of obtaining useful information, but any of these guesses would allow me to "enter" the lower right corner for further data collection.) The chances were higher for the B configuration, so I chose a cell in which there was a mine in the configuration <b> A < / b>.

image

Eight times out of nine, I would be right.
KlauS 25 september 2017, 7:07
Vote for this post
Bring it to the Main Page
 

Comments

Leave a Reply

B
I
U
S
Help
Avaible tags
  • <b>...</b>highlighting important text on the page in bold
  • <i>..</i>highlighting important text on the page in italic
  • <u>...</u>allocated with tag <u> text shownas underlined
  • <s>...</s>allocated with tag <s> text shown as strikethrough
  • <sup>...</sup>, <sub>...</sub>text in the tag <sup> appears as a superscript, <sub> - subscript
  • <blockquote>...</blockquote>For  highlight citation, use the tag <blockquote>
  • <code lang="lang">...</code>highlighting the program code (supported by bash, cpp, cs, css, xml, html, java, javascript, lisp, lua, php, perl, python, ruby, sql, scala, text)
  • <a href="http://...">...</a>link, specify the desired Internet address in the href attribute
  • <img src="http://..." alt="text" />specify the full path of image in the src attribute