You missed a trick. When you're forced to guess, with an equal chance of death, some choices can give you more information, if successful, than others. Particularly, a cell one square away from a row of 1s can open up a new cavity if it shows the cells between are already allocated to the row of 1s.
You do have a point. This is where things stand for me: The best version I came up with (not the one in the video, but the one I re-written from scratch), has a 36% success rate. The best version I have heard of (the research paper I mention in the video) claims they have gotten to over 40%. I did read that paper and it is somewhat more complex, but essentially yes, if they have to guess, they would try to open the one that "gives more information". A lot of fancy words, not a line of code, but this was my impression. I tried to do something similar, by removing all least probably cells and recursively running algorythms further to see which option will get best result. I probaby messed up implementing it, or maybe there is more to it - but unfortunately, the success rate didn't go up beyond error margin. Anyway, thanks for your interest and your suggestion. I think I should probably come back to this project at some point and give it another go.
@@GamesComputersPlay I think in the ideal case you would build a search tree with propability nodes (where you have to guess). So at start you make a list of all possible mines combinations which are possible with the avalible information. Then you select the node, which maximizes your winning chances down the line and not necessarily the survival chance at the next guess (the method you described). However, due to the search space, I can imagine that finding a perfect solution is only possible for toy cases at the end game. Did you think about writing a neural network which would only be in charge of play in case you need to make a guess? I also would like to know how you make the first move and what the winning statistics are, since here the chance of hitting a mine are obviously identical.
By the way, maybe have have to select a cell with a slightly higher chance of death, but gain so much information in the success case that you basicly do not have to guess anymore. But I do not have an example at hand, but finding one would be also in interesting challange :)
When comparing yourself to all those papers, do you know if there's a chance they were using different minesweeper implementations that might've generated slightly easier / slightly harder puzzles? It seems like if you're using CSP + counting I would expect you to be able to do just about as well as anything.
I only read one of those papers (the one with the highest score). From what I understood, everything was simulated inside of a program - so they just generated a minesweeper board and solved it. I later did something similar, with generating and solving puzzles in the code, also fixed a few things, got my success rate to 36% (this was after the video was published). Reading their paper didn't help much, apparently there is a way to push some more, but the math gets a little over my head. Well they are 5 actual professors of CS, so I feel defeated by worthy opponent. :)
I would argue that those risky 50% guesses are often better, since they give you good info that adds up well with what you've gathered so far, thus pushing the next guess you'll need to make further away. I'd improve on that by estimating whether we have a few or a lot of mines left (#mines÷#cells is greater in the totals or in the remaining), in the former case I'll guess that the mine is near the wall and in the latter it's away from the wall (for a more "efficient" use of mines). If I found the time I'd try comparing it to guessing at the lowest risk
I geniuenly don't understand how you're not getting atleast 1k sub a day, this is actually quality content! It's the first ever time I've ever clicked on an ad!
Much faster indeed. I had a completely rewrittem program that does exacly that. It goes about 2-3 Expert games per second or 16-17 Beginner games per second.
I can't say anything, as the first Windows I saw was 3.1 - and it had minesweeper. But Google search suggests that yes, it was part of Entertainment pack that was available on WIndows 2 (or on 2.0 - 386 edition) a couple of years before 3.1 came out. Funny thing I learned searching for it. Support for Windows 1, 2 and 3 officially ended in 2001, after XP came out. I remember that time and it is fun to think that Win 1, 2 and 3 weren't officially obsolete at that moment.
8:00 the left picture is actually not a 50/50. if the top left square of the box is a mine, only 1 mine will be required to satisfy the 1, 2 and 3. However, if the bottom square is the mine, then another mine (to the bottom right if the 3) is required to satisfy the 3. Since the mine density of most boards is less than 50% (12.35% for 9x9/10 beginner, 15.63% for 16x16/40 intermediate, and 20.63% for 30x16 expert), unless the unsolved part of the board is unusually dense with mines, it is much more likely that the 1, 2 and 3 share a mine in the top left corner. So, instead, when calculating probability, it is much to calculate if the said square is a mine, how many ways are there to fill in the rest of the (unopened) board with mines, and compare that to if the said square was safe. side note: this box pattern is a 50/50 only if there are 2 mines left in that box (via minecounting), maybe the example could have been made more accurate by using a simpler example like this at a corner (x is a mine, o is unopened) x 3 1 | x o o | ______
This is really neat. For calculating win rates (either your calculation or in the papers), does clicking a mine on the first click count as a loss? Because to me it feel like those results shouldn't count, since you have zero information for that first click and just got unlucky; i.e., it's a "loss" but it doesn't actually reflect on the strategy of the solver. (Anything after the first click should be fair game though, since you have _some_ information to make a decision on, even if that decision is a guess.)
To the best of my knowledge - yes, all simulations move mine if it is cliked on the first click. Here in the video it is done by Minesweeper X. In my other simulation, where I reached 36% I did that too. Those guys in the paper, I think mentioned they did it also. All fair.
Thank you for sharing. I personally have used all of those strategies except the equation one (which I have pondered but never used), but I'm curious to see what you did differently from these other ones where the other ones were better on expert.
So the one that I gave up on went something like this. When you have to guess, giben the chances and everything - take into account which cell will give you the most information for the remaining part of the board. In other words, say you have 50/50 and you cannot do anything about it. Pick one that potentially opens the pathway to go farthest if it happens to be safe. I tried to implement it, probably did it wrong (no change in the outcome) and since it was a long project already, just decided that it is probably time to move on.
That was so inspiring! Can you share some idea about how did you implemented the grouping part? ( with lower complexity ). I am thinking about checking knowledge base entailment, but that has a worst case of NP-hard right?
I have to be honest with you - I have very little idea what you are talking about... There is some research about minesweeper and computational complexity, but they are about solving a different problem: given the board, determine if it is legit (consistent with the game rules). Conversely, playing the minesweeper is pretty straightforward - at least up until you have to start guessing. Grouping is one of the deterministic strategies, and if you look at it from a math perspective, it's rather trivial...
@@GamesComputersPlay Yeah, I am confused about how does the group and subgroup part work in code. Do you walk through the frontier and check the tiles near each other?
Yes, pretty much this is how it is done. There is no frontier from the program's perspective - it just goes through all the cells. If there are closed cells around - get their coordinates and number of remaining mines - there is a group. When you go through all of them - you have an array of all groups - you can start matching them to find mines/safe cells. It is slightly more tricky with subgrooups. What I did dis to look at each group and derive subgroups "no more then X mines" and " at least Y mines", where possible. I used recursive functions to do that. You can check the source code (especially the refactored version) in the description - I tried to leave
If your "CSP" strategy seldom gets results, you probably coded it wrong. Whenever I play Minesweeper casually, a large number of cells get revealed in this way. The example you show at 7:15 is totally standard, although the green cell at the bottom is mislabeled. You don't have to do much work, just recognize a few patterns and do them one at a time. Even at high speed, this type of strategy is usually necessary.
My bad - screenshot is cut there, so those lables look weird. As for CSP. Hmmm... My code is not above suspicions, for sure... but... I mean if it was wrong-wrong, it would probably get game overs when it was used. But I only got gameovers with guessing. Also, the way I did it was just kind of a bruteforce - few things can go wrong there. I looked at my code again (it's been a while) - and I see I set a limit to a number of conditions to take into account. Otherwise it ends in computational explosion. And here, I admit may be indeed a room for improvement, to implement something more complex. It shouldn't affect popular patterns though - those my brute force will crack. It is with the long fronts of mines across the full width of the board this approach has a problem with. Another potential explanation - maybe those you normally get with CSP I get with other strategies - those groups/subgroups are weirdly strong.
@@GamesComputersPlay I rewatched the video, and it looks like I was misunderstanding how the groups/subgroups worked. Most of the strategies those use I would consider to be CSP (though I guess really, the whole game of Minesweeper is). Other places call them basic patterns. I guess it just depends how you view it. Your order makes sense, I assume, because it speeds up the computation.
Hai, me and a few of my friends are playing a game where within the game there is a minesweeper, we tryed to edit your code to work on it, but we failed, would you be interested to adjust your script to work on our minesweeper for a reward? можно и так
You mean for the program to read and play your version (or your "skin" I guess you can say) of Minesweeper? Sure , I can give it a try. Send me an email at gamescomputersplay@gmail.com with details.
Sure, uploaded. Note, it may not work out-of-the-box though. I coded image recognition for my screen settings and didn't include anyt8ing to make it universal. It is an easier part of the program though, so in theory with a little Python knowledge can be adjusted.
It's really a rather boring part, also quite inefficient, could for sure be done much better. What I did is summed up all the pixel values of a cell for all situations: closed, 1,2,...8, mine, 0 - produsing a "signature" of a cell. Than just get the sum of the cell on a screen and compatre with a sample signature. If I did it today - first, you don't need to sum all the pixels. Also, I'd keep some sample files and would get the signature autimatically, not by hardcoding it in the program.
@@GamesComputersPlay The extraction of data from a picture is far from boring 😅 It's very useful and interesting - I think many would watch a video about it 🙂
This was interesting to see after trying the problem myself. I used a site that guarantees the minesweeper board is solvable, so I didn't implement guessing. My approach used the basic and counter strategies, and then did a recursive search on subsequent boards until those strategies yielded a known tile. I'll have to look into CSP, since calculating that system of equations upfront seems more efficient than guessing and checking.
Actually the way I used CSP is it llilttle more that brute force, but limited to a particular region of the board. It did bring a few % points t the win rate though. Also quite helpful for guessing.
hello, i find your content interesting but i briefly looked at the code and couldn't find out how you connect your code to the game (make it work on the actual game) , any idea ? or maybe i'm getting smth wrong haha
Hi Gabriel, There are two files in the repo: *Mine-x_**publish.py* This is the program that was used in the video (or some later iteration of that program). It wasn’t written as a “universal” solver for all minesweepers in the world - just for the one I had right then and there on my computer. It happened to be Minesweeper X and my screen was set up at 125% scale. It is very unlikely to work in any other settings. The way it worked was it looked for a specific pixel of specific color on the screen and guessed where all the cells were. When reading the opened cells, it compares average color to a set of presets. I am not too proud of this code. I think I can do better now and maybe I will someday. Anyway, with enough resolve to dig into my less-than-perfect code it can be recalibrated to almost any other minesweeper version. *Minesweeper.solver.py* This one is a more abstract one. I rewrote the whole solver from scratch, aiming for a cleaner code (code-wise it is better than the original one, but still has some room for improvement). In this one there is no connection to the actual game, I used this one to simulations and trying to reach the higher win rate.
I recently got into Minesweeper, and now I want to make something like this that would play as good as a true pro, and then I can make a replay of it and pretend I'm superhuman, if only for a brief moment.
Hi! I was looking at this and I was super interested. How do you run it? When I run it through pycharm, it can't recognize (77802, 77802, 77802) and also can't find the field. Thanks!
Sorry, but it was for the minesweeper X and for full HD screen at 125% scale. Probably wouldn't work in any other setup. Or, at least would require some adjustment in the code. I was thinking of making it more universal - but the code is so old and ugly and I think I would rather rewrite the whole thing from scratch.
You missed a trick. When you're forced to guess, with an equal chance of death, some choices can give you more information, if successful, than others. Particularly, a cell one square away from a row of 1s can open up a new cavity if it shows the cells between are already allocated to the row of 1s.
You do have a point.
This is where things stand for me:
The best version I came up with (not the one in the video, but the one I re-written from scratch), has a 36% success rate. The best version I have heard of (the research paper I mention in the video) claims they have gotten to over 40%.
I did read that paper and it is somewhat more complex, but essentially yes, if they have to guess, they would try to open the one that "gives more information". A lot of fancy words, not a line of code, but this was my impression.
I tried to do something similar, by removing all least probably cells and recursively running algorythms further to see which option will get best result. I probaby messed up implementing it, or maybe there is more to it - but unfortunately, the success rate didn't go up beyond error margin.
Anyway, thanks for your interest and your suggestion. I think I should probably come back to this project at some point and give it another go.
@@GamesComputersPlay I think in the ideal case you would build a search tree with propability nodes (where you have to guess). So at start you make a list of all possible mines combinations which are possible with the avalible information. Then you select the node, which maximizes your winning chances down the line and not necessarily the survival chance at the next guess (the method you described). However, due to the search space, I can imagine that finding a perfect solution is only possible for toy cases at the end game. Did you think about writing a neural network which would only be in charge of play in case you need to make a guess?
I also would like to know how you make the first move and what the winning statistics are, since here the chance of hitting a mine are obviously identical.
By the way, maybe have have to select a cell with a slightly higher chance of death, but gain so much information in the success case that you basicly do not have to guess anymore. But I do not have an example at hand, but finding one would be also in interesting challange :)
Finally another good ad
When comparing yourself to all those papers, do you know if there's a chance they were using different minesweeper implementations that might've generated slightly easier / slightly harder puzzles? It seems like if you're using CSP + counting I would expect you to be able to do just about as well as anything.
I only read one of those papers (the one with the highest score). From what I understood, everything was simulated inside of a program - so they just generated a minesweeper board and solved it.
I later did something similar, with generating and solving puzzles in the code, also fixed a few things, got my success rate to 36% (this was after the video was published).
Reading their paper didn't help much, apparently there is a way to push some more, but the math gets a little over my head. Well they are 5 actual professors of CS, so I feel defeated by worthy opponent. :)
lol I watched all your Minesweeper videos and I don't even know what are the rules of the game.
That's some dedication!
I can say I have a couple of videos about Monopoly - and I don't think I ever played classic Monopoly (only some knock offs)
I would argue that those risky 50% guesses are often better, since they give you good info that adds up well with what you've gathered so far, thus pushing the next guess you'll need to make further away. I'd improve on that by estimating whether we have a few or a lot of mines left (#mines÷#cells is greater in the totals or in the remaining), in the former case I'll guess that the mine is near the wall and in the latter it's away from the wall (for a more "efficient" use of mines). If I found the time I'd try comparing it to guessing at the lowest risk
I geniuenly don't understand how you're not getting atleast 1k sub a day, this is actually quality content! It's the first ever time I've ever clicked on an ad!
Thanks! One of these days... one of these days....:)
Nice. Hope your channel grows..
Thanks, man.
I'm curious how fast this would be if the game was stored fully digitally and it didn't need to interact with an actual game
Much faster indeed. I had a completely rewrittem program that does exacly that. It goes about 2-3 Expert games per second or 16-17 Beginner games per second.
cool, your such a good programer :D
Thanks! Honestly though, you wouldn't say that if you were to have a look at the code - it's quite a mess :)
Games Computers Play but still your awsome dude!
Wow. Only 142 subs. More like 142k or 142B
Minesweeper was actually available in Windows 286 and Windows 386 (prior to windows 3), IF you had the expansion pack (2 extra floppies).
I can't say anything, as the first Windows I saw was 3.1 - and it had minesweeper.
But Google search suggests that yes, it was part of Entertainment pack that was available on WIndows 2 (or on 2.0 - 386 edition) a couple of years before 3.1 came out.
Funny thing I learned searching for it. Support for Windows 1, 2 and 3 officially ended in 2001, after XP came out. I remember that time and it is fun to think that Win 1, 2 and 3 weren't officially obsolete at that moment.
Fun fact: Kaye also proved that infinite Minesweeper is Turing-complete
8:00 the left picture is actually not a 50/50. if the top left square of the box is a mine, only 1 mine will be required to satisfy the 1, 2 and 3. However, if the bottom square is the mine, then another mine (to the bottom right if the 3) is required to satisfy the 3. Since the mine density of most boards is less than 50% (12.35% for 9x9/10 beginner, 15.63% for 16x16/40 intermediate, and 20.63% for 30x16 expert), unless the unsolved part of the board is unusually dense with mines, it is much more likely that the 1, 2 and 3 share a mine in the top left corner. So, instead, when calculating probability, it is much to calculate if the said square is a mine, how many ways are there to fill in the rest of the (unopened) board with mines, and compare that to if the said square was safe.
side note: this box pattern is a 50/50 only if there are 2 mines left in that box (via minecounting), maybe the example could have been made more accurate by using a simpler example like this at a corner (x is a mine, o is unopened)
x 3 1 |
x o o |
______
I agree. Well spoted.
How about using CSP to get more accurate chances to be a mine? It might give more accurate chances to the wilderness rather than 24% to all of them
This is exactly right. I implemented this, but after a video was already done. It raised the success rate to 36%.
This is really neat. For calculating win rates (either your calculation or in the papers), does clicking a mine on the first click count as a loss? Because to me it feel like those results shouldn't count, since you have zero information for that first click and just got unlucky; i.e., it's a "loss" but it doesn't actually reflect on the strategy of the solver. (Anything after the first click should be fair game though, since you have _some_ information to make a decision on, even if that decision is a guess.)
To the best of my knowledge - yes, all simulations move mine if it is cliked on the first click. Here in the video it is done by Minesweeper X. In my other simulation, where I reached 36% I did that too. Those guys in the paper, I think mentioned they did it also. All fair.
The windows minesweeper generates the board after the first press. You will never get a bomb on first click
Thank you for sharing. I personally have used all of those strategies except the equation one (which I have pondered but never used), but I'm curious to see what you did differently from these other ones where the other ones were better on expert.
So the one that I gave up on went something like this. When you have to guess, giben the chances and everything - take into account which cell will give you the most information for the remaining part of the board.
In other words, say you have 50/50 and you cannot do anything about it. Pick one that potentially opens the pathway to go farthest if it happens to be safe.
I tried to implement it, probably did it wrong (no change in the outcome) and since it was a long project already, just decided that it is probably time to move on.
That was so inspiring! Can you share some idea about how did you implemented the grouping part? ( with lower complexity ). I am thinking about checking knowledge base entailment, but that has a worst case of NP-hard right?
I have to be honest with you - I have very little idea what you are talking about...
There is some research about minesweeper and computational complexity, but they are about solving a different problem: given the board, determine if it is legit (consistent with the game rules). Conversely, playing the minesweeper is pretty straightforward - at least up until you have to start guessing. Grouping is one of the deterministic strategies, and if you look at it from a math perspective, it's rather trivial...
@@GamesComputersPlay Yeah, I am confused about how does the group and subgroup part work in code. Do you walk through the frontier and check the tiles near each other?
Yes, pretty much this is how it is done.
There is no frontier from the program's perspective - it just goes through all the cells. If there are closed cells around - get their coordinates and number of remaining mines - there is a group. When you go through all of them - you have an array of all groups - you can start matching them to find mines/safe cells.
It is slightly more tricky with subgrooups. What I did dis to look at each group and derive subgroups "no more then X mines" and " at least Y mines", where possible. I used recursive functions to do that.
You can check the source code (especially the refactored version) in the description - I tried to leave
14 subs only?
*let's make it 15 cuz I can*
How do you have less subscribers than me?
I'm new to this, I guess...
If your "CSP" strategy seldom gets results, you probably coded it wrong. Whenever I play Minesweeper casually, a large number of cells get revealed in this way. The example you show at 7:15 is totally standard, although the green cell at the bottom is mislabeled. You don't have to do much work, just recognize a few patterns and do them one at a time. Even at high speed, this type of strategy is usually necessary.
My bad - screenshot is cut there, so those lables look weird.
As for CSP. Hmmm... My code is not above suspicions, for sure... but...
I mean if it was wrong-wrong, it would probably get game overs when it was used. But I only got gameovers with guessing.
Also, the way I did it was just kind of a bruteforce - few things can go wrong there.
I looked at my code again (it's been a while) - and I see I set a limit to a number of conditions to take into account. Otherwise it ends in computational explosion. And here, I admit may be indeed a room for improvement, to implement something more complex.
It shouldn't affect popular patterns though - those my brute force will crack. It is with the long fronts of mines across the full width of the board this approach has a problem with.
Another potential explanation - maybe those you normally get with CSP I get with other strategies - those groups/subgroups are weirdly strong.
@@GamesComputersPlay I rewatched the video, and it looks like I was misunderstanding how the groups/subgroups worked. Most of the strategies those use I would consider to be CSP (though I guess really, the whole game of Minesweeper is). Other places call them basic patterns. I guess it just depends how you view it. Your order makes sense, I assume, because it speeds up the computation.
Hai, me and a few of my friends are playing a game where within the game there is a minesweeper, we tryed to edit your code to work on it, but we failed, would you be interested to adjust your script to work on our minesweeper for a reward? можно и так
You mean for the program to read and play your version (or your "skin" I guess you can say) of Minesweeper? Sure , I can give it a try. Send me an email at gamescomputersplay@gmail.com with details.
@@GamesComputersPlay Alright sent you a mail
Glad to see CVUT paper at 10:26 =w=
let the computer play tetris?
Absolutely! I do have plans for writing a program that plays tetris, and it should be an interesting project to do. Will take some time though.
I would have just done a brute-force expectimax tbh...
Not sure how Expectiminimax would work here.
But hey, I have something about MInimax in my upcoming video!
Can we still get the "old" version (shown in the video) to be able to play on minesweeper x?
Sure, uploaded.
Note, it may not work out-of-the-box though. I coded image recognition for my screen settings and didn't include anyt8ing to make it universal.
It is an easier part of the program though, so in theory with a little Python knowledge can be adjusted.
I was hoping you would run through the "analyse screenshot" part
It's really a rather boring part, also quite inefficient, could for sure be done much better.
What I did is summed up all the pixel values of a cell for all situations: closed, 1,2,...8, mine, 0 - produsing a "signature" of a cell.
Than just get the sum of the cell on a screen and compatre with a sample signature.
If I did it today - first, you don't need to sum all the pixels. Also, I'd keep some sample files and would get the signature autimatically, not by hardcoding it in the program.
@@GamesComputersPlay The extraction of data from a picture is far from boring 😅 It's very useful and interesting - I think many would watch a video about it 🙂
This was interesting to see after trying the problem myself. I used a site that guarantees the minesweeper board is solvable, so I didn't implement guessing. My approach used the basic and counter strategies, and then did a recursive search on subsequent boards until those strategies yielded a known tile. I'll have to look into CSP, since calculating that system of equations upfront seems more efficient than guessing and checking.
Actually the way I used CSP is it llilttle more that brute force, but limited to a particular region of the board. It did bring a few % points t the win rate though. Also quite helpful for guessing.
hello, i find your content interesting but i briefly looked at the code and couldn't find out how you connect your code to the game (make it work on the actual game) , any idea ? or maybe i'm getting smth wrong haha
Hi Gabriel,
There are two files in the repo:
*Mine-x_**publish.py*
This is the program that was used in the video (or some later iteration of that program).
It wasn’t written as a “universal” solver for all minesweepers in the world - just for the one I had right then and there on my computer. It happened to be Minesweeper X and my screen was set up at 125% scale. It is very unlikely to work in any other settings.
The way it worked was it looked for a specific pixel of specific color on the screen and guessed where all the cells were. When reading the opened cells, it compares average color to a set of presets.
I am not too proud of this code. I think I can do better now and maybe I will someday.
Anyway, with enough resolve to dig into my less-than-perfect code it can be recalibrated to almost any other minesweeper version.
*Minesweeper.solver.py*
This one is a more abstract one. I rewrote the whole solver from scratch, aiming for a cleaner code (code-wise it is better than the original one, but still has some room for improvement). In this one there is no connection to the actual game, I used this one to simulations and trying to reach the higher win rate.
I recently got into Minesweeper, and now I want to make something like this that would play as good as a true pro, and then I can make a replay of it and pretend I'm superhuman, if only for a brief moment.
That's a great aspiration. Actually, if you watch real Minesweeper champions play, it does look superhuman (even if it is times slower than the bot)
good and interesting video
Super good video.
Good video
Wow :D
Really cool!!!
Lol
👍
BoOoOoO
Despite your explanations I can't wrap my head around minesweeper, it makes no sense.
have a look for the "Minesweeper: The Movie" trailer, it will clarify everything
3.1-95 have this
You are right. And they kept including it up until Win 7, and then stopped...
IIRC, it was included to get people used to precision clicking. Solitaire was to get people used to drag and drop
I am 27th sub
Hi! I was looking at this and I was super interested. How do you run it? When I run it through pycharm, it can't recognize (77802, 77802, 77802) and also can't find the field. Thanks!
Sorry, but it was for the minesweeper X and for full HD screen at 125% scale. Probably wouldn't work in any other setup. Or, at least would require some adjustment in the code.
I was thinking of making it more universal - but the code is so old and ugly and I think I would rather rewrite the whole thing from scratch.