This is perhaps what may be considered as the 'hard part' of a minesweeper solver program. It will gather various data about the minesweeper window and can determine the value of a single square anywhere on the mine field. As indicated in the comments, after finishing the framework, I didn't want to contruct the algorithm for systematically solving the mine field, nor did I know the best way to go about it. Ideas?
Oops. Link: http://labs.f0rked.com/minesweeper.pl
This is a problem I've been thinking about over the years on and off, but I never got around to doing any real work on it.
One idea: Use linear algebra. The unopened squares neighbouring on opened ones are variables, and you use the opened numbers to set up equations to try and solve.
If you have this kind of setup (X, A, B, C D are unopened squares, and this is only a fragment of the real playfield):
XXA1
XXB2
XXC2
XXD1You can find the equations:
A+B=1 (1)
A+B+C=2 (2)
B+C+D=2 (3)
C+D=1 (4)
Which is easily solved - for instance, (2)-(1) gives C=1, insertion in (4) gives D=0, insertion in (3) gives B=1, and (1) gives A=0.
Doing this in the general case is a lot trickier, especially since there won't be complete solutions for any given set of equations. I'm sure there's a lot of linear algebra solving code to learn from, though.
The only problem I see with trying to break it, is making the first move since we don't have a clue (lol xyzzy) as to which squares are loaded, and which are not.
Since every field has the same chance of being loaded before a move has been made, I think it's safe if some sort of random generator just picked a field.
Strategically, maybe you would also want to consider whether a move with as much neighbouring fields as possible will get you an easier start than one done on the sides... I dunno about that, tho.
I'm not too familiar with minesweeper, but I'd probably do it by summing weighted values onto each hidden square based on values at the edge. Ie, squares adjacent to a 1 would have 9-1 added to them for every adjacent 1, adjacent to 2 would have 9-2, 3 would have 9-3, etc.
The reduced values for squares adjacent to values of 2 or higher will ensure the algorithm always chooses the less-risky first.
The next move would be the square with the highest resulting sum.
After a bit of thought, the above would only work for a minesweeper variant I used to play on an HP-48. The windows one works quite a bit differently, but I'd still use a similar process.
Instead of attempting to solve which squares have mines, it's probably easier to solve which squares don't. Make an algorithm that avoids high values.
That's against the spirit of Minesweeper, which is mostly a deterministic game where you can logically prove which squares have mines or not. Probabilities have no place in it except in really tricky situations where there is not enough information.
The algorithm is entirely deterministic; you don't even need an RNG. If two or more possible moves have the same value, a naive scanning of the evaluated values list will always return the same move.
Besides, how do we often solve combinatonic problems? By asking the opposite question and subtracting the result from the universal set. This is no different.
Yes, but you're talking about "risks" - that implies you do not mathematically prove that a square is empty or filled, but that you are evaluating risks. That's not how you play Minesweeper. A real game of Minesweeper is played by proof, and not by minimization of risk.
I'm not certain I understand your argument. If the algorithm works, why should I care? Chess isn't played by evaluating all viable moves in a minimax tree to a depth of x ply either, but that's how Deep Blue did it.
Not that the two are mutually exclusive. In order for a proof-based algorithm to work, it'll need to avoid risky moves until it has sufficient information to be certain where a mine is.
Which is exactly how you play minesweeper. There is nearly always enough information to prove at least one square is safe, and thus you open that one. You will sooner or later run into a situation where you cannot prove any square to be safe, and it's then and only then that you should start calculating probabilities.
I am enjoying you two having a "gentlemen's argument" about this problem.
>>12
If you prove a square is a mine, then what? Marking it doesn't open up new areas to explore, unless I've misunderstood Windows Minesweeper. You'll still evaluate a least-risk square to explore next.
My stance is that a pure least-risk approach is just as much a proof as solving linear equations, so long as the number of mines are known. I don't mind that it doesn't play like a human, although the human-like approach is certainly a more interesting problem.
Whoops, nix that, I misread part of >>12.
the only time you can be sure of mined squares is when the number of unopened squares around a opened square equals the number on the opened square.
so, you start clicking randomly until you find such a case (you will usually find more than one after you click on a 0-numbered square)
then you mark all the ones that you can be sure of (as defined above; if you can't find any go back to the random stage). then you get rid of the ones that must be logically eliminated by the marks you just placed (i.e. all unmarked squares around a square when the number of marked squares equals the number on that square). repeat until no squares are unmarked!
> the only time you can be sure of mined squares is when the number of unopened squares around a opened square equals the number on the opened square.
Incorrect! Observe this simple counter-example:
XXXX...
1221...We can easily deduce here that X number three is a mine, since Xs one and two, together, contain one mine, and Xs one, two and three contain two. Thus, X three contains one mine. The linear algebra solution will find these cases.
fuck! i only ran into it once i tried it on expert mode :[ i got pretty far before i had to take into account two squares at a time
The code is terrible, and I did not use f0rked's framework (found it a bit too late!), but went along the same exact lines and took it one step farther. It can actually "play", but will stop and ask whenever it can't make a deterministic move. When it stops, it even makes a suggestion (and marks it with "?") for a probabilistic (if it's a word) move. It would be easy to modify it to actually make that move too, but what's the point? We're seem to be bumping against NP-completeness of the problem very early: once the most obvious moves are done, lots of CPU cycles buy very little progress.
Oops, sorry. I meant to say that my code was terrible. And I forgot to include the link to prove it :) . Here we go: <A href="http://gerchikov.narod.ru/files/SoftwarePC/Minesweeper_Bot/bot.pl">bot.pl</A>
So what kind of algorithm do you use? Just picking the obvious choice, or anything more clever?