TL;DR
This paper introduces a novel filtering method for logic programs that allows AI agents to reason effectively in general games with imperfect information. By adapting backward-chaining and abduction techniques, the authors enable a "legal player" to always know its valid moves, even when the game state is partially hidden, demonstrating significant efficiency and effectiveness across various GGP competitions.
What Problem Does This Paper Address?
General Game Playing (GGP) aims to create AI agents that can play any game given its rules. While early GGP focused on games where players know the complete game state (perfect information), recent extensions to the Game Description Language (GDL) allow for games with imperfect and asymmetric information. This introduces a significant challenge: how can an agent determine its legal moves when it doesn't know the full state of the game? Traditional methods, like standard backward-chaining, fail because they assume complete knowledge. Existing imperfect information GGP systems often resort to logically unsound methods like sampling states. This paper tackles the problem of building a logically sound and efficient reasoning system for GGP with imperfect information by focusing on a core sub-problem: filtering incomplete knowledge based on observations.
Methods
The core contribution is a filtering method for logic programs. This method is designed to update an agent's incomplete knowledge of a logic program (representing game rules and state) when new observations become available.
Here's a breakdown of the key techniques:
- Open Logic Programs: The authors adapt concepts from "open logic programs" (Bonatti 2001a, 2001b). These programs involve a base logic program
Pand two sets of ground atoms:B+(known to be true) andB°(potentially true). This(P, B+, B°)structure provides a compact way to represent incomplete knowledge. - Skeptical and Credulous Inference: Reasoning with open logic programs involves two modes: skeptical inference (conclusions true in all possible extensions of the incomplete knowledge) and credulous inference (conclusions true in some possible extension).
- Backward-Chaining with Support Computation: The filtering method is built upon a backward-chaining inference procedure. Crucially, this procedure computes "supports" for derived facts. A support is essentially a query that, if satisfied, justifies the derivation. This is key for filtering.
- Filtering Algorithm: The filtering process takes the current incomplete knowledge
(B+, B°)and a set of observationsO. It computes new setsBrewandBnewby analyzing the supports for observed facts (and their negations). If a literal is present in all supports for an observation (or its negation), it's used to strengthen the knowledge: literals consistently true are moved toBrew, and those consistently false are removed fromBnew. - Basic Legal Player for GDL-II: This filtering method is then applied to construct a basic legal player for GDL-II. The player maintains its knowledge of the game state using
(B+, B°)pairs. In each round, it determines its own legal moves skeptically and the opponents' possible legal moves credulously. It then updates its knowledge based on its own move and its percepts, using the filtering method to refine its belief about the next state.
Datasets
Not discussed in the paper. The paper evaluates its method on existing games from past AAAI General Game Playing competitions.
Key Insights and Ideas
- Filtering as a Core Reasoning Primitive: The paper frames "filtering" – updating beliefs based on observations in the presence of incomplete knowledge – as a fundamental reasoning problem for agents in uncertain environments.
- Bridging Logic Programming and Imperfect Information: By adapting techniques from open logic programs and backward-chaining, the authors provide a principled, logically sound way to handle uncertainty in GDL-II, moving beyond ad-hoc sampling methods.
- The Power of Supports: The concept of "supports" in backward-chaining is crucial. It allows the system to understand why a conclusion is reached and to use this justification to refine knowledge when observations are made or not made.
- Skeptical vs. Credulous for Different Tasks: The paper elegantly uses skeptical inference to determine the player's own legal moves (ensuring correctness) and credulous inference for determining opponents' possible moves (exploring possibilities).
- Implications for Game Design: The experimental results suggest that for basic backward-chaining players to be effective, game descriptions need to provide sufficient percepts for players to determine termination and goal values. This highlights a potential design principle for future GGP competitions.
Key Results
- Always Knows Legal Moves (Mostly): The basic legal player successfully determines its legal moves in almost all tested games. Exceptions were noted in Krieg-Tictactoe and Blackjack due to specific rules requiring disjunctive reasoning or incomplete information about opponent actions.
- Efficient Performance: The backward-chaining filtering method proved to be efficient, with average times per round being very low (e.g., 0.21s for Monty Hall, 4.08s for Hidden Connect).
- Challenges with Termination/Goal: In several games, the player struggled to determine game termination or its own goal value, indicating that the game rules themselves might not provide enough information through percepts.
- Vis_Pacman Anomaly: A notable exception in performance was the 3-player vis_Pacman game, where the reasoner slowed down significantly. A simplified filtering approach (only considering actual observations) improved performance for this specific case.
Limitations and Future Work
- Incompleteness of Filtering: The paper acknowledges that the compact representation of incomplete knowledge (
B+,B°) and the filtering method itself are inherently incomplete. This means the player might not always derive all possible conclusions. - Disjunctive Reasoning: The current method struggles with situations requiring disjunctive reasoning (e.g., "either A or B is true, but I don't know which").
- Future Work: The authors suggest that the filtering method could be extended to more complex reasoning tasks beyond just determining legal moves. They also imply that further research into more expressive representations of incomplete knowledge might be beneficial. The experimental results also point towards the need for game designers to ensure sufficient percepts for basic players to determine game outcomes.
Summary updated