Minesweeper AI

[Togra]

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!

[Sang-drax]

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

[Shakti]

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

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.

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"?

[Shakti]

I could not edit the first post (dont know why). Here is the updated 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]++;
			
		}
	}
}

[quzah]

You cannot have mine-sweeper without guessing.

11
11

Where's the mine?

Quzah.