With a 52.4% win rate on Beginner level when the first click is allowed to be a mine. Four learning models are tested and combined to create an optimal strategy Machine learning is used to create a Minesweeper solver (Mio). Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence Learning Minesweeper with Multirelational Learning (2003) (where no cell can touch more than 3 mines) is NP-complete and that ASP-Minesweeper (where multiple solutions are consistent) is also NP-complete. The Complexity of Puzzles: NP-Completeness Results for Nurikabe and Minesweeper (2003)īrandon McPhail reviews SAT and NP-completeness and in Chapter 5 applies these concepts to Minesweeper. TheĪuthors explore ways to reduce state space calculations then solve various densities for grids up to 4*4. Nakov and Wei define Minesweeper as a Markov Decision Problem and propose that the counting problem #Minesweeper is #P-complete. Meredith Kadlac develops a solver in C++ to explore minesweeper consistency in one dimension. Undergraduate Thesis (Oregon State University) Lecture by Richard Kaye on his famous "Minesweeper is NP-complete" paper.Įxplorations of the Minesweeper Consistency Problem (2003) Public Lecture (University of Birmingham) The Minesweeper Game: Percolation and Complexity (2002)Ĭombinatorics, Probability & Computing, 11 (5), 487-499Įlchanan Mossel uses perculation theory to calculate safe paths within an infinite Minesweeper lattice. Three strategies are implemented in three modes for Microsoft Minesweeper with a CSP implementation producing world record win ratios of 80.0% on Beginner and 33.9% on Expert. Solver (1995) to test constraint satisfaction solving strategies. Graduate Term Paper (University of Toronto) Minesweeper as a Constraint Satisfaction Problem (2001) Source code is shared forĪ solver capable of solving a 4*4 grid and he demonstrates that starting in corners increases the chance of winning. Lindgren calculates mine probabilities using combinatorics, algebra and matrices. Stephen Rhee applies genetic programming to evolve a Minesweeper solver. Undergraduate Thesis (Genetic Algorithms and Genetic Programming, Stanford, 2000, 312-318) This is the updated version of the paper from 2007.Įvolving Strategies for the Minesweeper Game using Genetic Programming (2000) Richard Kaye explores the consistency problem for infinite versions of Minesweeper and proves the game is Turing complete. Infinite versions of minesweeper are Turing complete (2000) Logic gates and in this updated version from 2007 he comments on Kadlac's 2003 "Minesweeper Consistency" paper. (The original paper was published on his website in 1998.)īoletim Sociedade Portuguesea de Mathemática, Janeiro 2007, 181-189Ĭompanion paper to Richard Kaye's famous "Minesweeper is NP-complete" paper. He demonstrates how to create a Minesweeper computer usingīoolean circuits then proves that solving Minesweeper is a satisfiability (SAT) problem thus NP-complete. Richard Kaye proves Minesweeper belongs to the class of P=NP? problems. Mathematical Intelligencer, Vol 22, No 2, 9-15 He also discusses how different approaches could be used to solve real-world problems. Ṕal Ruj́an discusses whether a neural network could solve Minesweeper and proposes several strategies. The Minesweepers' Bayesian Guide to Survival (1998) Undergraduate Thesis (Genetic Algorithms and Genetic Programming, Stanford, 2000, 137-146)Ĭhris Quartetti applies genetic programming to evolve a Minesweeper solver. How Cellular Automaton Plays Minesweeper (1997)Īpplied Mathematics and Computation 85, 2-3, 127–137Īndrew Adamatzky develops a two-dimensional deterministic celluar automaton for solving n*n Minesweeper lattices.Įvolving a Program to Play the Game Minesweeper (1998) Article hosted with permission from COMAP. Where mines touching numbers can reduce those numbers to a known pattern. The paper includes an early description of the 1-2-1 pattern and the first mention of "relative" patterns Philip Crow introduces a Minesweeper notation system and defines several theorems on what can and cannot be knownįrom some common mine configurations. Introducing Proof Techniques Using The Logical Game Mine Hunter (1995)Īllan Struthers uses Mine Hunter (an early Windows Minesweeper rival) to introduce proof techniques.Ī Mathematical Introduction to the Game of Minesweeper (1997) Welcome to the biggest collection of published math papers about Minesweeper!
0 Comments
Leave a Reply. |