We think we have found project that will take over our holiday free time. [Bai Li] just published an excellent article about writing a program that can automatically solve the game of Minesweeper. For those of you who are unfamiliar, Minesweeper gives you a grid in which land mines have been randomly placed. As you click on boxes to reveal what is underneath you are greeted with a number which represents how many mines surround that box. [Bai’s] project examines how the puzzle may be solved programmatically.
He chose to use Java to write the solver. This works well both reading from the screen as well as simulating mouse clicks on the game. The reading portion of the program uses color detection with a screenshot. There were two problems associated with this, the numeral one is almost the same color as an uncovered square, and the numerals seven and three use identical colors. The input portion was much simpler as he’s able to use the existing Robot class.
The logic behind writing an efficient solver is very interesting. One of the most fascinating examples is shown above. What should you do when there is no possible way to ensure a safe move? As with traditional chess games, [Bai] has the solver calculate all possible solutions and choose the move that has the best odds of success.
His source code is available, but won’t this one be fun to hack out from the concepts alone? For some reason this seems more accessible to us than something like the Bejeweled Blitz solver.
[via Reddit]
I’ve thought of doing this too. The question I want to answer is: given that many games end with you having to guess where the mine is, what is the best percentage of games you can expect to win?
on expert, I had to guess at least once in almost every game I played. I’d be more inclined to use code from this solver to write a game that doesn’t need any guessing.
If you’re getting those results then you need to think more in minesweeper. At worst I come across a 50/50 at the end about 30% of the time. Leaving about a 15% failure rate for a program. Necessary early guesses can be passed probably about 75% of the time when one plays the odds. The random necessary guessing would actually allow a pretty interesting test for how intelligent your solver is. Does it just put bombs based on what is directly implied, or can it rule out possibilities and predict blank areas.
Set every field in memory to “no mine”
Problem solved
You mad?
That assumes root access, since modifying the memory of other programs is not something an unprivileged program can do.
However, the screenshots ARE of Windows, so… :P
Guess analysis can actually go deeper than simply choosing the safest place to guess. There are many cases where a single more risky guess can replace a series of lower risk guesses. For example, if I had 3 squares, each with an equal chance of being a mine, it’s very possible to run into a situation where the next rational decision is the 50/50 chance that remains (assuming the revealed square would not offer enough information to avoid a second guess.) For this reason, it’s often important to look several moves ahead, much like chess, to determine the value/risk of a given move. Doing this would significantly increase the win % of the minesweeper bot.
If anyone ever needs a litmus test of what makes someone destined for the STEM fields, this is it. Building the solver is more fun and inspiring than the game itself.
To be pedantic, this program will solve many games of Minesweeper, not all. Minesweeper has been shown to be NP complete, so if someone worked out how to solve all Minesweeper puzzles computer science would be revolutionized. Banking security and privacy would be devastated as cracking public key cryptography is also NP complete.
If you’re going to get technical, the puzzle being NP complete merely comments on the time it takes to solve a given puzzle. If someone were able to solve all games of Minesweeper it doesn’t necessarily mean that they have done anything more than thrown lots of cpu time at the problem. If they were to create an algorithm which is able to solve any arbitrary minesweeper game in polynomial time that would be something to write home about.
wonder if the bot is using the old MS minesweep cheat :p
xyzzy