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

John Tan Chong Min  Mehul Motani

###### 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.

Machine Learning, Reinforcement Learning, AlphaZero, ICML

##  1 Introduction

Through the years, there has been tremendous progress in Reinforcement
Learning (RL) techniques for both single-player environments and two-player
perfect information environments. Progress has been fuelled by both hardware
advancements as well as availability of computer simulation environments such
as OpenAI Gym (Brockman et al., 2016).

Current RL algorithms are largely trained and tested in the same environment,
for instance Atari 2600, chess and Go. While superhuman performance have been
achieved in these environments (Mnih et al., 2013; Campbell et al., 2002;
Silver et al., 2016), they may not generalize well 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. This limits their deployability
to the real world, where the environment is not stationary and can change over
time.

Previous work on single-player games: Previous work on single-player games
include continuous control tasks such as Cart Pole, Mountain Car as well as
physics joint-based MUJOCO environments (Todorov et al., 2012). A general
survey of RL methods for these environments, typically policy gradient methods
such as REINFORCE (Williams, 1992) or Trust Region Policy Optimization (TRPO)
(Schulman et al., 2015) is detailed in Duan et al. (2016). For the Atari 2600
arcade environment, Deep Q-Network (DQN) was a breakthrough for Model-Free RL,
combining traditional Q-Learning with deep neural networks along with a replay
buffer to achieve superhuman performance on a variety of Atari 2600 games
(Mnih et al., 2013, 2015).

Previous work on two-player perfect information games: Previous work on two-
player perfect information games are generally model-based methods used on
board games and can be classified under three main approaches. The first
approach is via lookahead search with the Minimax algorithm, alpha-beta
pruning and heuristics for evaluating the value of a game state, and is
applied in Samuel’s checkers (Samuel, 1959), Shannon’s chess (Shannon, 1950),
and eventually Deep Blue’s chess (Campbell et al., 2002). The second approach
is via Temporal Difference (TD) learning, most notably utilized in TD-Gammon
(Tesauro, 1994) for backgammon. The third approach is via Monte Carlo Tree
Search (MCTS) (Chaslot et al., 2008) to prioritize searching for paths through
the game tree which are higher in potential reward using an explore-exploit
Upper Confidence Bounds in Trees (UCT) heuristic (Kocsis & Szepesvári, 2006).
This was utilized in AlphaGo (Silver et al., 2016), AlphaGo Zero (Silver et
al., 2017b) for the game of Go. AlphaZero (Silver et al., 2017a) is an
extension of AlphaGo Zero for generic games such as Go, Chess and Shogi.
MuZero (Schrittwieser et al., 2019) is an extension of AlphaZero for both one-
player and two-player games using an internal learned model for planning.
There have been numerous works improving or reimplementing AlphaZero (Bratko,
2018; Moerland et al., 2018; Tian et al., 2019; Wang et al., 2019a, b; Grill
et al., 2020; Ben-Assayag & El-Yaniv, 2021; Dam et al., 2021).

Figure 1: BTTT Environment (Variant 1) with starting brick position at D4

Figure 2: BTTT Environment (Variant 2) with starting brick position at E5

Figure 3: Player 1 (O) winning in BTTT

Figure 4: Player 2 (X) winning in BTTT

Limitations of current environments: The current environments used for RL
generally do not have different train and test environments. Indeed, even the
pseudo-random-number-generator for Atari 2600 games were hardware-constrained
by the Linear Feedback Shift Register to have a fixed random seed, causing the
same deterministic environmental interactions in both train and test
environments (Hausknecht & Stone, 2015). Hence, while neural network-based
approaches such as DQN (Mnih et al., 2013, 2015) can learn without human
expertise in majority of single-player Atari 2600 games, DQN may be able to
just play well by memorizing winning sequences of actions. Indeed, recent
papers (Yuan et al., 2019; Qu et al., 2020) have shown that even a one-pixel
change can adversely affect outcomes in DQN, which indicates that the learned
algorithm only works on an exact replication of the training environment, and
is not generalizable. Likewise, although AlphaZero achieves superhuman
performance for two-player perfect information games such as chess, Shogi and
Go (Silver et al., 2017a), the same phenomenon of memorizing might occur for
AlphaZero when trained and tested on the same environment, which will be the
focus of this paper.

Similar work: Some progress has been made to improve quantization of
generalization ability, most notably through the use of Procedural Content
Generation (PCG) (Risi & Togelius, 2020). One such PCG-based approach is “Coin
Run”, which feature different train and test environments for a single-player
game. Our work is presented in a similar vein to that of PCG-based approaches
- to quantize and develop more generalizable deep RL algorithms in a two-
player setting. One similar work exploring generalizability in two-player
games is Ben-Assayag & El-Yaniv (2021), which has focused on generalizability
to different board sizes via infusing AlphaZero with a graph neural network
(GNN). Another work focuses on zero-shot transfer learning of AlphaZero-like
network weights between game variants and varying board sizes (Soemers et al.,
2021). Another work similar to our objective is XLand, an open-ended
environment which was recently created to test generalization to novel
environments. However, XLand is very complex and requires billions of
timesteps in order to train an agent (Team et al., 2021), which limits fast
iteration of algorithms. Our proposed environment similarly is able to test
generalization to novel environments, but only requires hundreds of
iterations, each using thousands of timesteps, to train the agent. In this
paper, we demonstrate that our proposed environment is sufficient to learn
about the generalizability of AlphaZero. Furthermore, our environment has an
advantage that we can use heuristics to create an agent which achieves perfect
play using Minimax, which helps facilitate benchmarking our other agents.

Motivation: In order to test students’ understanding, a good teacher would set
an examination which is structurally different from the practice problems, yet
conceptually similar. Similarly, in order to test the generalizability of
current RL algorithms such as AlphaZero, MCTS, Minimax, we should use a
slightly different test environment to see if they merely memorize the “model
answer” or are able to learn the underlying concepts. To this end, we propose
a test bed called Brick Tic-Tac-Toe (BTTT) where the test environment is
different from the training environment, so as to better model changing
environmental conditions in real-life. In BTTT, the first player can
theoretically always win under perfect play using the same learned strategy in
the training environment.

Our Contributions: The contributions of this paper are:

  * •

In order to analyze the generalizability of current RL algorithms for two-
player games, we introduce our own test bed, BTTT. The BTTT environment code
and code for the experiments can be found here.

  * •

We pit various agents using different RL methods in a round-robin tournament
on the BTTT environment. We observe that state-search approaches such as MCTS
and Minimax are more generalizable than AlphaZero. While all algorithms can
win as first player in the training environment, only AlphaZero fails to win
as first player in a novel test environment.

  * •

We investigate the effect of changing the parameters of AlphaZero on its
generalizability. We find that 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.
Specifically, we show that it is more generalizable after training on at least
two distinct starting brick positions, and fails to generalize when there is
only one brick starting position.

##  2 Brick Tic-Tac-Toe environment

Current popular learning environments (e.g., Cart Pole, Mountain Car, MUJOCO,
checkers, chess, Go, Atari 2600) typically have the same environment for both
training and testing and are not a good proxy to our real-world environment
where the environment itself can change over time.

To enable the study of RL methods under changing environments, we propose to
use a test bed, Brick Tic-Tac-Toe (BTTT), to serve as a controlled environment
to evaluate the performance of various RL methods under a conceptually
similar, yet unseen test environment. While BTTT might be a simple
environment, it allows us to do a comprehensive analysis of generalizability
across various algorithms, which makes it a suitable testbed for quick
benchmarking of generalizability.

The BTTT environment is a two-player perfect information, sequential turn-
based environment. The following details the core components of the BTTT
environment:

State/Board: The game is played on a 7x7 grid, with the rows labelled A to G,
and columns labelled 1 to 7. Each grid square has a unique name derived from
the row then column, e.g. A3, E5.

Pieces: There are three pieces, O for Player 1’s piece, X for Player 2’s
piece, and B for a brick block. If there are no pieces on a grid square, it is
represented as a blank space.

Start State: At start state, a grid square will be chosen to be a brick block
B, making that square unplayable by both players. The remaining squares will
be empty. The start state will be known to both players.

Rules: The game is a two-player game played sequentially on a 7x7 grid. It is
similar in concept to Tic-Tac-Toe and Gomoku (Tang et al., 2016), except that
the aim of the game is to form a 4-in-a-row, for both players 1 (O) and 2 (X).
O plays first, followed by X, and so on, until there is a winner. If the game
is not won and all possible squares are filled up, it is counted as Player 2’s
(X) win.

Training Environment (Variant 1): This is a 7 x 7 grid with a brick block B in
the centre, position D4. This is depicted in Fig. 4.

Test Environment (Variant 2): This is a 7 x 7 grid with a brick block B at
position E5. This is depicted in Fig. 4.

Win Condition: A win occurs after a player’s move when there is a 4-in-a-row
of Os or Xs in any row, column or diagonal. Note that there is no wraparound
in BTTT, that is, the left and right side of the grid, or the top and bottom
of the grid do not connect. An example of Player 1’s win (O) is depicted in
Fig. 4, and an example of Player 2’s win (X) is depicted in Fig. 4.

Perfect Play: BTTT is designed for the first player to win (Refer to Appendix
A), which means that an agent that is generalizable should be able to win as
first player regardless of where the brick block appears at start state.

##  3 Algorithm Details

We firstly go through some algorithm details for the agents which we use for
the tournament.

###  3.1 Markov Decision Process

We will model the BTTT environment as a Markov Decision Process (MDP), whereby
for a policy mapping a state to an action distribution, $\pi:S\to A$, only the
current state $s_{t}$ is needed as input and the policy is independent of all
previous states. That is,

$\pi(s_{t}|s_{1},s_{2},s_{3},...,s_{t-1})=\pi(s_{t}),$ (1)

where $s_{i}$ represents the state of the game after action $i$.

From (1) above, we can see that given the current state of the game $s_{t}$,
an optimal player has all the information he/she needs to decide on the next
action/move (action space is all of the empty grid squares). Unlike other
games like Chess and Shogi (Silver et al., 2017a), there is no need to
maintain a history of past states in the MDP formulation when doing action-
selection, since there will not be a case of repeated game states in the same
game.

The formulation of the environment as a MDP helps facilitate applying tree-
search based methods like Minimax and MCTS. At each node in the tree, we can
choose our next action based on just on the game state of that node itself.

Parameter |  Value
---|---
Optimizer |  Stochastic Gradient Descent (SGD), learning rate 0.1, momentum 0.9
Exploration factor $c_{PUCT}$ |  1
Memory size per iteration |  6000
Batch size for training |  256
MCTS simulations per move |  100
Regularization constant $c$ |  0.0001
Architecture (Input) |  Input layer of three binary planes of 7x7, followed by a Conv2D (75) block
Architecture (Body) |  From Input, ResNet architecture with 5 hidden layers of two Conv2D (75) blocks each
Architecture (Output - Value) |  From Body, Conv2D (1) block, a Flatten layer, a Dense layer with 20 nodes, LeakyReLU activation function, a Dense layer with 1 node
Architecture (Output - Policy) |  From Body, Conv2D (2) block, a Flatten layer, a Dense layer with 49 nodes
Table 1: Architecture and Hyperparameters of AlphaZero. Each Conv2D (X) block
has this structure: Conv2D with X filters of 4x4, ’same’ padding, followed by
BatchNormalization, followed by the LeakyReLU activation function. For the
Conv2D (X) blocks at the output, the filter size is 1x1 instead.

###  3.2 Minimax

Minimax has been used successfully in world champion chess programs such as
Deep Blue (Campbell et al., 2002), and is a tree-based search method which
models both players acting sequentially in an optimal manner. In particular,
we focus on a two-ply lookahead Minimax which considers all board states
$s_{t+2}$ two moves ahead. In particular, for board state $s_{t}$ which
contains all actions till action $t-1$: $a_{1},a_{2},...,a_{t-1}$, if it is
the maximizing player’s move, we choose the next action $a_{t}$ for the
maximizing player as

$a_{t}=\operatorname*{argmax}_{a_{t}}\min_{a_{t+1}}V(s_{t+2}|s_{t},a_{t},a_{t+1}).$
(2)

Similarly, if it is the minimizing player’s move, we choose the next action
$a_{t}$ for the minimizing player as

$a_{t}=\operatorname*{argmin}_{a_{t}}\max_{a_{t+1}}V(s_{t+2}|s_{t},a_{t},a_{t+1}).$
(3)

In (2) and (3) above, $V(.)$ represents a heuristic-based value function that
evaluates the game state. A positive value represents a state which is good
for the maximizing player, while a negative value represents a state which is
good for the minimizing player. The higher the magnitude, the more desirable
the state for that player.

###  3.3 MCTS

MCTS, like Minimax, is a tree-based search method, but it allows the game tree
to be searched efficiently by prioritizing the moves which lead to higher
rewards in an explore-exploit manner. It comprises of four steps at each
iteration.

Selection. At each node (state) in the game tree, the next action is chosen in
a way to balance between exploration and exploitation. This is done using the
Upper Confidence Bound applied to Trees (UCT) algorithm (Kocsis & Szepesvári,
2006).

We choose the child node by the UCB1 formula

$\operatorname*{argmax}_{a}{\frac{v_{a}}{n_{a}}+C\times\sqrt{\frac{\ln(\sum_{b\in
A}{n_{b}})}{n_{a}}}},$ (4)

where $C$ is the exploration constant, which we set as 1, $v_{a}$ is the value
of the child node taking action $a$ based on the total value of all nodes
below it, $n_{a}$ is the number of visits of the child node taking action $a$,
$A$ represents the entire set of valid actions from the parent node.

Expansion. Once the tree reaches a leaf node which is not fully expanded (all
child nodes created), we expand out a new node by selecting an untried action
from this leaf node.

Simulation. The outcome of a game from the leaf node is simulated by a random
rollout, that is, by playing random moves from the game state of the node to
the end of the game. Heuristic-based action-selection could be used to make
the rollout more accurate, but is not used in this paper.

Backpropagation. At the end of the game, the value of each node traversed
during the game is updated with the game result $r$, which is 1 for Player 1’s
win, -1 for Player 2’s win, and 0 for a draw. For a node below a maximizing
player, $v_{a}=v_{a}+r$, while for a node below a minimizing player,
$v_{a}=v_{a}-r$. This ensures that the value of the game result is converted
to a form where both players can maximize to choose the optimal action based
on (4). Also, for each node traversed during the game, the visit counts are
increased by one: $n_{a}=n_{a}+1$.

Finally, after going through the iterations, the action selected is simply the
child node which was explored the most, which should lead to the highest
reward.

###  3.4 AlphaZero

AlphaZero combines neural networks (i.e. policy and value networks) with MCTS.
The policy network helps to narrow down the search at each game state $s_{t}$
to moves which can lead to good outcomes, while the value network helps to
give a value for the game state as an approximation for lookahead search. This
was first utilized in AlphaGo (Silver et al., 2016), and then AlphaGo Zero
(Silver et al., 2017b) for the game of Go. We use the methodology of
AlphaZero, that is, tabula-rasa without human expert knowledge (Silver et al.,
2017b). For the self-play iterations, we update the best agent after each
self-play iteration, without the need for tournament evaluation, just like in
Silver et al. (2017a).

The neural network in AlphaZero starts off with randomly initialized
parameters $\theta$. The self-play games are played by selecting actions via
MCTS for both players, $a_{t}\sim\pi_{t}$. The terminal position $s_{T}$ is
scored as $z$: -1 for a loss, 0 for a draw and +1 for a win. At the end of a
batch of self-play games, the network parameters $\theta$ are updated to
minimize the error of the predicted outcome $v_{t}$ and the actual game
outcome $z$ using mean-squared error, as well as maximize the similarity of
the policy vector $p_{t}$ to MCTS search probabilities $\pi_{t}$ using
Kullback-Leibler (KL) divergence, with an L2 weight regularization term
parameterized by $c$.

The loss function used to update the neural network is

$l=(z-v)^{2}-\pi^{T}\log p+c{||\theta||}^{2},$ (5)

with $(s,\pi,z)$ sampled uniformly across all time steps
$(s_{t},\pi_{t},z_{t})$ of self-play games in the last agent iteration, while
the policy and value network values are derived from

$(p,v)=f_{\theta}(s).$ (6)

The architecture of the neural network used follows closely to that of Silver
et al. (2017b), and is detailed in Table 1. The feature planes used are a 7x7
binary plane for the current players’ pieces, a 7x7 binary plane for the next
players’ pieces, and a 7x7 binary plane for brick pieces. This differs
slightly from Silver et al. (2017b) as we do not have a plane to encode player
turn, but rather, we always let the first 7x7 binary plane be that of the
current player so that it will always be invariant to either player.

Similar to the AlphaZero papers (Silver et al., 2017a, b), in order to enable
sufficient exploration in beginning states, we pick a move from the move
probability distribution of the visited moves of the MCTS searches in the
first 10 turns, before reverting to greedy action selection based on the most
visited move from the MCTS search. Also, dirichlet noise was added during
training (removed during testing) to bias move selection from the root node in
MCTS so as to increase move diversity.

4-in-a-row Configurations | Value
---|---
X___ or ___X | -0.000001
_X__ or __X_ | -0.000002
X_X_ or X__X or _X_X or XX__ or __XX | -0.0001
_XX_ | -0.0002
X_XX or XX_X or XXX_ or _XXX | -0.01
XXXX | -1
O___ or ___O | 0.0000015
_O__ or __O_ | 0.000003
O_O_ or O__O or _O_O or OO__ or __OO | 0.00015
_OO_ | 0.0003
O_OO or OO_O or OOO_ or _OOO | 0.015
OOOO | 1.5
Other | 0
Table 2: Heuristic used to evaluate state position of the 7x7 grid in Minimax.
‘_’ represents a blank grid square. Value of a grid state is the sum of values
of all possible 4-in-a-row configuration values across all rows, columns,
diagonals in the 7x7 grid. Each 4-in-a-row configuration value is determined
by reading off this lookup table. Higher value is given to more pieces of the
same kind, and configurations with blanks on both sides of them get higher
weightage due to increased possibilities of an extension later in the game.
The 4-in-a-row configuration for Player 1 (O) gets 1.5 times the weightage of
the corresponding ones for Player 2 (X), so as to encourage Player 2 to block
Player 1, as Player 1 has the initiative and needs to be prevented from
winning before Player 2 can win.

##  4 Methodology

In this section, we describe the BTTT tournament in which various agents are
pit against each other.

###  4.1 Tournament Format

We run a round-robin tournament of 100 rounds between various agents using
Variant 2 in order to determine the most generalizable agent. At each turn,
the input to the agent will be the board state of each of the 7x7 grid
squares, and the output will be the action index indicating the selected
square to place the piece on. We then evaluate an agent’s performance by the
number of wins it obtained over 100 games: the higher the number, the better
the performance.

###  4.2 Agents used in the Tournament

  * •

Random. This agent simply selects a random (valid) action each turn. This is
the weakest baseline and all other methods are supposed to be stronger than
this.

  * •

MCTS 1000. This is MCTS with 1000 iterations. This serves as a weak baseline
to evaluate other models.

  * •

MCTS 10000. This is MCTS with 10000 iterations. This serves as a strong
baseline to evaluate other models.

  * •

Minimax. This is applying the Minimax tree search with alpha-beta pruning to
select optimal actions by expanding the game tree to depth 2, and thereafter
using an expert heuristic (see Table 2) to determine the value of a game
state. This serves as the strongest baseline to evaluate other models, and is
a proxy to perfect play.

  * •

AlphaZero 100. An AlphaZero agent was trained from self-play using MCTS
lookahead search to perform policy improvement and evaluation as suggested by
the AlphaZero papers (Silver et al., 2017a, b). The architecture is similar to
the generic version of AlphaZero (Silver et al., 2017a), and we augment the
memory with all 4 reflections of the game due to the symmetrical nature of the
game, which helps the neural network to train faster. We use 100 MCTS
lookahead steps for each move. Each iteration of AlphaZero trains until it has
6000 new states in memory (including reflections) before using minibatch
sampling to train the model for the next iteration. We train it for two weeks,
for a total of 850 iterations.

  * •

AlphaZero 1000. This is the same as AlphaZero 100 during training, except that
during testing, we use 1000 MCTS lookahead searches.

  * •

AlphaZero NS. This is the same as AlphaZero 100 during training, but with no
MCTS lookahead search during testing. The agent simply selects the move with
the highest move probability based on the policy network. This agent is used
as a control to evaluate the role of the MCTS lookahead in the
generalizability of the network.

###  4.3 Training Procedure

There is no training required for MCTS and Minimax. For AlphaZero, which
utilizes a deep learning model, we train the model under Variant 1, and test
it under both variants. We train AlphaZero for up to two weeks (850
iterations). If the model has sufficiently learned the concept of winning with
a brick under Variant 1 and not just memorize the sequence of winning moves in
Variant 1, it should win all the time under Variant 2 as well, since the game
is designed to be always winnable by the first player under perfect play.

Player 1 | Player 2 | Result | Result
---|---|---|---
|  | (Var 1) | (Var 2)
Any | Random | 100 - 0 | 100 - 0
Random | Any | 0 - 100 | 0 - 100
Random | Random | 60 - 40 | 53 - 47
Table 3: Results of Random agent versus Any (AlphaZero NS/100/1000, MCTS 1000/10000, Minimax) and also Random agent against itself in a round-robin tournament of 100 rounds, under both Variant 1 and Variant 2 environments. AlphaZero is trained only on Variant 1, but tested on both variants. Player 1 | Player 2 | Result | Result
---|---|---|---
|  | (Var 1) | (Var 2)
MCTS 1000 | MCTS 1000 | 70 - 30 | 70 - 30
MCTS 1000 | MCTS 10000 | 15 - 85 | 15 - 85
MCTS 10000 | MCTS 1000 | 100 - 0 | 100 - 0
MCTS 10000 | MCTS 10000 | 70 - 30 | 70 - 30
Minimax | MCTS 1000 | 100 - 0 | 100 - 0
Minimax | MCTS 10000 | 100 - 0 | 100 - 0
Minimax | Minimax | 100 - 0 | 100 - 0
MCTS 1000 | Minimax | 9 - 91 | 9 - 91
MCTS 10000 | Minimax | 51 - 49 | 51 - 49
AlphaZero NS | Minimax | 100 - 0 | 0 - 100
AlphaZero 100 | Minimax | 100 - 0 | 0 - 100
AlphaZero 1000 | Minimax | 100 - 0 | 0 - 100
Minimax | AlphaZero 1000 | 100 - 0 | 100 - 0
Table 4: Results of round-robin tournament of 100 rounds. AlphaZero is trained only on Variant 1, but tested on both variants. Agent | Time per move (s)
---|---
Random | 0.000006
MCTS 1000 | 1.88
MCTS 10000 | 18.8
Minimax | 0.97
AlphaZero NS | 0.51
AlphaZero 100 | 5.99
AlphaZero 1000 | 54.87
Table 5: Time per move for each agent, averaged over 100 moves.

###  4.4 Runtime Analysis Procedure

In order to measure the tradeoff between playing strength and runtime, we
perform the runtime analysis by calculating the average time taken per move
over 100 moves for the agent to choose a move/action given the initial board
state. The runtime was calculated using an NVIDIA 2080 RTX GPU and a 256GB RAM
CPU.

##  5 Tournament Results

Player 1 | Player 2 | Result (Var 1) | Result (Var 2)
---|---|---|---
AlphaZero 100 (trained under D4 only) [Baseline] | Minimax | 100 - 0 | 0 - 100
AlphaZero 100R2 (trained randomly under D3 and D4) | Minimax | 100 - 0 | 100 - 0
AlphaZero 100R3 (trained randomly under C3, D3 and D4) | Minimax | 100 - 0 | 100 - 0
AlphaZero 1000 (trained under D4 (Var 1) only) | Minimax | 100 - 0 | 0 - 100
Table 6: Additional results of AlphaZero vs Minimax in 100-round games, under both Variant 1 and Variant 2 environments. Player 1 | Player 2 | Result | Player 1 Win Rate(%)
---|---|---|---
AlphaZero 100 (trained under D4 only) [Baseline] | Minimax | 139 - 351 | 28.4
AlphaZero 100R2 (trained randomly under D3 and D4) | Minimax | 306 - 184 | 62.4
AlphaZero 100R3 (trained randomly under C3, D3 and D4) | Minimax | 443 - 47 | 90.4
AlphaZero 1000 (trained under D4 only) | Minimax | 364 - 126 | 74.3
AlphaZero 1000R2 (trained randomly under D3 and D4) | Minimax | 415 - 75 | 84.7
AlphaZero 1000R3 (trained randomly under C3, D3 and D4) | Minimax | 483 - 7 | 98.6
Minimax [Benchmark for Generalizable Perfect Play] | Minimax | 490 - 0 | 100
Table 7: Additional results of AlphaZero vs Minimax in 490-round games, with
10 games for each starting brick position.

Summary: The results of the round-robin tournament are detailed in Tables 3
and 4. We observe that Minimax achieves perfect play, while AlphaZero trained
on only Variant 1 fails to generalize to Variant 2.

Random Agent vs MCTS/Minimax/AlphaZero: From Table 3, we can see that the
random agent loses all games against MCTS/Minimax/AlphaZero, regardless
whether it is Player 1 or Player 2, under both Variants 1 and 2. We conclude
that the MCTS, Minimax and AlphaZero agents perform better than random under
any general environment.

MCTS vs Minimax: From Table 4, we can conclude that MCTS 1000 and MCTS 10000
are not playing perfectly as they lose some games as Player 1 when pit against
Minimax as Player 2. This is likely because Minimax has expert knowledge
integrated into the heuristic used to evaluate the value function of the game
state, and as such performs the best. MCTS evaluates the game state by random
rollouts, and just 10000 iterations worth of rollouts is probably insufficient
to give a proper valuation of the game state due to the large game state
space.

Minimax vs MCTS: From Table 4, we can conclude that Minimax is superior to
MCTS as it claims victory in all games as Player 1 and MCTS as Player 2.
Minimax typically employs a strategy similar to that of perfect play.

Minimax/MCTS self-play: From Table 4, when Minimax is pit against itself, it
wins all 100 games as Player 1. This shows that Minimax is playing perfectly
as it wins all the time as Player 1. The same cannot be said for MCTS, as even
MCTS 10000 only wins 70 out of 100 of its games as Player 1, which shows that
the state space of BTTT is so large that 10000 lookahead steps cannot
guarantee perfect play. That said, MCTS 10000 is clearly superior to MCTS
1000, as the former wins all 100 of its games against the latter regardless as
Player 1, but the converse is not true.

AlphaZero vs Minimax: From Table 4, we can see that AlphaZero as Player 1 is
able to win all games in Variant 1 against Minimax, but is unable to do so in
a slightly different Variant 2. This hints that AlphaZero may be overfitting
to the training environment and hence unable to generalize to novel
environments. Surprisingly, AlphaZero NS also managed to win all games in
Variant 1, which means that the neural network has already achieved perfect
play in the training environment, even without any lookahead search. This
validates the power of the self-play algorithm of AlphaZero to improve itself
as even the policy network alone is sufficient to make a good decision after
enough training.

Minimax vs AlphaZero: As a control, we pit Minimax as Player 1 against
AlphaZero as Player 2, and Minimax managed to win all games in both variants.
This means that a truly generalizable method such as Minimax should be able to
do so, and hence AlphaZero in its native form is not generalizable enough.

##  6 Runtime Analysis

From Table 5, we can see that the agents which are more generalizable (MCTS,
Minimax) typically are those with lookahead search, and take more time to
evaluate the position the more lookahead is done. This can be seen as MCTS
10000 has a lookahead of 10000 steps, and is about ten times the runtime of
MCTS 1000, which has a lookahead of 1000 steps. Minimax looks ahead for two
ply, which is $48\times 47=2256$ moves. We would expect Minimax to have a
runtime in between that of MCTS 1000 and MCTS 10000. However, because Minimax
uses a heuristic to evaluate a leaf node (no random rollouts needed like MCTS)
and utilizes alpha-beta pruning, it is actually much faster and is about half
the runtime of MCTS 1000. This shows that having a heuristic can help reduce
runtime significantly.

For a neural network-based value approach like AlphaZero, it is slower than
the lookahead search methods, since it executes both lookahead and running
through the neural network algorithm. However, AlphaZero NS with no lookahead
performs significantly faster than the lookahead methods.

Overall, there is a tradeoff between playing strength and runtime. Rather than
increasing playing strength by increasing lookahead steps and incurring an
increase in runtime, feasible alternatives are to use a heuristic (Minimax) or
to use a neural network (AlphaZero NS).

##  7 Improving AlphaZero

In Table 4, we can see that AlphaZero does not generalize well. We investigate
if we can make AlphaZero generalize better by training with an increased
variety of starting brick positions. We train two other variants of AlphaZero
100, namely AlphaZero 100R2 (starting brick position randomly at D3 and D4),
and AlphaZero 100R3 (starting brick position randomly at C3, D3 and D4), In
Table 6, we compare the performances of AlphaZero 100, 100R2 and 100R3 against
the strongest baseline for perfect play (Minimax) in both Variants 1 and 2.

Results: From Table 6, AlphaZero 100R2 and AlphaZero 100R3 perform better than
the baseline, achieving perfect play even in Variant 2. We posit that the
varying starting brick positions could have enabled the network to learn the
function of the brick block, rather than just memorizing it as a fixed
position. It may hint that there may have been overfitting occuring in the
AlphaZero baseline when it was only exposed to Variant 1, as even with 1000
MCTS lookahead searches, it was unable to generalize to Variant 2.

##  8 Can we generalize even more?

Given the similar performance of AlphaZero 100R2 and 100R3 in Table 6, we
perform more experiments to further distinguish their generalizability.
Instead of just evaluating on Variant 2, we evaluate on all possible starting
brick positions, for a total of 490 games, with 10 games for each possible
starting brick position. In Table 7, we compare the performance of AlphaZero
100, 100R2 and 100R3 and the variants with 1000 MCTS lookahead searches during
testing (AlphaZero 1000, Alphazero 1000R2, AlphaZero 1000R3).

Results: The AlphaZero 100 baseline does very poorly and is only able to win
in a small number of games (139 out of 490). This is likely due to the fact
that the model did not manage to have sufficient examples to learn the
function of a brick block. AlphaZero 100R2 performed better, winning 306 out
of 490 games. This shows that even just two different starting brick positions
is able to help achieve a higher level of generalizability. AlphaZero 100R3
performed even better, winning 443 out of 490 games. While AlphaZero 100R3
achieves a higher number of wins as compared to AlphaZero 100 baseline, it
does not win all games and we posit that we would need more training
environments in order to achieve generalizable perfect play.

The AlphaZero 1000 variants perform better than their AlphaZero 100
counterparts, highlighting the usefulness of increased lookahead searches in
generalizing to most environments (though not for all as seen in Table 6).

Towards Perfect Play: Even with 1000 MCTS lookahead searches and three
training environments, AlphaZero 1000R3 still did not manage to win all games,
which highlights the complexity of the BTTT environment. As a benchmark,
Minimax wins all games regardless of brick position as first player, which
will be something to strive towards for neural network-based methods such as
AlphaZero.

##  9 Conclusion

BTTT is a novel testbed to study generalizability of RL methods and we use it
to study the performance of AlphaZero. Our results show that Minimax performs
the best for BTTT, followed by MCTS, AlphaZero, then random. When trained
solely on one training environment, AlphaZero seems to memorize the training
environment and is only effective within the same training environment. It is
unable to extrapolate well to novel unseen test environments, which limits its
deployment to the real world. Our results also show that AlphaZero generalizes
better to novel test environments when trained with more diverse environments,
as well as with increased lookahead searches.

Overall, we can see that although BTTT is a simple environment, it allows us
to do a comprehensive analysis of generalizability across various algorithms,
which makes it a suitable testbed for quick benchmarking of generalizability.

Future Work: Given that AlphaZero is able to generalize better with increased
variability in the training environments, it is interesting to see whether
MuZero (Schrittwieser et al., 2019) is able to generalize with even lesser
variability of the training environments, as it internally keeps a learned
model of the environment, which may help it plan better. Furthermore, given
the success of GNN-based methods to generalize to different board sizes (Ben-
Assayag & El-Yaniv, 2021), we would like to explore if using GNN as the
internal architecture to encompass the state information in AlphaZero/MuZero
could help it generalize better as well. Furthermore, we can also scale BTTT
to larger grids with varying number of bricks to test out the effects of more
complex environments on generalizability.

## References

  * Ben-Assayag & El-Yaniv (2021) Ben-Assayag, S. and El-Yaniv, R.  Train on small, play the large: Scaling up board games with alphazero and gnn.  _arXiv preprint arXiv:2107.08387_ , 2021.
  * Bratko (2018) Bratko, I.  Alphazero–what’s missing?  _Informatica_ , 42(1), 2018.
  * Brockman et al. (2016) Brockman, G., Cheung, V., Pettersson, L., Schneider, J., Schulman, J., Tang, J., and Zaremba, W.  Openai gym.  _arXiv preprint arXiv:1606.01540_ , 2016.
  * Campbell et al. (2002) Campbell, M., Hoane Jr, A. J., and Hsu, F.-h.  Deep blue.  _Artificial intelligence_ , 134(1-2):57–83, 2002\.
  * Chaslot et al. (2008) Chaslot, G., Bakkes, S., Szita, I., and Spronck, P.  Monte-carlo tree search: A new framework for game ai.  In _AIIDE_ , 2008.
  * Dam et al. (2021) Dam, T. Q., D’Eramo, C., Peters, J., and Pajarinen, J.  Convex regularization in monte-carlo tree search.  In _International Conference on Machine Learning_ , pp. 2365–2375. PMLR, 2021.
  * Duan et al. (2016) Duan, Y., Chen, X., Houthooft, R., Schulman, J., and Abbeel, P.  Benchmarking deep reinforcement learning for continuous control.  In _International Conference on Machine Learning_ , pp. 1329–1338, 2016.
  * Grill et al. (2020) Grill, J.-B., Altché, F., Tang, Y., Hubert, T., Valko, M., Antonoglou, I., and Munos, R.  Monte-carlo tree search as regularized policy optimization.  In _International Conference on Machine Learning_ , pp. 3769–3778. PMLR, 2020.
  * Hausknecht & Stone (2015) Hausknecht, M. J. and Stone, P.  The impact of determinism on learning atari 2600 games.  In _AAAI Workshop: Learning for General Competency in Video Games_ , 2015.
  * Kocsis & Szepesvári (2006) Kocsis, L. and Szepesvári, C.  Bandit based monte-carlo planning.  In _European conference on machine learning_ , pp. 282–293. Springer, 2006.
  * Mnih et al. (2013) Mnih, V., Kavukcuoglu, K., Silver, D., Graves, A., Antonoglou, I., Wierstra, D., and Riedmiller, M.  Playing atari with deep reinforcement learning.  _arXiv preprint arXiv:1312.5602_ , 2013.
  * Mnih et al. (2015) Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Veness, J., Bellemare, M. G., Graves, A., Riedmiller, M., Fidjeland, A. K., Ostrovski, G., et al.  Human-level control through deep reinforcement learning.  _Nature_ , 518(7540):529–533, 2015.
  * Moerland et al. (2018) Moerland, T. M., Broekens, J., Plaat, A., and Jonker, C. M.  A0c: Alpha zero in continuous action space.  _arXiv preprint arXiv:1805.09613_ , 2018.
  * Qu et al. (2020) Qu, X., Sun, Z., Ong, Y. S., Gupta, A., and Wei, P.  Minimalistic attacks: How little it takes to fool deep reinforcement learning policies.  _IEEE Transactions on Cognitive and Developmental Systems_ , 2020\.
  * Risi & Togelius (2020) Risi, S. and Togelius, J.  Increasing generality in machine learning through procedural content generation.  _Nature Machine Intelligence_ , 2(8):428–436, 2020.
  * Samuel (1959) Samuel, A. L.  Some studies in machine learning using the game of checkers.  _IBM Journal of research and development_ , 3(3):210–229, 1959.
  * Schrittwieser et al. (2019) Schrittwieser, J., Antonoglou, I., Hubert, T., Simonyan, K., Sifre, L., Schmitt, S., Guez, A., Lockhart, E., Hassabis, D., Graepel, T., et al.  Mastering atari, go, chess and shogi by planning with a learned model.  _arXiv preprint arXiv:1911.08265_ , 2019.
  * Schulman et al. (2015) Schulman, J., Levine, S., Abbeel, P., Jordan, M., and Moritz, P.  Trust region policy optimization.  In _International conference on machine learning_ , pp. 1889–1897, 2015.
  * Shannon (1950) Shannon, C. E.  Xxii. programming a computer for playing chess.  _The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science_ , 41(314):256–275, 1950.
  * Silver et al. (2016) Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., Van Den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., et al.  Mastering the game of go with deep neural networks and tree search.  _Nature_ , 529(7587):484–489, 2016.
  * Silver et al. (2017a) Silver, D., Hubert, T., Schrittwieser, J., Antonoglou, I., Lai, M., Guez, A., Lanctot, M., Sifre, L., Kumaran, D., Graepel, T., Lillicrap, T., Simonyan, K., and Hassabis, D.  Mastering chess and shogi by self-play with a general reinforcement learning algorithm, 2017a.
  * Silver et al. (2017b) Silver, D., Schrittwieser, J., Simonyan, K., Antonoglou, I., Huang, A., Guez, A., Hubert, T., Baker, L., Lai, M., Bolton, A., et al.  Mastering the game of go without human knowledge.  _Nature_ , 550(7676):354–359, 2017b.
  * Soemers et al. (2021) Soemers, D. J., Mella, V., Piette, E., Stephenson, M., Browne, C., and Teytaud, O.  Transfer of fully convolutional policy-value networks between games and game variants.  _arXiv preprint arXiv:2102.12375_ , 2021.
  * Tang et al. (2016) Tang, Z., Zhao, D., Shao, K., and Lv, L.  Adp with mcts algorithm for gomoku.  In _2016 IEEE Symposium Series on Computational Intelligence (SSCI)_ , pp. 1–7. IEEE, 2016.
  * Team et al. (2021) Team, O. E. L., Stooke, A., Mahajan, A., Barros, C., Deck, C., Bauer, J., Sygnowski, J., Trebacz, M., Jaderberg, M., Mathieu, M., McAleese, N., Bradley-Schmieg, N., Wong, N., Porcel, N., Raileanu, R., Hughes-Fitt, S., Dalibard, V., and Czarnecki, W. M.  Open-ended learning leads to generally capable agents, 2021.
  * Tesauro (1994) Tesauro, G.  Td-gammon, a self-teaching backgammon program, achieves master-level play.  _Neural computation_ , 6(2):215–219, 1994.
  * Tian et al. (2019) Tian, Y., Ma, J., Gong, Q., Sengupta, S., Chen, Z., Pinkerton, J., and Zitnick, L.  Elf opengo: An analysis and open reimplementation of alphazero.  In _International Conference on Machine Learning_ , pp. 6244–6253. PMLR, 2019.
  * Todorov et al. (2012) Todorov, E., Erez, T., and Tassa, Y.  Mujoco: A physics engine for model-based control.  In _2012 IEEE/RSJ International Conference on Intelligent Robots and Systems_ , pp. 5026–5033. IEEE, 2012.
  * Wang et al. (2019a) Wang, H., Emmerich, M., Preuss, M., and Plaat, A.  Alternative loss functions in alphazero-like self-play.  In _2019 IEEE Symposium Series on Computational Intelligence (SSCI)_ , pp. 155–162. IEEE, 2019a.
  * Wang et al. (2019b) Wang, H., Emmerich, M., Preuss, M., and Plaat, A.  Hyper-parameter sweep on alphazero general.  _arXiv preprint arXiv:1903.08129_ , 2019b.
  * Williams (1992) Williams, R. J.  Simple statistical gradient-following algorithms for connectionist reinforcement learning.  _Machine learning_ , 8(3-4):229–256, 1992.
  * Yuan et al. (2019) Yuan, X., He, P., Zhu, Q., and Li, X.  Adversarial examples: Attacks and defenses for deep learning.  _IEEE transactions on neural networks and learning systems_ , 30(9):2805–2824, 2019.

##  Appendix A Proof that BTTT is always winnable as first player

This section demonstrates why BTTT is always winnable as first player, for
Variant 1, Variant 2 as well as for any arbitrary starting brick location.

###  A.1 Brick at D3 location (Variant 1)

Key Concept. The key concept behind BTTT is to form multiple threat axes with
the pieces. Each piece can form a 4-in-arow in four different orientations -
either row, column, forward diagonal or backward diagonal, making there exist
four threat axes. The moment one player has a 3-in-a-row with the left and
right flank empty (we term this the Unblockable-3), then there is nothing the
other player can do to stop him/her from forming 4-in-a-row as blocking either
the left or right flank would still allow that player to put his/her piece on
the other flank to form the 4-in-a-row.

Winning Strategy Idea. The idea behind the sure-win strategy for Player 1 is
to place pieces to maximize threat axes, and after three moves, have two axes
which could be expanded to form an Unblockable-3. The next step will then be
to form the Unblockable-3 regardless of which axis the opponent blocks and win
the game.

Illustration of Winning Strategy. The winning strategy is shown in Fig. A1.
Initially, Player 1 should place his/her piece at C3, in order to form three
threat axes (shown as the orange, blue and green axes). Player 2 can only
block one of these axes in the next move as strongest play. Thereafter, Player
1 should expand to form a two-in-a-row in one of the unblocked axis (here
shown as the green axis). Seeing as this can lead to an Unblockable-3 the next
turn, Player 2 will have to block this axis to prevent Player 1 from winning.
Then, the third move for Player 1 will form a two-in-a-row with the first
piece and the second piece (shown as the blue and orange axes), thereby
ensuring his/her victory. Player 2 can only block one such axis, leaving
Player 1 to form an Unblockable-3 on the unblocked axis the next turn, and
thereafter, winning the game.

Figure A1: Winning sequence for Player 1 if the starting brick is at the
centre (D3) location. Moves are read left to right, then top to bottom. First
two board states show the starting brick position, and the first move by
player 1 respectively. Thereafter, the next few board states show Player 2’s
(X) response followed by Player 1’s (O) follow-up response.

###  A.2 Brick at E4 location (Variant 2)

If the starting brick is not at the centre (D4), but instead at E5, then it is
even easier for the first player to win as there is more open space on the top
left corner of the board. One way for the first player to win is to apply the
same set of moves as in Fig. A1. This sequence of moves played out in Variant
2 is illustrated in Fig. A2.

Figure A2: Winning sequence for Player 1 if the starting brick is at the E4
location. Moves are read left to right, then top to bottom. First two board
states show the starting brick position, and the first move by player 1
respectively. Thereafter, the next few board states show Player 2’s (X)
response followed by Player 1’s (O) follow-up response.

###  A.3 Brick at any location

In fact, we can generalize the argument made above to show that the brick can
be at any starting position, and there will always be a winning sequence for
Player 1. Without loss of generality, let us assume that the brick is always
in the bottom right quadrant shown as the B locations in Fig. A3. We can
always assume this because BTTT is rotationally symmetric, and we can always
rotate the grid such that the brick is at the bottom right quadrant.
Thereafter, we apply the same argument for the brick in D4 or E5, and show
that there exists a winning sequence for Player 1. In fact, for the brick at
any position other than at D4, there will be more room for Player 1 to form
threat axes and, in general, it should be easier for Player 1 to win.

Figure A3: Winning sequence for Player 1 if the starting brick is at any
location. Moves are read left to right, then top to bottom. First two board
states show the starting brick position, and the first move by player 1
respectively. Thereafter, the next few board states show Player 2’s (X)
response followed by Player 1’s (O) follow-up response.