Bayesian Minesweeper

2 points

expand_less expand_more

Sep 20, 2011

This is an idea I've been throwing around in my head for the last couple of days, but finally got around to actually implementing in code today. I am now ready to subject the world to my terrible programming skills.

I suspect most computer users will be familiar with the game of minesweeper - it really isn't all that complex by itself. However, I've added a little twist to it. The idea is the following:

Mines and people are randomly distributed across the minefield.
The player can only detect mines, not people.
The player can stop searching for mines at any time she/he desires.
If the player opens a cell with a mine, all mines detonate.
If the player stops searching, only the non-flagged mines detonate.
Once the game ends, every person in an explosion or next to one dies.
Every survivor contributes 10 pleasure.
Every death contributes 10 pain.
For every death, every survivor contributes 0.05 pain.
There are 480 cells, 250 people and 99 mines.
Your goal, should you choose to embrace it, is to maximise the pleasure/pain ratio.

That is all. The values I chose arbitrarily, but right now I feel it's pretty balanced. Once you flag around a third of the mines, the ratio starts rising considerably, but there is always an element of chance. If you hit a mine on your first try (or quit immediately), around 80% of the people will die on average.

SYSTEM REQUIREMENTS: Python 2.7, ncurses.

Update #1: Implemented JushuaZ's idea - if you flag an empty cell, all your flags are disregarded.

Update #2: Fixed bug spotted by DanielLC

Bayesian Minesweeper

2 points

expand_less expand_more

Comments

sorted by

Highlighting new comments since Today at 6:07 AM

All comments loaded

5 points

expand_less expand_more

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.

5 points

expand_less expand_more

1 point

expand_less expand_more

Agreed, fixed, updated.

1 point

expand_less expand_more

5 points

expand_less expand_more

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.

5 points

expand_less expand_more

1 point

expand_less expand_more

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.

1 point

expand_less expand_more

5 points

expand_less expand_more

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.

5 points

expand_less expand_more

0 points

expand_less expand_more

I think the "Now 20% more Bayesian!" slogan is just marketing to the LessWrong audience.

0 points

expand_less expand_more

4 points

expand_less expand_more

Your goal, should you choose to embrace it, is to maximise the pleasure/pain ratio.

Shouldn't you be trying to maximise the pleasure-pain difference? They're not quite the same thing.

4 points

expand_less expand_more

1 point

expand_less expand_more

Interesting.

That's the difference between sum and average utilitarianism, I believe.

1 point

expand_less expand_more

1 point

expand_less expand_more

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.

1 point

expand_less expand_more

Oscar_Cunningham

3 points

expand_less expand_more

Using probability to win normal minesweeper: http://nothings.org/games/minesweeper/

3 points

expand_less expand_more

1 point

expand_less expand_more

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.

1 point

expand_less expand_more

2 points

expand_less expand_more

For anyone trying to play this, you need to run it from terminal, running it from IDLE won't work.

2 points

expand_less expand_more

1 point

expand_less expand_more

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.

1 point

expand_less expand_more

1 point

expand_less expand_more

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.

1 point

expand_less expand_more

0 points

expand_less expand_more

Well caught, fixed.

You quit with the 'q' key.

0 points

expand_less expand_more

0 points

expand_less expand_more

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.

0 points

expand_less expand_more

0 points

expand_less expand_more

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.

0 points

expand_less expand_more

2 points

expand_less expand_more

Maybe you flagged an empty cell? That causes all your flags to be disregarded.

That seems like something that ought to have been mentioned in the documentation :)

2 points

expand_less expand_more

1 point

expand_less expand_more

Maybe you flagged an empty cell?

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.

1 point

expand_less expand_more

0 points

expand_less expand_more

That's what it prints if there's zero pain. Should it be "infinity" instead?

0 points

expand_less expand_more

3 points

expand_less expand_more

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.

3 points

expand_less expand_more