Here's a fun, frivolous, and simple little program I wrote recently 
which seemed just interesting enough to share.  The idea is to write an 
AI assistant for the game of minesweeper.  The trickiness is that 
sometimes every available square has a chance of having a mine on it, so 
running a basic constraint satisfaction algorithm on it won't give you 
any useful information.

Instead, you can generate a sequence of random mine assignments which 
are each consistent with the numbers on the currently visible squares 
and then calculate a running average of the probability that each square 
has a mine.  In some cases this probability is 100% or 0%, in which case 
it (with high likelihood) gives you the same result as a standard 
logical deduction would, but in other cases the probabilities are very 
useful for making a move.

It's fun to watch the colors flicker around and then quickly converge to 
an answer, and to see the ways in which different patterns interact with 
each other.  Attached are a couple of screenshots.  Blue is low 
probability and red is high probability.  Squares with 100% or 0% 
probability are highlighted with a white border.

Post a reply to this message

Attachments:
Download 'monte_carlo_minesweeper1.png' (10 KB) Download 'monte_carlo_minesweeper2.png' (12 KB)

Preview of image 'monte_carlo_minesweeper1.png'

Preview of image 'monte_carlo_minesweeper2.png'

Really cool - where's the program, again? :)

-- 
...Chambers
www.pacificwebguy.com

Post a reply to this message

On 4-4-2009 8:49, Kevin Wampler wrote:
> Here's a fun, frivolous, and simple little program I wrote recently 
> which seemed just interesting enough to share.  The idea is to write an 
> AI assistant for the game of minesweeper.  The trickiness is that 
> sometimes every available square has a chance of having a mine on it, so 
> running a basic constraint satisfaction algorithm on it won't give you 
> any useful information.
> 
> Instead, you can generate a sequence of random mine assignments which 
> are each consistent with the numbers on the currently visible squares 
> and then calculate a running average of the probability that each square 
> has a mine.  In some cases this probability is 100% or 0%, in which case 
> it (with high likelihood) gives you the same result as a standard 
> logical deduction would, but in other cases the probabilities are very 
> useful for making a move.

The lower one has at least 5 positions where you will end up having a 
50% change and no additional information. The change of surviving this 
minefield are therefore below 3%. Possibly much below that if you have 
had to guess before arriving at the current position. That is not good 
for a game. Perhaps you can employ something like this to find grids 
that can be solved with a reasonable chance.

Post a reply to this message

andrel wrote:
> The lower one has at least 5 positions where you will end up having a 
> 50% change and no additional information. The change of surviving this 
> minefield are therefore below 3%.

It's not quite as bad as it looks since the groups on the upper right 
are actually connected to the large unsolved section, so it should be 
possible to solve them indirectly by starting at the lower probability 
blocks on the lower right.  The two on the left there's nothing you can 
do about though.

> Perhaps you can employ something like this to find grids 
> that can be solved with a reasonable chance.

I've thought about this too since the 50% guess patterns are pretty 
annoying.  I probably won't end up actually getting around to it unless 
I get a spurt of renewed interest, but it's a neat idea.

Post a reply to this message

Chambers wrote:
> Really cool - where's the program, again? :)

If you're interested I can post the source, although I'll want to 
comment it and clean it up a touch first.  It's not very complicated 
though, just 700 lines of python, most of which is the user interface.

Post a reply to this message