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.
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.
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 becauseBut 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.
Ok, that I do agree with.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.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.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.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.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
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.
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
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
+ + # # #
# # # # #
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.
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.
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?
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.
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).Originally Posted by PJYelton
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.
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.
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.
If you begin at the bottom-right corner, it is solvable.
Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling
