Solving Witness-type Triangle Puzzles Faster with an Automatically Learned Human-Explainable Predicate

Abstract

The Witness is a game with difficult combinatorial puzzles that are challenging for both human players and artificial intelligence based solvers. Indeed, the number of candidate solution paths to the largest puzzle considered in this thesis is on the order of 10^(15) and search-based solvers can require large amounts of time and memory to solve such puzzles. We accelerate search by automatically learning human-explainable predicates that predict whether a partial path to a Witness-type puzzle is not completable to a solution path. We prove a key property of one of the learned predicates which allows us to use it for pruning successor states in search. Our method accelerates search by an average of six times while maintaining completeness of the underlying search. We also explain how our predicate speeds up search on a specific puzzle instance by over 1000 times. Conversely given a fixed search time budget per puzzle our predicate-accelerated search can solve more puzzle instances of larger sizes than the baseline search. We also empirically compare the performance of our learned predicate to two popular competitors, weighted A* and Levin tree search with neural networks, and show that our learned predicate outperforms both of them in terms of how much they speed up a baseline.