Minesweeper AI

This is a discussion on Minesweeper AI within the Contests Board forums, part of the Community Boards category; How can choosing the wrong order of blocks make it insolvable. I agree that you would need more than one ...

  1. #16
    Registered User
    Join Date
    Jul 2004
    Posts
    17
    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...
    Last edited by Pete; 05-10-2005 at 01:22 PM.

  2. #17
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    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.

    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

  3. #18
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    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.
    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.
    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.

  4. #19
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    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.

  5. #20
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    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

  6. #21
    Tropical Coder Darryl's Avatar
    Join Date
    Mar 2005
    Location
    Cayman Islands
    Posts
    503
    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

    + + # # #
    # # # # #

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

  8. #23
    Registered User
    Join Date
    Mar 2005
    Posts
    38
    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.
    Last edited by Togra; 05-10-2005 at 04:16 PM.

  9. #24
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    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?

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

  11. #26
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    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.

  12. #27
    Tropical Coder Darryl's Avatar
    Join Date
    Mar 2005
    Location
    Cayman Islands
    Posts
    503
    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).

  13. #28
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    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.

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

  15. #30
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    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.
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

Page 2 of 3 FirstFirst 123 LastLast
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