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

arXiv: https://arxiv.org/abs/2308.02666 · HTML: https://mlsanity.com/paper/2308.02666/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 22 references that are in the map.
- First posted on arXiv 4 Aug 2023.

## Builds on (most cited first, 5 of 5)

- [Procedural Content Generation via Machine Learning (PCGML)](https://mlsanity.com/paper/1702.00539/) (2017)
- [The LAMA Planner: Guiding Cost-Based Anytime Planning with Landmarks](https://mlsanity.com/paper/1401.3839/) (2014)
- [Learning programs by learning from failures](https://mlsanity.com/paper/2005.02259/) (2020)
- [Inductive logic programming at 30](https://mlsanity.com/paper/2102.10556/) (2021)
- [Policy-Guided Heuristic Search with Guarantees](https://mlsanity.com/paper/2103.11505/) (2021)

## Abstract (arXiv)

Automatically solving puzzle instances in the game The Witness can guide players toward solutions and help puzzle designers generate better puzzles. In the latter case such an Artificial Intelligence puzzle solver can inform a human puzzle designer and procedural puzzle generator to produce better instances. The puzzles, however, are combinatorially difficult and search-based solvers can require large amounts of time and memory. We accelerate such search by automatically learning a human-explainable predicate that predicts whether a partial path to a Witness-type puzzle is not completable to a solution path. We prove a key property of the learned predicate which allows us to use it for pruning successor states in search thereby accelerating search by an average of six times while maintaining completeness of the underlying search. 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.