For decades, I never understood how to play Minesweeper. In 40 seconds, you explained it in a way I understood for the first time and I actually won a game for the first time in my life. Thank you.
@@Logia_ Come on, you know what they probably mean is they tried it once, didn't get it at first, and then never touched/thought about it again until now. Not that they've spent decades trying to figure it out.
@@Logia_ I was a stupid kid. I would just click on boxes around the numbers. I started on Microsoft 3.1. There wasn’t a tutorial. There weren’t instructions. All I saw were boxes that would occasionally explode. For my 8 year old mind, it seemed to be luck based. I figured out that the numbers meant “3 means don’t click within 3 squares,” but I never understood that meant “3 squares in this 3x3 grid are mined,” I assumed it was like a plus shape. Sometimes it worked, sometimes it didn’t. I never won a game, I’d only get it to a few squares left unclicked and at that point it was random chance in my mind because I couldn’t figure out the pattern. By Windows 95, I had just given up. It was random to me. In the old days of TH-cam, there was a “Minesweeper: The Movie” parody trailer that sort of explained it and I still didn’t get it. It was only 2 weeks ago that someone actually explained it in a way I understood. I did have a learning disability back then, if that makes it more clear. I preferred Solitaire, Mahjong, SkiFree, and Pinball.
In the late 1990s I actually wrote a Java applet to play and solve minesweeper, capturing all these strategies that you discussed. Pretty much used the same ideas you did. These days, I'm wondering if a deep learning neural net could do better somehow.
How very interesting! I specifically chose a strategy which is fairly intuitive and doesn't require much computation. So just like I say towards the end of the video I have no expectations of this being an optimal method, just a good enough one you can use yourself. Sure machine learning will probably net you a pretty strong agent but I suspect some sort of strategy based in information theory will be just as powerful with far less "unusual behaviour" so to speak. Thanks for the input!
I don't know if deep learning can come up with an optimal algorithm, but we can do just with brute force, and that approach is surprisingly practical. th-cam.com/video/cGUHehFGqBc/w-d-xo.html Note that there is no "perfect" algorithm for Minesweeper, as there exist arrangements that cannot be solved without guessing.
Deep learning is huge overkill for this and not really appropriate. Minesweeper is crying out for a rules based system as discussed - highly discrete and only a tiny number of choices to consider
@@TAP7a Minesweeper is NP complete and thus any such rule system must come with a caveat. I see two possibilities (maybe I'm missing some): * The number of rules depends on the board size, and grows exponentially * There are rules for which checking if they can be applied takes an exponential amount of time Actually it's easy to come up with a system (actually consisting of just just one rule) that fits the latter: - Consider all possible Minesweeper boards with the same size and number of mines as the board we are solving - Build a set S of all boards that agree with our current game state (i.e., a board B is in S iff all open cells in our game have the same number in B, and all cells we flagged are mines in B) - For each cell that is a mine in each board in S, it is a mine in our game - For each cell that is safe in each board in S, it is safe in our game Here, S is exponential in size, and thus this rule takes exponential time to apply.
Minesweeper is such a simple game that it's fairly straightforward to come up with an algorithm which plays perfectly, you don't need neural networks or any AI trickery at all. You just take the algorithm in the video and compute statistics about where the remaining mines are most likely to be and which cell is most likely to reveal the non-mined cells. I'm not sure how much computing power this will require on large boards though, it might be more efficient to immediately click on the cells which are 100% guaranteed to not have mines on them and only compute more complicated statistics if necessary. Even a perfect player will need to gamble if there are enough mines though, so you can never guarantee the board is solvable
Configurations are faster but require more memorization. An algorithmic approach like this requires more brain juice and is not as fast and obviously, it will repeat the same calculations even if the pattern has already been solved BUT the big advantage is that it doesn't need you to spend hours memorising the patterns.
It took me 6 minutes to realize this random video bestowed upon me by The Algorythm is actually teaching me math. And then suddenly programing. If only it was this entertaining when I was learning.
I watched this entire video with the automatic assumption based on the quality that you must have had hundreds of thousands of subscribers, and I was just about to click off before I noticed you don't even have a thousand! I had to stop to just say how incredibly well done this, it's almost like watching 3b1b, I hope you keep making more videos!
I have to agree with @Sheep44. I wasn't expecting set theory, and was pleasantly surprised with its application to minesweeper. It even helped me understand it better. I also hope you keep making more videos.
Oh awesome! Honestly I got this strategy by working out what it is I'm doing when I play, and ended up with something a whole lot better! It's a shame I couldn't get around to mentioning the more unique patterns where this approach gives you loads of information despite seeming like there's none to uncover. Thanks very much!
I loved your video! I took a very similar approach when I started making a solver for the minesweeper variant game called Tametsi. I also used sets to describe sets of unknown neighbors and overlapped them in a second step after I applied the first two rules about being full and empty. I’m so happy to see that someone else came to a similar conclusion on their own. Something I did for tametsi that I didn’t see you describe here, was define the number of mines in a set as a set of possible sums of mines, rather than as a single sum. In tametsi this was a required step. You could deduce information from whether two cells had one or two mines and not zero, or zero or one mines and not two. Tametsi has the added bonus that all puzzles are deterministically solvable and premade by hand, so it could test your solver very effectively.
@@applemaths4062 In the mean time, pass an Lowpass filter through audacity with a frequency of 12kHz and it will remove a lot of the whines the microphone introduces.
@@applemaths4062 yes, you can actually record a sample of the noise in the starting (i.e. idle recording of 5s before you start speaking - assuming the noise level in sorrounding stay roughly same), then subtract that from the recording throghout to denoise
@J.Azz. Woods Ooh that's a good idea! Thanks very much, I will definitely give that a try at some point. I must admit, even though I know a fair bit about audio in theory, I haven't done much with it in practice. Video production is definitely a beast of a learning curve!
Ferb, I know what we are gonna this weekend! Everything aside though, this is a banger start to a new channel, subscribed! I hope you make more content!
The animations are so fuckin smooooooth, I kept thinking about that!!! I can’t wait for you to blow up in subs and all the analytics goodies man, keep up the good work!!!! And I also whole heartedly agree with the 3b1b comparison in one of the comments!!
I learned playing minesweeper by common understanding, practice and no mathematic means, and has beated the game several time in hardest mode. But watching this video is interesting to know there's mathematical way to understand and play the game. Good vid
What's the problem? It's the mathematical equivalent to a box of unloved wires: it's never organised, and you don't care about duplicates - you either have the one you want or you don't! 😀
lol it's pretty ironic to me how an algorithm that solves a 33 years old obscure game is enough to "prove you wrong" but the device you used to write this comment on isn't.
It's always nice to see a video on minesweeper :) I've played it quite a bit, and there are certainly more effective methods available than the one showcased here (especially when it comes to counting remaining mines), but it's a very interesting starting point, as it describes how we can turn the game into a purely mathematical problem. What I'm interested in about this algorithm that I don't think was specified: are you running the algorithm on boards that are always solvable, or are you running the game on boards where even an optimal strategy would be forced to guess a value at some point?
Thanks very much! Great question! The implementation of the minesweeper clone I created for the AI is very bare bones so no. In fact, it didn't even make sure the first move was safe originally! Essentially as this strategy could do something in the order of 50 boards per second, I just ran it over and over again until I had an interesting layout that clearly demonstrated the relevant problems and how this strategy overcame them in an obvious way. I'll probably put it up on GitHub if I get around to doing some code sanitising!
What methods (to find mines) do you have in mind? Of the top of my head I only recall two other rules: 1) in a line of ones (such as a line starting at the edge of the board) the third one is safe and 2) that a line of ones interrupted by a single 2 means that the square directly next to the 2 (to its side or above/below it) is safe, i. e. the two neighbouring squares are mines.
@@xCorvus7x Most of the methods I use are things I've just come up with as I solved more and more of these puzzles. Not completely remembering everything presented in the video right now, there are several useful rules beside the 1-2-1 rule that is the most commonly used one. For instance, if we have a row/column with the numbers 1-2-2-1 then we know that there are exactly 2 mines located right next to the 2's, and in certain cases if we have a 1-1-1 configuration we know that the mine is next to the 1 in the middle. Counting arguments are also really powerful, as they can be used effectively in later stages of solving a mine field for ruling out specific potential mine configurations based on how many mines are left and in which general regions the remaining mines have to be distributed.
Minesweeper would be a huge optimisation problem for sure. In random maps, the script would need to look for the starting location with the highest probability of winning (the corners have a higher chance of survival, meanwhile the centre has the highest chance of bigger openings). General minesweeper strategy is to always take any forced guesses as early as possible so that less time is wasted on runs. And there are even more difficult optimisations like mine counting and finding probabilities in situations. There is also the concept of an 'optimal move' using chording. Placing a flag next to a 1 and then chording it only takes 2 clicks, while clicking the mines next to the 1 would take longer. In other situations it would be better to not place any flags and just open the safe tiles.
I sorta understand the ideas, which I should be more familiar with either way since I'm a computer science major. But man the production quality of this video is crazy good for below 100 subscribers! I hope this channel grows!
This is very cool, I really thought that first board was going to force you to click the tile that's most likely safe, and that it was a gamble, but I was wrong. You can deduce enough information from those tiles to actually clear the whole board! Awesome!
i enjoy coding so breaking it down into code did actually help me as I can visualize what to do when something happens. i right most of my notes in a sudo code like structure using the common if, if else, and for loops cause those were what I learned on .
Really fun video, and it’s come into my feed so hopefully it’ll go into some other STEM enthusiasts on YT, you clearly have a passion for this type of thing, and a knack for good video presentation. I think the main recommendation would be to get a better mic, and maybe add some light background music, it doesn’t have to be strong or loud, but often helps viewers deal with silence between your audio. Also a slightly better mic will be able to isolate out your voice from mouse clicks which were done to trigger animations during recording. Really fantastic stuff though overall and I’m looking forward to hearing/seeing more of your stuff in the future 😁
10/10 for the animations and the script. Like @Sheep44 it is almost like watching 3b1b. Very interesting concept aswell. I just think that you should invest in a better mic for improved sound quality. It’s not a distraction by any means but I think it would make the vids seem more professional. If you keep making videos like this you can probably expect at least 100k in a year or so. I’m excited to check out the rest of your channel! You just gained a new subscriber😀
Very interesting video. 👏👏👏 Pros to you for showing the maths behind minesweeper but it's much easier to learn patterns. 🤣👍Looking forward to more vids from you
Thanks! I have linked the source code to the agent in the description which, if you're confident with a command line, you can use to automatically generate more of the visualisations like the one at the end of the video!
A powerful algorithm could work as following: Identify all possible combinations of mine placements for a given board and use that to calculate the probability of each tile being a mine. If any tiles are 100% or 0% click them or flag them and repeat the process. If no tiles are 100%/0%, click the one with the lowest probability of being a mine and restart the algorithm. It's not optimal because it doesn't account for how likely the board is to be solvable after guessing which it should take into account when chosing a guess, but it's probably close.
In theory yes, that is one of the approaches I'd absolutely consider. In fact it's what I tried taking a look into for when the algorithm I had got stuck. However, I've got a feeling that that probability calculation would be *very* expensive and convoluted unless there's some clever transformation you can do to make it into a matrix multiplication or something. Not to say it's not worth looking into! I actually used the most watered down version of this when my agent got stuck, using the sets I already had a hold of with the strategy in the video, clicking the tile with the lowest probability of being a mine. Sure it's not great, but it was enough for me to explore the situations the agent could end up in and iron out the bugs! Thanks very much for the input!
I applied the above algorithm and even applied set theory logic for a simulation but it was unable to solve the board nearly half of the time in simulation. There is a need to properly use more information gained from the board while solving every next tile.
I should start by saying this is much nicer than most Minesweeper videos I have seen. A lot of people discuss Minesweeper strategy as strategy, but the discussion of it as mathematical or even algorithmic is nice and concrete as a model. However, you've not solved Minesweeper in any of the ways which are meaningful to solve Minesweeper. From my perspective, the great pillars of Minesweeper analysis are as follows: high accuracy strategy with a focus on using probabilistic methods to determine the best guess at any point on a board where a guess is required to progress, minimal click strategies with a focus on things like information theory and how much a strategy is likely to reduce the uncertainty of the board and which mines aren't worth flagging and which are, and then the development of speed strategy for humans and things like powerful visual patterns and applications of mouse tricks. Codifying the rules and most basic techniques of Minesweeper is something of a beginner project, and you see it done a lot, but it's not the interesting part by a long shot. It's like a chess engine which can find a legal move, or a sudoku solver which scans rows and columns the way my mom does.
First of all, thank you! I thought it was a fairly good choice as a problem I can abstract into very few very simple mathematical objects, and I therefore really appreciate the compliment! I came into this project with the intention of doing very little research. I thought I'd give a unique perspective to, and hopefully teach, a strategy with significant efficiency and hopefully simplicity which I was familiar with. That's why I didn't bother with the flood fill most implementations bother with whenever you click a zero, and is why I thought it best to just flag everything. Granted "How do you _solve_ Minesweeper" was a pretty misleading choice of words, especially for those who are already familiar with everything I mentioned in the video, but for the audience I was targeting - those with little confidence with either the game, or the mathematical description I supplied, or just problem solving in general, I personally thought it was adequate, as it was a passion project of mine turned into a simple lesson about problem solving. Now that's not to say I didn't consider some of the more advanced things you can do with the game, such as construct a probability field of mines at each position in the grid, or how you could use information theory or constraint satisfaction algorithms to solve a board with a million tiles in only a few milliseconds, but I decided not to include them, partially due to the limited time constraints for SoME, but also because they were much harder to visualise in this way, and I have far less confidence with them: it would have turned a 2-3 month video project into a 4-6 month programming project which would have only been seen by a half dozen or so programmer friends instead of thousands who could genuinely have learned something from it. Personally, I think that comparison to verifying the validity of a move in chess or finding the possible available options in sudoku is quite harsh. Although yes it will probably come out to a similar number of lines of code, that doesn't mean there's a similar amount of thought or complexity within. In those two examples, you're writing code that essentially enforces a set of rules you read out of a book, whereas the strategy I described in the video is based on a few simple but clever observations about how the mine counts of neighbouring cells interact with each other. I do still see what you mean, it is a very primitive strategy, but a win rate of 20% in a game which requires you to cross your fingers and hope for the best half the time is not as insignificant as the rules of the game in terms of creating an agent. Don't take it like I think you're spouting rubbish, because I absolutely see where you're coming from! Creating an optimal strategy, both in the case of an abstract agent on a computer and a strategy humans can keep in their heads and execute quickly, is miles above and beyond what I've described. However, as I only play the game recreationally and the video was supposed to be approachable to many, I don't think working something like that in would be appropriate.
@@applemaths4062 I suppose through this lens of "a good video for SoME which uses set theory to help us grapple with a complicated but familiar problem", surely all your boxes are checked. As a video discussing Minesweeper, I think most do it in this no research, from the ground up sort of way, but the math is certainly a nice touch. Perhaps I am projecting too much, but it reminds me very much of the "Sudoku solver" I wrote in high school. I implemented a few intuitive strategies about scanning and elimination, things of course that followed directly from the rules but were not rules, and it could solve "easy and medium" puzzles from my test bank. Learning about Knuth solving the problem with dancing links but a bit of a hamper in my pride, and then doubly so as I became more familiar with what an interesting sudoku is and is not, what their solution paths look like, what happens in the mind of an experienced sudoku solver and how grossly different it is from brute forcing pattern checks in order of increasing complexity. I guess what the comparison is meant to highlight is that, rather than some simple but intuitive implementation of a solution to a complicated problem, you have created a simple and intuitive implementation of a simplified problem, one which is rough and mechanical in its methodology, one which is making far more observations and deductions than any human would need to, a video which is less about solving or even playing a game and more about a grand and valuable set of computations on a Minesweeper board. I fully acknowledge at least some of this is totally unfair, but it is such a strong and intuitive urge in me to keep going from here that I hate to see people stop at this sort of stage. All of this, I suppose, in hopes of inspiring a deeper dive.
Yeah I have to agree with you, this is a problem where most people are going to be satisfied with the first non-trivial strategy, which is certainly what I've supplied; not doing any research and doing the first clever thing that comes to mind. I absolutely see what you mean with that sudoku solver. In fact, one of my Artificial Intelligence units at university requested I create such an agent! I tried to optimise it by using whatever shortcuts I was aware of, but ended up slowing the whole thing down! Going the wrong route first time in a constraint satisfaction algorithm is not as bad as adding extra tree pruning checks which only get used a couple of times. I loved the look of Knuth's Algorithm X (still can't get over how cool of a name that is), and you bet I tried my hardest to recreate it! (sadly the initial problem matrix setup took way too long...) If I'm interpreting your words correctly then yeah! This was supposed to be a general lesson in problem solving by simplifying the problem into something much more manageable and attacking the problem at a different angle through those abstractions. It's a very algorithmic strategy, which fits in that gap between what a casual player would be able to notice in terms of patterns and what the computers do using their black box algorithms. It doesn't "solve the board" by any means, but it does push most people in the right direction, giving them more opportunity to recognise new patterns! I understand the urge, there is a lot of potential in what you can do with this game, and I too would be understandably disappointed in your position! However, as you said, this was meant to be a good introductory style SoME submission, so the time constraints really limit how far I can go. I'd love to see it investigated further in this way, see more of what can be done, so if someone wants to give it a go they have full encouragement and support from me that's for sure! If I'm going to revisit it, it'd have to be a little ways down the line. I have some other ideas and I don't particularly want to be known as the minesweeper guy! Thanks for keeping it constructive, heck, commenting at all; it means a lot!
short answer: git gud btw, when the smarter strategy section came up (which i had skipped to after basic) i immediately knew what to do and was pleased to see the same thing being done but with formal terms
I think 5:45 is where knowing math terms helps big time, even then had to re-watch and listen a few times... i seriously hate Maths terms and think the industry has a usability problem that stems from 100 of years ago... I can't think of anything better however! Nice vid.
That is a brilliant point, I never even considered that! Terminology has perhaps the worst form of the curse of knowledge; really slow and obnoxious to learn, really trivial looking back. This is really helpful, I'll absolutely try to incorporate that in future. Thanks very much!
A better algorithm would be to prioritize solving the 1s since they almost always yield more cleared tiles. Meanwhile, your set solving strategy is good and I use it too but as others have said, it should be paired with pattern recognition since it is more efficient since you don't have to do the same operation over and over again. Finally, a proper algorithm should be able to backtrack and go over previous unsolved tiles since the nature of the game unlocks more clues on previous tiles the closer you get to the end.
Reasonable observations, thank you! When describing the agent, I specifically chose to avoid mentioning any sort of order of operations. Yes this can absolutely be improved by changing where you perform this analysis, however deducing a good ordering for which cells to do this with is too expensive to justify in the case of a computer playing, and for a human player, this prioritisation is either already employed or can be picked up by intuition. In the examples in the video, I chose the ordering myself to demonstrate my ideas, and the agent which plays the game at the end of the video is designed in a way where it inevitably will perform some backtracking. Concerning pattern recognition, yes of course that can make the game easier, however this approach in practice would be more of a way of generating patterns you can use. Talking about patterns doesn't provide any interesting insight as to why they work, whereas providing a way of generating them is far more valuable if someone wants to learn to be good at games like this. Rote memorisation of patterns will get the job done, and is indeed the best choice for learning to be fast at it, but it is perhaps the least helpful way of learning. Granted I could have gone through more examples and show off why some other more unique patterns work, which I apologise for, however there will always exist prospective improvements to a project like this.
Beautiful video! As an asterisk, many non-math literate viewer might benefit from a quick link to an intro to discrete math if they want to look further into this. Myself, I hadn't done any math in nearly 10 years and picked up TrevTutor's Discrete Math series a few days ago prior to watching this. PS: same comment as Sheep44 -> I was surprised to see such an amazingly produced video for a sub-1000 subs channel!
Thank you! This was supposed to be self explanatory, which is why I included that brief description of sets. The outcome was more geared towards encouraging people to reframe problems in general rather than the introduction to and use of discrete maths and sets specifically. However, I do still see where you're coming from, so thank you very much for the feedback!
The only thing that differs this video from the ones with 6, 7 digits number count is lack of subtitles; however, your voice is so coherent that autogenerated subtitles get the job done.
Great to hear! Subtitles was one of those things I was concerned about and wanted to include, however this is all very new to me and I had far too little time to correctly set them up with my script. Glad to know the algorithm responsible for those subtitles understood me!
@@applemaths4062 Subtitles would go a long way in getting more people to watch your stuff. I myself have partial hearing damage, and at points I struggled to hear and parse what you said, but that's moreso on me than your voice being unaudible. If you end up making full subtitling on all your vids, I think you might just earn a sub from me
I would use a more versatile strategy, albeit maybe slow, that can solve the game optimally even when there is not enough information to surely advance. 1. List all the cases of arrangement of mines. 2. Remove the cases that don't match the numbers being shown on the tiles, as well as cases that don't match the number of remaining mines. 3. If a tile has mine in all of the remaining cases, that tile must have mine. If a tile doesn't have mina in any of the remaining cases, that tile must not have mine. If there is no tile found with those 2 searches, calculate the actual probability of each tile having mine, then open the tile with least probability of having mine. Theoretically, this is the strategy with the best win rate. To make it faster, we would: 1. Apply the basic strategies and other fast strategies while they can be applied. 2. Classify unknown tiles into neighbouring with at least a number, and not neighbouring any number. Then we only need to check all possible arrangements of mines in the neighbouring tiles; if we need to calculate probability, we can add "weight" for each arrangement of mines in the neighbouring tiles by the corresponding numbers of possible arrangements of mines in the non-neighbouring tiles (using the corresponding numbers of remaining mines).
after playing minesweeper for months out of boredom, i actually tried to make educated guesses to know if there's a mine or not using the logic of: "this tile is missing 2 flags; and the one next to it 1. Each of them with 3 neighbor tiles, so the tile further from the other missing one flag, must have a flag" it could be explained better, but i don't really know how. Ever since i aplied that logic i started to win more games, now i do runs where i don't even use flags and no automated clears, it's pretty fun!
That's probably the only difference from how I solve it naturally, like if you see a whole row of 2's you can pretty quickly work out that there's only two configurations, even though there's many tiles. Of course, I don't use sets at all, just outcomes.
Thanks for the comment! The situations where it mess up mostly fall down to getting unlucky and having to rely on random chance, and towards the end of the game where you need to start thinking about the total number of mines. I decided not to bring up these cases because the kind of strategy required to solve them strays a fair bit away from the approach in the video. Of course it would make it blatantly clear what the limitations are, but a deadline is a deadline so I only decided to mention them briefly in the summary. The agent I created for this does try to address these cases, but its approach to solving these problems are very primitive, and in my opinion not worth covering.
@@applemaths4062 Simon Tatham's version as part of the Portable Puzzle Collection throws out the element of chance by running a solver like described here (that also takes the number of remaining mines into account) when the player picks their first tile, shuffling the board if no solution can be found (or a mine would be revealed).
When I play minesweeper (and I play a lot of it) I use these strategies but I don't think of them as sets. Rather it's more like probability or maybe quantum superpositions. I mentally keep track of how many bombs would be in specific tiles and if I can gain information from that in any way. Say I know there's two mines in a set of three tiles near a tile denoted with a three. I then know for sure that the last mine is in whatever tiles are left. Sometimes you have to chain this together to get somewhere but it's still good to know
Hey! Great video, I quite liked the first principles approach to Minesweeper. However, while you did explain correct mathematics, I was quite confused by *why* the rule was correct. I kept not understanding what rule you were trying to express as a set problem. There lacked some kind of connector phrase of the kind "Ignoring flags, if you have as many empty cells only belonging to B as the difference between the value of B and the value of A, then those cells must have mines". Just a thought to improve your next video ;)
1:38 "In many problem solving fields, there exist so many problems which can be grouped together as functionally identical. For example, navigation software like what's available in google maps often uses the exact same strategy used by chess engines like Stockfish". I don't think navigation software uses the same sort of strategy as chess engines. My understanding is that the core algorithm in navigation software is A*, whereas the core algorithm in chess engines is MiniMax.
Yes you're right, but ultimately they're both variants of a tree search with different case-specific optimisations. That's why I made that comparison: In A* you're constantly trying to minimise, whereas in minimax you're acknowledging that your opponent is trying to do the opposite.
@@applemaths4062 Nitpick: they are both searching graphs, not trees. A tree has a unique path from the root to each node. Sure, I suppose they both follow the strategy of doing some sort of graph search. Here I'm really arguing about what words mean but... When you say "functionally identical" and "exact same strategy" what comes to my mind is the idea that you can take an off the shelf implementation of the same algorithm and then work around that algorithm e.g. represent board states as nodes in a graph. I'm not aware of an algorithm which is a generalization of MiniMax and A*, though I suppose I can imagine one(though I feel it would be overly general). I don't agree with the statement that MiniMax and A* are different sets of optimizations for the same base algorithm.
yes they are searching more abstract graphs, however they are ultimately tree searches. You can apply tree searches to less structured graphs, you just have a chance of getting stuck in a loop. That's why they're based on breadth first searches, where you're more likely to find a terminal state before getting stuck, and is also why they have a maximum search depth. I was aware of the caveat that they are _technically_ different, and had quite a hard time trying to come up with an example which wouldn't seem similar to the untrained eye while also being problems people were familiar with. I could have done the comparison of designing a swinging pendulum in a grandfather's clock to designing a bridge that won't shake itself to bits (where it seemed obvious the common starting point of working them out just comes from oscillation); or how the problem of the towers of Hanoi is mathematically equivalent to the problem of walking around some higher dimensional cube (which doesn't seem particularly useful). The generalised algorithm I was describing was simply a cost-dependent tree search, and I hoped that those familiar with the details would recognise the point I was making. You can take an algorithm for one, tweak it a touch, and end up with the algorithm for the other (ignoring the fact that problem specific optimisations can make them drastically different).
@@applemaths4062 fair enough, good examples to demonstrate your point aren't easy to list off the top of my head either. I just can't help but be pedantic, sometimes to the detriment of pedagogy.
Absolutely you can! With sudoku you can use sets to work out the possible moves for each tile, and use them to solve the board with a good old tree search. There's another algorithm with the amazing name "Knuth's Algorithm X" which can do it much faster using sets in a different way, although it's a bit harder to interpret.
the 20% winrate is all the times that can be solved only with those rules? including the first move ? i guess that it can't actually loose by stepping on a mine after the first move
yeah 20% includes all the "unfair" losses where it can't find a good starting point from the first move. When getting that number I did include the grace feature of "moving a mine if you just got unlucky on your first click", but of course sometimes that first move will show a cell of value "4" or something so it essentially needs to make another stab in the dark.
That is really close to how I play minesweeper This seems to be the case where you only consider if the mines cover the entire A/B and none in the other side But sometimes thinking about "then this set has 1 mine and this set touches this other one as well" works too
Awesome! This is exactly how I play, although writing it out formally like this has actually made me better at the game! What do you mean by "if the mines completely cover A\B"? Are you talking about if there's more than enough space in that set difference, the other is still safe anyway? I don't think that'd work, but I'm definitely interested!
Oh I think I get it, took quite a while to interpret but I think I got it: using the two 1s up top to deduce B has no mines because whatever mines are present have to be in A? That seems really promising, I'm not sure if the set difference strategy actually accounts for this! Thank you!
The number N on the board indicates that there are at least N mines in the neighboring cells. Hence, sometimes, when you think you have flagged all the mines, you fall into a trap.
I don't know what version of the game you've played but for standard rules that's not the case! The value of a tile equals exactly the number of mines within its 8 immediate neighbours. Granted there are moments where you need to rely on random chance, but I don't think the game is quite that unfair...
There is one more rule which is often implemented: If the first space that the player chooses is a mine, move that mine somewhere else on the board and return the new board configuration as if that first chosen space was not a mine.
What I would be really interested in would be to find some algorithm that tells you the highest EV guess. Because most Expert games of Minesweeper typically result in a board that you can't solve without having to guess a few fields. While guesses are typically equally likely to reveal a mine, some of them are more likely to prevent future guesses, maximizing the odds of winning. But besides considering every single configuration of the remaining mines, I really can't think of a strategy here.
Do these rules solve all (logic-only) games? I remember doing some hard minesweeper games where I had to make assumptions and follow them with quite a large number of sets(>2 as in the video). Was I just picking the wrong spot to analyze?
It obviously depends on the exact game, but doing it with just 2 sets is usually enough. Expanding the idea to three or four sets, although having the potential for much cleverer moves, is often times too much work for too little reward, so I didn't go into it
For people who are first hearing about or learning the rules of Minesweeper in this video, you should know that with most applications you use Minesweeper isn't always solvable, as in you can't always logically deduce the solution as there may be more than one and then you're forced to guess. Just thought of saying this since I didn't know it when I first learned and for a while spent a lot of time trying to figure out some configurations which I now know aren't solvable.
The real question I have about Minesweeper strategies is whether it is even possible to achieve 100% winrate - or are there situations where no matter the algorithm, you just cannot accurately determine the next mine location with certainty.
A few hours ago someone in this comment section posted a scenario where a 100% winrate is impossible. 2🚩33🚩2 2🚩××🚩2 1 mine left, all surrounding squares are cleared, and this is at the bottom of the board.
i figured out simpler version of smarter strategy by simple "what if" deduction (didn't understood almost any of the things about connection with sets though). but the final playthrough of the bot was still useful because i found the reverse of my strategy
That's fair, abstraction can definitely be a difficult to work with, it can really make it hard to interpret what you're really doing! I'm happy you made it at least that far, I hope you can get the gist of what the pairwise strategy entails!
That's a great algorithm for humans, but to increase probability of success finishing the game it will be better to use a computer specific algorithm. Best technic I can know of is to count all possible remaining mine positions and marking the most probable mine tile as "temporary mine". And so on. But, I guess probability of win can hardly up to 50%. It is really common thing on "Hard" when in the end you have two tiles with 50/50 probability which one is actually a mine.
My goodness yes! That final fifty-fifty accounts for so many of the losses, I wouldn't be surprised if it was the main cause. I chose this strategy specifically for the human accessibility, so I know for sure there's much better algorithms which are more of a "black box". That strategy of using probability calculations to make the statistically safest move every time is actually one I considered when the strategy in the video got stuck! However, computing those probabilities seems both very slow for an algorithm to work out and intimidating for me to work out considering I'm a bit rusty on conditional probability so I didn't get around to it. I'd love to see what that strategy would result in!
@@applemaths4062 actually it is really easy. You take all unknown tiles and try all possible locations of remaining mines. If certain configuration is possible you make +1 to all tiles containing mines. Configuration is possible if mine placement fits all known tile data. After you try all configurations -- tile with biggest number is the most probable mine placement. Of course there are a lot of possible optimizations, but it is an open question are they really needed.
Well yes, but the problem is that computing those permutations is EXP class, so way too slow to have any sort of efficiency. Starting with the information you have first will probably work faster and even then optimisations are sorely needed.
For decades, I never understood how to play Minesweeper. In 40 seconds, you explained it in a way I understood for the first time and I actually won a game for the first time in my life. Thank you.
Decades? Bro... It took me like 10 mins to learn... alone... when I was 8...
@@Logia_ Come on, you know what they probably mean is they tried it once, didn't get it at first, and then never touched/thought about it again until now. Not that they've spent decades trying to figure it out.
@@Logia_ I was a stupid kid. I would just click on boxes around the numbers. I started on Microsoft 3.1. There wasn’t a tutorial. There weren’t instructions. All I saw were boxes that would occasionally explode. For my 8 year old mind, it seemed to be luck based. I figured out that the numbers meant “3 means don’t click within 3 squares,” but I never understood that meant “3 squares in this 3x3 grid are mined,” I assumed it was like a plus shape. Sometimes it worked, sometimes it didn’t. I never won a game, I’d only get it to a few squares left unclicked and at that point it was random chance in my mind because I couldn’t figure out the pattern. By Windows 95, I had just given up. It was random to me. In the old days of TH-cam, there was a “Minesweeper: The Movie” parody trailer that sort of explained it and I still didn’t get it. It was only 2 weeks ago that someone actually explained it in a way I understood.
I did have a learning disability back then, if that makes it more clear. I preferred Solitaire, Mahjong, SkiFree, and Pinball.
@Vins wow such big epeen
In the late 1990s I actually wrote a Java applet to play and solve minesweeper, capturing all these strategies that you discussed. Pretty much used the same ideas you did. These days, I'm wondering if a deep learning neural net could do better somehow.
How very interesting! I specifically chose a strategy which is fairly intuitive and doesn't require much computation. So just like I say towards the end of the video I have no expectations of this being an optimal method, just a good enough one you can use yourself. Sure machine learning will probably net you a pretty strong agent but I suspect some sort of strategy based in information theory will be just as powerful with far less "unusual behaviour" so to speak. Thanks for the input!
I don't know if deep learning can come up with an optimal algorithm, but we can do just with brute force, and that approach is surprisingly practical. th-cam.com/video/cGUHehFGqBc/w-d-xo.html Note that there is no "perfect" algorithm for Minesweeper, as there exist arrangements that cannot be solved without guessing.
Deep learning is huge overkill for this and not really appropriate. Minesweeper is crying out for a rules based system as discussed - highly discrete and only a tiny number of choices to consider
@@TAP7a Minesweeper is NP complete and thus any such rule system must come with a caveat. I see two possibilities (maybe I'm missing some):
* The number of rules depends on the board size, and grows exponentially
* There are rules for which checking if they can be applied takes an exponential amount of time
Actually it's easy to come up with a system (actually consisting of just just one rule) that fits the latter:
- Consider all possible Minesweeper boards with the same size and number of mines as the board we are solving
- Build a set S of all boards that agree with our current game state (i.e., a board B is in S iff all open cells in our game have the same number in B, and all cells we flagged are mines in B)
- For each cell that is a mine in each board in S, it is a mine in our game
- For each cell that is safe in each board in S, it is safe in our game
Here, S is exponential in size, and thus this rule takes exponential time to apply.
Minesweeper is such a simple game that it's fairly straightforward to come up with an algorithm which plays perfectly, you don't need neural networks or any AI trickery at all. You just take the algorithm in the video and compute statistics about where the remaining mines are most likely to be and which cell is most likely to reveal the non-mined cells. I'm not sure how much computing power this will require on large boards though, it might be more efficient to immediately click on the cells which are 100% guaranteed to not have mines on them and only compute more complicated statistics if necessary.
Even a perfect player will need to gamble if there are enough mines though, so you can never guarantee the board is solvable
I remember back then trying to memorize mine configurations like 1 2 1, 2 2 1, ect. and never wondered why... This is a way more logical approach.
Thank you! I think this approach will actually net you more patterns than just memorising what works, it certainly did for me!
Configurations are faster but require more memorization.
An algorithmic approach like this requires more brain juice and is not as fast and obviously, it will repeat the same calculations even if the pattern has already been solved BUT the big advantage is that it doesn't need you to spend hours memorising the patterns.
Wait 0 exist in mineswipeer?
@@Shio_Saganelidze yes and no, zeros are the "blank spaces" wich are the ones with no number
@@Shio_Saganelidze also the game auto click or open them automatically
It took me 6 minutes to realize this random video bestowed upon me by The Algorythm is actually teaching me math. And then suddenly programing. If only it was this entertaining when I was learning.
Elementary Set theory!
I watched this entire video with the automatic assumption based on the quality that you must have had hundreds of thousands of subscribers, and I was just about to click off before I noticed you don't even have a thousand! I had to stop to just say how incredibly well done this, it's almost like watching 3b1b, I hope you keep making more videos!
Thank you very much!
To be frank, a lot of that quality probably just comes down to how great of a tool manim really is. 😂
I have to agree with @Sheep44. I wasn't expecting set theory, and was pleasantly surprised with its application to minesweeper. It even helped me understand it better. I also hope you keep making more videos.
Same! This was an amazing explanation and great video overall
I noticed that he has only a thousand but it's very well done, I think we are witnessing the start of a great channel
@@applemaths4062 Nice work on the video quality.
2:50 And you've just clarified which symbol is which for me. Union has the U, iNtersection has the N. Very helpful mnemonic!
I already know how to play minesweeper, but I feel like if I didn't, this would teach me very quickly. Nice job!
need more videos that explains programs/algorithms using pure mathematical approach, Subscribed to your channel and i hope it grows more.
Grant really did a huge contribution helping and encouraging great channels like this one
You made me actually want to play minesweeper again never really thought of using sets to help solve the game.
Oh awesome! Honestly I got this strategy by working out what it is I'm doing when I play, and ended up with something a whole lot better! It's a shame I couldn't get around to mentioning the more unique patterns where this approach gives you loads of information despite seeming like there's none to uncover. Thanks very much!
I loved your video! I took a very similar approach when I started making a solver for the minesweeper variant game called Tametsi. I also used sets to describe sets of unknown neighbors and overlapped them in a second step after I applied the first two rules about being full and empty. I’m so happy to see that someone else came to a similar conclusion on their own.
Something I did for tametsi that I didn’t see you describe here, was define the number of mines in a set as a set of possible sums of mines, rather than as a single sum. In tametsi this was a required step. You could deduce information from whether two cells had one or two mines and not zero, or zero or one mines and not two.
Tametsi has the added bonus that all puzzles are deterministically solvable and premade by hand, so it could test your solver very effectively.
How very interesting! It's not a game I've personally heard of, but I'm interested to take a look!
You just made me solve minesweeper. Something I really wanted to do for a long time. Even though it was on easy mode I still did it. Thank you.
My brother get yourself a half decent microphone and your channel will become a goldmine. Good job mate 👍🏻
Thanks very much! Will get to it once I get the chance!
@@applemaths4062 In the mean time, pass an Lowpass filter through audacity with a frequency of 12kHz and it will remove a lot of the whines the microphone introduces.
@@applemaths4062 yes, you can actually record a sample of the noise in the starting (i.e. idle recording of 5s before you start speaking - assuming the noise level in sorrounding stay roughly same), then subtract that from the recording throghout to denoise
lol it feels like every time he said "s" the audio gets amplified +46dB
@J.Azz. Woods Ooh that's a good idea! Thanks very much, I will definitely give that a try at some point. I must admit, even though I know a fair bit about audio in theory, I haven't done much with it in practice. Video production is definitely a beast of a learning curve!
Videos like this make timeless channels that everyone loves like minutephysics and veritisium
Ferb, I know what we are gonna this weekend!
Everything aside though, this is a banger start to a new channel, subscribed! I hope you make more content!
THIS TUTORIAL REALLY WORKS I AM FROM PHILIPPINES! THIS MAN DESERVES A SUBSCRIPTION!
The animations are so fuckin smooooooth, I kept thinking about that!!! I can’t wait for you to blow up in subs and all the analytics goodies man, keep up the good work!!!!
And I also whole heartedly agree with the 3b1b comparison in one of the comments!!
I learned playing minesweeper by common understanding, practice and no mathematic means, and has beated the game several time in hardest mode. But watching this video is interesting to know there's mathematical way to understand and play the game.
Good vid
Oh ho ho, you almost got me there. I WILL NOT BE TRICKED INTO LEARNING A SINGLE THING ABOUT SET THEORY.
What's the problem? It's the mathematical equivalent to a box of unloved wires: it's never organised, and you don't care about duplicates - you either have the one you want or you don't! 😀
I got 6 minutes in before my brain hurt too much to keep going, I'm not smart enough for this lmaooo; great video, lovely production quality
Really enjoyed this video. Nice work!
Great video. Always a pleasure to see someone use manim so beautifully.
This was awesome! Hope your channel blows up :)
With your videos my learning curve will shrink drastically. Thank you.
I'm a doctor. Never liked math. Felt math had no reality application. U proved me wrong at many levels. Kudos 👏
lol it's pretty ironic to me how an algorithm that solves a 33 years old obscure game is enough to "prove you wrong" but the device you used to write this comment on isn't.
It's always nice to see a video on minesweeper :)
I've played it quite a bit, and there are certainly more effective methods available than the one showcased here (especially when it comes to counting remaining mines), but it's a very interesting starting point, as it describes how we can turn the game into a purely mathematical problem. What I'm interested in about this algorithm that I don't think was specified: are you running the algorithm on boards that are always solvable, or are you running the game on boards where even an optimal strategy would be forced to guess a value at some point?
Thanks very much!
Great question! The implementation of the minesweeper clone I created for the AI is very bare bones so no. In fact, it didn't even make sure the first move was safe originally! Essentially as this strategy could do something in the order of 50 boards per second, I just ran it over and over again until I had an interesting layout that clearly demonstrated the relevant problems and how this strategy overcame them in an obvious way. I'll probably put it up on GitHub if I get around to doing some code sanitising!
What methods (to find mines) do you have in mind?
Of the top of my head I only recall two other rules: 1) in a line of ones (such as a line starting at the edge of the board) the third one is safe and 2) that a line of ones interrupted by a single 2 means that the square directly next to the 2 (to its side or above/below it) is safe, i. e. the two neighbouring squares are mines.
@@xCorvus7x Most of the methods I use are things I've just come up with as I solved more and more of these puzzles. Not completely remembering everything presented in the video right now, there are several useful rules beside the 1-2-1 rule that is the most commonly used one. For instance, if we have a row/column with the numbers 1-2-2-1 then we know that there are exactly 2 mines located right next to the 2's, and in certain cases if we have a 1-1-1 configuration we know that the mine is next to the 1 in the middle. Counting arguments are also really powerful, as they can be used effectively in later stages of solving a mine field for ruling out specific potential mine configurations based on how many mines are left and in which general regions the remaining mines have to be distributed.
Of course you must guess, or you can never start
Minesweeper would be a huge optimisation problem for sure. In random maps, the script would need to look for the starting location with the highest probability of winning (the corners have a higher chance of survival, meanwhile the centre has the highest chance of bigger openings). General minesweeper strategy is to always take any forced guesses as early as possible so that less time is wasted on runs. And there are even more difficult optimisations like mine counting and finding probabilities in situations. There is also the concept of an 'optimal move' using chording. Placing a flag next to a 1 and then chording it only takes 2 clicks, while clicking the mines next to the 1 would take longer. In other situations it would be better to not place any flags and just open the safe tiles.
I sorta understand the ideas, which I should be more familiar with either way since I'm a computer science major. But man the production quality of this video is crazy good for below 100 subscribers! I hope this channel grows!
Thank you very much!
idk why, this video is sooo satisfying.
This is very cool, I really thought that first board was going to force you to click the tile that's most likely safe, and that it was a gamble, but I was wrong. You can deduce enough information from those tiles to actually clear the whole board! Awesome!
i enjoy coding so breaking it down into code did actually help me as I can visualize what to do when something happens. i right most of my notes in a sudo code like structure using the common if, if else, and for loops cause those were what I learned on .
Very helpful, and surprisingly therapeutic
The first time in my life I learned how to play it. When I was 12 I used to click at random places exploding the bombs and thought I won. LOL
Really fun video, and it’s come into my feed so hopefully it’ll go into some other STEM enthusiasts on YT, you clearly have a passion for this type of thing, and a knack for good video presentation.
I think the main recommendation would be to get a better mic, and maybe add some light background music, it doesn’t have to be strong or loud, but often helps viewers deal with silence between your audio. Also a slightly better mic will be able to isolate out your voice from mouse clicks which were done to trigger animations during recording.
Really fantastic stuff though overall and I’m looking forward to hearing/seeing more of your stuff in the future 😁
10/10 for the animations and the script. Like @Sheep44 it is almost like watching 3b1b. Very interesting concept aswell. I just think that you should invest in a better mic for improved sound quality. It’s not a distraction by any means but I think it would make the vids seem more professional. If you keep making videos like this you can probably expect at least 100k in a year or so. I’m excited to check out the rest of your channel! You just gained a new subscriber😀
Wow that's an ambitious prediction! Thanks very much, I'll get to making the investment when it's feasible.
1:50 Divide and rule
great thanks for that! Very clear and articulate!
Amazing video! Always nice to see videos on minesweeper
Very interesting video. 👏👏👏 Pros to you for showing the maths behind minesweeper but it's much easier to learn patterns. 🤣👍Looking forward to more vids from you
Thanks very much! At least hopefully you can see why the patterns work and maybe find your own... 🤔
@@applemaths4062 yeah I loved the visualization of the grid as the board was getting solved. 💯
Thanks! I have linked the source code to the agent in the description which, if you're confident with a command line, you can use to automatically generate more of the visualisations like the one at the end of the video!
@@applemaths4062 OH thx!!
how dare you make me thoroughly entertained by mathematical terminology. how dare you.
This is wonderful, I finally know the rules of the game.
this made me so much better at minesweeper
A powerful algorithm could work as following:
Identify all possible combinations of mine placements for a given board and use that to calculate the probability of each tile being a mine. If any tiles are 100% or 0% click them or flag them and repeat the process. If no tiles are 100%/0%, click the one with the lowest probability of being a mine and restart the algorithm. It's not optimal because it doesn't account for how likely the board is to be solvable after guessing which it should take into account when chosing a guess, but it's probably close.
In theory yes, that is one of the approaches I'd absolutely consider. In fact it's what I tried taking a look into for when the algorithm I had got stuck. However, I've got a feeling that that probability calculation would be *very* expensive and convoluted unless there's some clever transformation you can do to make it into a matrix multiplication or something. Not to say it's not worth looking into!
I actually used the most watered down version of this when my agent got stuck, using the sets I already had a hold of with the strategy in the video, clicking the tile with the lowest probability of being a mine. Sure it's not great, but it was enough for me to explore the situations the agent could end up in and iron out the bugs!
Thanks very much for the input!
@@applemaths4062 it is a deceptively hard problem. I don't believe it can be solved without enumerating a large search space.
I applied the above algorithm and even applied set theory logic for a simulation but it was unable to solve the board nearly half of the time in simulation. There is a need to properly use more information gained from the board while solving every next tile.
You and fans of this video would love the computer game Bombe, where you use Venn Diagram rules to automatically solve Minesweeper variants.
How soldiers minesweep: Cautiously looking at the ground and disarming mines.
How people minesweep in computer: *Math intensifies*
Quality video. I hope you continue to post :D
I've been playing a version of Minesweeper called Bombe - if you enjoy this idea of building rules that solve Minesweeper, you might appreciate it!
I came back to this video after seeing bombe
I dont really understand this, but I'll try to learn some discrete maths. Really nice video
I should start by saying this is much nicer than most Minesweeper videos I have seen. A lot of people discuss Minesweeper strategy as strategy, but the discussion of it as mathematical or even algorithmic is nice and concrete as a model. However, you've not solved Minesweeper in any of the ways which are meaningful to solve Minesweeper. From my perspective, the great pillars of Minesweeper analysis are as follows: high accuracy strategy with a focus on using probabilistic methods to determine the best guess at any point on a board where a guess is required to progress, minimal click strategies with a focus on things like information theory and how much a strategy is likely to reduce the uncertainty of the board and which mines aren't worth flagging and which are, and then the development of speed strategy for humans and things like powerful visual patterns and applications of mouse tricks. Codifying the rules and most basic techniques of Minesweeper is something of a beginner project, and you see it done a lot, but it's not the interesting part by a long shot. It's like a chess engine which can find a legal move, or a sudoku solver which scans rows and columns the way my mom does.
First of all, thank you! I thought it was a fairly good choice as a problem I can abstract into very few very simple mathematical objects, and I therefore really appreciate the compliment!
I came into this project with the intention of doing very little research. I thought I'd give a unique perspective to, and hopefully teach, a strategy with significant efficiency and hopefully simplicity which I was familiar with. That's why I didn't bother with the flood fill most implementations bother with whenever you click a zero, and is why I thought it best to just flag everything. Granted "How do you _solve_ Minesweeper" was a pretty misleading choice of words, especially for those who are already familiar with everything I mentioned in the video, but for the audience I was targeting - those with little confidence with either the game, or the mathematical description I supplied, or just problem solving in general, I personally thought it was adequate, as it was a passion project of mine turned into a simple lesson about problem solving.
Now that's not to say I didn't consider some of the more advanced things you can do with the game, such as construct a probability field of mines at each position in the grid, or how you could use information theory or constraint satisfaction algorithms to solve a board with a million tiles in only a few milliseconds, but I decided not to include them, partially due to the limited time constraints for SoME, but also because they were much harder to visualise in this way, and I have far less confidence with them: it would have turned a 2-3 month video project into a 4-6 month programming project which would have only been seen by a half dozen or so programmer friends instead of thousands who could genuinely have learned something from it.
Personally, I think that comparison to verifying the validity of a move in chess or finding the possible available options in sudoku is quite harsh. Although yes it will probably come out to a similar number of lines of code, that doesn't mean there's a similar amount of thought or complexity within. In those two examples, you're writing code that essentially enforces a set of rules you read out of a book, whereas the strategy I described in the video is based on a few simple but clever observations about how the mine counts of neighbouring cells interact with each other. I do still see what you mean, it is a very primitive strategy, but a win rate of 20% in a game which requires you to cross your fingers and hope for the best half the time is not as insignificant as the rules of the game in terms of creating an agent.
Don't take it like I think you're spouting rubbish, because I absolutely see where you're coming from! Creating an optimal strategy, both in the case of an abstract agent on a computer and a strategy humans can keep in their heads and execute quickly, is miles above and beyond what I've described. However, as I only play the game recreationally and the video was supposed to be approachable to many, I don't think working something like that in would be appropriate.
@@applemaths4062 I suppose through this lens of "a good video for SoME which uses set theory to help us grapple with a complicated but familiar problem", surely all your boxes are checked. As a video discussing Minesweeper, I think most do it in this no research, from the ground up sort of way, but the math is certainly a nice touch.
Perhaps I am projecting too much, but it reminds me very much of the "Sudoku solver" I wrote in high school. I implemented a few intuitive strategies about scanning and elimination, things of course that followed directly from the rules but were not rules, and it could solve "easy and medium" puzzles from my test bank. Learning about Knuth solving the problem with dancing links but a bit of a hamper in my pride, and then doubly so as I became more familiar with what an interesting sudoku is and is not, what their solution paths look like, what happens in the mind of an experienced sudoku solver and how grossly different it is from brute forcing pattern checks in order of increasing complexity. I guess what the comparison is meant to highlight is that, rather than some simple but intuitive implementation of a solution to a complicated problem, you have created a simple and intuitive implementation of a simplified problem, one which is rough and mechanical in its methodology, one which is making far more observations and deductions than any human would need to, a video which is less about solving or even playing a game and more about a grand and valuable set of computations on a Minesweeper board.
I fully acknowledge at least some of this is totally unfair, but it is such a strong and intuitive urge in me to keep going from here that I hate to see people stop at this sort of stage. All of this, I suppose, in hopes of inspiring a deeper dive.
Yeah I have to agree with you, this is a problem where most people are going to be satisfied with the first non-trivial strategy, which is certainly what I've supplied; not doing any research and doing the first clever thing that comes to mind.
I absolutely see what you mean with that sudoku solver. In fact, one of my Artificial Intelligence units at university requested I create such an agent! I tried to optimise it by using whatever shortcuts I was aware of, but ended up slowing the whole thing down! Going the wrong route first time in a constraint satisfaction algorithm is not as bad as adding extra tree pruning checks which only get used a couple of times. I loved the look of Knuth's Algorithm X (still can't get over how cool of a name that is), and you bet I tried my hardest to recreate it! (sadly the initial problem matrix setup took way too long...)
If I'm interpreting your words correctly then yeah! This was supposed to be a general lesson in problem solving by simplifying the problem into something much more manageable and attacking the problem at a different angle through those abstractions. It's a very algorithmic strategy, which fits in that gap between what a casual player would be able to notice in terms of patterns and what the computers do using their black box algorithms. It doesn't "solve the board" by any means, but it does push most people in the right direction, giving them more opportunity to recognise new patterns!
I understand the urge, there is a lot of potential in what you can do with this game, and I too would be understandably disappointed in your position! However, as you said, this was meant to be a good introductory style SoME submission, so the time constraints really limit how far I can go. I'd love to see it investigated further in this way, see more of what can be done, so if someone wants to give it a go they have full encouragement and support from me that's for sure! If I'm going to revisit it, it'd have to be a little ways down the line. I have some other ideas and I don't particularly want to be known as the minesweeper guy! Thanks for keeping it constructive, heck, commenting at all; it means a lot!
I thought this was a minesweeper tutorial for people that didn't know how to play minesweeper, and instead was given a great lil math lesson.
short answer: git gud
btw, when the smarter strategy section came up (which i had skipped to after basic) i immediately knew what to do and was pleased to see the same thing being done but with formal terms
damn,
I just yesterday thought about searchin for strategies I might missed.
Thank you!
it's a bit spooky, tho))
Thanks to the ridiculous numbers in combinatorics, it's bound to happen once!
I can see some Potential in this channel. So Imma subscribe
I think 5:45 is where knowing math terms helps big time, even then had to re-watch and listen a few times... i seriously hate Maths terms and think the industry has a usability problem that stems from 100 of years ago... I can't think of anything better however! Nice vid.
That is a brilliant point, I never even considered that! Terminology has perhaps the worst form of the curse of knowledge; really slow and obnoxious to learn, really trivial looking back. This is really helpful, I'll absolutely try to incorporate that in future. Thanks very much!
5:18 bonus content: the intersection of rhythm and blues.
A better algorithm would be to prioritize solving the 1s since they almost always yield more cleared tiles.
Meanwhile, your set solving strategy is good and I use it too but as others have said, it should be paired with pattern recognition since it is more efficient since you don't have to do the same operation over and over again.
Finally, a proper algorithm should be able to backtrack and go over previous unsolved tiles since the nature of the game unlocks more clues on previous tiles the closer you get to the end.
Reasonable observations, thank you!
When describing the agent, I specifically chose to avoid mentioning any sort of order of operations. Yes this can absolutely be improved by changing where you perform this analysis, however deducing a good ordering for which cells to do this with is too expensive to justify in the case of a computer playing, and for a human player, this prioritisation is either already employed or can be picked up by intuition. In the examples in the video, I chose the ordering myself to demonstrate my ideas, and the agent which plays the game at the end of the video is designed in a way where it inevitably will perform some backtracking.
Concerning pattern recognition, yes of course that can make the game easier, however this approach in practice would be more of a way of generating patterns you can use. Talking about patterns doesn't provide any interesting insight as to why they work, whereas providing a way of generating them is far more valuable if someone wants to learn to be good at games like this. Rote memorisation of patterns will get the job done, and is indeed the best choice for learning to be fast at it, but it is perhaps the least helpful way of learning. Granted I could have gone through more examples and show off why some other more unique patterns work, which I apologise for, however there will always exist prospective improvements to a project like this.
Beautiful video!
As an asterisk, many non-math literate viewer might benefit from a quick link to an intro to discrete math if they want to look further into this.
Myself, I hadn't done any math in nearly 10 years and picked up TrevTutor's Discrete Math series a few days ago prior to watching this.
PS: same comment as Sheep44 -> I was surprised to see such an amazingly produced video for a sub-1000 subs channel!
Thank you! This was supposed to be self explanatory, which is why I included that brief description of sets. The outcome was more geared towards encouraging people to reframe problems in general rather than the introduction to and use of discrete maths and sets specifically. However, I do still see where you're coming from, so thank you very much for the feedback!
The only thing that differs this video from the ones with 6, 7 digits number count is lack of subtitles; however, your voice is so coherent that autogenerated subtitles get the job done.
Great to hear! Subtitles was one of those things I was concerned about and wanted to include, however this is all very new to me and I had far too little time to correctly set them up with my script. Glad to know the algorithm responsible for those subtitles understood me!
@@applemaths4062 Subtitles would go a long way in getting more people to watch your stuff. I myself have partial hearing damage, and at points I struggled to hear and parse what you said, but that's moreso on me than your voice being unaudible. If you end up making full subtitling on all your vids, I think you might just earn a sub from me
This game is so weirdly addicting. It's so elegantly simple but complicated
I would use a more versatile strategy, albeit maybe slow, that can solve the game optimally even when there is not enough information to surely advance.
1. List all the cases of arrangement of mines.
2. Remove the cases that don't match the numbers being shown on the tiles, as well as cases that don't match the number of remaining mines.
3. If a tile has mine in all of the remaining cases, that tile must have mine. If a tile doesn't have mina in any of the remaining cases, that tile must not have mine. If there is no tile found with those 2 searches, calculate the actual probability of each tile having mine, then open the tile with least probability of having mine.
Theoretically, this is the strategy with the best win rate.
To make it faster, we would:
1. Apply the basic strategies and other fast strategies while they can be applied.
2. Classify unknown tiles into neighbouring with at least a number, and not neighbouring any number. Then we only need to check all possible arrangements of mines in the neighbouring tiles; if we need to calculate probability, we can add "weight" for each arrangement of mines in the neighbouring tiles by the corresponding numbers of possible arrangements of mines in the non-neighbouring tiles (using the corresponding numbers of remaining mines).
after playing minesweeper for months out of boredom, i actually tried to make educated guesses to know if there's a mine or not using the logic of: "this tile is missing 2 flags; and the one next to it 1. Each of them with 3 neighbor tiles, so the tile further from the other missing one flag, must have a flag" it could be explained better, but i don't really know how. Ever since i aplied that logic i started to win more games, now i do runs where i don't even use flags and no automated clears, it's pretty fun!
Great vid, hope the best for you
I like your set theory approach! It could be generalized beyond 2 sets though
Yes it could! I considered doing that actually - trying three, four sets - however it seemed that it was too much work for too little benefit.
That's probably the only difference from how I solve it naturally, like if you see a whole row of 2's you can pretty quickly work out that there's only two configurations, even though there's many tiles.
Of course, I don't use sets at all, just outcomes.
Me who plays minesweeper but watches minesweeper ideas really says something
Well Made! It would be nice if in a next video you talk about how to solve Sudoku
Lovely video, where are the next ones? I can't wait to see what topic you'll focus on in the future
would be cool to see some situations where it failed, to see if there’s anything that could be learned from its limitations
Thanks for the comment!
The situations where it mess up mostly fall down to getting unlucky and having to rely on random chance, and towards the end of the game where you need to start thinking about the total number of mines. I decided not to bring up these cases because the kind of strategy required to solve them strays a fair bit away from the approach in the video. Of course it would make it blatantly clear what the limitations are, but a deadline is a deadline so I only decided to mention them briefly in the summary. The agent I created for this does try to address these cases, but its approach to solving these problems are very primitive, and in my opinion not worth covering.
@@applemaths4062 Simon Tatham's version as part of the Portable Puzzle Collection throws out the element of chance by running a solver like described here (that also takes the number of remaining mines into account) when the player picks their first tile, shuffling the board if no solution can be found (or a mine would be revealed).
As a child, I beat minesweeper, on windows 7, without even knowing how to play the game, or without any help. I still feel proud.
When I play minesweeper (and I play a lot of it) I use these strategies but I don't think of them as sets. Rather it's more like probability or maybe quantum superpositions. I mentally keep track of how many bombs would be in specific tiles and if I can gain information from that in any way. Say I know there's two mines in a set of three tiles near a tile denoted with a three. I then know for sure that the last mine is in whatever tiles are left. Sometimes you have to chain this together to get somewhere but it's still good to know
Hey! Great video, I quite liked the first principles approach to Minesweeper. However, while you did explain correct mathematics, I was quite confused by *why* the rule was correct. I kept not understanding what rule you were trying to express as a set problem. There lacked some kind of connector phrase of the kind "Ignoring flags, if you have as many empty cells only belonging to B as the difference between the value of B and the value of A, then those cells must have mines". Just a thought to improve your next video ;)
aha i love that i learned how to play this on my own during my developmental years and have no recollection of not understanding wth this means
1:38 "In many problem solving fields, there exist so many problems which can be grouped together as functionally identical. For example, navigation software like what's available in google maps often uses the exact same strategy used by chess engines like Stockfish".
I don't think navigation software uses the same sort of strategy as chess engines.
My understanding is that the core algorithm in navigation software is A*,
whereas the core algorithm in chess engines is MiniMax.
Yes you're right, but ultimately they're both variants of a tree search with different case-specific optimisations. That's why I made that comparison: In A* you're constantly trying to minimise, whereas in minimax you're acknowledging that your opponent is trying to do the opposite.
@@applemaths4062
Nitpick: they are both searching graphs, not trees. A tree has a unique path from the root to each node.
Sure, I suppose they both follow the strategy of doing some sort of graph search.
Here I'm really arguing about what words mean but...
When you say "functionally identical" and "exact same strategy" what comes to my mind is the idea that you can take an off the shelf implementation of the same algorithm and then work around that algorithm e.g. represent board states as nodes in a graph. I'm not aware of an algorithm which is a generalization of MiniMax and A*, though I suppose I can imagine one(though I feel it would be overly general).
I don't agree with the statement that MiniMax and A* are different sets of optimizations for the same base algorithm.
yes they are searching more abstract graphs, however they are ultimately tree searches. You can apply tree searches to less structured graphs, you just have a chance of getting stuck in a loop. That's why they're based on breadth first searches, where you're more likely to find a terminal state before getting stuck, and is also why they have a maximum search depth.
I was aware of the caveat that they are _technically_ different, and had quite a hard time trying to come up with an example which wouldn't seem similar to the untrained eye while also being problems people were familiar with. I could have done the comparison of designing a swinging pendulum in a grandfather's clock to designing a bridge that won't shake itself to bits (where it seemed obvious the common starting point of working them out just comes from oscillation); or how the problem of the towers of Hanoi is mathematically equivalent to the problem of walking around some higher dimensional cube (which doesn't seem particularly useful).
The generalised algorithm I was describing was simply a cost-dependent tree search, and I hoped that those familiar with the details would recognise the point I was making. You can take an algorithm for one, tweak it a touch, and end up with the algorithm for the other (ignoring the fact that problem specific optimisations can make them drastically different).
@@applemaths4062 fair enough, good examples to demonstrate your point aren't easy to list off the top of my head either. I just can't help but be pedantic, sometimes to the detriment of pedagogy.
thank you man,you are a legend
2:36 I want a set of all sets that don't contain themselves as elements
404 not found
Amazing video! I really enjoyed it.
Excellent video ...............................Thank You !!!
great video bestie 💅✨ slayy! ✨✨☺️☺️☺️
I really enjoyed this video
Great video! I want to write a program to play the game board clue and I think this video will help me a lot
Such a great video!
there's also cases when you can't get complete information and must do probabilities to get the best chance of not losing
Very nice. I have subscribed you, expect more videos like this.
Thanks for the educational video, might i ask how did you make this presentation? Which app
Will start to learn it tomorrow, lets be patient pips! Godbless us haha
interesting hearing all the strategies i use simplified into maths
Very interesting. I wonder if its possible to use sets or a strategy similar to this with sudoku?
Absolutely you can! With sudoku you can use sets to work out the possible moves for each tile, and use them to solve the board with a good old tree search. There's another algorithm with the amazing name "Knuth's Algorithm X" which can do it much faster using sets in a different way, although it's a bit harder to interpret.
I am afraid when i am in the corner and there is "1" and "2", pointing at the same area of 2 tiles. It's 50/50.
the 20% winrate is all the times that can be solved only with those rules? including the first move ? i guess that it can't actually loose by stepping on a mine after the first move
yeah 20% includes all the "unfair" losses where it can't find a good starting point from the first move. When getting that number I did include the grace feature of "moving a mine if you just got unlucky on your first click", but of course sometimes that first move will show a cell of value "4" or something so it essentially needs to make another stab in the dark.
That is really close to how I play minesweeper
This seems to be the case where you only consider if the mines cover the entire A/B and none in the other side
But sometimes thinking about "then this set has 1 mine and this set touches this other one as well" works too
Awesome! This is exactly how I play, although writing it out formally like this has actually made me better at the game! What do you mean by "if the mines completely cover A\B"? Are you talking about if there's more than enough space in that set difference, the other is still safe anyway? I don't think that'd work, but I'm definitely interested!
@@applemaths4062 I think they mean
[B][1][A][1][0]
[B][1][A][2][1]
[ ][ ][ ][ ][ ]
Apologies for the slightly wonky graphic
Oh I think I get it, took quite a while to interpret but I think I got it: using the two 1s up top to deduce B has no mines because whatever mines are present have to be in A? That seems really promising, I'm not sure if the set difference strategy actually accounts for this! Thank you!
@@applemaths4062 tbh I wrote it at like 3 am my time and I have no idea what I meant, sorry 😐😅
Ooh! Minesweeper! And a letter pfp! 😊
The number N on the board indicates that there are at least N mines in the neighboring cells. Hence, sometimes, when you think you have flagged all the mines, you fall into a trap.
I don't know what version of the game you've played but for standard rules that's not the case! The value of a tile equals exactly the number of mines within its 8 immediate neighbours. Granted there are moments where you need to rely on random chance, but I don't think the game is quite that unfair...
Very nice!
Damn this made me interested to mine sweeper been avoiding on from my windows xp for years because i cant understand it
There is one more rule which is often implemented: If the first space that the player chooses is a mine, move that mine somewhere else on the board and return the new board configuration as if that first chosen space was not a mine.
What I would be really interested in would be to find some algorithm that tells you the highest EV guess. Because most Expert games of Minesweeper typically result in a board that you can't solve without having to guess a few fields. While guesses are typically equally likely to reveal a mine, some of them are more likely to prevent future guesses, maximizing the odds of winning.
But besides considering every single configuration of the remaining mines, I really can't think of a strategy here.
Do these rules solve all (logic-only) games?
I remember doing some hard minesweeper games where I had to make assumptions and follow them with quite a large number of sets(>2 as in the video). Was I just picking the wrong spot to analyze?
It obviously depends on the exact game, but doing it with just 2 sets is usually enough. Expanding the idea to three or four sets, although having the potential for much cleverer moves, is often times too much work for too little reward, so I didn't go into it
For people who are first hearing about or learning the rules of Minesweeper in this video, you should know that with most applications you use Minesweeper isn't always solvable, as in you can't always logically deduce the solution as there may be more than one and then you're forced to guess. Just thought of saying this since I didn't know it when I first learned and for a while spent a lot of time trying to figure out some configurations which I now know aren't solvable.
Someone help, he's teaching me linear algebra again!
The real question I have about Minesweeper strategies is whether it is even possible to achieve 100% winrate - or are there situations where no matter the algorithm, you just cannot accurately determine the next mine location with certainty.
A few hours ago someone in this comment section posted a scenario where a 100% winrate is impossible.
2🚩33🚩2
2🚩××🚩2
1 mine left, all surrounding squares are cleared, and this is at the bottom of the board.
i figured out simpler version of smarter strategy by simple "what if" deduction (didn't understood almost any of the things about connection with sets though). but the final playthrough of the bot was still useful because i found the reverse of my strategy
actually, i was using that reverse strategy but didn't realized how much often it can be used
Great video, but you lost me somewhere around 7:00. When things get too abstract, I just tend to not follow anymore.
That's fair, abstraction can definitely be a difficult to work with, it can really make it hard to interpret what you're really doing! I'm happy you made it at least that far, I hope you can get the gist of what the pairwise strategy entails!
That's a great algorithm for humans, but to increase probability of success finishing the game it will be better to use a computer specific algorithm. Best technic I can know of is to count all possible remaining mine positions and marking the most probable mine tile as "temporary mine". And so on. But, I guess probability of win can hardly up to 50%. It is really common thing on "Hard" when in the end you have two tiles with 50/50 probability which one is actually a mine.
My goodness yes! That final fifty-fifty accounts for so many of the losses, I wouldn't be surprised if it was the main cause. I chose this strategy specifically for the human accessibility, so I know for sure there's much better algorithms which are more of a "black box". That strategy of using probability calculations to make the statistically safest move every time is actually one I considered when the strategy in the video got stuck! However, computing those probabilities seems both very slow for an algorithm to work out and intimidating for me to work out considering I'm a bit rusty on conditional probability so I didn't get around to it. I'd love to see what that strategy would result in!
@@applemaths4062 actually it is really easy. You take all unknown tiles and try all possible locations of remaining mines. If certain configuration is possible you make +1 to all tiles containing mines. Configuration is possible if mine placement fits all known tile data. After you try all configurations -- tile with biggest number is the most probable mine placement.
Of course there are a lot of possible optimizations, but it is an open question are they really needed.
Well yes, but the problem is that computing those permutations is EXP class, so way too slow to have any sort of efficiency. Starting with the information you have first will probably work faster and even then optimisations are sorely needed.