News for hackers. Stuff that matters.
Re:How to Write your own Minesweeper AI by benzor on Sunday December 23, 2012 @10:43PM (#4961764)
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-mous...

Re:How to Write your own Minesweeper AI by miahi on Monday December 24, 2012 @04:56AM (#4962404)
It's probably safer to keep it in a VM until you have a finished product.
Re:How to Write your own Minesweeper AI by finnw on Monday December 24, 2012 @09:53AM (#4962951)
This kind of product often runs in a VM anyway
Re:How to Write your own Minesweeper AI by mrgriscom on Monday December 24, 2012 @12:21AM (#4961968)
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.

Re:How to Write your own Minesweeper AI by vacri on Monday December 24, 2012 @03:13AM (#4962257)
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.
Re:How to Write your own Minesweeper AI by endoself on Monday December 24, 2012 @01:02AM (#4962044)
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.

Re:How to Write your own Minesweeper AI by JoachimSchipper on Monday December 24, 2012 @07:21AM (#4962657)
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.
Re:How to Write your own Minesweeper AI by csense on Monday December 24, 2012 @02:07AM (#4962142)
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

Re:How to Write your own Minesweeper AI by rgarcia on Monday December 24, 2012 @01:00AM (#4962039)
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.
Re:How to Write your own Minesweeper AI by huhtenberg on Monday December 24, 2012 @04:02AM (#4962323)
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.
Re:How to Write your own Minesweeper AI by Someone on Monday December 24, 2012 @06:13AM (#4962525)
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.

Re:How to Write your own Minesweeper AI by patrickk on Monday December 24, 2012 @06:55AM (#4962607)
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

Re:How to Write your own Minesweeper AI by nayuki on Monday December 24, 2012 @12:45PM (#4963507)
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...

Re:How to Write your own Minesweeper AI by nemo1618 on Monday December 24, 2012 @01:51AM (#4962108)
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.