Rome Wasn't Built in One Turn: Replay-Grounded Reward Signals for Long-Horizon Freeciv Agents

AI summary

Overview

Research area: Reinforcement learning for large language model (LLM) agents in long-horizon strategy games, with a focus on reward design and reward-signal grounding.

Technical level: Advanced. The paper assumes familiarity with reinforcement learning, advantage estimation, and LLM fine-tuning, though its central idea (current score is a bad predictor of who wins) is intuitive.

Scope: The paper diagnoses "scoreboard traps" — positions where the higher in-game score leads to a worse eventual outcome — across eight strategy games, and proposes a replay-based harness, a trained judge, and a phased training recipe to give Freeciv agents reward signals grounded in replayed future outcomes.

What This Paper Is About

Training LLM agents to play long strategy games is hard because the only reliable feedback arrives at the very end of a game that runs for hundreds of turns. The obvious shortcut — using the in-game scoreboard as a dense reward — is unreliable, because a position that looks ahead right now often turns out worse later; the authors show this happens in 8–68% of position pairs across eight strategy games. The paper's goal is to build a reward signal that reflects how a position actually turns out, by branching from saved game states, replaying them to the end, and training a language-model judge on those realized outcomes.

Key Contributions

1. Scoreboard traps. The authors define and measure the phenomenon where the higher-scoring of two positions leads to a worse future outcome, showing it affects 8–68% of decidable position pairs across eight strategy games (26% in Freeciv under the civ2civ3 ruleset, 27% under classic), and that frontier LLMs fall below chance at detecting it in Freeciv.

2. CivHarness. An open-source harness for agentic reinforcement learning in Freeciv that saves game states, branches on alternative decisions with deterministically seeded replays, and records observations, actions, and outcomes, so any feedback signal can be checked against actual future outcomes from shared positions.

3. CivTelescope. A pairwise language-model judge fine-tuned from Qwen2.5-7B on replay outcomes (LoRA rank 16, 10,800 training pairs) that predicts which of two positions will reach the higher terminal score, reaching 77.5% accuracy on held-out trap pairs and generalizing to new game starts, later turns, and an unseen ruleset.

4. CivMarshmallow. A phased training recipe (phases with 20, 40, 80, and 120 turns remaining) that uses CivTelescope as a dense reward, alone or combined with scoreboard or end-of-game rewards in a hybrid schedule over full games.

Main Findings

• Traps are common and worsen with game length. Trap rates range from 8–68% across eight games. In civ2civ3, the Freeciv trap rate falls from 55% in the first tenth of a game to 8% in the last tenth, while across game lengths the scoreboard's correlation with terminal score drops from 0.81 (60-turn games) to 0.12 (80-turn games) and the trap rate rises from 30% to 54%.

• Frontier models fail on trap pairs. Six LLMs, from frontier closed models to a small open model, score 0.26–0.34 on held-out Freeciv trap pairs — below chance — even though they reach 0.77–0.82 on non-trap pairs. Warning them in the prompt that visible scores can mislead still leaves frontier models at only 0.32–0.38. Four of five frontier models also rank below chance in Chess, and two of five in Othello.

• Replay-grounded judging beats preferences and regression. CivTelescope reaches 0.775 on held-out trap pairs (versus 0.260 for its own zero-shot backbone and 0.258–0.343 for the frontier models), and 0.878 on non-trap pairs. A judge trained on GPT-5.6-sol's preferences instead reaches 0.391 — near its labeler's own 0.330. A regression value head on the same backbone is at chance on held-out trap pairs (0.520, against 0.688 for CivTelescope on the same pairs). Out of domain, CivTelescope reaches 0.592 on classic trap pairs versus 0.241 for its backbone.

• The judge uses scores but does not reduce to them. With all score numbers masked, trap accuracy is 0.687; with only score numbers and no textual description, it falls to 0.113 while non-trap accuracy stays at 0.842 — which is the scoreboard heuristic itself.

• Biggest training gains come mid-game. At 80 turns remaining, CivTelescope as a reward gains 8.94 points, against 5.04 for the sparse end-of-game reward and 0.83 for the scoreboard reward — 77% more than the best baseline — with paired win rates of 81% against sparse and 96% against scoreboard. This is where traps are frequent: in the policy's own 120-turn training games, same-start rollouts are traps 18–22% of the time over turns 30–69.

• Hybrid rewards win over the full game. At 120 turns remaining, scoreboard → CivTelescope gains 5.21 points and sparse → CivTelescope gains 5.15, against 4.87 for scoreboard, 2.87 for sparse, and 2.77 for CivTelescope alone. The handover happens at turn 35 because in turns 10–29 the judge's potential correlates only 0.09–0.10 with terminal score (versus 0.34–0.36 for the scoreboard), rising to 0.41–0.60 from turn 30 on.

• Order matters in the hybrid. Reversing the schedule removes the gain: CivTelescope → sparse gains only 1.76, and scoreboard → CivTelescope → sparse (returning to sparse at turn 80) gains 2.84.

• Trained policies beat prompting scaffolds. The best CivMarshmallow policy (sparse → CivTelescope) reaches a terminal score of 23.4 on 45 held-out full-game positions, against 13.2 for the best prompting scaffold (SAGA); it is eliminated in 4% of games versus 9–26% for scaffolds, and proposes invalid actions in 0.4% of decisions versus 41.6% for SAGA.

• Rewards must be applied throughout the game. Using CivTelescope only on a game's final position does not help (−0.13 points per iteration at 40 turns remaining, two-seed mean), whereas applying it at every decision improves by 0.44.

Methodology in Plain English

Freeciv is an open-source empire-building game where four players manage units, cities, research, and diplomacy over hundreds of turns; the agent controls one player on a 1000-tile map against three built-in AI bots at a fixed difficulty. The researchers first built CivHarness, which takes a saved game state and replays it forward many times with different random seeds, all the way to the end of the game, recording the final score each time. The average of those final scores becomes the "ground truth" value of that position — an expensive but honest answer to "how does this actually turn out?"

Using this replay oracle, they constructed trap pairs: pairs of positions where the scoreboard prefers one but the replayed outcomes prefer the other, keeping only pairs where the two outcomes differ by more than twice their pooled error. They then fine-tuned a 7B language model, CivTelescope, to look at two text descriptions of positions and pick the one with the better replayed outcome, querying both orderings and averaging to cancel position bias.

To turn the judge into a reward, they compare each state against a reference set of positions with known terminal scores, convert the judge's average win probability into a quantile, and read off the corresponding score — producing a potential with the same units as the game's final score. That potential is plugged into generalized advantage estimation, with the reference set periodically refreshed and only accepted if it still ranks held-out recent rollouts well.

Training proceeds as a reverse curriculum: start with 20 turns remaining, then 40, then 80, then the full 120, each phase resuming from the previous checkpoint. For full 120-turn games, the hybrid reward gives the simpler signal (scoreboard or end-of-game score) early and hands weight to the judge over time via a sigmoid schedule centered at turn 35. Everything is compared against baselines trained identically, and evaluated on 45 held-out positions with eight games per position.

Why This Matters

Impact on research. The paper provides a concrete, measurable counterexample to the common practice of using a game's displayed score as a dense reward, and shows that preference-distillation from a strong model inherits that model's blind spots while replay-grounded labels do not. The released harness lets other researchers check any proposed reward signal against actual future outcomes from shared starting positions, which is a reusable evaluation primitive for long-horizon agent work well beyond games.

Real-world applications:

• Agent training for long business or operational workflows where the visible dashboard metric (revenue, engagement, tickets closed) diverges from the eventual outcome, and where "replay from a saved state" maps onto simulation or backtesting.
• Process reward models for reasoning and coding agents, where the paper's finding that replay-grounded labels beat preference labels suggests a cheaper path to step-level supervision.
• Evaluation of LLM judges in any setting where a judge might be anchored on a salient but misleading number.
• Simulation-based decision support (supply chain, resource allocation, portfolio management) where a slow simulator can be branched and rolled forward to value a decision.

Industry relevance. The result that a trained 8B policy reaches terminal score 23.4 versus 13.2 for the best prompting scaffold, with a 0.4% invalid-action rate versus 41.6%, is a practical argument that reinforcement learning with a well-grounded reward outperforms elaborate prompting scaffolds — and that the reward design, not the scaffold, is where the leverage is.

Future Directions

• Extending the replay oracle to imperfect-information and multi-agent settings where branching from a saved state is harder than in Freeciv, and where opponents' hidden information limits what a replay can establish.
• Reducing the cost of the replay oracle, which requires many full-game branches per position, and testing whether cheaper partial rollouts preserve the judge's advantage.
• Applying replay-grounded judges to domains outside games — the paper's own framing suggests long-horizon agent trajectories in web use and device control as candidates.
• Improving the judge's reliability early in games, where its potential correlates only 0.09–0.10 with terminal score and the hybrid reward must fall back on the scoreboard.

Target Audience

Researchers and practitioners working on LLM agents, reinforcement learning with verifiable or learned rewards, and long-horizon decision-making; also useful to game-AI engineers and to anyone building process reward models or LLM-as-judge pipelines, since the label-source ablation (0.610 for replay labels versus 0.391 for preference labels) is directly relevant to judge construction. Beginners can follow the problem framing and headline numbers but will need RL background for the reward-shaping and advantage-estimation sections.

Authors’ abstract

Training language-model agents to play long-horizon strategy games is hard because deterministic feedback is sparse and often arrives only at the end of a game. In-game scores can offer dense signals, but they do not reliably predict future outcomes: in 8-68% of position pairs across eight strategy games, the higher-scoring position leads to the worse outcome. We term this phenomenon scoreboard traps. In Freeciv, an open-source turn-based empire-building game where several players manage units, cities, and diplomacy over hundreds of turns, we look into better reward signals for gameplay agents. To facilitate this, we build CivHarness, an open system that saves current game states, branches on different decisions, and replays the game to future turns to provide measurable long-horizon feedback from saved positions. We use CivHarness to train CivTelescope, an LLM Judge that predicts which one of two game positions will yield the better outcome. On scoreboard-trap pairs, CivTelescope is 1.3-2.0 times more accurate than off-the-shelf language models, and it generalizes to new game starts, later turns, and unseen rules. We then train a Freeciv gameplay agent with CivTelescope as a dense reward, and call this recipe CivMarshmallow. When used in the middle stage of the game where scoreboard traps are common, CivMarshmallow reaches an average training phase gain of 8.94 points, 77% more than the best baseline, the end-of-game reward. Over the full 120-turn game, CivMarshmallow uses a hybrid reward that starts from the scoreboard or the end-of-game reward and shifts to CivTelescope as the game advances; this hybrid reward scores highest among the rewards we compare.