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

Justin Stevens  Department of Computing Science
University of Alberta  Vadim Bulitko  Department of Computing Science
University of Alberta  David Thue  School of Information Technology
Carleton University

###### Abstract

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.

##  1 Introduction

The Witness is a well known game with challenging combinatorial puzzles [24].
Solving its puzzles automatically with artificial intelligence (AI) is useful
both to players and to puzzle designers. Indeed both players and puzzle
designers can use such an AI puzzle solver to see a solution to a particularly
challenging puzzle instance. Designers can also use the AI solver in concert
with a procedural puzzle generator to generate puzzles with desired solution
qualities [12].

Various search techniques can be applied to Witness puzzles. For instance, in
the triangle Witness-type puzzles that we use for our testbed in this paper
(Figure 1), a complete search can enumerate all possible paths for smaller
puzzles [22]. However, for puzzles of larger sizes such search becomes
intractable. For instance, for the puzzle size of $8\times 8$, the number of
candidate solution paths can be on the order of $10^{15}$ [15]. Furthermore,
arbitrary-sized, triangle Witness-type puzzles are NP-complete [1].

To scale up search to larger instances of Witness puzzles, we automatically
learn a predicate (i.e., a binary function) that predicts whether a partial
path considered during search can be completed to a solution path. We use this
predicate to focus the search on more promising partial paths. We compare the
results of our machine-learned predicate with a human-designed predicate that
implements a simple strategy for pruning partial paths that violate local
constraints.

We automatically learn predicates from training data using an off-the-shelf
Inductive Logic Programming (ILP) system, Popper [11]. Using Popper results in
human-readable predicates, which can shed light on the puzzle structure and be
useful to game designers.

The paper makes the following contributions. First, we present and evaluate a
method for machine-learning predicates from triangle Witness-type puzzles.
Second, we demonstrate the human-readability of the highest-performing learned
predicate. Third, the human-readability allows us to prove a key property of
the predicate which in turn enables its use for pruning while maintaining
completeness. In other words, given enough time and memory, our predicate-
accelerated search will solve any triangle Witness-type problem that is
solvable. Fourth, we empirically evaluate the predicate and present the
substantial performance gains over the baseline on puzzle instances we
generated.

Finally we make our code and data available upon request111Contact
<EMAIL_ADDRESS>in the hope of introducing the triangle Witness-type
puzzles as a standard benchmark to the community of Artificial Intelligence
and Procedural Content Generation (PCG) [23] game researchers.

##  2 Problem Formulation

We first formally define the type of Witness puzzle considered in this paper.
We then describe how heuristic search can be used to solve such puzzle
instances with predicates to accelerate search. Finally, we describe
performance measures to test efficacy of these predicates.

###  2.1 The Witness Triangle Puzzle

An $m\times n$ Witness-type triangle puzzle instance
$p=(G,v_{\text{start}},v_{\text{goal}},C)$ is a single-player combinatorial
puzzle using the triangle constraint from The Witness [24]; we refer them
henceforth as “Witness puzzles”.

Witness puzzles are played on a two-dimensional rectangular grid with $m\times
n$ squares. Here, $G=(V,E)$ is a graph representing the grid. Each vertex
$v\in V$ is a vertex on the grid where each corner of a puzzle square is
situated at a vertex. An $m\times n$ puzzle is thus represented by an
$(m+1)\times(n+1)$ rectangular grid of vertices and edges. To illustrate: the
$1\times 2$ puzzle in Figure 1 has one row of two squares. It is represented
by a $2\times 3$ rectangular grid with two rows of three vertices each (shown
as the blue circles). There are seven edges, $e_{1},\dots,e_{7}$, connecting
the six vertices.

Figure 1: A $1\times 2$ Witness-type triangle puzzle. The green dashed line
solves the puzzle since the solution path intersects the left square once and
right square twice which are equal to the number of triangles in their
respective squares. The red dotted line is not a solution to the puzzle.

Each square is delineated by four grid edges and can carry a constraint $c\in
C$ which associates that square with a positive number of triangles contained
in that square. A solution to the puzzle is a path on $G$ which (i) connects
the start vertex $v_{\text{start}}$ to the goal vertex $v_{\text{goal}}$ using
the edges in $E$, (ii) never visits a vertex more than once and (iii)
satisfies all constraints in $C$. To satisfy a square’s constraint $c\in C$
(i.e., the $k>0$ triangles in that square) the path must include exactly $k$
of that square’s four edges. A square without triangles imposes no
constraints.

To illustrate, the $1\times 2$ puzzle in Figure 1 has two constraints. The
left square contains a single triangle ($k=1$) which means that any solution
path to the puzzle must include exactly one of the square’s edges. The right
square carries two triangles ($k=2$) which imposes the constraint of including
two of the square’s edges in any solution path.

The red dotted line connecting the start and goal vertices in Figure 1 is not
a solution since it violates both constraints (i.e., includes two edges from
the first square and only one edge from the second square). On the other hand,
the dashed green line is a solution satisfying both constraints. A partial
path is any path in $G$ that starts out in $v_{\text{start}}$ but does not
reach $v_{\text{goal}}$. A partial path is incompletable if it is not a prefix
of a solution. In Figure 1, the partial path $[e_{3},e_{6}]$ is incompletable,
while $[e_{1},e_{2}]$ is completable. Solution length is the number of edges
in a soultion’s path.

###  2.2 Search for Solving Witness Triangle Puzzles

We now describe an A* search algorithm [13] for solving Witness puzzles
(Algorithm 1).

The search starts at $v_{\text{start}}$ and proceeds by expanding its search
frontier (i.e., the open list) containing partial paths and housed in a
priority queue. The priority queue is sorted by $(\pi,g+h,h)$ meaning that
lower values of $\pi$ are returned from the queue first. Ties among $\pi$
values are broken in favor of lower $g+h$ (length of the partial path so far +
a heuristic estimate of the remaining length). Remaining ties are broken in
favor of the lower heuristic estimate $h$ of the remaining length which is
equivalent to breaking ties towards higher $g$, a common technique in A*
search. Any residual ties are then broken in an arbitrary fixed order. Given
the four-connected rectangular grid underlying our Witness puzzles we use
Manhattan distance (MD) as the heuristic $h$.

Any real-valued function $\pi$ will allow sorting the open list. We will
demonstrate benefits of restricting $\pi$ to a two-valued function. Such a
predicate takes a partial path and a puzzle instance and returns True if the
partial path is predicted to be incompletable and False otherwise. In sorting
by $\pi$, partial paths for which $\pi$ returns False are placed earlier in
the queue than paths labeled True. An accurate predicate will thus focus the
A* search on completable partial paths.

Furthermore the binary nature of the predicate allows us to switch from
sorting the open list by $\pi$ to pruning partial paths by $\pi$ without even
putting them on the open list. Later in this section we will discuss when such
a switch from sorting to pruning can be made while maintaining completeness of
the underlying A* search.

input : puzzle $p=(G,v_{\text{start}},v_{\text{goal}},C)$, predicate $\pi$

output : solution $\ell$

1

2$\mathcal{Q}\leftarrow\text{priority queue sorted by }(\pi,g+h,h)$

3

4push $[v_{\text{start}}]$ onto $\mathcal{Q}$

5

6while  _$\mathcal{Q}\neq\emptyset$_ do

7 $\ell\leftarrow\text{head}(\mathcal{Q})$

8

9 $v\leftarrow\text{\rm end}(\ell)$

10

11 foreach  _$v_{\text{\rm new}}\in N(v)\setminus\ell$_ do

12 $\ell_{\text{\rm new}}\leftarrow\ell,v_{\text{\rm new}}$

13

14 if  _$v_{\text{\rm new}}=v_{\text{\rm goal}}$_ then

15 if  _$\forall c\in C\left[\text{\rm$\ell_{\text{\rm new}}$ satisfies
$c$}\right]$_ then

16 return $\ell_{\text{new}}$

17

18

19 else

20 push $\ell_{\text{new}}$ onto $\mathcal{Q}$

21

22

23

24return $\emptyset$

Algorithm 1 A* search for Witness puzzles.

The search loop continues as long as the open list is not empty (line 1) and a
solution is not found (line 1). The first sorted element of the open list, a
partial path $\ell$, is removed from the queue in line 1 and the last vertex
$v$ of the path is retrieved in line 1. We then expand the end of the path $v$
by generating all neighbours $v_{\text{new}}$ of $v$ in the graph $G$ that are
not already on the path $\ell$ (line 1). We generate each new path by
appending $v_{\text{new}}$ to the end of $\ell$ (line 1). If the new path
$\ell_{\text{\rm new}}$ reaches the goal vertex, we check if it satisfies all
constraints in $C$ (line 1). If so, the search stops and the solution is
returned in line 1. Otherwise, each new partial path is put onto the open list
with its $\pi,g+h,$ and $h$ values (line 1). When $\pi$ is constant (e.g.,
always True or always False) we have the standard A* algorithm.

Notice that Algorithm 1’s search is complete (i.e., it will find a solution if
one exists) even when $\pi$ has false positives, since any solution that is
wrongly predicted to be incompletable by $\pi$ will still end up in the queue
– just with a lower priority. An interesting case occurs when $\pi$ has no
false positives (i.e., when $\pi$ only returns True if a partial path is
incompletable). In this case, we can safely use $\pi$ to prune partial paths
that $\pi$ predicts are incompletable (never putting them in the queue) while
still maintaining a complete search, meaning it will return a solution to the
puzzle if there is one. This is due to a predicate with no false positives
only pruning incompletable partial paths from the queue.

###  2.3 Baseline

Figure 2: Search tree for solving the puzzle from Figure 1. The dashed lines
show the partial paths for solving the puzzle so far and the faded nodes show
partial paths that the baseline predicts are incompletable. The two vertex
markers $\star,\heartsuit$ mark the start and goal vertices of the grid.

Consider the fact that any partial path that includes more of a square’s edges
than there are triangles in that square cannot possibly be completed to a full
solution. Suppose that we had a predicate that predicted incompletability
based on this observation. This predicate would have no false positives, since
adding any edges to such a path would still result in a path that violated the
triangle constraint that made the predicate predict True. We can thus use this
predicate for pruning.

To illustrate, consider a search tree for solving the puzzle instance in
Figure 1. The predicate would label the bottom left and right nodes as
incompletable (True) since they include two edges of the square that has one
triangle in it. Since this predicate has no false positives, these partial
paths (and all of their descendants) can be pruned from the search tree.
Consequently, of the partial paths of length two (the bottom row in the
figure), only the middle node would be added to the priority queue. This node
leads to a solution.

We refer to this predicate throughout the paper as $\pi_{\text{baseline}}$. We
use Algorithm 1 with this local constraint checking predicate (implemented by
hand) as our baseline search. While this is a simple predicate for pruning
paths, we show later on that it is possible to automatically learn more
complex predicates that yield additional substantial savings.

###  2.4 Accelerating the Search

We aim to automatically find a predicate $\pi$ that speeds up A* on a set of
Witness puzzles $\mathcal{P}=\\{p_{1},\dots,p_{n}\\}$. We use two metrics to
quantify the speed-up: improvements in the solution time and the number of
nodes expanded. For a given puzzle $p\in\mathcal{P}$, let the time it takes
our baseline to solve the puzzle be $t(\pi_{\text{baseline}},p)$ and the
number of nodes expanded by the baseline be given by
$\mathcal{E}(\pi_{\text{baseline}},p)$. Similarly let the time it takes to
solve the puzzle using a learned predicate $\pi$ be $t(\pi,p)$ and the number
of nodes expanded be $\mathcal{E}(\pi,p)$.

The relative time reduction from using the predicate $\pi$ on the set of
puzzle instances $\mathcal{P}$ is defined as the time speedup:

$\displaystyle\text{speedup}_{t}(\pi,\mathcal{P})$
$\displaystyle=\frac{\sum\nolimits_{p\in\mathcal{P}}t(\pi_{\text{baseline}},p)}{\sum\nolimits_{p\in\mathcal{P}}{t(\pi,p)}}.$
(1)

Similarly the expansion speedup is:

$\displaystyle\text{speedup}_{\mathcal{E}}(\pi,\mathcal{P})$
$\displaystyle=\frac{\sum\nolimits_{p\in\mathcal{P}}\mathcal{E}(\pi_{\text{baseline}},p)}{\sum\nolimits_{p\in\mathcal{P}}{\mathcal{E}(\pi,p)}}.$
(2)

Notice that the set $\mathcal{P}$ can consist of a single problem instance
which then defines a per-instance speedup.

Treating the time speedup measure as an objective function, we set out to find
an approximate solution to the optimization problem:

$\displaystyle\pi^{*}=\operatornamewithlimits{argmax}\limits\limits_{\pi\in\Pi}\text{speedup}_{t}(\pi,\mathcal{P})$
(3)

where $\Pi$ is a space of predicates defined on paths and puzzle instances.
Thus, given a puzzle instance set $\mathcal{P}$ we wish to find the predicate
$\pi^{*}$ which speeds up A* the most relative to the baseline.

A desirable solution to the optimization problem would be found automatically
by a computer and will be portable: a predicate synthesized for one puzzle
should speed up search on other puzzles. We also prefer the predicate to be
compact and human-readable insomuch as their operation can be analyzed and
explained by a human. Finally, we prefer the predicate to be verifiable in
that it has no false positives so it can be used for pruning and maintain
completeness of A*.

##  3 Related Work

[4] (browne2013deductive) used deductive search to solve Slitherlink puzzles
[19] whose constraints are similar to triangle Witness puzzles. They modelled
each puzzle as a constraint satisfaction problem and used hand-coded rules to
manually reduce the domains of each variable. In our work, we aim to
automatically find such rules that can speed up search. [7]
(butler2017synthesizing) used program synthesis to find strategies for solving
Nonogram puzzles. They compare the outputs of their system to a set of
documented strategies for these puzzles, while we desire to find novel
strategies for solving puzzles in The Witness.

[20] (orseauL21) used neural networks to learn policies for solving a
different non-triangular type of Witness puzzle. However, policies encoded
with neural networks can be difficult to understand, resulting in less
available guidance for players and puzzle designers.

[17] (krishnan2022synthesizing) synthesized chess tactics using ILP. However,
their approach required data from human chess games where we prefer computer-
generated solutions. [16] (krajvnansky2014learning) learned predicates for
pruning actions in classical planning. This approach and similar work in
classical planning that pruned states from heuristic search use the relaxed
plan of a problem [14, 21]. Such a relaxed plan is computed by dropping
constraints from a problem. However, an effective constraint relaxation
strategy is not obvious for triangle Witness puzzles since removing a single
constraint can substantially change the solution path.

[6] (bulitko2022portability) used genetic algorithms and simulated annealing
to synthesize algebraic heuristic functions that speed up search on video game
maps. Our work is complementary in that they synthesized heuristic functions
while we hold the heuristic function fixed and attempt to synthesize
predicates. [9] (chen2021avoiding) used priority functions to avoid reopening
nodes in heuristic search. These priority functions were manually designed and
based on $g$ and $h$, which makes it unclear how to encode a binary property
of a given path using them. [3] (botea2022tiered) used multiple expansion
tiers, placeholder nodes and constraint propagation to speed up solving
Romanian crosswords puzzles. The tiers were defined by the two types of words
specific to Romanian crosswords and the number of points they contribute to
the solution. Their tiering mechanism is similar to our sorting of the open
list with a predicate but we have an additional ability to completely prune
partial paths instead of delaying their expansions.

##  4 Proposed Approach

As per Section 2.2, we aim to automatically learn an incompletability
predicate $\pi$ that accepts a partial path and a puzzle instance $p$ and
returns whether or not that path is incompletable. To simplify the learning
task we will learn a predicate $\pi^{\prime}$ defined on a partial path and a
single constraint from the set of constraints contained in the puzzle $p$.
Then whenever we need our desired predicate $\pi$ in Algorithm 1 we will call
$\pi^{\prime}$ repeatedly on each constraint from in the puzzle. If
$\pi^{\prime}$ returns True for any constraint we end the iteration and set
$\pi$ to True. Otherwise we set the output of $\pi$ to False.

###  4.1 Learning Predicates from Puzzle Instances

To automatically generate incompletability predicates, we employ inductive
logic programming (ILP) [18, 10] and use Popper as our off-the-shelf ILP
system [11].

Popper uses answer set programming to generate predicates based on background
knowledge. It then evaluates each candidate using the positive and negative
examples in the data set. If a candidate predicate satisfies a negative
example, Popper prunes generalizations of the predicate from the space of
candidates. If a predicate fails to satisfy some positive examples, Popper
prunes specializations of the predicate from the space. This allows Popper to
prune multiple candidate predicates given performance of a single candidate
predicate on the training data.

If Popper cannot find a predicate that satisfies all positive examples and
does not satisfy any negative examples, it returns a predicate that satisfies
the most positive examples while not satisfying any negative examples.

To generate examples for Popper given a puzzle instance $p$ we enumerate all
paths (without vertex repetitions) between the start and the goal vertices and
check to see which are solutions to the puzzle. Any partial path that is not
the prefix of a solution is incompletable and is thus recorded as a positive
training example. Any other partial path is recorded as a negative training
example.

In addition to the positive and negative examples, we supply Popper with
background knowledge: predicates to use as building blocks while learning the
incompletability predicate. For instance, the predicate square specifies the
number of triangles in a particular square. To illustrate, square(c1, 1, [e1,
e3, e4, e6]) specifies that the left square, c1, in Figure 1 contains one
triangle and has the list of edges specified. Table 1 lists the background
knowledge.

Predicate | Returns True if
---|---
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$
count(A,B,C) |  the number of occurrences of list $A$ in list $B$ is $C$, that is $|A\cap B|=C$
len(A,B) | the length of list $A$ is $B$
gte(A,B) | $A\geq B$
greaterThan(A,B) | $A>B$
adjacent(A, B) |  last vertex of path $A$ has an edge adjacent to it in square $B$
notAdjacent(A,B) |  last vertex of path $A$ does not have an edge adjacent to it in square $B$
one(A), two(A), three(A) |  $A$ is $1$, $2$ or $3$ respectively.
Table 1: Background knowledge given to Popper.

The background knowledge, a bias file controlling Popper’s operation, and the
training examples for a single puzzle instance $p$ are given as inputs to
Popper. We direct Popper to learn a predicate $\pi_{p}$ that predicts
incompletability separately for every constraint in $p$, leveraging
decomposition we introduced earlier. We use $\pi_{p}$ to compute $\pi$ in
Algorithm 1.

###  4.2 Filtering Predicates

In this section we show our approach for evaluating the learned predicates
from inductive logic programming. Our overall approach is shown in the
pseudocode in Algorithm 2. Since we learn each predicate for a single puzzle
instance we want to find a top performing predicate that generalizes well to
other puzzle instances. Henceforth in this section we use $\pi_{1,\dots,k}$ as
a shorthand for $(\pi_{1},\dots,\pi_{k})$ and generalize
$\operatornamewithlimits{argmax}\limits$ in
$x_{1,\dots,k}\leftarrow\operatornamewithlimits{argmax}\limits\nolimits_{x\in
X}f(x)$ to return the $k$ elements from $X$ that have the $k$ maximum values
of $f$.

input : training problem set $\mathcal{P}_{\text{train}}$, filter problem sets
$\mathcal{P}_{\text{filter}_{1}}$, $\mathcal{P}_{\text{filter}_{2}}$, and
$\mathcal{P}_{\text{filter}_{3}}$, filter numbers $k_{1}$ and $k_{2}$

output : predicate $\pi^{\circ}$

assert :
$|\mathcal{P}_{\text{filter}_{1}}|<|\mathcal{P}_{\text{filter}_{2}}|<|\mathcal{P}_{\text{filter}_{3}}|$
and $|\mathcal{P}_{\text{train}}|>k_{1}>k_{2}$

1

2foreach  _$p\in\mathcal{P}_{\text{train}}$_ do

3 $\pi_{p}\leftarrow\textit{Popper}(p)$

4

5

6$\pi_{1,\dots,k_{1}}\leftarrow\operatornamewithlimits{argmax}\limits_{\\{\pi_{p}\;\mid\;p\in\mathcal{P}_{\text{train}}\\}}\text{speedup}_{t}(\pi_{p},\mathcal{P}_{\text{filter}_{1}})$

7

8$\pi_{1,\dots,k_{2}}\leftarrow\operatornamewithlimits{argmax}\limits_{\\{\pi_{i}\;\mid\;i\in\\{1,\dots,k_{1}\\}\\}}\text{speedup}_{t}(\pi_{i},\mathcal{P}_{\text{filter}_{2}})$

9

10$\pi^{\circ}\leftarrow\operatornamewithlimits{argmax}\limits_{\\{\pi_{i}\;\mid\;i\in\\{1,\dots,k_{2}\\}\\}}\text{speedup}_{t}(\pi_{i},\mathcal{P}_{\text{filter}_{3}})$

11

12return $\pi^{\circ}$

13

Algorithm 2 Triage for incompletability predicates.

We generate three disjoint sets of distinct puzzle instances: training,
filtering, and testing. Each instance $p$ from the first set,
$\mathcal{P}_{\text{train}}$, is used to generate positive and negative
training examples for Popper. Thus, for each $p\in\mathcal{P}_{\text{train}}$,
Popper learns an incompletability predicate $\pi_{p}$ in line 2.

We have no guarantees on how the predicated learned on single instances will
perform on other instances. Thus we filter generated predicates in the hopes
of finding a predicate that generalizes well. We partition the filtering set
into three disjoint subsets, $\mathcal{P}_{\text{filter}_{1}}$,
$\mathcal{P}_{\text{filter}_{2}}$, and $\mathcal{P}_{\text{filter}_{3}}$ such
that
$|\mathcal{P}_{\text{filter}_{1}}|<|\mathcal{P}_{\text{filter}_{2}}|<|\mathcal{P}_{\text{filter}_{3}}|$
to implement our version of the triage used by [5] (bulitko2021fast).

We begin by evaluating each of the generated incompletability predicates on
$\mathcal{P}_{\text{filter}_{1}}$. We then choose the $k_{1}$ predicates with
the highest time speedup in line 2. We then evaluate these $k_{1}$ predicates
on a second, larger set of puzzle instances,
$\mathcal{P}_{\text{filter}_{2}}$. Again we retain the $k_{2}$ predicates with
the highest time speedup in line 2.

Finally, we evaluate the remaining $k_{2}$ predicates on the largest filter
set of puzzles, $\mathcal{P}_{\text{filter}_{3}}$ and the single highest-
speedup predicate $\pi^{\circ}$ is picked in line 2. The predicate
$\pi^{\circ}$ is the sole output of the learning process and constitutes our
machine-learned approximation to $\pi^{*}$ (Equation 3).

Lines 2 through 2 of Algorithm 2 comprise our machine-learning algorithm for
the predicates with the puzzle sets $\mathcal{P}_{\text{train}}$,
$\mathcal{P}_{\text{filter}_{1}}$, $\mathcal{P}_{\text{filter}_{2}}$ and
$\mathcal{P}_{\text{filter}_{3}}$ comprising the data used for machine
learning. The predicate $\pi^{\circ}$ is the sole output of the learning
process.

To measure performance of the learned predicate $\pi^{\circ}$ we use a novel
testing set of puzzle instances, $\mathcal{P}_{\text{test}}$, not seen by the
learning algorithm. On this set we measure
$\text{speedup}_{t}(\pi^{\circ},\mathcal{P}_{\text{test}})$ and
$\text{speedup}_{\mathcal{E}}(\pi^{\circ},\mathcal{P}_{\text{test}})$.

##  5 Empirical Evaluation

In the following sections we describe the puzzle sets and hyperparameters used
in the empirical study. We then present and discuss the results.

###  5.1 Puzzle Sets

As there is no existing repository of triangle puzzle instances we generated
them ourselves. We present our generators in this section with the hope they
will be used by the community to build additional triangle puzzle datasets.

input : puzzle dimensions $m,n$

output : puzzle $p$

1 repeat

2 $p\leftarrow\text{empty puzzle}(m\times n)$

3 $\text{goal}\leftarrow$ random location on peripheral of puzzle

4 $k\leftarrow U(\\{1,\dots,\lfloor\nicefrac{{mn}}{{2}}\rfloor\\})$

5 $S\leftarrow k$ randomly picked squares from the grid

6 foreach  _$s\in S$_ do

7 $q\leftarrow U(\\{1,2,3\\})$

8 put $q$ triangles into square $s$

9

10 $\ell\leftarrow$ Algorithm 1’s solution to $p$

11

12until  _$\ell\neq\emptyset$_

13return _$p$_

14

Algorithm 3 Generate a puzzle instance by placing triangles randomly.

The first generator places triangles randomly on the grid (Algorithm 3). In
line 3 we create an empty $m\times n$ Witness puzzle. We randomly initialize
the goal location to be any vertex that is peripheral to the graph (meaning it
has edge degree less than $4$) such that $v_{\textup{start}}\neq
v_{\textup{goal}}$ in line 3. The starting location, $v_{\textup{start}}$, is
always fixed to be the bottom-left corner.

In lines 3 and 3 we pick the number of squares containing triangles uniformly
randomly between $1$ and half of all squares (in the spirit of the challenge
room maze in the actual game). We then randomly select such squares in the
grid. For each of these squares we uniformly randomly assign between $1$ and
$3$ triangles to it in lines 3 and 3. After generating the puzzle we use
Algorithm 1 with the baseline solver to determine if the puzzle is solvable
(line 3). If it is not, we restart the generation process.

The second puzzle generator (Algorithm 4) starts with a path from the start
vertex to the goal vertex and then populates the empty grid with triangles so
that the path becomes a solution to the puzzle (in the spirit of [2]’s
(blow2011truth) work).

input : puzzle dimensions $m,n$

output : puzzle $p$

1 $p\leftarrow\text{empty puzzle }(m\times n)$

2 $\ell\leftarrow$ random path from start to goal

3 $S^{\prime}\leftarrow$ all squares in $p$ with at least one edge in $\ell$

4 $k\leftarrow U(\\{1,\dots,|S^{\prime}|\\})$

5 $S\leftarrow k\text{ randomly picked squares from }S^{\prime}$

6 foreach  _$s\in S$_ do

7 $q\leftarrow$ count $s$’s edges in $\ell$

8 put $q$ triangles in square $s$

9

return _$p$_

Algorithm 4 Generate a puzzle instance from a path.

Line 4 generates a path from the start to the goal vertices that does not
contain repeating vertices. We then find all squares that have at least one
edge in $\ell$ (line 4) and uniformly randomly sample a number of these
squares (lines 4\- 4). For each of these squares, we add to the puzzle the
number of edges it has in $\ell$ so that $\ell$ is a solution to the puzzle.

###  5.2 Hyper Parameters

To generate a puzzle set we sampled $m$ and $n$ uniformly at random between
$2$ and a maximum size. Note there are fewer possible puzzles of smaller sizes
(such as $2\times 2$) so the overall distribution of puzzle sizes is not
uniform. All puzzles used for triage were generated with Algorithm 3.

We generated $\mathcal{P}_{\text{train}}$ as a puzzle set of $500$ puzzles of
sizes between $2\times 2$ to $4\times 4$. The number of puzzles and the puzzle
sizes were chosen to generate enough training data for learning each predicate
within a few minutes.

We picked the maximum number of variables used when Popper generates
predicates to be $v=7$. Setting $v$ higher creates the potential to learn
better predicates but the learning time increases substantially.

The filter sets contained puzzles of sizes between $2\times 2$ and $5\times 5$
with
$|\mathcal{P}_{\text{filter}_{1}}|=100,|\mathcal{P}_{\text{filter}_{2}}|=500$,
and $|\mathcal{P}_{\text{filter}_{3}}|=2500$. The sizes were chosen to
efficiently filter the initial learned predicates to the top $k_{1}=25$
predicates, then the top $k_{2}=5$ predicates, and finally determine
$\pi^{\circ}$.

The testing set $\mathcal{P}_{\text{test}}$ contained $15000$ puzzles of sizes
between $2\times 2$ and $5\times 5$. The test size included more puzzles to
get less noisy results for
$\text{speedup}_{t}(\pi^{\circ},\mathcal{P}_{\text{test}})$ and
$\text{speedup}_{\mathcal{E}}(\pi^{\circ},\mathcal{P}_{\text{test}})$. The
distribution of testing puzzle sizes is listed in Table 2.

size | instances | expansions | time (sec)
---|---|---|---
$2\times 2$ | $135$ | $11$ | $0.0005$
$2\times 3$ | $1,\\!321$ | $31$ | $0.001$
$2\times 4$ | $1,\\!788$ | $72$ | $0.025$
$3\times 3$ | $1,\\!012$ | $109$ | $0.004$
$2\times 5$ | $1,\\!977$ | $173$ | $0.006$
$3\times 4$ | $2,\\!112$ | $401$ | $0.01$
$3\times 5$ | $2,\\!313$ | $1,\\!533$ | $0.06$
$4\times 4$ | $1,\\!137$ | $2,\\!397$ | $0.09$
$4\times 5$ | $2,\\!123$ | $1.4\times 10^{4}$ | $0.6$
$5\times 5$ | $1,\\!082$ | $1.4\times 10^{5}$ | $7.6$
Table 2: The $15000$ instances in $\mathcal{P}_{\text{test}}$ by puzzle size. Bucket average number of expansions and wall time for the baseline search with the Python version of $\pi_{\text{baseline}}$ are listed as well. Predicate $\pi^{\circ}(A,B)$ | English Explanation | Simplified Python
---|---|---
square(B,C,D), path(A,E) count(D,E,F), greaterThan(F,C). | Checks local constraints as in $\pi_{\text{baseline}}$ |  if path.edges[square]$\textgreater$puzzle.triangles[square]: incompletable = True
square(B,D,C), path(A,E), count(E,C,F),notAdjacent(A,B), three(D), one(F). |  Path head is not adjacent to square, the number of triangles is $3$, and the current intersections is $1$ |  if path.head is not adjacent to square and puzzle.triangles[square]=3 and path.edges[square]=1: incompletable=True
Same except two(F). | Same except current intersections $2$ | Same except path.edges[square]=2
Table 3: Output of Algorithm 2: the predicate $\pi^{\circ}$. On the left, the
predicate is shown in Prolog, in the middle, an English explanation
demonstrating readability of the predicate, and on the right pseudocode in
Python implementing the predicate.

###  5.3 Learned Predicate: Going beyond Human Knowledge

Learned predicates progress through triage based on how much time speedup they
offer beyond the baseline predicate.

To study effects of injecting human knowledge we experimented with using two
different versions of A*. In the first case, we ran A* with the learned
predicate exactly as described previously in Algorithm 1 and Section 4.1. Thus
it did not use pruning with human-implemented $\pi_{\text{baseline}}$.

The second version of A* did use human-implemented $\pi_{\text{baseline}}$ to
prune all partial paths which violated local constraints (i.e., paths on which
$\pi_{\text{baseline}}$ returned True). Those paths were never put on the open
list.

With the first version of A* used for filtering, Algorithm 2 returned the
predicate shown in Table 3 as $\pi^{\circ}$; its value computed as a
disjunction of the three lines. Using the second version of A* used for
filtering, our Algorithm returned the same predicate but without the first
line.

Interestingly the first line of Table 3 is _equivalent_ to
$\pi_{\textup{baseline}}$ as it performs local constraint checking by
returning True when path $A$ shares more edges with square $B$ than $B$’s
triangle constraint allows. This means that without any prior knowledge of
completability (the first version of A*), our approach automatically learned a
predicate that captures human knowledge about solving Witness triangle
puzzles.

The remaining two lines of the predicate in Table 3 offer useful _additions_
to what the first line (i.e., $\pi_{\textup{baseline}}$) checks. They capture
the idea that if a partial path leaves a three-triangle constraint square’s
edges without including enough of them, the path can never return there
because doing so would require visiting one of the square’s vertices twice.

Thus the learning algorithm was flexible with respect to the human knowledge
given to it. When the local constraint checking and pruning was included in A*
the learned predicate had only additional knowledge (i.e., the second and
third lines in the table) in it. Conversely, when the version of A* used for
filtering lacked human knowledge the algorithm included it in the learned
predicate.

The flexibility has a simple mechanism: computing each line of the predicate
takes time and our triage process avoids including elements in the predicate
that offer insufficient speedup relative to the time they take to compute. In
this particular case the first predicate line in the table adds $26\%$ to the
predicate run time on $\mathcal{P}_{\text{filter}_{2}}$ without delivering any
benefits when it duplicates local constraint checking.

Note that while the table lists our learned predicate $\pi^{\circ}$ in Prolog
it can be ported to another language in a straightforward fashion. In our
experiments we re-implemented $\pi^{\circ}$ in Python in which our A* was
implemented. This allowed us to call $\pi^{\circ}$ from A* without invoking
Prolog, improving A* performance substantially.

To find the initial set of learned predicates, running Popper on $500$ puzzle
instances in $\mathcal{P}_{\text{train}}$ produced $489$ predicates with $11$
runs not finding a solution in the approximate one-hour time limit. On each of
the successful runs, Popper took an average of eight minutes, with a range of
$[0.15,60.1]$ minutes. This large range reflects the difference between
learning predicates for smaller puzzles which have fewer examples to learn
from and larger puzzles that have many examples to learn from.

###  5.4 Learned Predicate: Verifiability

The fact that the learned predicate is a binary function with only two values,
True and False, affords us an opportunity to use it for pruning incompletable
partial paths instead of merely putting them at the end of the open list. The
pruning speeds up the search relative to sorting because it never puts such
paths on the open list but it also carries the risk of pruning a prefix to the
only solution by mistake. Doing so would render A* incomplete on that puzzle
instance.

A partial path is pruned when $\pi$ returns True on it. Thus if the predicate
has no false positive (i.e., never returns True on a prefix of a solution)
then such $\pi$ preserves completeness of A*. The fact that the learned
predicate $\pi^{\circ}$ is human-readable allowed us to prove the following
theorem.

######  Theorem 1.

The learned predicate $\pi^{\circ}$ in Table 3 has no false positives (i.e, it
never predicts that a solution prefix is incompletable).

###### Proof.

Since $\pi^{\circ}$ consist of a disjunction of the three rows in Table 3, it
suffices to prove that each individual row yields no false positives. The
first line is equivalent to $\pi_{\text{baseline}}$ which we showed had no
false positives in Section 2.3.

In the second and third row, by square(B,D,C) and three(D) we know that B is a
square containing a three-triangle constraint with the list of edges given by
C. Let the vertices by this square be $v_{1},v_{2},v_{3},v_{4}$. By path(A,E)
we know that A is a path across a list of edges E. Furthermore by
notAdjacent(A,B) we know that the head of path A (a vertex in the graph) is
not adjacent to any edge in square B. Therefore, the head of the path is not
$v_{1}$, $v_{2}$, $v_{3}$ or $v_{4}$.

In the second row, given count(E, C, F) and one(F) we know that path A (with
edges in E) and square B (with edges in C) share only a single edge in common.
Without loss of generality, let vertices $v_{1}$ and $v_{2}$ be the two
vertices along this shared edge. An example of this situation is shown by the
red dotted line in Figure 3.

Figure 3: Portion of a Witness puzzle with a partial path for the one(F) case
drawn in a red dotted line and for the two(F) case drawn in a blue dashed
line.

Assume for the sake of contradiction that path A is completable. Hence square
B’s triangle constraint must be satisfied so path A needs to be extended to
include two more of square B’s edges. However, every pair of the three
remaining edges in square B contain an edge that either has $v_{1}$ or $v_{2}$
as one of its vertices. Thus this extension of A would need to visit the same
vertex twice, which violates rule (ii) of Witness puzzles. Thus, path A is
incompletable.

The proof for the third row is similar, however, we are given count(E, C, F)
and two(F) instead, so we know that path A and square B share two edges in
common in this case. These two edges must include at least three vertices in
square B. Without loss of generality, assume these vertices are $v_{1}$,
$v_{4}$, and $v_{3}$. An example of this situation is shown by the blue dashed
line in Figure 3.

Assume for the sake of contradiction that path A is completable, so an
extension of A needs to include one more of square B’s edges. However, any
additional edge will include at least one of the vertices $v_{1}$, $v_{4}$,
and $v_{3}$, so this extension of A would need to visit the same vertex twice
which violates rule (ii) of Witness puzzles. Hence path A is incompletable.

Since we have shown each line has no false positives, $\pi^{\circ}$ has no
false positives. ∎

###  5.5 Learned Predicate: Search Acceleration

Since both the human-designed $\pi_{\text{baseline}}$ and the machine-learned
$\pi^{\circ}$ have no false positives we will be using them for pruning of
partial paths. On the test set $\mathcal{P}_{\text{test}}$, we thus compared
two Python implementations of Algorithm 1 with $\pi^{\circ}$ and
$\pi_{\text{baseline}}$. The predicate $\pi^{\circ}$ had the following
speedups:

$\displaystyle\text{speedup}_{t}(\pi^{\circ},\mathcal{P}_{\text{test}})$
$\displaystyle=$ $\displaystyle 6.12,$ (4)
$\displaystyle\text{speedup}_{\mathcal{E}}(\pi^{\circ},\mathcal{P}_{\text{test}})$
$\displaystyle=$ $\displaystyle 6.27.$ (5)

Notice that the expansion speedup is slightly higher than the time speedup
since invoking the more complex $\pi^{\circ}$ within A* takes more time than
invoking the simpler $\pi_{\text{baseline}}$.

The range of time speedups was $[0.37,1136]$ and of expansion speedups was
$[1,1447]$. Thus A* with predicate $\pi^{\circ}$ never expanded more nodes
than the baseline on any problem in $\mathcal{P}_{\text{test}}$. On problems
where the same number of nodes was expanded, $\pi^{\circ}$ had to do more
computation. This led to $\pi^{\circ}$ being slower than the baseline $32.5\%$
of the time. However, $\pi^{\circ}$ also has the potential to significantly
speed up search, and on one instance had a time speedup of $1136$. We analyze
this instance in Appendix A.

The speedup afforded by using the predicate appears to increase with the
puzzle size. We partitioned the $15000$ instances from
$\mathcal{P}_{\text{test}}$ into ten buckets based on size (Table 2). Figure 4
shows time and expansion speedups for the instances in each bucket, plotted as
a function of the number of squares in the bucket’s puzzles.

Figure 4: Time and expansion speedup of $\pi^{\circ}$ on
$\mathcal{P}_{\text{test}}$.

###  5.6 Solving Large Puzzle Instances

Given the speedups of these predicate we investigated how large a puzzle could
be solved using $\pi^{\circ}$ within fixed time and memory limits. We
generated a set of $500$ puzzle instances of each of the following sizes:
$5\times 5$, $5\times 6$, $5\times 7$, $5\times 8$, $6\times 6$, $6\times 7$,
$6\times 8$, $7\times 7$, $7\times 8$, and $8\times 8$ using Algorithm 4.
222We chose it over Algorithm 3 as it can generate larger puzzle instances
faster, not needing to verify existence of a solution.

Figure 5: Rounded percentage of puzzle instances solved by baseline search
(left) and with $\pi^{\circ}$ (right).

We then ran A* using $\pi^{\circ}$ and $\pi_{\text{baseline}}$ for pruning on
these large puzzles. We recorded the number of puzzle instances solved under a
time limit of $\\{1,5,15,30\\}$ minutes and memory limit of $128$ Gbytes
(Figure 5).

The puzzle instances were challenging for the baseline search; only the two
smallest puzzles ($25$ and $30$ squares) could all be solved in under $30$
minutes. The learned predicate, $\pi^{\circ}$, sped up A* enough to allow for
solving more puzzles.

A* using $\pi^{\circ}$ solved all puzzles up to $36$ squares as well as over
half of the largest sized puzzles ($64$ squares). Furthermore, A* with
$\pi^{\circ}$ given a time limit of $5$ minutes solves $83.9\%$ of puzzles
which is more than the $83.1\%$ our baseline solver solves given a time limit
of $30$ minutes. Also A* with $\pi^{\circ}$ given a time limit of $1$ minute
solves $74.4\%$ of puzzles which is more than the $74.0\%$ our baseline solves
in $5$ minutes. This shows A* with $\pi^{\circ}$ solves more puzzles in less
time than the baseline.

##  6 Open Questions and Future Work

We have demonstrated how an off-the-shelf ILP system with a triage-based
filtering is able to learn a predicate that substantially speeds up a baseline
search algorithm in solving Witness puzzles.

Future work will compare our approach to other types of program synthesis such
as bottom-up search or genetic algorithms. It will also explore automatically
converting predicates from Prolog to Python to gain performance benefits
without the effort of a manual re-implementation.

We used the learned predicate for safe pruning because we were able to prove
its lack of false positives. Other learned predicates may achieve an even
higher speedup but have an occasional false positive. To use such a predicate
for pruning while preserving A* completeness one can run A* with the predicate
in parallel with A* with $\pi^{\circ}$. Both versions of A* are stopped as
soon as one of them finds a solution. In this way if the predicate in question
prunes out a prefix of the only solution by mistake its A* will not find the
solution. Note the other copy of A* guided by $\pi^{\circ}$ will thereby
preserving completeness of the pair. This is similar in spirit to planning
with a portfolio of planners running in parallel.

Future work will investigate applicability of this approach to other puzzle
types in The Witness beyond triangle puzzles. It will also investigate how the
approach presented in this paper can be used to improve approaches that
automatically compute the difficulty of puzzles [8].

##  7 Conclusions

Searching for solutions to Witness puzzles can be combinatorially difficult.
We presented an automated approach to speeding up A* via machine-learned,
human-readable predicates that predict the incompletability of a partial path.
The human readability can offer insights to both Witness players and puzzle
designers. It also may afford the opportunity to prove that they have no false
positives which in turn allows them to be used to safely prune successor nodes
within A* and preserve completeness. When used for provably safe pruning our
learned predicate accelerated the baseline search by about six times on larger
puzzle instances.

In closing, we hope that our work presented in this paper will encourage other
game AI researchers to add Witness puzzles to their portfolio of game AI
testbeds.

##  8 Acknowledgements

The authors acknowledge the support of the Natural Sciences and Engineering
Research Council of Canada (NSERC), including grant #2020-06502. The authors
also acknowledge the support from Compute Canada, Alberta Innovates and
Alberta Advanced Education. The authors would like to thank Andrew Cropper,
Nathan Sturtevant, Jonathan Schaeffer, and Faisal Abutarab for useful
discussions on the paper.

##  Appendix A Puzzle with a Large Speedup

In this section we show the puzzle instance from our testing set
$P_{\text{test}}$ where $\pi^{\circ}$ sped up A* the most. On this example, A*
with $\pi^{\circ}$ had a time speedup of $1136$ and expansion speedup of
$1447$. The $5\times 5$ puzzle is shown in Figure 6. We will show that
predicate $\pi^{\circ}$ forces A* to have the first eight vertices visited in
a solution to Figure 6 to be $1,2,3,4,5,6,7,8$. This demonstrates how A* with
$\pi^{\circ}$ prunes many partial paths from its search tree.

Figure 6: A $5\times 5$ Witness-type triangle puzzle. The vertices are
numbered to show the partial path that pruning with $\pi^{\circ}$ forces A* to
take. The two vertex markers $\star,\heartsuit$ mark the start and goal
vertices.

Solving this puzzle from the start, we can either move up to vertex $3$ or
right to vertex $1$. Either path intersects the three-triangle square, and
lines two and three of predicate $\pi^{\circ}$ predict that leaving this
square before satisfying the square’s triangle constraint will result in an
incompletable path. There are two possible ways to satisfy the three-triangle
constraint: $3,2,1$ or $1,2,3$. In the first case, we are then forced to move
right from vertex $1$, which would then intersect a one-triangle square twice.
The first line of $\pi^{\circ}$ detects that this is incompletable, and hence
the first sequence of moves must be $1,2,3$.

From vertex $3$, we can only move up to vertex $4$. From vertex $4$ we cannot
move right since then the path will intersect a two-triangle square three
times, which $\pi^{\circ}$ detects is incompletable. Thus we must move up to
vertex $5$ and our partial path so far is $1,2,3,4,5$.

From vertex $5$ we must move either up to vertex $6$ or right to vertex $8$.
In either case we have one edge in our path that is adjacent a three-triangle
square. Predicate $\pi^{\circ}$ predicts that leaving this square without
satisfying the square’s triangle constraint will make the path incompletable.
We have two ways to satisfy the three-triangle constraint: either $6,7,8$ or
$8,7,6$. In the latter case, our partial path would be $1,2,3,4,5,8,7,6$, and
our only move without repeating any vertices would be to move up to the goal.
However, there are still squares with triangle constraints that are not
satisfied so this path is invalid. While $\pi^{\circ}$ will not detect this,
no successor states of this partial path will be added to the open list.
Hence, the former case is the only possibility and the starting sequence of
eight moves is $1,2,3,4,5,6,7,8$.

## References

  * [1] Zachary Abel et al.  “Who witnesses _The Witness_? Finding witnesses in _The Witness_ is hard and sometimes impossible”  In _Theoretical Computer Science_ 839 Elsevier, 2020, pp. 41–102
  * [2] Jonathan Blow  “Truth in Game Design” Presented at Game Developers Conference Europe, 2011
  * [3] Adi Botea and Vadim Bulitko  “Tiered State Expansion in Optimization Crosswords”  In _Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment_ , 2022, pp. 79–86
  * [4] Cameron Browne  “Deductive search for logic puzzles”  In _Proceedings of the IEEE Conference on Computational Inteligence in Games_ , 2013, pp. 1–8
  * [5] Vadim Bulitko, Sergio Poo Hernandez and Levi HS Lelis  “Fast Synthesis of Algebraic Heuristic Functions for Video-game Pathfinding”  In _Proceedings of the IEEE Conference on Games_ , 2021, pp. 1–5
  * [6] Vadim Bulitko, Shuwei Wang, Justin Stevens and Levi HS Lelis  “Portability and Explainability of Synthesized Formula-based Heuristics”  In _Proceedings of the International Symposium on Combinatorial Search_ , 2022, pp. 29–37
  * [7] Eric Butler, Emina Torlak and Zoran Popović  “Synthesizing interpretable strategies for solving puzzle games”  In _Proceedings of the International Conference on the Foundations of Digital Games_ , 2017, pp. 1–10
  * [8] Eugene Chen, Nathan Sturtevant and Adam White  “Computing the Entropy of a Puzzle: Modeling Difficulty, Enjoyment and Learning”  In _Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment_ , 2023
  * [9] Jingwei Chen and Nathan R Sturtevant  “Avoiding Re-expansions in Suboptimal Best-First Search”  In _Proceedings of the International Symposium on Combinatorial Search_ , 2021, pp. 162–163
  * [10] Andrew Cropper, Sebastijan Dumančić, Richard Evans and Stephen H Muggleton  “Inductive logic programming at 30”  In _Machine Learning_ 111 Springer, 2022, pp. 147–172
  * [11] Andrew Cropper and Rolf Morel  “Learning programs by learning from failures”  In _Machine Learning_ 110 Springer, 2021, pp. 801–856
  * [12] Barbara De Kegel and Mads Haahr  “Procedural puzzle generation: A survey”  In _IEEE Transactions on Games_ 12.1, 2019, pp. 21–40
  * [13] P.E. Hart, N.J. Nilsson and B. Raphael  “A formal basis for the heuristic determination of minimum cost paths”  In _IEEE Transactions on Systems Science and Cybernetics_ 4.2, 1968, pp. 100–107
  * [14] Jörg Hoffmann and Bernhard Nebel  “The FF planning system: Fast plan generation through heuristic search”  In _Journal of Artificial Intelligence Research_ 14, 2001, pp. 253–302
  * [15] Hiroaki Iwashita, Jun Kawahara and Shin-ichi Minato  “ZDD-based computation of the number of paths in a graph”  In _Hokkaido University Division of Computer Science TCS Technical Report TCSTR-A-12-60_ , 2012
  * [16] Michal Krajňanskỳ, Jörg Hoffmann, Olivier Buffet and Alan Fern  “Learning pruning rules for heuristic search planning”  In _Proceedings of the European Conference on Artificial Intelligence_ , 2014, pp. 483–488
  * [17] Abhijeet Krishnan and Chris Martens  “Synthesizing Chess Tactics from Player Games”  In _Workshop on Explainable Agency in Artificial Intelligence Workshop, AAAI Conference on Artificial Intelligence_ , 2022
  * [18] Stephen Muggleton  “Inductive logic programming”  In _New generation computing_ 8 Springer, 1991, pp. 295–318
  * [19] Nikoli Co., Ltd  “ _Slitherlink_ ”  Nikoli Co., Ltd, 1989
  * [20] Laurent Orseau and Levi H.. Lelis  “Policy-Guided Heuristic Search with Guarantees”  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , 2021, pp. 12382–12390
  * [21] Silvia Richter and Matthias Westphal  “The LAMA planner: Guiding cost-based anytime planning with landmarks”  In _Journal of Artificial Intelligence Research_ 39, 2010, pp. 127–177
  * [22] Nathan Sturtevant  “HOG2”  In _https://github.com/nathansttt/hog2/tree/PDB-refactor_ GitHub, https://github.com/nathansttt/hog2/tree/PDB-refactor, 2023
  * [23] Adam Summerville et al.  “Procedural content generation via machine learning (PCGML)”  In _IEEE Transactions on Games_ 10.3 IEEE, 2018, pp. 257–270
  * [24] Thekla, Inc.  “ _The Witness_ ”  Thekla, Inc., 2016