Introduction
Minesweeper is more than a simple computer game; it is a mathematically formidable challenge, with the task of determining board consistency classified as NP-complete. Playing effectively requires a sophisticated blend of spatial logic, arithmetic, and probabilistic reasoning. While most game-playing AIs rely on hand-crafted heuristics, this research explores whether a machine can automatically induce these complex relational strategies from scratch.
Traditional propositional machine learning often struggles with Minesweeper because the game is defined by the relationships between tiles rather than static attributes. To address this, the authors utilize Inductive Logic Programming (ILP), specifically a system called Mio, to learn rules in the form of clausal logic.
The Mio Learning System
Mio is an example-driven "covering" system. It starts with background knowledge and a set of positive and negative examples, iteratively building a theory that explains the data.
To make learning feasible in the massive search space of Minesweeper, three key optimizations were implemented:
- Macro-operators (Macros): Instead of adding one logic literal at a time, Mio uses sequences of literals. This allows the search to "jump" over intermediate steps, significantly reducing the search space.
- Greedy Search with Macros: Bundling literals together allows a fast greedy search to overcome the "myopia" problem, where necessary but currently unhelpful literals are otherwise ignored.
- Active Inductive Learning: Mio uses an "active learning server" to provide specific counterexamples to generated rules, preventing overfitting and maintaining a manageable training set.
Experimental Setup and Results
The system was trained and tested on "Beginner" level 8x8 boards with 10 mines. Background knowledge included predicates for identifying neighbors, counting mines in a "fringe" (the border between hidden and revealed tiles), and performing set operations.
The strategy learned by Mio achieved a 52% win rate. In comparison, an informal study of non-expert humans showed a win rate of only 35% under the same conditions. When the learned logic rules were combined with a simple probabilistic guessing heuristic for ambiguous "stuck" situations, the win rate increased to 60%.
The optimizations proved essential: the combination of Active Learning, Greedy Search, and Macros reduced the average number of nodes explored per search from 3,135 to just 566.
Conclusion
The research demonstrates that multirelational learning can effectively rediscover human-like expertise in complex logical domains. The most sophisticated rule learned by the system (Rule S-3) mirrors strategies used by expert human players and hand-coded solvers. While logic provides a strong foundation, future work will explore more complex board sizes and the integration of advanced probabilistic reasoning to handle the game's inherent uncertainty.
Summary updated