Beefy Boxes and Bandwidth Generously Provided by pair Networks
Don't ask to ask, just ask
 
PerlMonks  

App::SweeperBot - Perl plays minesweeper, automatically.

by pjf (Curate)
on May 22, 2008 at 12:52 UTC ( #687947=CUFP: print w/ replies, xml ) Need Help??

G'day everyone,

A couple of years ago at OSDC I was playing around with some code to play minesweeper under Windows. It formed an interesting curiosity, and a fun lightning talk, but the code had so many dirty hacks and odd dependencies that it wasn't exactly portable.

Well, all that's changed. With the help of pp I've released App::SweeperBot, which includes a ready-to-use Windows executable, with no pre-existing Perl installation required at all.

Of course, the best way to see it in action is to go to sweeperbot.org and watch the video, which if nothing else should give you a good laugh. ;)

The code at the moment is still awful (read: big ball of spaghetti mixed with mud), the documentation is poor, the build process is fragile, and the image recognition code could be made at least an order of magnitude faster. But it does play a good game of minesweeper. ;)

Comment on App::SweeperBot - Perl plays minesweeper, automatically.
Re: App::SweeperBot - Perl plays minesweeper, automatically.
by Limbic~Region (Chancellor) on May 22, 2008 at 19:00 UTC
    pjf,
    Very cool. I have often thought about writing a minesweeper solver since it is a tough problem (NP Complete). I just never got around to it. I did a 20 second scan over your source to see what strategies you used and didn't really see any other than:
    • If I can cheat - cheat
    • If all the adjacent bombs have been flagged - clear the rest
    • If all the remaining unflagged adjacent squares add up to the number on the current square - flag them all as bombs
    • If none of the above, choose at random

    I haven't read any minesweeper strategy guides, but I personally have more complex rules than above. For instance

    ??????? 121 Becomes ? B B ? 121 Because in order for the 2 to hold it would have to be one of the foll +owing ??BB??? 121 or ???BB?? 121 or ??B?B?? 121 And only the last one doesn't violate the rules of the "1" block.

    Another strategy I use towards the end of the game when there are not that many unknown bombs remaining. For instance, you have X squares that have unsatisfied constraints, Y unflagged bombs, and Z unclicked/unflagged squares. If the total number of unsatisfied constraints of X squares accounts for all of the Y unflagged bombs then all of the Z unclicked/unflagged squares that are not adjacent to any of the X squares are not bombs.

    My final strategy is when I have to guess. Rather than picking any square at random, I use a relationship to the number of unflagged/unclicked squares in an "area" to the number of bombs remaining. I choose areas where there is less of a chance of choosing a bomb. Of course, this strategy is probably not mathematically sound.

    Have you considered incorporating any of these (or more advanced strategies)? I would be happy to contribute since that would be easier than developing my own code.

    Cheers - L~R

      Your summary of SweeperBot's current strategies are correct, although by default cheating is only done as a last resort (if we're guessing, and would have stepped on a mine, guess again).

      I agree that the current logic is very sub-optimal, most of it was hacked together during coffee breaks at OSDC a few years ago, when I was preparing for talks, and hasn't been touched since. A better AI and faster image-handling are the two areas I think have the greatest scope for improvement.

      I would love contributions towards the AI, and would be very happy to accept submissions and suggestions. My current goal is to try and get the code cleaned up and properly documented with a decent test suite; the original code from Matt Sparks used a lot of package variables, and many of them are still present in the code I've released.

      Patches are extremely welcome, and I'll see if I can find a suitable way to make my git repository accessible to assist that. However please don't let that hold you up; any patches against what's released on the CPAN will apply just fine (I'll make sure of it).

      Best regards,

      A new release (0.03) of App::SweeperBot is being uploaded to the CPAN as I write this.

      The new version uses a simple OO design from which you should be able to inherit cleanly. If you want to replace the AI, it should be as simple as:

      package App::SweeperBot::Smarter; use base qw(App::SweeperBot); sub make_move { my ($this, $game_state) = @_; # Your AI goes here. } 1;

      You can find what's in a given square using $game_state->[$x][$y]. Note that App::SweeperBot considers (1,1) to be the top-left square (not (0,0)).

      The new release has all entire API documented; there are methods for stepping on squares, flagging squares, stomping (middle-clicking) on squares, and a few helpers for things like "how many unknown mines are adjacent to this square"?

      Feedback, questions, and criticism all welcome.

      Well, look. The rule you already explained goes like this. Take any square you've already guessed. Calculate the number the program has given for that square minus the number of known mines adjacent to it: let this difference be D. Tally the number of adjacent unknown squares, let their number be S. If 0 == D, you mark all adjacent unknown squares as non-mines and guess them; if S == D, flag all of them as known mines; if D is something in between, do nothing; if D < 0 or S < D, then you've done something wrong.

      (The third rule you gave is quite similar but you use the number of total mines instead of the number written on one square, and take all fields of the board instead of just the adjacent fields.)

      But there's a more complicated rule that you can also apply. Take any two squares you've guessed with distance less than 3, and for each of the two, calculate the difference of the number you've got from the program for it and the number of known mines adjacent to it: this difference is D_0 for the first square and D_1 for the second. Tally the number of unknown squares adjacent to the first square, this number is S_0. Also tally the number of unknown squares adjacent to both squares at once, this number is C. Now if D_1 <= C and D_0 - D_1 == S_0 - C then you can mark as mines all squares adjacent to the first square but not adjacent to the second square, and mark as non-mine all squares adjacent to the second square but not adjacent to the first square; if D_1 <= C and D_0 - D_1 > S_0 - C then you've done something wrong. Do this also with the two squares in swapped role.

Re: App::SweeperBot - Perl plays minesweeper, automatically.
by ambrus (Abbot) on May 22, 2008 at 21:55 UTC

    Really cool!

Re: App::SweeperBot - Perl plays minesweeper, automatically.
by Cap'n Steve (Friar) on May 25, 2008 at 04:39 UTC
    Nice work. Have you been keeping track of its best scores? It does quite well on the smaller sizes, but can't beat me at expert yet. It might also be interesting to record the time when it gets to the point where it can't continue without guessing, which is apparently what the "pros" do (bunch of cheaters!).

    There's also some interesting strategy articles at www.planet-minesweeper.com.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: CUFP [id://687947]
Approved by marto
Front-paged by Arunbear
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others rifling through the Monastery: (18)
As of 2014-08-29 16:24 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The best computer themed movie is:











    Results (282 votes), past polls