Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper focus on solving a game, i.e. deciding the win/lose outcome for each game state. In order to finish the task in limited time, it is necessary to expand as little leaf nodes as possible when searching on the game state tree. The number of such leaf nodes is defined as proof cost and the paper proposes to set it as the new learning target based on the AlphaZero learning framework. Experiments are conduct to verify the ability of the model by solving $15 \times 15$ Gomoku and $9 \times 9$ Killall-Go games in limited time.
main_review: Strength:
The proposed PCN network equipped with AlphaZero (MCTS in precise) or FDFPN solver is able to solve the game more efficiently then the original algorithm. Sufficient experiment results and illustrations are provided.

Weaknes:
1. The term, solving a game, is ambiguous without a formal description in math. It is easily confused with computing a Nash equilibrium or other solution concept for a game. This brings difficulty to understand what problem this paper is going to solve.
2. The contribution of this work is not well discussed in this paper. I wonder whether it is significant to quickly solve a game from scratch. It seems that a pretrained AlphaZero or other programs is als oable to solve the game (as what they didi in generating the game examples). Moreover, even the importance of solving a game is not well described in this paper.
summary_of_the_review: This paper proposed a new learning objective that enhance AlphaZero and FDFPN to solve a game. However, without a sufficient discussion about the significance of the studied problem, I do not recommend acceptance.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper describes an AlphaZero-like approach to train networks from self-play, where the networks are trained to predict (logarithms of) proof costs / disproof costs, which are heuristics closely related to proof numbers / disproof numbers. Empirical evaluations show that these heuristics can be used by MCTS-based solvers as well as solvers based on Proof Number Search, and effectively enable both types of solvers to solve problems more efficiently / solve more problems in fixed time budgets.
main_review: **Primary Strengths**:
1) Well-written paper, almost everything is clear.
2) Interesting contribution.
3) Good empirical results.

**Primary Weaknesses**:
I really don't have much to remark here. I do have several minor issues (like some notation) and a few small points that confused me, but I expect these should be relatively easy to resolve; see detailed comments below.

---

**Detailed Comments**:
- Acronym FDFPN used in abstract without fully writing it out, and (arguably unlike MCTS) this one really isn't common enough to assume that every reader will know what it is.
- When putting words/phrases in quotes, use backticks instead of '' on the left-hand side
- In Eq. (1), the symbol on the left-hand side of the equality (currently $a$) should probably be different from the symbol used under the argmax (also $a$) on the right-hand side. I'd suggest using $a^*$ on the left-hand side.
- First paragraph of 3.1 ends with "Then the inductive definition of $n(s)$ is $n(s) = 1 + \sum_{i=1}^b n(s_i)$." But the next paragraph immediately seems to contradict this, because it's actually only correct for AND nodes, not for OR nodes.
- "Then, $n(s_{AND}) = 1 + \sum_{s_i} n(s_i)$ for all children $s_i$" --> the "for all children $s_i$" phrasing is a bit confusing since the sum already implies a "for-all loop". Should probably be changed to something like ", where $s_i$ are the children of $s_{AND}$."
- In Subsection 3.2, I got really curious about whether there is any particular reason for not adding $+ 1$ to the definitions of the $\bar{n}(s)$ heuristics, as you also would for the real proof/disproof numbers? This would be worth clarifying.
- Final sentence of first paragraph of 4.2: the results really don't back up this claim about "closing the gap in performance" in my opinion. The gap is almost identical.

---

**After authors' response**: I am satisfied with the authors' response and revisions.
summary_of_the_review: A well-written paper, with no major issues. Some minor issues but I expect these should be relatively easy to clear up or resolve.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper uses a modified AlphaZero MCTS training loop to generate proof tree size heuristics, for use in MCTS or proof number search (PNS). The authors demonstrate that both heuristics outperform no heuristic and a existing heuristic method based off of standard search policy and value functions. The ideas and results are a nice step forward in a search domain that is is not always well-addressed by classical value-maximising search.
main_review: In general, I like the ideas and results in this work, and would like to see it published. My main concern is that the paper has a organisational issue, with a recurring pattern of discussing things before they are introduced. I like the author's discussion of the background material, but found the discussion of the algorithm hard to follow, despite being familiar with both PNS and AlphaZero. Subjectively, it felt like the extra details I wanted to know were not where I expected them to be.

One suggestion for an easy-to-follow structure would be reducing the current level of detail in section 3.1, adding a brief mention of a similar notion of minimum disproof tree size, and adding a couple of sentences foreshadowing how approximations of these tree sizes will be the heuristic generated by the selfplay loop and then used in a modified PN solving algorithm. Then move the both the selfplay and solving algorithms to the beginning of section 3.2, and subsequently discuss the correctness / design choices afterwards.

--- Specific questions and comments ---
There is an unadressed issue of total computation time. While the heuristic generated during training is general, that training time is amortised over the number of problems that actually get solved. Where is that break-even point of 1500h training vs 30m search? For example, presumably for one problem the 1500h is best spent on a no-heuristic version of that problem, and for millions of problems that 1500h training time is cheap. 1000s of problems?  The 90 problems tested?

"Then the inductive definition of n(s) is n(s) = 1 + sum_i=1 n(s_i)."
The definition must include a distinction between OR and AND node, or the player to act, or ...? Otherwise for state s leading to a loss and a win, n(s) = 1 + n(L) + n(W) = 1 + 1 + inf = inf. The following discussion corrects this, but the statement as given here does not seem to be technically correct.

For clarity, consider indexing the proof tree size by the player of interest, as in n_p(s). This would help with two things. First, it would then be clear that n_p(t) is the size of the minimum proof tree of t for some particular player of interest, not the current player -- it is possible to misinterpret "number of tree nodes, denoted by n(s), for the player at s to win". Second, it would help smooth the jump from the fixed root of the selfplay training, to (dis)proving wins at other states s -- this works as long as the player of interest P(s) matches the P(s_0) for the initial game state s_0 used in the selfplay training, which is why OR/AND player is fixed.

"In practice, with an imperfect heuristic, the order in which children of AND nodes are searched will still have implications on the solution size, regardless of which search algorithm is used (MCTS or PNS)."
Is it possible to clarify why directly in the text, so the reader isn't left waiting to discover why, or stuck thinking about why?  Something like
"with an imperfect heuristic, the order in which children of AND nodes are searched matters because one child might lead us to discovering the mis-ordering faster than other children."

"Instead, we take advantage of the self-play phase in AlphaZero to collect game episodes"
This would be a good place to note that it's selfplay using a modified MCTS search -- don't leave this for the reader to eventually discover later on.

"There are some similarities and differences between our heuristic and the concept of PNs in PNS. First, PN/DN are meant to change as PNS progresses and new nodes are expanded and evaluated. In that sense, the PN/DN are a dynamic quantity used to signify the least number of nodes that need to be expanded to prove/disprove each node at that point in the search. In contrast, n̄(s) is a static estimate of an oracle number that represents the minimum proof tree size."
This starts with similarites and differences. What are the similarities?
Would it be simpler (and still correct) to describe PNs as a lower bound on n(s) - current_tree_size(s), the remaining work to build a proof tree, using an uninformed estimate of n(s)~=n̄(s)=1 for all unexpanded nodes?

"Second, PNS makes no assumptions ...  m̄(s)"
The introduction of m̄() at this point feels like a forward reference.  n̄() is related to the preceding discussion of minimum proof tree size n(), but this is missing for m̄. Consider adding a sentence at end of the discussion of minimum proof tree size, noting there is a similarly defined minimum disproof tree size m(s) that shows s is not a win.

"In our method, while OR nodes behave similarly in that the smallest n̄ value is chosen ... when training the heuristic network."
I found this paragraph confusing -- it is another forward reference to an algorithm which has not yet been given. Either the algorithm needs to precede this discussion, or this paragraph needs to be re-written to be a gentle, more general discussion of what properties a game-solving algorithm using n() and m() should have.

Experimental section:
Consider combining table 1 and 2. Comparing MCTS and PN seems like a natural thing to do, and splitting into two tables makes this harder.  If the authors prefer splitting the table so it is smaller, consider splitting by game instead?

Experimental section:
The choices in b_heur seem fairly safe, at least with respect to ratios of n(s) and n(s_child). Particularly using a b factor of the number of legal moves, versus all possible moves on an empty board. Given that, it seems like a surprise that b_max is often better than b_heur, and worth mentioning. Do the authors have a (short) explanation or conjecture that can be added? Is this not actually a surprise?

summary_of_the_review: I am generally positive about this paper. There are a few small issues to correct, and some things which could be expanded, but the basic pieces of a solid submission are there. Howeve, I do think that the readability of the paper could be substantially improved through some reorganisation and rewriting of some sections.

---  Thoughts after revisions and discussion ---
I think the readability of the paper could has improved. Even if it could be further improved, I think the paper is in a reasonable state for publication.
------
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: As we know that, from AlphaGo to AlphaZero, less and less expert knowledge is used. In this paper, however, the authors make AlphaZero becomes faster by modifying the training target of the AlphaZero algorithm, such that it prioritizes solving the game quickly, rather than winning, and training knowledge-based networks. Experimental evaluation is provided on 15x15 Gomoku and 9x9 Killall-Go problems.
main_review: This paper makes AlphaZero becomes faster by modifying the training target of the AlphaZero algorithm, such that it prioritizes solving the game quickly, rather than winning, and training knowledge-based networks. However, I have several concerns:

1. I think the discussion about the relationship between playing games and solving games is questionable. In this paper, they argue, “There are two main goals in the pursuit of strong game-playing agents. The first is to push the boundaries of artificial intelligence since games can be seen as simplified models of the real world. The second involves finding game-theoretic values, or outcomes given optimal play, for various games (van den Herik et al., 2002). These two closely related yet separate goals are commonly referred to as playing and solving games, respectively.” In other words, authors think playing games and solving games are two different goals. In my opinion, solving games is the first step for playing games, i.e., playing games is the goal for solving games. Otherwise, what is the goal for (after) solving games? Our goal should be using the computed strategy in a game, not just solving a game.

2. It is straightforward that this paper makes AlphaZero faster by modifying the target and using existing heuristic knowledge. As we know that, AlphaZero achieved super-human playing levels for many games without hand-crafted expert knowledge. We can expect that AlphaZero can perform better by adding expert knowledge. In addition, this work just incrementally modifies/exploits existing methods/heuristic knowledge.

3. The challenge for this problem in this paper is unclear. We know that the challenge for game solving/playing is the difficulty of searching the huge action space. If the problem in this has the same challenge, how does the proposed method mitigate this difficulty (in contrast to AlplaZero)?  
 
4. Experiments can be improved. Current experiments are only on 15x15 Gomoku and 9x9 Killall-Go problems. I suggest that the authors use the games in the original AlphaZero paper, e.g., the original Go and Chess, to better evaluate the proposed approach. AlphaZero can solve the original Go and Chess with the huge action space, and then we need to know if the proposed method can better solve them or not.

summary_of_the_review: It is straightforward that this paper makes AlphaZero faster by modifying the target and using existing heuristic knowledge.
review_title: null

Meta-review: This paper modifies the AlphaZero algorithm to generate proof tree size heuristics and shows empirical improvements over standard search algorithms. This is an interesting distinction that might lead to algorithms with distinct play styles and a deeper understanding of the games that we apply our agents to.

The two positive reviewers felt that it was a solid contribution, worthy of publication. There were some questions regarding the clarity of the writing that were addressed in the discussion phase. The two reviewers that gave lower scores felt that the paper did not do a sufficient job motivating the work and distinguishing itself from the literature. Ultimately, I agree with the positive reviewers, and it is my opinion that the revised version is acceptable for publication.
Decision: Accept (Poster)