Abstract
General Game Playing (GGP) aims to develop agents capable of playing unseen games based solely on their rules. While the original Game Description Language (GDL) successfully modeled deterministic games of perfect information, it lacked the capacity for randomness and hidden information. This paper introduces GDL-II, a minimalist extension that incorporates a random player and a sees predicate. These additions enable the formal description of imperfect information games, providing a rigorous framework for agents to reason about uncertainty and epistemic states.
Introduction
In the field of General Game Playing, the objective is to create artificial intelligence that can be handed the rules of a brand-new game and begin playing effectively without human intervention. Historically, this endeavor was constrained by the limitations of the Game Description Language (GDL), which could only describe deterministic games with "perfect information"—scenarios where all players have complete knowledge of the game state, such as Chess or Go.
However, many significant challenges in AI and real-world decision-making involve uncertainty. Games like Poker (hidden cards), Backgammon (dice rolls), or scenarios like automated trading (private valuations) require reasoning about what is unknown. The original GDL lacked the vocabulary to express concepts like hidden moves or stochastic events. This paper bridges that gap by introducing GDL-II (Game Description Language with Incomplete Information), moving GGP into the realm of imperfect information games.
The GDL-II Language Extension
GDL-II maintains the logic-programming foundation of the original GDL but introduces two critical components to handle uncertainty and randomness. By adding just two new keywords, the language expands its reach to include any finite game with perfect or imperfect information.
- The
randomPlayer: A special, built-in role that acts as "Nature." The game rules define legal moves forrandom(e.g., rolling a die or dealing a card), and the game controller selects one of these moves with uniform probability. Non-uniform probabilities can be modeled by providing multiple legal moves that lead to the same outcome. - The
seesPredicate: In standard GDL, all players are automatically informed of every move. In GDL-II, players only receive information explicitly defined bysees(Role, Percept). If a move or state change is not wrapped in aseesclause, it remains hidden from that player.
Formal Semantics and Epistemic Reasoning
The paper provides a rigorous mathematical semantics for GDL-II, defining how a game state evolves and how a player’s "perceptual history" allows them to distinguish between different possible game states. A core concept is indistinguishability: two sequences of states and moves (developments) are indistinguishable to a player if they have made the same moves and received the same percepts in both scenarios.
Because the rules are public, players can engage in implicit epistemic reasoning. An agent can calculate not only what it knows but also what its opponents likely know based on the moves made and the percepts distributed. This allows for the modeling of complex strategies involving bluffing and information gathering.
Illustrative Game Domains
To demonstrate the expressive power of GDL-II, the paper provides formal axiomatizations for several classic game types that were previously impossible to represent in GGP:
- Kriegspiel: A "blind" version of chess where players only see their own pieces and receive limited feedback (e.g., being told a move is illegal or a capture has occurred).
- Card Games: Demonstrating dealing, hidden hands, and asymmetric knowledge through betting rounds.
- Coloured Trails: A benchmark for decision-making and negotiation under uncertainty.
Conclusion and Future Directions
GDL-II is a true superset of GDL; any game written in the original language can be represented in GDL-II without loss of information. While the language successfully maps high-level logic rules to a formal state-transition model, it introduces significant computational challenges. Reasoning about "information sets" (groups of states that appear identical to a player) is more complex than searching a standard game tree.
Future work involves adapting search algorithms like Monte Carlo Tree Search (MCTS) to handle these information sets and exploring more direct ways to specify non-uniform transition probabilities. Despite these challenges, GDL-II provides the necessary formal foundation for the next generation of general game-playing agents.
Summary updated