⚡ Minesweeper Is Hard - Keegan R
ฝัง
- เผยแพร่เมื่อ 16 ธ.ค. 2021
- A slightly questionable exploration of one of the oldest digital games: Minesweeper. This talk will in absolutely no way send us down the rabbit hole of computational complexity, million-dollar questions, or Turing completeness.
Sources and Further Reading:
minesweepergame.com/math/expl...
www.claymath.org/sites/defaul...
www.minesweeper.info/articles...
web.mat.bham.ac.uk/R.W.Kaye/m...
Errata:
At 5:55 I claim that if n = 1000, then the number of digits needed to display the output number would be larger than the number of atoms in the universe. This isn't quite right - it applies to the value of the number itself, not the number of digits. - วิทยาศาสตร์และเทคโนโลยี
I grinned when you showed the NOT gate and then laughed out loud when you showed the AND. Awesome talk
4:30 might just be the best segue I've ever heard.
"Surely it must be possible right?"
"... Just as a quick aside, let's talk about *P and NP"*
5:55 if n=1000, 2^n would be larger than the number of atoms in the universe. But the number of digits needed to write down 2^1000 is only about 300.
This is very true! The person doing this talk mentioned the mistake to us at the time, but it seems like it went unnoticed until very recently.
In fact it can fit into a TH-cam comment: 10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376
in fact you'd need n to only be a minimum of 266
@@Cessated what would N need to be in order for the minimum to be 300?
@@warwickcomputing
This illustrates a phenomenon that I've noticed that when people are really advanced at something they also have a higher chance at missing the really obvious. Like I have only high school math and didn't have a clue what you were talking about through 99% of it but I spotted that one immediately.
The first click was NOT guaranteed to be safe in earlier versions, it was a guess like any other click. I got blown up often enough that I just accepted the randomness of success, and used available information and probabilities as I worked through it.
this video is excelent, it had me lost at the P/NP part but the final twist at the end caught me off guard. i was about to write a comment with more CAPS LOCK but just the fact that this video made me think is incredable.
Came here to maybe learn how difficult it is to generate a Minesweeper board... Ended up learning I could use Minesweeper to code Minesweeper inside of Minesweeper.
I saw the thumbnail and totally called minesweeper was turing complete. Stayed for the P vs NP
Minesweeper videos are a bit hit or miss but this one is quite beautiful
Was... Was that a minesweeper pun?
I absolutely loved this video. I implemented a minesweeper game in Java some years ago that featured an extra rule that appears in some of the ones I played and I liked: I considered the 4 corner tiles to ALWAYS be not only non-bomb tiles, but to be at least 2 cells away from any nearby bombs. I realized that my play time increased at least 30% more before I had to start making guesses, based on my difficulty logic. And by the way, my difficulty system was implemented to reflect the desired winning probability by generating the amount of bombs dynamically based on the desired field size. It was such a fun project to work on! Thank you so much for the upload, I hope you have more interesting content like this ;)
So...ultimately solving infinite minesweeper is equivalent to the halting problem. I'm surprised you didn't get around to saying that.
the consistency problem turns out to be REALLY hard :D
The halting problem? I couldn't quite grasp the connection there, could you please explain it to me?
@@spaghettiking653 If infinite minesweeper is equivalent to a Turing Machine then the question "Is this game unambiguously solvable?" is equivalent to the question "will this program halt?"
Sure it's the halting problem but it's of finite size so it is possible to do clever organization of the problem space to reduce the overall complexity of the problem to be solvable on a "reasonable" time. I'm guessing.. stockfish is pretty damn good and Google ai beat the Go champion so I think minesweeper might be understandable if not solvable in the near future.
@@andrewferguson6901 neither go nor chess is solved. The AIs are just better than humans.
"Surely we can just... make it consistent? Right?"
"Quick aside: P vs NP"
15:00 "∞ Minesweeper is Turing Complete"
😮😨🤯🤯🤯
In case you're wondering, solving the developer problem not in general, but for reasonable boards like the expert size. is actually fairly easy and has been done.
Checking that a board is solvable without guessing it's fast, and there's a relatively good chance a random board will be (given reasonable parameters) so you just generate random boards and keep checking until one is solvable without guessing.
That's what Simon tatham's puzzle collection implementation of minesweeper does. it's pretty fun
I had to retake a java course in college because my dumb ass submitted the final to gitlab and forgot to add the professor and by the time I noticed he had stopped checking emails for the semester, since I still had to show up every day for attendance I just sat at a computer during a weekly three hour lecture and played Simon Tatham's mines.
@@IReviewChairs oof
Boss makes a dollar - I make a dime
That's why I solve problems in polynomial time
Here I was thinking I was just sitting through another fundamentals of computing lecture, then BAM, infinite minesweeper is turing complete
I did not expect this to end with that revelation
this video got me diving back down the rabbit hole of complexity classes (which i know as a mathematician from 'uncomputable' numbers being 2^2^ω instead of the reals' 2^ω), it's awesome how these deep connections like P=NP come up in such common and seemingly trivial examples. great video!! i would love to see more about the topic!!
Let's call it the UωU conjecture
This is not the kind of presentation I'm used to from university channels, however i really could get used to it.
I was immediately horrified when you brought up P and NP, that is always the boogeyman hiding under any mathematicians bed
Solitaire is the same way. It's luck of the draw and you're just battling the odds. The more skilled you are the better you're liable to perform, but it's always ultimately how the cards are stacked, or mines are laid, that determines winnability. Then there's also luck, at least in minesweeper, when you go out on a limb and just click an unknown box - you might get lucky and be able to finish the game, or you might hit a mine and lose!
Saw the Turing Complete twist coming
3:08 - also you can have a look at the numbers of mines left to for example update the probability of the square affected by 5 and 6.
Because having a bomb there forces 1 less bomb on the board the odds of having a bomb there decreases as you have more bombs.
Was looking for this comment :)
I was not ready for you to pull out p and np man
The first half of this video is why I love the Hexcells games: not only are they more interesting (IMO) than Minesweeper, but Hexcells Infinite lets you solve millions of procedurally generated levels which are all solvable without guessing!
My enjoyment of minesweeper comes from the simple rules and the building/recognizing of patterns. I wasn't a fan of all the extra rules you had to keep track of in hexcells
Great video!
Personally, I believe P != NP because I once had the dubious joy of using a small flashlight to search a large field at night for someone's car keys. "Here are the keys!" is easy to verify, but "Where are the keys?" is hard.
Ah yes, the best hyper computer, MINESWEEPER
I had a bunch of mathematically complicated ideas but I guess the easy way to get around this if you want is to just throw out inconsistent grids, which should be fairly fast.
One possible strategy is to generate a random board on first click, run a solver, and if it can fully clear the board, return the grid, otherwise regenerate until it can. At small enough board sizes, this works quite well (remember how expert grids are solvable approx 50% of the time?), but consider that solving the grid is also an NP problem, so in general it won't scale well, but could be okay in practice.
Fun little exercise: try seeing how big these 'always solvable' generated grids have to get with this strategy before the generation times get too long...
Woah woah WOAH, the first tile is NOT always safe who the hell told you that nonsense?
Oh wait, right, y’all kids got the newer version with that as an option
We 90’s folk did not have that option, Minesweeper could end your run on the first move, completely random
Success rates were consistently less than 40% because of this
random video about minesweeper that turns out to be informative, funny and entertaining! I'll have to share with my software students.
Just give the player a health bar that depletes whenever a mine is detonated. Just enough so the luck-based parts could be dealt with, but not enough to randomly click where ever.
I expected flood filling algorithms, but instead I got a trip to high-school math, and then more math, and more, and then it took a weird turn to prove that Minesweeper Turing complete
Wow, this blew up very much recently, and I'm happy so, congrats on the great video tho! I really enjoyed it!
We're just as surprised as you are, and thank you!
@@warwickcomputing 😁
I currently have a 19.20 on easy, 102.67 on medium, 306.93 on hard (which is the equivalent of expert, and 636.61 pr on extreme on the minesweeper app, all with no guess mode enabled, so I am slowly becoming the gigachad we all aspire to be
This is a great video, love it.
As a minesweeper veteran, which isn't to say a minesweeper expert, I can say with (turing) complete knowledge that I hate minesweeper.
3:30 with a simple game lile minesweeper you don't notice when you got good, but I'm kinda proud that I solved your "difficult" example almost immediately.
Never thought i would hear about P and NP in this video hahaha great work
imagine playing minesweeper inside a minesweeper
Hard to believe that the simplest NAND gate implementation in Minesweeper includes a whole AND gate 🤔
I'm sure we'll figure out a better one when making computers out of minesweeper games catches on
7 minutes in, and my brain is like, "hey wait this isn't minesweeper!"
POV you clicked on a minesweeper video to relax and get transported back to University for a P NP lecture
nvm this video was so much more than that, I hadn't watched til the end
First of all, great fucking talk. Great banter.
2:42
If I’m not mistaken the 5 hast to have 2 bombs north and west of it.
This eliminates the top right dilemma. Leaving you with a 1/4 chance instead of 1/8th.
So if we can figure out a minesweeper solver, we could then code that solver into minesweeper itself... How wonderfully over engineered 😂
I never expected this video to go this way, I mean WHAT
what in the world!!! I never imagined minesweeper being a computer LOL, crazy
The only flaw using these gates is the number of mines changes based on inputs since every not gate you use will produce one more mine than x'.
As far as I can see with the pairs and triplets of a1,2,3 and b1,2,3 the and gate doesn't suffer from this.
And minesweeper should let you know the number of mines on the field (in some cases there are minesweeper games where fe. 99 mines is possible to solve and 100 wouldn't be and vice versa).
I intend to use this flaw for bare-minefield exploits when we finally get minesweeper based computers.
6:00 2¹⁰⁰⁰ has 10log2*1000 digits, so like 280 digits... wow i didn't know there were less than 300 atoms in the observable universe...
That Minesweeper wire sounds awfully much like Schroedingers wire... :o
Nice tutorial.... Very helpful
Really nice and helpful... Thanks!
So, like almost everything else, Minesweeper is turing complete - fine. Doesn't matter for the task of making it solvable without guessing by a perfect player though.
The obvious solution is to generate the field and validate it by a simulated player on first click. Like it probably is already done, you randomly position the selected amount of mines on a board of selected size. But then you run a simulation that tries to solve it with only the information, the player would have and gives up whenever it would have to guess. If that simulation fails, you restart with a freshly generated board until the simulation succeeds.
The player might wait a while (theoretically, it could be an infinite amount of time, but for the 100 mines default board, it shouldn't take too long on modern hardware). The final board presented to the player will always be solvable without guessing (depending on the simulation, it might not require the maximum skill though).
At most it can be (1-bombs/size) because we have 0 information about the first square.
For exemple for a grid of 10x10 with 15bombs the maximum probability of winning is 85%
That's a good start for an upper bound on the problem - are there any other guarantees that might be able to improve it?
@@warwickcomputing Improving would be difficult but at least we are not dealing with too many variables: size and bomb%. It is possible that the size is becomes irrelevant after some big size. I wonder if anyone knows more.
We do have the information that the first square cannot be a mine.
@@Cr42yguy I am making a probability table for minesweeper.
@@qy9MC Cr42yguy is correct though - no matter what square you click on first, Minesweeper guarantees it's not a mine.
Great video but a couple of concerns, 1. Though NAND does dominate in gate count, CPUs are not actually made exclusively of NAND, this is a common misconception since it is a universal gate (all other _logic_ operations can be reduced to it), however simple not gates are also quiet common as well as many less common gates such as transmission gates, delay circuitry, etc. 2. I did not see a demonstration of any kind of memory, which is pretty critical if attempting to prove TC by way of CPU architecture. (to be clear, minesweeper is provably TC, just nand alone is insufficient)
There is actually a game very similar to minesweeper called hexcells, instead of squares its hexagons. There are additional rules which makes the gameplay more exciting. Anyway there's a gamemode with literally billions of generated solvable(without guessing) puzzles. So there you go! Solveable minesweeper.
Absolutely love hexagons, I was going insane over the RNG in minesweeper after having played literally tens of thousands of games with like a 15% winrate.
3:36 im soo glad i clicked on this video
Actually, I'd usually try to avoid the consistency problem as much as possible in a game using one guess and going from there. Many times you end up with pretty big logical chains that sometimes end up solving the remaining consistency problems. I'd say most of my games end either because I'm going too fast, misclicking or getting wrong at the 50/50 last square. I'd say in expert mode a significant amount of games end in 1-4 consistency problem issues in each localized instance.
For instance, your example on inconsistency not being obvious, the first thing I'd try would be seeing where it's impossible to have a mine (the chain of 2's has a place). Depending on your luck a simple information of 1 number solves the inconsistency chain.
Relative to being Turing complete, I suspected it could be, kinda cool to find this vid. I had no idea an and gate was possible.
Encore! Great video
Fun fact:
the halting problem is solvable in reality.
Because an infinite tape and set of instructions is impossible it must be finite.
If we remember the condition of the tape after each step and compare to all previous conditions of our Turing machine, we know when a Turing machine is back in its initial configuration.
Turing machines are determinate, therefore same input = same output.
Therefore the halting problem is solved for finite Turing machines.
All modern computers are finite, therefore I can claim that a proof of P=NP doesn't mean jack s**t for the practical prime factorization.
Even if P=NP there's plenty of algorithms that are """"""faster""""""" for lim_n -> inf
Just because it's polynomial doesn't mean it's solvable on human timescales...
The """""""fastest""""""""" way to multiply two number is a 1729-dimensional fourier transform, while returning results in O(n*log(n)) that's ignoring everything that isn't the dominant factor.
Having a 10^(10^(10^10))*n runtime would still make it O(n) but we all know it's never going to be of any use for us or any potential life form in existence...
I get the point of ignoring constants and less fast growing parts but big-O just has obvious problems.
edit: if you want a chuckle have a look at "galactic algorithms"....
just a clear demonstration of mathematics doing what mathematics does, showing that "leaving-the-trees", "walking-upright" and "becoming-vertebrates" was a massive f*****ing mistake
returning to monkeigh is already too conservative
at some point we should accept that protozoa were right and simply return to our ancestors roots.
humanity wasn't intended to get this far, returning to primordial sludge is probably the best idea (and saves a bunch of taxes).
so true, all these theoretical people with their 'proofs' and 'infinities' are really causing issues around here
In an infinite minesweeper board, what is the maximum density of mines where the entire board can be revealed in a finite number of clicks?
Zero. For any nonzero density you get in any finite area clusters that require at least one click to resolve with nonzero probability, and hence on the infinite grid with probability one an infinite amount of such clusters.
Yea, i agree with you. Minesweeper is UNFAIRLY hard.
It took me an entire 2 days to learn how to easily beat minesweeper. It's only hard when you don't understand how to play the game, or get caught into a scenario when the game gives you no hint on where the mines could be, which makes it turn into a guessing game with educated guesses, and matter how skilled the player is, they can still easily fail, and have to do everything and all over again, but also making it randomized.
Once you learn the patterns of generation, you can make educated guesses that increase your odds of winning via intuition.
Such an abstract thing, this is.
Mind boggling.
I dont understand shit from the pnp part but a tentacle might actually pop out
2:20 should be permutation since each orientation of the board is unique
(not an expert) I don't think it is a permutation, because it doesn't matter if you change the mine in (a, b) for the one in (c, d) coordinates, in both cases you lose if you touch any on them.
for the one at 2:53, wouldnt that be solvable by knowing how many mines are remaining in the puzzle like you would in a regular game, allowing you to work your way out from the inside?
Maybe, but it would at least depend on how many are left: There are at least four mines left. If we are told that there are five or more, then any of the squares that are left could hide a mine.
No. You could reduce the problem to a 2 by 3 grid in top left and have mine counter of 1. You have no way of knowing which yellow field it's in, because exactly the same hint map is valid for two different mine layouts.
This video is a banger
I wonder if this is also true for Blind Mamono Sweeper.
Agreed.
Have encountered numerous tile maps where I was left with nothing but a guess; the 50% rule you expressed is quite valid provided the "guess" event occurs only once, but I've also had maps (8x8) with up to 3 "guess" moments of which I've not won over yet. Minesweeper can be very challenging due to the presence of the "guess" when it occurs - definitely adds depth and breaks the linearity of the game keeping things fresher longer. Interesting discussion.
Good vid.
A bit quiet, but wonderful content!
tbh I'm still not convinced that "can make binary logic gates" is equivalent to Turing completeness, because you can't make loops of any kind.
I guess since the board is infinite you just repeat the same expression forever in a direction?
Right, the infinite board means you can unroll any loops.
And you can make a crossover from nand gates, so the 2d isn't a limitation either.
hm, i guess the best strategy for proving this would actually be to lay out each individual timestep of the computer vertically, and then repeat that infinitely to the right. then rather than having like the actual "program" of the computer laid out possibly with multiple nested loops, you just have the computer pick its next step and have that be in the next column, and the next, etc.
then you can use a very simple state based structure like rule 110 which can eventually be reduced into a turing machine
Simulate minesweeper in a minesweeper infinity grid
i'm downloading minesweaper
I think it’s sad that, he gets to his conclusion of it being Turing Complete, and I’m disappointed. I read a comment about a twist at the end, and it’s just another Turing complete video game, it happens so often I’m not even sure why it’s interesting…
is it realy turing complete? If you build an And gate you cut a part of the infinity fild so one direction isnt infinity anymore that everything on one side of the and can not connect with everything on the other side. But maybe it is possible to point U and V (13:49) in the same direction. Than it is possible. But I am to stupid for this.
It gets worse. When someone loses, I randomly punch them 🤣
absolutely amazing video and a great p/np example, but your speech is a bit hard to understand when you speak so quickly.
Agreed. I kept having to jump back
I see O notation I click video
I'm a computer science student in Hungary, and I'm currently doing my first semester, and during programming class we got a practice assignment that goes like this;
Write a C program that solves every type of minesweeper grid.
I actually got 557/1600 points with just some if-else conditions, and actually got more points than the teacher (at 529, although he could probably get more if he wanted to)
But if I understand this video correctly, it is actually impossible to write a program that would get 1600/1600 points??
Unfortunately there's no real way to get into the state required for e.g. a Minesweeper wire without guessing… in actual play, you would end up with blank space above, an infinite row of 1s, an infinite row of unknown squares, another infinite row of 1s, and blank space below. You would need to arbitrarily guess the position of a break point.
(let alone an AND gate, of course!)
Well, ACTUALLY, a computer would be equivalent to an arbitrarily big minesweeper grid. It wouldn’t even need to be infinite lmfao
But great video anyway, it was really interesting
That was unexpected
I don't like that the example here uses the trite "more than the number of atoms in the Universe" line, copied from every other discussion on combinatoric explosions.
The 2 at 4:00 that shouldn't be there is sending me
I actually hit a mine on the 1st pick a few times
Great video. Completely lost me with the kitchen analogy haha,. It was the opposite of useful
Is there a version of minesweeper with no 50/50 guesses?
Been trying to find it. Dropped this comment before watching, will delete if he mentions it
and eventually
Minesweeper is not Turing complete. Nand gates + feedback allows you to make computers, which can simulate Turing Machines. There's no "step forward in time to run with feedback" in vanilla minesweeper. Also, a SAT solver can easily be fed minesweeper constraints (with a constant number of constraints per tile), so clearly it's only NP-complete at worst.
Yep - without the concept of timesteps/feedback, it's technically not quite enough to give Turing Completeness. There was a mention of "inputs on the left and outputs on the right", but the speaker didn't dive into the extra subtlties needed.
I guess you need to dig into the details. Kaye's paper with this result is here: web.mat.bham.ac.uk/R.W.Kaye/minesw/infmsw.pdf
@@Chalisque I didn't read the full paper, but I did realize my mistake. There is a "step forward with feedback" in infinite minesweeper. You can just use a "translate a large (and possibly increasing) number of units to the right" to take you forward a timestep. As long as "past" versions properly feed into future versions, and you pair the "machine" part with a pair of arbitrarily growing accessible stacks growing up and down by the timestep.
In finite minesweeper, this wouldn't be a problem since you can just "run the turing machine until you hit the right wall" at which point execution is abruptly halted. With infinite minesweeper, you can add little inconsistencies with the "halt" state at each timestep, allowing "consistent" to tell you that this machine never halts, and "inconsistent" to tell you that it does.
what if P=NP and P!=coNP
has this and its closely-related sibling where P=coNP but P!=NP been proven conclusively false
I feel like the answer is probably yes hehe
You can turn any NP problem into a coNP problem quite easily, these two are the same:
- NP: does X instance have Y property (can verify YES certificate polytime)
- coNP: does X instance NOT have Y property (can verify NO certificate polytime)
This makes the existence of coNP seem a bit pointless, until you discover there are problems simultaneously in both NP and coNP, but not known to be in P. One of these is to determine whether or not a number is prime :)
uhhhh your name is Keegan R? same. Roy 😎
OK, but can it play doom?
you'd have to be a bit more specific about what constitutes as a pixel, so it wouldn't look like Doom in the standard sense, but... maybe 😳
@UWCS - University of Warwick Computing Society I mean you could do it similar to Conway's game of life's pixels where you create a module to act as one. As well you would have to have a way to refresh the screen. For that, I would suggest moving the screen over to a new set off "pixels" and display the next frame there.
Still dont know how to solve unsolvable problem
Minesweeper got too easy
minesweeper are turingcomplete WTF, now i wanna see someone to try to port DOOM to it hahusahhahahahasha
what
after playing it for decades,.. my probability of winning only 26%,....
With all this math it is hard. It is a lot easier when you just play the game.
1:07 You want to get good so you buy a 309d graphics card to get the best fps
lol
You glossed over too much of designing minesweeper to only generate solvable boards. You made it sound like a bad thing but it's actually quite important.
"A minesweeper wire", oh boy, here we go again. I almost wonder if it's more interesting to prove stuff isn't Turing complete at this point.