SAG-Agent: Enabling Long-Horizon Reasoning in Strategy Games via Dynamic Knowledge Graphs
Summary: arXiv:2510.15259v3 Announce Type: replace
Abstract: Most commodity software lacks accessible Application Programming Interfaces (APIs), requiring autonomous agents to interact solely through pixel-based Graphical User Interfaces (GUIs). In this API-free setting, large language model (LLM)-based agents face severe efficiency bottlenecks: limited to local visual experiences, they make myopic decisions and rely on inefficient trial-and-error, hindering both skill acquisition and long-horizon planning.
To overcome these limitations, we propose SAG-Agent, an experience-driven learning framework that structures an agent’s raw pixel-level interactions into a persistent State-Action Graph (SAG). SAG-Agent mitigates inefficient exploration by topologically linking functionally similar but visually distinct GUI states, constructing a rich neighborhood of experience that enables the agent to generalize from a diverse set of historical strategies.
Key Features of SAG-Agent
- Persistent State-Action Graph (SAG): The core of the SAG-Agent framework is the persistent State-Action Graph that organizes the agent’s interactions, allowing for better decision-making and planning.
- Improved Exploration Efficiency: By linking visually distinct states that serve similar functions, SAG-Agent enhances the agent’s ability to explore more efficiently, reducing reliance on trial-and-error methods.
- Hybrid Intrinsic Reward Mechanism: This innovative reward system combines state-value rewards for known high-value pathways with novelty rewards, promoting both exploitation and exploration.
Long-Horizon Reasoning
The design of SAG-Agent allows for effective long-horizon reasoning. By decoupling strategic planning from pure discovery, the agent can evaluate actions that may not yield immediate rewards but are essential for long-term success. This approach drastically changes the way agents interact with complex environments, enabling them to plan several steps ahead.
Evaluation and Results
We evaluated SAG-Agent in two complex, open-ended GUI-based decision-making environments: Civilization V and Slay the Spire. The results demonstrated significant improvements in exploration efficiency and strategic depth compared to state-of-the-art methods.
- Civilization V: In this strategic simulation game, SAG-Agent was able to navigate complex diplomatic and economic systems with greater success than previous models.
- Slay the Spire: The agent showcased improved decision-making capabilities, allowing it to create more effective strategies to overcome challenging opponents.
Conclusion
SAG-Agent represents a significant advancement in the field of autonomous agents within strategy games. By leveraging a structured approach to experience and reward, it opens up new possibilities for long-horizon reasoning and strategic planning in environments where traditional API-based interactions are not feasible. The implications of this research extend beyond gaming, suggesting potential applications in various domains requiring complex decision-making under uncertainty.