in reply to App::SweeperBot - Perl plays minesweeper, automatically.

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:

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.

[download]

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

Replies are listed 'Best First'.
Re^2: App::SweeperBot - Perl plays minesweeper, automatically.
by pjf (Curate) on May 23, 2008 at 09:52 UTC

    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,

    Paul Fenwick
    Perl Training Australia
[reply]
Re^2: App::SweeperBot - Perl plays minesweeper, automatically.
by pjf (Curate) on May 24, 2008 at 05:41 UTC

    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;

    [download]

    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.

    Paul Fenwick
    Perl Training Australia
[reply]
[d/l]
Re^2: App::SweeperBot - Perl plays minesweeper, automatically.
by ambrus (Abbot) on May 24, 2008 at 11:44 UTC

    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.

[reply]

In Section Cool Uses for Perl