13 ms·

How to Write your own Minesweeper AI

82 points by nostromo 14y ago

benzor 14y ago
Nicely done! 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-mouse-keystroke http://alvinalexander.com/java/java-robot-class-example-mous...
- miahi 14y ago
  It's probably safer to keep it in a VM until you have a finished product.
  - finnw 14y ago
    This kind of product often runs in a VM anyway
  - joeycfan 14y ago
    That's how Skynet got started....
mrgriscom 14y ago
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/ 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.
- vacri 14y ago
  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.
rgarcia 14y ago
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.
endoself 14y ago
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.
- JoachimSchipper 14y ago
  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.
nemo1618 14y ago
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.
csense 14y ago
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 http://web.mat.bham.ac.uk/R.W.Kaye/minesw/ordmsw.htm
huhtenberg 14y ago
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.
- Someone 14y ago
  I remember seeing that debunked, but cannot find that now. What I can find is http://www.minesweeper.info/wiki/Main_Page 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 http://www.minesweeper.info/wiki/Dreamboard). That debunks the theory.
dobbinmicky 14y ago
They turned off the lights before the helicopter airframe hit the surface of the pool. In the dark, the churn of the water that tried to pull me from the four-point harness was the main indication that the helo's cabin was rotating.
patrickk 14y ago
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-python-bot-that-can-play-web-games/ 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/ 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 http://www.amazon.com/dp/1591844924
nayuki 14y ago
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-solver http://nayuki.eigenstate.org/page/automatic-minesweeper-solv...

82 points by nostromo 14y ago

Nicely done! 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-mouse-keystroke http://alvinalexander.com/java/java-robot-class-example-mous...

miahi 14y ago
It's probably safer to keep it in a VM until you have a finished product.
- finnw 14y ago
  This kind of product often runs in a VM anyway
- joeycfan 14y ago
  That's how Skynet got started....

mrgriscom 14y ago

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/ 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.

vacri 14y ago
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.

rgarcia 14y ago

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.

endoself 14y ago

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.

JoachimSchipper 14y ago
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.

nemo1618 14y ago

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.

csense 14y ago

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 http://web.mat.bham.ac.uk/R.W.Kaye/minesw/ordmsw.htm

huhtenberg 14y ago

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.

Someone 14y ago
I remember seeing that debunked, but cannot find that now. What I can find is http://www.minesweeper.info/wiki/Main_Page 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 http://www.minesweeper.info/wiki/Dreamboard). That debunks the theory.

dobbinmicky 14y ago

They turned off the lights before the helicopter airframe hit the surface of the pool. In the dark, the churn of the water that tried to pull me from the four-point harness was the main indication that the helo's cabin was rotating.

patrickk 14y ago

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-python-bot-that-can-play-web-games/ 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/ 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 http://www.amazon.com/dp/1591844924

nayuki 14y ago

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-solver http://nayuki.eigenstate.org/page/automatic-minesweeper-solv...