Fast and Knowledge-Free Deep Learning for General Game Playing (Student Abstract)

Michal Maras, Michal Kepa, Jakub Kowalski, Marek SzykulaAAAI 2024 · DOI

TL;DR

This paper presents a novel approach to General Game Playing (GGP) by adapting AlphaZero to be "knowledge-free," meaning it requires minimal explicit information about game rules like action spaces or board topology. By using attention mechanisms and generating training data via MCTS instead of self-play, they achieve competitive performance with significantly faster model generation, making GGP more accessible.

What Problem Does This Paper Address?

General Game Playing (GGP) aims to create AI agents that can play any game given its rules, without prior game-specific knowledge. While deep learning, particularly AlphaZero, has shown immense success in specific games like Go and Chess, applying it to GGP faces challenges. Existing GGP systems often rely on formalisms like GDL or RBG, and adapting deep learning models like AlphaZero requires significant manual effort to encode game-specific information, such as the action space and board topology. This manual encoding is a bottleneck, especially for games with complex or unusual structures. Furthermore, training these models can be computationally expensive and time-consuming. This paper tackles the problem of building effective GGP agents with deep learning while minimizing the need for game-specific knowledge and accelerating the model generation process.

Methods

The authors adapt the AlphaZero framework for General Game Playing, focusing on two-player, zero-sum, perfect information games. Their key innovations lie in:

  • Knowledge-Free Adaptation: They eliminate the need for explicit knowledge of the action space and board topology.
  • Action Space: Instead of a policy network that predicts actions, they rely solely on a value network. This bypasses the need to define or infer the action space, which can be complex and vary greatly between games. They use the standard UCT formula for exploration, rather than PUCT which relies on action predictions.
  • Board Topology: They replace convolutional neural networks (CNNs), which inherently assume spatial locality and neighborhood relationships, with attention-based neural networks (Vaswani et al., 2017). Attention mechanisms allow the model to learn relationships between any tiles on the board, regardless of their spatial proximity, making it robust to non-standard or obfuscated board layouts.
  • Fast Dataset Generation: They generate training data using standard Monte Carlo Tree Search (MCTS) agents playing against each other, rather than relying on computationally expensive self-play. This approach is faster, can be easily parallelized on CPUs, and doesn't require GPUs, significantly reducing training time and resource requirements.

Datasets

The paper does not introduce new datasets. Instead, it evaluates its method on a variety of existing board games, including:

  • Breakthrough (various sizes)
  • Connect Four
  • English Draughts
  • Fox and Hounds
  • Gomoku
  • Hex (various sizes)
  • Pentago
  • Reversi
  • The Mill Game

The training datasets are generated on-the-fly using MCTS plays, with varying numbers of plays (200, 400, 1,000) and generation times (up to 2 hours).

Key Insights and Ideas

  • Attention is a powerful alternative to CNNs for GGP: The ability of attention mechanisms to learn arbitrary relationships between board elements, without assuming spatial locality, makes them highly suitable for GGP where board topologies can be irregular or non-intuitive.
  • Value-only networks are sufficient for GGP: By removing the policy network and relying solely on a value network, the authors demonstrate that effective game-playing agents can be trained without explicit action space knowledge.
  • MCTS-based data generation is a viable shortcut: Using MCTS plays for dataset generation, instead of computationally intensive self-play, significantly speeds up the training process and makes GGP research more accessible, especially for researchers with limited computational resources.
  • Knowledge-free GGP is achievable and competitive: The results suggest that deep learning models can achieve strong performance in GGP without requiring game-specific knowledge, challenging the notion that such knowledge is a prerequisite for success.

Key Results

  • Competitive Performance: The proposed attention-based NN agents, trained with MCTS-generated data, outperform the standard UCT baseline in most games tested.
  • Robustness to Board Permutation: When board tiles are randomly permuted (to break spatial correlations), the attention NN shows a smaller win ratio drop compared to the convolutional NN, highlighting its robustness.
  • Fast Model Generation: The method allows for rapid model generation. For instance, after just a few minutes of computing (short training), the agents can achieve competitive win rates against the UCT baseline. Table 1 shows average win rates against a UCT baseline with 600 iterations, with the attention NN achieving 75% and the convolutional NN 63%. Table 2 shows results after very short training, where the attention NN achieves win rates like 60% for Breakthrough (6x6) and 42% for English Draughts.

Limitations and Future Work

  • Focus on Two-Player, Zero-Sum, Perfect Information Games: The current method is limited to this class of games. Extending it to imperfect information or multi-player games would be a significant next step.
  • Short Training Focus: The paper emphasizes fast model generation and short training times. While this is a key contribution, exploring performance with longer training durations could reveal further potential.
  • Comparison to AlphaZero: While inspired by AlphaZero, a direct comparison of the knowledge-free approach against a fully tuned AlphaZero for specific games (where knowledge is available) is not the primary focus. The paper's strength lies in its generality and speed.
  • Future Work: The authors suggest exploring the use of learned positional embeddings in the attention network and further investigating the trade-offs between MCTS playout quality and training efficiency.

Summary updated

BibTeX
@inproceedings{maras2024fast,
  author = {Michal Maras and Michal Kepa and Jakub Kowalski and Marek Szykula},
  title = {{Fast and Knowledge-Free Deep Learning for General Game Playing (Student Abstract)}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i21.30480},
}
Figure