Introduction
In General Game Playing (GGP), agents are tasked with playing games based solely on their formal rules. While the General Game Description Language (GDL) effectively handles perfect-information games, its extension for hidden information, GDL-II, remains purely descriptive. It lacks a native mechanism for agents to reason about their own knowledge or the knowledge of opponents. Previous attempts to bridge this gap by embedding GDL into powerful logics like Alternating-time Temporal Epistemic Logic (ATEL) resulted in model-checking complexities that are 2EXPTIME-hard, making them computationally impractical.
This paper introduces Epistemic General Game Description Language (EGDL), a logic designed to balance expressivity with computational efficiency. By focusing on imperfect recall semantics and a streamlined set of operators, the authors achieve a model-checking complexity of $\Delta^P_2$, a significant improvement over existing high-level logical frameworks.
Methodology and EGDL
EGDL extends standard GDL with two primary epistemic operators: $K_i \phi$ (agent $i$ knows $\phi$) and $C \phi$ (common knowledge of $\phi$). The logic is built upon Epistemic State Transition (ET) models, where game states are connected by transitions and equivalence relations representing indistinguishability. If two states look identical to a player based on their current observations, they are considered part of the same equivalence class.
A critical design choice in EGDL is the assumption of imperfect recall. Unlike agents with perfect recall who remember the entire history of the game, EGDL agents are "memoryless," basing their knowledge only on the current state and their current observations. This simplification significantly reduces the state space and is a primary driver of the logic's efficiency.
Efficient Model Checking via Operator Elimination
The core of EGDL’s tractability lies in the elimeop algorithm. This procedure eliminates epistemic operators from formulas in a bottom-up fashion, effectively reducing complex epistemic queries into simpler sub-problems.
By iteratively replacing epistemic sub-formulas with new atomic propositions that represent the truth of those formulas across indistinguishable states, the algorithm transforms the model-checking task into a sequence of simpler checks. This recursive elimination allows the framework to handle complex knowledge queries while remaining within the $\Delta^P_2$ complexity class.
Case Study: Krieg-Tictactoe
To demonstrate the practical utility of EGDL, the authors apply it to Krieg-Tictactoe. In this variant of Tic-Tac-Toe, players cannot see their opponent's marks unless they attempt to play in a square that is already occupied. This creates a state space where multiple board configurations may be indistinguishable to a player.
EGDL allows for the formalization of complex epistemic properties in this environment, such as "uniformity"—the requirement that if a move is legal, the player must know it is legal: $legal(a^i) \to K_i(legal(a^i))$.
Complexity and Results
The primary contribution of this work is the proof that model checking for EGDL is $\Delta^P_2$-complete. This places the problem in the second level of the polynomial hierarchy, which is considered manageable compared to the exponential complexity of competing frameworks. The logic is shown to be a sound and conservative extension of standard Epistemic Modal Logic ($S5C_n$), ensuring that it maintains standard reasoning properties while adding temporal dimensions necessary for game playing.
Limitations and Future Work
While the memoryless assumption enables efficiency, it limits the logic's applicability to games where history is vital, such as Poker or Bridge. Furthermore, the absence of an "until" operator restricts reasoning about long-term future goals (e.g., "I know that eventually, I will win"). Future research will focus on incorporating varied levels of agent memory and investigating the satisfiability problem for EGDL.
Summary updated