acceptodds
Under review as a conference paper at ICLR 2027

Learning Search Guidance from Solver-Generated Ground Truth

Abstract

AlphaZero made strides in the field of game playing not just because it trained via self-play, but also because it learned *tabula rasa*, i.e., from a random initialization on self-generated data. That learning philosophy has not yet made its way into the field of game solving, which requires deriving the game-theoretic value of the initial position rather than merely selecting a good move. In this paper, we apply AlphaZero's learning philosophy in the context of game solving to introduce AlphaSolve, a game solver that learns search guidance from the game-theoretic values of intermediate nodes it proves while solving a game. We verify it on previously solved games: Connect Four and three Breakthrough variants. Programs for solving games are evaluated on their efficiency, which is determined by how well they search the game tree for a proof of the game-theoretic value. Prior art has relied on estimating proof cost (the number of positions required to solve a node), but we show that on Connect Four training on win/loss outcomes (as AlphaZero does) is competitive with training on the measured proof cost as the value target. AlphaSolve generates roughly a hundred times more ground truth labels than self-play game trajectories, and on Connect Four we find that a small share of trajectories mixed into the verdicts is better than either stream alone. This is significant because reinforcement learning algorithms are notorious for investing heavily in data generation, but AlphaSolve generates ground truth labels in abundance.

Primary area:
reinforcement learning
Keywords:
game solving, weak solving, Monte Carlo tree search, AlphaZero, self-play, proof-number search, AND/OR search, proof cost, tabula rasa learning

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_hYEQOpenReview ↗
Rating
2
Confidence
4
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper introduces AlphaSolve, a game solver using AlphaZero style learned guidance to more quickly solve games.

Critical strengths

Approach is interesting, and so are results. This introduces a method for best-first solvers. Limitation is that not compared against state of the art other solvers.

Critical weaknesses

The three listed contributions are measurement facts. It would be nice to also provide a more high level contribution concerning the impact on the field of Game Solving.

Related Work, the term weakly solving goes back much further than the listed references, and should be introduced formally. Scholarship appears weak, with many older references, starting with the first survey. There are many diverse topics in related work. Are they all relevant?

Full code is not provided as part of the reproducibility requirements. There is no supplementary material. Why?

Questions for authors

The footnote on page 1 should add a reference to the definitions of strong and weak solving.

The paper is light on discussion/future work. How would this approach work in larger games? Can it solve 8x8 Othello, Chess? Please shrink related work and enlarge discussion, and provide some ideas how this coudl work on state of the art solver problems (such as 8x8 Othello).

Unbalanced paper. weak reject.

2 comments

Higher-level contribution. §1 now opens the contributions with it: solvers have so far started from guidance built outside the solve, and we show a solve can supply its own, from random initialization on its exact verdicts. The three findings are the evidence for it.

Weak solving and scholarship. §2 gives Allis's (1994) definitions of ultra-weak, weak and strong solutions, and the page-1 footnote points to them.

Balance and larger games. Related work is shortened to what the paper uses, and the conclusion (§6) now discusses larger games, including 8×88 \times 8 Othello and chess.

State-of-the-art comparison. See Table 3: alpha-beta and Pons's Connect Four solver.

Code. We intend to release the code upon approval of our institution's release process. Algorithm 1 (Appendix B) and Appendix A specify the search and every setting used.

Reviewer_hYEQOpenReview ↗

Main concern remains

Thank you for your remarks. Adding 8x8 Othello and Chess is worthwhile. The overall feeling remains: interesting idea, but not groundbreaking, and writing style is for insiders. Code is still not released, main contributions are still rather technical, without reference to broader impact or outside the narrow field of combinatorial game solving, few recent related work references, difficult to scale to larger games.

I feel the paper has improved, but I still believe this paper is better suited for a more focused, technical/games oriented venue, where AlphaZero-inspired combinatorial game solving might be better appreciated.

I leave my score unchanged

Reviewer_zXoKOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper proposes a novel way to use solver-generated data generated while solving a game as an additional supervision signal. If I understand it correctly, it basically gives a richer training signal than the final verdict via intermediate nodes, not just the end result.

Critical strengths

I find the contribution to be very interesting. Based on how the authors presented it, it seems to be rather novel, with experimental results backing up substantial gains compared the comparisons in Table 1 (although whther the comparison is representative for the field, I do not know). The authors contextualise the result by comparing it to the approach by AlphaZero, which I think is useful for the readers, since probably many more people know AlphaZero than solving approaches.

Also, I really like the figures in Appendix B. I think they deserve to be moved to the main text because it makes the understanding of the descriptions of the tree structure much easier.

Critical weaknesses

There are a few things I'd remark on. I must say that I'm not an expert on games, and many of the experimental settings and the object of study are presumably standard in this literature. However, it clearly makes it harder to understand. The paper is not really self-contained because the games that are referred to are not really explained. The reader can't really tell from the paper what those games mean, what the actions are, and how you can solve them (what is the winning condition, the rules).

There are a few nice conceptual aspects of the paper. For example, Figure 1, which I think has a good effort in terms of trying to illustrate what the algorithm does—even that, I think, is not really self-contained. Many of the symbols represented on the figure are not explained (in the caption). For example, it's unclear to me what is trained, what the model is, and similar. To that extent, I think making the paper more self-contained, resolving the acronyms (df-pn, PUCT, TT), and explaining all the symbols would clearly improve ease of understanding.

Also, on the experimental side, without knowing the standards in this community, I find the fact that you are only using one training run (apart from one with n=6) means that the conclusions might not be as robust. I would urge the authors to at least explain their choice, since the computation does not seem to be that expensive.

If the authors make these changes, then I'm happy to update my score and vote to recommend acceptance based on the discussion with other reviewers.

Questions for authors

N/A

2 comments

Thank you for the detailed suggestions; we have adopted all of them:

  • Games: the rules of Connect Four and Breakthrough open §4.
  • Acronyms: MCTS, df-pn, PUCT and TT are spelled out at first use.
  • Figure 1: its caption now defines every symbol and says what is trained.
  • Appendix B figures: moved into §3.2 (Figures 2 and 3).
  • Runs: every arm was rerun at n≥3n \geq 3 (n=6n = 6 for the two main Connect Four arms). The conclusions hold, except that f=0.25f = 0.25 now also helps (see the general comment).

We hope these address your concerns.

Dear Authors,

Thank you for your response. I agree with Reviewer hYEQ that, though the paper has somewhat improved, the writing is still very dense and hard to follow. Thus, I maintain my score.

Reviewer_2K8sOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper proposes an algorithm that learns to solve games whils solving them. It generates solved states to learn from by self play similar to Alpha Zero except that it used solved states as data. It solves already solved games better than MCTS Solver. It is not compared to strong solving algorithms and does not solve new games.

Critical strengths
  • An improvement over MCTS Solver
Critical weaknesses
  • The algorithm is not tested against strong game solvers
  • The games solved are too simple
  • The experimental results in Table 1 are incomplete
Questions for authors
  • Can you complete Table 1?
  • Is your algorithm better than Iterative Deepening Alpha-Beta with TT and move ordering heuristics?
1 comment

Table 1. It is now complete: all four boards at n≥3n \geq 3.

Iterative-deepening alpha-beta with TT and move ordering. We implemented it (transposition table, history and killer heuristics, 13 threads on the same machine, rules only) and added Pons's Connect Four solver (Table 3). Alpha-beta is about twice as fast as AlphaSolve on 5×55 \times 5 Breakthrough, but did not finish 6×56 \times 5 Breakthrough or Connect Four within 8 hours, where AlphaSolve takes 2h32m and 1h57m. Pons, engineered for Connect Four, is about 40×40\times faster than AlphaSolve. Limitations (§5) states this plainly.

Simple games / no new solves. We agree that none of these games was open. Our contribution is where a solver's guidance comes from: it can be learned from random initialization on the solve's own verdicts. That complements, rather than replaces, the engineered solvers that reach larger games (§6).

Comments on the paper

1 comment

We thank the reviewers. We have uploaded a revised PDF; the main changes:

  • Every result was rerun, at n=3n = 3 per arm (n=6n = 6 for the two main Connect Four arms). Table 1 is now complete; the frozen-network controls move to their own table (Table 2).
  • Baselines (Table 3, §4.1): iterative-deepening alpha-beta with a transposition table and history/killer move ordering, and Pons's Connect Four solver.
  • Self-containment: game rules (§4), acronyms, Figure 1's symbols, and the policy-target figures moved into §3.2.
  • Framing: a high-level contribution (§1), formal definitions of weak solving (§2), a shorter related work, and a discussion of larger games (§6).

One finding changed: f=0.25f = 0.25 now also speeds up the solve (Table 5), so we no longer claim that a large trajectory share hurts.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.