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