Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Kaboom: an unusual Minesweeper

pwmarcz.pl

Post reply on HN
Print view View original

51–60 of 71 posts

Re: Kaboom: an unusual Minesweeper

#51

Post by np_tedious »

reificator wrote: post #32
LandR wrote: post #20

How can I choose which square has the mine without guessing here? https://imgur.com/gallery/GlAgExv

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 guaran…

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?

Re: Kaboom: an unusual Minesweeper

#52

Post by reificator »

np_tedious wrote: post #51
reificator wrote: post #32

Earlier quoted context omitted.

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 guaran…

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…

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

Re: Kaboom: an unusual Minesweeper

#53

Post by TheCycoONE »

ljm wrote: post #40
vlovich123 wrote: post #34

Earlier quoted context omitted.

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.

Re: Kaboom: an unusual Minesweeper

#54

Post by bobbiechen »

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

Re: Kaboom: an unusual Minesweeper

#55

Post by amluto »

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.

Re: Kaboom: an unusual Minesweeper

#56

Post by ekimekim »

unnouinceput wrote: post #43

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 corre…

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.

Re: Kaboom: an unusual Minesweeper

#57

Post by lalaland1125 »

amluto wrote: post #55

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?

Re: Kaboom: an unusual Minesweeper

#58

Post by amluto »

lalaland1125 wrote: post #57
amluto wrote: post #55

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.

Re: Kaboom: an unusual Minesweeper

#59

Post by dmurray »

reificator wrote: post #50
dmurray wrote: post #47

Earlier quoted context omitted.

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 combi…

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

Post reply on HN