Introduction
General Game Playing (GGP) represents a significant frontier in artificial intelligence, moving beyond "narrow" systems designed for specific tasks toward agents capable of mastering any game given only its formal rules. Unlike specialized engines like Deep Blue, which rely on hard-coded expert knowledge, a GGP agent must interpret a game's logic—typically expressed in Game Description Language (GDL)—and develop effective strategies on the fly. This paper presents a methodology for the automatic construction of search heuristics, enabling agents to evaluate game states without human intervention or prior domain knowledge.
The Problem: Beyond Hard-Coded Expertise
Traditional game-playing AI is limited by its specificity. A system optimized for Chess cannot play Tic-Tac-Toe because its evaluation functions and search parameters are inextricably linked to the semantics of Chess. In GGP, agents are provided with GDL descriptions just minutes before a match begins. These descriptions often use scrambled variable names to prevent agents from using lexical clues. The core challenge is to derive a meaningful evaluation function (a heuristic) from abstract logical relations.
Methodology: From Logic to Strategy
The authors propose a multi-stage pipeline to transform formal rules into actionable heuristics:
1. Syntactic Pattern Matching
The agent first analyzes the GDL for structural patterns that suggest common game components. For instance, it looks for ternary relations—logical structures with three arguments—that might represent a 2D board (e.g., (cell ?x ?y ?state)). Because the agent ignores variable names, it identifies these structures based on their logical "shape" and how they interact with other rules.
2. Verification via Internal Simulation
Static analysis alone can be ambiguous. To confirm that a discovered structure functions as intended, the agent performs "mini-simulations" during the pre-game startup phase. It tests for invariants; for example, if a structure is a game board, a specific cell should typically contain only one piece at a time. If these invariants hold across numerous random simulations, the agent confirms the structural identification.
3. Heuristic Generation
Once structures like boards, pieces, and counters are identified, the agent generates a suite of candidate heuristics. These include:
- Piece Counting: Maximizing or minimizing the quantity of specific markers.
- Manhattan Distance: Calculating spatial relationships between pieces on an identified grid.
- Mobility: Measuring the number of available moves in a given state.
4. Distributed Search and Evaluation
To manage the computational complexity of evaluating these heuristics, the agent employs a master-slave architecture. It uses iterative deepening minimax search with alpha-beta pruning, distributing the evaluation of different candidate heuristics across multiple remote processes to find the most effective strategy within the time constraints.
Experimental Results and Insights
The system was evaluated during the inaugural 2005 AAAI General Game Playing Competition, facing a variety of games including Chess, Checkers, and abstract puzzles.
Structure over Semantics
A key insight is that semantic understanding is unnecessary for high-level play. By recognizing that certain objects move across a grid and that their removal correlates with lower utility, the agent can play Chess effectively without knowing what a "Pawn" or "Rook" is.
The "Nothello" Case Study
The agent's adaptability was most evident in "Nothello," a variant of Othello where the objective is to have the fewest pieces. While human-designed agents often struggled with the counterintuitive goal, this system’s automated generation of both maximizing and minimizing heuristics allowed it to correctly identify and prioritize the "fewest pieces" strategy, leading to superior performance.
Limitations and Future Directions
While successful, the current approach relies on linear combinations of single features. Future work could explore non-linear evaluation functions and more complex feature interactions. Additionally, the reliance on GDL-specific pattern matching could be broadened through more generalized theorem-proving techniques. Finally, improving the speed of the underlying logic interpreter would allow for deeper search trees, further enhancing the utility of the generated heuristics.
Summary updated