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

Why do we need such a holistic approach. Surely we need only look at one square at a time? Something like this:

(Initial random clicking)
Iterate through all squares
IF square already clear NEXT
If square NOT adjacent to cleared square NEXT
IF square has zero prob of having a mine STEP & restart iteration
IF squarte has 100% prob of having a mine FLAG & restart
IF square has lowest prob so far, remember square
IF beyond last square, STEP on remembered square ( which will have the lowest prob )
IF all mines flagged FINISH
restart iteration

This is also how I would attempt this problem. One thing that hasn't been mentioned though, is how to calculate the probability that a square contains a mine. Here is how I would do it.

If the square is adjacent to 1 or less stepped-on squares, then it is obvious what the probability is. However if it is next to 2 or more, things get tricky. Without having thought too hard about it, I would think that the best strategy would be to take the maximum of the probabilities found by considering each adjacent square individually.

For example, if you know from square A that there is a 60% chance that there is a mine in the square and from square B that there is a 75% chance that it contains one, then set the probability for this square to be 75%. This is obviously a careful approach. A more reckless one would be to take the average instead. I would be interested to see which worked better.

There is a special case - if one of the adjacent stepped on squares indicates zero mines, then this zero probability over-rides the probability indicated by any other adjacent stepped on squares.
Otherwise, I think that if all adjecent stepped on squares indicate one or more mines could be present, then the program has to assume the highest probability. Every posibility would have to be considered ( there are not prohibitively many - a reason that this is more an algorithmic question rather than an AI ) to be sure there did not exist other special cases.

I tried to get a program to play using simple rules of thumb and local logic; it didn't work out too well. Try it yourself... it is incredibly difficult to come up with rules which work consistantly. Well, I couldn't do it with an hour or so's messing about...

The approach outlined in the article has the advantage that it is, in effect, a perfect strategy. Strategies undoubtedly exist which require less calculation, but they require more complicated rules: my approach to the problem is the most simple, most general approach which guarantees that I haven't missed anything.

What would be interesting would be to combine my algorithm with another which generates simple rules for playing minesweeper - a heuristic generation algorithm. It'd be possible to produce something which uses my perfect, if calculation-intensive, strategy to produce equally perfect rules-of-thumb...

I'd love to do just that, 'cept I don't exactly have the time right now. If there are any programmers out there interested in such a project, I'd love to collaborate...

26199

Do you see a problem with the algorithm I have proposed?

How does it work out the probabilities?

Anything which doesn't consider the whole board isn't making use of the information about the number of mines remaining, which can occasionally be crucial...

26199

Very simply:

for all stepped on squares
if number of mines indicated = zero
assign zero prob to adjacent hidden squares
else
divide number of mines indicated by number of adjacent hidden squares
assign ratio to hidden squares, unless hidden square have zero or prob greater than just calculated

[Broken link removed by Moderator]
and
[Broken link removed by Moderator]
and
[Broken link removed by Moderator]
and
http://www.wirehub.nl/~berto/itsmine.htm
and
[Broken link removed by Moderator]
and ... oh what the heck...
http://www.google.com/search?q=solver+minesweeper+program&num=10&meta=hl%3Den%26lr%3D&safe=off

And I was having so much fun thinking about this for myself. As a mathematician, I find this feeling all too familiar; As soon as you find something interesting to investigate, you find that someone else has written a thesis on it.

Those IF rules sound like a good approach. But I wouldn't call this
Artificial Intelligence (I know you didn't claim it to be either). After all, you came up
with the rules, so the intelligence at work is yours, right?

It would be really interesting to let a computer find these rules by
trial and error. Something like reinforcement learning could surely be used.
Give the system a set of options (like your NEXT, STEP & restart iteration etc), then
reward the system each time it makes a move that clears a square, and punish it each
time it hits a bomb. This is not all the way, I know. You still have to tell the system
which options it has...

'Fraid that won't work, Raven... some positions of mines rule out others, so just taking the probability as the number of mines around a square divided by the number of spaces doesn't tell the whole story.

Consider something like a whole load of '1's in a row... quite often it's possible to work out where the mines must be, by reasoning 'if there was a mine here, there couldn't possibly be one here'... that sort of thing.

Arguing that it ain't AI because I specified the rules is somewhat complicated... after all, it plays minesweeper much better than I do...

26199

Arguing "if there was a mine here then there cant be one here" is a sort of proof by contradiction method of finding safe squares. Raven's algorithm doesn't use this strategy, however I cant think of an example off the top of my head where Raven's algorithm doesn't find a safe move but this method does. If I come up with one then I will post it.

As for the AI debate, I would say that it depends on your definition of AI. I think technically a program doesn't have AI unless it passes the Turing test and to the best of my knowledge nothing has done that yet. However many people use AI in a much looser sence to mean any program that has does something a human usually does (eg play chess).

You say that your program plays minesweeper better than you do but if you followed your own rules then you would play equally well. The only difference between you and your program is that it does it much faster and doesn't make mistakes. Two things that computers are very good at.

The definition of AI is, as you point out, a tricky one. Intelligence is hard enough to define by itself...

You're right: if I followed my own rules, I could play as well as my computer - if not as quickly. Therein lies an interesting problem. What if I wrote a computer program which simulated a person more intelligent than myself? Not, I admit, very likely... but if you accept that intelligence is merely an emergent property of whatever the brain is made of, it's got to be theoretically possible.

Now, I can take this program and work through every step on paper... thus simulating an intelligence greater than my own, simply by following my own rules...

So... does being able to emulate something yourself necessarily mean it isn't genuine intelligence? Not that I'm claiming my program is intelligent, but this is an interesting philosophical problem, I think...

I could be wrong

26199

I don't think it would be possible to write a program to simulate someone cleverer than yourself - you certainly couldn't do it for this problem. How can you get tell a computer to do something that you don't know how to do yourself?

It might be possible for you to write a program that can learn to do stuff that you can't, but you'd have to find someone else to teach it.

How about something which uses a genetic algorithm or some such to find an algorithm appropriate to the particular problem?

26199

Define "clever"... as far as I'm concerned, speed is an important part of intelligence.

I could easily write a program that played "perfect" chess, simply by evaluating to an infinite depth. But it would be less clever than Kasparov, because it would take a length of time longer than the age of the universe to make it's first move.

So I would say that you can simulate someone clever than yourself, but in the process of simulation, you would (a) be slower, (b) make mistakes.

Yep, that sounds about right.

26199