Learning Simulation Control in General Game-Playing Agents

Hilmar Finnsson, Yngvi BjörnssonAAAI 2010 · DOI

Abstract

General Game Playing (GGP) agents must master unknown games using only a formal rulebook. This paper introduces several novel simulation control schemes—most notably the Features-to-Action Sampling Technique (FAST)—that allow agents to move beyond blind random playouts. By using reinforcement learning to infer piece values and other game features on the fly, these methods significantly outperform the previous state-of-the-art across diverse game types, particularly in tactically complex environments where random simulations fail to provide a clear signal.

Introduction: The Challenge of Generalization

In artificial intelligence, specialized systems like Deep Blue are highly effective but limited to specific domains. General Game Playing (GGP) represents the "decathlon" of AI: agents are provided with the rules of a brand-new game in a formal language (GDL) and must learn to play at an expert level within minutes.

Modern GGP agents rely on Monte-Carlo Tree Search (MCTS). As illustrated in Figure 1, MCTS works by running thousands of "playouts"—simulating a game from the current state to the end by picking moves.

The four phases of Monte-Carlo Tree Search (MCTS): Selection, Expansion, Playout, and Back-Propagation.

Traditionally, these playout moves are selected at random. However, in complex games like Chess or Skirmish, random play is so low-quality that the agent receives a "noisy" signal, making it nearly impossible to distinguish a good move from a bad one. The core challenge is automatically learning which moves to prioritize during these simulations without any pre-existing knowledge of the game.

Methods: Informed Simulation Control

The authors evaluate five search-control mechanisms designed to bias simulations toward more promising moves:

  1. MAST (Move-Average Sampling Technique): Maintains a global average of move performance across all simulations, regardless of the specific board state.
  2. TO-MAST (Tree-Only MAST): A variation that learns only from moves made within the high-quality search tree, ignoring noisier playout data.
  3. PAST (Predicate-Average Sampling Technique): A context-aware version of MAST that tracks move values based on specific board facts (predicates).
  4. RAVE (Rapid Action Value Estimation): A technique that uses moves made later in a simulation to update the values of those same moves at the current step, accelerating learning.
  5. FAST (Features-to-Action Sampling Technique): The paper’s primary contribution. It uses Temporal-Difference learning (TD-λ) to automatically identify and weigh features like piece types and cell locations, effectively learning a "piece-square table" on the fly.

Experimental Results and Analysis

The agents were evaluated on four distinct games: Breakthrough (a race game), Checkers, Othello, and Skirmish (a chess-like game designed to be difficult for random simulations).

Win percentages of various simulation control techniques against a standard MCTS baseline across four benchmark games.

Key Insights

  • Feature Inference as a Game-Changer: Even without explicit knowledge of piece values, the FAST method can infer that certain symbols consistently lead to higher rewards. In the tactically complex Skirmish, FAST achieved a staggering win rate of over 96% against standard MCTS.
  • Quality vs. Quantity: TO-MAST demonstrated that learning from a smaller amount of "informed" tree data can be superior to using massive amounts of noisy playout data, particularly in games like Checkers.
  • The Hybrid Advantage: Combining techniques—specifically using RAVE for the tree search and MAST or FAST for the playouts—yielded the best results in games like Othello, where standard simulation-based agents often struggle.

Conclusion

Informing MCTS simulations through automated feature learning is essential for robust General Game Playing. While no single technique is a "silver bullet"—MAST performed best in Breakthrough while TO-MAST excelled in Checkers—the introduction of FAST provides a powerful tool for mastering tactically deep games. Future work will focus on reducing computational overhead and expanding feature detection to include more complex spatial patterns.

Summary updated

BibTeX
@inproceedings{finnsson2010learning,
  author = {Hilmar Finnsson and Yngvi Björnsson},
  title = {{Learning Simulation Control in General Game-Playing Agents}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2010},
  doi = {10.1609/aaai.v24i1.7651},
}
Figure