Interesting, you’ve turned the game into an optimal stopping puzzle. What I find interesting is that a player could determine their optimal strategy if they had an accurate probability distribution for how many moves it will take them to lose the game by opening a cell with a mine. Players who are better at the Minesweeper aspect of the game will, of course, be able to do better than others by finding more mines.
What I don’t get is this: what is “Bayesian” about it? It’s really more of a utility maximization/optimal stopping game.
It is, as you’ve already pointed out, a matter of perspective. A player (like me, I’m ashamed to admit) who considers minesweeper an instinct akin to breathing will be able to focus on the dilemma between taking a risk or stopping, if they reach a point where taking a risk is required to progress. Of course, a minesweeper addict capable of playing without shutting their mind off (wait, that’s why I’m playing it in the first place!) will recognise the mine and population densities as prior probabilities, and try to workout the conditional probabilities, and how they’re likely to impact the outcome.
Makes sense. The title caused me to assume that there was going to be some surface-level Bayesian updating worked into the core gameplay mechanic and I guess I was surprised when there wasn’t.
Possible loophole: I can flag every single square. Then no mines will detonate. (I don’t know if your code lets me do that but most Minesweeper implementations let one have more flags out than there are mines). There should be a similar penalty for flagging an unmined square. Possibly if any square is flagged that is not a mine then all mines (flagged or not) detonate.
There’s a lot of interesting stuff related to minesweeper already. The standard minesweeper is already NP-complete in the sense that if you can ask for an arbitrary board with arbitrary configuration “is it consistent with what I know for their to be a bomb in this square” is an NP-complete problem. Proof. This suggests that your game is quite difficult because it is strictly harder than this since if you can prove a square is open then you should open it, and if you can prove a square has a mine then you should flag it.
No. In average utilitarianism, you take the difference and divide by the number of people. The method this game uses would imply that doubling the amount of pleasure and pain each person feels would have no net benefit or cost, regardless of what the original values were. If there were only pleasure, it wouldn’t matter how much, so long as it’s greater than zero.
Also, if you used this method, and there were lots of other people in the world, it would effectively come out to the same as normal utilitarianism.
I think minesweeper makes a nice analogy with many of the ideas of epistemic rationality espoused in this community. At a basic level, it demonstrates how probabilities are subjectively objective—our state of information (the board state) is what determines the probability of a mine under an unknown square but that there really is only one correct set of mine probabilities. However, we also run quickly into the problem of bounded cognition. In this situation we resort to heuristics. Of course, heuristics are of varying quality, and it is possible with mathematics, to make better heuristics.
For example, if you find that the set of possible configurations of mines in a particular neighborhood is partitioned into, say, those that involve k mines and those that involve k+1 mines, then you can get a pretty good estimate of the probability that the true configuration will be in one partition or the other. It depends on the density of mines under the squares that aren’t known (something like a prior).
There are situations which come up in which one must decide just what one’s goals are—is it to survive the next click or to maximize the chance to win the game? Often these two goals result in the same decision, but sometimes, interestingly, they result in different decisions.
I like to play on a 24x30 board (maximum allowed on windows machines), with 200 mines. This makes the game rarely about deductive logic alone. Situations in which probability theory is necessary come up all the time with this density.
Requesting some help… I’ve just installed Python 2.7, however I am having trouble getting the ncurses library. When I try to run bsweep.py it just shows a command prompt that disappears.
The game didn’t seem to work for me. I uncovered every mine, and 216 people died. Also, there seems to be no way to quit or restart the game after I lose.
I can quit now, but I still lost almost everyone when I only left one mine uncovered.
Also, it would be nice to have a feature where when you get a zero, it automatically uncovers all the adjacent mines.
I notice that the added challenge of being able to end early is only remotely difficult when you consider the chance of messing up. You can usually uncover virtually all the mines without having to worry about clicking somewhere at random, but you might accidentally uncover the wrong space.
You should add multiple difficulties. Also, have it track your score through several games. As-is, it seems likely people would just try to get the perfect score or something, rather than the highest expected score.
In my experience, even getting just around a third of the mines produces around twice the survivors (~80) of when you don’t flag anything. Maybe you flagged an empty cell? That causes all your flags to be disregarded. And, of course, there is always an element of chance.
You should definitely be trying to maximize the difference. If you give the possibility of infinite utility, than it overpowers the high probability of finite utility. If people are trying to get the highest possible expected utility, they’ll maximize the chance of getting everyone to survive, rather than quitting early when they’re not sure.
Interesting, you’ve turned the game into an optimal stopping puzzle. What I find interesting is that a player could determine their optimal strategy if they had an accurate probability distribution for how many moves it will take them to lose the game by opening a cell with a mine. Players who are better at the Minesweeper aspect of the game will, of course, be able to do better than others by finding more mines.
What I don’t get is this: what is “Bayesian” about it? It’s really more of a utility maximization/optimal stopping game.
It is, as you’ve already pointed out, a matter of perspective. A player (like me, I’m ashamed to admit) who considers minesweeper an instinct akin to breathing will be able to focus on the dilemma between taking a risk or stopping, if they reach a point where taking a risk is required to progress. Of course, a minesweeper addict capable of playing without shutting their mind off (wait, that’s why I’m playing it in the first place!) will recognise the mine and population densities as prior probabilities, and try to workout the conditional probabilities, and how they’re likely to impact the outcome.
Makes sense. The title caused me to assume that there was going to be some surface-level Bayesian updating worked into the core gameplay mechanic and I guess I was surprised when there wasn’t.
I think the “Now 20% more Bayesian!” slogan is just marketing to the LessWrong audience.
Possible loophole: I can flag every single square. Then no mines will detonate. (I don’t know if your code lets me do that but most Minesweeper implementations let one have more flags out than there are mines). There should be a similar penalty for flagging an unmined square. Possibly if any square is flagged that is not a mine then all mines (flagged or not) detonate.
There’s a lot of interesting stuff related to minesweeper already. The standard minesweeper is already NP-complete in the sense that if you can ask for an arbitrary board with arbitrary configuration “is it consistent with what I know for their to be a bomb in this square” is an NP-complete problem. Proof. This suggests that your game is quite difficult because it is strictly harder than this since if you can prove a square is open then you should open it, and if you can prove a square has a mine then you should flag it.
Also related amusing video.
Agreed, fixed, updated.
Shouldn’t you be trying to maximise the pleasure-pain difference? They’re not quite the same thing.
Interesting.
That’s the difference between sum and average utilitarianism, I believe.
No. In average utilitarianism, you take the difference and divide by the number of people. The method this game uses would imply that doubling the amount of pleasure and pain each person feels would have no net benefit or cost, regardless of what the original values were. If there were only pleasure, it wouldn’t matter how much, so long as it’s greater than zero.
Also, if you used this method, and there were lots of other people in the world, it would effectively come out to the same as normal utilitarianism.
Using probability to win normal minesweeper: http://nothings.org/games/minesweeper/
I think minesweeper makes a nice analogy with many of the ideas of epistemic rationality espoused in this community. At a basic level, it demonstrates how probabilities are subjectively objective—our state of information (the board state) is what determines the probability of a mine under an unknown square but that there really is only one correct set of mine probabilities. However, we also run quickly into the problem of bounded cognition. In this situation we resort to heuristics. Of course, heuristics are of varying quality, and it is possible with mathematics, to make better heuristics.
For example, if you find that the set of possible configurations of mines in a particular neighborhood is partitioned into, say, those that involve k mines and those that involve k+1 mines, then you can get a pretty good estimate of the probability that the true configuration will be in one partition or the other. It depends on the density of mines under the squares that aren’t known (something like a prior).
There are situations which come up in which one must decide just what one’s goals are—is it to survive the next click or to maximize the chance to win the game? Often these two goals result in the same decision, but sometimes, interestingly, they result in different decisions.
I like to play on a 24x30 board (maximum allowed on windows machines), with 200 mines. This makes the game rarely about deductive logic alone. Situations in which probability theory is necessary come up all the time with this density.
For anyone trying to play this, you need to run it from terminal, running it from IDLE won’t work.
Requesting some help… I’ve just installed Python 2.7, however I am having trouble getting the ncurses library. When I try to run bsweep.py it just shows a command prompt that disappears.
The game didn’t seem to work for me. I uncovered every mine, and 216 people died. Also, there seems to be no way to quit or restart the game after I lose.
Well caught, fixed.
You quit with the ‘q’ key.
I can quit now, but I still lost almost everyone when I only left one mine uncovered.
Also, it would be nice to have a feature where when you get a zero, it automatically uncovers all the adjacent mines.
I notice that the added challenge of being able to end early is only remotely difficult when you consider the chance of messing up. You can usually uncover virtually all the mines without having to worry about clicking somewhere at random, but you might accidentally uncover the wrong space.
You should add multiple difficulties. Also, have it track your score through several games. As-is, it seems likely people would just try to get the perfect score or something, rather than the highest expected score.
In my experience, even getting just around a third of the mines produces around twice the survivors (~80) of when you don’t flag anything. Maybe you flagged an empty cell? That causes all your flags to be disregarded. And, of course, there is always an element of chance.
That seems like something that ought to have been mentioned in the documentation :)
The second time I did. I didn’t know where the last mine was and didn’t realize there was a penalty to guessing wrong.
I played again and got them all right and had no deaths. Now the pleasure over pain ratio is divide by zero error.
That’s what it prints if there’s zero pain. Should it be “infinity” instead?
You should definitely be trying to maximize the difference. If you give the possibility of infinite utility, than it overpowers the high probability of finite utility. If people are trying to get the highest possible expected utility, they’ll maximize the chance of getting everyone to survive, rather than quitting early when they’re not sure.