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.

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.

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.

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.

Minesweeper videos are a bit hit or miss but this one is quite beautiful

15:00 "∞ Minesweeper is Turing Complete" 😮😨🤯🤯🤯

"Surely we can just... make it consistent? Right?" "Quick aside: P vs NP"

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 ;)

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

So...ultimately solving infinite minesweeper is equivalent to the halting problem. I'm surprised you didn't get around to saying that.

I was immediately horrified when you brought up P and NP, that is always the boogeyman hiding under any mathematicians bed

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 is not the kind of presentation I'm used to from university channels, however i really could get used to it.

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!!

I saw the thumbnail and totally called minesweeper was turing complete. Stayed for the P vs NP

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

Boss makes a dollar - I make a dime That's why I solve problems in polynomial time

I was not ready for you to pull out p and np man

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.

This is a great video, love it.

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!

Ah yes, the best hyper computer, MINESWEEPER

Wow, this blew up very much recently, and I'm happy so, congrats on the great video tho! I really enjoyed it!

random video about minesweeper that turns out to be informative, funny and entertaining! I'll have to share with my software students.

Never thought i would hear about P and NP in this video hahaha great work

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.

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.

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

Nice tutorial.... Very helpful

7 minutes in, and my brain is like, "hey wait this isn't minesweeper!"

Really nice and helpful... Thanks!

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

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.

Encore! Great video

So if we can figure out a minesweeper solver, we could then code that solver into minesweeper itself... How wonderfully over engineered 😂

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

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.

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.

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.

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.

imagine playing minesweeper inside a 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.

POV you clicked on a minesweeper video to relax and get transported back to University for a P NP lecture

As a minesweeper veteran, which isn't to say a minesweeper expert, I can say with (turing) complete knowledge that I hate minesweeper.

I never expected this video to go this way, I mean WHAT

Hard to believe that the simplest NAND gate implementation in Minesweeper includes a whole AND gate 🤔

This video is a banger

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?

A bit quiet, but wonderful content!

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)

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%

2:20 should be permutation since each orientation of the board is unique

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).

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?

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.

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

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.

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?

I wonder if this is also true for Blind Mamono Sweeper.

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.

Yea, i agree with you. Minesweeper is UNFAIRLY hard.

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.

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).

It gets worse. When someone loses, I randomly punch them 🤣

i'm downloading minesweaper

3:36 im soo glad i clicked on this video

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!)

absolutely amazing video and a great p/np example, but your speech is a bit hard to understand when you speak so quickly.

That was unexpected

Simulate minesweeper in a minesweeper infinity grid

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??

I dont understand shit from the pnp part but a tentacle might actually pop out

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…

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.

I actually hit a mine on the 1st pick a few times

I see O notation I click video

The 2 at 4:00 that shouldn't be there is sending me

and eventually

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

Great video. Completely lost me with the kitchen analogy haha,. It was the opposite of useful

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.

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

uhhhh your name is Keegan R? same. Roy 😎

OK, but can it play doom?

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

Minesweeper got too easy

Still dont know how to solve unsolvable problem

minesweeper are turingcomplete WTF, now i wanna see someone to try to port DOOM to it hahusahhahahahasha

what

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.

With all this math it is hard. It is a lot easier when you just play the game.

after playing it for decades,.. my probability of winning only 26%,....

You joke, but people literally want the best graphics cards to play Minecraft and Among Us lol