Somewhat OT... Computer playing Minesweeper
heikowu at ceosg.de
Wed Jul 14 16:26:25 CEST 2004
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...
More information about the Python-list