Somewhat OT... Computer playing Minesweeper

[Heiko Wundram]

Am Mittwoch, 14. Juli 2004 02:55 schrieb Terry Reedy:
> I have no idea what KMines is. 

KMines is the KDE Minesweeper clone.

> I do know that it is easy to undercompute 
> which unexplored positions are knownable as to their true status and which
> therefore can be safely marked or opened.

Hmm... But this is exactly what I'm not doing with the algorithm I chose. It 
always computes all possible consistent combinations of mines surrounding the 
known fields. At least I think it does... If you want to check for yourself, 
have a look at the source, especially at __iterConsistentFields().

> In particular, there are multiposition patterns which are only
> deterministic when considered together.

But pattern matching isn't important in case you compute all possible 
consistent field states, and then simply create a histogram containing the 
percentage of consistent states which had a mine on a position. In case the 
probability of a mine on a certain position is one, there has to be a mine 
(all consistent states had a mine at this position), and in case the 
probability is zero (no consistent state had a mine at this position), you 
can safely discover this field. Consistent state in this respect meaning that 
the state matched the discovered field/mines state.

And, as I already said before, if there are no safe hits/misses, you simply 
choose a position which has the least probability of being a mine for 
discovery.

Basically, it's just about calculating the probability that a mine is at a 
given position. And this is exactly what makeHistogram() does...

Anyway, as I said, I don't know if __iterConsistentFields() does what it 
should, that's basically why I asked... And I don't know whether this 
approach is the best approach to solving a minefield...

Heiko.