# Thread: Minesweeper AI

1. ## Minesweeper AI

This is my first competition so bear with me.

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]++;

}
}
}```

2. 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?

3. 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.

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?

4. 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.

5. 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.

6. 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.

7. 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.

8. 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

9. 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
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?

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

11. 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...

12. 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.

13. 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 )

14. 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.

15. 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?

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.

Popular pages Recent additions