A Temporal Proof System for General Game Playing

Michael Thielscher, Sebastian VoigtAAAI 2010 · DOI

Abstract

General Game Playing (GGP) requires agents to understand and play games based solely on their formal descriptions. Traditionally, agents have relied on statistical sampling to infer game properties, which lacks formal rigor. This paper presents a novel temporal proof system that combines Temporal Logic with Answer Set Programming (ASP) to formally verify game invariants. By employing an inductive proof strategy, the system can efficiently prove local properties such as turn-taking and state persistence across all reachable states, providing a solid foundation for search heuristics.

Introduction

In General Game Playing, an agent receives the rules of an unknown game in Game Description Language (GDL) and must play effectively without human intervention. A critical component of high-level play is the identification of game-specific knowledge—invariants that hold true throughout the game. For instance, knowing that a piece once placed in Tic-Tac-Toe never moves is vital for pruning search trees.

Historically, GGP systems have used random simulations to "guess" these properties. However, such empirical observations are not proofs; a property might hold for thousands of simulations but fail in a rare, reachable state. This paper addresses the challenge of formally proving "local" properties—invariants concerning successive states—without exhaustive state-space traversal.

Methodology

The proposed system bridges the gap between formal logic and practical game analysis through two primary components:

1. Formal Language Extension

The authors extend GDL by incorporating temporal operators, specifically the "next" operator ($\bigcirc$) from Linear Temporal Logic (LTL). This allows for the formalization of properties that span multiple states. The core predicates of GDL, which form the basis for this extension, are summarized in Figure 1.

Table 1: Core predicates of the Game Description Language (GDL) used as the foundation for the temporal proof system.

2. ASP-Based Proof Theory

The system utilizes Answer Set Programming (ASP), a declarative logic programming paradigm, to perform inductive proofs. The verification process follows a standard mathematical induction schema:

  • Base Case: The ASP solver verifies if the property holds in the initial state ($S_0$).
  • Inductive Step: The solver assumes the property holds in an arbitrary state $S$ and checks if it must hold in all possible successor states $S'$.

A successful proof is achieved if the ASP solver (specifically Clasp) finds the program to be "inconsistent" when searching for counter-examples. If no counter-model exists, the property is an invariant for all reachable states.

Experimental Evaluation and Results

The system was evaluated on a suite of standard GGP benchmarks, including Tic-Tac-Toe variants, Connect4, and Othello. The researchers focused on proving three categories of properties: Turn Taking (only one player moves at a time), Persistence (features remaining unchanged), and Control (predicting which player has the move after $n$ steps).

Table 2: Experimental results showing proof status and computation time (in seconds) for various game properties across different benchmarks.

As shown in Figure 2, the system demonstrates remarkable efficiency. Most properties for games like Tic-Tac-Toe and Connect4 were proven in under 0.2 seconds. Even for more complex scenarios like "Endgame," proofs were completed within 15 seconds. This performance makes the system highly practical for the "start clock" phase of GGP competitions, where agents have limited time to analyze rules before play begins.

Discussion and Conclusion

The distinction between "local" and "global" properties is central to this work. While global properties (e.g., "Player 1 has a winning strategy") are often computationally intractable, local invariants are both provable and highly beneficial for building search heuristics.

One limitation of the current approach is that it requires candidate properties to be provided; it does not autonomously discover them. Future work aims to integrate automatic property generation to create a fully autonomous knowledge discovery engine. Nonetheless, this system represents the first formal and practical framework for verifying temporally extended properties in GGP, moving the field from heuristic guessing to rigorous proof.

Summary updated

BibTeX
@inproceedings{thielscher2010temporal,
  author = {Michael Thielscher and Sebastian Voigt},
  title = {{A Temporal Proof System for General Game Playing}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2010},
  doi = {10.1609/aaai.v24i1.7646},
}
Figure