Game Solving with Online Fine-Tuning
Authors: Ti-Rong Wu
Hung Guei
Ting Han Wei
Chung-Chin Shih
Jui-Te Chin
I-Chen Wu
Venue: NeurIPS 2023 poster (2023)
Keywords: Game Solving
Computer Games
AlphaZero
Online Fine-Tuning
Monte Carlo Tree Search
Deep Reinforcement Learning
TL;DR: This paper proposes methods for game solving with online fine-tuning; namely, while solving, we simultaneously use an online fine-tuning trainer to fine-tune heuristics to provide higher accurate evaluations.

Abstract: Game solving is a similar, yet more difficult task than mastering a game. Solving a game typically means to find the game-theoretic value (outcome given optimal play), and optionally a full strategy to follow in order to achieve that outcome. The AlphaZero algorithm has demonstrated super-human level play, and its powerful policy and value predictions have also served as heuristics in game solving. However, to solve a game and obtain a full strategy, a winning response must be found for all possible moves by the losing player. This includes very poor lines of play from the losing side, for which the AlphaZero self-play process will not encounter. AlphaZero-based heuristics can be highly inaccurate when evaluating these out-of-distribution positions, which occur throughout the entire search. To address this issue, this paper investigates applying online fine-tuning while searching and proposes two methods to learn tailor-designed heuristics for game solving. Our experiments show that using online fine-tuning can solve a series of challenging 7x7 Killall-Go problems, using only 23.54\% of computation time compared to the baseline without online fine-tuning. Results suggest that the savings scale with problem size. Our method can further be extended to any tree search algorithm for problem solving. Our code is available at https://rlg.iis.sinica.edu.tw/papers/neurips2023-online-fine-tuning-solver.

Game Solving with Online Fine- Tine-Tunnig
Ti-Rong Wu," 1- Hung Guei," Ting Han Wei, Chung- Soung-Chin Shih, Jui-Te Chin," I-Chen Wu
"Intitttee of Information Science, Academia Sinica, Taiwan Departmennt of Computing Science, University Alberta, Canada Depaatmeet of Computer Science, National Yang Ming Chiao Tung University, Taiwan 'Research Center for Information Technology Innovation, Academia Sinica, Taiwan
tirongwuliie sinica. edu. tw, bgueiRiis. www.iaiiiic...mmmm edu. tw, tinghanQualberta. rockmanray.. catimanray.cc220yyeea. www20nycu. eew.yccueedd........ pikachin betaccin.caao0nyee. cs10@nycu.edi edu...edu.bbe tw, icsuêcs wwt.cc..ncccc... actu.edu. tw
Abstract
Game solving is a similar, yet more difficult task than mastering a game. Solving game typically means find the game-theoretic value (outcome given optimal play), and optionally a full strategy to follow order to achieve that outcome. The AlphaZero algorithm has demonstrated super-human level play, and its powerful policy and value predictions have also served as heuristics in game solving. How- ever, to solve game and obtain full strategy, winning response must be found for all possible moves by the losing player. This includes very poor lines of play from the losing side, for which the AlphaZero self-play process will encounter. AlphaZero-baat -aazed heuristics can be highly inaccurate when evaluating these out- of-distribution positions, which occur throughout the entire search. To address this issue, this paper investigates applying online fine-tuning while searching and proposes two methods learn tailor-designed heuristics for game solving. Our experiments show that using online fine-tuning can solve series of challenging 7x7 Killall-Go problems, using only 23.54% of computation time compared to the base- line without online fine-tuning. Results suggest that the savings scale with problem size. Our method can further be extended to any tree search algorithm for problem solving, Our code is available at https://rlg. iis iis.sinnia.eee. wwwpiii..e..tt/ppppppeeeeeeeeeee http://siiiiiiii......////e/ee/p online-fine-une fintte-iin-tunin--Soo
Introduction
Playing and solving strategic games have served as drivers and major milestones I in artificial intelligence research. To master such games, the objective is often designed to optimize on the objective of maximizing the probability of winning. In the past several decades, researchers made sig- nificant progress game playing, reaching super-human playing levels many domains. Successful examples include Chinook (checkers) 2 Deep Blue (chess) 3. AlphaGo (Go) 14, and AlphaStar (StarCraft II) 5) Furthermore, AlphaZero G and MuZero even boast generality by mastering variety of games without requiring expert human knowledge. Although these learning-basee agents have progressed dramatically in playing strength, there are no guarantees that their decisions are always correct 9 [0] in terms of game-theoretic value, which is defined as the outcome of the game given optimal play for both players. Game solving this pursuit of finding game-theoretic values.
Game solving is more difficult challenge than game playing. Many seemingly simple games have astronomically large state spaces, with no simple way of exploring this space. Here where
These authors contributed equally.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

advancements in game playing can aid game solving, Strong agents are commonly leveraged to evaluate positions, providing guidance and reducing the search space significantly. For example, the checkers program Chinook claimed to have reached super-human levels as early as 1996 (2), then about 10 years later, played an instrumental role in the proof that checkers is a drawn game [[]. Similarly, contemporary learning-based approaches such as AlphaZero are widely used to help reduce the search space for game solving. Game solvers that utilized AlphaZero include Hex [12]. Go [3), Killall-Go [14), and the Rubik's ' cube [15 [6]. Such approaches are not limited to applications in games but extend to other non-game fields, like automated theorem proving 117.
However, major issue still exists when using learning-bass approaches to aid game solving, In the two-player, zero-sum setting, a simple description for a proof involves verifying that there is a winning move for the winner, for all possibilities played by the losing side; i.e. no matter how the loser plays, the winner must be able to respond correctly. However, most learning-based agents are trained along strong line of play by both players, with some exploration to nearby states for robustness. Using AlphaZero as an example, training samples are generated via self-play by the best version of itself up to that point. Learning-based methods are powerful in that they generalize for previously unseen positions, but accuracy tends to drop the further you stray from training samples. To verify all possibilities on the losing side, the vast majority of positions we must evaluate during the search for a proof are therefore out-of-distribuute to make inconsistent or completely incorrect evaluations, simply by adding two meaningless stones to a position [0]. In another example, in the attempt to solve one of the hardest Go life-and-death (L&D) problems from the famous book Igo Hatsuyoron ! all AlphaZero- like programs failed. It was hypothesized that this was because these highly specific problems are rarely encountered during training (18)
To illustrate, AlphaZero-lin
networks have been shown
This paper proposes applying online fine-tuning methods to train learning-basse -baedd systems while solving games. In our proposed methods, during game solving, online trainer is added so that the learned heuristic is improved as new data that is relevant to the solving task is generated. This is done by utilizing new information such as solved and critical positions in the current solver search tree. The trainer therefore can learn better heuristics dynamically, that are particularly fine-tuned for the upcoming evaluations. Experiments are conducted on 16 challenging 7x7 Killall-Go three-move openings, shown in Figure 3 We develop a distributed game solver with online fine-tuning, that is built upon the state-of-the-art 7x7 Killall-Go solver [3]. Experiment results show that the online fine-tuning solver can greatly reduce the search space by factor of 4.61 on average. Namely, it searches only 21.69% of nodes, using 23.54% of the computation time, as compared to the offline solver. Most importantly, for larger problems, the online fine-tuning solver performs significantly faster than that without, which implies that our method scales with problem size.
2 Background
2.1
Game solvers
A two-player zero-sum game is considered solved if we know of a winning strategy for either player which guarantees a winning outcome regardless of how the opponent plays; i.e. the player must have at least one action that leads to win, for all actions by the opponent. A winning strategy is often represented as an AND-OR tree called a solution free [19], where the game positions with the winner to move are represented by OR-nodes, and those for the opponent by AND-nodes. Leaf nodes in solution tree are all terminal positions where the outcome is a win.
A solver is program that does a proof search and can identify winning strategy or solution tree, if found. Solvers often rely on heuristic tree search for games with large and complex game state spaces. Search algorithms such as alpha-beta search (20). proof number search (PNS) 21I, or Monte Carlo tree search (MCTS) [22 23 have all been shown to be successful. In addition, previous research has
shown that none of the algorithms dominates the others 24 25 14
"Igo Hatsuyoron is classic collection of L&D problems in Go, which demand complex calculations to solve. L&D problems are puzzles that test your ability identify the safety of specific pieces in given game position. 'We only consider "weak solutions" 0 in this paper. where different opening positions are treated as independent sub- games. Draws are also not considered, but can be determined via two searches, one for each player. If both outcomes are losses, then it must be draw.

---

2.2 Distributed game solver
In cases where search spaces are too large for single instance solver under reasonable time and memory constraints, multiple solvers are often run in parallel, forming distributed computing system, to scale up the solving process. Examples of games solved by distributed computing include checkers
[1. heads-up limit hold'en em poker [26], breakthrough (27. Hex (28). and Connectó [25] [2]].
These distributed game solving/analysis systems, also known distributed game solvers, have been presented commonly with two components, a manager and a set of workers. A manager divides the overall problem into smaller sub-problems. keeping only the initial portion of the search tree the beginning of the game in memory. As this search tree is expanded, the manager may decide to offload analysis of specific positions to workers. These offloaded sub-problems are also called jobs [25 [29]. A worker computes jobs by taking as input, specific position and any relevant parameters (e.g. time limits), then outputs either a solved or heuristic value for that position. A worker can be single solver, a game engine, or even combination of both.
For example, in the checkers proof, Chinook and another depth-first proof-number search 30] solver were combined as a heuristic. From the perspective of the manager, solved job result, such as proven win, loss, or draw, can be thought of terminal node in its solution tree. Unsolved jobs also provide useful information, such as heuristic values to determine likely win or likely loss, to guide further tree expansions, with the worker acting as a relatively expensive and accurate heuristic. Similar to the checkers proof, Connectó openings have also been solved by encapsulating the task of solving and playing position into single job, which was then dispatched by manager to a set of workers 225 29 31 In all examples listed above, centralized scheme is used where one manager coordinates between dozens to hundreds of workers.
2.3 Proof Cost Network
When using neural networks as heuristics in solving, recent research points out that there is room for improvement when using the value network learned from the AlphaZero algorithm| [16] [4]. In a search tree, when several actions reach winning outcome, AophaZero-trainee networks have no preference for choosing one that wins fastest. This can increase the amount of computation significantly.
To address this challenge, the Proof Cost Network (PCN) [4] predicts a proof cost value, rather than win rate. The cost value represents Dogarichmicall--nomaaizz
estimate of the number of nodes that are required to solve the position. Specifically, PCN adopts the AlphaZero training process and generates self-play games using the cost value to guide the MCTS toward faster winning moves. These self- pely games are then used to update PCN's cost values. The resulting network will focus the proof search actions with minimal cost. Experiments show that the proof cost value is highly correlated to problem difficulty, and can significantly improve solving capability.
3 Game solver with online fine-tuning
This section describes our methods for applying online fine-tuning to game solving. We chose an MCTS-based solver due to its popularity when integrating AlphaZero networks heuristics 16 1 14] However, it worth noting that the methods presented in this paper are search- independent and can be readily applied other search algorithms such as alpha-beta search or PNS.
3.1 Distributed game solver
Our distributed game solver consists of a PCN serving as its heuristic, a manager, and a set of workers. The manager maintains an MCTS rooted at the position to be solved. During the proof search, the manager follows PUCT [32] selection to traverse from the root PCN estimates the cost of the selected leaf node, denoted by ty. 2/ is a heuristic value representing the log estimated number of positions that must be examined to solve this node. If the value is larger than designated threshold, i.e. e 2 Uthe. its proof cost is considered too high to warrant job. The manager will then continue to follow MCTS, expanding the node and backpropagating v to the root. Alternatively, if on < Vthr. the leaf node is highly likely to be solved outright by worker, which
leaf node. Next, the
3

---

(a) Managar
(l)) Wirkess
Jobs
a
C
Solutions
MCTS Selection Path
Splvod
Wirker
g
Selection 1: r g.
Selection r
j
k
Selection 3: kn
Salved
Queee
Models
Selection 4: r
Postior
Sai-Paay
Selection b
Tuaiing
Selection r
(c) Online Fine Tuning Thains
Figure 2: A manager AND-OR tree with six MCTS selection paths. Positions and j are solved this tree.
Figure 1: The online fine-tuning game solver architecture.
point a job is created. Job granularity is therefore controlled with Uehr- Larger Ushr generates more difficult jobs with higher failure rates, while smaller Uthr leads to easier but more numerous jobs. A balanced Var should be set according to the game instance and worker capabilities.
Workers are game solving programs that are limited by specific constraints, say, a given time limit, To keep the heuristic consistent during the proof search, workers use the same PCN weights as the manager. If the job is solved within the given constraint, the worker returns the result, either win or loss, back to the manager; otherwise, returns an unknown. Once the manager receives the job result, it updates the search tree accordingly. For unsolved jobs, the manager expands the nodes that generated the corresponding jobs. The interaction between the manager and the workers is shown between Figure a and [b).
3.2 Online Fine- Tuning Trainer
The Online Fine- Tuming Trainer (OFT) maintains the PCN during the proof search that the manager and workers have access to ever improving heuristics. Without online fine-tuning, both the manager and workers simply
fixed PCN, denoted by On. trained via the AlphaZero self-play process. The OFT starts with dp. then fine-tunes the weights via updates during the proof search. To do this, the manager picks out solved and/or critical positions in its search tree, adds them to the list of training samples, then the OFT uses them to perform self-play and training. The fine-tuned PCN (0,, O2,,.., ...) can then be used further guide the manager and workers towards faster proof. The manager and workers update to the most recent 0, immediately when a new PCN checkpoint trained by the OFT. The above iterative process is shown in Figure Details are provided in the following sections.
3.2.1 Online fine-tuning trainer with solved positions
During the proof search, many previously unsolved positions may become solved in the manager's search tree. This new information can be used by the OFT to improve the accuracy of the PCN. F an example of manager's AND-OR search tree and six recent selection paths. In this example, positions j and d are marked as solved and sent to the OFT after the first and fourth selection, respectively. The OFT maintains queue that stores these solved positions, shown in Figure C).. Self-play games are generated as in normal PCN training [4]. However, in the optimization phase, the OFT randomly samples training data not only from the generated self-play games, but also from the queue of solved positions. For these solved positions, the cost values are always set zero (i.e. solved be win, from the perspective of the OR-player). since no nodes need to be examined to solve the position. The OFT only samples 10% of training data from the solved queue during optimization to avoid overfitting, where the remaining 90% are sampled from self-play -laa games. In addition, the queue only stores the most recent 1,000 solved positions received from the manager. During self-play, when using 0, to evaluate positions that are solved by the manager, is highly likely to predict costs close to zero. From the AND-player's perspective, it favors moves that lead to larger costs to delay the OR-player's victory. Therefore, self-play naturally explores positions which have not yet been solved in the manager's 's search tree.

---

3.2.2 Online fine-tuning trainer with critical positions
Other than solved positions, we can also improve the PCN with specific positions of interest chosen from the manager's 's current search tree. Positions are considered critical if they are selected in the most recent MCTS iterations in the manager. For example, in the first selection in Figure 2 all positions r, a, 9. and j in the MCTS selection path are considered critical positions. During sell-paay, the trainer randomly chooses one critical position, and performs self-play starting from that position. Thus, 9g can provide more accurate predictions for positions that proof search is currently exploring.
A more selective process can be used to improve the quality of critical positions. First, we can omit since self-play from r is already performed to train 0p. Ideally, we would prefer to focus on deeper unsolved positions. To achieve this, we only consider the leaf position in the selection path critical. Also, the OFT maintains a queue in which only the recent 1,000 critical positions are stored. This way, the OFT can focus on the most urgent positions which are likely to be solved soon. As these positions are also usually sent to the workers (if the PCN value v S Uphr), the workers can also take advantage of Oz. Next, we can omit leaf positions solved solely by the manager; i.e. leaf nodes that were solved not as jobs. For example, j will not be considered critical in the first selection in Figure Since j is already solved, it not necessary to perform self-play from that position. Only m, n, h, and i will be sent to the OFT as critical positions in the second, third, fifth, and sixth selection, respectively. Note that r. o, and g were critical positions before and k became critical, since the parent nodes are always expanded before their children. Thus, the trainer will gradually fine-tune the PCN by focusing only on deeper critical positions to help avoid redundancy during fine-tuning.
In summary, the pre-trained Og learns general heuristics by exploring from empty games, while the online 0g refines its heuristics for specific positions of interest. As a side note, the fine-tuning process is related to the catastrophic forgetting phenomenon [3 as the focus is shifted from one part of the proof search another. Interestingly, forgetting is not only acceptable in this context, but probably even preferred, because the heuristic only needs to be accurate for the part of the search space the manager currently working on. Additionally, the two proposed methods are independent and can be combined. We evaluate these methods in our experiments.
3.3 Manager job assignment improvements
Job assignment refers to the manager's ss responsibility of dividing the overall problem into distinct jobs. Better job assignment schemes can eliminate redundancy and improve parallelism. We propose three techniques to further improve the efficiency of job assignment, which we call virtual solving, top-k selection, and AND-player job assignment.
Virtual solving. When a job is assigned to workers, we assume that the job result will be solved, even before it is actually returned by a worker. The virtually solved outcome backpropagated as a normal job outcome. This technique has similar concepts to the virtual loss (34). virtual win [29]. and Young Brothers Wait Concept (YBWC) (35), which were used to avoid repeatedly searching superfluous nodes during the proof search. For example, in Figure 2 assume the manager selects a path from r to leaf h and assigns the job to a worker, at which point h is immediately marked as virtually solved. Its parent node b, an node is then also marked as virtually solved. Furthermore, if nodes a, c, and e (d is solved already) are all solved or virtually solved, their parent will also be marked as virtually solved. When the job result returns, the manager reverts the virtually solved markers and updates the status of all nodes accordingly. The virtual solving technique can provide a highly efficient job assignment scheme, in that the manager search tree can be nearly the same as the solution tree if most virtually solved nodes are indeed winning.
Top-k selection. We exploit the fact that all child nodes must be solved for every AND-node to improve parallelism. At each AND-node, we select uniformly at random among the top k unsolved children that are likely to be sent off as jobs eventually, i.e. those with the top 1 highest PUCT scores. For example, in Figure 2 assume i- = 2 and nodes a and b are the top two children of AND-node r: nodes l and I are the top two for g. Note that we omit node because it is already solved. At node the manager selects between a and b with equal probability. Note that selections at Oodes remain unchanged. In addition, we only apply top-k selection when the simulation count of the AND-node larger than k. Top-k selection improves parallelism by allowing the manager to assign more jobs simultaneously, when it is combined with virtual solving. We use A = 4 in our experiments.
5

---

AND-player job assignment. We only distribute AND-nodes as jobs, i.c. OR-nodes are never assigned and are directly expanded in the manager. For example. in F2 the -R-node b is not assigned job even if < Wthr- The manager creates the AND-node h from the leaf node b, then assigns to a worker as a job. The underlying intuition is that assuming the PCN policy head output is accurate as a move ordering heuristic, the first guess will often be the move that leads to solution for Oo-nosss Therefore, by skipping OR-nodes job assignment entirely, the manager gains a 1-ply look ahead. In practice, all three job assignment schemes are applied simultaneously.
4 Experiments
We demonstrate our online fine-tuning game solver by solving several three-move 7x7 Killall-Go openings. 7x7 Killall-Go is a variant of Go, where the rules are the same except that: (a) Black places two stones initially, and (b) Black wins if all white stones are killed; otherwise, White wins. Since White aims to live, winning specific openings for this variant is equivalent to solving a L&D problem. Many Go experts believe that 7x7 Killall-Go is a win for White. So far, no proof has been published yet. In this paper, we only focus on weakly solved games [3 in which White wins. Thus, White is considered the OR-player throughout.
4.1 The 7x7 Killall-Go solver
We build our 7x7 Killall-Go solver upon an AlphaZero training framework (37. First, we pre-train a PCN 0p [4] to serve as heuristics for the game solver (starting from an empty board). We incorporate the Gumbel AlphaZero algorithm [38] into PCN training, since it performs equivalently well even with a small simulation count. This reduces the computation cost for online fine-tuning without compromising accuracy. The pre-training took around 52 1080Ti GPU-hours. Next, we incorporate several useful techniques into the solver to accelerate solving. This includes relevance zone-based search (RZS) [ zone pattern tables [39], and GHI handling to deal with cycles in Go 40. This solver is then used as workers in a distributed game solver. The manager is also based on the above
solver, with the job assignment techniques added, described in subsection 3.3 The OFT is similar
to the PCN pre-training, but with fine-tuning as described in subsection 3.2
Two kinds of distributed game solvers are considered for our experiments. The baseline solver uses the manager and worker only, while using pre-trained, fixed 9g as the heuristic throughout the whole proof search. In contrast, the online dynamically during the proof search. addition, we consider three variations of online fine-tuning solvers using solved positions (SP), critical positions (CP), and combination of both (SP+CP). Both solvers use Uthr = 16.5 for the manager job granularity f For fairness, we ran both solvers on 1080Ti GPUs. The baseline solver uses GPU for the manager and eight GPUs shared among workers. For the online fine-tuning solver, the manager and trainer each uses one GPU, while workers share the remaining seven GPUs. Detailed implementations and other machine configuration details are specified in the appendix.
solver uses the OFT to fine-tune the PCN heuristic
B
(a) Jump (J)
(b) Knight's 's move (K)
(c) Diagonal jump (D)
(d) Stretch (S)
Figure 3: Four 7x7 Killall-Go opening groups including (a) four openings, JA-JD; (b) six openings, KA-KF; (c) one opening, DA; (d) five openings, SA-SE.
We select a set of three-move openings based on recommendations from experts, including profes- sional 9-dan player. These openings can classified into four groups, named after their commonly
We choose vtrr 16.5 according the experiments on different PCN thresholds, shown the appendix.

---

shared first move opening: jump (J), knight's move (K), diagonal jump (D), and stretch (S), shown in and respectivve.. For each opening group, experts also suggest the most likely winning move for White. We split these openings into several three-move openings by exploring Black's possible replies. For each opening group, we select the most difficult replies by Black according to expert recommendations and the PCN policy head output. For simplicity, in the rest of the paper, JA represents the position resulting from Black playing at A in the jump group; KB represents Black playing B in the knight's move group, etc. The gray solid squares represent moves that are also suggested by the PCN, but cannot be solved by both of the baseline and online fine-tuning solvers in one day. With limited computing resources, we leave these openings for future work. In total, we use 16 three-move openings as shown in Figure 3
Figure 3b 3d
4.2 Baseline versus online fine-tuning
Table/[list statistics for solving the 16 three-move openings by the baseline solver and three variants of online fine-tuning solvers. In general, all online fine-tuning solvers outperform the baseline solver in most openings. ONLINE-SP, ONLINE-CP, and ONLINE-SP+CP, require only about 48.53%, 21 21.69% and 23.07% of the visited nodes, and 52.67%, 23.54%. and 24.99% of the computing time compared to BASELINE. This shows that fine-tuning PCNs with critical positions, which are currently being solved by either the manager or workers, provides better hcuristics for the current search tree and accelerates the solving process. Furthermore, ONLINE-SP+CP has nearly the same performance as ONLINE-CP, with both methods outperforming ONLINE-SP. This means that training with critical positions is more important than solved positions. To reduce the overhead of sending both solved and critical positions, we simply choose ONLINE-CP CP for further analysis, i.e. all instances of online fine-tuning solver for the rest of this section refers to ONLINE-CP. In conclusion, these results indicate that On provides less accurate heuristics, which impacts the proof search negatively. By performing online fine-tuning with either solved or critical positions, we can fine-tune the PCN dynamically according to the manager's current focus and therefore find faster solutions.
Table I: The number of nodes and time to solve 16 7x7 Killall-Go three-move openings by the baseline and three variants of online fine-tuning solvers. "# Nodes" lists the numbers of all nodes visited by the manager and workers together. All the listed times are rounded to the nearest second. The rightmost column lists the number of PCN models produced by the online fine-tuning trainer.
BASELINE
UNLINE-SP
UNLINE-UP
UNLINE-SPACP
# Nodes
Time (s)
# Nodes
Time (s)
# PCN
# Nodes
Time (8)
# PCN
A Nodes
Time (s) # PCN
8,964,444,59
142.115
4,054,562.593
69,699
1,288,601445
22,384
1,425666871D
24,865
JB
7.137,514.712
155,786
3,378,672.517
83,454
424
1,576,437,133 139
31.957
272
1,601449,130
31,455
283
JC
721 721.004,784
12.514
819,264.890
13,963
57
316.391.324
6,537
59
414,108, 746
8.343
69
1,271,426.148
30,209
846.365.092
19,396
113
545,655,175
11,083
102
502.966,563
10,896
103
KA
134,881 1,922
2,103
143.814,448
2,621
14
111.8 838,838889
2,102
18
104,905,173
1,931
18
10,153,035.63 633
156,583
3,794.290, 131
64,493
305
2,242,789,14
38,947
2,527 177,4888112
43,200
386
KC
38,217,263
747
45.217. 101
1,156
26,441,980 .989
758
25, 25,508,784
706
KD
2,754,213,379
47,494
1,504,977,329
25,715
126
955,257, 191
17,434
145
920,902,808
16,357
148
1,197,819441
18.771
214.614,577
3,917
21
889,4
3,336
168_590,287
3,095
28
KF
9,516,440,39 440
147,271
6,080.836, 868
100,690
$19
2,107, 185, 330
35.418
285
2,027,558,510 555,,00
35.197
305
DA
7.332,743.383
112,874
3,015,438.589
50,046
248
L,761,8224777
30,313
266
1,665,511,033
28,337
235
$1,272,288
937
$4,574,495
1,471
41,863,49 480
992
41,796,555
1.105
10
SB
215,380, 103
3,860
65.970.358
1,423
7
55,541.455
1,364
12
109 (19.591155 487
2,258
20
97,559,402
1,557
213.889.777
3,553
95,561,355
1.715
83,
15
SD
8.187.017.65
124,644
3,821.472.453
63,058
329
1,395,444.447
23,751
154
1.485 4.39 307
25.531
224
SE:
4,297,808,88 808, 879
64,227
2,065,528.927
33,437
166
757,256,934
12,465
103
1,200,741, 176
20,428
182
62,060,780,990
1,021.692
30,119,490.445
538,092
13,462,626.704
240.556
14.315.792.186
255.359
Table I also shows another interesting result: the larger the problem, the better the improvement. For better visualization, the solving times are depicted as a bar chart in Figure 4 where the x-axis is sorted according to the solving time of the baseline solver. In Figure 4 the online fine-tuning solver solves all openings within 40,000 seconds, while the baseline solver uses more than one day to solve six openings. Most impressively, for JA, the online fine-tuning solver performs about 6.35 times faster than the baseline, reducing the computation time from 142,115 to 22,384 seconds, while the number of visited nodes is reduced from 8.96 billion to 1.29 billion or so nodes.
The online fine-tuning solver does not always perform better than the baseline, especially when the openings are relatively easy to solve for the baseline. In Table the baseline uses less time to solve SA and SC. The following reasons may be why this limitation exists for smaller problems. First, the
7

---

160,000
BASELINE
ONLINE-SP
140,000
ONNINNE-C
ONLINE-SP+CP
120,000
100,000
Time (s)
80,000
60,000
40,000
20,000
0
SE
DA
Figure 4: Solving time comparison for three-move 7x7 Killall-Go openings.
(b) Average length of critical positions. Figure 5: Behavioral analysis of the online fine-tuning solver for the opening JA.
(a) Sub cub-position of JA.
online finettuning solver relies on trainer to fine-tune the PCN. The quicker the problem can be solved, the less time the trainer has to fine-tune specific PCN weights. Consequently, it has weaker impact on improvement. This is corroborated by the fact that these two openings end up with less than 20 PCN versions as shown in Table 1 Second, when compared the baseline, the online fine-tuning solver has less computing power for the workers. The trainer overhead takes up GPU and leaves workers with seven instead of eight GPUs used by the baseline.
also worth mentioning that all three-move openings in both jump and stretch are solved. As these openings are considered the most difficult moves, we expect that both jump and stretch (i.e., the two-move openings) can probably be solved completely the near future, with more computing resources.
4.3 Behavior analysis for the online fine-tuning solver
We further analyze the behavior of two solvers by studying the opening JA, where the online fine- tuning solver has the largest speedup among all openings, i.c. 6.35 times faster than the baseline. We observe several positions in which the winning moves for White differed between the two solvers. For example, crucial sub-position in the solution tree is shown in Figure 5a The baseline and online fine-tuning solver chose moves and to search, respectively. We examine Og and find that the
In settings, the trainer typically generates PCN version about every 120 seconds.

---

probabilities from the policy network for moves A and B are 0.416 and 0.133, respectively. As result, the baseline solver has lower chance to explore B. contrast, with the help of the OFT, the online fine-tuning solver quickly realizes that solving B is faster, though it still attempted to search A initially, as it starts with the same On. In terms of node counts, the baseline spent a total of 1.6 1.63 billion nodes, with approximately 1.48 billion (91.00%) and 35.50 million (2.18%) nodes spent on searching A and B, respectively, while the online fine-tuning solver spent a total of 136.47 million nodes on that position, with approximately 22.13 million (16.21%) and 95.17 million (69. 74%) nodes spent on searching A and B, respectively. This example clearly demonstrates the advantage of using the OFT.
Next, we investigate the set of critical positions maintained by the online fine-tuning trainer, as described in subsection B.2.2] During fine-tuning, the trainer randomly selects positions from the queue, then runs self- play games from these positions. Figure 55 shows the average path length of critical positions during training in the y-axis, and the training iteration in the x-axis, where the trainer generates a new PCN version for every iteration. The length starts at around 10 and gradually increases to nearly 25 in the end. This is because as the manager search tree grows through node expansion, the critical positions are chosen from deeper parts of the tree. The curve also fluctuates as the proof search progresses. This is because the manager tends to focus on a sub-problem at a time. When a subtree is solved, the manager may then shift its attention to other unsolved parts of the proof search, which can have a relatively shallower depth. We also analyze similar figures for other openings in the appendix.
4.4 Updating PCNs in online fine-tuning
We investigate the impact of updating PCNs for the manager and workers during online fine-tuning. We select four openings, JC, KE. DA, and SE, one from each opening group, for this experiment. Table Table(2summn summarizes results, where BASELINE denotes the baseline solver, ONLINE-CP denotes the online fine-tuning solver that updates PCNs for both the manager and workers (as described in subsection 3.2.2). ONLINE-CP-M denotes updating the PCN for the manager only, and ONLINE-CP-W for workers only.
First, updating PCNs for both the manager and workers performs the best. By using consistent PCNs, jobs assigned by the manager are efficiently solved by the workers. With inconsistent PCNs, the results can be even worse than the baseline. Generally, ONLINE-CP-M outperforms ONLINE-CP-W- except for the opening SE. We find that the pre-trained PCN causes ONLINE-CP -P-NE w to divide its computing resources across several OR nodes (white moves), many of which are relatively difficult to solve. contrast, for ONLINEE-CP-I M, with the updated PCNs, the manager focuses on one white move (or a smaller number of white moves), of which they are much easier to solve. Thus, even if there a mismatch between the manager and workers in ONLINE-CP-M, focusing on one good white move can still result in efficiency.
Table 2: Impact of updating PCNs in the Table 3: Ablation study for job assignment schemes in online fine-tuning solver. The number repre- sents the time (in seconds) for solving each opening by using different methods.
the online fine-tuning solver. The number represents the time (in seconds) for solving each opening by using different methods.
KE
JC
KF
DA
SF
BASELINE
12,514
18,771
112,874
64,227
ONLINE-CP
6,537
3,336
30,313
12,465
ONLINE-CP-M
9,992
5,445
46,719
28,769
w/o AND assg.
8,618
3,762
53,275
18,926
ONLINE-CP-W
13,516
54,360
65,304
26,168
w/o top-k
6,520
3,639
46,080
36,093
ONLINE-CP
6,537
3,336
30,313
12,465
w/o AND assg. & top-k
10,480
6.171
58,527
33,677
4.5
Ablation study for job assignment schemes
We conduct an ablation study in the online tne-tuning solver to analyze the impact of job assignment
schemes, described in subsection 3.3 We only include ablations for top-k selection and AND-player job assignment, since virtual solving required to avoid job redundancy. The ablation study is performed on the same four openings as subsection 4.4 JC, KF, DA, and SE. Table Jaumarissss the ablation results, where ONLINE-CP denotes the online fine-tuning solver that uses both schemes; the other three versions denote the ablations by removing specific schemes from ONLINE-CP. If the top-k

---

selection is removed, the manager always selects the best child during selection for both AND-nodes and -odes.. we do not follow the AND-player job assignment scheme (abbreviated as AND assg. in the table), the manager assigns both AND-player and OR-player jobs.
From Table ONLINE-CP performs the best in general. In particular, ONLINE-CP only requires around 48.37 3%% of the computing time on average over all four openings, compared to the solver without both schemes (the last row in the table). When comparing each technique individually, the improvement varies from problem to problem.
5 Discussion
This paper demonstrates the potential of using online fine-tuning for game solving. On average across multiple openings, our proposed online fine-tuning solver only uses 23.54% of the computation time compared to the baseline. Our distributed game solver is the first online fine-tuning method for problem solving based on AlphaZero-like algorithms. Although we focus on online fine-tuning throughout this paper, we can also claim that the complete distributed game solver life-long learning system. The online trainer continuously refines heuristics for unfamiliar (unsolved) positions, and forgets the previously learned knowledge (solved positions). However, this forgotten knowledge is saved (remembered) in the manager's 's solution tree. As result, the worker and trainer will not need evaluate these positions again.
There are many other topics for future investigation. Our experiments on the four challenging 7x7 Killall-Go opening groups show that two groups likely be solved in the future. However, for the other two, or even 7x7 Killall-Go in its entirety, we expect more novel techniques are needed. As for the standard Go game, the largest solved board to date is only 5x6 in size [41], with no published progress in 14 years. We expect online fine-tuming to one of the key improvements that can help push this boundary. As for generality, our method is not limited Go but can be easily applied to other two-player zero-sum games like Hex or Othello. Moreover, we expect it has the potential to extend to single-player games such as Rubik's Cube, even other non-game fields, such as automated theorem proving [17 or chemical syntheses 42 43
Acknowledgments and Disclosure of Funding
This research is partially supported by the National Science and Technology Council (NSTC) of the Republic of China (Taiwan) under Grant Number NSTC and NSTC 111-2634-F-A49-013.
NSTC
NSTC
References
[1] 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):27-3311, 2002.
[2] Jonathan Schaeffer. One Jump Ahead: Challenging Human Supremacy in Checkers. ICGA Journal, 20(2):93-92 93, 1997.
[3] Murray Campbell, A Joseph Hoane Jr. and Feng-hsiung Hsu. Deep Blue. Artificial intelligence, 134(1-2):577 83, 2002.
[4] David Silver, Aja Huang. Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driess- che, Julian Schrittwieser, loannis Antonoglou, Veda Panneershelvam, Mare Lanctot, et al. Mas- tering the game of Go with deep neural networks and tree search. Nature, 529(7587):484 489, 2016.
[5] Oriol Vinyals, Igor Babuschkin, Wojciech M Czarnecki, Michaël Mathieu, Andrew Dudzik, Jun- young Chung. David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster level in StarCraft II using multi-agent reinforcement learning. Nature, 575(7782)350-335, 2019.
[6] David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, al. Mastering the game of Go without human knowledge. Nature, 550(7666):34--55,, 2017.
10

---

[7] David Silver, Thomas Hubert. Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Mare 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-11444 2018.
[8] Julian Schrittwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, Timothy Lillicrap, and David Silver. Mastering Atari, Go, chess and shogi by planning with learned model. Nature, 588(7839):604-699 2020.
[9] Adam Gleave, Michael Dennis, Cody Wild, Neel Kant, Sergey Levine, and Stuart Russell. Adversarial Policies: Attacking Deep Reinforcement Learning. In 8th International Conference on Learning Representations, ICLR 2020, 2020.
[10] Li-Cheng Lan, Huan Zhang, Ti-Rong Wu, Meng-Ye Yu Tsai, I-Chen Wu, and Cho-Jui Hsich. Are AlphaZero-like Agents Robust to Adversarial Perturbations? In 36th Advances in Neural Information Processing Systems, NIPS 2022, 2022.
[11] Jonathan Schaeffer, Neil Burch, Yngvi Björnsson, Akihiro Kishimoto, Martin Müller, Robert Lake, Paul Lu, and Steve Sutphen. Checkers Is Solved. Science, (5555444):51881555 2007.
[12] Chao Gao, Martin Müller, and Ryan Hayward. Focused Depth-first Proof Number Search using Convolutional Neural Networks for the Game of Hex. In 26th International Joint Conference on Artificial Intelligence, IJCAI 2017, volume 17, pages 3668 3674,,774777 2017.
[13] Chung-Chin Shih, Ti-Rong Wu, Ting Han Wei, and I-Chen Wu. A Novel Approach to Solving Goal-Achieving Problems for Board Games. In 36th AAAI Conference on Artificial Intelligence, AAAI 2022, volume 36, pages 10362-10369, 2022.
[14] Ti-Rong Wu, Chung-Chie Chin Shih, Ting Han Wei, Meng- Yu Tsai, Wei- Yuan Hsu, and I-Chen Wu. AlphaZero-based Proof Cost Network to Aid Game Solving. In 10th International Conference on Learning Representations, ICLR 2022, 2022.
[15] Stephen McAleer, Forest Agostinelli, Alexander Shmakov, and Pierre Baldi. Solving the Rubik's Cube with Approximate Policy Iteration. In 7th International Conference on Learning Representations, ICLR 2019, 2019.
[16] 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.
[17] Guillaume Lample, Marie-Anne Lachaux, Thibaut Lavril, Xavier Martinet, Amaury Hayat, Gabriel Ebner, Aurélien Rodriguez, and Timothée Lacroix. HyperT'ee Proof Search for Neural Theorem Proving. In 36th Advances in Neural Information Processing Systems, NIPS 2022, 2022.
[18] David Wu. Deep-Learning the Hardest Go Problem in the World. https: /tttps//bbopg j janestreet. wwt.co/ocaaa.. wwt.:cceemeeeeeeeeeee wewreeeee-rann---eeeeeeeeee hhwaamaing------aadd------------ porpttt--g-roooe---i--ee -neeleeemi--t-eweeoeeeee the- thorldldd/ww 2019. Accessed: 2023-01-19.
[19] Wim Pijls and Arie de Bruin. Game tree algorithms and solution trees. Theoretical computer science, 212(1-2): 197-215, 15: 2001.
[20] George C. Stockman. A minimax algorithm better than alpha-beta? Artificial Intelligence, 12 129,179-196, 1979.
[21] Louis Victor Allis, Maarten van der Meulen, and H Jaap van den Herik. Proof-number search. Artificial Intelligence, 66(1 11912444,,, 1994.
[22] Mark H M Winands, Yngvi Björnsson, and Jahn-Takeshi Saito. Monte-carlo tree search solver. In International Conference Computers and Games, pages 25-36. Springer, 2008
[23] Tristan Cazenave and Abdallah Saffidine. Score Bounded Monte-Carlo Tree Search. In 7th International Conference on Computers and Games, CG 2010, pages 93-104. Springer Berlin Heidelberg, 2011.
11

---

[24] Timo V Ewalds. Playing and Solving Havannah. Master's 's thesis, University of Alberta, 2012.
[25] Ting Han Wei, Chao-Chin Liang, I Wu, Lung- Pin Chen, et al. Software development architecture for job-level algorithms. ICGA Journal, 38(3):131-148, 2015.
[26] Michael Bowling, Neil Burch, Michael Johanson, and Oskari Tammelin. Heads-up limit hold'em poker is solved. Science, 347(6218; 2015.
[27] Abdallah Saffidine, Nicolas Jouandeau, and Tristan Cazenave. Solving BRREAKTHROUGH with Race Patterns and Job-Level Proof Number Search. In 13th International Conference on Advances Computer Games, ACG 2011, pages 197-207. Springer, 2011.
[28] Philip Henderson, Broderick Ameson, and Ryan B Hayward. Solving 8x8 Hex. In 21st International Joint Conference Artificial Intelligence, IJCAI 2009, volume 9, pages 505-510, 2009.
[29] I-Chen Wu, Slung-Hsuan Lin, Der-Johng Sun, Kuo-Yuan Kao. Ping-Hung Lin, Yi-Chih Chan, and Po-Ting Chen. Job-Level Proof Number Search. IEEE Transactions on Computational Intelligence and Al in Games, ((1):44-56, 2012.
[30] Ayumu Nagai. Df-pn Algorithm for Searching AND/OR Trees and Its Applications. PhD thesis, University of Tokyo, Tokyo, Japan, 2002.
[31] Jr-Chang Chen, I-Chen Wu, Wen-Jie Tseng, Bo-Han Lin, and Chia-Hui Chang. Job-level alpha-beta search. IEEE Transactions on Compulational Intelligence and Al in Games, 7(1): 28-38. 2014.
[32] Christopher D Rosin. Multi-armed bandits with episode context. Annals of Mathematics and Artificial Intelligence, 61())003,, 2011.
[33] Michael McCloskey and Neal Cohen. Catastrophic Interference in Connectionist Networks: The Sequential Learning Problem. In Psychology of learning and motivation, volume 24, pages 109-165. Academic Press, 1989.
[34] Guillaume MJ-B Chaslot, Mark HM Winands, and H. Jaap van den Herik. Parallel Monte-Carlo Tree Search. 6th International Conference on Computers and Games, CG 2008, pages 60-71. Springer, 2008
[35] Rainer Feldmann, Burkhard Monien, Peter Mysliwictz, and Oliver Vornberger. Distributed game-tree search. ICCA Journal, 12(2):65-73, 1989.
[36] Louis Victor Allis. Searching for Solutions in Games and Artificial Intelligence. PhD thesis, Transnational University Limburg, Maastricht, Netherlands, 1994.
[37] Ti-Rong Wu, Hung Guei, Po-Wei Huang, Pei-Chiun Peng. Ting Han Wei, Chung-Chin Shih, and Yun-Jui Tsai. Minizero: Comparative analysis of Alphazero and Muzero on Go, Othello, and Atari games. arXiv preprint arXiv:2310.11300 2023.
[38] Ivo Danihelka, Arthur Guez, Julian Schrittwieser, and David Silver. Policy improvement by planning with Gumbel. In 10th International Conference on Learning Representations, ICLR 2022, 2022.
[39] Chung-Chin Chin Shih, Ting Han Wei, Ti-Rong Wu, and I-Chen Wu. A Local-Pattern Related Up Table. IEEE Transactions on Games, 2023.
[40] Akihiro Kishimoto and Martin Müller. A General Solution to the Graph History Interaction Problem. In 19th AAAI Conference Artificial Intelligence, AAAI 2004, volume 4, pages 2004.
[41] Erik C van der Werf and Mark H M Winands. Solving go for Rectangular Boards. ICGA Journal, 32(2):77-88, 2009.
[42] Marwin HS Segler, Mike Preuss, and Mark Waller. Planning chemical syntheses with deep neural networks and symbolic AI. Nature, 555(7698):604-61)) 2018.
12

---

[43] Akihiro Kishimoto, Beat Buesser, Bei Chen, and Adi Botea. Depth-First Proof-Numbor Search with Heuristic Edge Cost and Application to Chemical Synthesis Planning. In 33rd Advances in Neural Information Processing Systems, NIPS 2019, pages 7224-7234, 2019.
[44] Andrew J Palay, Searching with Probabilities. PhD thesis, Carnegie Mellon University, 1983.
[45] Akihiro Kishimoto and Martin Müller. A solution to the GHI problem for depth-first proof- number search. Information Sciences, 175(4):296-31) 314,1,, 2005.
13

---

A Implementation details
A.1 PCN training
We basically follow the same PCN training method by Wu et al. [14 but replace the AlphaZero algorithm with the Gumbel AlphaZero algorithm [38) where the simulation count set to 3 in self-play and starts by sampling 16 actions. The architecture of the PCN contains three residual blocks with 256 hidden channels. A total of 400,000 self-play games are generated for the whole training. During optimization, the learning rate is fixed at 0.02, and the batch size is set to 1,024. The PCN is optimized for 500 steps for every 2,000 self-plat games. The pre-trained PCN requires around 13 hours to train machine with four 1080Ti GPUs, i.c. 52 1080Ti GPU-hours. For the online trainer, we use the same hyperparameters as the pre-trained PCN but only use one GPU.
A.2
7x7 Killall-Go solver
Our solver is built upon the oftte-of-thh-ar (SOTA) 7x7 Killall-Go solver [3 except for the following three changes. First, our solver uses PCN as heuristics while the SOTA solver trains a network with Faster to Life (FTL) techniques. Both networks aim provide faster move for solving, but FTL requires additional (kom)) settings in solving, so PCN is much easier to use in our solver. Second, implement the transposition table based on Shih al. 339 This greatly reduces the solving time. Finally, we implement solution for resolving
(GHI, i.c. cycles in Go) (44) problems ensure the correctness of reusing solutions in the transposition table, based on Kishimoto and Müller 40 45''s s GHI solution.
A.3 Worker design
The worker itself a Killall-Go solver. is GPU bound, i.c. it relies on GPUs more than CPUs since the PCN (a neural network) requires intensive GPU computation. Thus, to fully utilize GPU resources, we implement batch GPU inferencing to accelerate PCN evaluations for workers. In practice, we collect 48 workers together in one process with multiple threads. The process runs MCTS selection for each worker independently. Namely, a total 48 leaf nodes are generated and evaluated by PCN with one GPU at once. The 48 leaf nodes are collected inferencing, with a batch size of 48. This method greatly reduces the solving time when more workers are used. The baseline distributed game solver creates eight processes workers, each with one GPU, for a total of 384 workers (cight processes with 48 workers). The online fine-tuning solver has the same number of workers for fairness, but uses seven GPUs (one GPU is spared for the online trainer); the configuration is six processes with 55 workers and one process with 54 workers.
batch for batch GPU
B Experiment details
B.1
Setup
All experiments are conducted in three machines, each equipped with two Intel Xeon E5-2678 v3 CPUs, 192G RAM, and four GTX 1080Ti GPUs We list other hyperparameters in Table 4
For the memory used in solving, the manager requires 20G RAM for expanding every 1M nodes, and every 48 workers together in one process requires 30G RAM at most, Note that workers use the same amount of memory regardless of problem size. They are limited to 100,000 nodes per job; the job result "unsolved" if a solution is not obtained within that limit.
Specifically, for BASELINE with 384 workers, solving KA used 2,103 seconds, required 3G RAM for the manager and 240G RAM for the workers; solving KB used 156,583 seconds, required 170G RAM for the manager and 240G RAM for the workers. However, for RASELINE with only 48 workers, solving KA used 12,151 seconds but only required 2G RAM for the manager and 30G RAM for the workers. Overall, the settings can be varied depending on available machines.
'The original PCN training used 400 simulation counts in the self self-play, requiring much more computing resources than using Gumbel algorithm. 'Sinee Black plays the first stone in the game of Go, White usually earns some extra points called komi for balance.
14

---

Table Hyperparameters used in the baseline and online fine-tuning solvers. All variants of online fine-tuning solvers use the same settings.
BASELINE
ONLINE
# GPUs
1
1
Manager
Uthr
16.5
16.5
k for top-k selection
4
4
GPUs
8
7
Worker
# workers
384
384
node limitation per job
100,000
100,000
Trainer
# GPUs
B.2 Scalability of the distributed game solver
To evaluate the scalability of the distributed game solver, we run BASELINE with different numbers of workers on KA. Specifically, the solvers use 384, 192, 96, and 48 workers, using 8, 4, 2, and GPU, respectively. Every 48 workers share one GPU. The results are shown in Table [ Overall, the speedup is around 1.8 times faster when the number of workers is doubled (up to 384 workers due to our machine limitation).
Table Detailed statistics for solving KA by BASELINE with different numbers of workers.
Workers
# Nodes
Time (s)
Manager Nodes
Jobs
Avg. Job Time (6)
Avg. Job
PCN
Solved Jobs (%)
Avg. Worker Loading (%)
Speedup
Nodes
384
134,881,957
2,103
121,236
21,748
34.48
6,196.46
97 87%
94.53%
5.78
192
120,676,465
3,596
99,678
18,598
35.92
6,483.32
98 08.44%
98.57%
3.09
96
112.344,894
6,502
84,752
16.422
37.45
6,835.96
0
98 98.87%
98.90%
1.71
48
109,362,406
12,151
74,665
15,292
37.78
7,146.73
99.05%
98.60%
1.00
B.3
Statistics of solving 7x7 Killall-Go three-move openings
Figure 6 shows the next winning moves (the fourth moves) of 16 three-move openings for both baseline and ONLINE-CP solvers. Generally, both solvers solve the openings the
moves, except JB. The full solution trees for each opening can be found in this link: https://rlg.inn sinica. edu. wwtptttww//p/p/pptpppp /neu pas2020-oonnnee finee-finnttttnn-----e- www.ttunnnnnnnnnnooooooooo solver//ooluiion-tees We also provide a tool and a README file for explaining the solution tree.
It is worth mentioning that JA and JB are similar one of the common joseki joseki played in 19x19 Go. The joseki usually occurs when Black makes a corner enclosure move, also known as shimari in Japanese, like the two stones marked as "1" in JA and JB. Then, White attempts to invade Black's s territories by playing at the stone marked as "2" Judging by the online fine-tuning solver's ability to solve JA and JB, we foresee high potential extend our work to solving other 19x19 Go corner josekis in the future.
In addition, Figure 7 shows the curve for average critical position lengths. These curves are all similar in the sense that it starts with small average lengths, which gradually increases during fine-tuning.
T Table 7 Table & and Table 9 list the experiment results of the baseline and three variants of online fine-tuning solvers respectively. in more detail than those in Table 1 in the main text. These tables include the number of nodes for solving, the solving time in seconds, the number of nodes used in the manager, the number of jobs, the average time for solving each job, the average number of nodes for solving each job, the number of updated PCNs, the success rate of solving jobs, and the average worker load during solving. general, the solving time is correlated with the number of nodes and the number of jobs. For online fine-tuning, the solving time is also correlated with the number of PCNs as the trainer updates PCNs at a stable speed. Note that the number of PCNs is always 0 for the baseline solver, as they do not update PCNs during solving.
A joseki is move sequence that is widely believed to be balanced play by both players.
15

---

(a)
(b)
(c)
(d)
(e)
(I)
(g) KC
(h) KD
(i) KE
(i (k) DA
()) SA
(m) SB
(n) SC
(0) SD
(p)
Figure 6: The solutions of the next winning move for 16 7x7 Killall-Go openings. For each opening, "A" and "B" represents the winning move found by the baseline solver and the online fine- munituning solver respectively. If both solvers solve the opening with the same winning move, only "A" is shown on the board.
In our experiments, the average success rates of solving jobs are around 97.30%, 98. 98.44%, 99.14% and 99.08% for the baseline and the online fine-tuning solvers, respectively. In addition, for some quickly solved openings, e.g. KC, SA, and SB, the average time for solving each job is far less than other difficult openings. While the workers are able to solve jobs quickly, the managers are relatively unable to create enough jobs for the workers, causing the workers to be relatively idle (lower avg. worker loading). Compared with the baseline solver, online fine-tuning solvers have better success rates of solving as well lesser nodes for each job. This confirms that online fine-tuning successfully fine-tuned the PCNs for critical positions that the manager interested in, thereby increasing the job efficiency overall.
Table 6: Detailed statistics for the openings solved by BASELINE.
Manager Nodes
Avg. Job Time (S)
Job Nodes
Solved
Avg. Worker Loading (%)
Nodes
Time (8)
Johs
PCN
Jobs (%)
3,964,444955)
142,115
4.842.554
792,465
68.68
11,305.90 .9
0
96.83%
99.48%
JB
7.137.514.712
155.786
3.689.548
635,263
93.90
11,229.72
0 96.80%
99.48%
JC
721,004,784
12,514
900,221
165,308
23.66
4,356.
0
98. 96%
73.70%
1,271.426.148
30,209
655,078
128,885
89.32
9,859.73
97.75%
98.96%
134.881,952
2,103
121.236
21.748
34.48
6,196.46
0
97, 87%
94.53%
KB
10,153.035,632
156,583
8,241,207
1,240,258
48.34
8,179.58
0
98. 20%
99.48%
KC
38,217,263
747
72,880
15,284
10.33
2,495.71
97.07% 0
98. 39%
62.02%
2.754.213.379
47.494
1,499.735
246.500
73.67
11.167.20
99.22%
1.197,819,407
18,771
1,024,660
150,490
47.14
7,952.65
97.79% 0
98.44%
KF
9,516.440,320
147.271
5.208.724
789.225
71.50
12.051.36
96.88% 0
99.68%
DA
7,322.743,383
112,874
1,326.195
636,200
67.90
11.503.33
98.37% 0
95.62%
99.22%
51,272.288
937
79,967
17.772
14.26
2,880.50
75.78%
215,380,103
3,860
288.751
52.191
22.91
4,121.23
97.99%
78.65%
SC
97,559,402
1.557
113.821
22.376
23.31
4.354.92
0
97.94%
90.62%
SD
177,7717,667
124,644
4,286,025
668,654
71.36
12.237.62
0
95.18%
99, 48%
4,297,808. 808,879
64.227
2,234.093
345.124
71.00
12,446.47
95.10%
98.86%
B.4 Different PCN thresholds
We examine different Porr from 11.5 21.5 on opening JC, using the baseline solver. The experiment result is presented in Table [O] where the four columns represent the examined 0thr, the total solving time, the average time for workers to solve jobs, and the job success rate. Among these PCN thresholds, we consider taár = 16.5 to be balanced setting as it performs well in the three metrics. However, the results also show that the performance is not necessarily sensitive different wer settings, i.c. the solving time is similar when Ush (15.5, 17.5).
16

---

100
120
100
180
160
180
200
240
260
Terattin
Taeration
(a) JA
(b) JB
X
10
Leaph
11
15
100
Beratiee
Berrasoe
(c)
(d) JD
KA
24
XII
15
76
Ezngh
1/
12
10
30
100
2001
2541
300
300
Theraion
Tonatio
(e) KA
( KB
K0
Lougt
15
15
355
6.5
53
6.
30
100
100
brotlen
Tamation
(g) KC
(h) KD
1.0
180
700
350
780
(i) KE
(i) KF
Figure 7: Average length of critical positions for each opening.
As demonstrated in the table, Uthr outside of this range deteriorates the solving performance. On the one hand, when Uer is too high, e.g. Ushr = 21.5, only about 95% of jobs can be solved, implying that about 5% of the jobs wasted. On the other hand, when Vthr is too low, e.g. Uskr 11.5, the
17

---

DA
20
Langh
20
20
100
180
1.00
100
220
340
200
10
Betaroo
Toniion
(k) DA
(I) SA
10
12
(m) SB
(n) SC
30
Leagst
80
100
120
140
100
150
00
70
50
Decation
Deratio
(0) SD
(p) SE
Figure 7: Average length of critical positions for each opening.
Table 7: Detailed statistics for the openings solved by ONLINE-SP.
Manager Nodes
Avg. Job Time
Avg. Job # Nodes
Salved Jobs (%)
Avg. Worker Loading
Nodes
Time (s)
# Jobs
PCN
4.054.562.593
69.699
2,491.326
479.455
55.45
8,451.41
359
98.49%
98.95
3,378.672,517
83,454
1,607,080
327,626
97.49
10,307
424
97.27%
99.14%
819,264.890
13,963
704,540
137,752
35.96
5,942.28
98.08%
88.34%
JD
846.365.092
19.396
500.259
106.495
69.00
7,942.77
113
98.50%
98.91%
KA
143,814,448
2,621
174,202
34.222
26.17
4,197.31
14
98.55%
90.25%
KB
3,794.290,131
64,493
1,69
548,306
43.54
6,913.33
305
98 99%
99.05%
45,217.101
1.156
100,985
21.847
11.12
2,065.09
99.47%
54.07%
KD
1.504.77.3299
25,715
986,849
202.651
48.37
7,421.58
126
98.86%
98.95%
KE
214.614,577
3,917
246,259
50.422
28.29
4,251.48
21
98.85%
95.48%
KF
6,080,836.866
100,690
5,431,753
855,725
44.93
7,099.72
519
99.19%
99.21%
DA
438,5,438,589
50,046
2,682,998
418.088
45.56
7,206.03
248
98.55%
98.90%
54,574.495
1,471
122.611
25,403
11.78
2,143.52
98.47%
56.245%
65,970,358
124,986
25,917
2,540.62
98.10%
79.84%
213,889,777
3,553
141,447
32.739
39.32
6,528.86
98.06%
95.22%
SD 4,8214722453
63,058
2.224.352
406.191
59.27
9,402.59
329
97.37%
99.01%
SE
2,065,528,927
33,437
1,647.455
282,992
44.79
7,293.07
166
98.21%
98.26%
assigned jobs can be solved quickly with high success rate. However, this requires the manager to assign more jobs, which increases overhead of handling job assignments between the manager and the workers, thereby increasing the solving time. Note that the appropriate Ushr may vary for different games and for different numbers available workers. is possible adjust vahr dynamically during solving, which is left for future work.
18

---

Table Detailed statistics for the openings solved by ONLINE-CP.
Manager Nodes
Avg. Jub Time (5)
Avg. Job # Nodes
Solved Jobs (%)
Avg. Worker Loading (%)
Nodes
Time
Jobs
PCN
JA
1,288,601,416
22,384
1,314,785
259,008
32.68
4,970.07
186
99.48%
98.44%
JB
1.576.437.139
31,957
1,643,806
327,442
36,67
4,809.38
272
99.46%
96.66%
JC
316,391,324
6,537
538,369
109,298
17.09
2,889.83
59
99.27%
72.38%
JD
145,655,175
11,083
501,953
109,891
18.12
4,960.85
102
99.32%
98.75%
KA
111,838.88 889
2,102
159.614
32.153
22.60
3,473.37
18
98.70%
92.69%
KB
2,242,789,148
38,947
3,202,296
575,365
24.45
3,892.46
343
99.65%
93.25%
KC
26.441.989
758
69,052
15,423
9.12
1.709.97
99.01%
50.78%
KD
955.257.191
17,434
1,222,772
227,427
26,86
4.194.90
145
99.69%
89.35%
KE
181,418,954
3,336
261,253
49,484
24.25
3,660,93
30
98. 86%
94.53%
KF
2,107.185.330
35,418
2,555,399
427.993
31.27
4,917.44
285
99 99.60%
98.06%
DA
1,761 .776,744,477
30,313
2,556,573
421,268
26.16
4,176.17
266
99.60%
94.03%
41,863,480
992
86,749
19,634
12.60
2,127.77
9
98.57%
70.96%
55,541.455
1,364
125,338
27,612
11.64
2,006.96
98.48%
64.32%
SC
98,661,355
1,715
116,980
24,770
24.34
3,978.38
16
98.17%
94.28%
SD
1,395,444,447
23,751
1,575,572
278,198
32.24
5,010.35
195
99.13%
98.33%
SE
757,256,934
12,465
892,615
153,343
30.43
4,932,50
103
99.17%
98.26%
Table 9: Detailed statistics for the openings solved by ONLINE-SP+CP.
Nodes
Time (8)
Manager Nodes
#obs
Avg. Job Time (6)
Avg. Job # Nodes
PCN
Solved Jobs (%)
Avg. Worker Loading (%)
1,425,6688
24,865
1,370,665
278,183
33.85
5,120.00
225
99.45%
98.18%
1.601.479.130
31,455
1.743,905
351,934
33.16
4,545.55
283
99.50%
95.31%
JC
414,108,746 746
8,343
693,560
140,608
17.68
2,940.20
69
99.54%
75.26%
JD
502.966.563
10,896
401,057
89,954
45.82
5,586.92
103
99.13%
98.44%
KA
104.905.173
1,931
109.111
23.739
28.97
4,414.51
18
98.21%
95.83%
2,527.488. 112
43,200
3,148.579
578,009
27.79
4,367.30
386
99.59%
96.09%
25.508.784
706
58,399
13.172
10.58
1,932166
6
99.18%
53.65%
KD
920.902.808
16,357
1,092.352
210,345
27.80
4.372.87
148
99.57%
91.15%
KE
288
3,095
214,173
42,447
26.24
3,966.74
28
98.81%
94.79%
KF
2,027.558..
35.197
2,203,830
383.317
34.79
5,283.76
305
99.57%
98.33%
DA
1,665,511, $1,033
28,337
2,252,356
377,189
27.77
4,409.62
235
99.53%
95.57%
SA
41,796,555
1,105
95,672
21,325
10.67
1,955.49
10
98.61 98.67%
55.73%
109,591.487
2,258
167,238
34,085
19.62
3,210.33
98.04%
78.12%
93,535.813
1,655
94,822
21,820
26.28
4,282.36
98.12%
93.49%
SD 1,885,499.307
25,531
1,674,274
296,617
32.26
5,002.29
224
99.15%
97.12%
SE
1,200,741.176
20,428
1,289,405
231,498
33.15
5,181.26
182
99.17%
98.01
B.5
Comparison to offline fine-tuning
We now investigate how much benefit we can gain from offline fine-tuning for a specific opening. To do this, we first train Og by generating 400,000 self-play games (around 52 1080Ti GPU-hours) from the empty board. The resulting network is the same as the one referred to as Og in the main text. Next, we fine-tune by generating 200,000 additional self-play games (around 26 1080Ti GPU-hours) from the specific opening we are interested in. That is, if we want to solve the opening JC, we generate self-play games starting from that opening, and perform updates on Og to obtain what we refer to as OnJC. For this experiment, we used four openings, so the networks Op-JC, 0g-KE, DD and SE were produced. Lastly, in the baseline case, we do not update the network with critical positions; the same network is used all throughout the proof search. In ONLINE-CP critical positions chosen and the 6 is further fine-tuned using the OFT (resulting in 8/, 8 .... 8 ...).
Table II shows the times for solving these four openings with and without offline fine-tuning. The left two columns use 0g while the right two columns use 0g With offline fine-tuning, the solving times for these openings generally decrease in the baseline solver, since the by is specifically fine-tuned for each opening, but exceptions may still occur, as in opening JC. However, when using 0g the solving times for ONLINE-CP increase for opening JC, DA, and SE. This may be because 0g only helps learn better heuristics for the opening positions, but does not always guarantee providing accurate heuristies for all varieties of positions during solving. In addition, it is worth noting that although
19

---

Table 10: The solving time, average job completion time, and success rate solvable jobs for solving opening JC by the baseline solver with different PCN thresholds.
Mthr
Time (8)
Avg. Job Time (s)
Solved Jobs (%)
11.5
23,559
2,00
99.92%
12.5
22,870
3.60
99.84%
13.5
18.356
5.75
99.74%
14.5
19,458
12.06
99.55%
15.5
12,519
16.29
99.29%
16.5
12,514
23.66
98.96%
17.5
12,877
33.73
98.34%
18.5
17,536
46.06
97.35%
19.5
22,343
52.04
96.75%
20.5
24,469
58.73
95.99%
21.5
27,810
70.50
94.94%
Table 11:
Comparing the impact of single batch, offline fine-tuning, i.e. pre-training for the specific
opening instead of from an empty board.
wfo offline fine-tuning (0o)
w/ offline fine-tuning (%)
BASELINE
ONLINE-CP
BASELINE
ONLINE-CP
JC
12,514
6,537
22,748
10,099
KE
18,771
3,336
2.248
2,417
DA
112,874
30,313
90,298
33,055
SE
64,227
12,465
28,905
42,522
offline fine-tuned 6g accelerates the solving time for the baseline solver, it is impractical since cannot expect pre-train 0g for each opening, especially if our eventual goal is solve complete games from an empty board outright. In contrast, our online fine-tuning solver provides an automatic method that fine-tunes the PCN dynamically without too much extra computation cost.
20


Reviews:
[{"review_id": "pTaMpn6VKw", "reviewer": "Reviewer_Q8Zg", "summary": "The paper proposes an AlphaZero-based MCTS search procedure modified for game solving (vs the original game playing objective). The algorithm consists of a carefully-engineered distributed MCTS procedure leveraging GPU-based learned proof-cost-network estimates to grow the search tree in promising directions. The key idea is to interleave search steps with updating the PCN network, on a non-stationary distribution of states encountered during the search, via self-play. The main contributions are algorithmic and empirical. The experiments are conducted on a variant of Go. The results indicate the proposed method reduces the search space and overall computation time on the challenging task of solving 7x7 Killall-Go.\n\nUPDATE: I thank the authors for their detailed response. After reading the other reviews and comments, I'm now more inclined to recommend acceptance and have adjusted my review accordingly.", "questions": "- Could you please describe the parts of the proposed algorithm or technical ideas that are novel?\n\n- The baseline used is the algorithm without online learning. Are there other baselines for 7x7 Killall-Go from prior work?\n\n- I assume that the reported runtimes include the time spent on updating the parameters. Please confirm this is the case.\n\n- I was a bit confused by L127-L127. The criteria for spawning a job (when $v_l < v_{thr}$) seems to control the distribution of the tree nodes sent to the solver, using the node's $v_{thr}$ value. Thus, increasing v_thr would allow more jobs to be spawned, with the newly included nodes likely being harder to solve. My question is about decreasing v_thr. I'd expect this to generate **fewer** solver jobs, which are likely easier to solve. But L128 claims otherwise, \"smaller v_thr leads to easier but **more numerous** jobs\". What am I missing?\n\n- Can you provide more details about the role of the critical queue? For example, are the nodes in it shallow or deep? How does node depth correlate with sampling frequency / time spent in the queue? How does the PCN network loss curve correlate with the contents of the queue? Additional empirical details, discussion and insight on this subject would be interesting.\n\n- Is it possible to include additional domains? Can you provide information on whether this approach works in other domains?\n\n- Is there a reason code wasn't included? Can it be included?", "limitations": "To an extent. The paper does a better job explaining its strengths than its weaknesses.", "rating": 7, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "+ The paper tackles a challenging problem of game solving, which has implications for combinatorial search problems.\n\n+ The approach of adjusting the distribution of states explored during the self-play learning step towards those likely to be encountered soon by the outer MCTS search is intuitively clear.\n\n+ The proposed approach consisting of a number of algorithmic choices (distributed search, guided self-play, PCN threshold, manager vs worker roles, etc.) to improve search efficiency. Despite being somewhat heuristic and perhaps not entirely novel, each implementation detail is well explained, intuitively clear and fits nicely into the final algorithm. Overall, the approach seems to be a well-engineered solution to efficiently apply modern GPU-based search procedures to the challenging problem of game solving.\n\n+ The paper includes a detailed experimental investigation. The results indicate that the proposed method clearly has better empirical performance. The utility of training on critical positions is demonstrated clearly. While the baselines could be stronger and other improvements could be made (discussed below), overall, the empirical section is convincing that the proposed method does well on a challenging combinatorial search problem.", "weaknesses": "- The paper does not clearly formalize the online learning objective and does not include a mathematical analysis of the algorithm's performance (e.g., wrt regret).\n\n- The overall approach seems novel but I'm not sure which components of the algorithm are novel. The paper could do a better job of placing its contributions within the larger body of prior work on game solving. In its current form, it's a bit difficult to assess novelty.\n\n- It's difficult to assess how much this approach moves the needle on solving 7x7 Killall-Go or other games compared to prior efforts. Additional baselines and / or domains would help here but likely at large computational expense.\n\n- The paper could go into more detail analyzing the role of the critical node queue, given its importance to the overall performance. On a related note, the paper could do a better job of analyzing the overall stability of the updates to the PCN parameters / model (perhaps in the appendix).\n\n- Code hasn't been included as far as I can tell. The omission will make reproducibility challenging and likely to limit the impact of the paper.\n\n- (minor) The description of the experimental results could be tightened a bit more. Examples with suggestions below.\n  - L283: Comparing \"within 40000 seconds\" with \"more than one day\" could be \"~10 hours\", \"24 hours\" or 2.4x faster. \n  - L286: \"1.29 billion or so\" could be \"~1.29 billion\".", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful reviews and constructive comments. We address your concerns and questions below. All numbered citations in our rebuttal refer to the sources in the paper’s bibliography.\n\n> Could you please describe the parts of the proposed algorithm or technical ideas that are novel?\n\nThe online learning methods (using solved/critical positions to fine-tune PCN models) in Section 3.2 and the techniques introduced in Section 3.3 are all novel methods. Please refer to “Novelty and contribution” in the rebuttal for all reviewers (at the top) for more information.\n\n> The baseline used is the algorithm without online learning. Are there other baselines for 7x7 Killall-Go from prior work?\n\nOur baseline solver is built upon the state-of-the-art 7x7 Killall-Go solver [13, 38] but with some improvements/modifications as mentioned in appendix A.2. In Shih’s work, they solved 20 7x7 Killall-Go problems, but the most challenging problems are merely five-move openings (as opposed to the three-move openings in our paper). We didn’t compare our solver to them directly because this work mainly focuses on investigating different online learning methods (solved/critical positions) in a game-independent distributed game solver rather than solving 7x7 Killall-Go specifically. We also ran a quick experiment and compared a non-distributed version of our baseline to Shih’s solver for fairness. Shih’s solver uses a total of 692,338 nodes to solve the 20 problems in their paper, while our solver only requires 502,679 nodes (reduce by 27.39% of nodes).\n\n> I assume that the reported runtimes include the time spent on updating the parameters.\n\nYes, the reported time is the total time from start to finding a solution, measured by the manager.\n\n> I was a bit confused by L127-L127.\n\nHigher $v_l$ ​​indicates that solving this node requires a larger proof tree, i.e. more difficult to solve. Usually, nodes closer to the root are more difficult to solve. The root generally has the highest proof cost estimate. Typically, there are also fewer nodes near the root of the tree (in contrast to the numerous leaf nodes). Therefore, smaller $v_{thr}$ leads to more jobs, whereas larger $v_{thr}$ leads to fewer.\n\n> Can you provide more details about the role of the critical queue? For example, are the nodes in it shallow or deep? How does node depth correlate with sampling frequency / time spent in the queue?\n\nCritical positions are unsolved leaf nodes that the manager recently selected. Whether the nodes in it are shallow or deep depends on the manager’s current proof tree. Fig. 5 (b) in the main text shows the average depth (length) of critical nodes of each iteration when solving opening *JA*. Figures for other openings are provided in Fig. 2 in the appendix. Generally, the critical nodes gradually become deeper when the manager digs into the search tree. However, if the manager changes its focus branch during solving (especially when some previous branches are solved), shallower nodes may become critical. For example, Fig. 2 (f) in the appendix shows such a phenomenon when solving opening *KB*. We observe that the manager changes its focus from move A to B (as shown in Fig. 1 of the one-page PDF) around iteration 135, resulting in a sudden change in the average depth of critical positions. A similar phenomenon happens again at around iteration 185. The online trainer uniformly samples critical positions from the critical queue.\n\n> How does the PCN network loss curve correlate with the contents of the queue?\n\nSince the online trainer is limited to fine-tuning the critical positions only, generally the loss curve decreases gradually during online learning. We provide two additional loss curves for the pre-trained PCN model and online PCN model while solving *JA* (as shown in Fig. 2 of the one-page PDF). Nevertheless, we have observed that the loss is not highly correlated with the critical queue.\n\n> Is it possible to include additional domains? Can you provide information on whether this approach works in other domains?\n\nPlease refer to “Generalizability to other games” in the rebuttal for all reviewers (at the top) for more information.\n\n> Is there a reason code wasn't included? Can it be included?\n\nThe code for our game solver is built on top of an AlphaZero/MuZero game-playing framework under development and in preparation for publication. Specifically, we used its MCTS to construct our distributed game solver and expanded it for online PCN training with slight modifications. We were planning to release the code once the report for the framework is completed. We will gladly provide access to our code for your reference during the review process if you think it necessary. We fully agree that reproducibility is critical; once the framework is published or if this paper is accepted, we will release all related code to ensure reproducibility."}, {"review_id": "Sxm3dD0L0Z", "reviewer": "Reviewer_tMcZ", "summary": "The paper addresses the problem of computing provably optimal solutions to game instances. A naive game solving algorithm must therefore address all the possible actions an opponent may pick before emitting a  judgement about the game instance value. A leading paradigm when developing this category of algorithms is that of employing strong agents to evaluate game states and therefore inform heuristics that aid in exploring the game tree.\n\nThe paper focuses on developing a AlphaZero-based heuristics for game-solving. The main issues are that a self-play learning algorithm is a very robust player on path, but its values do not distinguish among actions leading to games of different lengths (useful in order to solve subgames while exploring less) and they lack prediction quality when considering positions that it would not normally reach in game (and that instead are reached as part of the game solving proof algorithm).\n\nTo address those issues, the paper proposes:\n- the training of Proof Cost Networks (PCN) via the AlphaZero self-play process in order to better inform the expansion heuristics about the complexity of solving a subgame. This is in contrast to naively use a value network that hints at whether the subgame is possibly lost/won, but does not include any complexity estimation.\n- the fine-tuning of the PCN used using selected subgames which have been encountered during the proof process. \n\t- When using solved positions (ie. solved subgames) to fine-tune, those subgames's proof complexity is set to 0 (since it is already proven their value). Then a fine-tuning batch mixing both solved games and self-play games is employed to update the network. This allows to push the heuristics towards game instances which have already been solved, thus efficiently reusing already computed subgame proofs\n\t- When using critical positions (ie. recently explored subgames) to fine tune, the fine-tuning batch is updated by adding experience sampled from applying self-play starting from those positions. This allows to improve PCN's performances on the nodes that will probably be expanded in the future", "questions": "The following questions highlight parts of the paper which felt unclear or possibly benefitting from extra detail.\n1. It is not clear how the PCN is trained and its relation to AlphaZero training process. My high-level intuition from reading [14] is that the MCTS algorithm on top of which AlphaZero is based is modified in the Q-values used in the exploration of the game tree. In particular, $\\bar n(s)$ and $\\bar m(s)$ quantities are estimated from episodes of sampled experience (approximating in a \"importance weighting\"-like fashion) and then used to direct self-play towards smaller areas of the tree. My opinion is that including extra details in this direction in Section 2.3 could help readers to have an algorithmic understanding of what it means to the *sampling of self-play strategy* which is employed throughout Section 3.\n2. When using solved/critical positions as heuristics, are the self-play games re-sampled at the moment, or taken from some buffer of experience used to train the first version of the PCN?\n3. Any idea on the theoretical lower bound achievable by having a perfect heuristcs? I.e. is it possible to evaluate the empirical increase in quality of the PCN-based heuristics in terms of the gap between baseline and a perfect heuristic?\n4. How different are the performances of alpha-beta search or PNS algorithms for the problem of game solving?\nOn top of this clarifications, I'd like to hear the authors' opinion regarding the weaknesses I've highlighted in the previous section.", "limitations": "The only limitation of the work is the focus on Go instances and MCTS routines, and those limitations are clearly expressed in the paper.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* Clear and exhaustive experimental evaluation\n* Strong experiment results\n* Clear explanation of the heuristics introduced", "weaknesses": "* Purely experimental work applied to a specific subset of go instances. This weakens the generality of the approach because the same heuristics may not apply to other game instances\n* Many dependencies on previous work. Those weaken the overall clarity of the paper for people who are not familiar with the past literature\n* Misleading nomenclature. Online Learning is a terminology which is misleading given the actual technique employed. In particular, Online Learning in games usually refers to *Online convex optimization* techniques, while the paper refers to a Continual Learning technique.  My suggestion would be to switch to Online Fine-tuning to avoid the strong unintended overlap in terminology.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful reviews and constructive comments. We address your concerns and questions below. All numbered citations in our rebuttal refer to the sources in the paper’s bibliography.\n\n> Purely experimental work applied to a specific subset of go instances.\n\nPlease refer to “Generalizability to other games” in the rebuttal for all reviewers (at the top) for more information.\n\n> Many dependencies on previous work.\n\nThe online learning methods (using solved/critical positions to fine-tune PCN models) in Section 3.2 and the techniques introduced in Section 3.3 are all novel methods. Please refer to “Novelty and contribution” in the rebuttal for all reviewers (at the top) for more information.\n\n> Misleading nomenclature.\n\nWe settled on using the term “online learning” after reviewing chapter 2, “Related Learning Paradigms”, in the book “Lifelong Machine Learning” by Chen and Liu. Among other related learning paradigms, online learning (subsection 2.3) was the closest to our approach since, 1) our training data arrives sequentially; 2) the existing model is quickly updated when new data arrives to produce the best model so far; 3) we do not have access to a full set of training data as in traditional batch learning. To clarify how our method works, we also use the term “fine-tuning” throughout the paper. We are open to, albeit a little reluctant, to make this change since it is part of our paper’s title. If a consensus among the reviewers is that the term is confusing, we will make the necessary changes.\n\n> Q1: It is not clear how the PCN is trained and its relation to AlphaZero training process.\n\nThank you for the suggestions. We will revise the manuscript accordingly.\n\n> Q2: When using solved/critical positions as heuristics, are the self-play games re-sampled at the moment, or taken from some buffer of experience used to train the first version of the PCN?\n\nWe use replay buffers in our PCN training, as is the case with AlphaZero. In the beginning, the self-play games generated by the first version of the PCN will still be sampled by the online trainer. However, after several training iterations, these self-play games will be gradually replaced by the new self-play games (playing starts from critical positions).\n\n> Q3: Any idea on the theoretical lower bound achievable by having a perfect heuristcs?\n\nIf we understand your idea of the perfect heuristic correctly, i.e. the heuristic can find a minimum solution tree for any given position, this theoretical lower bound is extremely difficult to obtain. In addition, since our online learning solver attempts to minimize the number of examined nodes dynamically, a more apt theoretical comparison for our online trainer is finding the minimum solution tree while the search is ongoing, taking into account the effort already spent. This non-stationary problem is even harder. To clarify, assume in a perfect situation, we know solving moves A and B requires 2000 and 5000 nodes. Then, the perfect heuristics for A and B will be PH(A)=2000 and PH(B)=5000. However, given a scenario where a proof tree already spent 4000 nodes on solving B but no nodes on solving A, the online trainer should theoretically adjust PCN to predict PCN(A)=2000 and PCN(B)=1000, and guide the search to keep solving on B. We hope this sufficiently explains why this kind of comparison is not feasible, unless the entire search space is fully explored. Nonetheless, our empirical experiments should indicate strongly that the quality of PCN improves during solving.\n\n> Q4: How different are the performances of alpha-beta search or PNS algorithms for the problem of game solving?\n\nPrevious research has shown that none of these algorithms (alpha-beta/PNS/DFPN/MCTS) dominates the others [14, 24, 25] for game solving. We agree that it is very interesting to compare the performances of different search algorithms, and we are currently working on incorporating different search algorithms into our game solver. However, since our proposed online learning method is search-independent, we think this comparison is out-of-scope for this paper and leave it for future work."}, {"review_id": "M0bsD6kpQG", "reviewer": "Reviewer_quVs", "summary": "This paper proposes a parallel setup for solving games, which includes online fine-tuning of trained proof cost networks to improve their estimations of the proof cost of nodes specifically for subsets of the state space that the prover is currently focusing on. Experiments show significant reductions in the number of nodes and computation time required to solve numerous 7x7 Killall-Go openings, with improvements also appearing to scale well with problem difficulty.", "questions": "### Suggestions\n- \"Game solving is a much higher challenge than game playing\" --> this is slightly strange phrasing, in particular the \"higher\". Something like \"Game solving is a more difficult challenge than [...]\" would seem more natural.\n\n### Questions\n- \"A two-player zero-sum game is considered solved if there exists a winning strategy for a player which guarantees a winning outcome.\" --> as far as I'm aware this is not correct. A game is solved if we know the outcome under perfect play (either from any state or from the initial state). It may be that this outcome is a draw (or a loss) for the first player though, it need not necessarily be a winning outcome with a winning strategy. I would appreciate a clarification to this question, especially because I also raised this comment when reviewing the same paper submitted to a previous comment, and at the time the authors said the manuscript would be revised accordingly. Which evidently did not happen. If I'm wrong here that's fine, but then please clarify.", "limitations": "No unaddressed limitations.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- Relatively straightforward and simple, but good idea.\n- Good empirical results.\n- Paper very well written, easy to follow.\n", "weaknesses": "- Game solving is a fairly niche topic that probably is mostly of real interest to a relatively small subset of the NeurIPS community (but I think it's fine, not a reason for rejection).\n- The main contribution (online fine-tuning) seems relatively limited in novelty. As far as I'm aware it's novel specifically within the game solving setting, but outside of that, online fine-tuning is not a groundbreaking idea.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful reviews and constructive comments. We address your concerns and questions below.\n\n> The main contribution (online fine-tuning) seems relatively limited in novelty.\n\nPlease refer to “Novelty and contribution” in the rebuttal for all reviewers (at the top) for more information.\n\n> Something like \"Game solving is a more difficult challenge than [...]\" would seem more natural.\n\nWe will revise the manuscript.\n\n> It may be that this outcome is a draw (or a loss) for the first player though, it need not necessarily be a winning outcome with a winning strategy.\n\nThank you for pointing this out. Taking your previous comment re: draws into consideration, we added a footnote this time around (footnote 2 at the bottom of page 2), which, admittedly, is not as front and center as it could be. It is true that the solution may be a loss for the first player. That situation is covered in our statement “winning strategy for _a_ player”. In the two-player zero-sum case, a loss for the first player is a win for the second player.\n"}, {"review_id": "Du3jWvsVDu", "reviewer": "Reviewer_wrov", "summary": "The paper aims to address the game solving problem: providing a game theoretic value to all states in a game. To address the task the paper extends AlphaGo to the game solving case using an approach that distributes game playing scenarios to solvers on parts of the full game tree. Building off prior distributed game solvers, the new technique uses a self-play learning algorithm to improve estimates of the difficulty of solving new game states during the game solving process (as opposed to using a pretrained and frozen estimation method). The work distribution manager incorporates several new heuristics to select the most promising nodes to solve next and avoid wasted computation. These improvements reduce computation time in 7x7 Killall-Go to roughly 1/4 of a non-learning baseline algorithm. Ablations show the heuristics chosen individually and jointly improve the overall solver performance.", "questions": "- [Q1] How do the core algorithms scale?\n\t- How does performance change with more or fewer workers?\n\t- What are the demands in compute and memory? How do they scale with the size of the problem and/or workers?\n- [Q2] Does critical position prioritization break down when MCTS thrashes between expanding new shallow node and deeper nodes in the tree?\n\t- Often tree search can suffer from a thrash between vastly different branches on the shallow parts of the tree. At a glance this would seem to be a more substantial problem for game solving as the full tree must be solved.\n\t- Is this not a problem in practice? Or is there a way to quantify this effect and measure it's impact?\n- [Q3] Table 1\n\t- What is going on with SB?\n\t- Online-SP and online-CP both do very well compared to the baseline. But online SP+CP does substantially worse than either alone.\n\t- I don't have sufficient knowledge of Go (let alone Killall-Go) to tell why this might be expected or how to evaluate the case. It is interesting as the one scenario that defies the general patterns.\n- [Q4] Figure 4\n\t- Include all 4 variants in the bar plot, not only baseline and online-CP. Also, consider changing the color scheme to be colorblind friendly.\n- [Q5] What is the direct evidence that the manager remembers what the OLT trainer forgets?\n\t- Is there any way to probe the checkpoints to demonstrate this phenomenon?\n\t- The claim is intuitive, but the results would benefit from a direct test / evidence for this claim.\n\n\nBelow are some other less important questions / suggestions:\n- For PCN state estimates:\n\t- How effective is a naive heuristic that computes a similarity between new positions and a database of solved positions? (for solved positions using OLT)\n\t- This would be an alternative to the OLT / PCN approach. I'm not deeply familiar with the game solving literature and so am not sure if this is already a common / established practice.\n- Could the fixed PCN be used to generate compressed/embedded state vectors to improve this matching?\n\t- Could that apply to the learning process to prioritize selection of training samples?", "limitations": "The paper does not address limitations nor negative societal impact. Limitations merit some discussion, specifically around generalization / applicability to other game solving scenarios, classes of games solved (ex: turn-based, 2 player, ...), or computational requirements.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "## originality\n\nModest. The core architecture of distributed game solving and the core AlphaGo algorithm are both established in the literature. The originality of the paper stems from devising a way to do online learning during AlphaGo distributed solving in such a way that state value estimates remain useful throughout the search estimation process. This is not trivial, but is necessarily a highly targeted application.\n\n## quality\n\nGood. The results show substantial improvements over baselines and the ablations are thorough.\n\n## clarity\n\nGood. The substantial background that is needed to understand both distributed game solving and AlphaGo is clearly introduced. Reasoning for each of the major heuristics is clear and the results are unpacked well for an audience not familiar with the target domain.\n\n## significance\n\nModest. Game solving is a somewhat niche topic, so the audience will be limited by that reach. The work itself is building on two prior methods - the improvements are clear, but are sufficiently complex that it is not immediately obvious they will generalize to other games or applications. That said, reducing to 1/4 the computation needed on a fair benchmark is a substantial improvement!", "weaknesses": "One weakness (hard to address) is the results are only in terms of solving a single game. The game playing literature is awash with game benchmarks and has created a norm of multi-game evaluation to demonstrate generality. This may not apply to game solving, but the lack of multi-game evaluation makes it hard to tell how general the algorithms are. Are there any easy alternative scenarios (like the cited Hex or Rubik's Cube) that would show the algorithm can be generalized to other scenarios? These would be an opportunity to compare against other established baselines, perhaps on smaller or simpler problems.\n\nBelow are detailed suggestions around scalability. The paper would benefit from addressing those concerns as it helps show the potential of the technique over the long run or for larger problems (even if the paper does not directly measure those cases).\n\nThe lifelong learning claim would benefit from direct evidence that the manager remembers what the trainer forgets. See the questions below for more detail.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful reviews and constructive comments. We address your concerns and questions below. All numbered citations in our rebuttal refer to the sources in the paper’s bibliography.\n\n> results are only in terms of solving a single game\n\nPlease refer to “Generalizability to other games” in the Rebuttal (at the beginning) for all reviewers.\n\n> [Q1] How does performance change with more or fewer workers?\n\nTo evaluate the scalability of our distributed game solver, we add an additional experiment by running the baseline solver with different numbers of workers on opening *KA*. Specifically, we use 384, 192, 96, and 48 workers, using 8, 4, 2, and 1 GPU, respectively. Every 48 workers share one GPU. The results are shown in Table 1 in the additional one-page PDF (in rebuttal for all reviewers). Overall, the speedup is around 1.8 times faster when the number of workers is doubled (up to 384 workers due to our machine limitation). The results show that it can potentially speed up with more workers, such as 768 workers. We will add this experiment in the appendix.\n\n> [Q1] What are the demands in compute and memory?\n\nWe provided details of hardware specifications in Appendix B.1. For the memory consumption: (a) the manager requires 20G RAM for expanding every 1M nodes, (b) every 48 workers together in one process requires 30G RAM at most. Note that workers use the same amount of memory regardless of problem size. They are limited to 100,000 nodes per job; the job result is “unsolved” if a solution is not obtained within that limit.\nSpecifically, for the baseline solver with 384 workers:\n* solving *KA* used 2,103 seconds and 243G memory (3G for the manager and 240G for the workers)\n* solving *KB* used 156,583 seconds and 410G memory (170G for the manager and 240G for the workers)\n\nHowever, if running the baseline solver with only 48 workers, solving *KA* used 12,151 seconds but only required 32G (2G for the manager and 30G for the workers). Overall, the settings can be varied depending on available machines.\n\n> [Q2] Does critical position prioritization break down when MCTS thrashes between expanding new shallow node and deeper nodes in the tree?\n\nThe critical positions may suddenly change if the manager changes its focus to an as yet unexplored subtree. For example, in Fig. 2 (f) in the appendix, the average length of critical positions drops intensely around iterations 135 and 185. However, since we only maintain the most recent 1,000 critical positions in the critical queue, old critical positions are kept temporarily for a short time and are soon replaced by new critical positions. In addition, we ran an additional experiment for using online-CP to solve opening *KA* with different critical queue sizes, from 100 to 10,000. The results are shown in Table 2 of the rebuttal one-page PDF. For larger queues, more positions are retained. Nevertheless, the solving times of using five different queue sizes are around 2,100s, demonstrating that this does not have a noticeable impact in practice. \n\n> [Q3] Table 1, What is going on with SB?\n\nIn a relatively small problem such as *SB*, online learning may not have sufficient time to fine-tune the PCN models. Besides, the online-SP+CP introduces additional overheads of sending both solved and critical positions than online-SP and online-CP. We suspect this overhead is the potential reason that online-SP+CP performs worse than the other online solvers in opening *SB*.\n\n> [Q4] Figure 4\n\nWe will change to use colorblind options. Due to the space limit, the bar plot will become too crowded and almost unreadable if it includes all 4 variants. We can add a new bar plot in the appendix including all variants.\n\n> [Q5] What is the direct evidence that the manager remembers what the OLT trainer forgets?\n\nForgetting is not a critical issue in our context since the forgotten knowledge (solved positions) is saved (remembered) in the manager solution tree, and the worker/trainer won’t need to solve/evaluate these positions again. This is the reason why we claim that the whole distributed solver (including the manager, workers, and trainer) can be seen as a life-long learning system.\n\n> How effective is a naive heuristic that computes a similarity between new positions and a database of solved positions?\n\nThis is an interesting idea, and possibly feasible if a heuristic can be trained to effectively compute similarity (defined as close for two positions sharing the same winning strategy, or far for very different strategies). Even for positions that are close but do not share the exact same strategy, parts of it can be reused via simulation [Kawano].\n\nHowever, to the best of our knowledge, naive heuristics to compute the similarity between two positions in Go haven’t been very effective. Given a Go position, the results might be completely different simply by adding or removing one stone. Instead of using similarity to match positions, it is common to build a transposition table in game solvers. The trick is to do partial matching with solved positions. For all solved positions, common patterns are extracted and stored in a database. If a new position exactly matches the same patterns in the database, the same winning strategy can be repeated. \n\n[Kawano] Kawano, Yasuhito. \"Using similar positions to search game trees.\" Games of No Chance 29 (1996): 193-202.\n\n> Could the fixed PCN be used to generate compressed/embedded state vectors to improve this matching?\n\nIf we understand your questions correctly, PCN already serves the role of learning a good representation (embedding). For example, in our online-SP method, given a series of solved positions, PCN should be able to further generalize to other unsolved positions and help prioritize selection. If you are proposing further improvements on PCN training, we are always looking for new ways to improve and would love to read some papers in this direction of research."}]

Author rebuttal:
Dear all reviewers, 

We appreciate your time and effort in reviewing our paper. We would like to address the common concerns raised by reviewers. The numbered citations refer to the sources in the paper’s bibliography.

* Novelty and contribution

First, to the best of our knowledge, we are the first to propose using online learning in game solving and present concrete and detailed methods (solved/critical positions). Furthermore, we provide sufficient experiment results to demonstrate that using the online learning method can achieve great advantages in game solving in terms of solving time and nodes searched. 
Second, in terms of solving 7x7 Killall-Go, our online learning game solver is able to solve 16 three-move problems from four different opening groups, while the original state-of-the-art solver [13, 38] can only solve two five-move openings. In conclusion, our experiments not only extend solving 7x7 Killall-Go but also provide valuable insights for other domains in the community.

* Generalizability to other games

Our proposed online learning method (solved/critical positions) and manager job assignment are **game-independent** and can be easily applied to any other two-player zero-sum games such as Hex, Othello, Chess, etc. Beyond two-player zero-sum games, we believe that the online learning method can be extended to other problems with corresponding modifications, such as automated theorem proving, chemical syntheses, or other combinatorial search problems. However, we must emphasize that most worthwhile problems to solve often require every trick (i.e. domain specific knowledge) to be applied. This effort is non-trivial and highly specific, but entirely orthogonal to online learning, so we did not include other domains in this paper.

In addition, we attached a one-page PDF, including additional experiments for answering reviewer questions.
* Figures 1 and 2 provide a detailed analysis of the critical queue. (reviewer Q8Zg)
* Table 1 shows the scalability of our distributed game solver. (reviewer wrov)
* Table 2 shows the results of using different critical queue sizes in the online learning solver. (reviewer wrov)


Meta-review: The paper presents a novel variant of AlphaZero for solving perfect information, zero-sum games. This is a straight-forward idea to adapt the machinery of AlphaZero to the case of game-solving rather than strong game-playing. The method is well-motivated and very clearly well-presented. With one minor exception (noted below), the authors give a very good coverage of the context and related work in the field (proof number search, etc.) which is especially important to this paper, since NeurIPS has not been a traditional venue for this kind of work. The results are impressive and it's clear that the method can easily generalize to other games despite having experiments for only one game. 

However, there is one critical point that is imperative that the authors address: the nomenclature issue pointed out regarding the term "Online Learning". As NeurIPS is primarily a machine learning conference, this term is very well-understood to have a specific meaning within the NeurIPS and Machine Learning community, far more standard than how the authors are using it. In fact, there is an entire Wikipedia page devoted to this accepted meaning of the term (https://en.wikipedia.org/wiki/Online_machine_learning) which has also been used in many text books, as pointed out by the reviewers. This term also has to be removed from the title because it is misleading as a result. The suggested term of "online fine-tuning" seems quite appropriate to me, but I leave it up to the authors to decide on the specific name.

A minor issue: given the content of the paper, I was quite surprised not to see a citation to Monte Carlo Tree Search Solver (MCTS-Solver) by Winands et al '2008 (https://link.springer.com/chapter/10.1007/978-3-540-87608-3_3).  Of course, this is only related work since it combined solving and playing in one algorithm, but I feel like it's still worth mentioning in the early part of the paper.

Finally, the paper could benefit from pointing out its main limitation that this technique only applies to two-player zero-sum games with perfect information.
Decision: Accept (poster)