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
Fig. 1: A 1×2 triangle puzzle. The green dashed line solves the puzzle since the solution path intersects the left square once and right square twice, matching the numbers of triangles in their respective squares. The red dotted line is not a solution to the puzzle.
Fig. 2: A partial search tree for solving the puzzle in Figure 1 . The dashed lines show the partial paths for solving the puzzle so far. The two vertex markers ⋆,♡ mark the start and goal vertices of the grid.
Fig. 3: Figure 1 with updated vertex labels.
Predicate
Returns True if
edge(A, B,C)
A is an edge connecting vertices B and C
square(A,B,C)
B is the number of triangles and C is the list of edges around square A
path(A,B)
B is the list of edges in path A
pathHead(A,B)
B is the vertex at the head of path A
count(A,B,C)
the number of occurrences of list A in list B is C , that is ∣A∩B∣=C
len(A,B)
the length of list A is B
TABLE I: Predicate building blocks for the background knowledge given to Popper .
if path.head is not incident to square and puzzle.triangles[square]=3 and path.edges[square]=1: incompletable=True
2
Same except two(F) .
Same except path.edges[square]=2
TABLE II: Output of Algorithm 2 : the predicate π∘ computed over a single constraint.
Speedup Metric
Aπ∗
WA*
NN
speedupt
6.38
1.11
0.02
speedupE
6.27
1.04
0.77
TABLE III: Aggregate Results.
Fig. 4: Time and expansion speedup of π∘ on Ptest .
Fig. 5: A 5×5 puzzle. The vertices are numbered to show the partial path that pruning with π∘ forces Algorithm 1 to take. The two vertex markers ⋆,♡ mark the start and goal vertices.
Fig. 6: Rounded percentage of puzzle instances solved by Algorithm 1 with pruning using πbaseline (above) and with π∘ (below).
Fig. 7: Portion of a puzzle with a partial path for the one(F) case in a red dotted line and for the two(F) case drawn in a blue dashed line.
Fig. 8: Search tree with a policy for solving the puzzle from Figure 1 .
Size
Instances
Expansions
Time (s)
2×2
135
11
0.0005
2×3
1,321
31
0.001
2×4
1,788
72
0.025
3×3
1,012
109
0.004
2×5
1,977
173
0.006
3×4
2,112
401
0.01
TABLE IV: Test-set distribution and mean baseline search costs by puzzle size.