# ALPHAZERO-BASED PROOF COST NETWORK TO AID GAME SOLVING

**Ti-Rong Wu[1][∗], Chung-Chin Shih[1,2], Ting Han Wei[3][∗], Meng-Yu Tsai[1], Wei-Yuan Hsu[1], I-Chen Wu[1,2]**

1Department of Computer Science, National Yang Ming Chiao Tung University, Hsinchu, Taiwan
2Research Center for Information Technology Innovation, Academia Sinica, Taiwan
3Department of Computing Science, University of Alberta, Edmonton, Canada
_{kds285, rockmanray}@aigames.nctu.edu.tw, tinghan@ualberta.ca_
_{atuno, in13 13}@aigames.nctu.edu.tw, icwu@cs.nctu.edu.tw_

ABSTRACT

The AlphaZero algorithm learns and plays games without hand-crafted expert
knowledge. However, since its objective is to play well, we hypothesize that a
better objective can be defined for the related but separate task of solving games.
This paper proposes a novel approach to solving problems by modifying the training target of the AlphaZero algorithm, such that it prioritizes solving the game
quickly, rather than winning. We train a Proof Cost Network (PCN), where proof
_cost is a heuristic that estimates the amount of work required to solve problems._
This matches the general concept of the so-called proof number from proof number search, which has been shown to be well-suited for game solving. We propose two specific training targets. The first finds the shortest path to a solution,
while the second estimates the proof cost. We conduct experiments on solving
15x15 Gomoku and 9x9 Killall-Go problems with both MCTS-based and focused
depth-first proof number search solvers. Comparisons between using AlphaZero
networks and PCN as heuristics show that PCN can solve more problems.

1 INTRODUCTION

There are two main goals in the pursuit of strong game-playing agents. The first is to push the
boundaries of artificial intelligence since games can be seen as simplified models of the real world.
The second involves finding game-theoretic values, or outcomes given optimal play, for various
games (van den Herik et al., 2002). These two closely related yet separate goals are commonly
referred to as playing and solving[1] games, respectively. For playing, researchers have found success
in building super-human level game-playing agents for many games, including Go (Silver et al.,
2017; 2016), Chess, Shogi (Silver et al., 2018), and Atari games (Schrittwieser et al., 2020; Mnih
et al., 2015). Achievements for solving include checkers (Schaeffer et al., 2007), Hex up to board
sizes of 9x9 (Pawlewicz & Hayward, 2013; Henderson et al., 2009), Go for board sizes up to 5x6
(van der Werf & Winands, 2009), 15x15 Gomoku (Allis, 1994), among others.

Previously, researchers used hand-crafted heuristics with game-specific knowledge, combined with
search methods such as Monte Carlo tree search (MCTS) (Winands et al., 2008), proof number
search (PNS) (Allis et al., 1994), depth-first proof number search (DFPN) (Nagai, 2002; 1999), and
threat-space search (Allis et al., 1993), to solve problems by massively pruning away unnecessary
branches (Schaeffer et al., 2007; van der Werf et al., 2003; Allis et al., 1996; Allis, 1994). With
the great success of AlphaGo and AlphaZero, there have been attempts to combine neural networks
with previous solvers to further improve game solving. For example, Gao et al. (2017) incorporated
an AlphaGo-like neural network into a state-of-the-art Hex solver to solve 8x8 Hex openings more
quickly, which demonstrated that neural networks can have a positive impact when combined with
previous techniques and heuristics. Meanwhile, McAleer et al. (2018) also trained an AlphaZero
_∗These authors contributed equally._
1A solution to a game is an exhaustive strategy that guarantees the game-theoretic value against all opposing
actions from the game’s initial position (Allis, 1994).


-----

like agent to solve the Rubik’s Cube. In addition, game solving techniques were also shown to be
viable for non-game applications (Kishimoto et al., 2019; Segler et al., 2018).

However, a limitation of using these techniques is that the networks trained with the objective of
strong play may not be well-suited for obtaining game-theoretic values. Since the goal of a strong
player is to play moves that maximize win rates (or the highest confidence for winning), as a heuristic
it often does not choose moves that result in the fewest nodes in the search tree when solving. As an
example, Agostinelli et al. (2019) pointed out that AlphaZero-like systems tend to solve problems
with longer solutions. For games with a singular end state, e.g. Rubik’s cube and n-puzzles, they
proposed an approach that trains a cost-to-go value function that approximates the cost of finding the
shortest-path solution, which can be viewed as a kind of prioritized-sweeping (Moore & Atkeson,
1993) algorithm, starting from the end state (goal). However, singular end states are often only
exploitable for puzzles. Indeed, in two-player zero-sum games such as Go, Hex, Gomoku, Connect6,
and many others, the game may end in too many configurations to enumerate practically. This paper
presents a novel approach to solving these problems, while still tending to choose moves that lead
to the fastest solutions.

In our approach, we propose a new heuristic, referred to as the proof cost. We give two concrete
examples of how proof cost can be designed. The first acts as a “shortest path” heuristic to a proof,
while the second predicts solution tree sizes. Then, we use AlphaZero training to approximate this
heuristic. The resulting network is referred to as the Proof Cost Network (PCN), which can be used
as a heuristic with any AND/OR tree search algorithm to improve solving efficiency.

Experiments were conducted on 15x15 Gomoku and 9x9 Killall-Go problems. The results show that
PCN outperforms AlphaZero when used as a heuristic with MCTS-based and Focused DFPN (Gao
et al., 2017; Henderson et al., 2009) solvers, which are both commonly used to solve games.

2 BACKGROUND

2.1 THE GAME-THEORETIC VALUE AND PROOF TREES

For a one or two-player game, the game-theoretic value of a game state is the best outcome that can
be obtained by all players if they play optimally. In this paper, we focus on two-player games,
and simplify the outcome to only include win/loss; draws are considered losses for both players[2]. A game state is said to be solved when the game-theoretic value for the state is obtained,
and proved/disproved if the player to play for the state has a winning/losing outcome. In a proof,
the winning player needs to ensure a winning response to all possible actions by the losing player.
A proof tree (Pijls & de Bruin, 2001; Stockman, 1979) is an AND-OR search tree representing a
strategy of answering actions such that (a) all terminal nodes are wins, (b) the winning player (the
OR-player) contains at least one winning action, (c) all losing player (the AND-player) actions are
enumerated, and the OR-player needs to have winning responses to each AND-player action. A
_disproof tree is the dual case of the above (with win/loss and AND/OR reversed); a solution tree is_
a general term used to describe both proofs and disproofs.

2.2 MONTE CARLO TREE SEARCH

Monte Carlo tree search (MCTS) (Coulom, 2006; Kocsis & Szepesv´ari, 2006) is a heuristic best-first
search algorithm that iteratively repeats the following four phases: selection, expansion, evaluation,
and backpropagation. In the selection phase, starting from the root node, the algorithm chooses a
child node according to a specified selection criterion until a leaf node is reached. Given a state s
during selection, AlphaZero selects an action a[∗] by the PUCT equation (Silver et al., 2018; Rosin,
2011):

_b_ _[N]_ [(][s, b][)]

_a[∗]_ = arg max _Q(s, a) + cP UCT_ _P_ (s, a) _,_ (1)
_a_ ( _×_ _×_ pP1 + N (s, a) )

where Q(s, a) = W (s, a)/N (s, a) is the estimated mean win rate, N (s, a) is the number of times a
is selected at s, W (s, a) is the number of wins, cP UCT is a weight for exploration, and P (s, a) is a

2We can solve the same problem twice, once for each player; if both outcomes are losses, then we know the
outcome is a draw.


-----

prior knowledge heuristic. The above selected leaf then expands all children which are added to the
tree. The leaf node is then evaluated. In AlphaZero, a two-head network is trained such that it outputs
a policy p(s, a), and a value v(s). The policy is a distribution that estimates how likely each child of
_s will be visited during selection; p(s, a) can then be used as P_ (s, a) in eq. 1. The scalar v(s) is an
estimate for the game-theoretic value of s. During backpropagation we move back up the selection
sequence and Q(si, ai) is updated for all ancestors si. While originally designed for playing, MCTS
can also be used to solve games with AND-OR Boolean backpropagation. MCTS has been used to
solve games and problems for Lines of Action (Winands et al., 2010; 2008), Connect4, Seki in the
game of Go (Cazenave & Saffidine, 2010), and Connect6 (Wei et al., 2015).

2.3 PROOF NUMBER SEARCH

Proof number search (PNS) (Allis et al., 1994) is a best-first search algorithm that was designed
specifically for solving games. Each node is associated with two numbers: the proof number (PN)
and the disproof number (DN), which are heuristics that represent the minimum required number of
leaf nodes that need to be expanded to prove and disprove the node respectively. PNS largely follows
the same four phases as in MCTS. What is called the most-proving node (MPN) is selected during
the selection phase. Specifically, the child with the lowest PN at each OR node, or the lowest DN
at each AND node is selected; the resulting leaf node is then the MPN that needs to be evaluated.
Following the definition of the PN/DN, PNS therefore builds the solution tree by expanding and
evaluating the least number of nodes. There are many PNS variants, one of which is the so-called
depth-first proof number search (DFPN) (Nagai, 2002; 1999), which addresses the large memory
requirements for large searches.

PNS was originally designed such that all newly expanded nodes initialize PN/DN values to 1/1. To
improve the heuristic, domain knowledge can be used to initialize PN/DN values differently, which
speeds up the search for a solution (Winands & Schadd, 2010; Wu et al., 2010; Saito et al., 2006;
Kishimoto & M¨uller, 2005; Allis, 1994). In addition, Henderson (2010) proposed Focused DFPN
(FDFPN), which uses heuristics to direct the search toward promising solutions with a technique that
is often referred to as progressive widening. Specifically, progressive widening involves prioritizing
search on only a portion of all possible moves. The branching factor b at an internal search node
is dynamically adjusted by b = bbase + ⌈µ × |blivechildren|⌉, where bbase is set to 1, blivechildren
is the number of all yet unsolved children of the node, and µ is a weighting constant. With an
accurate heuristic, FDFPN can solve problems while searching fewer nodes than unmodified DFPN.
Further, Gao et al. (2017) proposed FDFPN-CNN by incorporating the policy and value outputs
from an AlphaGo-based agent as heuristics to solve 8x8 Hex. Namely, the policy was used for move
ordering and the value was used to control the branching factor by b = bbase+ _f_ (s) _blivechildren_
_⌈_ _×|_ _|⌉_
and f (s) = min{µ, 1 + v(s)}.

2.4 THE ALPHAZERO ALGORITHM

AlphaZero (Silver et al., 2018) is a general reinforcement learning algorithm that can achieve superhuman level playing strength for games without requiring any expert domain knowledge. The training routine consists of two phases: self-play and optimization. In a nutshell, a two-headed neural
network that outputs a policy distribution p and a value scalar v is periodically optimized with data
that is collected via self-play. Self-play games are generated by running a set number of MCTS
simulations with the most recently optimized neural network. In the optimization phase, random
positions are sampled from the latest self-play games, where the network is optimized by the following loss function:

_L = (z −_ _v)[2]_ _−_ _π[T]_ log p + c∥θ∥[2], (2)

where z is the ground truth outcome of the game for that position, π is the MCTS search distribution,
_c is an L2 regularization weight, and θ represents the network parameters._


-----

3 OUR APPROACH

3.1 ESTIMATING PROOF TREE SIZES

We first examine the size of a proof tree, i.e. the number of nodes that need to be searched to obtain
a proof for a player of interest from a given state. Since we do not know the game-theoretic outcome
of the game before finding a solution, either player can be designated the player of interest. Given
limited time and resources, it is almost always preferable to prove a given state by traversing as
small a search tree as possible, where the ideal case is called a minimum proof tree. A minimum
proof tree, say rooted at a node representing state s, is defined as a proof tree containing the least
possible number of tree nodes, denoted by n(s), for the player of interest at s to win. m(s) is defined
likewise, but for the opposite player. With no loss of generality, we focus on n(s) for the remainder
of this section, unless otherwise specified.

By definition, n(s) is a perfect measures of resource efficiency for proving s. Unfortunately, in
order to derive the true value of n(s), we would need to traverse the game tree starting at s by
induction as follows. Suppose sT are terminal states. Then, n(sT ) = 1 if the player to play at
_s is winning, and n(sT ) = ∞_ otherwise. Suppose sAND are non-terminal AND nodes. Then,
_n(sAND) = 1 +_ _si_ _[n][(][s][i][)][, where][ s][i][ are the children of][ s][AND][. Suppose][ s][OR][ are non-terminal OR]_

nodes. Then, n(sOR) = 1 + minsi n(si) for all children si. To obtain minsi n(si), we would need
to search all children of non-terminal OR nodes; combined with having to search all children of

[P]

non-terminal AND nodes, the conclusion is that the entire tree rooted at s will have to be searched.

In practice, even if we cannot obtain the true value, a sufficiently accurate heuristic estimate of
_n(si), which we denote as ¯n(si), can be useful in guiding the search. In the ideal case, ¯n(si)_
perfectly preserves the order of n(si), i.e. ¯n(s1) _n¯(s2) if and only if n(s1)_ _n(s2). Then, for_
_≤_ _≤_
_sOR, we would only have to compute the heuristic ¯n(si) for all children si, then choose to search the_
child with the smallest value. The difficulty, as is always the case in heuristic search, is in designing
such a heuristic so that ¯n(si) preserves the order of n(si) as best as possible.

While prioritization according to ¯n is straightforward for OR nodes, the AND node case requires
some more thought. Theoretically, in this case ¯n should have no effect on priority since all children need to be searched for AND nodes. In practice, with an imperfect heuristic, the order in
which children of AND nodes are searched impacts how quickly OR node prioritization mistakes
are corrected.

To obtain reasonably accurate heuristics ¯n and ¯m, we take advantage of AlphaZero’s ability to
converge on accurate positional value estimates through self-play, and modify the algorithm so that
it approximates n and m instead. We describe the details on how the training targets are defined in
subsection 3.2 and the training loop in subsection 3.3. The heuristics ¯n and ¯m are then used in a
modified PNS algorithm, which we describe in subsection 3.4.

3.2 THE PROOF TREE SIZE ESTIMATE AS A TRAINING TARGET

Let us assume that s is the root, is an OR node, has b children, s1, ..., sb, and that all ¯n(si) are
available with ¯n(s1) _n¯(s2)_ _..._ _n¯(sb). We propose that ¯n(s) := ¯n(s1), similar to the way_
_≤_ _≤_ _≤_
PNs are calculated for OR nodes in PNS. Since ¯n(s) grows exponentially, the +1 term’s impact is
overall negligible. Moreover, the omission of this term preserves the order of ¯n among all children,
so it can be safely omitted for simplicity. As described in subsection 3.1, the OR-player should
prioritize searching s1, or those si with small i. The dual case where the root is an AND node is
_n¯(s) :=_ _i=1_ _n[¯](si), where si are the children of s, following PNs for AND nodes in PNS. In order_
to design the heuristic ¯n(s) such that it preserves the ordering of n(s) as accurately as possible, a
naive way as describe in the previous subsection would be to perform brute force search to obtain

[P][b]
all the ground truths for machine learning. However, it is apparent that this is not feasible given the
exponential tree size growth.

Instead, we use a modified MCTS in the self-play phase of AlphaZero to collect game episodes,
which are then used to learn ¯n(s).

1. For the terminal state, the ground truths are set to 1 if the root player wins, and ∞ otherwise.
2. For all non-terminal OR nodes st and its child st+1 in the episode, ¯n(st) is set to ¯n(st+1).


-----

|b s 0 0|s 1|b b 1 s 2 2|s 3|b 3 s 4|
|---|---|---|---|---|


_n¯(s0) = b0_ _b2_
_×_


_n¯(s1) = b2_


_n¯(s2) = b2_


_n¯(s3) = 1_


_n¯(s4) = 1_


Figure 1: An illustration for different
_b._


Figure 2: Estimate ¯n(s) from an episode of a game.


3. For all non-terminal AND nodes st and its child st+1 in the episode, ¯n(st) is set to b ×
_n¯(st+1), where b is the number of children for st._

We use b ¯n(st+1) for AND nodes as the training target since we do not know the values for all
_×_
other siblings of st+1 (recall that self-play generates single episodes), which makes it difficult to
obtain _i=1_ _n[¯](si). Effectively, we are assuming that the costs for all of st’s children are equal to_
_st+1’s. There are domain-specific improvements for many games to improve the accuracy of this_
estimate. As an example, the Gomoku position illustrated in Fig. 1 contains what is called a “four

[P][b]
threat” (4T) for Black. We know that Black will achieve a 5-in-a-row and win if White does not
block at A, so we can effectively reduce b to 1.

To differentiate the case where we use heuristics to reduce b like in the 4T example above, we will
use bheur to specify the number of valid children when heuristics are used, and bmax for the setting
where we use the entire action space. We illustrate three examples for b in 15x15 Gomoku. First,
_bmax is always 225 since that is the maximum number of moves for the 15x15 board; next, if we use_
the game independent heuristic where we only consider legal moves, we set bheur to the number of
empty grids left on the board; last, if a 4T exists, as in Fig. 1, bheur = 1.

An example episode is illustrated in Fig. 2. It starts from s0 and ends at s4 with a win (achieving
the goal) for the OR-player; b0 to b3 are the branching factors of s0 to s3 respectively (with no loss
of generality to whether bheur or bmax is used). The heuristic function ¯n(s) for the states in the
episode are set to the following: ¯n(s3) = ¯n(s4) = 1, ¯n(s1) = ¯n(s2) = b2 ¯n(s3) = b2, and
_n¯(s0) = b0_ ¯n(s1) = b0 _b2. Based on this calculation, we can see that every move counting ×_
backwards from the terminal node increases the proof cost by a factor of × _×_ _b equally when using bmax._
Thus, the resulting heuristic can be seen as a measure of how many moves are left until the solution,
so it can be useful for finding the shortest path to the solution.

There are some similarities and differences between our heuristic and the concept of PNs in PNS.
First, PN/DN are dynamic quantities meant to change as PNS progresses and new nodes are expanded and evaluated. In contrast, ¯n(s) is a static estimate of an oracle number that represents the
minimum proof tree size. More specifically, rather than the PN value, ¯n(s) estimates PN plus the
current tree size of s.

Second, PNS makes no assumptions as to which player is more likely to win, and so both PN/DN are
used. Since we already have self-play episodes to train from, we add an auxiliary target ¯m(s), which
is conceptually similar to DNs. In Fig. 2, ¯m(s0) = ¯m(s1) = ¯m(s2) = ¯m(s3) = ¯m(s4) = .
_∞_

Last, in PNS, the search arrives at the MPN by choosing the minimum PN at OR nodes, and the
minimum DN at AND nodes. In our method, while OR nodes behave similarly in that the smallest
_n¯ value is chosen, for AND nodes, we prioritize moves which have the maximum ¯n value. The OR_
node estimate is most accurate when the OR-player chooses the move with the lowest ¯n(s) value
because n(s) = 1 + min n(si). To leverage the AlphaZero algorithm, where the two players’ goals
run counter to each other, the AND-player behavior should be designed such that it tries its best to
oppose the OR-player, which in this case means it should pick the largest ¯n. Intuitively, the ORplayer will try to prove a win as quickly as possible, while the AND-player will delay as much as it
can. It is important to stress that this difference only affects how the heuristic network is trained, not
how search algorithms work. In other words, the choice of the maximum ¯n value for AND nodes is
used only in the self-play phase described in subsection 2.4 when training the heuristic network.

3.3 TRAINING THE PROOF COST NETWORK WITH ALPHAZERO

We train the Proof Cost Network (PCN) fθ(s) = (p, vn, vm), with parameters θ, such that it predicts
the policy distribution p, and the values vn and vm, corresponding to the proof cost ¯n(s) and auxil

-----

iary ¯m(s) for the state s. Intuitively, for p, moves with higher probabilities lead to faster solutions
for s, either proof or disproof. Our method replaces the AlphaZero v(s) output, which estimate the
win rate (or outcome of the game z), with vn(s) and vm(s), which estimate ¯n(s) and the auxiliary
target ¯m(s). In practice, since ¯n(s) grows exponentially the closer s is to the root, we replace ¯n(s)
with the surrogate ln(s), where ln(s) = log(¯n(s)), likewise with ¯m(s).

With the single-sided proof cost heuristic ¯n, our method tends to perform stronger when we designate a specific player as the OR-player and attempt a proof (as opposed to solving problems without
any assumptions as to the winner/loser). Thus, we need to first decide which are the AND/ORplayers, e.g. knowing that Black is proven to be the winner for 15x15 Gomoku, we set Black as
the OR-players. In the self-play phase, ideally, the OR-player should select arg minai ¯n(si) among
all candidate moves ai which lead to si. Intuitively this motivates the self-play agent to solve s
as quickly as possible. Meanwhile, the AND-player should select arg maxai ¯n(si) to prevent the
OR-player from solving the game quickly, as described in subsection 3.2.

To implement this behavior into the MCTS process for move selection during self-play, we make the
following changes. In the MCTS selection phase, we still follow eq. 1, but now Q(s, a) is a moving
average of vn(s), representing the estimated overall mean cost of solving s with the action a. Since
_Q(s, a) is not limited to [−1, 1], we calculate_ _Q[¯](s, a) by normalizing Q(s, a) with the following_
equation (similar to Schrittwieser et al. (2020)):

_Q¯(s, a) = 2_ _Q(s, a) −_ mins,a∈T ree Q(s, a) (3)
_×_ maxs,a _T ree Q(s, a)_ mins,a _T ree Q(s, a)_

_∈_ _−_ _∈_ _[−]_ [1][.]

Lastly, to motivate the OR/AND-player to choose small/large values of ¯n, we simply flip the value
to −Q[¯](s, a) for the OR-player.

During AlphaZero optimization, we randomly sample the self-play games and calculate ¯n and ¯m as
described in subsection 3.2, then convert them to ln and lm accordingly. The network is optimized
by a modified version of eq. 2, as follows:

_L = φ(vn)[T]_ log ln + φ(vm)[T] log lm − _π[T]_ log p + c∥θ∥[2], (4)
where φ is a transformation function that changes scalar values to categorical representations (Schrittwieser et al., 2020).

3.4 FOCUSED DFPN WITH PROOF COST NETWORK

In this subsection, we present a method that incorporates PCN into the FDFPN solver (Henderson
et al., 2009), called FDFPN-PCN. With the PCN, since the value outputs vn and vm are not scalars
between [−1, 1], we cannot directly apply them as heuristics like FDFPN-CNN (Gao et al., 2017),
described in subsection 2.3.

We propose a separate method based on FDFPN and FDFPN-CNN that is able to use the PCN as
a heuristic in the FDFPN solver. The fundamental search behaves just as DFPN would, including PN/DN calculation and the MPN selection mechanism, with two differences. First, we follow
FDFPN-CNN where the policy output serves as move ordering, and FDFPN where the branching
factor is limited by a parameter µ. Second, since vn and vm take inspiration from PN/DN, we can
initialize PN/DN values with the PCN as follows. Let us assume we are expanding state s, at which
point we will call fθ(s). A naive way would be to set PN = vn(s) and DN = vm(s) directly. The
problem is that we do not have vn(si) and vm(si) for every expanded child. Additionally, calling
_fθ(si) for all si slows the entire search down. To conserve time, we initialize the PN/DN of si, then_
calculate the PN/DN of s with its children’s values. If s is an OR node, we set PN = vn(s) and
DN = vm(s)/b for all si, where b is the number of children for s. On the other hand, if s is an AND
node, we set PN = vn(s)/b and DN = vm(s) for all si. This way, the PN/DN of s will then be
_vn(s) and vm(s), respectively._

4 EXPERIMENTS

4.1 TRAINING SETTINGS

All experiments were performed by solving 15x15 Gomoku and 9x9 Killall-Go problems. We use
two different solvers, one MCTS and the other FDFPN. The MCTS solver is an AlphaZero player


-----

with AND/OR tree logic to propagate win/loss information. The FDFPN solver follows the mechanism described in 3.4. Both solvers make use of transposition tables (Nelson, 1985) to conserve
evaluation costs when identical positions are encountered during search[3].

For each experiment, we focus on comparing the number of solved problems by using different
_networks as heuristics on the same solvers. There are four network configurations: (1) no network,_
(2) α0 (AlphaZero), (3) PCN-bmax, and (4) PCN-bheur. For fairness, we use the same training
settings for each network configuration, described as follows. We run 400 MCTS simulations for
each move during self-play, for a total of 1,500,000 games, and the network is optimized every
5,000 games. The network contains 5 residual blocks with 64 filters, is optimized by SGD with
0.9 for momentum, 1e-4 for weight decay, and a fixed learning rate of 0.02. We use 1080Ti GPUs
for training, where the network is implemented with PyTorch (Paszke et al., 2019). Each 15x15
Gomoku training takes about 1,000 GPU-Hours, and for 9x9 Killall-Go, about 1,500 GPU-Hours.
For simplicity, we select the last snapshot model for each network in our experiments.

Additional detailed settings are as follows. In 15x15 Gomoku, the network input has 4 channels,
including black and white stones in the current position, and two channels representing the turn
color. The α for Dirichlet noise is set to 0.05. The maximum value (∞), used to set training targets,
is set to 1600. There are two variations for 15x15 Gomoku: (1) NDK: no domain knowledge is
provided, and (2) 4T: uses the four threat heuristic. For the NDK variation, all legal moves are
considered in the solver; bmax = 225, and bheur is the number of legal moves. For the 4T variation
in Gomoku, whenever a 4T occurs, the solver will only consider blocking[4]; bmax = 225; bheur = 1
with a 4T and is the number of legal moves else wise. Note that bmax and bheur are not “branching
factors” for the solver, but hyperparameters that define the training labels for ¯n and ¯m.

9x9 Killall-Go (Cauwet et al., 2015) is similar to the game of Go except the following additional
rules. Black plays four stones first on the board as shown in Fig. 4a, then White and Black play normally, as in standard Go. White wins if any white stones becomes unconditionally alive, otherwise
Black wins. Namely, Black wins if and only if there are no white stones on the board at the end of
the game. The network input for 9x9 Killall-Go has 18 channels, including black and white stones
for the last 8 positions, and two channels representing the turn color. The α for Dirichlet noise is set
to 0.2. The maximum value (∞) is set to 500. In 9x9 Killall-Go, we implement two heuristics for
the solver to help the game end quickly; first is Benson’s algorithm (Benson, 1976) which detects
unconditional life, which we use to end the game immediately if White achieves unconditional life
anywhere on the board[5]; second, we prohibit players to fill their own true eyes. There are also two
variations for Go, one assuming White is the OR-player, and the other Black; recall that vn is the
proof cost estimate for the OR-player. For both variations, bmax is set to 82 (9 × 9 + 1 for passing),
and bheur is set to the number of legal moves excluding filling in one’s own eye.

4.2 SOLVING 15X15 GOMOKU PROBLEMS WITH MCTS-BASED SOLVER

A set of 77 problems are generated automatically for the experiment, detailed in Appendix B. The
results for the number of solved problems within 30 minutes are shown in Table 1. We list the node
counts in Appendix C. From the table, when no domain knowledge is provided for 15x15 Gomoku,
both PCN-bmax and PCN-bheur outperform α0, with PCN-bmax being better than PCN-bheur.

No Network _α0_ PCN-bmax PCN-bheur

15x15 Gomoku (NDK) 1 / 77 23 / 77 **43 / 77** 38 / 77
15x15 Gomoku (4T) 22 / 77 64 / 77 **77 / 77** 73 / 77

9x9 Killall-Go (OR: White) **79 / 81** 76 / 81
1 / 81 28 / 81
9x9 Killall-Go (OR: Black) 38 / 81 **46 / 81**


Table 1: The number of problems that can be solved by MCTS-based solver within 30 minutes.

3Note that we only consider the single-ko as repetition in 9x9 Killall-Go, as was the case in van der Werf
et al. (2003) on solving small Go boards.
4Since this changes the way the game behaves by removing all other branches, the networks training will
also be affected.
5Like 4T, this affects the game tree, and therefore also the network training process.


-----

|Col1|Col2|Col3|Col4|Col5|Col6|Col7|Col8|Col9|Col10|Col11|Col12|
|---|---|---|---|---|---|---|---|---|---|---|---|
|||||||||||||
|||||||||||||
|||||||||||||
|||||||||||||
||||2|||||||||
|||||||||||||
||||1|||||||||
|1|4 1|3|7|1|1|||||||
||||3||9||6|||||
|||8|4 1|5 1|2|||||||
||||||5|1|0|||||
|||||||||||||
|||||||||||||

|Col1|Col2|Col3|Col4|Col5|Col6|Col7|Col8|Col9|Col10|Col11|Col12|
|---|---|---|---|---|---|---|---|---|---|---|---|
||||||1|1||||||
||||||10|||||||
|||||||||||||
|||8||||||||||
|||9 2||||||||||
|||||||||||||
||||1|||||||||
|1|2 7|||5||||||||
||||3|||14||||||
|||6|4 1|5||||||||
||||||13|||||||
|||||||||||||
|||||||||||||


(a) A 15x15 Gomoku problem.


(b) Solving with PCN-bheur.


(c) Solving with PCN-bmax.


Figure 3: An illustration for using PCNs on solving 15x15 Gomoku problems.

We use Fig. 3, one of the problems, to illustrate that with the help of 4T, PCN-bheur can take
advantage of the VCF (victory by continuous four) (gom, 2021) strategy more effectively. Fig. 3a is
a problem where Black plays first and wins. Fig. 3b shows the solution following bheur calculation,
where Black wins using VCF. Namely, if White does not respond to any of Black’s threats, Black
wins directly. In bheur, l(s) 0 since the branching factor is reduced to 1 by 4T. Fig. 3c shows
_≈_
the solution found by PCN-bmax, which has the same length as PCN-bheur, but move 7 (Black) is
not a 4T. This means that White has many choices, such as moves 8 and 10, that does not result in
an immediate loss. All possibilities need to be searched to ensure a Black win, so limiting White
choices narrows down the search and improves efficiency. With bmax, since the branching factor
is always set to 225, the solver cannot identify 4Ts. As a result, PCN-bmax requires 7,090 nodes
while PCN-bheur only uses 2,283 to solve this problem. We expect that PCN-bheur can perform
even better when incorporating more domain knowledge, such as three-threats.

4.3 SOLVING 9X9 KILLALL-GO PROBLEMS WITH MCTS-BASED SOLVER

Next, we try to solve 81 automatically generated problems for 9x9 Killall-Go. We exclude Black
wins from the generated problem set because they are trivial for PCN for the following reason. The
goal for Black in this game is to own the entire board. However, since we generate problems from
self-play outcomes, for Black winning states close to the end of the game, e.g. in Fig. 4b, Black
has many similar moves that lead to victory. In situations like these, AlphaZero-based agents are
known to play passively, unnecessarily extending the game length, which is a well-known problem
for MCTS-based players. In fact, the AlphaZero-based Leela Chess Zero program implemented a
“moves left head” in its network to handle this issue (Forst´en & Pascutto, 2019), which functions
similarly to ¯n when we use bmax. Whereas the “moves left head” is only used near the end of the
game, PCN is used throughout a problem. As favorable as this is for PCN, it is not a fair comparison,
so we excluded Black win problems from the Killall-Go set.

Now we observe results for White win problems. Both bmax and bheur still outperform α0 as shown
in Table 1. Note that since the baseline and α0 do not need to designate which side is the OR-player,
they only have one result each. Interestingly, for the variation where Black is set to be the OR-player
(and vm is used instead of vn as the proof cost), it can still solve about half of the problems, despite
the problem being White win and vm being an auxiliary task.

G F C C

|D A B E|Col2|Col3|Col4|Col5|
|---|---|---|---|---|
|||||D|
||A|B|||
||E||||


|A D E B|Col2|Col3|Col4|Col5|
|---|---|---|---|---|
||||A|D|
||||||
||||||


B

C

(a) 9x9 Killall-Go open
G F C

(b) A black win problem. (c) A white win problem. (d) A white win problem.
ing.

Figure 4: An illustration for using PCN and AlphaZero on solving 9x9 Killall-Go problems.

Fig. 4 shows two examples to illustrate the difference between α0 and our method. In Fig. 4c, a
problem for White to play and win, White can become Benson safe by directly playing at A, which


-----

forms two eyes (square labels). Both PCN-bmax and PCN-bheur only focus on A, which solves the
problem directly. However, since White has many ways to win in this position, α0 will attempt other
moves, e.g. play at B, C, or D to kill the cross-marked black stones, or play at E, F, or G to kill the
triangle-mark stones. Since the goal for AlphaZero is to win, and all of A to G can reach this goal,
_α0 does not focus on A only, spending more nodes to solve this problem._

In the problem in Fig. 4d, there is a capturing race between the three white blocks (marked as cross,
triangle, and square) and the black block (marked as circle). White can win the capturing race by
directly playing at A (for Black D, reply E, and for E, reply D). For another sure win, White can first
extend liberties for the square-marked white blocks by making an exchange, a common technique in
Go, where White plays at B and Black replies at C. For both winning moves at A and B, we observe
that α0 tends to make the exchange at B first to increase the win rate, while PCN prefers the faster
A. Again, exploring all possibilities is costly. So much so that α0 takes nearly three times the node
count of PCN to solve this problem.

4.4 SOLVING WITH THE FDFPN SOLVER

Table 2 shows the results for baseline FDFPN[6] and the three types of networks. In FDFPN, we set
_µ = 0.1 on both 15x15 Gomoku and 9x9 Killall-Go. The result shows that both PCN-bmax and_
PCN-bheur still outperform α0. When comparing MCTS and FDFPN solvers directly, we find that
there is no clear winner. FDFPN can solve the same number of problems for 9x9 Killall-Go, while
MCTS-based solver is slightly better for 15x15 Gomoku. The fact that neither DFPN nor MCTS
dominates the other in solving has been corroborated by previous research (Ewalds, 2012; Wei et al.,
2015). However, in either case, PCN has a positive impact on efficiency. We therefore expect PCN
to be extendable to other search algorithms.

No Network _α0_ PCN-bmax PCN-bheur

15x15 Gomoku (NDK) 6 / 77 15 / 77 45 / 77 **48 / 77**
15x15 Gomoku (4T) 34 / 77 41 / 77 **71 / 77** 69 / 77

9x9 Killall-Go (OR: White) **79 / 81** 77 / 81
31 / 81 76 / 81
9x9 Killall-Go (OR: Black) 66 / 81 68 / 81


Table 2: The number of problems that can be solved by FDFPN solver within 30 minutes.

5 DISCUSSION

The experiments demonstrate that, in general, AlphaZero-like networks can be used to enhance
solving without expert knowledge. It is somewhat surprising that bheur is not consistently better
than bmax, since it is theoretically a more accurate estimate. A possible explanation is that the main
benefit of PCN is contingent upon the ordering of ¯n, rather than ¯n itself, and that the limited scope
of heuristics may have led to inaccuracies in general. However, there is potential in fine-tuning a
combination of heuristics so that bheur performs even better. We leave this as a future direction of
research. We note that 15x15 Gomoku has been solved by a combination of PNS, dependency-based
search, and threat-space search (Allis, 1994). Nonetheless, we choose to perform experiments on
Gomoku because it is a straight-forward benchmark that is well-known and often used in games. By
excluding the highly specific dependency-based and threat-space search in our experiments, and by
including experiments for the yet unsolved 9x9 Killall-Go, we wish to demonstrate PCN’s generality and positive impact on solving efficiency, regardless of whether expert knowledge is provided.
Combining PCN with powerful, highly game-specific heuristics is left as a future topic of research.
A strong case that supports the idea that neural networks do not clash with hand-crafted heuristics
in solving is the results presented by Gao et al. (2017), where a highly game-specific engine was
combined with networks to enhance solving on 8x8 Hex. We expect that PCN can be used to solve
more challenging game problems in the future with the introduction of more sophisticated knowledge. Lastly, PCN may be helpful for domains in which heuristics can be difficult to design, e.g.
planning, chemistry, material science, among others.

6FDFPN relies on networks to provide heuristics for progressive widening and move orderings, so without
a network, the baseline is implemented as DFPN.


-----

**Ethics Statement** We do not foresee any potential for ethical concerns for this research.

**Reproducibility Statement** All experiments can be reproduced by following the instructions in
the README file on https://github.com/kds285/proof-cost-network, including source code, problem sets, MCTS and FDFPN solvers, and the trained models used in this paper.

ACKNOWLEDGEMENT

This research is partially supported by the Ministry of Science and Technology (MOST) of Taiwan under Grant Numbers 110-2634-F-009-022, 110-2634-F-A49-004 and 110-2221-E-A49-067MY3, and the computing resources are partially supported by National Center for High-performance
Computing (NCHC) of Taiwan. The authors would also like to thank Professor Martin M¨uller and
anonymous reviewers for their valuable comments.

REFERENCES

[Gomoku World - Game Theory, 2021. URL http://gomokuworld.com/gomoku/1.](http://gomokuworld.com/gomoku/1)

Forest Agostinelli, Stephen McAleer, Alexander Shmakov, and Pierre Baldi. Solving the Rubik’s
cube with deep reinforcement learning and search. Nature Machine Intelligence, 1(8):356–363,
2019.

Louis Victor Allis. Searching for Solutions in Games and Artificial Intelligence. PhD thesis, University of Limburg, Maastricht, The Netherlands, 1994.

Louis Victor Allis, Hendrik Jaap van den Herik, and Matty P H Huntjens. Go-moku and threat-space
_search. University of Limburg, Department of Computer Science, 1993._

Louis Victor Allis, Maarten van der Meulen, and H Jaap van den Herik. Proof-number search.
_Artificial Intelligence, 66(1):91–124, 1994._

Louis Victor Allis, Hendrik Jaap van den Herik, and Matty P H Huntjens. Go-moku solved by new
search techniques. Computational Intelligence, 12(1):7–23, 1996.

David B Benson. Life in the game of go. Information Sciences, 10(1):17–29, 1976.

Marie-Liesse Cauwet, Olivier Teytaud, Tristan Cazenave, Abdallah Saffidine, Hua-Min Liang, ShiJim Yen, Hung-Hsuan Lin, and I-Chen Wu. Depth, balancing, and limits of the elo model. In 2015
_IEEE Conference on Computational Intelligence and Games (CIG), pp. 376–382. IEEE, 2015._

Tristan Cazenave and Abdallah Saffidine. Score bounded monte-carlo tree search. In International
_Conference on Computers and Games, pp. 93–104. Springer, 2010._

R´emi Coulom. Efficient selectivity and backup operators in monte-carlo tree search. In International
_Conference on Computers and Games, pp. 72–83. Springer, 2006._

Timo V Ewalds. Playing and solving havannah. 2012.

[Henrik Forst´en and Gian-Carlo Pascutto. Moves left head, 2019. URL https://github.com/](https://github.com/LeelaChessZero/lc0/pull/961)
[LeelaChessZero/lc0/pull/961.](https://github.com/LeelaChessZero/lc0/pull/961)

Chao Gao, Martin M¨uller, and Ryan Hayward. Focused depth-first proof number search using
convolutional neural networks for the game of hex. In IJCAI, pp. 3668–3674, 2017.

P. Henderson. Playing and solving the game of Hex. 2010.

Philip Henderson, Broderick Arneson, and Ryan B Hayward. Solving 8x8 Hex. In IJCAI, volume 9,
pp. 505–510, 2009.

A. Kishimoto, Beat Buesser, B. Chen, and A. Botea. Depth-first proof-number search with heuristic
edge cost and application to chemical synthesis planning. In Advances in Neural Information
_Processing Systems, 2019._


-----

Akihiro Kishimoto and Martin M¨uller. Search versus knowledge for solving life and death problems
in Go. In AAAI, pp. 1374–1379, 2005.

Levente Kocsis and Csaba Szepesv´ari. Bandit based monte-carlo planning. In European conference
_on machine learning, pp. 282–293. Springer, 2006._

Stephen McAleer, Forest Agostinelli, Alexander Shmakov, and Pierre Baldi. Solving the Rubik’s
cube with approximate policy iteration. In International Conference on Learning Representations,
2018.

Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level
control through deep reinforcement learning. Nature, 518(7540):529–533, 2015.

Andrew W Moore and Christopher G Atkeson. Prioritized sweeping: Reinforcement learning with
less data and less time. Machine learning, 13(1):103–130, 1993.

Ayumu Nagai. Application of df-pn+ to othello endgames. In Proceedings of Game Programming
_Workshop, 1999._

Ayumu Nagai. Df-pn Algorithm for Searching AND/OR Trees and Its Applications. PhD thesis,
University of Tokyo, Tokyo, Japan, 2002.

Barry L Nelson. Hash tables in cray blitz. ICGA Journal, 8(1):3–13, 1985.

Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor
Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, highperformance deep learning library. In Advances in Neural Information Processing Systems, 2019.

Jakub Pawlewicz and Ryan B Hayward. Scalable parallel dfpn search. In International Conference
_on Computers and Games, pp. 138–150. Springer, 2013._

Wim Pijls and Arie de Bruin. Game tree algorithms and solution trees. Theoretical computer science,
252(1-2):197–215, 2001.

Christopher D Rosin. Multi-armed bandits with episode context. Annals of Mathematics and Artifi_cial Intelligence, 61(3):203–230, 2011._

Jahn-Takeshi Saito, Guillaume Chaslot, Jos W H M Uiterwijk, and H Jaap van den Herik. Montecarlo proof-number search for computer Go. In International Conference on Computers and
_Games, pp. 50–61. Springer, 2006._

Jonathan Schaeffer, Neil Burch, Yngvi Bj¨ornsson, Akihiro Kishimoto, Martin M¨uller, Robert Lake,
Paul Lu, and Steve Sutphen. Checkers is solved. Science, 317(5844):1518–1522, 2007.

Julian Schrittwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon
Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, et al. Mastering Atari,
Go, chess and shogi by planning with a learned model. Nature, 588(7839):604–609, 2020.

Marwin HS Segler, Mike Preuss, and Mark P Waller. Planning chemical syntheses with deep neural
networks and symbolic ai. Nature, 555(7698):604–610, 2018.

David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche,
Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering
the game of Go with deep neural networks and tree search. Nature, 529(7587):484–489, 2016.

David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez,
Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of Go
without human knowledge. Nature, 550(7676):354–359, 2017.

David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez,
Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. A general reinforcement
learning algorithm that masters chess, shogi, and Go through self-play. Science, 362(6419):1140–
1144, 2018.


-----

George C. Stockman. A minimax algorithm better than alpha-beta? Artificial Intelligence, 12(2):
179–196, 1979.

[Kai Sun. Yixin, 2018. URL https://www.aiexp.info/pages/yixin.html.](https://www.aiexp.info/pages/yixin.html)

H Jaap van den Herik, Jos W H M Uiterwijk, and Jack Van Rijswijck. Games solved: Now and in
the future. Artificial Intelligence, 134(1-2):277–311, 2002.

Erik C D van der Werf and Mark H M Winands. Solving go for rectangular boards. ICGA Journal,
32(2):77–88, 2009.

Erik C D van der Werf, H Jaap van den Herik, and Jos W H M Uiterwijk. Solving go on small
boards. ICGA Journal, 26(2):92–107, 2003.

Ting han Wei, I-Chen Wu, Chao-Chin Liang, Bing-Tsung Chiang, Wen-Jie Tseng, Shi-Jim Yen, and
Chang-Shing Lee. Job-level algorithms for connect6 opening book construction. ICGA Journal,
38(3):165–179, 2015.

Mark H M Winands and Maarten PD Schadd. Evaluation-function based proof-number search. In
_International Conference on Computers and Games, pp. 23–35. Springer, 2010._

Mark H M Winands, Yngvi Bj¨ornsson, and Jahn-Takeshi Saito. Monte-carlo tree search solver. In
_International Conference on Computers and Games, pp. 25–36. Springer, 2008._

Mark H M Winands, Yngvi Bjornsson, and Jahn-Takeshi Saito. Monte carlo tree search in lines of
action. IEEE Transactions on Computational Intelligence and AI in Games, 2(4):239–250, 2010.

I-Chen Wu, Hung-Hsuan Lin, Ping-Hung Lin, Der-Johng Sun, Yi-Chih Chan, and Bo-Ting Chen.
Job-level proof-number search for connect6. In International Conference on Computers and
_Games, pp. 11–22. Springer, 2010._


-----

A PLAYING STRENGTH

Although our method does not optimize for strongest playing strength, it is an interesting question
worth investigating, since we expect playing and solving to be correlated tasks. With PCN the ORplayer tends to solve (win) the game as soon as possible, which coincides with strong play. On
the other hand, the goal for the AND-player is to maximum ¯n(s); it receives the maximum reward
(∞) if it wins the game. This encourages the AND-player to win the game if possible, and prevent
the OR-player from winning the game as much as possible otherwise. Overall, PCN optimization
preserves playing strength while prioritizing game solving.

Interestingly, the results in Table 3 show that our method is stronger than α0 for 9x9 Killall-Go
(with a win rate of 60%), and has nearly the same playing strength as α0 in 15x15 Gomoku. Each
experiment contains 250 games with alternating Black and White assignment.

Win Rate (WR) Black WR White WR

15x15 Gomoku (NDK) PCN-bmax 50.40% 6.21% 100.00% 0.80%
_±_
15x15 Gomoku (NDK) PCN-bheur 50.80% 6.21% 100.00% 1.60%
_±_
15x15 Gomoku (4T) PCN-bmax 50.40% 6.21% 96.80% 4.00%
_±_
15x15 Gomoku (4T) PCN-bheur 50.00% 6.21% 100.00% 0.00%
_±_

9x9 Killall-Go PCN-bmax (OR: White) 50.00% ± 6.21% 34.40% 65.60%
9x9 Killall-Go PCN-bheur (OR: White) 60.80% ± 6.07% 66.40% 55.20%
9x9 Killall-Go PCN-bmax (OR: Black) 62.25% ± 6.03% 60.00% 64.52%
9x9 Killall-Go PCN-bheur (OR: Black) 60.08% ± 6.06% 53.23% 66.94%


Table 3: Comparing the playing strength between PCNs and α0.

B PROBLEM SET GENERATION

We generate self-play games to create the problem sets. For each self-play game, we start from the
last move at the end of game and try to solve the game by using the three networks (α0, PCN-bmax,
PCN-bheur) with an MCTS solver. If the problem can be solved within 5 minutes, we rollback two
moves and try solving the resulting larger problem. To generate problems with strong discriminating
power, we repeat this process until one of the three programs cannot solve the problem within 5
minutes, upon which the problem is added into the problem set.

For 15x15 Gomoku, we choose Yixin (Sun, 2018), a strong Gomoku program that won several
championships from 2012 to 2018, as the problem generating program. Self-play games were generated with one second per move. Since 15x15 Gomoku has been proven as Black win (Allis, 1994),
and Yixin plays almost optimally, we only select problems with Black wins. We collect 77 problems for Black wins from two variations, 43 and 34 problems from the NDK and 4T respectively.
Generally, the 34 problems is harder than 43 problems.

For 9x9 Killall-Go, since there are no open-source 9x9 Killall-Go programs, we simply use α0 and
PCN-bmax to generate self-play games. The self-play games were generated with 400 simulations
per move. In addition, the Dirichlet noise is maintained in order to increase the diversity of self-play
games. We collect 81 problems for White wins, 39 and 42 problems from the self-play games by
_α0 and PCN-bmax respectively. Black wins are trivial for PCN but difficult for α0 (as we mention_
in subsection 4.3), so we exclude them from our problem set.

C DETAILS FOR SOLVING PROBLEM SETS WITH DIFFERENT SOLVERS

Table 4 to 7 and Table 8 to 11 list the node count and the time for solving 15x15 Gomoku and 9x9
Killall-Go with different network settings as heuristics on both MCTS-based and FDFPN solvers.
In the table, the fewest node counts and the shortest time to solve the problems among the different
settings are bolded, where dashes represent settings where the problems cannot be solved within
30 minutes. Note that the “no network” configuration searches more nodes than any of the configurations where networks are used, within the same amount of time. Each solver runs with one
CPU and one NVIDIA Tesla V100. In 15x15 Gomoku, the solver without networks can visit nearly


-----

10,000 and 30,000 nodes on MCTS-based and FDFPN solvers respectively, while the solver with
networks can only visit 600 and 1,000 nodes on MCTS-based and FDFPN solvers respectively. In
9x9 Killall-Go, the solver without networks can visit nearly 5,600 and 15,000 nodes on MCTS-based
and FDFPN solvers respectively, while the solver with networks can only visit 600 and 950 nodes
on MCTS-based and FDFPN solvers respectively. Despite this massive difference in node counts,
network-assisted solvers can still solve more problems.

To further improve network-assisted solvers, we can use asynchronous evaluation between CPU and
GPU. By doing so, the solver no longer needs to wait for the GPU to compute during evaluation.
The FDFPN-CNN Hex solver by Gao et al. (2017) is one such example. In regards to the slower
CNN evaluations, they state that the runtime overhead of CNN evaluation is not an issue, since the
sophisticated hand-crafted Hex heuristics can be up to 10 times slower than the CNN evaluations in
early positions. As a result, FDFPN-CNN can solve problems more quickly than DFPN and FDFPN
(both without networks) in the same amount of time.

For 15x15 Gomoku, problems 1 to 43 are generated by NDK and problems 44 to 77 are generated
by 4T. The NDK problem set is determined to be easier to solve than the 4T set because all NDK
problems are solvable by the three networks trained with 4T, except for problem 6.


-----

|ID|NDK No Network α0 PCN-b PCN-b max heur|4T No Network α0 PCN-b PCN-b max heur|
|---|---|---|
|1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43|- - 903,544 836,419 - 1,012,028 686,546 749,374 - - 783,765 940,395 - 908,688 635,155 652,825 - - 687,892 758,434 - 653,312 638,560 - - 1,119,700 470,906 433,757 - 534,685 591,610 957,519 - - 515,801 751,947 - 862,561 938,374 - - 559,413 361,723 - - 94,659 839,179 - - 1,113,649 287,016 386,683 - - 685,446 715,306 - - 672,121 644,224 - 680,569 568,632 698,349 - 926,956 784,247 809,173 - 1,032,936 639,561 1,014,679 - 1,000,189 93,057 273,953 - 990,392 781,816 935,157 - - 651,847 830,393 - 1,030,986 770,577 639,290 - - 450,445 431,117 - - 420,275 454,366 - 395,492 987,041 - - 1,156,791 653,604 757,952 - - 712,891 509,584 - 1,103,090 862,540 796,669 - - 861,855 834,637 - - 652,067 865,387 - 231,797 69,152 1,028,435 - - 172,368 577,034 - - 530,040 648,157 - - 487,206 504,550 - - 399,652 593,615 - - 603,235 666,346 13,955,507 465,375 799,030 953,092 - - 583,851 646,149 - 1,106,087 747,578 719,157 - 1,036,870 466,665 807,696 - - 539,523 548,735 - 1,049,955 719,127 912,464 - - 889,495 762,337|- 4,492 3,051 3,164 8,480,868 2,437 2,938 2,416 9,422,154 3,014 1,962 2,015 512,488 2,571 2,668 2,706 - 5,501 4,063 5,815 - 699,398 10,735 - 2,781,342 2,219 1,288 1,981 5,518,358 2,382 3,503 2,006 12,757,192 2,700 2,707 3,608 1,201,265 5,936 4,232 2,851 - 1,681 4,215 2,460 2,266,157 8,307 7,798 3,484 - 2,206 1,796 1,268 - 2,868 5,105 3,452 2,662,073 3,777 1,680 2,571 5,666,572 4,090 6,236 4,254 - 3,112 2,949 2,878 - 8,837 2,234 13,235 - 18,424 7,090 2,283 507,186 2,782 2,799 2,802 - 5,679 4,735 6,405 264,069 2,577 2,776 3,043 - 4,631 1,320 1,281 - 5,271 1,758 3,367 6,959,837 1,618 2,738 8,177 - 4,576 1,717 3,054 11,033,791 5,159 4,675 2,758 13,049,802 3,423 4,066 3,786 293,187 2,789 3,867 3,538 198,562 4,097 2,097 2,464 1,808,145 5,014 3,957 4,035 - 20,016 78,047 92,014 - 6,658 1,775 1,944 - 3,368 1,254 1,257 - 6,204 1,788 2,849 - 8,290 2,770 6,285 93,510 1,273 682 983 13,734,784 3,771 3,198 2,951 2,091,312 2,348 2,938 2,115 - 1,865 1,897 1,861 11,774,261 3,964 1,384 983 - 158,302 2,622 2,345 - 5,004 3,134 2,751|


-----

|ID|NDK No Network α0 PCN-b PCN-b max heur|4T No Network α0 PCN-b PCN-b max heur|
|---|---|---|
|44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77|- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -|- 948,612 11,816 136,827 - - 32,691 28,290 - - 63,209 364,122 - 233,314 294,051 549,238 - 660,045 657,619 651,482 - 879,833 536,679 584,436 - - 418,675 209,113 - 1,008,722 35,214 61,311 - - 478,926 911,914 - - 61,331 317,466 - - 273,710 249,321 - 633,981 479,537 453,190 - - 268,991 238,730 - 854,630 287,420 284,574 - 1,147,125 464,559 891,960 - 261,682 581,801 361,861 - 553,491 72,787 587,483 - 535,287 328,709 1,005,042 - 802,585 585,090 - - - 831,631 294,646 - 1,042,594 342,084 411,711 - 199,122 120,191 - - - 342,094 304,327 - 84,050 794,435 150,296 - 198,359 438,366 866,356 - - 376,675 489,782 - 527,975 505,992 719,737 - 310,169 267,580 654,385 - - 538,784 272,023 - - 354,198 304,270 - 1,048,393 415,890 437,995 - 95,530 77,530 - - 329,171 928,163 675,018 - - 544,247 673,300|


Table 4: The number of nodes for solving 15x15 Gomoku problems by MCTS-based solver within
30 minutes.


-----

|ID|No Network α0|OR: White PCN-b PCN-b max heur|OR: Black PCN-b PCN-b max heur|
|---|---|---|---|
|1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39|- - - - - - - - - 1,133,362 - - - - - - - - - - - - - - - - - - - 61,204 - - - - - 666,273 - - - - - - - - - - - 259,634 - - 3,902,940 - - - - 550,715 - - - - - - - 1,072,229 - 699,976 - 1,152,164 - 682,934 - 889,594 - 690,280 - 660,857 - 188,863|437,427 339,633 4,618 33,160 192,309 211,574 6,555 5,379 554,846 233,965 156,314 70,436 349,935 421,157 409,362 449,030 160,034 201,496 437,794 429,521 529,023 400,903 156,672 182,602 403,117 405,541 69,294 50,143 46,534 355,033 455,218 405,530 227,845 274,924 576,607 605,017 570,149 574,660 70,939 68,671 491,865 363,363 453,038 245,053 476,680 453,657 544,990 - 257,715 193,855 1,981 2,851 102,884 51,444 368,897 352,836 14,519 19,203 325,283 233,978 340,825 321,689 650,540 506,066 670,141 658,158 136,569 94,909 210,127 330,116 362,456 327,290 319,203 214,199 782,389 656,469 1,014,805 214,094|- 785,525 - - - - 10,642 12,223 877,935 1,061,766 - - - 925,416 - - - - - - - - 586,437 440,626 397,002 454,119 - - 55,525 - - 497,717 - 791,601 - 693,361 - 917,036 120,887 75,346 - - - 830,380 - - - - 1,020,210 - 137,263 3,990 20,350 45,310 855,787 719,720 18,116 108,653 484,467 612,807 - 536,506 483,832 507,081 790,459 647,781 182,727 237,083 549,703 335,215 606,410 470,420 241,502 249,145 604,494 836,375 458,387 285,908|


-----

|ID|No Network α0|OR: White PCN-b PCN-b max heur|OR: Black PCN-b PCN-b max heur|
|---|---|---|---|
|40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81|- - - - - - - - - 835,478 - - - - - - - - - 598,013 - - - - - 1,058,102 - 1,079,923 - - - 524,162 - 681,781 - - - - - 702,626 - - - 656,951 - - - - - - - 952,956 - 979,685 - - - - - 773,437 - - - - - - - 761,161 - - - 830,266 - - - - - 712,686 - - - 333,202 - -|391,510 646,069 381,749 425,425 603,583 722,377 360,083 385,016 134,934 372,879 49,328 94,117 - 1,016,020 766,115 618,161 456,166 289,890 313,586 321,995 661,909 499,206 544,187 455,409 458,325 237,500 71,166 127,477 165,955 210,692 258,051 270,910 294,556 - 429,972 763,296 361,453 278,488 176,605 123,341 263,338 279,139 10,355 187,801 306,116 241,333 545,717 782,683 353,096 438,834 478,213 463,806 748,465 654,854 815,722 462,405 896,922 547,063 85,371 97,659 536,289 656,174 758,350 800,725 305,553 352,893 403,713 445,774 564,561 - 37,573 34,223 315,803 332,915 541,111 - 553,105 451,014 779,636 320,105 - - 305,263 480,568|590,645 723,964 - 757,229 - - - - - - - - - - - 833,902 980,939 700,542 - 205,000 - - - - - - - 625,432 - - 418,062 406,587 416,460 - - - 664,460 646,122 600,530 323,570 431,096 249,955 207,440 121,996 1,032,826 958,818 - 779,757 - 421,204 615,836 566,792 709,501 804,058 - - - - - - - - 913,483 - 544,303 - 680,177 553,268 - - 594,617 161,846 - - - - 892,304 606,382 - - 144,310 - 528,225 543,474|


Table 5: The number of nodes for solving 9x9 Killall-Go problems by MCTS-based solver within
30 minutes.


-----

|ID|NDK No Network α0 PCN-b PCN-b max heur|4T No Network α0 PCN-b PCN-b max heur|
|---|---|---|
|1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43|- - 543,160 300,826 - 1,052,180 339,216 575,363 - - 179,216 264,336 - - 262,151 224,069 - - 426,690 261,045 - - 566,537 510,176 - 1,081,268 180,677 131,859 - 512,308 361,114 196,655 - - 375,162 174,019 - - 158,011 160,819 - 242,705 432,620 398,452 1,187,021 5,326 250,782 205,715 - - 265,696 189,882 - - 382,906 529,466 - - 248,953 375,955 - - 646,271 516,882 - - 441,738 527,535 - - 254,980 83,524 2,076,725 136,831 339,247 285,687 - - 286,949 318,495 - - 839,876 281,356 - - 323,425 114,274 6,674,096 140,310 419,757 196,482 - - 322,051 159,776 - - 1,452,491 453,056 - - 641,847 209,837 - 615,044 496,379 115,182 - - 508,185 261,287 - 363,656 741,413 277,864 - - 1,241,236 234,492 423,196 443,681 526,924 329,662 2,698,810 156,409 5,573 16,313 - - 130,813 226,744 - - 253,464 121,042 - 430,639 294,400 482,790 - - 1,459,236 1,308,142 49,658,836 159,883 44,904 41,163 - - 138,609 258,479 - 462,126 450,905 177,037 - - 210,674 212,195 - 426,269 654,285 85,745 - - 1,378,481 186,671 - - 645,077 206,283|2,177,195 28,632 12,195 7,225 390,282 3,202 2,406 8,729 - - 2,394 2,532 2,688,024 54,325 2,610 2,383 1,245,999 13,423 3,748 4,916 - - 10,133 9,760 1,459,111 3,310 1,248 2,092 1,409,132 2,689 3,627 855 - 292,830 2,078 2,498 1,437,840 26,542 2,797 889 87,376 1,271 3,745 3,694 2,497 58 3,990 5,932 6,610,347 164,078 1,215 2,867 2,022,077 11,191 3,480 4,308 23,691,221 2,972 2,024 2,035 21,022,574 7,978 4,748 9,440 - 199,248 5,792 3,355 - 4,173 877 8,192 22,819 1,298 4,688 8,163 894,652 13,950 2,782 2,782 - - 6,815 16,147 23,531,128 3,492 2,330 2,472 18,671 292 1,164 2,336 34,292,960 4,162 1,588 1,588 - - 4,104 4,389 3,227,357 1,556 1,606 3,296 975,205 5,759 1,165 1,167 - - 2,523 2,873 99,310 2,563 5,855 4,823 4,750,995 13,191 2,058 2,058 3,767 14 6,793 7,824 9,891 986 1,942 2,499 - 839,813 1,239 2,520 24,304,241 44,919 1,194 1,194 5,816,694 3,297 6,354 4,420 7,288,513 1,295,829 10,432 5,081 1,007,093 465 400 401 - - 4,723 10,196 235,960 2,377 1,674 2,471 2,526,582 61,503 2,100 1,953 34,663 1,101 814 1,274 37,091,680 625,646 1,759 2,770 - 4,295 3,642 2,042|


-----

|ID|NDK No Network α0 PCN-b PCN-b max heur|4T No Network α0 PCN-b PCN-b max heur|
|---|---|---|
|44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77|- - - 1,792,382 - - - - - - 541,211 183,799 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 1,374,985 - - - - - - - - - - 654,994 - - - - - - - - 1,822,097 - - - - - - - - - - - - - - - - - - - 1,257,882|- - 251,433 267,422 - - 56,306 44,743 34,104,016 439,562 37,161 4,239 - - 93,820 159,739 - - 81,989 1,790,298 - - 480,072 386,461 - - - 1,610,384 - - 298,338 1,033,424 - - - 1,798,644 - - 88,042 125,743 - - - - - - 356,504 337,247 - - - - - - - - - - 948,526 1,584,855 - 1,438,345 468,174 982,546 - - 92,478 114,131 - - 1,068,376 - - - 519,382 958,805 - - 594,017 281,991 - - 460,714 597,067 - - 1,081,090 578,086 21,638,030 - 1,300,876 - - 69,420 57,288 26,993 - - 611,155 1,490,409 - - 709,441 1,297,859 - - 60,078 1,507,901 - - 705,697 318,132 - - 102,770 251,269 - - - - - - 709,832 - - - 143,401 204,409 - - 1,359,561 - - 130,946 88,314 34,050|


Table 6: The number of nodes for solving 15x15 Gomoku problems by FDFPN solver within 30
minutes.


-----

|ID|No Network α0|OR: White PCN-b PCN-b max heur|OR: Black PCN-b PCN-b max heur|
|---|---|---|---|
|1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39|- 105,581 440,072 1,185,075 - 165,180 156,629 11,862 12,225,417 134,212 94,776 - - 88,568 - 324,258 - 91,815 - - - 76,156 - 109,511 - 91,202 913,926 139,042 714,249 - - 74,575 - 104,483 - 371,360 - 236,576 - 49,697 - 229,227 - 68,046 - 201,110 - 55,827 5,751,181 70,464 18,955 155,636 267,915 17,387 - 94,007 160,073 20,682 6,306,634 19,652 - 123,465 - 204,057 - 453,994 9,370,462 76,096 18,455,057 92,739 - 130,105 - 365,501 - 171,239 1,325,967 40,338|- 251,446 85,304 849,589 66,414 48,006 25,744 58,257 49,372 82,856 229,484 - 49,381 42,336 99,992 84,942 38,332 58,377 168,602 - 707,040 439,179 47,928 65,455 68,399 70,416 30,826 38,837 594,300 - 56,884 73,200 67,225 52,809 404,028 764,740 153,104 175,386 52,844 81,449 414,353 112,112 352,552 37,635 154,734 108,834 - 92,276 72,376 73,656 308,769 119,415 30,025 24,954 77,754 73,580 4,142 4,140 41,903 41,139 176,841 61,750 77,380 74,878 455,168 142,337 169,268 40,835 125,019 90,691 187,389 115,271 191,485 39,745 75,797 92,581 309,778 243,186|- - - 1,517,593 282,534 254,917 402,391 598,018 899,547 384,364 - - 327,931 92,959 550,406 1,204,383 904,472 576,223 - - - - 166,016 158,398 78,761 69,916 344,542 - 440,596 - 716,529 649,376 269,910 326,266 - 994,024 538,322 454,310 840,154 52,794 - - 349,411 85,562 - 854,835 1,152,654 735,299 228,755 151,235 311,918 210,555 26,811 27,820 1,073,040 246,813 25,690 32,209 116,303 74,733 184,350 575,231 432,883 207,227 368,747 292,738 173,576 - 959,719 207,097 - 555,793 41,332 59,091 153,552 96,992 451,765 61,551|


-----

|ID|No Network α0|OR: White PCN-b PCN-b max heur|OR: Black PCN-b PCN-b max heur|
|---|---|---|---|
|40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81|1,568,427 11,062 5,582,584 85,341 12,159,258 208,083 - 398,535 7,868,261 51,794 - 42,763 - 332,714 - 153,737 3,546,708 61,985 3,538,421 - - 119,373 - 202,341 - 60,529 2,532,381 931,158 7,796,804 96,960 23,427,876 78,237 - 62,164 - 297,229 - 45,637 - - - 76,577 3,228,036 180,397 1,732,495 95,734 - 136,273 19,265,809 94,870 - 226,771 - 101,958 - 191,855 - 453,862 3,538,272 40,611 - 184,262 - 345,270 - 113,105 - 241,979 - 329,613 4,266,281 39,189 - 216,528 5,212,057 74,484 - 101,740 3,951,997 913,206 5,556,840 51,665 - 203,609|68,513 62,227 77,923 49,357 250,075 727,195 104,223 109,207 116,171 95,303 26,045 59,236 481,330 470,446 178,395 324,031 190,729 63,435 60,819 33,260 59,956 57,896 86,683 75,376 27,602 623,511 49,522 43,069 28,603 38,995 44,023 42,123 58,695 229,139 298,112 563,293 67,159 60,974 35,303 - 96,680 134,284 1,000,430 551,266 67,390 53,681 51,063 86,901 199,416 193,159 81,651 83,622 52,661 169,573 120,125 92,385 130,535 247,408 389,813 268,809 141,848 226,816 338,292 135,537 63,087 491,455 108,124 112,510 478,603 108,690 177,188 26,459 162,290 222,421 372,793 283,878 890,386 1,313,460 538,557 1,560,344 189,705 137,227 258,430 116,320|121,919 119,334 239,248 80,325 1,515,988 297,450 155,762 393,325 105,250 127,852 260,910 1,155,942 517,647 481,537 105,871 649,895 570,575 119,572 542,081 363,988 172,871 226,773 - 1,194,333 932,927 - - 141,410 127,005 216,658 51,499 61,907 84,872 230,724 1,277,324 567,529 131,614 174,553 - 247,154 396,421 99,898 45,367 1,004,425 84,854 67,360 164,990 98,916 212,520 166,488 81,599 308,324 53,265 64,568 948,000 - 128,594 143,000 1,212,621 761,402 - 754,497 323,659 952,482 - - 231,873 1,488,998 338,535 707,935 61,456 108,976 516,084 591,543 57,896 - 75,293 214,671 - - 688,728 431,534 250,402 130,868|


Table 7: The number of nodes for solving 9x9 Killall-Go problems by FDFPN solver within 30
minutes.


-----

|ID|NDK No Network α0 PCN-b PCN-b max heur|4T No Network α0 PCN-b PCN-b max heur|
|---|---|---|
|1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43|- - 1,641.85 1,391.13 - 1,603.53 1,164.22 1,211.55 - - 1,285.74 1,575.19 - 1,359.59 1,086.16 1,089.31 - - 1,156.20 1,300.91 - 985.13 1,111.49 - - 1,679.10 762.32 713.26 - 818.23 996.76 1,617.30 - - 872.64 1,236.99 - 1,302.95 1,588.18 - - 849.36 612.68 - - 143.59 1,459.04 - - 1,764.95 473.21 643.69 - - 1,390.14 1,407.12 - - 1,145.41 1,110.29 - 1,046.80 970.73 1,155.58 - 1,361.17 1,341.06 1,425.94 - 1,556.42 1,133.75 1,747.26 - 1,494.58 156.03 457.72 - 1,471.13 1,323.64 1,587.48 - - 1,132.25 1,422.36 - 1,549.52 1,296.35 1,055.47 - - 753.05 727.39 - - 711.89 755.30 - 606.42 1,654.57 - - 1,739.03 1,103.72 1,237.65 - - 1,193.00 827.29 - 1,701.56 1,480.14 1,336.36 - - 1,478.13 1,373.58 - - 1,051.20 1,428.38 - 353.11 115.50 1,722.87 - - 292.02 1,004.17 - - 887.65 1,196.47 - - 789.29 825.19 - - 680.09 988.54 - - 1,011.33 1,127.02 1,546.59 727.96 1,367.75 1,539.05 - - 944.65 1,051.17 - 1,655.04 1,255.56 1,201.15 - 1,553.98 798.03 1,346.00 - - 910.09 900.26 - 1,588.72 1,444.92 1,498.58 - - 1,654.17 1,261.58|- 6.91 5.24 5.26 909.63 3.79 4.76 4.06 960.39 4.81 3.42 3.56 49.73 4.16 4.56 4.62 - 8.29 6.80 9.62 - 1,043.69 17.64 - 303.18 3.62 2.41 3.44 635.09 3.79 5.92 3.52 1,508.31 4.40 4.60 6.11 117.27 8.89 6.91 5.00 - 2.74 7.08 4.18 252.64 12.48 12.49 5.89 - 4.20 3.13 2.37 - 4.36 8.31 5.74 276.29 5.82 2.92 4.35 619.56 6.34 10.14 7.06 - 4.90 4.95 4.94 - 13.35 3.89 21.70 - 26.66 11.88 3.89 49.84 4.34 4.76 4.77 - 8.45 7.92 10.42 25.47 4.38 4.65 5.08 - 7.14 2.41 2.42 - 8.29 3.07 5.81 685.59 2.62 4.63 13.23 - 7.01 3.04 5.15 1,191.56 7.78 7.68 4.65 1,550.17 5.14 6.75 7.60 24.06 4.41 6.50 5.83 18.52 6.42 3.76 4.20 161.98 7.75 6.60 6.67 - 29.57 127.56 144.17 - 9.90 3.10 3.38 - 5.21 2.31 2.35 - 9.47 3.20 5.00 - 14.79 4.76 10.34 7.41 2.17 1.41 1.89 1,444.89 5.76 5.35 5.04 210.16 3.81 5.01 3.68 - 3.02 3.40 3.32 1,339.80 7.40 2.51 1.95 - 282.98 5.35 4.05 - 7.69 5.39 4.72|


-----

|ID|NDK No Network α0 PCN-b PCN-b max heur|4T No Network α0 PCN-b PCN-b max heur|
|---|---|---|
|44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77|- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -|- 1,416.51 18.58 219.25 - - 53.10 47.68 - - 107.05 609.18 - 342.41 483.62 934.34 - 963.28 1,295.06 1,106.29 - 1,287.97 908.03 1,001.88 - - 730.09 354.13 - 1,477.58 56.31 103.56 - - 848.60 1,605.55 - - 103.88 556.51 - - 437.53 404.02 - 915.69 791.14 742.92 - - 436.69 390.40 - 1,292.87 478.50 491.27 - 1,765.34 820.44 1,565.14 - 382.00 1,114.89 623.94 - 823.72 117.10 1,002.04 - 836.36 566.13 1,788.09 - 1,181.13 998.12 - - - 1,475.81 510.46 - 1,569.05 554.86 691.11 - 307.41 204.81 - - - 573.36 503.69 - 127.16 1,592.37 258.61 - 296.08 772.00 1,534.01 - - 646.82 835.70 - 770.25 872.30 1,241.65 - 456.92 447.29 1,099.47 - - 948.82 477.99 - - 574.38 495.11 - 1,564.80 680.49 739.09 - 145.03 129.98 - - 488.09 1,541.00 1,129.12 - - 931.98 1,120.48|


Table 8: The number of seconds for solving 15x15 Gomoku problems by MCTS-based solver within
30 minutes.


-----

|ID|No Network α0|OR: White PCN-b PCN-b max heur|OR: Black PCN-b PCN-b max heur|
|---|---|---|---|
|1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39|- - - - - - - - - 1,699.97 - - - - - - - - - - - - - - - - - - - 92.62 - - - - - 1,016.10 - - - - - - - - - - - 397.35 - - 694.75 - - - - 813.48 - - - - - - - 1,642.09 - 1,055.87 - 1,786.24 - 1,047.99 - 1,413.90 - 1,026.93 - 1,021.81 - 286.99|717.29 550.25 7.64 53.68 310.45 455.50 10.95 8.91 883.03 373.53 257.29 112.90 593.42 692.15 678.70 760.72 249.15 318.21 720.91 743.88 859.67 670.63 251.54 314.89 657.45 637.39 112.69 80.58 76.34 589.04 865.33 670.93 361.44 454.74 947.34 980.16 930.83 927.06 114.96 110.13 859.63 594.28 710.73 408.30 776.83 745.13 923.48 - 409.48 306.63 3.43 4.87 166.86 88.92 590.50 576.55 23.39 30.57 516.90 376.76 562.35 525.96 1,051.68 848.82 1,089.96 1,047.25 226.78 151.43 337.09 533.51 699.19 527.28 525.22 349.81 1,319.52 1,045.71 1,639.58 346.67|- 1,308.06 - - - - 17.15 19.88 1,407.40 1,716.12 - - - 1,574.53 - - - - - - - - 960.04 701.50 624.48 728.20 - - 90.74 - - 803.47 - 1,283.96 - 1,141.83 - 1,562.77 194.30 135.16 - - - 1,404.40 - - - - 1,665.77 - 219.22 6.67 32.27 73.49 1,420.97 1,189.86 29.27 171.38 766.32 976.99 - 885.91 777.79 948.32 1,287.27 1,057.17 293.71 380.98 876.26 545.96 983.93 749.81 382.59 393.80 993.30 1,335.96 753.18 486.64|


-----

|ID|No Network α0|OR: White PCN-b PCN-b max heur|OR: Black PCN-b PCN-b max heur|
|---|---|---|---|
|40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81|- - - - - - - - - 1,254.88 - - - - - - - - - 965.99 - - - - - 1,606.60 - 1,709.32 - - - 769.36 - 1,043.89 - - - - - 1,095.48 - - - 1,000.77 - - - - - - - 1,435.88 - 1,444.08 - - - - - 1,184.15 - - - - - - - 1,219.56 - - - 1,269.77 - - - - - 1,096.09 - - - 496.93 - -|609.87 1,055.59 624.47 789.08 969.97 1,151.57 581.76 726.57 214.95 600.15 82.95 151.06 - 1,691.70 1,244.11 989.85 747.32 478.10 499.94 523.49 1,083.70 819.99 902.41 734.51 742.37 375.71 113.59 208.31 270.97 334.19 426.23 432.22 473.24 - 703.08 1,228.99 593.03 459.56 306.37 195.31 422.89 449.17 17.10 314.45 495.79 377.44 853.85 1,253.60 582.64 727.92 786.31 730.44 1,227.15 1,057.24 1,339.81 739.78 1,503.63 961.99 140.69 162.64 856.74 1,087.59 1,205.52 1,314.98 501.21 578.36 634.80 736.14 903.23 - 60.95 55.17 512.92 540.63 989.07 - 873.19 720.92 1,322.26 556.49 - - 503.55 796.72|972.74 1,154.97 - 1,225.60 - - - - - - - - - - - 1,345.12 1,620.92 1,119.28 - 336.27 - - - - - - - 1,059.81 - - 682.90 650.82 683.99 - - - 1,099.31 1,071.77 950.30 529.00 699.77 404.72 354.66 195.99 1,659.71 1,544.58 - 1,316.05 - 674.43 984.65 943.31 1,163.36 1,333.39 - - - - - - - - 1,496.59 - 882.80 - 1,077.52 899.74 - - 954.76 267.81 - - - - 1,461.39 996.62 - - 237.71 - 873.12 887.82|


Table 9: The number of seconds for solving 9x9 Killall-Go problems by MCTS-based solver within
30 minutes.


-----

|ID|NDK No Network α0 PCN-b PCN-b max heur|4T No Network α0 PCN-b PCN-b max heur|
|---|---|---|
|1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43|- - 452.58 250.79 - 1,089.85 287.76 486.31 - - 147.90 219.14 - - 225.64 187.48 - - 373.72 214.83 - - 483.94 426.65 - 1,050.54 150.95 111.42 - 500.92 290.77 174.87 - - 315.60 148.64 - - 131.21 129.81 - 228.54 381.68 344.47 38.44 8.55 204.32 171.83 - - 225.16 158.58 - - 386.61 428.26 - - 204.07 343.96 - - 553.34 422.95 - - 362.46 538.79 - - 213.73 69.44 59.33 169.88 289.70 244.17 - - 234.84 279.29 - - 701.95 230.92 - - 267.92 94.72 196.64 171.50 339.06 160.70 - - 267.21 130.39 - - 1,344.21 373.23 - - 533.24 175.49 - 572.92 400.28 96.45 - - 419.59 217.19 - 309.18 645.21 236.40 - - 1,082.56 193.67 13.94 389.29 447.95 272.70 77.56 150.14 7.54 17.33 - - 108.39 187.57 - - 229.58 102.62 - 500.48 244.87 396.00 - - 1,476.63 1,135.60 1,708.60 159.03 39.99 35.99 - - 115.46 257.76 - 462.48 462.54 168.51 - - 178.03 173.06 - 415.11 543.92 72.02 - - 1,322.47 152.56 - - 534.58 169.33|92.40 34.36 14.90 10.23 19.31 5.97 6.27 13.83 - - 5.95 4.52 112.61 70.03 4.27 4.24 57.89 17.62 6.50 6.62 - - 13.08 13.44 67.48 5.39 3.35 3.98 64.05 4.71 5.57 3.01 - 353.89 3.96 4.40 62.44 29.35 4.42 3.10 6.07 3.10 5.48 5.29 2.44 2.28 7.15 7.14 277.23 161.44 3.27 5.08 87.17 16.28 4.99 5.81 995.42 6.11 3.90 3.93 935.03 12.68 6.53 9.81 - 265.95 7.08 5.06 - 7.56 3.39 13.55 2.69 4.76 6.78 9.13 41.60 16.44 4.69 5.61 - - 10.40 18.68 952.18 6.51 4.23 4.37 2.71 2.58 3.18 4.25 1,500.09 6.97 3.50 3.56 - - 6.21 5.90 137.86 4.40 3.55 5.78 43.25 8.08 3.15 3.15 - - 4.55 4.88 6.10 4.11 7.44 6.59 218.66 16.67 4.00 3.86 2.45 2.18 8.07 9.72 2.26 3.83 4.25 5.70 - 1,036.16 3.24 4.62 1,047.46 48.76 3.40 3.31 257.96 6.10 9.04 5.85 259.40 1,704.00 13.61 6.96 45.19 2.53 2.72 2.51 - - 8.38 12.98 12.81 4.15 3.53 4.46 105.34 68.63 4.25 5.05 3.55 3.50 4.04 3.23 1,748.07 712.34 4.53 6.47 - 7.06 7.06 4.01|


-----

|ID|NDK No Network α0 PCN-b PCN-b max heur|4T No Network α0 PCN-b PCN-b max heur|
|---|---|---|
|44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77|- - - 1,531.60 - - - - - - 479.45 154.43 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 1,146.29 - - - - - - - - - - 559.80 - - - - - - - - 1,531.69 - - - - - - - - - - - - - - - - - - - 1,075.57|- - 231.69 254.88 - - 54.78 44.81 1,365.49 552.57 35.40 6.32 - - 93.92 147.53 - - 73.80 1,535.73 - - 428.07 355.17 - - - 1,467.75 - - 260.30 975.85 - - - 1,573.53 - - 82.38 122.28 - - - - - - 323.44 303.80 - - - - - - - - - - 834.94 1,385.13 - 1,747.38 422.92 1,119.64 - - 81.03 98.32 - - 932.23 - - - 452.09 857.88 - - 550.55 274.11 - - 426.04 559.13 - - 1,260.36 558.35 929.66 - 1,194.21 - - 81.16 50.39 27.80 - - 583.33 1,385.67 - - 614.95 1,148.70 - - 52.98 1,421.51 - - 606.93 280.18 - - 98.30 229.78 - - - - - - 609.68 - - - 144.79 215.34 - - 1,159.34 - - 149.06 87.45 34.11|


Table 10: The number of seconds for solving 15x15 Gomoku problems by FDFPN solver within 30
minutes.


-----

|ID|No Network α0|OR: White PCN-b PCN-b max heur|OR: Black PCN-b PCN-b max heur|
|---|---|---|---|
|1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39|- 123.57 31.58 1,427.51 - 198.97 13.43 15.10 886.54 156.85 7.89 - - 103.60 - 371.78 - 109.20 - - - 84.11 - 130.78 - 114.65 61.45 144.57 54.44 - - 85.17 - 119.74 - 434.44 - 284.36 - 64.16 - 273.99 - 69.99 - 219.83 - 66.71 231.02 82.18 3.20 183.71 26.03 20.94 - 104.69 16.22 24.03 623.01 24.35 - 144.15 - 221.47 - 582.08 960.28 91.37 1,198.23 104.04 - 151.65 - 434.39 - 183.02 86.48 50.87|- 240.92 83.20 942.16 62.60 46.13 25.76 56.57 49.55 80.30 250.80 - 49.37 41.54 98.65 81.89 37.78 55.22 153.40 - 725.33 463.33 46.56 61.71 65.08 71.93 32.69 37.78 624.53 - 56.61 73.32 65.52 51.85 385.28 766.47 166.35 179.28 51.23 77.72 384.46 101.71 325.36 38.38 148.88 105.60 - 104.04 75.33 74.93 319.49 119.51 31.05 26.29 75.16 73.88 6.18 5.83 40.71 39.76 183.09 60.75 74.58 68.91 477.68 142.69 172.93 42.44 121.52 85.38 184.78 128.23 185.82 39.34 73.48 88.23 314.47 232.05|- - - 1,695.97 291.05 253.62 417.85 601.96 1,144.13 406.89 - - 318.74 89.22 581.53 1,339.79 900.34 587.29 - - - - 156.09 152.95 77.01 68.35 334.21 - 431.13 - 732.51 680.38 261.32 314.09 - 1,041.93 549.76 446.55 901.22 51.33 - - 331.10 83.25 - 921.71 1,166.18 728.24 278.38 157.90 338.69 225.64 31.74 28.56 1,093.91 246.79 25.89 31.84 115.49 70.90 205.21 624.58 453.48 194.93 377.24 301.71 186.74 - 1,052.79 203.96 - 545.87 38.79 57.92 148.20 93.28 440.41 61.29|


-----

|ID|No Network α0|OR: White PCN-b PCN-b max heur|OR: Black PCN-b PCN-b max heur|
|---|---|---|---|
|40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81|184.11 14.31 252.70 99.94 838.71 263.73 - 474.60 345.29 57.68 - 48.26 - 432.77 - 185.87 202.32 72.18 206.34 - - 131.79 - 241.02 - 73.73 233.12 1,153.92 430.20 106.41 844.70 92.66 - 69.00 - 350.69 - 54.89 - - - 96.72 286.99 208.00 166.89 105.47 - 178.92 1,079.18 108.55 - 270.09 - 126.95 - 230.61 - 706.19 264.20 45.12 - 214.32 - 401.63 - 157.31 - 309.80 - 401.79 368.85 46.48 - 239.43 349.00 81.59 - 120.78 212.18 1,161.57 377.69 63.16 - 236.54|66.06 58.98 85.21 53.00 252.75 740.79 101.17 104.18 127.94 96.94 26.04 57.68 491.31 465.43 164.82 302.55 186.28 63.25 68.18 36.49 56.36 56.53 84.23 77.15 30.88 624.36 50.00 41.29 26.53 38.03 49.99 46.33 56.28 224.92 281.45 585.07 77.31 59.04 36.58 - 91.44 140.39 951.63 519.76 75.49 54.51 50.21 81.57 212.10 194.94 78.17 84.74 55.17 165.01 116.47 93.38 123.35 230.51 382.15 296.52 141.80 220.62 336.30 129.38 63.33 481.37 104.24 109.34 494.81 105.64 170.07 25.79 153.76 217.91 372.46 286.34 916.71 1,374.30 631.20 1,695.10 189.77 140.90 268.44 113.45|115.94 111.50 250.28 88.53 1,770.01 326.05 150.20 366.13 103.44 125.41 295.36 1,129.93 528.22 499.04 99.48 618.58 565.44 120.45 605.91 384.63 161.66 223.69 - 1,224.39 976.04 - - 150.20 134.80 214.86 65.48 75.00 79.94 214.85 1,392.13 584.82 128.94 172.72 - 266.44 370.75 89.89 44.48 1,043.74 84.17 66.29 170.67 94.54 218.66 178.36 78.95 281.10 51.84 71.56 956.85 - 118.42 140.59 1,568.31 785.38 - 729.76 314.37 955.69 - - 241.93 1,449.46 348.10 680.13 57.99 101.98 526.48 632.97 54.16 - 105.49 214.10 - - 725.64 437.09 276.19 125.98|


Table 11: The number of seconds for solving 9x9 Killall-Go problems by FDFPN solver within 30
minutes.


-----

