Wang et al.: Making a Puzzle Solver the Teacher for Every Single Move — Fukai Reads

TL;DR

When you train a language model to play a puzzle like Sokoban or Minesweeper over dozens of turns, a single win/lose reward at the end says nothing about which individual move mattered. This paper proposes CAST, which puts a domain-specific puzzle solver (a search algorithm) beside the learner as a teacher, and for every single move computes how much the remaining distance to the goal shrank, feeding that into the training signal.

Across Sokoban, Minesweeper and Rush Hour (the sliding car-escape puzzle), the authors report beating every trained baseline they compared against, both at the difficulty tier used for training and at one tier harder that the model never saw. The three-game average success rate rises from 16.6% for the plain 4B model to 62.1%, and on unseen difficulty from 5.9% to 28.4% (Table 1).

The side effects are the interesting part. Querying the solver costs roughly 73 parts per million of a training step's wall clock (Figure 6), and a learned value network works nearly as well as the exact solver (Figure 5). The core of the paper, as I read it, is that a single scalar — remaining distance to the goal — is enough to act as a teacher, without ever naming the correct move.

Introduction

Today's paper is arXiv:2607.25308, "CAST: Game Solvers as Turn-Level Teachers for LLM Agents." Eleven authors, led by Yu Wang and Yi-Kai Zhang (equal contribution), with Wentao Shi, Ziang Ye, Yuchun Miao, Yueqing Sun, Qi Gu, Xunliang Cai, Lan-Zhe Guo, Han-Jia Ye and Fuli Feng. Affiliations: USTC, Nanjing University, Wuhan University, and Meituan. Submitted 28 July 2026, filed under cs.CL and cs.AI.

The arXiv record carries no conference note and no journal-ref, so I treat this as a preprint that has not been through peer review. Posted less than a week ago, its citation count is effectively zero — this has not yet been widely discussed. The implementation is public on GitHub (Wloner0809/CAST).

I picked it for a simple reason: the three evaluation games are Sokoban, Minesweeper and Rush Hour, all formats anyone who makes puzzles has built by hand at some point. And the paper states plainly, in a table, how it defined difficulty. It is an AI paper, but the material translates easily into the vocabulary of puzzle design.

Background

Training language models on games has converged on RLVR (reinforcement learning with verifiable rewards — rewarding only what can be checked mechanically). On tasks where correctness is machine-checkable, that is more trustworthy than a learned preference model. But in long-horizon games, the verifiable reward arrives exactly once, at the end.

That is the problem the paper names. Under methods like GRPO, one whole trajectory receives a single score, which is then handed identically to every turn and every token. The authors call this "the root of the credit-assignment failure in long-horizon games" — credit assignment being the job of deciding which action deserves the outcome. If a strong opening move and a weak thirtieth move get the same number, the model has no way to know what to fix.

The obvious fix is to score each turn. Existing options fall into three families: run a tree search (expensive), train a model to score intermediate progress (no guarantee the scorer is right), or compare across sibling trajectories (the GiGPO direction). The authors summarise these as leaving "trade-offs among computation, supervision, and signal reliability." Into that gap this paper inserts an obvious fact: for puzzles, exact solvers already exist.

Approach

Put into words, CAST is startlingly plain. A solver can report, for any board, the minimum number of moves left to the goal — the paper calls this cost-to-go. Every time the model makes a move during training, you compare the cost-to-go before and after, and use the difference as the score. An optimal move shrinks it by one, so it scores +1; a move that makes no progress scores 0; a harmful move goes negative. No formulas needed: think of it as a per-move progress meter.

Dead boards — a Sokoban box shoved into a corner — have infinite cost-to-go, and an infinite penalty would wreck training. The paper recounts it as "you lost the moves' worth of progress you had banked," keeping it finite. Two shaping steps follow: an asinh transform (near-linear for small values, compressive for large ones, preserving sign so that harmful/neutral/beneficial stays legible) and a batch-wide rescaling. Notably they do not subtract the mean, because zero has to keep meaning "no progress."

This per-move signal is added, with weight 0.1, on top of the usual win/lose score. The underlying algorithm is DAPO (a GRPO-family variant), and the definition of winning is untouched. Theoretically, under the assumption that the solver is near-optimal, maximising this progress signal is shown to be equivalent to on-policy distillation from the solver — learning the teacher's preferences on boards the student itself walked into. Crucially, that requires no distribution over the teacher's options, only the single scalar.

They train exactly one model: Qwen3-4B-Instruct-2507, roughly four billion parameters. The board is rendered as text, the model reasons and then emits one move in ReAct style, and illegal moves do not end the episode — the system replies "invalid" and the turn is simply spent. All three puzzle sets are generated automatically; for Rush Hour only boards whose exact shortest solution falls in a target length range are kept.

Findings

The headline numbers are in Table 1. Three-game average success (four attempts per instance, averaged over three training runs): plain 4B model 16.6%; baselines GRPO 44.9%, GSPO 41.9%, DAPO 44.7%, GiGPO 45.4%; CAST 62.1%. On the unseen harder tier: plain 5.9%, best baseline GiGPO 20.8%, CAST 28.4%. Concretely, against the same DAPO backbone, that is +17.4 points in-domain and +9.7 points on unseen difficulty.

The largest single-game gain is Minesweeper, +14.9 points over the best baseline in-domain. But the authors themselves write that its unseen-difficulty score "of 11.0 leaves room for improvement on harder instances" — winning is not the same as solving. Among the closed models listed for reference, CAST's 62.1% beats Gemini-2.5-Flash at 58.7% and Claude Sonnet 4.5 at 50.4%, but falls well short of Opus 4.6 at 79.9%.

Training speed is reported too. CAST reaches DAPO's final validation score after 120 / 200 / 140 steps on Sokoban / Minesweeper / Rush Hour, against DAPO's own 200 / 400 / 240 — a 1.7–2.0x speedup (Figure 3). Solver queries cost 8.4% of one environment step, 0.01% of a full trajectory, and about 73 parts per million of a training step's wall clock (Figure 6). Generation dominates, so the teacher is essentially free.

There is an ablation study on Sokoban — removing design elements one at a time to see what carries the result. Weight 0.1 is best: too small and it behaves like outcome-only training, too large and it climbs early then collapses. Dropping asinh hurts most, letting outliers dominate updates. Dropping the batch rescaling matches early on but plateaus late. I should note that this figure reports no numbers, only curves and qualitative description.

Where you can use it

One. Reuse the paper's "how much did cost-to-go drop" as a difficulty metric for hand-made puzzles. If you are building something Sokoban-like, you already have a solver. Run it along your intended solution and plot how the remaining distance moves. Flat stretches where it falls steadily are "long but thoughtless" regions; branch points where most legal moves score zero or negative are where players get stuck. What the paper uses as a training signal doubles as a hard-spot detector for humans.

Two. It bears directly on hint design. Most puzzle hints tell you the next move. This framework suggests another route: return no move at all, only a scalar — that move gained one step, or nothing, or made things worse. You can unstick a player without showing the answer, which preserves the feeling of having solved it. For a daily puzzle, cross-referencing hint usage against the progress meter tells you automatically which positions confuse people.

Three. Difficulty calibration for generated content. In Table 3 the authors build difficulty tiers from board size plus one count (boxes, mines, vehicles), and for Rush Hour they sieve generated boards, keeping only those whose exact shortest solution falls in a target range. For hyper-casual PCG (procedural content generation), three steps suffice for a difficulty curve: generate, measure shortest solution with a solver, shelve by move-count band. The implementation cost is one solver.

Four, more speculative. The paper reports that a learned value network substituted acceptably for the exact solver (Figure 5). Which suggests that for rules where no solver is writable — puzzles with luck or hidden information — you might learn board promise from a large play log and build the same progress meter. But that experiment covers one game and reports no numbers, so treat it as a direction rather than a result.

Limitations

What the authors admit. Minesweeper's unseen-difficulty score of 11.0 is low; hard boards remain out of reach. For Minesweeper they state plainly that "partial observability makes an optimal deterministic cost-to-go ill-defined," so they substitute the work a particular deterministic solver needs — not a true optimum. They also note that board generation does not filter for no-guess solvability, so some boards may still require a probabilistic guess. On the theory side, they concede that if the solver deviates from optimality, the distillation interpretation degrades proportionally.

From here, these are things I noticed as a reader. First, this paper has no Limitations section. Searching the full text, the word "limitation" does not appear once. The weaknesses are scattered through an appendix discussion of assumptions, and the reader has to assemble them. That may be a function of preprint status, but it is a reason not to weigh this the same as a peer-reviewed paper.

Second, exactly one model at one size is trained: Qwen3-4B. Whether the progress signal helps as much on larger models, or fades on models that already plan well, cannot be read off this paper. Third, the method presumes you can write a solver for the game, and three were written individually. One could observe that the three chosen games are precisely the ones where a solver is easy. The learned-value-network substitute was tried on one game only.

Fourth, what struck me most is the size of the difficulty step. The "unseen" tier in Table 3 is a single notch up — 6x6 with two boxes to 7x7 with three. Scoring only 34.8% there is a reason to read the generalisation claim modestly. And from a puzzle designer's eye, going from two boxes to three does not merely raise difficulty; it can change the kind of insight required. I would be careful about filing both under the single word "difficulty."

How Fukai reads it

This is my own reading. I would rather take this paper not as a story about credit assignment in machine learning, but as an experiment in a design question: how far can you collapse the difficulty of a puzzle into a single scalar? The one meter — how fast the remaining distance falls — captures difficulty-as-search-length remarkably well. But the fact that cost-to-go could not even be defined for Minesweeper, and that adding one box halved the score, is evidence in the other direction. In the vocabulary of design criticism, what this paper automates is the judgment of whether a player is stuck, not the judgment of what makes a puzzle good. The former is measurable. Nobody has measured the latter yet. That line, I think, is drawn clearly on the back of these tables.

Closing

If you want the step before this paper, look at GiGPO (Feng et al., 2026), in the same family of per-turn scoring. It builds turn-level credit without any external solver, by comparing sibling rollouts that reached the same state. Read alongside CAST, the pair maps out the contrast between having a solver and not having one.

If you come from the generation side, the closest neighbours are the search-based procedural generation lineage and the execution-gated self-distillation work covered here earlier. All of them measure difficulty by a solver's shortest solution and shelve content by it; what CAST adds is a reversal of direction — showing that shelf to a model in training, one move at a time, rather than to a player.

Tomorrow I will brew the coffee strong again and skim the new listings. A day with three puzzle names in a single title is a good day.

References

Papers and materials referenced in this article:

・CAST: Game Solvers as Turn-Level Teachers for LLM Agents (Yu Wang, Yi-Kai Zhang, Wentao Shi, Ziang Ye, Yuchun Miao, Yueqing Sun, Qi Gu, Xunliang Cai, Lan-Zhe Guo, Han-Jia Ye, Fuli Feng, 2026, arXiv preprint)

・DOI: 10.48550/arXiv.2607.25308 (arXiv, not peer-reviewed)

・Full HTML text (including Appendix B on environments and Appendix C on theory)

・Code: github.com/Wloner0809/CAST

・Related work (the paper's main process-level baseline): Group-in-Group Policy Optimization for LLM Agent Training (Feng et al., 2026)

・Citation check: Semantic Scholar / Google Scholar