Automatic Heuristic Construction in a Complete General Game Player

Gregory Kuhlmann, Peter Stone

Introduction

In the field of Artificial Intelligence, most game-playing systems are highly specialized. While programs like Deep Blue or AlphaZero achieve superhuman performance in specific domains like chess or Go, they lack the flexibility to play a game they haven't been explicitly programmed for. General Game Playing (GGP) addresses this limitation by requiring agents to play any game described in a formal Game Description Language (GDL). Because the rules are unknown until the start of the match, developers cannot hard-code heuristic evaluation functions—the mathematical formulas that guide search by estimating the "goodness" of a board state. This paper presents a fully autonomous GGP agent that solves this problem by automatically deriving search heuristics directly from the logical structure of game rules.

Automated Structure Identification and Verification

The core challenge in GGP is transforming raw logical rules into meaningful numerical features. The authors' agent employs a multi-stage pipeline to achieve this. First, it performs Syntactic Structure Identification, scanning GDL rules for patterns that indicate common game elements. It searches for "successor relations" to identify ordered sequences (like numbers or coordinates), "counters" for tracking game progress, and "boards" representing two-dimensional grids. Importantly, this process is name-invariant; the agent identifies a "board" based on its logical topology even if the rule-writer uses obfuscated terms.

To ensure these identified structures are valid, the agent uses Internal Simulation. Formally proving invariants in GDL is computationally prohibitive. Instead, the agent runs dozens of "mental" simulations of random games. If a hypothesized "piece" is observed to occupy two different "cells" simultaneously during simulation, the hypothesis is rejected. This empirical approach provides a high degree of confidence sufficient for heuristic generation without the overhead of formal proof.

Feature Extraction and Heuristic Generation

Once structures are verified, the agent maps them to a library of candidate features. For instance, if a two-dimensional board is identified, the agent can calculate the spatial coordinates of markers or the Manhattan distance between specific pieces.

Mapping identified game structures to automatically generated numerical features.

As shown in the table above, the agent generates a variety of features based on the identified structure. These features are then used to construct candidate heuristics by either maximizing or minimizing their values. For example, in a racing game, a heuristic might be generated to maximize the X-coordinate of a player's piece, encouraging forward movement toward a goal.

Distributed Search and the Paranoid Algorithm

During gameplay, the agent operates within a "Master-Slave" architecture to manage the uncertainty of which heuristic is most effective. The master process distributes different candidate heuristics to a cluster of slave processes. Each slave performs an alpha-beta search using its assigned heuristic and reports its recommended move back to the master. The master then selects the move from the search that reached the greatest depth or showed the most promise.

For multi-player environments, the agent utilizes the paranoid algorithm. This approach assumes that all other players have formed a coalition to minimize the agent's score. While pessimistic, this assumption allows the agent to apply efficient alpha-beta pruning techniques in non-zero-sum games, providing a robust defense against adversarial play.

Experimental Evaluation

The agent was evaluated against a baseline version of itself that utilized only exhaustive search without heuristics. The testing suite included games from the 2005 AAAI GGP Competition, such as Nothello (an Othello variant where the goal is to have the fewest markers), Hallway (a pawn-racing game), and Farmers (an economic simulation).

Win rates and statistical significance for the agent against a non-heuristic baseline.

The results, summarized in the table above, demonstrate the effectiveness of automated heuristic construction. In Nothello and Hallway, the agent achieved a perfect 100% win rate. In Nothello, the system correctly identified that minimizing its own markers was the winning strategy. In Hallway, it successfully prioritized moving its piece toward the goal. While the results in Farmers were less statistically significant, the agent still outperformed random expectations, suggesting that even complex economic games can benefit from these structural templates, though they may require more sophisticated feature sets.

Conclusion and Future Work

This research demonstrates that it is possible for an AI to "understand" the underlying structure of a game through logical analysis and simulation. By identifying abstract templates like boards and counters, the agent can play a wide variety of games without human intervention. Future work aims to reduce the dependency on pre-defined templates and improve the selection process for heuristics during the distributed search phase. Additionally, modeling opponent behavior rather than assuming pure adversarial "paranoia" could further refine the agent's strategic capabilities.

Summary updated

Abstract

Computer game players are typically designed to play a single game: today's best chess-playing programs cannot play checkers, or even tic-tac-toe. General Game Playing is the problem of designing an agent capable of playing many different previously unseen games. The first AAAI General Game Playing Competition was held at AAAI 2005 in order to promote research in this area. In this article, 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 in a Complete General Game Player}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
}
Figure