h2g2 The Hitchhiker's Guide to the Galaxy: Earth Edition

I'd actually intended to update that last section with some actual figures - looks like I've left it a little on the late side. I'll try and post some numbers here in the next few days, so they can be included... because my 'one in five' statement is not only ambiguous, it's also not very accurate.

As it turns out, my AI plays considerably better than most human players, and can win quite a lot more often that you might expect. Something like 0.5 chance of winning for a beginners board, 0.3 for an experts... I think. My other PC is currently hard at working playing Minesweeper with itself - we should know fairly soon.

26199

Right... my results thus far:

On a beginner's board (8x8, 10 mines), you should be able to win 55%-60% of the time.

On an intermediate board (16x16, 40 mines), you should be able to win 40%-60% of the time. I'm currently collecting more results to narrow down this somewhat over-wide margin...

I'll be testing on the expert board, next... but this might take quite a while...

26199

Right, I've now got some decent results for the intermediate board... chance of winning with a perfect strategy is 45%-52%.

I'll try and get some results for the expert board (30x16, 99 mines)... but I'm not sure my computers can handle it - it could be a loooong while.

26199

How long does it take to compute a board using your algorithm? What's its complexity: does this time increase linearly, exponentially...?

Beginner boards take typically less than a second; intermediate take perhaps ten seconds. Both occasionally take a lot longer if the program comes across a particularly awkward combination of information.

Expert boards, on the other hand, take anything from a minute to perhaps half an hour. As the size of the board increases, so does the number of mines and the clumpiness of the distribution of the mines. This means increase in computing time is extremely nasty.

On the other hand, I haven't used *any* hash tables or things of that kind, and my current program recalculates all probabilities every time it moves. I imagine that with some work processing time could probably be reduced by a factor of 10-1000, and increase in computing time could probably be reduced to near-linear.

The program is considerably faster than a human player, though, so I've not bothered thus far... especially since adding any complications might detract from the 'perfect strategy' ideal.

26199

(Running on a Celeron 400)