How to Write your own Minesweeper AI(luckytoilet.wordpress.com)
luckytoilet.wordpress.com
How to Write your own Minesweeper AI
http://luckytoilet.wordpress.com/2012/12/23/2125/
10 comments
I made a similar minesweeper solver that employs many of the same techniques. It really is an interesting algorithm to play with and involves some deep delving into combinatorics and probability. Glad to see someone else had the same thought process (or obsession)!
You can play with an HTML5 demo here: http://mrgris.com/projects/minesweepr/demo/player/
One fun side-effect is that once you have the core algorithm, you realize there's no reason minesweeper must be constrained to a grid. It works just as well on hexagonal tiles or on the surface of a cube.
You can play with an HTML5 demo here: http://mrgris.com/projects/minesweepr/demo/player/
One fun side-effect is that once you have the core algorithm, you realize there's no reason minesweeper must be constrained to a grid. It works just as well on hexagonal tiles or on the surface of a cube.
It's interesting how the grid+1 is really hard to safely get going, but once underway it progresses quickly and it's clear where the mines are.
Nice algorithm. That's pretty close to optimal. There is one improvement you missed, though it's not obvious how to implement it and I'm not sure how helpful it would be. When you aren't sure what to do, you assign probabilities in order to guess which square to click, but you could also estimate how useful each square would be.
There might be one square that's unlikely to contain a mine, but also unlikely to help much in solving the rest of the board. You might even be able to infer exactly what it will be before you click on it. Then, if there is another square that's a bit more likely to have a mine but also more likely to help, you can click on that one instead.
There might be one square that's unlikely to contain a mine, but also unlikely to help much in solving the rest of the board. You might even be able to infer exactly what it will be before you click on it. Then, if there is another square that's a bit more likely to have a mine but also more likely to help, you can click on that one instead.
You could just simulate a run of your algorithm against all the possible configurations left. Even with the segmenting trick from the article, this will sometimes be far too slow; but e.g. trying it for 10 seconds before terminating the computation may help.
Minesweeper has been shown to be NP-complete [1]. So if there's a way to avoid "brute force" and guarantee a polynomial-time solution to an arbitrary board, that would be a proof of P=NP and win you a million dollars, worldwide fame (at least among theoretical computer scientists), and a citation of that work in theory of computation textbooks for a long time to come.
[1] http://web.mat.bham.ac.uk/R.W.Kaye/minesw/ordmsw.htm
[1] http://web.mat.bham.ac.uk/R.W.Kaye/minesw/ordmsw.htm
Has anyone done an analysis that computes probabilities without brute force enumeration? Probabilistic decisions in Minesweeper are interesting, but this algorithm left me kind of disappointed.
Tangentially related - there was a conspiracy theory making rounds in early 90s that not only Windows Minesweeper was allocating mines as you played, it also rigged the game in its favor. That is, if you were opening a tile that may or may not have a mine, it'd be more likely to see a mine there than not see it. Allegedly, this was backed by a statistics research that some people did. I've never seen that research, but the game did feel unfair when it came to random poking around the mine field.
I remember seeing that debunked, but cannot find that now.
What I can find is http://www.minesweeper.info/wiki/Main_Page. Those guys aren't aware of this, and claim to see games repeated (http://www.minesweeper.info/wiki/Dreamboard). That debunks the theory.
What I can find is http://www.minesweeper.info/wiki/Main_Page. Those guys aren't aware of this, and claim to see games repeated (http://www.minesweeper.info/wiki/Dreamboard). That debunks the theory.
Interesting project.
In the past I've had a side project involving automating casino games for fun. I followed this tutorial for automating simple web games with Python:
http://active.tutsplus.com/tutorials/workflow/how-to-build-a...
This tutorial uses Python Image Library (PIL) for 'reading' the UI and PyWin to manipulate the mouse in order to play the game. I would suggest using AutoPy instead of PyWin to give platform-agnostic GUI manipulation:
http://www.autopy.org/
Cool project overall though, nice AI example.
As an aside, I find the whole area of bots automating repetitive human tasks fascinating, here's an excellent book about this topic (did you know a guy wrote a Lisp program that can compose orchestras in the style of Bach and fool human critics?):
http://www.amazon.com/dp/1591844924
In the past I've had a side project involving automating casino games for fun. I followed this tutorial for automating simple web games with Python:
http://active.tutsplus.com/tutorials/workflow/how-to-build-a...
This tutorial uses Python Image Library (PIL) for 'reading' the UI and PyWin to manipulate the mouse in order to play the game. I would suggest using AutoPy instead of PyWin to give platform-agnostic GUI manipulation:
http://www.autopy.org/
Cool project overall though, nice AI example.
As an aside, I find the whole area of bots automating repetitive human tasks fascinating, here's an excellent book about this topic (did you know a guy wrote a Lisp program that can compose orchestras in the style of Bach and fool human critics?):
http://www.amazon.com/dp/1591844924
Very nice article, luckytoilet!
I recently published my own minesweeper AI, and it does only a subset of what your program does. The explanations in your article would be applicable to my work too.
My program plays the pre-Vista/7 version of Windows Minesweeper, so the graphics detection is much simpler. I only implemented a strategy that considers a single cell and its neighbors, a strategy that considers pairs of cells and their neighbors, and random guessing.
http://nayuki.eigenstate.org/page/automatic-minesweeper-solv...
I recently published my own minesweeper AI, and it does only a subset of what your program does. The explanations in your article would be applicable to my work too.
My program plays the pre-Vista/7 version of Windows Minesweeper, so the graphics detection is much simpler. I only implemented a strategy that considers a single cell and its neighbors, a strategy that considers pairs of cells and their neighbors, and random guessing.
http://nayuki.eigenstate.org/page/automatic-minesweeper-solv...
It'd be fun to adapt this for Windows 8's new "adventure mode" minesweeper. There are some significant challenges though; for one, all the numbers are the same color! The nice thing is that you could avoid guessing in many situations by simply using a pickaxe/dynamite/map powerup.
Side note: for those of you inclined to try this, or make use of Java's Robot class in any way, a word of warning: Robot takes over your mouse and/or keyboard entirely, so if things go wrong (e.g. an infinite loop) you'll have to restart your computer. It can do far worse if you're not careful, too, so feel free to read up on the mistakes of others before running in guns blazing.
http://alvinalexander.com/java/java-robot-class-example-mous...