Applying General Induction Methods to the Card Game Eleusis

Thomas G. DietterichAAAI 1980

Abstract

This paper explores a methodology for bridging the gap between weak, general-purpose induction algorithms and highly specialized, domain-specific ones. Using the card game Eleusis as a testbed, the author introduces a multi-layered "knowledge-ring" architecture and a model-fitting approach. This system demonstrates that general induction methods can successfully discover complex, disjunctive rules—a task previously thought to require bespoke logic. By transforming raw data through successive layers of abstraction, the program achieves human-level performance in rule discovery within vast search spaces.

Introduction: The Eleusis Testbed

In the late 1970s, AI research struggled with a dichotomy: general algorithms were often too weak for complex data, while specialized ones lacked portability. The author uses Eleusis to investigate this. In Eleusis, a "dealer" creates a secret rule, and players must induce it by observing which cards are accepted or rejected.

Sample Eleusis layout showing the mainline of accepted cards and sidelines of rejected attempts.

Inducing rules in Eleusis is challenging because rules often involve disjunctions (OR conditions) and require features not explicitly present in raw card data, such as parity or color.

Methodology: Model-Fitting and Layered Knowledge

The system addresses these challenges through two primary innovations.

Induction by Model-Fitting

Rather than an unconstrained search, the program uses "syntactic skeletons" or models to guide discovery. These include Decomposition (mutually exclusive cases), Periodic (repeating sequences), and Disjunctive Normal Form (DNF) using Michalski’s $A^q$ algorithm.

The Knowledge-Layer Structure

The program is organized into five concentric layers. This modularity allows the system to transform raw card data into increasingly abstract concepts, making implicit relationships explicit for the induction engine.

The five-layer hierarchy bridging raw data to basic induction, illustrating the gradient from general to specific knowledge.
  • Layer 4 (Domain Knowledge): Extracts features like color, parity, and "faced-ness."
  • Layer 3 (Segmentation): Groups cards into strings or sequences.
  • Layer 2 (Sequential Analysis): Calculates relationships between consecutive cards, such as value differences.
  • Layer 1 (Basic Induction): The core engine that fits the transformed data to the predefined models.

Key Insights and Results

The program was evaluated against 15 human-played games, successfully navigating a search space of approximately $10^{183}$ possible rules. It typically generated 3 to 5 plausible candidate rules in less than seven seconds on a Cyber 175 mainframe.

A critical insight is the "Intermediate Generality" Heuristic: the system prioritizes rules that are neither too specific nor too general, mirroring the behavior of a "rational" human dealer. Furthermore, the success of the general induction algorithms was found to be entirely dependent on the feature engineering provided by the outer knowledge layers.

Conclusion

By isolating domain-specific knowledge in the outer layers, the author suggests that the inner induction core could be reused for diverse tasks, such as letter series completion, simply by swapping the outer "rings." This modular approach provides a robust framework for applying general induction methods to complex, real-world problems.

Summary updated

BibTeX
@inproceedings{dietterich1980applying,
  author = {Thomas G. Dietterich},
  title = {{Applying General Induction Methods to the Card Game Eleusis}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1980},
}
Figure