You're looking at Less Wrong's discussion board. This includes all posts, including those that haven't been promoted to the front page yet. For more information, see About Less Wrong.

JoshuaZ comments on Bayesian Minesweeper - Less Wrong Discussion

2 Post author: ZankerH 20 September 2011 12:43AM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Comments (20)

You are viewing a single comment's thread.

Comment author: JoshuaZ 20 September 2011 01:10:02AM 5 points [-]

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.

Comment author: ZankerH 20 September 2011 01:20:10AM 1 point [-]

Agreed, fixed, updated.