I hacked up a version of minesweeper that was “forgiving:” if there was no selection that was provably safe, it gave you a safe move. If you picked any square that was not provably a bomb, it would not be a bomb.
Typically, as long as you don’t select a number of bombs equal to the number of squares , your first move is safe. I just extended that for the whole game.
If you select N-1 bombs, you always win on the first move..
That's pretty neat. I wonder how it works. It's not obvious to me at all how to build something like this, as the program doesn't know the sequence in which the player will reveal the tiles.
I also once made my own variant of this (just like
gregfjohnson's idea): A "lucky minesweeper" where luck can be toggled on/off at any point during the game: https://github.com/yshklarov/minesweeper
There is a Korean indie game made in RPG Maker MV that pushes this idea to the extreme, titled How can I be a brave in the isekai while I suck even at the minesweeper's novice level?! (rough translation, original: 지뢰찾기 초급을 겨우 깰까말까한 내가 이세계에서는 용사라고?). Too bad it's only available in Korean.
I think this diminishes the game. Sometimes you just don't have enough information to know for sure. Experiencing this in a low stakes situation like a minesweeper game reminds us that life is like that sometimes and we just have to make a guess and accept the consequences.
Yes, this really depends on what one's expectations are of a "game". Luck, as a component, is often contested. In case of the minesweeper, I'd argue there is either
A) No place for luck at all, either by making the game "forgiving", or generating a game that never has an ambiguous block, or
B) The game should make luck's presence more constant.
In case of Minesweeper, the most unfair event is when after a lot of pure skill-based play, the outcome ends up being luck based. As a game mechanic, this can work out to be challenging, or work as a surprise the first time, but it gets old pretty fast - because why bother putting in all that skill, just so be judged by luck in the end? And those who are thrilled by luck checks, will be turned away from the game because the exciting part comes last.
Because of this, I'd keep this logic game be about logic, or work luck into the game more deeply.
Solitaire is similar, with some of its starting positions being outright unwinnable. I'd just filter these out when creating a new game.
Agree completely. The luck aspect kinda wrecked minesweeper for me. It's a super fun simple game, but after spending a lot of effort logic-ing my way through it, only to have to take a 50/50 or worse guess toward the end and have it blow me up, is deeply unsatisfying. When it comes at the beginning (that first block can be a bomb after all) it's not too bad, but at the end isn't cool
This is why Slay the Spire is as loved as it is -- clearly defined skill and luck checks delivered one after the other at the precise limits of your ability.
Minesweeper is more like a quirky old wooden board game, charming because it's always been what it is, warts and all.
I actually like the idea that it's always solvable. Like a sudoku puzzle. If a sudoku isn't solvable through logic, but requires guessing, it's considered an invalid puzzle.
Ha! This is NP-Complete, no? In practice, it probably doesn't matter but my bet is that there are some configurations that will take exponential time to see if the player should be "forgiven".
There was a Minesweeper on here that used a SAT solver, but I cannot find it at the moment. As I recall, it never had any issue with resolving the board quickly. I think it dynamically resolved where the mines would be as you played the game, and if you clicked a square that could be a mine, it would be a mine, except, I believe, when there were no open squares that were safe.
Every version of Minesweeper I've ever played makes your first move safe. I realize this is not going as far as your version, but I've had this argument with ardent players who insist it isn't true (and somehow they've just been lucky, I guess).
The article discusses Boltzmann's formula exp(-E/kT). I was recently looking at the same formula in the context of semiconductors and I realized that Boltzmann's constant k is only needed because temperature uses bad units. If we measured temperature in energy instead of degrees, then Boltzmann's constant drops out. For instance, you could express room temperature as 25 meV (milli electron volts) or 2444 joules/mole and the constant disappears. Likewise, the constant in the ideal gas law disappears if you measure temperature as energy rather than degrees Kelvin. In other words, degrees Kelvin is a made-up unit that should be abandoned. (I'm not sure I believe this, but I don't see a flaw.)
This is to an extent a party trick to befuddle lay people. Physicists know perfectly well that temperature is not a well-defined concept out of equilibrium. And when in a population inversion experiment when "temperature" is determined to be negative (or "beyond infinite" if you will) it arises because for a short while you have a non-Boltzmannian distribution.
Right, using beta is more convenient and also it's better behaved since it doesn't have the weird "goes to infinity then comes back from negative infinity as you keep increasing it" behaviour.
Oh, right, yes. But that's just because 1/T occurs in many formulas and thus it's often convenient to work with it instead. No exciting new physics hiding there. ;)
This is true of any units. A lot of physicists say things like "set c=1", does that mean that meters/feet are bad units and we should instead be measuring our height in fractions of c? That sounds inconvenient to me.
I just calculated that I’m about 6.24 nanolightseconds. A nanolightsecond is just over a foot, so at least Americans should easily get use to the unit.
Another example that shows up in mid school is how we measure angle.
Like the Greeks and Babylonians we usually measure it in degrees. Later around 18th century radians started getting used, especially in power series expansions.
In India, historically, angle was measured in the units of length (for a standardized circle). That made functions like sin be a function from length to length.
i.e. a variant of radians? A radian is the circular arc whose length is equal to the radius. If we standardise the unit circle then a radian is a length of 1.
Yes. Similar idea. Sometimes they would also use minutes. Whether this was as a result of contact with the Greeks I do not know. Indian trigonometry however has a different flavour from the trigonometry of Hipparchus.
What Indian mathematicians typically used was a circle with radius 3438 units. Where units would be one of the standard units of length.
Why 3438 you may wonder.
They also wanted to divide the circle into 360 x 60 minutes. For the standard circle they wanted each of those minute arcs to be of 1 unit length. The radius that would accomplish this is (360 x 60)/ 2pi ~= 3438 units.
An angle of 1 minute would then be described as arc length 1 unit on that standardized circle of radius 3438 units.
Indian version of sine and cosine were not expressed as ratios but the corresponding (half) chord for a hypotenuse of 3438 units.
Very neat. Alternative-length radians seem quite common. Radians are by definition one radius, but NATO mils are 0.00098 radii (and apparently the Finnish piiru are 0.00105 radii). What you describe are effectively a unit that is 0.0018 radii. Makes sense.
I do dislike the fact the libc sin takes argument in radians. For two reasons. One, the angles in the application are rarely in radians, so they need to be converted before the function call. Two, I would like the standard angles, such as the multiples of 15 degrees to have an accurate representation in 32 bits (or 64 bits).
I don't think temperature would be measured as energy, but rather as energy per information; e.g. joules per bit. Boltzmann's constant defines the degree as one joule per a very large number of bits, to get numbers convenient at macroscopic scales.
Only tangentially related, but Dragonsweeper is an interesting extension of minesweeper where you have hit points and the "mines" have attack values. I got a better appreciation for the mechanics of minesweeper by playing it; it's surprisingly deep. https://danielben.itch.io/dragonsweeper
it's a RPG variant of Minesweeper, where you have life points, level up and fight against monster (mines) that gives you xp once killed (you loose HP if you fight a monster higher lvl than you).
it's a flash game, that had an android release at some point (it was removed from the store for some reasons)
Minesweeper is a probabilistic game, that's why you should use probabilistic tools to solve it.
For example you can use a particle filter to approximate the distribution of mines. Every time you obtain new information you update the filter so that only distributions compatible with constraints remain.
Once you have an approximation to the distribution of mines you can calculate the probability of each spot being a mine. You can also calculate statistical indicator like the Information Gain of each action.
A good strategy is therefore to play low mine probability with highest information gain. But there is a trade-off, when the mine probability is non-zero. So you need to look-ahead.
Fortunately thanks to the mine distribution approximation you can also simulate any actions and their consequences, because you can use your approximation of the distribution to predict which number will be revealed upon a click.
So an even better strategy is to unroll the game tree for the best few candidate moves based on some heuristics, and calculate the cost gain probabilities after a few moves.
Most of the times Minesweeper is deterministic, and you can just think and get an empty spot. From time to time, you are unlucky and has to guess.
A few years ago, I modified the version of minesweeper in the "Games" collection of Racket to get more mines per board and get more hard cases. (I added the trick to autoopen the squares that have enough flags around, so it solved all the easy cases and it was more fun. I never upstreamed the changes...)
I like Dragonsweeper (discussed in a sibling comment) because it has a more clear probability and information tradeoff.
Interestingly, the main problem with Minesweeper is that is a game of chance (so the approach discussed in the article is very appropriate).
For a minesweeper variant purely based on logic, I highly recommend the game Tametsi. It has 160 handcrafted levels, and some have very interesting geometrical arrangements. I have logged over 100 hours in this game.
Yes, (original author here) in fact all the cells outside this region have an even better safety probability of 80.1%. I think the best move might be to start fresh in a new corner.
Hmm, but how likely are clicks on random squares to reveal more safe clicks? Seems likely that even if you hit a safe square you might still not have any safe moves. The goal ought to be to create more safe moves for the next turn, to reduce your chance of dying over the whole game, not just in the current turn. I wonder what that analysis would look like.
In the given example, if you click two squares down from the 3 in the 2-3-4 at the bottom, if you get a 3 it may reveal a 3 that will open up all the spaces around it. Which in the process may reveal what kind of 4 it is.
If you click on the square three to the right of the top 1, if that shows a 1, then a lot of surrounding squares can be revealed and again you may "walk up" to a more definitive mapping of the bombs.
I'm not even sure those are the optimal examples, but when I minesweeper it was for speed.
The real advantage, especially at this stage of the puzzle, is that those squares might quickly lead to another big field to be revealed.
At first I thought the "equal probability assumption" wasn't too bad an approximation, but it has an average Brier score of 0.217. Much worse than I thought.
The author’s math considers how mines would be distributed if mines were distributed to the empty squares after reaching that board state.
This is wrong.
This is classic Monty Hall Problem. The author is doing the equivalent of saying “there are two doors left, so the odds are 50 / 50 that the prize is behind either door.
It invalidates all of the numbers after this point.
The difference is that Monty knows which of the doors the car is behind and deliberately avoids it, thereby giving away information about where the car is.
Whereas in Minesweeper we've just blindly stumbled across a situation where we have to guess.
It would be like if every show Monty always revealed a random door. Sometimes he would reveal the car and the game would end immediately. In the cases when he didn't reveal the car it really would be 50/50 between the remaining two doors.
The bot at https://mrgris.com/projects/minesweepr/ does these calculations, and has a winrate of 37.8% on expert. I don't know what a more naive bot would achieve.
I think the human experts mostly care about speed rather than their average solve percentage. If they're forced to guess then they can just restart if they get it wrong.
I hacked up a version of minesweeper that was “forgiving:” if there was no selection that was provably safe, it gave you a safe move. If you picked any square that was not provably a bomb, it would not be a bomb. Typically, as long as you don’t select a number of bombs equal to the number of squares , your first move is safe. I just extended that for the whole game. If you select N-1 bombs, you always win on the first move..
Simon Tatham's _Mines_ deals with this in a different way: it generates the mine positions in such a way that they can never lead to an ambiguous state during a game. https://www.chiark.greenend.org.uk/~sgtatham/puzzles/doc/min...
That's pretty neat. I wonder how it works. It's not obvious to me at all how to build something like this, as the program doesn't know the sequence in which the player will reveal the tiles.
I also once made my own variant of this (just like gregfjohnson's idea): A "lucky minesweeper" where luck can be toggled on/off at any point during the game: https://github.com/yshklarov/minesweeper
He's written a bit about how it works here: https://www.chiark.greenend.org.uk/~sgtatham/quasiblog/mines....
There is a Korean indie game made in RPG Maker MV that pushes this idea to the extreme, titled How can I be a brave in the isekai while I suck even at the minesweeper's novice level?! (rough translation, original: 지뢰찾기 초급을 겨우 깰까말까한 내가 이세계에서는 용사라고?). Too bad it's only available in Korean.
> a version of minesweeper that was “forgiving:”
I think this diminishes the game. Sometimes you just don't have enough information to know for sure. Experiencing this in a low stakes situation like a minesweeper game reminds us that life is like that sometimes and we just have to make a guess and accept the consequences.
Yes, this really depends on what one's expectations are of a "game". Luck, as a component, is often contested. In case of the minesweeper, I'd argue there is either
A) No place for luck at all, either by making the game "forgiving", or generating a game that never has an ambiguous block, or
B) The game should make luck's presence more constant.
In case of Minesweeper, the most unfair event is when after a lot of pure skill-based play, the outcome ends up being luck based. As a game mechanic, this can work out to be challenging, or work as a surprise the first time, but it gets old pretty fast - because why bother putting in all that skill, just so be judged by luck in the end? And those who are thrilled by luck checks, will be turned away from the game because the exciting part comes last.
Because of this, I'd keep this logic game be about logic, or work luck into the game more deeply.
Solitaire is similar, with some of its starting positions being outright unwinnable. I'd just filter these out when creating a new game.
Agree completely. The luck aspect kinda wrecked minesweeper for me. It's a super fun simple game, but after spending a lot of effort logic-ing my way through it, only to have to take a 50/50 or worse guess toward the end and have it blow me up, is deeply unsatisfying. When it comes at the beginning (that first block can be a bomb after all) it's not too bad, but at the end isn't cool
This is why Slay the Spire is as loved as it is -- clearly defined skill and luck checks delivered one after the other at the precise limits of your ability.
Minesweeper is more like a quirky old wooden board game, charming because it's always been what it is, warts and all.
Balatro as well, I think. Luck there is a huge factor, and it's honest about it from the get-go.
I actually like the idea that it's always solvable. Like a sudoku puzzle. If a sudoku isn't solvable through logic, but requires guessing, it's considered an invalid puzzle.
Ha! This is NP-Complete, no? In practice, it probably doesn't matter but my bet is that there are some configurations that will take exponential time to see if the player should be "forgiven".
Yeah, it's NP-complete to decide whether a cell in Minesweeper must be a mine: https://logic.pku.edu.cn/ann_attachments/np.pdf.
In practice I suspect a SAT solver would make quick work of the positions that actually appear in games.
There was a Minesweeper on here that used a SAT solver, but I cannot find it at the moment. As I recall, it never had any issue with resolving the board quickly. I think it dynamically resolved where the mines would be as you played the game, and if you clicked a square that could be a mine, it would be a mine, except, I believe, when there were no open squares that were safe.
(Edit: Here it is! https://pwmarcz.pl/kaboom/ And the write-up: https://pwmarcz.pl/blog/kaboom/ )
This is similar in spirit to my take on the game: https://magnushoff.com/articles/minesweeper/
Unfortunately, not being familiar with SAT solvers, my implementation can grind to a halt in some configurations :)
I wonder if one learned to play faster with this kind of minesweeper.
I find in a lot of repetitive learning, you have a very noisy signal, you don't know if you succeeded because of luck or you did something right.
This variant takes out the luck part.
I made winsweeper, which will move the mine if there is no safe tile left for you to discover.
https://github.com/alaingilbert/winsweeper
Yeah I've debugged another game that attempted this and this system resulted in the game lagging as hard sometimes.
Every version of Minesweeper I've ever played makes your first move safe. I realize this is not going as far as your version, but I've had this argument with ardent players who insist it isn't true (and somehow they've just been lucky, I guess).
Prior art: https://news.ycombinator.com/item?id=21883875
I would also like to auto clear tiles that are unambiguous when I flag a mine. Perhaps by double tapping one of the adjacent tiles
Can't you right-then-left-click the flagged mine? Iirc there's an awkward way of doing this
The Windows 7 Minesweeper does something like this on the initial click, I think. You usually get a "good start".
The article discusses Boltzmann's formula exp(-E/kT). I was recently looking at the same formula in the context of semiconductors and I realized that Boltzmann's constant k is only needed because temperature uses bad units. If we measured temperature in energy instead of degrees, then Boltzmann's constant drops out. For instance, you could express room temperature as 25 meV (milli electron volts) or 2444 joules/mole and the constant disappears. Likewise, the constant in the ideal gas law disappears if you measure temperature as energy rather than degrees Kelvin. In other words, degrees Kelvin is a made-up unit that should be abandoned. (I'm not sure I believe this, but I don't see a flaw.)
Yes! Units are up to you (with some constraints)! Physicists do this in practice a lot: https://en.wikipedia.org/wiki/Natural_units
Physicists also sometimes deal with inverse temperature aka "coldness".
This is to an extent a party trick to befuddle lay people. Physicists know perfectly well that temperature is not a well-defined concept out of equilibrium. And when in a population inversion experiment when "temperature" is determined to be negative (or "beyond infinite" if you will) it arises because for a short while you have a non-Boltzmannian distribution.
I don't think they were talking about negative temperature, they just mean that sometimes the convenient quantity to work with is β = 1/T.
Right, using beta is more convenient and also it's better behaved since it doesn't have the weird "goes to infinity then comes back from negative infinity as you keep increasing it" behaviour.
Oh, right, yes. But that's just because 1/T occurs in many formulas and thus it's often convenient to work with it instead. No exciting new physics hiding there. ;)
See: Temperature as Joules per Bit https://arxiv.org/abs/2401.12119
Landauer's cost is one of those things that frighten me because it makes clear how little I understand about how the world works.
This is true of any units. A lot of physicists say things like "set c=1", does that mean that meters/feet are bad units and we should instead be measuring our height in fractions of c? That sounds inconvenient to me.
I just calculated that I’m about 6.24 nanolightseconds. A nanolightsecond is just over a foot, so at least Americans should easily get use to the unit.
Ah, but most natural unit systems don't measure time in seconds either. See https://en.wikipedia.org/wiki/Natural_units
Another example that shows up in mid school is how we measure angle.
Like the Greeks and Babylonians we usually measure it in degrees. Later around 18th century radians started getting used, especially in power series expansions.
In India, historically, angle was measured in the units of length (for a standardized circle). That made functions like sin be a function from length to length.
> angle was measured in the units of length
i.e. a variant of radians? A radian is the circular arc whose length is equal to the radius. If we standardise the unit circle then a radian is a length of 1.
Yes. Similar idea. Sometimes they would also use minutes. Whether this was as a result of contact with the Greeks I do not know. Indian trigonometry however has a different flavour from the trigonometry of Hipparchus.
What Indian mathematicians typically used was a circle with radius 3438 units. Where units would be one of the standard units of length.
Why 3438 you may wonder.
They also wanted to divide the circle into 360 x 60 minutes. For the standard circle they wanted each of those minute arcs to be of 1 unit length. The radius that would accomplish this is (360 x 60)/ 2pi ~= 3438 units.
An angle of 1 minute would then be described as arc length 1 unit on that standardized circle of radius 3438 units.
Indian version of sine and cosine were not expressed as ratios but the corresponding (half) chord for a hypotenuse of 3438 units.
Very neat. Alternative-length radians seem quite common. Radians are by definition one radius, but NATO mils are 0.00098 radii (and apparently the Finnish piiru are 0.00105 radii). What you describe are effectively a unit that is 0.0018 radii. Makes sense.
I see. Today I learned about piiru from you.
I do dislike the fact the libc sin takes argument in radians. For two reasons. One, the angles in the application are rarely in radians, so they need to be converted before the function call. Two, I would like the standard angles, such as the multiples of 15 degrees to have an accurate representation in 32 bits (or 64 bits).
Anyhow this is way off topic.
I don't think temperature would be measured as energy, but rather as energy per information; e.g. joules per bit. Boltzmann's constant defines the degree as one joule per a very large number of bits, to get numbers convenient at macroscopic scales.
The argument of the exponential E/kT needs to be dimensionless. If E and T are not homogeneous you will still need a k to “cancel” the units.
Only tangentially related, but Dragonsweeper is an interesting extension of minesweeper where you have hit points and the "mines" have attack values. I got a better appreciation for the mechanics of minesweeper by playing it; it's surprisingly deep. https://danielben.itch.io/dragonsweeper
Similar game: Mamono Sweeper https://duckduckgo.com/?q=mamono+sweeper (mamono is monster in japanese)
it's a RPG variant of Minesweeper, where you have life points, level up and fight against monster (mines) that gives you xp once killed (you loose HP if you fight a monster higher lvl than you).
it's a flash game, that had an android release at some point (it was removed from the store for some reasons)
This is actually a quite interesting game, I played it for like 2 hours when I saw it first time.
Minesweeper is a probabilistic game, that's why you should use probabilistic tools to solve it.
For example you can use a particle filter to approximate the distribution of mines. Every time you obtain new information you update the filter so that only distributions compatible with constraints remain.
Once you have an approximation to the distribution of mines you can calculate the probability of each spot being a mine. You can also calculate statistical indicator like the Information Gain of each action.
A good strategy is therefore to play low mine probability with highest information gain. But there is a trade-off, when the mine probability is non-zero. So you need to look-ahead.
Fortunately thanks to the mine distribution approximation you can also simulate any actions and their consequences, because you can use your approximation of the distribution to predict which number will be revealed upon a click.
So an even better strategy is to unroll the game tree for the best few candidate moves based on some heuristics, and calculate the cost gain probabilities after a few moves.
Most of the times Minesweeper is deterministic, and you can just think and get an empty spot. From time to time, you are unlucky and has to guess.
A few years ago, I modified the version of minesweeper in the "Games" collection of Racket to get more mines per board and get more hard cases. (I added the trick to autoopen the squares that have enough flags around, so it solved all the easy cases and it was more fun. I never upstreamed the changes...)
I like Dragonsweeper (discussed in a sibling comment) because it has a more clear probability and information tradeoff.
Interestingly, the main problem with Minesweeper is that is a game of chance (so the approach discussed in the article is very appropriate).
For a minesweeper variant purely based on logic, I highly recommend the game Tametsi. It has 160 handcrafted levels, and some have very interesting geometrical arrangements. I have logged over 100 hours in this game.
Tametsi is amazing. I also like the drawing mode, and I think it should be added to the Steam overlay so that you could use it in every game.
The HexCells series is also worth a look for anyone interested in pure logic Minesweeper.
There are other squares to click on on the other side of that "probability wall" that might reveal more info at a lesser danger percentage.
Yes, (original author here) in fact all the cells outside this region have an even better safety probability of 80.1%. I think the best move might be to start fresh in a new corner.
Hmm, but how likely are clicks on random squares to reveal more safe clicks? Seems likely that even if you hit a safe square you might still not have any safe moves. The goal ought to be to create more safe moves for the next turn, to reduce your chance of dying over the whole game, not just in the current turn. I wonder what that analysis would look like.
In the given example, if you click two squares down from the 3 in the 2-3-4 at the bottom, if you get a 3 it may reveal a 3 that will open up all the spaces around it. Which in the process may reveal what kind of 4 it is.
If you click on the square three to the right of the top 1, if that shows a 1, then a lot of surrounding squares can be revealed and again you may "walk up" to a more definitive mapping of the bombs.
I'm not even sure those are the optimal examples, but when I minesweeper it was for speed.
The real advantage, especially at this stage of the puzzle, is that those squares might quickly lead to another big field to be revealed.
How could this be extended to a negative bomb space like in Bombe (https://store.steampowered.com/app/2262930/Bombe/)?
At first I thought the "equal probability assumption" wasn't too bad an approximation, but it has an average Brier score of 0.217. Much worse than I thought.
The article makes a serious math error early on.
The author’s math considers how mines would be distributed if mines were distributed to the empty squares after reaching that board state.
This is wrong.
This is classic Monty Hall Problem. The author is doing the equivalent of saying “there are two doors left, so the odds are 50 / 50 that the prize is behind either door.
It invalidates all of the numbers after this point.
I don't agree (I'm the author).
The difference is that Monty knows which of the doors the car is behind and deliberately avoids it, thereby giving away information about where the car is.
Whereas in Minesweeper we've just blindly stumbled across a situation where we have to guess.
It would be like if every show Monty always revealed a random door. Sometimes he would reveal the car and the game would end immediately. In the cases when he didn't reveal the car it really would be 50/50 between the remaining two doors.
I agree, its definitely not Monty Hall, and IDK why they are so confident.
What would the winrate of a bot doing these calculations be compared to one that doesn't?
The bot at https://mrgris.com/projects/minesweepr/ does these calculations, and has a winrate of 37.8% on expert. I don't know what a more naive bot would achieve.
Is this better compared to an actual expert human?
I think the human experts mostly care about speed rather than their average solve percentage. If they're forced to guess then they can just restart if they get it wrong.
now this is time well spent