What are some interesting probability theory descriptions of games like minesweeper?
The Minesweeper game was (surprisingly) often used as a toy model for studying randomized algorithms and algorithms working in random environments.
A nice introduction to both algorithmic and probabilistic aspects of the Minesweeper can be found in this B. Sc. thesis “Algorithmic Approaches to Playing Minesweeper” by David J. Becerra from Harvard.
Some advanced studies exploring different algorithms and their relation to probabilistic models of the Minesweeper can be seen in the paper “Optimistic Heuristics for MineSweeper” by O. Buffet, Ch.-Sh. Lee, W. Lin, O. Teytaud,
or in the paper by M. Sebag and O. Teytaud “Combining Myopic Optimization and Tree Search: Application to MineSweeper”.
As for games like minesweeper in general, some of them were found to be connected with percolation theory (which is one of the most fashionable branches of probability at the moment), as well as with Markov decision processes, and computational complexity studies.
A good example of research in this direction is a paper “The Minesweeper game: Percolation and Complexity” written by Elchanan Mossel from Microsoft Research.
What does all of this beautiful mathematics says to a passionate gamer? Namely, what would be a good algorithm for solving the puzzle, and is the solution computationally hard?
In fact, the minesweeper is one of the classical board puzzles based on algebras of binary variables. Algorithmic solutions to these problems are typically sought with the use of integer linear programming. Unlike simple linear programming, integer programming problems are typically NP-hard. This is true even for binary integer programming where variables can only be 0 or 1 rather than arbitrary integers.
This transforms into the fact that, in its general formulation, the minesweeper is indeed algorithmically NP-complete. However, there is an argument that, if the minesweeper board is already known to be consistent, solving it is only guaranteed to be co-NP-complete, and might be (or not be) NP-complete.
And here is the raining defending Minesweeper world rekord holder Kamil Muranski performs his skillful play. Not sure if his brain is using integer linear programming or not 🙂
