Introduction
General Game Playing (GGP) represents a significant challenge in artificial intelligence, requiring agents to play a wide variety of games—ranging from Chess to Tic-Tac-Toe—using only a formal logic-based description of the rules (GDL). Traditionally, GGP agents relied on minimax search paired with automatically generated heuristic evaluation functions. However, these generic heuristics often fail to capture the strategic depth of complex games under strict time constraints. This paper introduces CADIAPLAYER, an agent that bypasses the heuristic bottleneck by utilizing Monte Carlo Tree Search (MCTS) with the UCT algorithm.
Methodology: UCT and Simulation-Based Search
CADIAPLAYER's core innovation is the application of the Upper Confidence-bounds applied to Trees (UCT) algorithm to the GGP domain. Instead of relying on a static evaluation function to estimate the value of a state, the agent performs thousands of random "playouts" (simulations) to the end of the game.
As shown in Figure 1, the search is divided by a "UCT Border." Above this border, the agent uses the UCT formula to balance exploration (visiting new nodes) and exploitation (focusing on high-reward paths). Below the border, the agent performs random simulations to reach terminal states, providing a ground-truth reward signal that propagates back up the tree. This approach allows for asymmetric tree growth, where the agent spends more computational resources on promising lines of play.
Enhancing Simulations: The History Heuristic
A key challenge in simulation-based search is the quality of the "random" playouts. Purely random moves often lead to unrealistic game states. To address this, the authors introduced a domain-independent history heuristic. This method tracks the global success rate of actions across the entire search, regardless of the specific state. By using Gibbs sampling to bias simulations toward generally successful actions, the agent effectively "discovers" strategic concepts like piece capture without explicit programming.
Experimental Results
The effectiveness of CADIAPLAYER was evaluated across several diverse games, including Connect-4, Checkers, Othello, and Breakthrough. The agent demonstrated significant superiority over standard Monte Carlo methods.
As detailed in Figure 5, the UCT-based agent ($CP_{uct}$) consistently outperformed baseline Monte Carlo agents, achieving win rates between 77% and 91% across all tested games. Notably, the history heuristic provided a massive boost in games like Breakthrough, where the enhanced version achieved a 90% win rate over standard UCT. Furthermore, the agent's performance scaled effectively with increased thinking time, proving its robustness in competitive environments.
Conclusion
CADIAPLAYER's victory in the 2007 AAAI GGP Competition solidified the viability of simulation-based approaches in general domains. By replacing fragile, hand-tuned heuristics with a combination of UCT and a learned history heuristic, the authors created an agent capable of expert-level play across a vast spectrum of games. Future work aims to address "chess-like" games where simulations converge slowly, potentially through hybrid methods that incorporate basic evaluation functions for early termination.
Summary updated