PaperlayerView exact revision on arXiv

Source-linked AI summary

Agents of Change: Self-Evolving LLM Agents for Strategic Planning

Nikolas Belle, Dakota Barnes, Alfonso Amayuelas, Ivan Bercovich, Xin Eric Wang, William Wang

arXiv:2506.04651v2cs.AI

TL;DR

Long-horizon LLM agents can struggle to sustain coherent strategies when they must repeatedly reinterpret evolving states, and few benchmarks test persistent strategy refinement against strong adversaries. HexMachina separates undocumented-environment discovery from strategy improvement, preserving executable artifacts as it iteratively evaluates players. In Catan, it is reported to outperform traditional LLM agents and common continual-learning architectures while rivaling AlphaBeta.

  • Problem

    Few benchmarks test whether agents can refine coherent strategies over long horizons against strong adversaries, while prompt-centric agents repeatedly reinterpret evolving states.

    Source: §1 · p. 1

  • Method

    HexMachina first discovers an undocumented environment and induces an adapter, then evolves a player through code refinement and repeated evaluation while preserving executable artifacts.

    Source: §1 · p. 2, §4 · p. 4, §4.1 · p. 5

  • Results

    HexMachina is reported to outperform traditional LLM agents and common continual-learning architectures and to rival the AlphaBeta baseline in Catan.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Artifact-centric continual learning shifts the LLM from per-turn decision-making toward higher-level strategy design with consistent policy execution.

    Source: §6.1 · p. 7

    Evaluation relied on coarse win-rate and final-victory-point metrics, inference costs restricted trials, and performance remained tied to the underlying model’s quality.

    Source: §7 · p. 9

Abstract

from arXiv · show

We address the long-horizon gap in large language model (LLM) agents by enabling them to sustain coherent strategies in adversarial, stochastic environments. Settlers of Catan provides a challenging benchmark: success depends on balancing short- and long-term goals amid randomness, trading, expansion, and blocking. Prompt-centric LLM agents (e.g., ReAct, Reflexion) must re-interpret large, evolving game states each turn, quickly saturating context windows and losing strategic consistency. We propose HexMachina, a continual learning multi-agent system that separates environment discovery (inducing an adapter layer without documentation) from strategy improvement (evolving a compiled player through code refinement and simulation). This design preserves executable artifacts, allowing the LLM to focus on high-level strategy rather than per-turn reasoning. In controlled Catanatron experiments, HexMachina learns from scratch and evolves players that outperform the strongest human-crafted baseline (AlphaBeta), achieving a 54% win rate and surpassing prompt-driven and no-discovery baselines. Ablations confirm that isolating pure strategy learning improves performance. Overall, artifact-centric continual learning transforms LLMs from brittle stepwise deciders into stable strategy designers, advancing long-horizon autonomy.

1 INTRODUCTION

Long-horizon agents need to sustain competitive strategies without repeatedly re-parsing evolving states, but few benchmarks test persistent strategy refinement against strong adversaries. HexMachina separates environment discovery from strategy improvement and is reported to outperform traditional LLM agents, continual-learning architectures, and AlphaBeta in Catan.

1 INTRODUCTION

  • Prompt-centric agents repeatedly interpret evolving states, while preserving reusable artifacts can shift heavy context parsing to deterministic code and leave the model to focus on strategy.The paper identifies this as a way to support agents that need not relearn their interface at each inference step.Source: §1 · p. 1
  • Few benchmarks test whether agents can refine a coherent strategy over long horizons against strong adversaries.The paper argues this ability matters for assessing whether lifelong agents close the long-horizon gap.Source: §1 · p. 1
  • Catan tests long-horizon planning because success requires balancing short- and long-term rewards amid stochastic production, trading, expansion, and adversarial play.The benchmark also presents a large, changing state and action space with delayed rewards.Source: §1 · pp. 1–2
  • HexMachina evolves players that outperform traditional LLM agents and common continual-learning architectures, and rival the AlphaBeta baseline in Catan.The system lets the LLM design strategy while compiled code executes it consistently.Source: §1 · p. 2
  • HexMachina learns an undocumented environment, preserves useful code and knowledge as artifacts, and improves strategy through a closed-loop process that generates and executes code without human intervention.The framework separates environment-artifact discovery from strategy refinement.Source: §1 · p. 2

2 RELATED WORKS

Prior work explores LLM agents, self-improvement, and executable skills, but the paper identifies a gap in sustaining one competitive policy through long-horizon adversarial play. It asks whether an undocumented environment can be adapted to and its artifacts used to evolve such a policy.

Game-Playing AI and Strategy Games

  • Prior Catan work used a specialized neural network to handle mixed data types and outperform traditional rule-based bots, whereas this paper focuses on LLM-based discovery and strategy refinement without extensive training data.The broader game literature also includes progress in perfect-information games and challenges involving expanding action spaces, partial observability, and multi-agent interaction.Source: §2 · p. 3

LLM Agents and Long-Horizon Planning

  • Prompt-centric and dialogue-based agents still re-parse large states in long-horizon adversarial domains and lack a persistent executable substrate for enforcing strategy across an episode.The passage describes the planning gap as largely intact.Source: §2 · p. 3

Self-Improvement and Continual Learning Agents

  • Prior lifelong systems such as Voyager emphasize breadth—discovering many primitives—rather than depth in refining one competitive policy.Other work spans verbal reflection, evolutionary prompt search, code refinement, reward/program evolution, and automated code improvement.Source: §2 · p. 3

Positioning

  • The paper asks whether a lifelong LLM system can induce a compact adapter to an undocumented environment and preserve executable artifacts to evolve one competitive policy for adversarial play.It distinguishes this focus from prior work on skill discovery, reward/program evolution, and automated code improvement.Source: §2 · p. 3

3 BACKGROUND

Catan combines resource collection, trade, building, and tactical uncertainty in a race to ten victory points. The paper evaluates agents in Catanatron against its strong AlphaBeta baseline, using a depth-2 search for reported comparisons.

Settlers of Catan as a Strategic Benchmark

  • Catan is a 3–4 player game in which players collect and trade resources, build settlements and roads, and race to ten victory points.Dice-driven production and the robber introduce luck and tactical blocking, while players must plan expansions and trade strategically.Source: §3 · p. 4

The Catanatron Framework

  • Catanatron is an open-source Python simulator with a programmatic interface for custom agents and rapid simulation, and games typically last 40 to 100 turns.Its game states expose resources, board positions, available actions, and observable opponent statuses.Source: §3 · p. 4

Alpha-Beta Benchmark

  • The primary baseline is Catanatron’s AlphaBeta agent, a stochastic-outcome minimax using chance expansion and a heuristic value function, with depth fixed at 2 for reported comparisons.The baseline uses author defaults, including a 20 s decision cap, and is described as strong and fast enough for thousands of head-to-head evaluations.Source: §3 · p. 4

4 HEXMACHINA

HexMachina first induces a reusable interface to Catanatron, then improves a compiled player through iterative code changes and game evaluation. Its agents coordinate discovery, strategy refinement, and persistent knowledge across evolutions.

4 HEXMACHINA

  • HexMachina separates undocumented environment discovery, which produces executable adapter artifacts, from improvement, which evolves a Catanatron player through testable code.Each phase is limited to 20 Coder calls.Source: §4 · p. 4, §4.1 · p. 5

4.1 CAPABILITIES

  • The player evolves from a minimal legal-action template into an executable policy that can carry out a long-term plan across a game.The Coder turns strategy ideas into syntactically valid, testable code.Source: §4.1 · p. 4
  • A deterministic harness evaluates evolving players against AlphaBeta under fixed seeds and identical settings, logging outcomes, states, and decision traces.The fixed environment lets the system attribute changes in win rate or victory points to code evolution rather than stochastic noise.Source: §4.1 · p. 5

Analyst: Experimentation evaluator

  • Game outcomes are distilled into summaries so the Orchestrator can preserve, modify, or discard candidate players; Analyst-to-Coder-to-Orchestrator evaluation yielded clearer signals.Additional role recommendations often diluted strategy coherence.Source: §4.1 · p. 5, Figure 2 · p. 5

4.1 CAPABILITIES

  • The Orchestrator plans high-level work and delegates low-level tasks, while game and semantic memories retain prior players, evaluation artifacts, and role-specific expertise.Past strategies and technical knowledge can be compared, reused, and carried into later evolutions.Source: §4.1 · p. 5

4.2 AGENTS

  • Specialist agents standardize their inputs and outputs, but discovery uses the full team while direct strategy refinement uses the Orchestrator, Analyst, and Coder.Strategist and Researcher recommendations often diluted coherence during improvement.Source: §4.2 · p. 6

5 EXPERIMENT SETUP

Experiments use controlled two-player Catan games and compare HexMachina with baselines ranging from random play to AlphaBeta. The setup also tests a no-discovery learner and several orchestrator backends.

5 EXPERIMENT SETUP

  • Experiments use controlled two-player, 10-point Catan games, repeatedly pitting agents against AlphaBeta and measuring win rate and final victory points.Games are deterministic by seed, enabling reproducibility and separation of improvements from stochastic variance.Source: §5 · p. 6

5.1 BASELINES

  • Baselines include random play, a 20-game Reflexion-style LLM Player, a single-phase learner without discovery, and AlphaBeta, a depth-2 minimax bot.The LLM Player uses Claude 3.7 once per turn; the no-discovery learner attempts to learn interface and strategy simultaneously.Source: §5.1 · pp. 6–7

5.2 MODELS

  • Three orchestrator backends—GPT-5-mini, Claude 3.7, and Mistral-large—are tested; GPT-5-mini generally codes while Mistral-large supports other roles.The model assignments balance code-synthesis reliability against cost and latency.Source: §5.2 · p. 7

6 RESULTS AND DISCUSSION

HexMachina improves through continual evolution and, in player comparisons, slightly exceeds AlphaBeta on win rate and victory points. The results also show that discovery and role configuration matter to the system’s performance.

6.1 CONTINUAL LEARNING

  • Across 10 evolution steps, discovery-enabled players improved reliably, while systems without discovery struggled to stabilize executable player code.Each step evaluated FooPlayer across 30 games; HexMachina eventually reached parity with and surpassed baseline players.Source: §6.1 · p. 7, Figure 3 · p. 8
  • The example evolution dialogue shows HexMachina iteratively proposing, coding, and refining strategies while preserving functional artifacts.The paper characterizes the system as a strategy designer whose compiled policy executes consistently.Source: §6.1 · p. 7, Figure 4 · p. 8

6.2 PLAYER COMPARISON

  • GPT-5-mini reached a 54.1% win rate and 8.2 ± 0.1 victory points, versus AlphaBeta’s 51.0% win rate and 7.8 ± 0.2 points.The comparison stress-tested each configuration across 10 runs of 100 games.Source: §6.2 · p. 8, Table 2 · p. 9

6.3 ABLATIONS

  • Removing the Strategist and Researcher improved performance, while removing the Analyst heavily impaired success by weakening diagnosis of adapter-function misreferences.The ablation studies used three independent runs of 10 steps, each tested on 30 games.Source: §6.3 · p. 9, Table 3 · p. 9
  • The authors conclude that artifact preservation and documentation-free discovery support executable strategies, while leaner role configurations may avoid unnecessary handoffs.They identify these findings among the paper’s contribution statements.Source: §6.3 · p. 9

7 CONCLUSION

The authors identify limitations in evaluation, code generation, cost, and dependence on model quality. They propose broader benchmarks and longer evolution runs as future work.

7 CONCLUSION

  • Evaluation used only win rate and final victory points, which can mask subtler strengths and weaknesses; hallucinated code, inference costs, and backend quality also constrained performance.The authors suggest testing beyond Catan and extending the current 20-step evolution limit.Source: §7 · p. 9

8 ETHICAL STATEMENT

The ethical statement describes HexMachina as a code-evolving tool rather than a sentient entity and notes safeguards around code execution.

8 ETHICAL STATEMENT

  • Generated code runs only in a controlled evaluation harness that prevents arbitrary system access; the authors characterize the system as a code-evolving tool, not a sentient entity.Experiments were logged with fixed random seeds and configuration files.Source: §8 · p. 10

9 REPRODUCIBILITY STATEMENT

The authors state that code, experiment harnesses, and configuration files are released with instructions for reproducing the results.

9 REPRODUCIBILITY STATEMENT

  • Reproduction requires cloning the repository, installing dependencies, following the README, and supplying API keys for the tested LLMs.The authors state that experiments can then be run as described to replicate the tables and figures.Source: §9 · p. 10

A.1 HEXMACHINA’S BEST STRATEGY

This section describes the supplied strategies’ action-selection methods, including phase-aware scoring and filtering, heuristic priorities, and rollout- or sampling-based evaluation. It also covers tie-breaking, exploration, and fallback behavior used to select playable actions.

A.1 HEXMACHINA’S BEST STRATEGY

  • The player combines early/mid/late phase detection with expansion, city, development-card, robber, and knight heuristics, plus phase-biased short rollouts and critical-action guarantees.The listed features include settlement and road potential for early expansion, disruption and steals from robber/knight actions, and settlement, road, city, and development-card priorities that vary by phase.Source: §A.1 · p. 13
  • The implementation uses the adapters surface defensively, trying alternative attribute names and string-based heuristics when game-model details or helpers are unavailable.The code notes that attribute names vary across environments and invites traceback-based patching if an adapter function or attribute still raises an error.Source: §A.1 · p. 13
  • The strategy exposes tunable simulation, rollout, and phase-threshold constants, including 24 maximum simulations, rollout depth 2, and early/mid thresholds of 20/45 turns.The implementation also specifies a simulation budget of 60 and an early-game settlement target of three.Source: §A.1 · pp. 13–14
  • The heuristic scores victory points, pieces, resources, production, and city progress with phase multipliers and phase-dependent production weights.Its weighted terms include 100 per VP, 25 per settlement, 60 per city, 6 per road, and production weighted at 80 in the early phase or 45 in the mid phase.Source: §A.1 · pp. 19–20
  • When an adapter value function is available, state evaluation blends 85% of its value with 15% of the heuristic, falling back to the heuristic on error.Source: §A.1 · p. 20
  • Settlement potential rewards each new adjacent resource type by 12 points and adjacent expected dice production by 8 points per unit.Source: §A.1 · pp. 21–22
  • Road potential adds 6.0 when any digit in the action matches a player node; names containing “build_road” or both “road” and “build” add 2.0 as a fallback.Source: §A.1 · p. 22
  • The player buys a development card with at least one ore, wheat, and another resource, or in the early phase with at least three resources.A separate estimate uses the static development-card deck and EV constants to estimate VP-equivalent value, with scaling based on the opponent.Source: §A.1 · p. 23
  • City urgency rises in mid or late game when the player has at least two ore and one wheat, while early settlement urgency applies below the settlement target.The implementation assigns urgency bonuses of 40.0 for cities and 35.0 for settlements, plus a 10.0 road bonus.Source: §A.1 · pp. 25–26
  • The strategy scores actions with phase-specific multipliers and bonuses for settlements, cities, development cards, roads, and knights.Settlement scoring also incorporates settlement potential; road scoring incorporates connection potential, and knight scoring includes evaluation bonuses.Source: §A.1 · pp. 26–27
  • The prefilter returns a bounded candidate list while guaranteeing must-include actions and early-game settlement and road actions.This keeps those action types available for subsequent evaluation even when candidates are filtered.Source: §A.1 · p. 28
  • In the early phase, the prefilter forces settlement and road actions into the candidate set when available.It also includes robber or knight actions when present.Source: §A.1 · pp. 28–29
  • The prefilter includes a development-card buy when its evaluation passes and estimated expected value meets the threshold.The code applies this recommendation only when the conservative condition and EV threshold are met.Source: §A.1 · p. 28
  • Candidate selection combines required actions with the top-K cheap-scored actions, then randomly fills the pool up to the simulation cap.The code scores the remaining actions, deduplicates the combined list, and samples additional actions when needed.Source: §A.1 · p. 29
  • Robber evaluation favors the target hex with greatest opponent production loss, using expected stealing and bonuses for affected opponent cities.When an action does not specify a target hex, the evaluator considers all hexes.Source: §A.1 · pp. 30, 32
  • Knight evaluation starts from a base score and incorporates army progress and a largest-army threshold.The code sets the largest-army threshold to three knights.Source: §A.1 · p. 33
  • Rollouts simulate up to six top-ranked actions, follow the most probable branch, and recurse until depth zero or no actions remain.At the initial rollout step, scoring can bias toward early expansion; deterministic execution is attempted before spectrum execution.Source: §A.1 · pp. 35–36
  • When an opponent is next to move at depth two or greater, the rollout simulates one greedy opponent action, preferring non-robber actions when available.The opponent’s candidate action is selected using a cheap score from their perspective.Source: §A.1 · p. 36
  • Action expectations average branch values by probability, blending 60% immediate state evaluation with 40% rollout estimates.The method tries spectrum execution, falls back to deterministic execution, and uses a heuristic if branch evaluation fails.Source: §A.1 · pp. 37–38
  • The player samples playable actions, divides a simulation budget among candidates, and selects actions by their expected scores.When no action receives a finite score, it falls back to the first playable action.Source: §A.1 · p. 39
  • With epsilon-greedy randomness, it may choose a score-weighted action from the top three candidates; otherwise, it chooses the highest-scoring action.Unexpected errors also trigger a fallback to the first playable action.Source: §A.1 · p. 39
  • For tied top scores, it favors actions with settlement, road-connection, and resource-diversity improvements, then randomly selects among remaining ties.If tie-metric evaluation fails, the action receives a default metric.Source: §A.1 · p. 40

A.2 HEXMACHINA (NO DISCOVERY) SHALLOW STRATEGY

This no-discovery shallow-strategy player selects among candidate actions using one-ply evaluation of successor states. Its composite score centers on victory points, adds small bonuses for available settlements, cities, and roads, and uses best-effort extraction with unknown victory points defaulting to zero.

A.2 HEXMACHINA (NO DISCOVERY) SHALLOW STRATEGY

  • Because the adapter does not expose helpers for enumerating playable actions from hypothetical states, the player cannot reliably perform multi-step rollouts.The passage says relying on unsupported internal APIs would risk non-portable behavior.Source: §A.2 · p. 41
  • The player samples candidate actions, applies each to a copied game, evaluates the successor state, and chooses the highest-scoring action.When there are too many playable actions, it samples a subset to limit computation.Source: §A.2 · p. 41
  • Its static state evaluation prioritizes victory points, using settlement, city, and road counts as smaller tiebreakers.The evaluator tries multiple access patterns to extract game-state values defensively across engine versions.Source: §A.2 · p. 44
  • If extraction fails, the code may count settlement lists but avoids brittle board-based victory-point estimates and falls back to zero when victory points remain unknown.Fallback extraction is described as optional and best-effort.Source: §A.2 · pp. 45–46
  • Victory points form the main score, with bonuses of 0.01 per settlement, 0.02 per city, and an additional road bonus when counts are available.The code adds the settlement and city bonuses explicitly; it says roads receive a small weighted bonus but the supplied excerpt does not show its weight.Source: §A.2 · p. 46
Loading 2506.04651v2…