Kaboom: an unusual Minesweeper(pwmarcz.pl) |
Kaboom: an unusual Minesweeper(pwmarcz.pl) |
Implementation details: https://danq.me/2019/09/26/cheatman/
https://github.com/qntm/hatetris
On the topic of hang man, we played some on breaks at work. Eventually I figured that I could use some tool assistance that scored dictionary words according to their length, the overall frequency of the letters that appear in them, the number of times letters are repeated within the words etc. and from the top of those I manually picked the most obscure ones.
But a truly awesome project.
That is an excellent idea, I'm going to have to try this and see if I'm really as good at Minesweeper as I think or if I just get lucky sometimes on unproven squares.
Also somewhat relevant, there's a recent Minesweeper roguelike that recently came out on Steam: https://store.steampowered.com/app/1141220/DemonCrawl/
If anything, this is Minesweeper as it should have been: A game of perception and deduction with no chance of random failure.
As a huge minesweeper fan, I think this is fantastic.
I used to play a version that was guaranteed to never require guessing [1], but it was still possible to accidentally make an unnecessary guess and not be punished for it. TFA's variant is a great way to fix that problem.
[1]: https://www.chiark.greenend.org.uk/~sgtatham/puzzles/ "Mines"
Sure. But, in a complex situation, it's rather hard to know whether "you're down to guessing". It seems like there's no more information to be extracted from the board, but you may be wrong. (At least I often am.) That said, you can cheat by pressing "Give me a hint", and it'll tell you whether it's safe to guess.
Apparently I am not that great at minesweeper and guess way too often when it's not necessary. This variation kills those bad habits pretty quickly by punishing you 100% of the time for guessing. Along with undo and double checking with the debugger, I've picked up way more patterns/heuristics than in my years of playing.
Coolest thing is that if you're a perfect logician you can always win!
Link to actual game since it's not prominent in article: https://pwmarcz.pl/kaboom/
It's in a similar vein as the variant I developed, which makes you declare that you are in a situation that requires a guess. I don't use an SAT solver, and I prepopulate the board.
https://magnushoff.com/articles/minesweeper/
In comparison to the Simon Tatham version mentioned at the end of the article, my game allows all game configurations while Tatham's version guarantees solvability by restricting the possible configurations.
Under the "Complete solution: Global reasoning" section, you say that the situation requires accounting for the entire game state - but I think my solver can do it without resorting to that?
Given
. a
.2 bX
.22 as cYZ
.... defg
(X:) `abc` contains 2 mines.
(Y:) `bcdef` contains 2 mines.
(Z:) `def` contains 2 mines.
Which can be combined:
(X-a:) `abc` contains 2 mines so `bc` contains between 1 and 2.
(Y-(X-a):) `bcdef` contains 2 and `bc` contains between 1 and 2 so `def` contains between 0 and 1.
(Z-d:) `def` contains 2 so `ef` contains 1-2.
((Y-(X-a))-(Z-d):) `def` contains 0-1 and `ef` contains 1-2 so d contains 0 mines and can be cleared.
Have I missed something? Let me know if I haven't explained it properly.
Right off the bat, I cannot agree that abc must contain exactly 2 mines. From what we can see, abc contains _at most_ 2 mines. There may or may not be mines in what you have left out, and we cannot know without considering what's there.
I haven't written a formal proof for that statement, but I have been unable to solve it to my own satisfaction by reasoning about a reduced view of the board.
If it's not stalemate, haven't you won at that point? The tiles are practically in a state of quantum superposition where they are both safe and unsafe at the same time. You can't know without observing.
Except... the game rules say they're both mines if they're uncertain (in that version of the game), so the player has won because the game has been backed into a corner.
If there's a way to make that situation truly unpredictable, I'd be amazed. For example, if it was networked and another player worked a similar board, but they clicked one of the same tiles. So your clicking of a tile is the observation of what happened in someone else's game as opposed to a random calculation or game logic.
> So I'll modify the idea a bit and say you are allowed to guess, but only if there are no safe squares left. This way, the game will be cruel, but fair.
For me that statement means player 2 played by computer. What he actually implemented is not that. Which gave me the idea to actually do that. Same rules as classic one, you click, another human click (or computer player) - loser is the one who reveals a bomb. In case nobody blows up winner is the one who is last to flag correctly a bomb on a guessing situation.
Ideas, constructive criticism is welcome. What you guys say?
When it was your turn, you'd reveal a tile. If it's a mine, you get a point and your turn continues. If it isn't, your turn is over and now your opponent has more information because of the square you revealed.
A great game that rewards following all the logic you have on the currently revealed board without the benefit of gaining more information as you go, as well as playing the odds when guessing. However, it had a tendancy to give a player an easy win if the other player happens to reveal a large blank area all at once.
Such a shame, it was a good "hey someone's online, let's play a game" paradigm, words(etc) with friends have a problem of waiting around for a long time and things fizzle out.
I guess we'll never really get back a "hey I'm online atm" immediacy situation
The golden rule of this variant is: If a tile could contain a mine, it does.
Except: If there are no more tiles that can be guaranteed to be safe given the information on the board, you have to guess.
When you're forced into guessing, the rule is inverted: If the tile could be safe, then it will be safe. Again, this only applies if there are NO other guaranteed safe tiles on the board.
So click whichever you prefer.
In this configuration, if you click "Hint" it will say there are no safe squares. If you click "Debug" you'll see they are both question marks. Therefore, whichever you click on will be safe (with a count of either 1 or 4) and the other is forced into being a mine.
The interesting question (if this were earlier in the game): when in this situation and you get to impose your will on which one is safe, what's the "best" one to pick?
If you are craving a quick game, there is a Chrome Labs PWA implementation called Proxx that works on all devices
Edit: Ah, this doesn't work, because of "You are still expected to select one of the adjacent cells." Clever.
In general, the Kaboom game logic seems to be nearly identical to writing an optimal minesweeper solver.
I think it’s a shame that there is a general lack of high-quality open source IP/MIP solvers. Formulating Minesweeper as an integer program is trivial. SMT solvers might work well, too.
There’s another twist. The right thing to do here is probably to divide the board into connected components (where two squares have an edge if they have a common neighbor), then solve each component with no constraints on the number of mines, and then to match up the solutions. This would improve the game, since the concept of “a guess is needed” could take into account that revealing more numbers might not help solve a given component.
The situation when your only move possible is a guess is exactly the same we have in the very beginning of the game so I would rather make such fields guaranteed safe the way the first click is.
On the flip side, the game punishes you for guessing by guaranteeing ambiguous squares result in a mine iff there there are moves you could make without guessing.
I wonder if solving the LP-relaxation might lead to a rounding based approach.
Having the face change if there are safe cells available would give the face a purpose.
I've been struggling with that question on `Ultra Violence` difficulty, where 4-6 are the norm and 1-3 are a breath of fresh air.
I've been preferring whichever will give me an open route to an unexplored area. I'll pack mines along the edges or against other mines if possible, as long as I have some path to new territory.
This is such a cool version of this game!
a b c d
2 3 4 2
0 e f g
That means only one of c,f is a mine - the third mine of the 3.
That means only three of b,d,e,g are mines - the remaining three mines of the 4.
But both d and g cannot be mines, because combined with the one mine in c,f that would put three mines around the right 2. So only one of d,g is a mine.
So if only one of c,f is a mine, and only one of d,g is a mine, that means b,e are both mines - the remaining two mines of the 4. So b,e can be flagged as mines.
That means the left 2 is complete, so a can be opened safely. Also the mine at e completes the bottom-most 1, and you can proceed from there.
Once there are no more guaranteed squares anywhere on the board, then you can guess. And if you guess somewhere that could be valid, it will be valid. But only if there are no other guaranteed spaces left.
Same here. To add a pinch to this, say there are two regions of the visible board that must be answered by guessing. If one has 1-in-3 odds of failure, and the other has 2-in-3 odds of failure, then make the guess on the one with better chances.
.--- a---
.2-- bX--
.22- as cYZ-
.... defg
. means unknown
- means clear (and in a real game would reveal a number and therefore a constraint, but we don't need to consider those numbers for this solution)
a number means clear and producing a constraint that we want to use
This mirrors the game state in the article, and would allow us to assert that abc contains exactly 2 mines, while still only having to consider a 4x4 section of the board.
Thanks for helping me with this btw, it's much appreciated :)
This is in contrast to the local rules I first describe that consider only a very limited part of the board, and there is a pre-determined hard limit for how much would ever need to be considered for these rules.
That would at least make this game more strict and perhaps even more difficult.
While trying this out I've encountered several sections where I would have to guess, and that guess cannot be influenced by other unrevealed cells, such as when there's an island in a corner of the map.
In these situations I will need to guess between these two spaces, but since there are still known safe areas on the map, guessing causes me to lose the game.
I can get used to that behavior of course, but it's fairly frustrating. It'd be nice if the guessing exception rules accounted for situations like this. When there are clearings or known mine patterns that separate out discrete smaller map(s), I want to solve the smaller map(s) before I move on.
I'm not sure how hard this is to add to the SAT solver. The formal definition is something like "if for some set of maybe-squares S, no matter what the solutions are to all of the squares outside S, the set of solutions to S is the same, then allow clicking anywhere in S". But that's a combinatorial explosion: just the number of sets S to consider is a factor of 2^#{maybe-squares} . I don't know enough to say if that can be optimized into something sane so that it can be rigorously applied, but a handful of special cases for small unconnected sections of the board would cover most of it.
If you have all of the possible information for that guess already, then yeah.
If there are still some unknowns that you could resolve first to get more information, then guessing should still result in a mine.
I can't think of any situations where it makes a difference, though, other than ones where you rely on the mines-remaining counter.