ALPHAZERO-BASED PROOF COST NETWORK TO AID GAME SOLVING
Year: 2022

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.

heading: 1 INTRODUCTION
text: 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 solving1 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.

heading: 2 BACKGROUND

heading: 2.1 THE GAME-THEORETIC VALUE AND PROOF TREES
text: 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 players2. 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.

heading: 2.2 MONTE CARLO TREE SEARCH
text: Monte Carlo tree search (MCTS) (Coulom, 2006; Kocsis & Szepesvári, 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):
a∗ = arg max a
{ Q(s, a) + cPUCT × P (s, a)× √∑ bN(s, b)
1 +N(s, a)
} , (1)
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, cPUCT 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 andQ(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).

heading: 2.3 PROOF NUMBER SEARCH
text: 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 & Müller, 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 + dµ × |blivechildren|e, 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+df(s)×|blivechildren|e and f(s) = min{µ, 1 + v(s)}.

heading: 2.4 THE ALPHAZERO ALGORITHM
text: 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.

heading: 3 OUR APPROACH

heading: 3.1 ESTIMATING PROOF TREE SIZES
text: 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(si), where si are the children of sAND. Suppose sOR 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 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.

heading: 3.2 THE PROOF TREE SIZE ESTIMATE AS A TRAINING TARGET
text: 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) := ∑b 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 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).
Figure 1: An illustration for different b.
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 ∑b 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 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 + minn(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.

heading: 3.3 TRAINING THE PROOF COST NETWORK WITH ALPHAZERO
text: 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∈TreeQ(s, a) maxs,a∈TreeQ(s, a)−mins,a∈TreeQ(s, a) − 1. (3)
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).

heading: 3.4 FOCUSED DFPN WITH PROOF COST NETWORK
text: 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.

heading: 4 EXPERIMENTS

heading: 4.1 TRAINING SETTINGS
text: 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 search3.
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 blocking4; 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 board5; 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.

heading: 4.2 SOLVING 15X15 GOMOKU PROBLEMS WITH MCTS-BASED SOLVER
text: 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) 1 / 81 28 / 81 79 / 81 76 / 819x9 Killall-Go (OR: Black) 38 / 81 46 / 81
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.

heading: 4.3 SOLVING 9X9 KILLALL-GO PROBLEMS WITH MCTS-BASED SOLVER
text: 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 (Forstén & 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.
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.

heading: 4.4 SOLVING WITH THE FDFPN SOLVER
text: Table 2 shows the results for baseline FDFPN6 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.

heading: 5 DISCUSSION
text: 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.

heading: ACKNOWLEDGEMENT
text: 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 Müller and anonymous reviewers for their valuable comments.

heading: A PLAYING STRENGTH
text: 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.

heading: B PROBLEM SET GENERATION
text: 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.

heading: C DETAILS FOR SOLVING PROBLEM SETS WITH DIFFERENT SOLVERS
text: 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 4TNo Network α0 PCN-bmax PCN-bheur No Network α0 PCN-bmax PCN-bheur 1 - - 903,544 836,419 - 4,492 3,051 3,164 2 - 1,012,028 686,546 749,374 8,480,868 2,437 2,938 2,416 3 - - 783,765 940,395 9,422,154 3,014 1,962 2,015 4 - 908,688 635,155 652,825 512,488 2,571 2,668 2,706 5 - - 687,892 758,434 - 5,501 4,063 5,815 6 - 653,312 638,560 - - 699,398 10,735 - 7 - 1,119,700 470,906 433,757 2,781,342 2,219 1,288 1,981 8 - 534,685 591,610 957,519 5,518,358 2,382 3,503 2,006 9 - - 515,801 751,947 12,757,192 2,700 2,707 3,608 10 - 862,561 938,374 - 1,201,265 5,936 4,232 2,851 11 - 559,413 361,723 - - 1,681 4,215 2,460 12 - 94,659 839,179 - 2,266,157 8,307 7,798 3,484 13 - 1,113,649 287,016 386,683 - 2,206 1,796 1,268 14 - - 685,446 715,306 - 2,868 5,105 3,452 15 - - 672,121 644,224 2,662,073 3,777 1,680 2,571 16 - 680,569 568,632 698,349 5,666,572 4,090 6,236 4,254 17 - 926,956 784,247 809,173 - 3,112 2,949 2,878 18 - 1,032,936 639,561 1,014,679 - 8,837 2,234 13,235 19 - 1,000,189 93,057 273,953 - 18,424 7,090 2,283 20 - 990,392 781,816 935,157 507,186 2,782 2,799 2,802 21 - - 651,847 830,393 - 5,679 4,735 6,405 22 - 1,030,986 770,577 639,290 264,069 2,577 2,776 3,043 23 - - 450,445 431,117 - 4,631 1,320 1,281 24 - - 420,275 454,366 - 5,271 1,758 3,367 25 - 395,492 987,041 - 6,959,837 1,618 2,738 8,177 26 - 1,156,791 653,604 757,952 - 4,576 1,717 3,054 27 - - 712,891 509,584 11,033,791 5,159 4,675 2,758 28 - 1,103,090 862,540 796,669 13,049,802 3,423 4,066 3,786 29 - - 861,855 834,637 293,187 2,789 3,867 3,538 30 - - 652,067 865,387 198,562 4,097 2,097 2,464 31 - 231,797 69,152 1,028,435 1,808,145 5,014 3,957 4,035 32 - - 172,368 577,034 - 20,016 78,047 92,014 33 - - 530,040 648,157 - 6,658 1,775 1,944 34 - - 487,206 504,550 - 3,368 1,254 1,257 35 - - 399,652 593,615 - 6,204 1,788 2,849 36 - - 603,235 666,346 - 8,290 2,770 6,285 37 13,955,507 465,375 799,030 953,092 93,510 1,273 682 983 38 - - 583,851 646,149 13,734,784 3,771 3,198 2,951 39 - 1,106,087 747,578 719,157 2,091,312 2,348 2,938 2,115 40 - 1,036,870 466,665 807,696 - 1,865 1,897 1,861 41 - - 539,523 548,735 11,774,261 3,964 1,384 983 42 - 1,049,955 719,127 912,464 - 158,302 2,622 2,345 43 - - 889,495 762,337 - 5,004 3,134 2,751
ID No Network α0 OR: White OR: BlackPCN-bmax PCN-bheur PCN-bmax PCN-bheur 1 - - 437,427 339,633 - 785,525 2 - - 4,618 33,160 - - 3 - - 192,309 211,574 - - 4 - - 6,555 5,379 10,642 12,223 5 - 1,133,362 554,846 233,965 877,935 1,061,766 6 - - 156,314 70,436 - - 7 - - 349,935 421,157 - 925,416 8 - - 409,362 449,030 - - 9 - - 160,034 201,496 - - 10 - - 437,794 429,521 - - 11 - - 529,023 400,903 - - 12 - - 156,672 182,602 586,437 440,626 13 - - 403,117 405,541 397,002 454,119 14 - - 69,294 50,143 - - 15 - 61,204 46,534 355,033 55,525 - 16 - - 455,218 405,530 - 497,717 17 - - 227,845 274,924 - 791,601 18 - 666,273 576,607 605,017 - 693,361 19 - - 570,149 574,660 - 917,036 20 - - 70,939 68,671 120,887 75,346 21 - - 491,865 363,363 - - 22 - - 453,038 245,053 - 830,380 23 - - 476,680 453,657 - - 24 - 259,634 544,990 - - - 25 - - 257,715 193,855 1,020,210 - 26 3,902,940 - 1,981 2,851 137,263 3,990 27 - - 102,884 51,444 20,350 45,310 28 - 550,715 368,897 352,836 855,787 719,720 29 - - 14,519 19,203 18,116 108,653 30 - - 325,283 233,978 484,467 612,807 31 - - 340,825 321,689 - 536,506 32 - 1,072,229 650,540 506,066 483,832 507,081 33 - 699,976 670,141 658,158 790,459 647,781 34 - 1,152,164 136,569 94,909 182,727 237,083 35 - 682,934 210,127 330,116 549,703 335,215 36 - 889,594 362,456 327,290 606,410 470,420 37 - 690,280 319,203 214,199 241,502 249,145 38 - 660,857 782,389 656,469 604,494 836,375 39 - 188,863 1,014,805 214,094 458,387 285,908
ID NDK 4TNo Network α0 PCN-bmax PCN-bheur No Network α0 PCN-bmax PCN-bheur 1 - - 543,160 300,826 2,177,195 28,632 12,195 7,225 2 - 1,052,180 339,216 575,363 390,282 3,202 2,406 8,729 3 - - 179,216 264,336 - - 2,394 2,532 4 - - 262,151 224,069 2,688,024 54,325 2,610 2,383 5 - - 426,690 261,045 1,245,999 13,423 3,748 4,916 6 - - 566,537 510,176 - - 10,133 9,760 7 - 1,081,268 180,677 131,859 1,459,111 3,310 1,248 2,092 8 - 512,308 361,114 196,655 1,409,132 2,689 3,627 855 9 - - 375,162 174,019 - 292,830 2,078 2,498 10 - - 158,011 160,819 1,437,840 26,542 2,797 889 11 - 242,705 432,620 398,452 87,376 1,271 3,745 3,694 12 1,187,021 5,326 250,782 205,715 2,497 58 3,990 5,932 13 - - 265,696 189,882 6,610,347 164,078 1,215 2,867 14 - - 382,906 529,466 2,022,077 11,191 3,480 4,308 15 - - 248,953 375,955 23,691,221 2,972 2,024 2,035 16 - - 646,271 516,882 21,022,574 7,978 4,748 9,440 17 - - 441,738 527,535 - 199,248 5,792 3,355 18 - - 254,980 83,524 - 4,173 877 8,192 19 2,076,725 136,831 339,247 285,687 22,819 1,298 4,688 8,163 20 - - 286,949 318,495 894,652 13,950 2,782 2,782 21 - - 839,876 281,356 - - 6,815 16,147 22 - - 323,425 114,274 23,531,128 3,492 2,330 2,472 23 6,674,096 140,310 419,757 196,482 18,671 292 1,164 2,336 24 - - 322,051 159,776 34,292,960 4,162 1,588 1,588 25 - - 1,452,491 453,056 - - 4,104 4,389 26 - - 641,847 209,837 3,227,357 1,556 1,606 3,296 27 - 615,044 496,379 115,182 975,205 5,759 1,165 1,167 28 - - 508,185 261,287 - - 2,523 2,873 29 - 363,656 741,413 277,864 99,310 2,563 5,855 4,823 30 - - 1,241,236 234,492 4,750,995 13,191 2,058 2,058 31 423,196 443,681 526,924 329,662 3,767 14 6,793 7,824 32 2,698,810 156,409 5,573 16,313 9,891 986 1,942 2,499 33 - - 130,813 226,744 - 839,813 1,239 2,520 34 - - 253,464 121,042 24,304,241 44,919 1,194 1,194 35 - 430,639 294,400 482,790 5,816,694 3,297 6,354 4,420 36 - - 1,459,236 1,308,142 7,288,513 1,295,829 10,432 5,081 37 49,658,836 159,883 44,904 41,163 1,007,093 465 400 401 38 - - 138,609 258,479 - - 4,723 10,196 39 - 462,126 450,905 177,037 235,960 2,377 1,674 2,471 40 - - 210,674 212,195 2,526,582 61,503 2,100 1,953 41 - 426,269 654,285 85,745 34,663 1,101 814 1,274 42 - - 1,378,481 186,671 37,091,680 625,646 1,759 2,770 43 - - 645,077 206,283 - 4,295 3,642 2,042
ID No Network α0 OR: White OR: BlackPCN-bmax PCN-bheur PCN-bmax PCN-bheur 1 - 105,581 - 251,446 - - 2 440,072 1,185,075 85,304 849,589 - 1,517,593 3 - 165,180 66,414 48,006 282,534 254,917 4 156,629 11,862 25,744 58,257 402,391 598,018 5 12,225,417 134,212 49,372 82,856 899,547 384,364 6 94,776 - 229,484 - - - 7 - 88,568 49,381 42,336 327,931 92,959 8 - 324,258 99,992 84,942 550,406 1,204,383 9 - 91,815 38,332 58,377 904,472 576,223 10 - - 168,602 - - - 11 - 76,156 707,040 439,179 - - 12 - 109,511 47,928 65,455 166,016 158,398 13 - 91,202 68,399 70,416 78,761 69,916 14 913,926 139,042 30,826 38,837 344,542 - 15 714,249 - 594,300 - 440,596 - 16 - 74,575 56,884 73,200 716,529 649,376 17 - 104,483 67,225 52,809 269,910 326,266 18 - 371,360 404,028 764,740 - 994,024 19 - 236,576 153,104 175,386 538,322 454,310 20 - 49,697 52,844 81,449 840,154 52,794 21 - 229,227 414,353 112,112 - - 22 - 68,046 352,552 37,635 349,411 85,562 23 - 201,110 154,734 108,834 - 854,835 24 - 55,827 - 92,276 1,152,654 735,299 25 5,751,181 70,464 72,376 73,656 228,755 151,235 26 18,955 155,636 308,769 119,415 311,918 210,555 27 267,915 17,387 30,025 24,954 26,811 27,820 28 - 94,007 77,754 73,580 1,073,040 246,813 29 160,073 20,682 4,142 4,140 25,690 32,209 30 6,306,634 19,652 41,903 41,139 116,303 74,733 31 - 123,465 176,841 61,750 184,350 575,231 32 - 204,057 77,380 74,878 432,883 207,227 33 - 453,994 455,168 142,337 368,747 292,738 34 9,370,462 76,096 169,268 40,835 173,576 - 35 18,455,057 92,739 125,019 90,691 959,719 207,097 36 - 130,105 187,389 115,271 - 555,793 37 - 365,501 191,485 39,745 41,332 59,091 38 - 171,239 75,797 92,581 153,552 96,992 39 1,325,967 40,338 309,778 243,186 451,765 61,551
ID NDK 4TNo Network α0 PCN-bmax PCN-bheur No Network α0 PCN-bmax PCN-bheur 1 - - 1,641.85 1,391.13 - 6.91 5.24 5.26 2 - 1,603.53 1,164.22 1,211.55 909.63 3.79 4.76 4.06 3 - - 1,285.74 1,575.19 960.39 4.81 3.42 3.56 4 - 1,359.59 1,086.16 1,089.31 49.73 4.16 4.56 4.62 5 - - 1,156.20 1,300.91 - 8.29 6.80 9.62 6 - 985.13 1,111.49 - - 1,043.69 17.64 - 7 - 1,679.10 762.32 713.26 303.18 3.62 2.41 3.44 8 - 818.23 996.76 1,617.30 635.09 3.79 5.92 3.52 9 - - 872.64 1,236.99 1,508.31 4.40 4.60 6.11 10 - 1,302.95 1,588.18 - 117.27 8.89 6.91 5.00 11 - 849.36 612.68 - - 2.74 7.08 4.18 12 - 143.59 1,459.04 - 252.64 12.48 12.49 5.89 13 - 1,764.95 473.21 643.69 - 4.20 3.13 2.37 14 - - 1,390.14 1,407.12 - 4.36 8.31 5.74 15 - - 1,145.41 1,110.29 276.29 5.82 2.92 4.35 16 - 1,046.80 970.73 1,155.58 619.56 6.34 10.14 7.06 17 - 1,361.17 1,341.06 1,425.94 - 4.90 4.95 4.94 18 - 1,556.42 1,133.75 1,747.26 - 13.35 3.89 21.70 19 - 1,494.58 156.03 457.72 - 26.66 11.88 3.89 20 - 1,471.13 1,323.64 1,587.48 49.84 4.34 4.76 4.77 21 - - 1,132.25 1,422.36 - 8.45 7.92 10.42 22 - 1,549.52 1,296.35 1,055.47 25.47 4.38 4.65 5.08 23 - - 753.05 727.39 - 7.14 2.41 2.42 24 - - 711.89 755.30 - 8.29 3.07 5.81 25 - 606.42 1,654.57 - 685.59 2.62 4.63 13.23 26 - 1,739.03 1,103.72 1,237.65 - 7.01 3.04 5.15 27 - - 1,193.00 827.29 1,191.56 7.78 7.68 4.65 28 - 1,701.56 1,480.14 1,336.36 1,550.17 5.14 6.75 7.60 29 - - 1,478.13 1,373.58 24.06 4.41 6.50 5.83 30 - - 1,051.20 1,428.38 18.52 6.42 3.76 4.20 31 - 353.11 115.50 1,722.87 161.98 7.75 6.60 6.67 32 - - 292.02 1,004.17 - 29.57 127.56 144.17 33 - - 887.65 1,196.47 - 9.90 3.10 3.38 34 - - 789.29 825.19 - 5.21 2.31 2.35 35 - - 680.09 988.54 - 9.47 3.20 5.00 36 - - 1,011.33 1,127.02 - 14.79 4.76 10.34 37 1,546.59 727.96 1,367.75 1,539.05 7.41 2.17 1.41 1.89 38 - - 944.65 1,051.17 1,444.89 5.76 5.35 5.04 39 - 1,655.04 1,255.56 1,201.15 210.16 3.81 5.01 3.68 40 - 1,553.98 798.03 1,346.00 - 3.02 3.40 3.32 41 - - 910.09 900.26 1,339.80 7.40 2.51 1.95 42 - 1,588.72 1,444.92 1,498.58 - 282.98 5.35 4.05 43 - - 1,654.17 1,261.58 - 7.69 5.39 4.72
ID No Network α0 OR: White OR: BlackPCN-bmax PCN-bheur PCN-bmax PCN-bheur 1 - - 717.29 550.25 - 1,308.06 2 - - 7.64 53.68 - - 3 - - 310.45 455.50 - - 4 - - 10.95 8.91 17.15 19.88 5 - 1,699.97 883.03 373.53 1,407.40 1,716.12 6 - - 257.29 112.90 - - 7 - - 593.42 692.15 - 1,574.53 8 - - 678.70 760.72 - - 9 - - 249.15 318.21 - - 10 - - 720.91 743.88 - - 11 - - 859.67 670.63 - - 12 - - 251.54 314.89 960.04 701.50 13 - - 657.45 637.39 624.48 728.20 14 - - 112.69 80.58 - - 15 - 92.62 76.34 589.04 90.74 - 16 - - 865.33 670.93 - 803.47 17 - - 361.44 454.74 - 1,283.96 18 - 1,016.10 947.34 980.16 - 1,141.83 19 - - 930.83 927.06 - 1,562.77 20 - - 114.96 110.13 194.30 135.16 21 - - 859.63 594.28 - - 22 - - 710.73 408.30 - 1,404.40 23 - - 776.83 745.13 - - 24 - 397.35 923.48 - - - 25 - - 409.48 306.63 1,665.77 - 26 694.75 - 3.43 4.87 219.22 6.67 27 - - 166.86 88.92 32.27 73.49 28 - 813.48 590.50 576.55 1,420.97 1,189.86 29 - - 23.39 30.57 29.27 171.38 30 - - 516.90 376.76 766.32 976.99 31 - - 562.35 525.96 - 885.91 32 - 1,642.09 1,051.68 848.82 777.79 948.32 33 - 1,055.87 1,089.96 1,047.25 1,287.27 1,057.17 34 - 1,786.24 226.78 151.43 293.71 380.98 35 - 1,047.99 337.09 533.51 876.26 545.96 36 - 1,413.90 699.19 527.28 983.93 749.81 37 - 1,026.93 525.22 349.81 382.59 393.80 38 - 1,021.81 1,319.52 1,045.71 993.30 1,335.96 39 - 286.99 1,639.58 346.67 753.18 486.64
ID NDK 4TNo Network α0 PCN-bmax PCN-bheur No Network α0 PCN-bmax PCN-bheur 1 - - 452.58 250.79 92.40 34.36 14.90 10.23 2 - 1,089.85 287.76 486.31 19.31 5.97 6.27 13.83 3 - - 147.90 219.14 - - 5.95 4.52 4 - - 225.64 187.48 112.61 70.03 4.27 4.24 5 - - 373.72 214.83 57.89 17.62 6.50 6.62 6 - - 483.94 426.65 - - 13.08 13.44 7 - 1,050.54 150.95 111.42 67.48 5.39 3.35 3.98 8 - 500.92 290.77 174.87 64.05 4.71 5.57 3.01 9 - - 315.60 148.64 - 353.89 3.96 4.40 10 - - 131.21 129.81 62.44 29.35 4.42 3.10 11 - 228.54 381.68 344.47 6.07 3.10 5.48 5.29 12 38.44 8.55 204.32 171.83 2.44 2.28 7.15 7.14 13 - - 225.16 158.58 277.23 161.44 3.27 5.08 14 - - 386.61 428.26 87.17 16.28 4.99 5.81 15 - - 204.07 343.96 995.42 6.11 3.90 3.93 16 - - 553.34 422.95 935.03 12.68 6.53 9.81 17 - - 362.46 538.79 - 265.95 7.08 5.06 18 - - 213.73 69.44 - 7.56 3.39 13.55 19 59.33 169.88 289.70 244.17 2.69 4.76 6.78 9.13 20 - - 234.84 279.29 41.60 16.44 4.69 5.61 21 - - 701.95 230.92 - - 10.40 18.68 22 - - 267.92 94.72 952.18 6.51 4.23 4.37 23 196.64 171.50 339.06 160.70 2.71 2.58 3.18 4.25 24 - - 267.21 130.39 1,500.09 6.97 3.50 3.56 25 - - 1,344.21 373.23 - - 6.21 5.90 26 - - 533.24 175.49 137.86 4.40 3.55 5.78 27 - 572.92 400.28 96.45 43.25 8.08 3.15 3.15 28 - - 419.59 217.19 - - 4.55 4.88 29 - 309.18 645.21 236.40 6.10 4.11 7.44 6.59 30 - - 1,082.56 193.67 218.66 16.67 4.00 3.86 31 13.94 389.29 447.95 272.70 2.45 2.18 8.07 9.72 32 77.56 150.14 7.54 17.33 2.26 3.83 4.25 5.70 33 - - 108.39 187.57 - 1,036.16 3.24 4.62 34 - - 229.58 102.62 1,047.46 48.76 3.40 3.31 35 - 500.48 244.87 396.00 257.96 6.10 9.04 5.85 36 - - 1,476.63 1,135.60 259.40 1,704.00 13.61 6.96 37 1,708.60 159.03 39.99 35.99 45.19 2.53 2.72 2.51 38 - - 115.46 257.76 - - 8.38 12.98 39 - 462.48 462.54 168.51 12.81 4.15 3.53 4.46 40 - - 178.03 173.06 105.34 68.63 4.25 5.05 41 - 415.11 543.92 72.02 3.55 3.50 4.04 3.23 42 - - 1,322.47 152.56 1,748.07 712.34 4.53 6.47 43 - - 534.58 169.33 - 7.06 7.06 4.01
ID No Network α0 OR: White OR: BlackPCN-bmax PCN-bheur PCN-bmax PCN-bheur 1 - 123.57 - 240.92 - - 2 31.58 1,427.51 83.20 942.16 - 1,695.97 3 - 198.97 62.60 46.13 291.05 253.62 4 13.43 15.10 25.76 56.57 417.85 601.96 5 886.54 156.85 49.55 80.30 1,144.13 406.89 6 7.89 - 250.80 - - - 7 - 103.60 49.37 41.54 318.74 89.22 8 - 371.78 98.65 81.89 581.53 1,339.79 9 - 109.20 37.78 55.22 900.34 587.29 10 - - 153.40 - - - 11 - 84.11 725.33 463.33 - - 12 - 130.78 46.56 61.71 156.09 152.95 13 - 114.65 65.08 71.93 77.01 68.35 14 61.45 144.57 32.69 37.78 334.21 - 15 54.44 - 624.53 - 431.13 - 16 - 85.17 56.61 73.32 732.51 680.38 17 - 119.74 65.52 51.85 261.32 314.09 18 - 434.44 385.28 766.47 - 1,041.93 19 - 284.36 166.35 179.28 549.76 446.55 20 - 64.16 51.23 77.72 901.22 51.33 21 - 273.99 384.46 101.71 - - 22 - 69.99 325.36 38.38 331.10 83.25 23 - 219.83 148.88 105.60 - 921.71 24 - 66.71 - 104.04 1,166.18 728.24 25 231.02 82.18 75.33 74.93 278.38 157.90 26 3.20 183.71 319.49 119.51 338.69 225.64 27 26.03 20.94 31.05 26.29 31.74 28.56 28 - 104.69 75.16 73.88 1,093.91 246.79 29 16.22 24.03 6.18 5.83 25.89 31.84 30 623.01 24.35 40.71 39.76 115.49 70.90 31 - 144.15 183.09 60.75 205.21 624.58 32 - 221.47 74.58 68.91 453.48 194.93 33 - 582.08 477.68 142.69 377.24 301.71 34 960.28 91.37 172.93 42.44 186.74 - 35 1,198.23 104.04 121.52 85.38 1,052.79 203.96 36 - 151.65 184.78 128.23 - 545.87 37 - 434.39 185.82 39.34 38.79 57.92 38 - 183.02 73.48 88.23 148.20 93.28 39 86.48 50.87 314.47 232.05 440.41 61.29

Review summaries:
This paper uses a modified AlphaZero MCTS training loop to generate proof tree size heuristics, for use in MCTS or proof number search (PNS). The authors demonstrate that both heuristics outperform no heuristic and a existing heuristic method based off of standard search policy and value functions. The ideas and results are a nice step forward in a search domain that is is not always well-addressed by classical value-maximising search.

This paper focus on solving a game, i.e. deciding the win/lose outcome for each game state. In order to finish the task in limited time, it is necessary to expand as little leaf nodes as possible when searching on the game state tree. The number of such leaf nodes is defined as proof cost and the paper proposes to set it as the new learning target based on the AlphaZero learning framework. Experiments are conduct to verify the ability of the model by solving $15 \times 15$ Gomoku and $9 \times 9$ Killall-Go games in limited time.

As we know that, from AlphaGo to AlphaZero, less and less expert knowledge is used. In this paper, however, the authors make AlphaZero becomes faster by modifying the training target of the AlphaZero algorithm, such that it prioritizes solving the game quickly, rather than winning, and training knowledge-based networks. Experimental evaluation is provided on 15x15 Gomoku and 9x9 Killall-Go problems.