用自动学习的谓词更快求解 Witness 三角谜题
Solving Witness Triangle Puzzles Faster with an Automatically Learned Predicate
AI 导读
一项 arXiv 研究提出自动学习一个谓词，用于预测 Witness 谜题的部分路径能否补全为解路径，并证明其关键性质可用于搜索中的后继状态剪枝。该方法将搜索速度提升约 6 倍且保持搜索完备性；在每题固定时间预算下能解出比手写谓词基线更大规模的谜题，并在时间与节点扩展数上优于 weighted A* 和基于神经网络的 Levin tree search 两种竞争方法。
正文 · 原文
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.
| Comments: | 11 pages, 8 figures, 4 tables |
| Subjects: | Artificial Intelligence (cs.AI) |
| MSC classes: | 68T20 (Primary) 68T05, 68T27 (Secondary) |
| ACM classes: | I.2.8 |
| Cite as: | arXiv:2308.02666 [cs.AI] |
| (or arXiv:2308.02666v2 [cs.AI] for this version) | |
| https://doi.org/10.48550/arXiv.2308.02666 arXiv-issued DOI via DataCite |
Submission history
From: Justin Stevens [view email]
[v1]
Fri, 4 Aug 2023 18:52:18 UTC (118 KB)
[v2]
Thu, 12 Nov 2026 16:51:13 UTC (235 KB)
来源：arXiv cs.AI · arxiv.org