Game Solving with Online Fine-Tuning

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.

Strengths

## originality Modest. 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. ## quality Good. The results show substantial improvements over baselines and the ablations are thorough. ## clarity Good. 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. ## significance Modest. 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. Below 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). The lifelong learning claim would benefit from direct evidence that the manager remembers what the trainer forgets. See the questions below for more detail.

Questions

- [Q1] How do the core algorithms scale? - How does performance change with more or fewer workers? - What are the demands in compute and memory? How do they scale with the size of the problem and/or workers? - [Q2] Does critical position prioritization break down when MCTS thrashes between expanding new shallow node and deeper nodes in the tree? - 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. - Is this not a problem in practice? Or is there a way to quantify this effect and measure it's impact? - [Q3] Table 1 - What is going on with SB? - Online-SP and online-CP both do very well compared to the baseline. But online SP+CP does substantially worse than either alone. - 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. - [Q4] Figure 4 - Include all 4 variants in the bar plot, not only baseline and online-CP. Also, consider changing the color scheme to be colorblind friendly. - [Q5] What is the direct evidence that the manager remembers what the OLT trainer forgets? - Is there any way to probe the checkpoints to demonstrate this phenomenon? - The claim is intuitive, but the results would benefit from a direct test / evidence for this claim. Below are some other less important questions / suggestions: - For PCN state estimates: - How effective is a naive heuristic that computes a similarity between new positions and a database of solved positions? (for solved positions using OLT) - 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. - Could the fixed PCN be used to generate compressed/embedded state vectors to improve this matching? - Could that apply to the learning process to prioritize selection of training samples?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

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.

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.

Strengths

- Relatively straightforward and simple, but good idea. - Good empirical results. - Paper very well written, easy to follow.

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). - 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.

Questions

### Suggestions - "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. ### Questions - "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.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

2 fair

Presentation

3 good

Contribution

2 fair

Limitations

No unaddressed limitations.

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. The 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). To address those issues, the paper proposes: - 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. - the fine-tuning of the PCN used using selected subgames which have been encountered during the proof process. - 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 - 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

Strengths

* Clear and exhaustive experimental evaluation * Strong experiment results * 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 * Many dependencies on previous work. Those weaken the overall clarity of the paper for people who are not familiar with the past literature * 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.

Questions

The following questions highlight parts of the paper which felt unclear or possibly benefitting from extra detail. 1. 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. 2. 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? 3. 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? 4. How different are the performances of alpha-beta search or PNS algorithms for the problem of game solving? On top of this clarifications, I'd like to hear the authors' opinion regarding the weaknesses I've highlighted in the previous section.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

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.

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. UPDATE: 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.

Strengths

+ The paper tackles a challenging problem of game solving, which has implications for combinatorial search problems. + 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. + 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. + 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). - 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. - 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. - 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). - 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. - (minor) The description of the experimental results could be tightened a bit more. Examples with suggestions below. - L283: Comparing "within 40000 seconds" with "more than one day" could be "~10 hours", "24 hours" or 2.4x faster. - L286: "1.29 billion or so" could be "~1.29 billion".

Questions

- Could you please describe the parts of the proposed algorithm or technical ideas that are novel? - The baseline used is the algorithm without online learning. Are there other baselines for 7x7 Killall-Go from prior work? - I assume that the reported runtimes include the time spent on updating the parameters. Please confirm this is the case. - 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? - 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. - Is it possible to include additional domains? Can you provide information on whether this approach works in other domains? - Is there a reason code wasn't included? Can it be included?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

3 good

Contribution

2 fair

Limitations

To an extent. The paper does a better job explaining its strengths than its weaknesses.