Meditations on probabilty, predetermination and luck

Started by
9 comments, last by Daerax 18 years, 11 months ago
In Expert mode, Minesweeper presents you with a 30x16 game field (480 slots), 99 of which contain mines. A brute force approach tells us that, (with the exception of edge slots) given that each slot can have up to 8 adjacent mines with the mean being around 3, the probability of solving an Expert game without using deductive logic approaches zero quite oh so infinitely. Let's use this knowledge to make some simple deductions: 1) by recognizing patterns in the placement of mines in relation to squares that are known to not contain mines, we can substantially increase the probability of being able to solve the Expert game 2) by presuming that our first guess always hits a slot that doesn't contain a mine (always the case in Minesweeper), we can further increase this probability. However, to translate this into a real life situation, we can't presume that - IRL this may lead to a butterfly effect (read on) or something similar 3) by avoiding guesswork, we can minimize the probability of hitting a mine 4) by minimizing guesswork, we can also minimize entropy on the game field (in the closed system) Armed with such knowledge, let's transfer this into a real life situation with a real life example: you are about leave for the airport to board a direct flight from London to NY. Your single aim is to reach the destination safely and on time - to do that, you need to make a series of decisions that would guarantee your duly arrival. Let's look at the above brute force example: if you were to leave your house symbolically blindfolded and ears filled with motor oil, then the chances of your reaching New York pretty much start to approach zero after you've been walking for two minutes. By recognizing some simple patterns, starting with things like "look to your left first, then to your right when crossing a street", you can increase this probability drastically. By eliminating guesswork, such as which route to take, before you leave (for instance, would it be quicker to take a chance and take the fictional A5 straight to the airport, or drive 2 miles along the fictional A17 and then take the safe bet - the offroad approach - with the risk of being snowed in?) you can start to make estimates. After you've taken the route to the airport to NY every Tuesday for two years, you'll be able to use rock solid empiric observation without any doubt to estimate within a couple of minutes the time it would take you to reach the destination or any of the "checkpoints" along the way. The only difference is that, this knowledge has actually been formed by recognizing more and more patterns: weather, road and traffic conditions, who the pilot is, what state the US international affairs are in, etc, and incorporating them into a customized, a very specific pattern that is precisely tailored (by yourself) to suit your needs. By shifting this "pattern of patterns" by a marginal amount you can easily offset the balance in the system in such a way that it will never be regained. This would lead to a butterfly effect, with the result being that you will not reach NY on time (or at all, in case you happen to get killed when you hurry across a busy street). While all of this may seem very natural and rational, it's weird how people disregard their ability to form such "sequential systems of patterns" - most people get up at a fixed time almost every morning, take a shower that lasts exactly n minutes, drink their coffee in m minutes and make it to the bus stop at exactly 8:27 AM. That is a pattern - in a way a predetermined pattern, unless it is offset by another pattern that interleaves this particular pattern, in which case we need to do some guesswork. The question is: why do some people always guess wrong, some people always guess correctly while most people seem to be at the tip of the Gaussian distribution (guessing correctly half of the time and wrong the other half of the time)? Humanity has coined the term luck to describe this phenomenon (apparently, according to the saying, in case you're Irish, then you have quite a bit better chances of reaching NY on time every Tuesday 40 years in a row than if you were, say, a Peruan). Or let me put it this way: why can some people finish an Expert game in Minesweeper 90% of the time they start one while some fail on a regular basis (such as myself)? Why is that? Is it that some people come with an incredibly better intuitive knack of being able to recognize vital links in potentially dynamically changing patterns while some could stare at a flock of pigeons manually switchable street light for their entire lives and die a starving death because their research went nowhere brains just couldn't grasp the "pattern"? If, so then why isn't "pattern recognition" being taught in grade school? After all, as it would seem, a gift in this would be a definitive weapon against the otherwise cruel and unsubjective world. Just a little something I thought of while playing Minesweeper...
"Literally, it means that Bob is everything you can think of, but not dead; i.e., Bob is a purple-spotted, yellow-striped bumblebee/dragon/pterodactyl hybrid with a voracious addiction to Twix candy bars, but not dead."- kSquared
Advertisement
Kinda low reader activity in this thread...
"Literally, it means that Bob is everything you can think of, but not dead; i.e., Bob is a purple-spotted, yellow-striped bumblebee/dragon/pterodactyl hybrid with a voracious addiction to Twix candy bars, but not dead."- kSquared
Just so you know, Minesweeper is NP complete. I don't know how this was proved or anything, but I was in the math building one day going to a session, and there was clearly a picture of mine sweeper on a whiteboard with some half erased equations and the underlined writing, "Minesweeper is NP complete".
SlimDX | Ventspace Blog | Twitter | Diverse teams make better games. I am currently hiring capable C++ engine developers in Baltimore, MD.
I can solve expert minesweeper most of the time if I really concentrate. Unfortunately I normally listen to music or am distracted and thus blunder.
after the first few clicks, it's mostly just a matter of paying attention. i thought i was good when i solved expert in 500 seconds, until i watched a friend doing it in 300, while he was talking to me ;-)

anyway, let's get philosphical :-P
i think everything happens as a reaction to what has happened before. everything we regard as "random" is just not knowing all the factors. this relates to minesweeper as well as to brain activity (aka thoughts) or quantum physics. so if you KNOW the current state the universe is in, you can tell EXACTLY what will happen. luckily we don't know, so life still holds some mysteries for us to wonder about ;-)


edit: what i tried to say was that everything is a pattern. of course, most of it is (and probably always will be) incomprehendable by humans, but on a small scale (like recognizing the "pattern" of the OP's route) it's perfectly feasible, although some people seem to be more apt than others...
You're all talking balderdash.
Quote:Original post by Promit
Just so you know, Minesweeper is NP complete. I don't know how this was proved or anything, but I was in the math building one day going to a session, and there was clearly a picture of mine sweeper on a whiteboard with some half erased equations and the underlined writing, "Minesweeper is NP complete".


Indeed, Minesweeper is NP complete, now, the more important question is doees NP equivocate to P?
Quote:Original post by Daerax
Quote:Original post by Promit
Just so you know, Minesweeper is NP complete. I don't know how this was proved or anything, but I was in the math building one day going to a session, and there was clearly a picture of mine sweeper on a whiteboard with some half erased equations and the underlined writing, "Minesweeper is NP complete".


Indeed, Minesweeper is NP complete, now, the more important question is doees NP equivocate to P?

The real question, will they pay to somebody who will prove that _average_ solution complexity is P ?

(Or maybe that average complexity of ideal gameplay is P. Where gameplay continues until there's either solution or we explode at necessary guess(when making ideal guess))

It will be proof for minesweeper only, indeed, and probably they'll refuse to pay on grounds that it doesn't answer "P=NP ?" question.

[Edited by - Dmytry on April 28, 2005 2:33:36 PM]
Quote:Original post by Dmytry
Quote:Original post by Daerax
Quote:Original post by Promit
Just so you know, Minesweeper is NP complete. I don't know how this was proved or anything, but I was in the math building one day going to a session, and there was clearly a picture of mine sweeper on a whiteboard with some half erased equations and the underlined writing, "Minesweeper is NP complete".


Indeed, Minesweeper is NP complete, now, the more important question is doees NP equivocate to P?

will they pay to somebody who will prove that _average_ time complexity is P ?
It will be proof for minesweeper only, indeed, and probably they'll refuse to pay on grounds that it doesn't answer "P=NP ?" question.


lol, do you have something in mind Dmytry? No I dont think they would pay you for precisely the reason you stated, such a special case proof would ofcourse not have been applied on a NP complete problem but rather a reduced special case of one. As you said one could not generalize such a result to a NP complete and thus all NP complete problems. Since P = NP? remains unresolved there is no money for you :P.

On a sidenote how would you go about proving complexity for average time in minesweeper is P?
Quote:Original post by Daerax
Quote:Original post by Dmytry
Quote:Original post by Daerax
Quote:Original post by Promit
Just so you know, Minesweeper is NP complete. I don't know how this was proved or anything, but I was in the math building one day going to a session, and there was clearly a picture of mine sweeper on a whiteboard with some half erased equations and the underlined writing, "Minesweeper is NP complete".


Indeed, Minesweeper is NP complete, now, the more important question is doees NP equivocate to P?

will they pay to somebody who will prove that _average_ time complexity is P ?
It will be proof for minesweeper only, indeed, and probably they'll refuse to pay on grounds that it doesn't answer "P=NP ?" question.


lol, do you have something in mind Dmytry? No I dont think they would pay you for precisely the reason you stated, such a special case proof would ofcourse not have been applied on a NP complete problem but rather a reduced special case of one. As you said one could not generalize such a result to a NP complete and thus all NP complete problems. Since P = NP? remains unresolved there is no money for you :P.

It would be fair not to pay if they would explicitly state that it's for worst case complexity.

As about "P=NP ?", I think prize for solution must be some tens millions at least, or even billion $.

[By solving I mean proving that "P=NP" is true(unlikely), or proving that "P=NP" is false. Or that proof satisfying requirements enclosed in brackets is impossible.]
note: this sentence have subtle meaning. Think about it.[grin]

Quote:

On a sidenote how would you go about proving complexity for average time in minesweeper is P?


I were thinking about something like that: first, make/find algorithm, and name it "SomeUsualAlgo". (It must work ideally, and have defined worst case complexity.)
How SomeUsualAlgo should work: it should try to solve it. When it is found that guess is unavoidable, it makes guess. Below, by "game" I mean some specific board with some specific placement of mines and some specific set of ideal guesses made until it is solved or losed. "NxM games" stands for games on NxM board.

Let SomeUsualAlgo have worst case complexity less than exp(a*N*M). (should be true for almost all algorithms)

Let simple_games(N,M) it's number of all NxM games that are solved/losed by SomeUsualAlgo in less than P(N*M) and we can prove that (P may be (N*M)^1000 or something similar :-).
complex_games(N,M) is > number of all other NxM games.

If ratio complex_games(N,M)/(complex_games(N,M)+simple_games(N,M)) is smaller than exp(-a*N*M) , SomeUsualAlgo will have polynomial avg. timecomplexity.
That's because we get average smaller than
exp(a*N*M)*complex_games(N,M)/(complex_games(N,M)+simple_games(N,M)) + P(N*M)*simple_games(N,M)/(complex_games(N,M)+simple_games(N,M))

(and we get first term-->0 as N,M grows)

All equations of course must hold true just for all N>A,M>B (where A and B is some finite numbers.)

If it will not work, I may need to make some nicer upper-bounds for complexity, or even find proof that avgerage is NP-complete too (but I doubt it is.).

(Also, it may be necessary to take into account number of guesses and resulting exponentially decreasing probability of susvival till guess N. Or it might be unnecessary)

This topic is closed to new replies.

Advertisement