Synthesizing interpretable strategies for solving puzzle games
Eric Butler, Emina Torlak, Zoran Popović · 2017
Understanding how players interact with games is an important challenge for designers. When playing games centered around problem solving, such as logic puzzles like Sudoku or Nonograms, people employ a rich structure of domain-specific knowledge and strategies that are not obvious from the description of a game's rules. This paper explores automatic discovery of player-oriented knowledge and strategies, with the goal of enabling applications ranging from difficulty estimation to puzzle generation to game progression analysis. Using the popular puzzle game Nonograms as our target domain, we present a new system for learning human-interpretable rules for solving these puzzles. The system uses program synthesis, powered by an SMT solver, as the primary learning mechanism. The learned rules are represented as programs in a domain-specific language for condition-action rules. Given game mechanics and a training set of small Nonograms puzzles, our system is able to learn sound, concise rules that generalize to a test set of large real-world puzzles. We show that the learned rules outperform documented strategies for Nonograms drawn from tutorials and guides, both in terms of coverage and quality.