The Witness is a game with combinatorial puzzles that are challenging for both human players and AI solvers. Search-based AI solvers can require large amounts of time to solve such puzzles. We accelerate search by automatically learning a predicate that predicts whether a partial path to a Witness puzzle is completable to a solution path. We demonstrate that our learned predicate is human-explainable, which makes it amenable to proofs, and we prove a key property that allows us to use it for pruning successor states in search. Doing so accelerates search by about six times while maintaining search completeness. Conversely, given a fixed time budget per puzzle, our predicate-accelerated search can solve more puzzles of larger sizes than a baseline search using a hand-coded predicate. Finally, we empirically demonstrate how accelerating search using an automatically learned predicate can outperform two competitors, weighted A* and Levin tree search with neural networks, in terms of time and number of nodes expanded.
We analyze a mathematical property of the popular card game SET. We present a revised geometric and computer-assisted proof that the maximum number of sets for 12 cards is 14 using finite field geometry, combinatorics, and graph theory. We present several computer algorithms for finding or approximating the maximum number of sets. We show a complete computer proof that iterates over all possible board configurations. We use this method to compute the maximum number of sets with 4 properties for a small number of cards, but it is generally too inefficient. With this method, we compute the maximum number of sets for 3 properties for all possible numbers of cards. Finally, we compare this to an existing approximation algorithm for finding maximal sets.