6 ms·
Algorithmic Approaches to Playing Minesweeper (2015)
- Casseres 9y agoFor anyone who wants to play Minesweeper without the hassle of trying to track down a known-good *.exe, I recommend Minesweeper X [0]. The board size isn't limited plus a ton of other features. It also works perfectly under WINE with Winetricks. [0] http://www.curtisbright.com/msx/ http://www.curtisbright.com/msx/
- accatyyc 9y agoI’ll join you and show off mine as well! Runs in terminals, and also has a rougelike adventure mode where you navigate the board with a character. https://github.com/accatyyc/terminal-mines https://github.com/accatyyc/terminal-mines
- Casseres 9y agoMinesweeper X isn't mine (just a happy user), but yours is cool too, thanks!
- joe_the_user 9y agoIf you're using linux, there's Gnome Mines, http://linux.softpedia.com/get/GAMES-ENTERTAINMENT/Puzzle/GNOME-Mines-102556.shtml http://linux.softpedia.com/get/GAMES-ENTERTAINMENT/Puzzle/GN...
- FRex 9y agoKDE of course has its clone too: https://www.kde.org/applications/games/kmines/ https://www.kde.org/applications/games/kmines/ And as always with old XP era exes: ReactOS has its own compatible copies and you can use them in Windows and they will usually work (minesweeper from ReactOS does work on Windows 10, I just checked).
- tomcdonnell 9y agoHere's my command-line minesweeper solver, in c++. It is not optimal, but does a pretty good job of solving expert sized minefields. I never worked out what percentage of minefields it solves, because I planned on doing some more work on end game scenarios. That was about ten years ago. The code is quite readable, so may be of interest to fellow coders, and anyone is welcome to extend it if they wish. https://github.com/tomcdonnell/minesweeper_solver_text_cpp https://github.com/tomcdonnell/minesweeper_solver_text_cpp
- kaffeemitsahne 9y agoI'll add another implementation, Mines from the great sgt-puzzles collection. https://www.chiark.greenend.org.uk/~sgtatham/puzzles/ https://www.chiark.greenend.org.uk/~sgtatham/puzzles/ It has an option to "ensure solubility" similar to the one @gergoerdi mentions above.
- luckyt 9y agoI did some work on a minesweeper solver [1], I'm surprised my work is not mentioned. The best version of their algorithm wins on expert 32.9% of the time, whereas my AI achieves about 50% win rate. My AI uses the connected components decomposition that they did, but also some endgame tactics that significantly improved win rate (that they didn't consider). [1]: https://luckytoilet.wordpress.com/2012/12/23/2125/ https://luckytoilet.wordpress.com/2012/12/23/2125/
- taneq 9y agoThanks for the interesting write-up! You say here yours wins around 50% of the time on expert, whereas your linked article says 50% of the time on advanced - is this a typo, and/or what's your success rate on expert?
- luckyt 9y agoSame thing -- 16x30 with 99 mines.
- ballenf 9y agoThanks! One question: does your algorithm account for the possibility that a non-border square could have a lower odds of being a mine when you reach the last-resort safest guess approach? It looks like you only consider the odds of mines in the borders, but not that a complete unknown square could have lower odds. You do mention the situation where you know that particular square has no mines, but not where you know the odds are lower than in any of the border squares. It's pretty rare, but in my minesweeper obsession days I would occasionally see it happen. Edit: upon further reflection, it's actually pretty common in the early stages, esp. in lower difficulty games. You will occasionally on the first click get a high-ish number and are much better off clicking a non-neighbor as the next guess. You must be doing this or couldn't achieve 50%, I'd guess.
- luckyt 9y agoYes, I do this as an endgame tactic. In some situations, knowledge of the mine counter can help you deduce that a non-border square is empty. (Details in the last part of the article)
- ronilan 9y agoWell, it has been a while since the last time, but a ritual is a ritual and it has to be followed. Whenever someone says "minesweeper", I have to post my implementation. Here goes: http://www.ronilan.com/bugsweeper/ http://www.ronilan.com/bugsweeper/ Few notes: 1. This is dated January 2014. It is a job interview homework. 2. The HN community has detected a bug and indicated that it should be fixed. That was done March 2017. 3. There are currently no known bugs. 4. The goal of the game is to find the unknowns. 5. No puns intended. 6. Code: http://www.ronilan.com/bugsweeper/js/bugsweeper.js http://www.ronilan.com/bugsweeper/js/bugsweeper.js
- mabbo 9y agoWell, you've successfully distracted me for a good ten minutes. Really like the UI.
- djaychela 9y agoLike it - did you get the job?
- ronilan 9y agoObviously not. But it is totally understood. You can't expect a leading tech startup like Thumbtack to lower the bar for a 40+ yo self taught programmer like myself. They only hire the best!
- deleted 9y ago[deleted]
- gergoerdi 9y agoI can't not plug Peter Divianszky's implementation at https://hackage.haskell.org/package/minesweeper https://hackage.haskell.org/package/minesweeper which has the awesome property that the board is generated as you play, in such a way that you never have to guess (in the sense that if a field is not forced by currently shown clues to have a mine, then it won't have one when you click on it).
- iiv 9y agoThis paper is wrong in section 4.1: >The first click of a Minesweeper game deserves special attention since it is rather unique. >Namely, the opener is always a guess because the player starts with a covered board. >In addition, the challenges associated with the opening move are unavoidable and are shared among all solvers. Thus, finding an optimal policy for dealing with the initial click will benefit every approach The first click of a Minesweeper game is always safe[1] [1]http://www.minesweeper.info/wiki/Strategy#First_Click http://www.minesweeper.info/wiki/Strategy#First_Click
- oerpli 9y agoI think what the author meant is: It's a guess where the best position is for the first click. You can't fail with the first move but you can have different outcomes and it's advisable to choose a position where the expected information gain is optimal.
- reificator 9y agoIn the original game, yes. Not every clone. I went out of my way to lookup the way that the original minesweeper handled this case, as you can see from that link it does have a perceptible effect on the game.
- samkellett 9y agoit's funny that there's a whole section (4.1) on picking a starting move that increases the probability that that first cell is a 0-cell when in fact the game guarantees that your first click will do that.
- ygra 9y agoIt guarantees that the first cell is not a mine. You could still just get a number there.
- YokoZar 9y agoI've long wanted to mak an "always possible" variant of minesweeper. This is equivalent to only presenting the player with a board that a "perfect" algorithm can solve.
- ggus 9y agoFor a nice minesweeper variant, try Mamono Sweeper. It has the same mechanic as minesweeper, but instead of bombs you are sweeping for monsters, which have a level (1 to 9). A clue in a cell is the sum of the monster's levels surrounding it. You can kill monsters of level 1, and eventually you level up and are able to kill bigger monsters.
- maggit 9y agoAh, let me throw my take on Minesweeper into the ring as well: http://magnushoff.com/minesweeper/ http://magnushoff.com/minesweeper/ My final variant is like the original Minesweeper except that when you are provably stuck, the game will help you to move on.