Thread: Minesweeper AI

  1. #1
    Registered User
    Join Date
    Aug 2003
    Posts
    1,218

    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]++;
    			
    		}
    	}
    }
    Last edited by Shakti; 05-10-2005 at 10:04 AM.
    STL Util a small headers-only library with various utility functions. Mainly for fun but feedback is welcome.

  2. #2
    Registered User
    Join Date
    Mar 2005
    Posts
    38
    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. #3
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,401
    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?
    Last edited by pianorain; 05-10-2005 at 07:12 AM.
    If I did your homework for you, then you might pass your class without learning how to write a program like this. Then you might graduate and get your degree without learning how to write a program like this. You might become a professional programmer without knowing how to write a program like this. Someday you might work on a project with me without knowing how to write a program like this. Then I would have to do you serious bodily harm. - Jack Klein

  4. #4
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    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. #5
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,401
    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.
    If I did your homework for you, then you might pass your class without learning how to write a program like this. Then you might graduate and get your degree without learning how to write a program like this. You might become a professional programmer without knowing how to write a program like this. Someday you might work on a project with me without knowing how to write a program like this. Then I would have to do you serious bodily harm. - Jack Klein

  6. #6
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    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. #7
    Registered User
    Join Date
    Aug 2003
    Posts
    1,218
    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.
    STL Util a small headers-only library with various utility functions. Mainly for fun but feedback is welcome.

  8. #8
    Tropical Coder Darryl's Avatar
    Join Date
    Mar 2005
    Location
    Cayman Islands
    Posts
    503
    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
    Last edited by Darryl; 05-10-2005 at 10:54 AM.

  9. #9
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    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?
    Last edited by PJYelton; 05-10-2005 at 10:58 AM.

  10. #10
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    I'd like to see a moderatly difficult board that is solvable with every possible combonation without guessing.

  11. #11
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    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. #12
    Tropical Coder Darryl's Avatar
    Join Date
    Mar 2005
    Location
    Cayman Islands
    Posts
    503
    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.
    Last edited by Darryl; 05-10-2005 at 12:42 PM.

  13. #13
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    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. #14
    Tropical Coder Darryl's Avatar
    Join Date
    Mar 2005
    Location
    Cayman Islands
    Posts
    503
    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.

  15. #15
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    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 subscribe to a feed

Similar Threads

  1. Simple space combat AI
    By VirtualAce in forum Game Programming
    Replies: 5
    Last Post: 01-06-2009, 12:54 AM
  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