Minesweeper = Secret to all happiness?

Colleges and Universities A-Z Massachusetts Institute of Technology
1

<p>Here's my harebrained hypothesis:</p>

<p>Imagine the following Minesweeper board:</p>

<p>1 1 2 2 _</p>

<hr>

<p>Now, solving such a board is an NP-complete problem. However, a human can solve it easily:</p>

<p>1 1 2 2 _
_ _ _ _ _</p>

<p>At least ONE of the two red spaces has to be a mine. Therefore, the one on the far left CANNOT be a mine.</p>

<p>Humans can use this "in any case" reasoning very effectively, solving such problems in what seems to be polynomial time.</p>

<p>Now, if this is true, then at least one of the following MUST be true:
Humans are non-deterministic, or
P = NP</p>

<p>Thoughts? Comments? Fallacies?</p>

2

<p>i think you play too much, but thats not a bad thing</p>

3

<p>Actually, I don't...I stink at Minesweeper...I've never once beaten Expert...</p>

<p>However, one of my CS assignments at Harvey Mudd was to write Minesweeper, and I wrote an autoplay program to go with it for extra credit.</p>

<p><a href="http://www.csupomona.edu/%7Etknguyen/tkn/andy/%5B/url%5D"&gt;http://www.csupomona.edu/~tknguyen/tkn/andy/&lt;/a>
Click on Bonussweeper, towards the bottom. Read the instructions first.</p>

4

<p>uhh that's not very clear logic? the reason that you can claim that the two red underlined spaces have mines is because you enumerated all the possible mine locations in your head, and then cancelled out the ones that didn't pass the minesweeper test...</p>

<p>actually the fact that "minesweeper is NP-complete" isn't as straightforward as you think--if you generalize minesweeper to a graph where every square is a vertex and is connected to adjacent squares/vertices via edges, then the problem becomes phrased as this:</p>

<p>given a graph G with numbers at every vertex, does there exist an assignment of mines to the vertices such that the numbers at each node are satisfied?</p>

<p>edit: you also seemed to have misunderstood the notion of NP. It means that the best algorithm we have to solve the problem is a brute-force search of the solution space, not that it's unsolvable! So if I give you a problem of size N where N = 10000000, and it's in NP, then it's basically unsolvable. But if I give you an NP problem of size N = 2, chances are you can solve it pretty damn quickly.</p>

5

<p>hey tanoev whats your record on the asteriod game...mines 18200</p>

6

<p>"hey tanoev whats your record on the asteriod game...mines 18200"</p>

<p>Old version (shoot with Shift): 40000ish on my computer, 100000ish on a really slow computer
New version (posted 1/2 weeks ago; no shoot with Shift, but can turn and go forward at the same time): 40000ish (the program is now fixed so that slow computers don't have an advantage)</p>

<p>Of course, as the creator, if I'm in a bad mood, I can adjust the cost of using Nova to 0 and just blast my way through :p But the scores above, I got by playing fair.</p>

7

<p>"the reason that you can claim that the two red underlined spaces have mines is because you enumerated all the possible mine locations in your head, and then cancelled out the ones that didn't pass the minesweeper test..."</p>

<p>My argument, though, is that the human mind can "enumerate all the possible mine locations" <em>simultaneously</em>, or otherwise condense the logic into a form that is much faster than actually searching all the possible combinations. Example: think 3D minesweeper. Your first click, somewhere near the center of a large cube, reveals the number "18". You now KNOW that there has to be at least one mine in the 9 squares that make up any of the 6 "faces" of the "neigbor cube". Notice that I did NOT have to enumerate all of the possible combinations, as there are 26!/(18!*8!) possible arrangements.</p>

<p>"edit: you also seemed to have misunderstood the notion of NP. It means that the best algorithm we have to solve the problem is a brute-force search of the solution space, not that it's unsolvable"</p>

<p>My argument is that the human mind solves Minesweeper in polynomial time as opposed to the exponential time currently needed to solve an NP-complete problem.</p>

<p>"given a graph G with numbers at every vertex, does there exist an assignment of mines to the vertices such that the numbers at each node are satisfied?"</p>

<p>Also consider the fact that we are somehow able to recognize "weak spots" that, while not directly solvable, are easy to deduce using this, shall we call it, "fuzzy" logic? Therefore, we are effectively using a divide & conquer algorithm that isolates a workable area that will make the rest of the problem much easier to solve.</p>

8

<p>I thought the Minesweeper problem was whether a given board/placement of numbers was possible and not about actually trying to solve/play a game.</p>

9

<p>"I thought the Minesweeper problem was whether a given board/placement of numbers was possible and not about actually trying to solve/play a game."</p>

<p>Oops...I may have misunderstood my HMC prof...</p>

<p>Either way, though, this is an example of human logic being able to see what possibilities are valid without even considering individual possibilities. That is vaguely similar to the whole quantum computing trick that allows the processing of all possibilities (in a very limited set of problems) simultaneously. However, prime factorization has not been shown to be NP-complete, while the Minesweeper problem has...</p>

10

<p>Andy(tanonev),
I played "Spampede," and it's really annoying that when I press up/down followed quickly by left/right, that I die when I shouldnt be dying. The problem is that if you press up/down/left/righ it probably immediately changes some direction variable, let's call it dir, to whatever key you pressed. That works fine and well, however when you change to a different axis (i.e. horizontal if you're going vertical or vice versa) and then quickly change to the previous axis yet going in the opposite direction than previously, then that will result in your snake object having a dir such that the snake head is directed to go directly behind itself, because the game doesn't process the direction CHANGES fast enough. So my suggestion in order to remedy this problem is to use a queue or a similar data strucutre in your snake object, such that when you change direction it stores the direction you want to change to in a queue and right before your snake moves in each iteration of the game loop have the queue dequeue(get and remove front most object) and set your snake's dir to that which you have just dequeued.</p>

11

<p>on a slightly off topic note...I just got 60,000 on the asteroids game, and I never moved from the center. awesome :)</p>

12

<p>yeah. you spun around in circles...buddy i've tried that as well. </p>

<p>TANOEV:</p>

<p>how long did it take to program those games (not the java) but the visual basic. do you need a special program. did you invent the program or is there a tutorial that tells you how to make it? i am really interest in that stuff!</p>

13

<p>when you don't move, the only way to move is to spin. and just spinning and holding space isn't going to last too long. curse you...trying to bring down my accomplishment ;)</p>

14

<p>you're the cool kid now greygoo. have fun with your little accomplishment and don't forget, now you're the cool kid so you have to act cool.</p>

15

<p>i was never trying to act cool. this is a pointless argument. drop it please.</p>

16

<p>"My argument, though, is that the human mind can "enumerate all the possible mine locations" <em>simultaneously</em>, or otherwise condense the logic into a form that is much faster than actually searching all the possible combinations. Example: think 3D minesweeper. Your first click, somewhere near the center of a large cube, reveals the number "18". You now KNOW that there has to be at least one mine in the 9 squares that make up any of the 6 "faces" of the "neigbor cube". Notice that I did NOT have to enumerate all of the possible combinations, as there are 26!/(18!*8!) possible arrangements."</p>

<p>Unfortunately, that's not the meaning of minesweeper being NP-complete. What you described is an algorithm that we can put on a computer ... I think that implying that humans can do that kinda of calculation means that we have nondeterministic thinking is a pretty big stretch. dLo hit the nail on the head.</p>

17

<p>greygoo i am being honest. now that you have beat the record for that game, you're cool. no need to be ashame of it, but take pride in your status of being cool.</p>

18

<p>"I played "Spampede," and it's really annoying that when I press up/down followed quickly by left/right, that I die when I shouldnt be dying. The problem is that if you press up/down/left/righ it probably immediately changes some direction variable, let's call it dir, to whatever key you pressed. That works fine and well, however when you change to a different axis (i.e. horizontal if you're going vertical or vice versa) and then quickly change to the previous axis yet going in the opposite direction than previously, then that will result in your snake object having a dir such that the snake head is directed to go directly behind itself, because the game doesn't process the direction CHANGES fast enough. So my suggestion in order to remedy this problem is to use a queue or a similar data strucutre in your snake object, such that when you change direction it stores the direction you want to change to in a queue and right before your snake moves in each iteration of the game loop have the queue dequeue(get and remove front most object) and set your snake's dir to that which you have just dequeued."</p>

<p>I considered doing that, but then I decided that (1) it would be too much work, (2) most players adapt after a while to the turnaround time, and (3) people will be tempted to overload the queue with keypresses. Also, technically, you can reverse and turn in the same clock tick (though I have yet to see a human player do that effectively :p). Therefore, with this system, there is no situation that is absolutely impossible to escape (I think)...though chances are you'll mess up anyway when you reach that situation...</p>

<p>"how long did it take to program those games (not the java) but the visual basic. do you need a special program. did you invent the program or is there a tutorial that tells you how to make it? i am really interest in that stuff!"</p>

<p>The Visual Basic programs took varying amounts of time to code. Solitaire took like 1/2 an hour, Asteroids took 4 hours to write the basic code, and several more to smooth it out, Civil War took some 100 hours (ugh...), Minesweeper took 2 (?) hours
In order to write a VB program, you need Microsoft Visual Basic, which you must purchase (or pirate...DON'T DO THIS THOUGH). When installed, there are two parts: the form design, where you can draw text boxes, command buttons, and shapes the way you would in Microsoft Word; and the code part, where you must type in almost everything (just like in Java or C++).</p>

<p>BTW, Visual Basic is NOT meant for making games :p It's meant for applications, which is why there are builtin things like drivelist boxes, filelist boxes, radio buttons, etc. I will probably rewrite Asteroids in Java someday with nearly identical mechanics, but much more efficiency.</p>

19

<p>"I considered doing that, but then I decided that (1) it would be too much work,"
It took me only 5 minutes to implement after I discovered the problem on my multiplayer nibbles.
" (2) most players adapt after a while to the turnaround time,"
I suck at most video/computer games...
"and (3) people will be tempted to overload the queue with keypresses."
I seriously doubt that the queue would be overloaded, conisdering that with every iteration of the game loop an element from the queue is being removed, and snake is a pretty basic game so it probably runs through each iteration of the game loop very very quickly. Plus, you shouldn't have to store every key press, you only have to store ones that are different from your current dir that are also not opposite to your current direction.</p>

20

<p>""I considered doing that, but then I decided that (1) it would be too much work,"
It took me only 5 minutes to implement after I discovered the problem on my multiplayer nibbles."</p>

<p>The thing is, if I were to do that, I would also have to rewrite the Evilpede's behavior to be fair.</p>

<p>"" (2) most players adapt after a while to the turnaround time,"
I suck at most video/computer games..."</p>

<p>Since when were my games supposed to be "readily accessible"? :p Besides, I tend to code my games for my own benefit, setting the difficulty based on the way I play...</p>

<p>"Plus, you shouldn't have to store every key press, you only have to store ones that are different from your current dir that are also not opposite to your current direction."</p>

<p>That works for regular snake, but since Spampede required the implementation of "reversing" the snake, you have to allow for (1) the continued repetition of pressing 'r' (which will become disastrous should someone accidentally "lean" on 'r') and (2) whatever direction follows after pressing 'r', which means you would have to precompute the tail direction.</p>