Brick Tic-Tac-Toe: Exploring the Generalizability of AlphaZero to Novel Test Environments

Chong Min John Tan, Mehul MotaniarXiv 2022 · DOI · OpenReview

TL;DR

This paper introduces "Brick Tic-Tac-Toe" (BTTT), a new benchmark designed to test the generalizability of Reinforcement Learning (RL) agents. They found that AlphaZero, despite its superhuman performance, struggles to generalize to slightly different game configurations, while simpler methods like Minimax and MCTS are more robust.

What Problem Does This Paper Address?

Many current RL algorithms are trained and tested in identical environments. This leads to agents that can perform exceptionally well in their training environment but fail to adapt when faced with even minor variations in the test environment. This lack of generalizability is a significant hurdle for deploying RL in real-world scenarios where environments are dynamic and non-stationary. The authors aim to address this by creating a testbed that specifically probes an agent's ability to generalize to novel, yet conceptually similar, environments.

Methods

The core of the paper is the introduction of the Brick Tic-Tac-Toe (BTTT) environment. BTTT is a two-player, perfect information, sequential turn-based game on a 7x7 grid, similar to Tic-Tac-Toe but with the goal of achieving four-in-a-row. The key novelty is the introduction of a single "brick" that occupies one square, making it unplayable. The training environment has the brick in a fixed position (D4), while the test environment uses a different, fixed position (E5).

The authors then pit several agents against each other in a round-robin tournament:

  • Random: A baseline agent.
  • MCTS (1000 and 10000 iterations): Monte Carlo Tree Search, a standard search algorithm.
  • Minimax: A classic game-tree search algorithm, often considered to represent "perfect play" with heuristics.
  • AlphaZero (various configurations): A state-of-the-art RL agent combining deep neural networks with MCTS.

They specifically investigate AlphaZero's generalizability by varying its training (e.g., using different brick positions) and testing parameters (e.g., MCTS lookahead depth).

Datasets

The paper introduces a novel benchmark environment: Brick Tic-Tac-Toe (BTTT).

  • Training Environment: A 7x7 grid with a brick at position D4.
  • Test Environment: A 7x7 grid with a brick at position E5.
  • Extended Test Environments: For further analysis, they also consider all possible starting brick positions.

No external datasets are used for training or evaluation; the agents are trained and evaluated within the BTTT framework.

Key Insights and Ideas

  • Generalization is Harder Than Superhuman Performance: AlphaZero's ability to achieve superhuman performance in complex games like Go doesn't automatically translate to generalizability in simpler, but varied, environments.
  • The "Novel Test Environment" Problem: A slight change in the game's setup (the brick's position) is enough to significantly degrade AlphaZero's performance, highlighting a common failure mode in RL.
  • Simpler Methods Can Be More Robust: Traditional algorithms like Minimax, which incorporate explicit heuristics and search, demonstrate superior generalizability to AlphaZero in this context.
  • Training Diversity is Crucial: Simply increasing the search depth (MCTS iterations) in AlphaZero wasn't enough. Exposing AlphaZero to a variety of training environments (different brick positions) was key to improving its generalization.
  • BTTT is a Rich Benchmark: Despite its simplicity, BTTT proves effective at revealing these generalizability issues, making it a valuable tool for future research.

Key Results

  • Minimax Achieves Perfect Play: Minimax consistently wins against all other agents, demonstrating robust performance across all BTTT variants.
  • AlphaZero Struggles with Novelty: When trained only on Variant 1 (brick at D4), AlphaZero fails to win against Minimax in Variant 2 (brick at E5).
  • MCTS is Better Than AlphaZero (in this context): MCTS agents, especially with more iterations, show better generalizability than AlphaZero when trained on a single environment.
  • Training Diversity Boosts AlphaZero: Training AlphaZero with multiple starting brick positions (e.g., R2 and R3 variants) significantly improves its win rate against Minimax in novel environments, with R3 achieving a 90.4% win rate in 490 games.
  • Runtime Trade-off: More generalizable agents (Minimax, MCTS) tend to have higher runtimes per move, but heuristics can help reduce this. AlphaZero NS (no lookahead search) is faster but less capable.

Limitations and Future Work

  • Limitations:
    • The paper acknowledges that even with increased training diversity, AlphaZero 1000R3 did not achieve perfect play in all scenarios, suggesting BTTT is complex enough to still pose a challenge.
  • The current AlphaZero implementation might be overfitting to the training environment, a common issue in deep learning.
  • Future Work:
    • Investigate if MuZero, which uses an internal learned model, can generalize better with less training variability.
  • Explore using Graph Neural Networks (GNNs) within AlphaZero/MuZero to better capture state information and improve generalization.
  • Scale BTTT to larger grids and more bricks to test generalization in more complex environments.
  • Develop neural network-based methods that can achieve generalizable perfect play, matching Minimax's performance.

Summary updated

Abstract

Traditional reinforcement learning (RL) environments typically are the same for both the training and testing phases. Hence, current RL methods are largely not generalizable to a test environment which is conceptually similar but different from what the method has been trained on, which we term the novel test environment. As an effort to push RL research towards algorithms which can generalize to novel test environments, we introduce the Brick Tic-Tac-Toe (BTTT) test bed, where the brick position in the test environment is different from that in the training environment. Using a round-robin tournament on the BTTT environment, we show that traditional RL state-search approaches such as Monte Carlo Tree Search (MCTS) and Minimax are more generalizable to novel test environments than AlphaZero is. This is surprising because AlphaZero has been shown to achieve superhuman performance in environments such as Go, Chess and Shogi, which may lead one to think that it performs well in novel test environments. Our results show that BTTT, though simple, is rich enough to explore the generalizability of AlphaZero. We find that merely increasing MCTS lookahead iterations was insufficient for AlphaZero to generalize to some novel test environments. Rather, increasing the variety of training environments helps to progressively improve generalizability across all possible starting brick configurations.
BibTeX
@misc{tan2022brick,
  author = {Chong Min John Tan and Mehul Motani},
  title = {{Brick Tic-Tac-Toe: Exploring the Generalizability of AlphaZero to Novel Test Environments}},
  year = {2022},
  eprint = {2207.05991},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2207.05991},
}
Figure