H
Heiko Wundram
Hi list!
I've written a little program which plays Minesweeper, using quite a simple
algorithm, which I've written in Python (pseudocode):
total_fields = 0
for field in <all possible consistent fields>:
total_fields += 1
for pos in <all positions>:
if pos is marked:
hist[pos] += 1
for pos in hist:
hist[pos] /= float(total_fields)
Now, the only non-trivial algorithm in this program is compute all possible
consistent fields, which does not compute all fields that are consistent, but
only computes those fields which have mines next to already discovered
numbers, to speed things up, and all positions which do not lie to a
discovered field get the standard probability minesleft/fieldsleft, which
should be the same as looping over all possible combinations (if I'm not
mistaken).
What the computer then does is evaluate the histogram: If a position has
probability zero of having a mine: discover it, if it has possibility one:
mark it, and only if there are no positions which have possibility zero or
one: discover a random field from the list of fields which have the lowest
probability of having a mine.
This is done iteratively until no empty fields are left, or a discovery blows
up.
I've let this little program run to check the average number of "solvable"
games on an 8x8 field, with 10 mines (this is the easy setting of any
Minesweeper clone), and I get a number in the range 55-65%.
Now, if I let KMines get the solvability rate for a field of this size, it
spits out a number of 80%...
So, I guess, either my algorithm is wrong (or suboptimal), or KMines algorithm
for solving a field is wrong (taking information into account which it may
not).
If anybody here knows more about game-theory than I do, I'd be happy if he/she
could enlighten me...
For anybody willing to try the program, you can download it here:
http://www.heim-d.de/~heikowu/PyMines.py
In case you don't have psyco installed, comment out all lines which concern
psyco. And be prepared that the runtime is somewhat slow, because the
algorithm used to find the consistent fields is recursive.
Thanks for any help!
Heiko.
I've written a little program which plays Minesweeper, using quite a simple
algorithm, which I've written in Python (pseudocode):
total_fields = 0
for field in <all possible consistent fields>:
total_fields += 1
for pos in <all positions>:
if pos is marked:
hist[pos] += 1
for pos in hist:
hist[pos] /= float(total_fields)
Now, the only non-trivial algorithm in this program is compute all possible
consistent fields, which does not compute all fields that are consistent, but
only computes those fields which have mines next to already discovered
numbers, to speed things up, and all positions which do not lie to a
discovered field get the standard probability minesleft/fieldsleft, which
should be the same as looping over all possible combinations (if I'm not
mistaken).
What the computer then does is evaluate the histogram: If a position has
probability zero of having a mine: discover it, if it has possibility one:
mark it, and only if there are no positions which have possibility zero or
one: discover a random field from the list of fields which have the lowest
probability of having a mine.
This is done iteratively until no empty fields are left, or a discovery blows
up.
I've let this little program run to check the average number of "solvable"
games on an 8x8 field, with 10 mines (this is the easy setting of any
Minesweeper clone), and I get a number in the range 55-65%.
Now, if I let KMines get the solvability rate for a field of this size, it
spits out a number of 80%...
So, I guess, either my algorithm is wrong (or suboptimal), or KMines algorithm
for solving a field is wrong (taking information into account which it may
not).
If anybody here knows more about game-theory than I do, I'd be happy if he/she
could enlighten me...
For anybody willing to try the program, you can download it here:
http://www.heim-d.de/~heikowu/PyMines.py
In case you don't have psyco installed, comment out all lines which concern
psyco. And be prepared that the runtime is somewhat slow, because the
algorithm used to find the consistent fields is recursive.
Thanks for any help!
Heiko.