Kaboom: an unusual Minesweeper | Hacker News Reader

Kaboom: an unusual Minesweeper

pwmarcz.pl

292 pointsowaty68 comments

In a similar vein: Cheating Hangman, once described as "an app that perfectly recreates the infuriating feeling of playing hangman with your older sibling who was definitely cheating and also knew way more words than you". https://cheatman.danq.me/

Implementation details: https://danq.me/2019/09/26/cheatman/

I love it, 9/10, my only complaint is the dictionary is ever so slightly too broad, I wish there was a filter to at least limit it to, say, OED words only.

But a truly awesome project.

Hatetris (or whichever implementation of that idea came first) appears on this trail:

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.

As far as I can tell bastet[1] goes back to 2004.

[1] http://fph.altervista.org/prog/bastet.html

Thanks for the shout-out! Even though I know it cheats (and how) I still play against Cheatman sometimes; the challenge is to make guesses that force the computer to bisect its search space into two approximately-even subdictionaries rather than - as it would prefer - splitting the search space into a smaller (rejected) one and a larger (adopted) one. It means thinking-ahead by about as many steps as there are undiscovered letters in the word, but it's just-about doable!

This seems like a MUCH easier version of Minesweeper, purely due to the fact that when you're down to guessing it's guaranteed to be safe.

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/

I wouldn't say it's "easier", since random chance of failure isn't a difficulty level, it's a lack of difficulty: Your gameplay has no effect on the outcome.

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.

It's "easier" in the sense that with normal Minesweeper you'd win less than 50% of the time, but with this you win 100% of the time. I agree, with normal Minesweeper I'd play "provably correctly" but then lose when I had to guess, with this I don't have to.

In complex situations it is easy to come to the conclusion that you have to guess, but sometimes there is an elaborate connection you might have missed. This game is sure to call you out on any mistakes you make of this kind.

That would at least make this game more strict and perhaps even more difficult.

I tend to solve Minesweeper locally as much as possible, solving cordoned off sections where the answer doesn't rely on the rest of the board. A major benefit to doing it this way in traditional implementations is that if I'm forced to guess, the sooner I make an incorrect guess the sooner I move on to a solvable map.

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.

Agreed, I'd like this to go one step further and allow you to guess on a square where you will inevitably have to guess anyway.

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.

> I'd like this to go one step further and allow you to guess on a square where you will inevitably have to guess anyway.

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.

Yeah, that's what I meant really, as per my attempt to formalize it.

I can't think of any situations where it makes a difference, though, other than ones where you rely on the mines-remaining counter.

I think we're in the same boat. Even though it's billed as more punishing, it's actually just significantly more fair.

Yes. I've always bemoaned the fact that people's first experience with the game is the one bundled in Windows. Because the player knows the game sometimes requires guessing, they never learn which situations actually require guessing and which are actually solvable; they just decide they need to guess because there is no number surrounded by the same number of empty squares, and never discover the math about possibilities that the game requires.

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"

I learned on Windows and 1. Never guessed if avoidable, 2. If guessing always considered both odds and potential reward for each option, at least heuristically. I feel in this context for saying "never" you deserve to click a mine ;-)

> 2. If guessing always considered both odds and potential reward for each option, at least heuristically.

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.

I would kinda like to see this approach (Kaboom) combined with Simon Tatham's version. Basically, add the guarantee that you can solve each one without guessing. Or, add instant death when you open a square that wasn't guaranteed safe to Simon Tatham's version. I think I would like that significantly better: I like the guarantee that each one can be solved, but I want to be punished when I incorrectly open a square that wasn't safe.

I'm not entirely sure the software's working correctly. I lost my first game, and I'm fairly certain that there was a different possible orientation of mines: https://imgur.com/gallery/hg1Mcwq

There were other possibilities, but you were punished for taking a guess when there were guaranteed-safe squares. Guessing is only supposed to be safe when you have to do it.

I'll label your sequence of 2, 3, 4, 2, 2 as 2a, 3b, 4c, 2d, and 2e, respectively. Although the exact configuration around 4c was not decided, 4c necessarily provided all of the mines for 2d, leaving 2e open along with the squares above and below 2e. Therefore, the game expected you to choose 2e, the squares above and below 2e, and the square above 2a, before you were allowed to take a guess.

This is such a cool version of this game!

In your screenshot, look at the green squares. Those are the spaces that are guaranteed to be safe based on the available information. The game wants you to click those before you do anything else.

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.

hatwash answered why the two green squares above and below the right-most 2 were safe. Here's why the top-left and bottom-left squares were safe:

    a b c d
    2 3 4 2
    0 e f g

Because of the left-most 2, only two of a,b,e are mines.

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.

> when you're down to guessing it's guaranteed to be safe

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.

It's amazing how good this is for training!

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/

Great read!

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.

I'm currently writing a minesweeper solver in my spare time and have a question about one section of your article.

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

Then we have the constraints:

(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.

It's been some years, but I think it boils down to the definition of when you are _considering_ some part of the game state.

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.

Sorry, I left out some bits of the game state for conciseness - perhaps this is a better way of displaying it

    .---       a---
    .2--       bX--
    .22-  as   cYZ-
    ....       defg

Where:

. 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 :)

Right, so, in my book, reasoning based on facts such as "these squares are clear" are _considering_ those squares.

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.

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.

Read further down.

> 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.

That's not quite the same though. The computer's rolling a dice on that one. My thinking was that the final state comes from a random player at the other side of the world.

The computer doesn't roll a dice, it makes whichever option you select the safe one - taking all the chance out of the game.

Quote: "Recently, I had an idea: what if you had to play Minesweeper against the computer?"

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?

Perhaps rather than awarding a "draw" to the last click, go by points for area marked safe? I think that would be slightly less weighted towards random chance rather than strategy (though I welcome correction from anyone with time+inclination to run the maths or Sims!).

There was a game a long time ago called "Minesweeper Flags" that was a 2-person minesweeper, except it worked in reverse.

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.

I definitely played this variant on MSN messenger. IIRC that service only ever managed to get 4 different games.

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

As far as I understand this has been done more than 15 years ago by the "Mines Perfect" game [0], which is open source IIRC. In this case you'd use the Lucky Mode and the Murphy's Law option (although more modes are available). And no SAT solver was used in that game, I think, which to me is more impressive, although perhaps less elegant.

[0] http://www.czeppi.de/english/index.html

How can I choose which square has the mine without guessing here?

https://imgur.com/gallery/GlAgExv

I believe from the description of the game whichever one you choose at that point will be safe

According to the rules of the game, both positions are safe.

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.

This is a good explanation. It took using the "cheat buttons" for me to fully internalize the logic.

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?

> 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?

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 reminds me a bit of the discussions around designing Quantum Minesweeper. Where you are playing N classical games in superposition. And the player is allowed to make "classical" or "entangled" choices. The ability to probe non-locally opens up interesting possibilities. See Qiskit for demo ;)

If you are craving a quick game, there is a Chrome Labs PWA implementation called Proxx that works on all devices

https://proxx.app/

Given that guessing is always safe when it's required, it means you have a choice in e.g. the initial play. Is it more efficient to click tiles on a line, or to click them in a cluster?

No math proof, but I'd favor a cluster strategy as being faster to force a (partial) solution to existing clues.

I'd assume that you'd be able to open the most squares by opening those that are completely disconnected from all other squares. That is, make a checkered pattern where there is at least one border of unopened squares around every opened one. (Except for 3's on the corners, 5's on the edges, and 8's anywhere in between, of course.)

Edit: Ah, this doesn't work, because of "You are still expected to select one of the adjacent cells." Clever.

Lines get you a lot more tiles on average it seems, but are extremely tricky to start playing. A cluster is more likely to force you to start thinking in 2 or 3 clicks, but is dramatically easier to start clearing a workable area, since the sides are not as entangled as they are in a line.

I've found it easier to hug the corners when possible, since it reduces the surface area in which you have to look for overlaps that might generate safe squares. In general, the game is easier when there are fewer places in the border.

Why a SAT solver? Constraint propagation with backtracking and arc consistency checks is very fast for minesweeper (source: this was an old Stanford CS homework problem), and it’s fairly straightforward to re-solve with added constraints to ask questions like “could there be a mine here”.

In general, the Kaboom game logic seems to be nearly identical to writing an optimal minesweeper solver.

Why implement backtracking when a SAT solver implements it for you?

You can turn this around; why implement complicated cardinality constraints to reduce a problem to SAT when a different solver can handle them directly.

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.

While playing this, I had an idea. What if marking the mine reduced the number of any number tiles adjacent to the mine? So the number tile would show the number of adjacent mines, minus the number of adjacent flags. Then you could work through the puzzle by bringing all the number tiles to 0, which might make certain situations more readily soluble.

> One of the bottom squares contain a mine, but it's impossible to say which one. You have to select one of them. But according to what I just said, that would mean certain death! I wanted the game to be cruel, but now it's unwinnable. 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.

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.

If you read through the rest of the article, that's actually the end result! Ambiguous squares are guaranteed not to be mines iff guessing is the only possible move.

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.

Super cool! I was playing with a friend and found the interesting strategy of minimizing the information available to us and trying to force as many guesses as possible. Start from the corners, and whenever you have to guess, guess in a way that limits you (for example, guessing to cover all your edges with known mines). Then, since you don't have any options, you get a "free" space to continue! And with the free space, you pick a different corner...

Man, I need to reserve a weekend to play with a SAT solver.

Beautiful solution with the binomial encoding. Apparently, "at most k" is a well known problem http://www.sat4j.org/maven233/apidocs/org/sat4j/tools/encodi...

I have been playing this obsessively the last few weeks without knowing about the implementation. I thought it expresses the known facts about the board configuration as a system of linear equations and uses one of the classic algorithms for solving these. Anyone know if that would be infeasible for some reason?

The variables would need to be constrained to be integers/booleans. And Integer Linear Programming is NP-complete.

I was thinking along the same lines when the systems of linear equations came up. The difficulty is that the variables are 0-1 while the equations are over the integers. So this is not quite as simple as solving a system over F_2, but is instead feasibility testing of an IP with 0-1 variables and a 0-1 matrix.

I wonder if solving the LP-relaxation might lead to a rounding based approach.

The ability to choose where mines aren't can yield some funny results. My goal is now to force as many mines as possible in the upper left corner. https://imgur.com/a/X1zxwdO

At first I thought it’s a variation of the old Atari game of the same name [1]

[1] https://en.wikipedia.org/wiki/Kaboom!_(video_game)

The original minesweeper had a smiley face up the top, which would turn dead if you lost, and would have a :o face while picking a cell.

Having the face change if there are safe cells available would give the face a purpose.

I love the doom style level names. Great game. Lots of fun! Awesome work.

See also the author's blog post about how he built it: https://pwmarcz.pl/blog/kaboom/

We've changed to that one from https://pwmarcz.pl/kaboom/ because it's a bit more informative and maybe more interesting to read first. Thanks!

Reply on news.ycombinator.com