Somewhat OT... Computer playing Minesweeper

[Heiko Wundram]

Am Mittwoch, 14. Juli 2004 15:41 schrieb Christopher T King:
> Rather than trying all possibilities of the mine field as a whole, why not
> just take it one number at a time?  Not all portions of the mine field are
> dependent on the field as a whole; you can greatly decrease the number of
> patterns checked if you work in this way.

The problem being that you cannot check how a certain pattern will react with 
the rest of the board, as you never know how long the pattern is. And this 
would defeat the second step, which selects a random element from the board 
which has the least probability of containing a mine, as this isn't 
necessarily an element which is not next to an element which has been 
discovered already. Which is shown by the following:

Say you have a 16x16 board, with 40 mines. If your first random get selects a 
one (outside of the edge), it's better to select an element next to this 
field, because the chance that you'll hit something is 1/8 = 12.5%, whereas 
selecting a random element from the remaining board (outside of the selected 
square and it's surroundings) will have chance 39/(16*16-9) =15.8% of 
containing a mine. Now if you had discovered a two, it'd be better to select 
a random element, as the chance of hitting a mine next to the two is: 2/8 = 
25%, and on the rest of the board 38/(16*16-9) = 15.4%...

When the board states become more complex, you have no chance but to iterate 
over all possible board states...

What I haven't tried yet (but what might speed things up) is to first create 
regions (areas of discovered squares which are not separated by more than one 
undiscovered square), create all possible states this region can have (which 
are far less than the total number of states), and then after creating this 
for all regions of the current field to cross-product the states and and then 
check each of the cross-products for consistency (with respect to total 
number of mines, which is fast and simple).

> IMHO Python is the wrong language to be doing this in though -- a
> constraint-logic language like Prolog would be much more well suited to
> the task (indeed, you could probably write a Minesweeper solver in a few
> dozen lines of Prolog).  It may be a lot easier to implement a CL
> algorithm in Python, and then to formulate your problem using that.

Hmm... I thought of that already, but I fear my Prolog has left me since I 
last programmed it at univ... ;) But anyway, 334 lines of Python (including 
empty lines) isn't all that bad, at least for my taste, and doesn't 
disqualify Python in the least bit...

Heiko.