I created a PERFECT minesweeper AI

[Music] with all my ai creations i've never actually claimed that any of them are any good never mind perfect most of the time they're borderline useless but this time is different because i actually believe that the ai i have created is the best minesweeper player ever of course other ais might have been created which are as good as my ai but no player can surpass my child because he is mathematically and absolutely perfect i think probably not but i think it's close okay let me show you the beast prepare yourself this is him playing minesweeper at an expert level [ __ ] okay well i never claimed it would always win but i am serious about the perfect thing the problem with minesweeper is that at heart it's a game of luck sure there is some problem solving but even the best player can get stuck with a 50 chance of losing so yes sometimes my baby fails but it always performs the best moves that it can it's worth pointing out that this ai is different to any previous ais this guy is hard coded that means no nate no neural networks no genetic algorithm just plain old coding if you don't care about the technical side you can skip forward to watch this ai kick some ass the first few moves are random because well there's not much else we can do after that i started by programming in some logic the first logical rule was if a tile has the same amount of hidden squares around it as unflagged bombs remaining around it then all the hidden tiles are bombs this really is some pretty basic stuff consider this example the two has only one bomb flagged near it and only one hidden space remaining so this hidden space must be a bomb the second rule is if a tile is the same amount of flags around it as the number on the square then all remaining hidden tiles around it are safe the square with the one has one bomb flagged around it so there cannot be any more bombs near it thus the rest are safe now with these two rules in place the ai can perform pretty well but has to guess way too much so let's add some more complex logic consider the following situation with our current logical rules the ai cannot solve it but it can be easily solved note that the three only needs one more flag around it that means that the two squares near it can't both be flagged because then the total would be brill up to four and that's just not how minesweeper works so now the two spaces are what i like to call linked between them they contain exactly one bomb so you can consider them as one square now this means when we look at the two if those two spaces contain exactly one bomb it means the remaining square near two must also be a bomb to bring the total up to two now with our old rules we can finish this example this is much harder to implement than all the other rules but with that in place the ai can handle many more situations we could keep hard coding logical rules for ages and then we still couldn't be sure that we got them all what we need to do is combine all possible rules into a single rule is such a rule possible we'll obviously otherwise i wouldn't bring it up anyway what you need to remember is minesweeper is a game of luck and what that means is we're gonna have to use a little bit of math and probability wait don't click away we can make this interesting math and probability oh yeah if we can calculate the probability of each square being a bomb and then clicking the one with the smallest chance of exploding in our faces then we would be set we can use this method to simulate all possible logical rules because any spaces that are safe have a zero percent chance of a bomb and any spaces which need to be flagged have a hundred percent chance of being a bomb so we just need to calculate the probability of h square being a bomb and then she will achieve perfection now how can we do this well it's simple really all we need to do is generate all possible arrangements of bombs in the remaining spaces and then count the number of arrangements in which a bomb is placed on that certain space then we divide that number by the total number of arrangements possible and voila we get the probability of a bomb being in this space and with that we have created the perfect minesweeper player this can replicate any logical method for finding bombs and safe spaces as well as tell us which squares have the best odds of not being a bomb okay deep breath that's the end of the math heavy side of the video now you can just sit back relax and watch as we crush some minesweeper [Music] okay this is hardly a challenge let's see how big a game this ai can take [Music] [Music] [Music] so i hope you enjoyed watching my ai like if you did subscribe if you did and i'll see you next time you

Channel: Code Bullet

Views: 6,926,068

Keywords: Math, AI, artificial intelligence, programming, java, computer science, games, minesweeper, perfect

Id: cGUHehFGqBc

Length: 7min 46sec (466 seconds)

Published: Fri Apr 13 2018

Reddit Comments

[u/KarlJay001]

Is this really considered AI? As best I can tell, it didn't really learn how to play the game, it was just a "reverse" or puzzle solver.

[u/rulersruler]

Nice, I wrote a similar program for a job application. https://rdsilver.github.io/minesweeper/ Didn't get the job :(

[u/vriemeister]

Did you actually use windows minesweeper, use screenshots to read the state of the board, and automate mouse movements? That would be wild.

[u/H3g3m0n]

I'm not sure this is 'perfect'.

Using a totally random position for the first move seems like it's sub-optimal. If the random choice is on an edge, then it will reveal less useful information since it's only showing information about 6 tiles rather than 9. A corner would be even worse at 4.

It would also seems to me that the distance to the edge (or previously revealed pieces) could also effect the game since you could be getting more information if you hit one of the 'open areas' that reveal a heap of the board in one go. An open area against an edge, or known bomb area isn't going to grow as far.

I suppose a lot will depend on if the fitness metric is win vs loose % or includes the number of moves to win.

EDIT: Actually since it's chance, the fewer moves made should increase the chance of winning unless a move is a sure thing.

[u/omniron]

I personally wouldn't consider this AI because the vast majority is strictly rule-based. There's essentially only 1 valid solution given the available percepts.

[u/Borthralla]

This is an algorithm, not an AI. And it's not perfect, it doesn't have a color-gradient overlay showing all the probabilties like mine does :P Play with mine here. Double click the file to start. Hold down enter to auto-play. It's also faster.