nice video. can u elaborate on how to programmatically enumerate all mines patterns given limited information, like u did around 2:00? maybe share a web describe how to do it?
Of course! I'll try my best to explain the process in steps: First, I wrote a function that will find all of the "edge" cells (aka the cells that border a revealed number) and stored them in an array with their row and column index and a mine status equal to null. Next we loop through the edge array and recursively run another function called "generateArrangements" which determines if a cell can contain a mine or if it can not contain a mine as determined by the neighboring numbers and other already placed mines. See below for more details. generateArrangements function logic: For each cell, if a mine can be placed in that cell, then we make a copy of the edge array and set that cell to a mine status equal to true. Then we re-run the generateArrangements function on the newly copied edge array with a new mine status. Also, if a cell has the possibility to not contain a mine, then we also make a copy of that edge array and set that cell mine status to false. Then we re-run generateArrangements on this new array as well. Finally, when generateArrangements reaches the last edge cell, then it will store the array as a possible arrangement. Overall, this will create an array of all possible arrangements for the edge cells. If this is still confusing here is a crude graphic representation with an edge array of 3 cells: Edge Cell # Possibility Tree (Y = mine) (N = not a mine) 1 Y N / \ / \ 2 Y N Y N | / \ / \ | 3 N Y N Y N Y Often times a previously placed mine or unplaced mine will cause the next cell to only have one possible mine status. In this hypothetical case, there would be 6 possible mine arrangements: Y Y N Y N Y Y N N N Y Y N Y N N N Y Hope this helps!
interesting approach, im surprised its feasible. heres how i did it 2 years ago for highschool maths project that i found to be pretty generalizable and somewhat efficient that i want to share: 1. treat the board like the huge system of linear equations that it is, that is, each number cell representing the sum of all its surrounding tiles, where each tile can take 0 or 1 as values. now youve got a huge matrix multiplication Ax = v where v is the numbered cells, A is the matrix representing the adjacency of each unrevealed cell to numbered cells and x is an arrangement of mines in those unrevealed cells that satisfies Ax = v 2. group together edge cells that shares the exact same relationship with all numbered cells, ie the corresponding columns in the matrix A of these cells are identical, eg all the 8 cells around an isolated 3 should be grouped into one cluster, since theyll share the same probabilities anyway. this creates another system of equation thats way smaller, A'x' = v where every valid solution x' only tells you the mine count for every cluster, not the specific configuration within each clusters. but we dont need that, since if you know theres 2 mines within a cluster of 6 cells you know theres 6C2 configurations where thats a mine. also while we're at it we might as well have a huge cluster of all non-edge cells and have an extra equation saying that sum of all cell clusters is the total mine count. 3. solve for constraints. its trivial that a 5-cells cluster F cant have 5 mines inside it and a 3-cells cluster G cant have 3 mines in it, but if you also have the equation F + G = 6 then you now have a tighter inequality 1
This is a great video! I recently watched a video by Code Bullet where he made an optimal Minesweeper solver using probability, and I wanted to attempt to code something similar, but I didn't understand the math he used. This video explained the math very clearly for me to understand, so thank you!
A suggestion for your website: Right clicking brings up a context menu in my Firefox. meaning that each mine I want to flag by right-clicking I have to click twice for. Clicking an empty cell is slow and prone to errors, and I have to click a third time to get back to normal mode. And clicking the "Flag mode" button is as much work as clicking an empty cell, except the clicks are also super far apart. Is there a hotkey that switches between normal and flag mode? Or even better, make Shift-left click do the same thing that right click currently does (and shift-right click the same thing that left click does).
This is so cool, I love Minesweeper and I love having this probability laid out right in front of me! Can I ask for an increased limit to the board parameters? I've been trying to beat a 99x99 grid with 2450 mines for ages, and this tool would be a massive QoL update!
Unfortunately, minesweeper is NP complete, meaning that the larger the board (and the larger the mine density), the longer the program will take to calculate the probability. You may even have already noticed some delays on the 16x30 board due to this fact. Since my code is by no means completely optimized, it will struggle with larger boards, so I decided to limit the size of the grid. Nevertheless, I think that playing around with probabilities on a smaller scale may still be helpful to improve your best guess intuition which can be translated to larger boards. If I were to recommend a substitute probability calculator, I would direct you to check out one of the following other sites: davidnhill.github.io/JSMinesweeper/ mrgris.com/projects/minesweepr/demo/player/
Hey, sorry for the late response. I explained it briefly at 1:34 in the video, but to expand: You calculate all possible mine arrangements around the revealed region of the board. Then, with each mine arrangement, you subtract the number of mines that that specific arrangement used from the total number of remaining mines. Then, you do a combinations probability calculation between the total number of unrevealed cells and number of remaining mines not used by that mine arrangement. Lastly, you add up all of the combinations calcuations to get the grand total.
Thanks a lot friend! I thought I was just stupid or lacking logic which still may be true but I showed my girlfriend this game from my childhood and we were trying to decide if some squares are a gamble.
Well I just manual, systematically tried out different possibilities and found out that only eight of them were possible. I don't know if that answered your question tho. Did it?
Recently, I've become very interested in coding minesweeper and a solver. After watching this and other videos I've developed a very efficient solver that you could maybe implement! Essentially, I first apply common algorithms, such as "if the number of surrounding unknown squares is the same number of the square, then all of them are mines" and other ones cited in this video: ruclips.net/video/8j7bkNXNx4M/видео.html. After that I noticed that the game can be put into a linear system of equations. Suppose the number of a square is n=3 and it is surrounded by 4 unknown squares a1,a2,a3 and a4, then a1+a2+a3+a4=n (ak is 1 if it has a bomb and 0 if not). And this can be applied to all number squares to get a large matrix. Solving this system (which I did using SymPy), the solution is given in a parametric form. Testing all possible values of the parameters (each can be 0 or 1, because each square either has or doesn't have a mine) and filtering out only those which satisfy the system gives all the possible combinations of mines. Note that this gets really efficient also because the majority of border squares is already decided to have or not a mine by the first algorithms. I am currently trying to think of ways to improve even more my solver. I believe that it would be better to break the set of border squares into groups that are not connected than to consider all of them at once, for example. Edit: I've uploaded it to github! github.com/PedroKKr/Minesweeper-probabilty-calculator
Hi! If you mean what algorithm I used to generate the probabilities, I wrote my own. You can see a rough logic explanation in the pinned comment on how it works.
nice video. can u elaborate on how to programmatically enumerate all mines patterns given limited information, like u did around 2:00? maybe share a web describe how to do it?
Of course! I'll try my best to explain the process in steps:
First, I wrote a function that will find all of the "edge" cells (aka the cells that border a revealed number) and stored them in an array with their row and column index and a mine status equal to null.
Next we loop through the edge array and recursively run another function called "generateArrangements" which determines if a cell can contain a mine or if it can not contain a mine as determined by the neighboring numbers and other already placed mines. See below for more details.
generateArrangements function logic:
For each cell, if a mine can be placed in that cell, then we make a copy of the edge array and set that cell to a mine status equal to true. Then we re-run the generateArrangements function on the newly copied edge array with a new mine status.
Also, if a cell has the possibility to not contain a mine, then we also make a copy of that edge array and set that cell mine status to false. Then we re-run generateArrangements on this new array as well.
Finally, when generateArrangements reaches the last edge cell, then it will store the array as a possible arrangement.
Overall, this will create an array of all possible arrangements for the edge cells.
If this is still confusing here is a crude graphic representation with an edge array of 3 cells:
Edge Cell # Possibility Tree (Y = mine) (N = not a mine)
1 Y N
/ \ / \
2 Y N Y N
| / \ / \ |
3 N Y N Y N Y
Often times a previously placed mine or unplaced mine will cause the next cell to only have one possible mine status.
In this hypothetical case, there would be 6 possible mine arrangements:
Y Y N
Y N Y
Y N N
N Y Y
N Y N
N N Y
Hope this helps!
@@Mewok given that minesweeper is turing-complete, larger maps may use a lot of memory for all the trees?
@@ollllj Yes, you're probably right.Was just a challenge to see if I could code something. Definitely more efficiently ways to do it though.
The probability is so useful. After playing this version, I can’t play without it anymore.
I hope it can help you improve your game!
you know there are other solvers out there right??
interesting approach, im surprised its feasible. heres how i did it 2 years ago for highschool maths project that i found to be pretty generalizable and somewhat efficient that i want to share:
1. treat the board like the huge system of linear equations that it is, that is, each number cell representing the sum of all its surrounding tiles, where each tile can take 0 or 1 as values. now youve got a huge matrix multiplication Ax = v where v is the numbered cells, A is the matrix representing the adjacency of each unrevealed cell to numbered cells and x is an arrangement of mines in those unrevealed cells that satisfies Ax = v
2. group together edge cells that shares the exact same relationship with all numbered cells, ie the corresponding columns in the matrix A of these cells are identical, eg all the 8 cells around an isolated 3 should be grouped into one cluster, since theyll share the same probabilities anyway. this creates another system of equation thats way smaller, A'x' = v where every valid solution x' only tells you the mine count for every cluster, not the specific configuration within each clusters. but we dont need that, since if you know theres 2 mines within a cluster of 6 cells you know theres 6C2 configurations where thats a mine. also while we're at it we might as well have a huge cluster of all non-edge cells and have an extra equation saying that sum of all cell clusters is the total mine count.
3. solve for constraints. its trivial that a 5-cells cluster F cant have 5 mines inside it and a 3-cells cluster G cant have 3 mines in it, but if you also have the equation F + G = 6 then you now have a tighter inequality 1
That's so cool! Probably pretty efficient if I had to guess.
This video will make me a professional minesweeper player.
I hope it does!
This is a great video! I recently watched a video by Code Bullet where he made an optimal Minesweeper solver using probability, and I wanted to attempt to code something similar, but I didn't understand the math he used. This video explained the math very clearly for me to understand, so thank you!
Thanks for watching! Glad you found it helpful.
WOW VERY HELPFUL VIDEO! Thank you! You are one talented student. I think you will be famous one day.
I'm glad you found it helpful!
A suggestion for your website: Right clicking brings up a context menu in my Firefox. meaning that each mine I want to flag by right-clicking I have to click twice for. Clicking an empty cell is slow and prone to errors, and I have to click a third time to get back to normal mode. And clicking the "Flag mode" button is as much work as clicking an empty cell, except the clicks are also super far apart.
Is there a hotkey that switches between normal and flag mode?
Or even better, make Shift-left click do the same thing that right click currently does (and shift-right click the same thing that left click does).
Ooh I did not account for firefox. Not sure why it would be different. Sorry for the extra hassle involved.
I always wondered how probability worked for cells that on one side are 1 of 2, but on the other side are 1 of 3. I guess that answers that. Cheers.
Yes, that conundrum is what made me want to figure it out!
This is so cool, I love Minesweeper and I love having this probability laid out right in front of me! Can I ask for an increased limit to the board parameters? I've been trying to beat a 99x99 grid with 2450 mines for ages, and this tool would be a massive QoL update!
Unfortunately, minesweeper is NP complete, meaning that the larger the board (and the larger the mine density), the longer the program will take to calculate the probability. You may even have already noticed some delays on the 16x30 board due to this fact. Since my code is by no means completely optimized, it will struggle with larger boards, so I decided to limit the size of the grid.
Nevertheless, I think that playing around with probabilities on a smaller scale may still be helpful to improve your best guess intuition which can be translated to larger boards.
If I were to recommend a substitute probability calculator, I would direct you to check out one of the following other sites:
davidnhill.github.io/JSMinesweeper/
mrgris.com/projects/minesweepr/demo/player/
2:50 how did you get the grand total number of arrangements?
Hey, sorry for the late response. I explained it briefly at 1:34 in the video, but to expand:
You calculate all possible mine arrangements around the revealed region of the board.
Then, with each mine arrangement, you subtract the number of mines that that specific arrangement used from the total number of remaining mines.
Then, you do a combinations probability calculation between the total number of unrevealed cells and number of remaining mines not used by that mine arrangement.
Lastly, you add up all of the combinations calcuations to get the grand total.
Thanks a lot friend! I thought I was just stupid or lacking logic which still may be true but I showed my girlfriend this game from my childhood and we were trying to decide if some squares are a gamble.
Haha yeah, I had a debate with my friend and that's how I wanted to figure out how the probabilities work too!
thank you so much brother I will be using this to help me make my game 🙏
I will credit you so hard
Glad it helped!
1:49 - how did you know that it has 8 possibilities on that case?
Well I just manual, systematically tried out different possibilities and found out that only eight of them were possible.
I don't know if that answered your question tho. Did it?
I am trying to comment your code on github fork
what license is it under? the project has none attached
Awesome video! Really clearly explained
Thank you! I'm glad you enjoyed it.
Recently, I've become very interested in coding minesweeper and a solver. After watching this and other videos I've developed a very efficient solver that you could maybe implement! Essentially, I first apply common algorithms, such as "if the number of surrounding unknown squares is the same number of the square, then all of them are mines" and other ones cited in this video: ruclips.net/video/8j7bkNXNx4M/видео.html. After that I noticed that the game can be put into a linear system of equations. Suppose the number of a square is n=3 and it is surrounded by 4 unknown squares a1,a2,a3 and a4, then a1+a2+a3+a4=n (ak is 1 if it has a bomb and 0 if not). And this can be applied to all number squares to get a large matrix. Solving this system (which I did using SymPy), the solution is given in a parametric form. Testing all possible values of the parameters (each can be 0 or 1, because each square either has or doesn't have a mine) and filtering out only those which satisfy the system gives all the possible combinations of mines. Note that this gets really efficient also because the majority of border squares is already decided to have or not a mine by the first algorithms. I am currently trying to think of ways to improve even more my solver. I believe that it would be better to break the set of border squares into groups that are not connected than to consider all of them at once, for example. Edit: I've uploaded it to github! github.com/PedroKKr/Minesweeper-probabilty-calculator
Thanks for sharing Pedro! That sounds really cool. Is there a way for people to try it?
@@Mewok I've created a repository for it on GitHub today. I've edited my comment to include a link for it.
Can you make a board on which you can input data (mine and number) on a partially played game so that you an calculate probabilities at that point?
I could... but that sounds like a lot of work. Here's a good website that does it already!
mzrg.com/js/mine/probability.html
excellent
Hope you got some use out of it.
Which algorithm did you use?
Hi! If you mean what algorithm I used to generate the probabilities, I wrote my own. You can see a rough logic explanation in the pinned comment on how it works.
So cool!
nice
thanks!
8.1 GOOGOL??
Craaaaaaaaaazy right?
Great job...
Thanks!
This is so cool
Thanks, I'm glad you think so!
Nice
Thank you thank you!