Skip to content

SAGA: Scene-Aware, Goal-Evolving Agents for Long-Horizon CivRealm Strategy Planning

🕒 Published (v1): 2026-06-29 08:07 UTC · Source: Arxiv · link

Why this paper was selected

Long-horizon multi-domain agent with scene-aware goal evolution; strong harness design patterns

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

SAGA is a three-mechanism LLM multi-agent framework for long-horizon strategy game planning (FreeCiv/CivRealm) that directly targets scene blindness, context overflow/domain coupling, and shallow cross-game learning. It achieves the highest mean civilization score among six baselines while cutting output tokens by 27%, and its cross-game evolution module functions as an architecture-agnostic plug-in that lifts all capable baselines. Ablations confirm each component contributes independently, with on-demand tooling being the most critical (−49% score when removed).

Problem

LLM agents in multi-domain strategy games exhibit five concrete failure modes grouped into three classes: (i) spatial blindness — raw grid coordinates carry no relational semantics; (ii) context overflow — monolithic state dumps exceed 15k tokens per step and grow unboundedly, while monolithic outputs cause domain coupling (high-priority military concerns crowd out infrastructure); and (iii) shallow cross-game learning — prior methods retrieve and replay past episodes without structured causal attribution, offering heuristic replay rather than principled strategic evolution. Mechanical constraint violations additionally produce silent failures invisible to the planner.

Method

SAGA composes three tightly integrated mechanisms over a POMDP formulation \(\mathcal{M} = \langle S, O, A, T, R, \gamma \rangle\) with factored action space \(A = A_{\text{tech}} \times A_{\text{gov}} \times A_{\text{dipl}} \times A_{\text{city}} \times A_{\text{civilian}} \times A_{\text{military}}\).

Map-Semantic Scene Graph \(G=(V,E)\) is rebuilt each turn. Nodes \(V\) are friendly and enemy entities; edges encode typed spatial relations (friendly-to-friendly for coordination, friendly-to-enemy for offense/defense) annotated with Manhattan distance discretized into three levels and eight-way cardinal direction. SceneGraph.invoke(entity_id) renders each entity's local neighbourhood as natural language delivered only to its own controller, achieving spatial grounding without global token inflation.

Tool-Augmented Planner is a ReActAgent operating in a pull-based information model: it starts each turn with a lean strategic digest and fetches fine-grained domain state on demand via three tools (query_city_metrics, query_army_roster, query_tech_status). Its structured PlannerResponse partitions directives into six non-overlapping controller-aligned streams (city, civilian, military, tech, gov, diplomacy), dispatched concurrently via ThreadPoolExecutor (up to 20 workers) to dedicated specialist ReActAgent controllers. City and Tech controllers enforce action-mask validation to prevent hallucinated illegal orders; Diplomacy executes under a mutex one turn after planning to prevent concurrent state conflicts.

Dual-Horizon Feedback Loop operates at two timescales. Inner loop (within-game): every \(K=6\) turns, AbstractAgent compresses SQLite action logs into a structured semantic summary; SetGoalAgent generates time-bounded, domain-specific directives grounded in both within-game progress and accumulated cross-game knowledge, serving as credit-assignment proxies under sparse reward. Emergency replanning triggers immediately on detecting new hostile units near friendly cities or a city capture, overriding the periodic schedule. Outer loop (cross-game): at game end, GameAnalyst performs structured post-mortem over diplomatic traces, production histories, and score trajectories, encoding root-cause findings into a JSON report. PreGameStrategist reads this alongside strategic_evolution_chain.md and injects top-ranked principles into the next game's Planner system prompt, realising a transferable strategic prior without manual reward engineering.

Key Contributions

  • SAGA multi-agent framework resolving all five identified failure modes in long-horizon multi-domain LLM planning.
  • Map-Semantic Scene Graph: per-entity relational spatial context without global token inflation.
  • Tool-Augmented Strategic Pipeline: pull-based, apples-to-apples isolation of planner-level architecture from controller infrastructure, enabling the first fair planner-level comparison on CivRealm.
  • Dual-Horizon Feedback Loop: architecture-agnostic, plug-and-play cross-game evolution module validated as a standalone enhancement across all capable baselines.
  • Comprehensive ablation confirming independent contribution of each component.

Results

  • Overall score: SAGA 60.7 ± 14.0 vs. CoS 47.8 ± 20.3, HIMA 43.7 ± 22.3, Optimus-2 41.5 ± 10.1, Mastaba 39.0 ± 14.2, EpicStar 35.4 ± 21.5 (all n=10, 150-turn games on Map Seed 2025).
  • Infrastructure (Buildings): SAGA 16.3 ± 10.5 vs. ≤7.5 for every baseline; only metric significantly beating all five baselines (Mann–Whitney \(p < 0.05\), Holm-corrected; head-to-head win-rate 78–98%).
  • Score significance: lead significant over three of five baselines; within noise against CoS (\(p=0.06\)) and HIMA (\(p=0.10\)) due to heavy-tailed distribution, but SAGA wins ≥72% of head-to-head games against both.
  • Token efficiency: output tokens 109k ± 14k vs. CoS 149k (−27%), HIMA 219k (−50%); input tokens higher (258k ± 54k) due to SetGoalAgent/AbstractAgent context.
  • Cross-game evolution (5 episodes): SAGA 57 → 90; HIMA 31 → 81; CoS 35 → 80; Mastaba 56 → 74; Optimus-2 34 → 59; EpicStar 23 → 17 (TF-IDF retrieval fails in high-dimensional state).
  • Ablations: removing SceneGraph or inner-loop cycle each reduce score by ~25%; removing on-demand tools reduces score by 49%.
  • Cross-seed generalization: radar polygon area grows Game 1→5 on all four seeds (2025–2028), confirming transfer of accumulated strategic priors.

Limitations

  • Score advantage over the two strongest baselines (CoS, HIMA) is statistically within noise at the 5% level due to CivRealm's heavy-tailed score distribution; claims rest on head-to-head win-rates rather than mean comparison.
  • Evaluation confined to a single game engine (FreeCiv 2.6 via CivRealm gym); generalizability to other complex strategy games is undemonstrated.
  • Fixed global map seed (GLOBAL_SEED=2025) for base experiments; cross-seed experiments use only four seeds and are single-run per seed rather than \(n=10\).
  • Cross-game evolution module amplifies capable backbones but cannot compensate for poor retrieval or weak base execution (EpicStar degrades); the module's value is backbone-dependent.
  • Higher input token cost (258k ± 54k) than several baselines — a latency and cost overhead for the SetGoalAgent/AbstractAgent context pipeline.

Relevance to Harnesses / Meta-Harnesses

SAGA is a direct embodiment of the harness/meta-harness pattern at two levels: the Tool-Augmented Strategic Pipeline is an orchestration harness that coordinates six specialist ReActAgent controllers through structured dispatch and action-mask validation, while the Dual-Horizon Feedback Loop is a meta-harness that wraps individual episode execution with causal post-mortem and injects distilled strategic priors into subsequent episodes' system prompts. The cross-game evolution module's demonstrated plug-and-play compatibility — lifting nearly all baselines when grafted onto their architectures — validates the meta-harness concept that an outer control loop can decouple strategic learning from inner execution mechanics. For researchers tracking harnesses, SAGA provides a concrete architecture showing how SQLite logging substrates, structured post-mortem agents, and evolving prompt injection can compose into a principled meta-harness without any gradient-based reward engineering.