Solving Witness Triangle Puzzles Faster with an Automatically Learned Predicate

arXiv:2308.02666 · cs.AI · Submitted 2023-08-04 · Read on arXiv

cs.AI

Submitted: 2023-08-04

Updated: 2026-11-12

Comments: 11 pages, 8 figures, 4 tables

License: http://creativecommons.org/licenses/by/4.0/

The gist: The Witness is a game with combinatorial puzzles that are challenging for both human players and AI solvers.

Terminology

Abstract

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.

Related papers