Jump to content
  • Advertisement
Sign in to follow this  
Backward

A* applied to minesweeper game

This topic is 1890 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I am trying to make the minesweeper solver. As you know there are 2 ways to determine which fields in minefield are safe to open, or to determine which fields are mined and you need to flag it. First way to determine is trivial and we have something like this:

if (number of mines around X – current number of discovered mines around X) = number of unopened fields around X

then

All unopened fields around X are mined

if (number of mines around X == current number of discovered mines around X)

then

All unopened fields around X are NOT mined

But my question is: What about situation when we can't find any mined or safe field and we need to look at more than 1 field?

10299095.png

For example this situation. We can't determine anything using previous method. So i need a help with algorithm for these cases.

I have to use A* algorithm to make this. That is why i need all possible safe states for next step in algorithm. When i find all possible safe states i will add them to the end of current shortest path and depending on heuristic function algorithm will choose next field that needs to be opened.

Share this post


Link to post
Share on other sites
Advertisement

I don't see why you need A* for this... is it really a graph search?

 

And click the square above the 2 next to the 2 flags... it's safe ;) EDIT: As are all the uncovered squares next to the 1s

 

EDIT2: I'm guessing you need to know HOW to identify those spaces as flagged... I still don't see how it involves A* though... you can probably just brute-force it, or encode in some simple rules for cases like that... The problem arises when you have to guess - you need to assign probabilities for each selection and pick the most safe option.

Edited by Paradigm Shifter

Share this post


Link to post
Share on other sites

76701232.png

 

What now? I am using A* because i have to find the shortest path to find all mined fields. When i find all mined fields algorithm is finished. Shortest path in this case means to find all mined fields but to open minimal number of fields. 

Share this post


Link to post
Share on other sites

I still didn't think about heuristic. For now i want to complete this part about finding all possible safe fields.

Share this post


Link to post
Share on other sites

Well, I'd suggest looking at the places with only 1 safe spot first (i.e. N-1 mines for N unknown spaces), starting with the smallest N (so the 2 in the picture next to 1s would fit the bill). Then you can examine all the combinations (there are N of them) looking for a contradiction.

 

After that it sounds like it is going to be a recursive problem... have you done any googling?

Share this post


Link to post
Share on other sites

Don't assume A* is your answer. A* is essentially Dijkstra's algorithm with a heuristic applied, and if you don't have a good heuristic to use, then skip it and just use Dijkstra's. But even here, Dijkstra's isn't really what you want, because you don't really want a graph search for an optimal path.

 

Minesweeper is NP-Complete, so you're not going to solve it with any polynomial time algorithm (assuming P != NP) (both A* and Dijkstra's are polynomial time algorithms, and as such are not powerful enough to solve this problem).

Edited by Cornstalks

Share this post


Link to post
Share on other sites

Presumably the OP wants to find a way to solve minesweeper using the least number of clicks. I think that is going to be a hard problem, unless you already know the locations of all the mines, then you could graph search it, but that isn't how the game is played... (EDIT: The game also cheats for you on the first move, it is never a mine... presumably it moves the mine elsewhere in that case - on Windows anyway).

 

You can get a situation where you have to make a guess, in that case you need to work out the guess least likely to reveal a mine but that is a probability question rather than a graph search one. Sometimes you end up with a 50-50 win/lose choice though... so it can be just a coin flip.

Edited by Paradigm Shifter

Share this post


Link to post
Share on other sites

There are some rules for that what you said. I have to make this for my homework but there are 2 rules:

1) I will get already opened minefield at start

2) Those test cases will be made without a need to guess anything. So i am sure there won't be 50/50 cases. I will always be able to find safe fields.

Share this post


Link to post
Share on other sites

There's a big difference between "opened minefield" and "locations of all mines known at the start"... if you don't know the locations of ALL the mines (i.e. you have missing information) I can't see a way to use a graph search...

 

Every click removes exactly 1 blank space unless there are no adjacent mines (when it does a flood fill of all 0 neighbouring mine squares)... but there is no way to know which squares will be 0s in advance...

Edited by Paradigm Shifter

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!