What are the other tips for mine-sweeping? You will never imagine how scientists play games

Sometimes, when I recall my childhood and youth, there always appears in front of me a blue sky and tender grassland, as well as the pleasant time I spent with my friends on it before...

Of course, don't think it's wrong

I mean this by blue sky and grass

In order to prevent being beaten, I chose to squat in advance for headshots

WindowsXP does carry a lot of memories, and the XP system is also really useful. Windows XP was officially released on August 24, 2001, and Microsoft stopped supporting Windows XP desktop version system on April 8, 2014. Until this Tuesday, April 9, 2019, the last batch of Windows XP running on embedded devices lost Microsoft's official support. XPs finally officially say goodbye to us. [1]

Classic mine-sweeping game

When it comes to XP, I have to say that the operating system comes with classic games such as minesweeping and cards, which are really classic, fun and time-consuming. If we can count the time spent by all mankind on this, it is probably an astronomical figure. . . However, although people have been playing minesweeping for a long time and have played a lot of times, I guess 99% of players have definitely never thought about why it is so easy to die when playing minesweeping by themselves. . .

Compare the speed of other people's children playing minesweeping

The picture is accelerated. If you want to see the fastest minesweeping record in the world at present, you can go to [2] to watch

Look at how you play minesweeping again...

It's almost this level. The thunder exploded just after clicking the minesweeping icon

Although XP has left us, luckily, the Win10 system can also directly search for "minesweeper" in the store to download the officially reset minesweeping game, and re-experience the previous classics.

Actually, many scientists also like to play the minesweeping game. However, if the average person dies quickly when playing minesweeping, he will keep reopening and reopening until he encounters a good start (and then dies quickly). Scientists are different. If they die quickly when playing minesweeping, they will not reopen. They will directly prove that "the probability of passing this game is 0."

Mine-sweeping has a long history after all, and there are a lot of papers that analyze the probability of solving mine-sweeping games. As a hand-rest minesweeper who is proficient in clicking the re-open button of minesweeping, today I will talk to you systematically about the story behind minesweeping.

Mine-sweeping secrets

Minesweeping cheat sheet

The martial arts in the world are invincible, but they can only be fast and cannot be broken!

From a mathematical point of view, mine-sweeping is equivalent to a process of constantly solving known conditions, just like an application problem that constantly increases conditions. You can confirm that the block is not a thunder by clicking the left button, and right button to mark the area you think is a thunder. If the piece you clicked is not a thunder, then it will tell you how many thunders are in the eight grids around this area. As long as you click fast enough, the thunder will not catch up with you.

Through a very simple counter-proof method, we can deduce where a large part of the thunder is located. [3]

Scenes on the corner

The so-called counter-proof method is to think about this problem in the opposite way. If there is such a concave corner, the inside is blank, but there is a 1 in the corner, then there will definitely be a thunder on this corner. Because if this place is not thunder, then the thunder referred to in the middle can only be wandering. . . Similarly, if there are 3 on one side, then the three next to 3 must be thunder. After all, the mine brothers cannot squeeze and move to a grid.

Scenarios when they are located in the border

In addition to this counter-proof method, there are many fixed "routines" in mine clearance. Learn this routine to ensure that your mine-sweeping skills will greatly increase and you will be among the top 500 mine-sweeping in the community.

It sounds like it's amazing

When clearing mines, you often encounter some fixed numbers, such as three consecutive numbers are 121. Without thinking, you can directly mark lightning in the opposite direction of 121 and 1. Or four consecutive numbers 1221, at this time, the opposite direction of the two 2 must also be thunder.

121 In the case of "1" on the left, there can only be one grey in the yellow area, but the 2 in the middle requires at least two greys, so the pink one must be a grey. Similarly, prove the other side

1221 In the case of "1221", the same as the above proof process, due to the limitation of 1, there can only be 1 grey in the yellow area, so the square opposite to the other 2 must be thunder.

"Editor, I have a question, what about 121221? According to the secret book, there are two thunders near the 1 in the middle?"

The secret that seems to be a problem?

"This situation is impossible! The three 1s on the left have covered all unknown spaces above, so there are only 3 mines. But the number of mines below is 1+2+2+1+2+1. With only 5 grids repeatedly counting in the middle, they all reach 7, which is twice as high as 3. So this kind of figure is impossible!"

Ahem, take back your ideas. As mentioned above, there are indeed some routines for mine clearance. Read this mine-sweeping secret every day. In time, the mine-sweeping skills will surely be successful.

Mine-sweeping or luck

Lucky or not, it's a question

You must accept playing minesweeping. This is a game that competes for character.

Although life is already so difficult, I still have to expose this ruthlessly. I guess you have mastered the tricks of mine-sweeping at this time, but sometimes you still have to face things like guessing thunder, and if you are not careful in one move, you will lose everything. . .

Guess how the yellow part of the thunder should be distributed?

The yellow part in the picture is a typical mine-sweeping problem that needs to be guessed. According to the numbers in the corner, we can only know that there must be only one thunder in the yellow part of 1×2, but we don’t know which one is thunder. If there is no other information, we worked hard on most of the chessboard, and the probability of passing this mine array in the end is still only 1/8.

This simple judgment is fine, but sometimes you will encounter some more obscure guesses.

Mine-sweeping Judgment Question

Suppose that we encountered such a pattern during the mine clearance process, it was indeed a matter of crying without tears. If you don’t know how to cry, you can prepare your tears first. The editor will tell you why you cry immediately. . . Starting from the left, assuming there is lightning in the first vacancy, then there is no lightning in the second vacancy, because there is 1 in the middle of the vacancy so there is lightning in the third vacancy, and so on. But if there is no lightning in the first vacancy, and there is lightning in the second vacancy, we can make sense. I'm going to step on a landmine, and it's still such a complicated problem, as for it? . .

Don't worry, there are more complicated things later. The situation of whether there is any lightning on x and the following number * is always the same, so this mine array is like a wire that transmits signals. On the mine-sweeping map, we can not only make such simple wires that transmit signals, but also realize the operation of logic gates in all electronic circuits. [4,5]

Non-gate circuit

OR gate circuit

These are two "simple" logic gates, which realize the NAG gate that flips the signal and the OR gate that operates the two signals respectively. In another famous sandbox game, Minecraft, players can also use the materials in the game, Redstone (actually, the annual update code for the Windows 10 operating system before this was named after Redstone), to achieve various complex logical operations. Some players even use Redstone to create computers that can truly run in Minecraft. . .

Redstone computer, with complete registers, adders and other components [6]

Forget it, I can't imagine what minesweeping will turn out. . .

It is very difficult to judge whether there is a solution or not.

Find solution

Back to the beginning of the article, if we are going to solve a mine-sweeping problem, if we are the ones who are the ones who are trying to solve the problem of mine sweeping, it is easy to die. So what if I leave this problem to a computer? Unfortunately, under normal circumstances, computers are still powerless to do anything about mine clearance. . .

Sad

Thankfully, under the smaller chessboard we usually play, the computer can also get answers through searching.

In order to understand several levels of difficulty in computer processing problems, it is necessary to first know a concept - polynomial time. For the same algorithm, the computer generally needs different time to calculate according to the size of the problem being processed. To use the most intuitive example, Xiao Ming has to wash clothes. He washes 1 piece of clothing for 2 minutes, washes 5 pieces of clothing for 10 minutes, washes 10 pieces of clothing for 20 minutes, and dealing with problems with the change of the scale of the problem is a linear relationship, a single polynomial. Now let's assume that Xiao Ming still has to wash clothes, but the clothes are quite special now. It takes 2 minutes to wash one piece of clothing, but the time for washing five pieces becomes 32 minutes, and the time for washing ten pieces becomes 1024 minutes. At this time, it is exponential, not polynomial anymore. Evaluating an algorithm, as the scale of the problem increases, how calculation time increases is a very important indicator.

In computers, we still think that polynomial level time is very fast. If the problem is classified according to the difficulty of solving, P refers to a problem that can be solved using polynomial time. As the saying goes, it is a problem that calculates quickly. NP refers to a question that may not necessarily be fast to calculate, but we can check any answer quickly. A complete problem of NP is an NP problem that is more difficult than all NP problems. Although people have a beautiful idea and always think that if they can check it quickly, they should find a way to make it quickly, but it is still an unknown number at present. . . [7]

Unfortunately, solving a solution to a minesweeping game is exactly a complete problem of NP - the most difficult category of problems that can easily verify whether the results are correct. So far, people have not found a solution algorithm for polynomial time, and usually only exponential or even factorial search algorithms are used to solve this type of problem.

Logic circuit used to display liquid crystal numbers. We can try one by one easily, but it is difficult on the other hand, especially when this logic circuit is very large

Mine-sweeping games are such a difficult problem. The reason lies in the previous chapter. Minesweeping games can be regarded as logic circuits for logic gates to perform calculations. Given a logic circuit, can the value of each input be determined if the output result is known? This problem, known as the SAT problem, is the first problem in the world to prove that it is NP-complete. [8] This kind of problem is very easy to verify. You just need to substitute the result into the logic circuit and you can immediately know whether it meets the requirements, but in reverse, you want to calculate the output that meets the result.It's extremely troublesome to enter.

Solving the results of mine-sweeping games and using those constructed logic gates is exactly equivalent to solving SAT problems. [9]

Mine-clearing is also related to infiltration

Precolation

Liquid, picture from Giphy, Michael Shillingburg

In fact, we find it difficult when playing minesweeping games, but there is another reason. This reason has something to do with physical penetration.

In the 1960s, scientists [10] discovered that when fluid flows through porous media, the hollows in the media are always blocked, which sometimes affects the flow of fluid. What is even more strange is that when the proportion of pores of these porous media is gradually increased and reaches a certain value, the fluid that can flow at the beginning is suddenly completely blocked. When the probability of the hole being randomly blocked changes, a mutation occurs in the ratio of liquid flowing through it.

This phenomenon is called precollation. [11]

In this case, how should you do it

In mine sweeping, similar percolation phenomenon also exists. When the mine density in a game is particularly low, we just click it casually, and we won’t click the mine, but click the big gap, and solve the problem in an instant. However, after the local mine density increases, after it increases to a certain level, even if we analyze rationally and never guess blindly, it is impossible to get the mine clearance problem right.

For different board sizes, someone calculated the probability of winning under different mine densities. The corresponding curve of the triangle is primary 8×8, the square is 15×13, the diamond is advanced, and 30×16. Whether the solution here actually does not include the probability of stepping on the mine when you click on the first random click. [12]

If we abstract the model of fluid passing through porous media, it actually corresponds to point percolation, that is, imagine the entire medium as a network, and when the fluid passes through each grid, there is a probability that p may pass through. If a grid that cannot flow through is connected into pieces in the network, the fluid cannot flow through.

Not strictly speaking, solving the mine-sweeping problem is actually very similar to the percolation model. The process of our solution is actually like a bulldozer, constantly using existing knowledge to advance the known area layer by layer to the outside. If the density of lightning is greater in the game, the more likely it is that the part of the solution is separated by lightning, and the mine density and percolation parameters play the same role. If it is separated so that the entire board cannot be connected, then it is impossible to continue to reason. For more stringent proofs, please refer to Elchanan Mossel's paper. [13]

Buldozer, pictures from the Internet

As the grid continues to grow, the middle part of this winning rate curve also becomesAs the mine-sweeping problem is getting steeper, the problem of mine-sweeping is becoming more and more extreme: either it cannot be solved at all, or it can be solved easily. In advanced mode, the mine density has actually reached 99/480=0.2, and the probability of solving it is less than 1/4. This is not considered a mistake in hand shaking, and it is not easy to restart at the beginning, which is really not friendly.

Conclusion

Conclusion

emoji version mine sweeping [14]

Believe those who see this

I must have been eager to try and play minesweeping

I believe you

Nothing is difficult in the world, as long as you are willing to give up

Uninstall is OK