I'm bringing back Minesweeper

[Barbarian]

There's no good reason for any of you to remember that I have asked a question about factorization of polynomials back on the old forum, and that IIRC I did issue the warning back then that I needed it because I was working on some game. Well, I have finished it and, it being a mathematical game, I thought I could post about it in the Natural Science forum.

The game is a modified Minesweeper, which works exactly like the old game(*) until you find yourself forced to guess which square to click next. At that point the program will analyse the situation and decide whether you really had to guess; if so, your guess will turn out to have been lucky, otherwise it will be unlucky. I have put up a blog post about it but probably just linking the program (it's a jar archive and should not access either network or filesystem on your computer) and the documentation will be enough here. The documentation is somewhat heavy, or so I am being told, but for aficionados it's probably a good read; QM makes a cameo appearance, as does P=NP.

So, have fun, tell me what you think about it, or just enjoy playing.

Also: the factorization stuff never made it into the game. Turned out it wasn't actually needed.

---
*) Nope, it's much uglier but also much more comfortable to play, because of, you know, innovation. Read the 'If you only want to play' part of the documentation for more details, but basically:

• single left click on empty field acts like combined left-and-right click in the Windows version, "sweeping around" the field
• 'AutoMark' switched on will automatically mark mines if you uncovered all non-mines around an empty field
• 'Force 0' can tweak chance and, if at all possible, give you an empty field with zero mines around it (initiating a sudden expansion of the open area) if you had to guess.

OTOH the way the numbers are drawn is ugly. I'm no GUI designer.

 

[Loren Pechtel]

How does it decide if you really had to guess? In years past I've found multiple scenarios where looking at things locally leaves multiple solutions but looking at them globally proves which solution is right. (This happens when the different choices involve a different number of mines.)

 

[Barbarian]

How does it decide if you really had to guess? In years past I've found multiple scenarios where looking at things locally leaves multiple solutions but looking at them globally proves which solution is right. (This happens when the different choices involve a different number of mines.)

The program sees if there are still covered squares which can be proven to be empty but whose valence - the number of mines around them - cannot be inferred from available information. I call these squares keyholes. The game only progresses when you open a keyhole and find out its actual valence. The bottom rule is that you are forced to guess, i.e. click a square that may or may not be a mine if there aren't any keyholes on the board, plus there's an exception: if an island of covered fields is independent from the rest of the board in the sense of having to host a single exact number of mines, and that island does not touch any keyholes, then guessing in that island is immediately allowed regardless of keyholes elsewhere.

I have considered other principles but ran into two limits. First, some of them simply do not lend themselves to solving via fast algorithms. For instance, one could say that if the just-clicked square will stay ambiguous, either empty or a mine, for all possible guessing-free paths of play from the current situation, then the clicking was a legal guess. I could not come up with a solution that would decide this in significantly less time than it takes to try out all the paths. Then I tried to add exceptions to the principle that no keyholes equals must guess, but there I ran into a different kind of limitation: the exceptions are too complicated to define, and at some point they become pointless because they allow situations that I really doubt humans can foresee and make use of.

 

[beero1000]

Dunno if you've looked at it, but you can formulate minesweeper as an integer linear program (binary even, each square has a binary mine/no mine variable, and the constraints are given by the exposed valences). Then, the question of having to guess for a square is the same as checking if the program is still feasible for both possible choices of variable value. There are any number of reasonably fast (though not polynomial in the worst case) algorithms to solve for feasibility. One nice one to look at are the cutting plane methods because they can at least partially be done online - you do not need to continuously resolve the same problem as you go. I don't have an estimate on running time, but you'll have hundreds to thousands of variables - which is no good for efficiency, but the constraints will be fairly simple and each only involve a handful of variables, so it might be possible to get that to run quickly enough.

 

[Loren Pechtel]

How does it decide if you really had to guess? In years past I've found multiple scenarios where looking at things locally leaves multiple solutions but looking at them globally proves which solution is right. (This happens when the different choices involve a different number of mines.)

The program sees if there are still covered squares which can be proven to be empty but whose valence - the number of mines around them - cannot be inferred from available information. I call these squares keyholes. The game only progresses when you open a keyhole and find out its actual valence. The bottom rule is that you are forced to guess, i.e. click a square that may or may not be a mine if there aren't any keyholes on the board, plus there's an exception: if an island of covered fields is independent from the rest of the board in the sense of having to host a single exact number of mines, and that island does not touch any keyholes, then guessing in that island is immediately allowed regardless of keyholes elsewhere.

But that still comes down to what you can infer from available information.

 

[Barbarian]

But that still comes down to what you can infer from available information.

Yes. Wouldn't it worry you if it was otherwise?

But seriously, I think I am misunderstanding you. Let me attempt to reply to what I think you are saying. The program does not decide upon a mine configuration up front; it works on a representation of all configurations compatible with the currently available information. I'd say no more information is even possible, because there's no hidden state of the board. In a sense all possible information equals all available information for this particular system. Or am I not addressing your issue?

 

[Barbarian]

Dunno if you've looked at it, but you can formulate minesweeper as an integer linear program (binary even, each square has a binary mine/no mine variable, and the constraints are given by the exposed valences). Then, the question of having to guess for a square is the same as checking if the program is still feasible for both possible choices of variable value. There are any number of reasonably fast (though not polynomial in the worst case) algorithms to solve for feasibility. One nice one to look at are the cutting plane methods because they can at least partially be done online - you do not need to continuously resolve the same problem as you go. I don't have an estimate on running time, but you'll have hundreds to thousands of variables - which is no good for efficiency, but the constraints will be fairly simple and each only involve a handful of variables, so it might be possible to get that to run quickly enough.

I haven't tried this tack mainly because in a sense I had the method first and found Minesweeper as an application area merely hours later, so there never was a time when I was thinking about what method to use to destroy Minesweeper for those who love it. My algorithm is exponentially complex (in terms of the number of squares) in the worst case but I strongly suspect it's kinda polynomial on average, just like the simplex method for linear programming IIRC. For quite a while I thought I had a P algorithm for an NP-complete problem there, and since there are possible improvements to the algorithm with as of yet unknown cost but bringing down the worst case of the rest of the algorithm to P, I'm not yet entirely done with P vs. NP vs. Minesweeper. I have it all documented and there's a link to the doc in the OP, if you feel masochistic enough for it.

 

[Loren Pechtel]

But that still comes down to what you can infer from available information.

Yes. Wouldn't it worry you if it was otherwise?

But seriously, I think I am misunderstanding you. Let me attempt to reply to what I think you are saying. The program does not decide upon a mine configuration up front; it works on a representation of all configurations compatible with the currently available information. I'd say no more information is even possible, because there's no hidden state of the board. In a sense all possible information equals all available information for this particular system. Or am I not addressing your issue?

It's just that I have sometimes been able to figure out where mines must be on the layer beyond the layer of contact, sometimes even behind an already-identified layer of mines.

 

[doubtingt]

Minesweeper: The Movie


This one is a joke, but sadly no more absurd that the real Tetris movie currently in production.

 

[beero1000]

Dunno if you've looked at it, but you can formulate minesweeper as an integer linear program (binary even, each square has a binary mine/no mine variable, and the constraints are given by the exposed valences). Then, the question of having to guess for a square is the same as checking if the program is still feasible for both possible choices of variable value. There are any number of reasonably fast (though not polynomial in the worst case) algorithms to solve for feasibility. One nice one to look at are the cutting plane methods because they can at least partially be done online - you do not need to continuously resolve the same problem as you go. I don't have an estimate on running time, but you'll have hundreds to thousands of variables - which is no good for efficiency, but the constraints will be fairly simple and each only involve a handful of variables, so it might be possible to get that to run quickly enough.

I haven't tried this tack mainly because in a sense I had the method first and found Minesweeper as an application area merely hours later, so there never was a time when I was thinking about what method to use to destroy Minesweeper for those who love it. My algorithm is exponentially complex (in terms of the number of squares) in the worst case but I strongly suspect it's kinda polynomial on average, just like the simplex method for linear programming IIRC. For quite a while I thought I had a P algorithm for an NP-complete problem there, and since there are possible improvements to the algorithm with as of yet unknown cost but bringing down the worst case of the rest of the algorithm to P, I'm not yet entirely done with P vs. NP vs. Minesweeper. I have it all documented and there's a link to the doc in the OP, if you feel masochistic enough for it.

Cool. I like the free algebra approach, and unless P = NP, an exponential algorithm is pretty much the best you can get. On the other hand, pre-built ILP solvers are super efficient, and working with a mine assignment means you don't need to keep track of all possible configurations. Just a thought, although the fixed-size minesweeper boards mean asymptotic efficiency isn't the end-all of algorithm design.

 

[beero1000]

Yes. Wouldn't it worry you if it was otherwise?

But seriously, I think I am misunderstanding you. Let me attempt to reply to what I think you are saying. The program does not decide upon a mine configuration up front; it works on a representation of all configurations compatible with the currently available information. I'd say no more information is even possible, because there's no hidden state of the board. In a sense all possible information equals all available information for this particular system. Or am I not addressing your issue?

It's just that I have sometimes been able to figure out where mines must be on the layer beyond the layer of contact, sometimes even behind an already-identified layer of mines.

You seem to be missing the global nature of the analysis. This looks at the feasibility of all possible mine configurations, not just the first basic inferences.

 

[Loren Pechtel]

It's just that I have sometimes been able to figure out where mines must be on the layer beyond the layer of contact, sometimes even behind an already-identified layer of mines.

You seem to be missing the global nature of the analysis. This looks at the feasibility of all possible mine configurations, not just the first basic inferences.

And runs in a sane timeframe??

 

[beero1000]

You seem to be missing the global nature of the analysis. This looks at the feasibility of all possible mine configurations, not just the first basic inferences.

And runs in a sane timeframe??

Define "sane".

Minesweeper is known to be NP-complete, so for all intents and purposes, an exponential-time algorithm is best possible (or at least, super-polynomial). However, this is only asymptotic worst-case analysis and isn't completely relevant to the fixed board sizes of regular play (any constant base to a constant power is still just constant). I don't see why his algorithm couldn't run fast enough for regular minesweeper play and given that he linked to an implementation, it probably does (I haven't tried it though).

 

[Barbarian]

You seem to be missing the global nature of the analysis. This looks at the feasibility of all possible mine configurations, not just the first basic inferences.

And runs in a sane timeframe??

Yep. It's as fast as the classic Minesweeper. There's a neat mapping between views - full available information about a game in progress - and a certain algebraic structure, and I manipulate the latter.

ETA: try the program. It's harmless. Requires Java 8 as far as I can tell - I don't have access to a variety of environments to test - but other than that it shouldn't need anything else. It does not try to save high scores - it has no high score feature at all, for I am against it - and does not save preferences. Does not access the network. Does not phone home.

 

[Barbarian]

Cool. I like the free algebra approach, and unless P = NP, an exponential algorithm is pretty much the best you can get. On the other hand, pre-built ILP solvers are super efficient, and working with a mine assignment means you don't need to keep track of all possible configurations. Just a thought, although the fixed-size minesweeper boards mean asymptotic efficiency isn't the end-all of algorithm design.

The situation is rather tense. On one hand if I had to bet, I'd bet on P != NP and all attempts to prove otherwise would then qualify merely as ways to waste one's time. On the other hand I cannot shake off the feeling that I should push a bit further with factorization because if this sort of very specific factorization task can be done in polynomial time - and my gut feel is that it can - then the entire algorithm would almost surely become polynomial and we'd have P=NP. Essentially it's gut feel vs. gut feel, and both of them are mine.

 

[beero1000]

Cool. I like the free algebra approach, and unless P = NP, an exponential algorithm is pretty much the best you can get. On the other hand, pre-built ILP solvers are super efficient, and working with a mine assignment means you don't need to keep track of all possible configurations. Just a thought, although the fixed-size minesweeper boards mean asymptotic efficiency isn't the end-all of algorithm design.

The situation is rather tense. On one hand if I had to bet, I'd bet on P != NP and all attempts to prove otherwise would then qualify merely as ways to waste one's time. On the other hand I cannot shake off the feeling that I should push a bit further with factorization because if this sort of very specific factorization task can be done in polynomial time - and my gut feel is that it can - then the entire algorithm would almost surely become polynomial and we'd have P=NP. Essentially it's gut feel vs. gut feel, and both of them are mine.

That would be a big deal. On the other hand there are numerous proofs about techniques which cannot be used to resolve P vs NP. Many of them are algebraic in nature, and might apply in some non-trivial way to this problem. I suspect that a little further in you'll come across a nearly insurmountable obstacle...

 

[Barbarian]

That would be a big deal. On the other hand there are numerous proofs about techniques which cannot be used to resolve P vs NP. Many of them are algebraic in nature, and might apply in some non-trivial way to this problem. I suspect that a little further in you'll come across a nearly insurmountable obstacle...

That's what usually happens with my pet projects. Nonetheless, I learn a lot in the meantime.

 

[beero1000]

That would be a big deal. On the other hand there are numerous proofs about techniques which cannot be used to resolve P vs NP. Many of them are algebraic in nature, and might apply in some non-trivial way to this problem. I suspect that a little further in you'll come across a nearly insurmountable obstacle...

That's what usually happens with my pet projects. Nonetheless, I learn a lot in the meantime.

Ain't that the truth.

 

[Barbarian]

I'm going to release a new version of the documentation soon, because I think have solved factorization, although it does not help with P vs NP. Bottom line: factors can have non-polynomial lengths, so factorization itself cannot bring the entire algorithm back to polynomial complexity and the particular factorization algorithm I've found is itself non-polynomial as a result of this. Actually the algorithm is kinda hinted at in the current documentation, but a bit of reasoning was missing.

I don't think I'll incorporate this method into the game. It would help curb unchecked growth of expressions but there's no evidence that this is a problem now, and implementing the algorithm would entail a somewhat ugly breach of modularity, not to mention lots of new code. I'm already working on another pet project, so I'll update the doc and let this one sleep.

 

[Loren Pechtel]

I'm going to release a new version of the documentation soon, because I think have solved factorization, although it does not help with P vs NP. Bottom line: factors can have non-polynomial lengths, so factorization itself cannot bring the entire algorithm back to polynomial complexity and the particular factorization algorithm I've found is itself non-polynomial as a result of this. Actually the algorithm is kinda hinted at in the current documentation, but a bit of reasoning was missing.

I don't think I'll incorporate this method into the game. It would help curb unchecked growth of expressions but there's no evidence that this is a problem now, and implementing the algorithm would entail a somewhat ugly breach of modularity, not to mention lots of new code. I'm already working on another pet project, so I'll update the doc and let this one sleep.

Yeah--a simple algorithm will only err on the side of declaring something a guess when there might have been a way to figure out what was in a cell. That's not a serious problem.