![](/i/fill.gif) |
![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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'
![monte_carlo_minesweeper1.png](/povray.off-topic/attachment/%3C49d70311%40news.povray.org%3E/monte_carlo_minesweeper1.png?preview=1)
Preview of image 'monte_carlo_minesweeper2.png'
![monte_carlo_minesweeper2.png](/povray.off-topic/attachment/%3C49d70311%40news.povray.org%3E/monte_carlo_minesweeper2.png?preview=1)
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Really cool - where's the program, again? :)
--
...Chambers
www.pacificwebguy.com
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |