cs.AIAug 4, 2023

Solving Witness Triangle Puzzles Faster with an Automatically Learned Predicate

Authors: Justin Stevens, Vadim Bulitko, David Thue

Organizations: Department of Computing Science, University of Alberta · School of Information Technology, Carleton University

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.

Figures & tables

Explore similar work

CardsList
  1. Witness: Discovery, Deciphering, and Epiphany in Interactive Puzzle Environments

    Sep 26, 2026Guanghan Ning, Ping Liu, Linyi Li +6AI Agent BenchmarksRL for LLM Agents

  2. PuzzleJAX: A Benchmark for Reasoning and Learning

    Aug 22, 2025Sam Earle, Graham Todd, Yuchen Li +5RL BenchmarksGame-Playing Agents