Minesweeper AI

This is a discussion on Minesweeper AI within the Contests Board forums, part of the Community Boards category; Originally Posted by Sang-drax If you begin at the bottom-right corner, it is solvable. I don't think so. You mean ...

  1. #31
    Registered User
    Join Date
    Mar 2005
    Posts
    38
    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!

  2. #32
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    I don't know how I thought. Of course it is unsolvable!
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  3. #33
    Registered User
    Join Date
    Aug 2003
    Posts
    1,205
    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"?
    Last edited by Shakti; 05-11-2005 at 10:53 AM.
    STL Util a small headers-only library with various utility functions. Mainly for fun but feedback is welcome.

  4. #34
    Registered User
    Join Date
    Aug 2003
    Posts
    1,205
    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]++;
    			
    		}
    	}
    }
    STL Util a small headers-only library with various utility functions. Mainly for fun but feedback is welcome.

  5. #35
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    You cannot have mine-sweeper without guessing.
    Code:
    11
    11
    Where's the mine?

    Quzah.
    Hope is the first step on the road to disappointment.

Page 3 of 3 FirstFirst 123
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Simple space combat AI
    By VirtualAce in forum Game Programming
    Replies: 5
    Last Post: 01-05-2009, 11:54 PM
  2. AI Contest - Minesweeper
    By Darryl in forum Contests Board
    Replies: 93
    Last Post: 04-24-2006, 05:48 PM
  3. chess ai contest
    By Raven Arkadon in forum Contests Board
    Replies: 7
    Last Post: 07-09-2005, 06:38 AM
  4. Game Design Topic #1 - AI Behavior
    By TechWins in forum Game Programming
    Replies: 13
    Last Post: 10-11-2002, 10:35 AM
  5. Technique of all board-like games?
    By Nutshell in forum Game Programming
    Replies: 28
    Last Post: 04-24-2002, 08:19 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21