Minesweeper AI

This is my first competition so bear with me.

Task:
Write a function that has this prototype:

Code:

---

int solver(MineField &field, int startX, int startY);

---

startX and startY being a position in the field which has 0 adjacent mines.
This functions task is to, with a given field and number of mines, solve this.

This is done by calling GetPosition(int x, int y) and SetPosition(int x, int y). Both located in MineField class. GetPosition will return how many adjacent squares that are mines, or if that square is a mine, it will have the value -1. SetPosition will set the given position to -2, indicating a possible bomb.

Rules:
Your function must immediately return to the main function if GetPosition returns -1. Failure to do so will result in the code going to the trash-can.

Your function must return the number of calls to GetPostition it had made.

Your function will be called only once per test.

The width and height of the field will be max 20, and there will be max 85 mines.

Judgement:
Your code will be judged as follows:
Speed (5* points)
Number of calls to GetPosition (3* points)
How many mines cleared (10* points)

*I reserve the right to change the points as I see fit.

Contest will end may 28th. PM me your submissions.

The MineField class:

Code:

---

#include <vector>
#include <cstdlib>

class MineField
{
private:
        std::vector<std::vector<char> > field;

        int width;
        int height;
        int numMines;
public:
        MineField() { width = 0; height = 0; }
        ~MineField() {}

        void GenerateField(int w, int h, int m);

        int GetWidth() { return width; }
        int GetHeight() { return height; }
        int GetNumMines() { return numMines; }
        void SetPosition(int x, int y)
        {
                field[x][y] = -2;
        }

        char GetPosition(int x, int y)
        {
                return field[x][y];
        }
};

void MineField::GenerateField(int w, int h, int m)
{
        width = w;
        height = h;
        numMines = m;


        int x;
        int y;
        int i;

        field.clear();
        field.resize(width);

        for(i=0; i<width; i++)
                field[i].resize(height, 0);

        for(i=0; i<numMines; i++)
        {
                x = std::rand()%width;
                y = std::rand()%height;

                if(field[x][y] == -1)
                {
                        i--;
                        continue;
                }

                field[x][y] = -1;
        }

        for(x=0; x<width; x++)
        {
                for(y=0; y<height; y++)
                {
                        if(field[x][y] == -1)
                                continue;

                        int left = x-1;
                        int right = x+1;
                        int up = y-1;
                        int down = y+1;

                        if(left < 0)
                                left = 0;
                        if(right >= width)
                                right = width-1;
                        if(up < 0)
                                up = 0;
                        if(down >= height)
                                down = height-1;

                        if(field[left][down] == -1)
                                field[x][y]++;
                        if(field[left][y] == -1)
                                field[x][y]++;       
                        if(field[left][up] == -1)
                                field[x][y]++;

                        if(field[x][down] == -1)
                                field[x][y]++;
                        if(field[x][up] == -1)
                                field[x][y]++;

                        if(field[right][down] == -1)
                                field[x][y]++;
                        if(field[right][y] == -1)
                                field[x][y]++;       
                        if(field[right][up] == -1)
                                field[x][y]++;
                       
                }
        }
}

---

The way I see it, GetPosition() tells the player where the mines are - that's no fun! Please define "selected" and "iteration".

Obviously, you will generate a field and have us solve it. To get a fair competition, I'd like the field to be 'solvable': first uncovered field does not give a bomb and there should not be any guessing involved during the mine finding process. Is this something you are willing (and able) to provide?

Quote:

---

Originally Posted by Togra

The way I see it, GetPosition() tells the player where the mines are - that's no fun! Please define "selected" and "iteration".

---

The way I understood it was that if GetPosition returns a -2, then you have to return out of your function. I'm not real sure what is meant by 'iteration', though.

[edit]In addition, I agree with Togra. A random field is a bad way to judge the effectiveness of a person's algorithm. How about an additional constructor on the MineField object so that you can pass in a good field?

In addition to a good field being used that is solvable, I'm thinking the first square to choose would need to be given to us. I can't proove it, but I'm guessing a solvable field can become unsolvable depending on which square is chosen first.

Heh...I'll prove it. Consider the following 2x2 field with X marking the mine:

Code:

---

1 1
X 1

---

Assuming both rows and columns are zero-indexed from the bottom-left corner, pick the square 0,0. Boom...unsolvable. ;)

In your case pianorain any of the choices make it unsolvable. So that doesn't prove that a solvable field can become unsolvable depending soley on the first choice.

Note: I'm assuming that unsolvable means without guessing. If you mean it in some other way please let me know.

GetPosition returns the number of adjacent mines, if the number is -1 you have hit an unmarked mine, if the number is -2 you hit a marked position, which probably is a mine.

Due to the nature of this a solvable field is hard to generate since you only uncover one square at a time (compare to minesweeper that comes with windows). This will always include some kind of guessing, even the original game. But to make the start a little easier I will modify the function prototype, please see description again.

I will do my best to come up with fields that are solvable but as I said, since you only uncover one square at the time you may end up with an unsolvable field. Try to solve it the best you can (and to clarify, I will use the same field with all algorithms during the judgement).

Togra:
What I mean with selected is that as soon as GetPosition returns -1 you function must return to main.

By iterations (bad wording), I mean the number of calls to GetPosition. I will update the original post.

Code is going to give wrong counts, for example:

Code:

---

Given this board, what's the value under the ?.  Should be 1, but will end up 2 because of code below:

 0 0 0
 ? 1 0
-1 1 0

if(left < 0) left = 0;

if(field[left][down] == -1) // left = 0, down = y+1
field[x][y]++;

if(field[x][down] == -1) // x = 0, down = y+1;
field[x][y]++;

---

The bomb is being counted twice

Quote:

---

Assuming both rows and columns are zero-indexed from the bottom-left corner, pick the square 0,0. Boom...unsolvable.

---

Yeah, I meant assuming you don't blow up on your first pick ;)

Quote:

---

I'm assuming that unsolvable means without guessing. If you mean it in some other way please let me know

---

Yep, thats what I meant.

While ideally it would be best to have a solvable field, if that becomes too difficult then as long as everyone is given the same starting spot then in theory everyone should be able to solve the same amount before having to resort to guessing. So the contest could still be graded based on how your algorithm gets to that point or if it gets there at all. So why not make a rule that no guessing is allowed?

I'd like to see a moderatly difficult board that is solvable with every possible combonation without guessing.

Heh, we could have one contest that generates a solvable field, then another one that solves it.

Of course, I'm not sure how you'd prove a field is solvable without actually solving it...

Although, you could generate a solvable field and give the person the first move, by picking the wrong second move(or any move) they could render it insolvable and because the rest of the field is hidden, there is no way to calculate the right path. In order to be solvable the problem must be deterministic or in other words you don't know the consequences of your actions until you do it. This is not like path finding or min-max, you are dealing with hidden information and no amount of number crunching is going to allow it to be solvable. There is just no way of knowing in advance that revealing a certain block before a certain other block is going to make the grid unsolvable.

Well you'd actually have to do it mathematically. You'd have to show that no matter the path taken you'd still be able to solve it.

Honestly I'm in doubt that such a board could be produced that wasn't something like a 30x30 board with 2 bombs in it. (actually I could prove that is unsolvable :) )

Quote:

---

Originally Posted by Thantos

Well you'd actually have to do it mathematically. You'd have to show that no matter the path taken you'd still be able to solve it.

Honestly I'm in doubt that such a board could be produced that wasn't something like a 30x30 board with 2 bombs in it. (actually I could prove that is unsolvable :) )

---

If you could create a board that no matter the path taken from multiple choices you'd still be able to win, I'd think that would probably be to easy, especially if you don't want guessing. You are basically saying that every time you reveal a square, there will be an guaranteed calculatable continuation ( where's the challenge?). You are basically turning this into a pathfinding competition and not minesweeper.

Actually I disagree. IF you are given the first choice and told that it was solvable from that point, then it doesn't matter what you choose from then on, it will always be solvable. As long as you don't choose a bomb, the correct path will always be there regardless of how many incorrect paths you take.

Can I prove this? Ummm... not exactly... But if you disagree, perhaps a simple counterexample?

Quote:

---

You are basically saying that every time you reveal a square, there will be an guaranteed calculatable continuation ( where's the challenge?). You are basically turning this into a pathfinding competition and not minesweeper.

---

But thats exactly what the competition is, to create an algorithm that solves a minesweeper board. The point is who can create the best and most efficient pathfinding solution. I fail to see how making the program guess at certain points makes it more of a challenge.

How can choosing the wrong order of blocks make it insolvable. I agree that you would need more than one block to start the AI off, but surely after that it will be possible. It can always go back and do another route if one requires guessing, often the 2 will meet up so it can be solved...

Pete

EDIT : looks like i was beaten to making this point...

See I wasn't putting in the additional clause that based on the first choice taht the board would be solvable. I was taking a solvable board and then choosing the first location to prove it unsolvable.

Ok so lets say given a starting point construct a board that is solvable regardless of path taken. But you still have to prove it.

Quote:

---

But thats exactly what the competition is, to create an algorithm that solves a minesweeper board. The point is who can create the best and most efficient pathfinding solution. I fail to see how making the program guess at certain points makes it more of a challenge.

---

Because every minesweeper like game I've ever played had a certain level of intuition assoicated. Where you know a bomb is/isn't in a particular spot just because

Quote:

---

See I wasn't putting in the additional clause that based on the first choice taht the board would be solvable. I was taking a solvable board and then choosing the first location to prove it unsolvable.

---

Ok, that I do agree with.

Quote:

---

Ok so lets say given a starting point construct a board that is solvable regardless of path taken. But you still have to prove it.

---

You're right, at the moment I can't prove that this is always true. I'm only saying this because at the moment I can't think of any possibilities where clicking on a non-bomb can turn it from solvable to non-solvable. I think it would be easier to disprove which is why I was wondering if anyone had a counter-example to prove me wrong.

Quote:

---

Because every minesweeper like game I've ever played had a certain level of intuition assoicated. Where you know a bomb is/isn't in a particular spot just because

---

I'm assuming you mean intuition that is still a guess, like "Chances are the bomb isn't here, but it COULD be". Ok you're right, adding something so that when your program needs to guess it makes the best guess it can possibly make would make it more of a challenge. Any other "intuition" can be programmed and would be expected in a pathfinding solution. But adding chance to the competition could make unpredictable results where a superior algorithm makes the best choice and is wrong while a poor algorithm can make a bad decision and get lucky.

Which is why you never test an algorithm on just one set of input but on many. I would probably do the method of reducing down to all you had left were guesses. Then you'd score the possibilities and the one with the lowest chance of bomb gets chosen.

That would be fine too. I'm guessing something along the lines of "So-and-so's algorithm is the winner because it solved the highest number of grids". Either way would be interesting for me. All depends on how much work Shakti wants to put into the testing program ;)

ok let's try something, here is a simple grid with two bombs (+) what square would you suggest be the first one given so that the AI doesn't have to guess the second?

# + # + #
# # # # #

I challenge anyone to rearrange the 2 bombs in any pattern where they are not adjacent (side-by-side or top-bottom) and suggest a starting spot that won't eventually involve guessing?.


Only an arrangements like this(all bombs adjacent) could yield a starting spot with no guessing, but then I say there is no challenge to it

+ + # # #
# # # # #

I don't understand what you are trying to prove. Neither example is solvable without guessing no matter where you start. The point was if a solvable grid at a starting point can become unsolvable after choosing a non-mine square.

Either contest idea would be fun and challenging, either one that only works solvable grids that is graded on code efficiency and algorithm, or one that solves grids that may need guessing and grades on number of times correct.

It might be easier for our contest host Shakti to leave in the probabilistic element, which just belongs to the game. But at least try to minimalize its effect by letting the players solvers run on many boards!

I also suggest revising the framework: let the true board be known only by the host class, handling the uncovering of positions and placement of bomb marks, terminating the program when a bomb is uncovered. Clean and easy to code, don't you think?

[edit]
language...

I'm still not sure if I'll participate... It might take some serious coding time, also I really need more clarity on how the solver is evaluated.

Another thought, we would need to be given more than just the starting square unless that square was very carefully picked. Anyone who has played Minesweeper knows that you usually have to click anywhere from 1 to 15 random squares before you have something you can work with, and often times have to start over based on pure luck. Wouldn't be fair to the programs that keep accidentally clicking mines at the beginning. Perhaps the program is given a starting square that has no mines next to it?

I guess my point is that you can't make a solvable grid unless you follow a certain overly simplistic pattern ( placing all bombs adjacent to one another) and I believe I can prove it if anyone is interested

ps. in light of the above revelation, I concede that if the grid is solvable, then there are no bad moves

Guess it depends on your definition of simplistic. I've solved Minesweeper a number of times without making any guesses beyond the first couple to get you started, and the mine layout seems no more or less random than other times.

Quote:

---

Originally Posted by PJYelton

Guess it depends on your definition of simplistic. I've solved Minesweeper a number of times without making any guesses beyond the first couple to get you started, and the mine layout seems no more or less random than other times.

---

On easy level, I am sure you probably have solved it quite often without guessing beyond the first couple, but it would be rare that you could do the same on expert, which the proposed max for this is 20x20 which falls in between intermediate(16x16) and and expert(30x16).

Right, percentage needed to guess for intermediate is usually 33-50% on the ones I solve, and expert maybe 5-20%, so infrequent but not impossible. I have no idea how to create a board like this other than for the contest judge to behind the scenes have a function that randomly creates a grid and has his own minesweeper solver try and work it to determine if any guessing is needed. Kind of a hack though.

Anyways, this all depends on how Shakti wants to run it.

I'd offer this suggestion, let the AI guess, but unlike regular minesweeper, don't end the game if you hit a bomb, just penalize the score in some way. This would make guessing more meaningful as a bot might sacrifice blowing himself up once or twice in order to get a clearer picture of the board. Also you alleviate the problem of the bot who by bad luck and hits a bomb on the first try.

I don't think I've ever played a minesweeper game (large) that has been solvable. But usually the guessing involves only 2-3 guesses when the board is almost clear.

I don't see the problem, though. Just make each program solve 100 random boards.

Quote:

---

Originally Posted by PJYelton

I don't understand what you are trying to prove. Neither example is solvable without guessing no matter where you start.

---

If you begin at the bottom-right corner, it is solvable.

Quote:

---

Originally Posted by Sang-drax

If you begin at the bottom-right corner, it is solvable.

---

I don't think so. You mean Darryl's examples, right?

# + # + #
# # # # #
gives a 1 bottom left, after which we have 1/3 and 1/6 guessing options.

+ + # # #
# # # # #
gives me
? ? 1 0 0
? ? 1 0 0
with only 1/2 guesses left.

But enough on the 'solvable' discussion, I want to hear something from Shakti! :)

I don't know how I thought. Of course it is unsolvable!

I think darryls suggestion would be quite good and a possible solution to the solvable/unsolvable problem.

Quote:

---

I'd offer this suggestion, let the AI guess, but unlike regular minesweeper, don't end the game if you hit a bomb, just penalize the score in some way. This would make guessing more meaningful as a bot might sacrifice blowing himself up once or twice in order to get a clearer picture of the board. Also you alleviate the problem of the bot who by bad luck and hits a bomb on the first try.

---

and if everybody else thinks this I am willing to go for it. I will also update the original code to fix the doublecount that occured.

Quote:

---

It might be easier for our contest host Shakti to leave in the probabilistic element, which just belongs to the game. But at least try to minimalize its effect by letting the players solvers run on many boards!

I also suggest revising the framework: let the true board be known only by the host class, handling the uncovering of positions and placement of bomb marks, terminating the program when a bomb is uncovered. Clean and easy to code, don't you think?

[edit]
language...

I'm still not sure if I'll participate... It might take some serious coding time, also I really need more clarity on how the solver is evaluated.

---

I will let the players solver run on many boards with different sizes and different number of bombs, but all solvers will solve the same boards.

And just so you know, the program was never meant to terminate when the solver hit a bomb, only return to main so that the next algorithm could have a go (of course write some score and stuff to a file) at the same field.

Can you be a little clearer on what you mean about "how the solver is evaluated"?

I could not edit the first post (dont know why). Here is the updated code:

Code:

---

#include <vector>
#include <cstdlib>

class MineField
{
private:
        std::vector<std::vector<char> > field;

        int width;
        int height;
        int numMines;
public:
        MineField() { width = 0; height = 0; }
        ~MineField() {}

        void GenerateField(int w, int h, int m);

        int GetWidth() { return width; }
        int GetHeight() { return height; }
        int GetNumMines() { return numMines; }
        void SetPosition(int x, int y)
        {
                field[x][y] = -2;
        }

        char GetPosition(int x, int y)
        {
                return field[x][y];
        }
};

void MineField::GenerateField(int w, int h, int m)
{
        width = w;
        height = h;
        numMines = m;


        int x;
        int y;
        int i;

        field.clear();
        field.resize(width);

        for(i=0; i<width; i++)
                field[i].resize(height, 0);

        for(i=0; i<numMines; i++)
        {
                x = std::rand()%width;
                y = std::rand()%height;

                if(field[x][y] == -1)
                {
                        i--;
                        continue;
                }

                field[x][y] = -1;
        }

        for(x=0; x<width; x++)
        {
                for(y=0; y<height; y++)
                {
                        if(field[x][y] == -1)
                                continue;

                        int left = x-1;
                        int right = x+1;
                        int up = y-1;
                        int down = y+1;

                        if(left < 0)
                                left = 0;
                        if(right >= width)
                                right = width-1;
                        if(up < 0)
                                up = 0;
                        if(down >= height)
                                down = height-1;

                        if(field[left][down] == -1 && down != y)
                                field[x][y]++;
                        if(field[left][y] == -1)
                                field[x][y]++;       
                        if(field[left][up] == -1 && up != y)
                                field[x][y]++;

                        if(field[x][down] == -1 && left != x && right != x && down != y)
                                field[x][y]++;
                        if(field[x][up] == -1 && left != x && right != x && up != y)
                                field[x][y]++;

                        if(field[right][down] == -1 && down != y)
                                field[x][y]++;
                        if(field[right][y] == -1)
                                field[x][y]++;       
                        if(field[right][up] == -1 && up != y)
                                field[x][y]++;
                       
                }
        }
}

---

You cannot have mine-sweeper without guessing.

Code:

---

11
11

---

Where's the mine?

Quzah.