Automatic Heuristic Construction for General Game Playing

Gregory Kuhlmann, Peter Stone

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

Abstract

Introduction Creating programs that can play games such as chess, checkers, and backgammon, at a high level has long been a challenge and benchmark for AI. While several game-playing systems developed in the past, such as Deep Blue (Campbell, Jr., & Hsu 2002), Chinook (Schaeffer et al. 1992), and TD-gammon (Tesauro 1994) have demonstrated competitive play against human players, such systems are limited in that they play only one particular game and they must be supplied with large amounts of expert knowledge. While their performance is impressive, it could be argued that the demonstrated intelligence is that of the system’s designers more so than that of the system itself. General Game Playing is the more challenging problem of designing an agent capable of playing many different previously unseen games (Pell 1993). The first AAAI General Game Playing Competition was held at 2005 AAAI meeting in Pittsburgh in order to promote research in this area (Genesereth & Love 2005). We were one of nine participants in that competition. We survey some of the issues involved in creating a general game playing system and introduce our entry to that event. The main feature of our approach is a novel method for automatically constructing effective search heuristics based on the formal game description. Our agent is fully implemented and tested in a range of different games.
BibTeX
@inproceedings{kuhlmann2006automatic,
  author = {Gregory Kuhlmann and Peter Stone},
  title = {{Automatic Heuristic Construction for General Game Playing}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
}

Loading related content...

Figure