# Evaluation Beyond Task Performance:
Analyzing Concepts in AlphaZero in Hex

Charles Lovering Jessica Zosa Forde∗
George Konidaris Ellie Pavlick Michael L. Littman
Department of Computer Science
Brown University
<EMAIL_ADDRESS>Equal contribution.

###### Abstract

AlphaZero, an approach to reinforcement learning that couples neural networks
and Monte Carlo tree search (MCTS), has produced state-of-the-art strategies
for traditional board games like chess, Go, shogi, and Hex. While researchers
and game commentators have suggested that AlphaZero uses concepts that humans
consider important, it is unclear how these concepts are captured in the
network. We investigate AlphaZero’s internal representations in the game of
Hex using two evaluation techniques from natural language processing (NLP):
model probing and behavioral tests. In doing so, we introduce new evaluation
tools to the RL community, and illustrate how evaluations other than task
performance can be used to provide a more complete picture of a model’s
strengths and weaknesses. Our analyses in the game of Hex reveal interesting
patterns and generate some testable hypotheses about how such models learn in
general. For example, we find that MCTS discovers concepts before the neural
network learns to encode them. We also find that concepts related to short-
term end-game planning are best encoded in the final layers of the model,
whereas concepts related to long-term planning are encoded in the middle
layers of the model.

https://bit.ly/alphatology https://github.com/jzf2101/alphatology

##  1 Introduction

AlphaZero [59], a reinforcement-learning agent that combines Monte Carlo tree
search [8] with deep reinforcement learning, has achieved impressive
performance at games like Go, chess, shogi, and Hex. Domain experts have
observed that AlphaZero uses, but does not master, identifiable game concepts.
For example, despite being exceptionally strong overall, AlphaZero appeared
unable fully to project the implications of a ladder—an important concept in
the game of Go [64].

Good performance can mask flaws in deep learning systems generally [3, 53, 23,
10, 15, 73, 11], and deep reinforcement-learning systems in particular [70,
74]. Evaluating systems in terms of task performance alone makes it impossible
to know if systems are “right for the right reasons” and difficult to predict
how they will generalize to new situations [71, 72]. Recently, the field of
natural language processing (NLP) has begun to develop evaluation techniques
that go beyond “just” task performance [4, 5]. For example, some techniques,
probing classifiers, inspect the form of models’ internal representations to
test whether they are consistent with linguistic theory [1, 9, 62]; other
techniques, behavioral tests or challenge sets, evaluate specific types of
out-of-distribution generalization to assess whether models encode human-like
inductive biases [14, 20, 33, 35, 37, 42, 48, 67]. Although these techniques
are only used over known concepts, often requiring expert domain knowledge to
define, the insights generated by these techniques are not only scientifically
interesting, but have begun to yield actionable insights on how to employ and
improve models. For example, Geva et al. [21] found that multilayer
perceptrons (MLPs) in transformer layers act as key-value memories, and Meng
et al. [44] leveraged this understanding to manipulate model behavior in a
controlled manner.

We demonstrate how these ideas leveraged in NLP can be applied to
reinforcement learning, testing the capabilities and limitations of our
models. Specifically, we leverage the above-described analysis
techniques—probing classifiers and behavioral tests—to interpret AlphaZero’s
behavior at a conceptual level. We use probing classifiers to determine if
reinforcement-learning agents encode tactical and strategic conceptual
information. However, probing performance alone is insufficient: Information
may be encoded but not used [38]. To address this issue, we also use
behavioral tests, which evaluate an agent’s decisions in a situation tailored
to require the understanding of a specific concept.

(a) An example winning board for black, which connects the black edges
together.

(b) Short- vs Long-term concepts. Left: If black plays A or B, black
immediately wins; the board concept containing A and B, bridge (See 2a), is
relevant in the short-term. Right: A and B can help black win only in the
long-term.

Figure 1: To win in Hex, a player must use their pieces to form a connecting
chain between the edges matching their color (a). Hex boards can be of varying
size; we evaluate AlphaZero on a 9x9 board. In our work, we make a distinction
between short- and long-term concepts (b).

Given these concept-level evaluation methods, we do an in-depth study of
AlphaZero (AZ) trained to play Hex. Hex is a board game similar to Go (§2),
but provides an opportune test bed for analysis: the game is complex, yet has
perfect-play baselines for smaller board sizes. Moreover, concepts and
strategies within Hex have been studied by the Hex-playing community, making
Hex a rich vector for study. Furthermore, the clear behavioral expectations in
Hex make it easier to interpret and guide future work.111Again drawing
inspiration from work in NLP, Linzen et al. [36] focused on one syntactic
phenomenon in simple current neural networks, and the basic insight and
methods enabled later studies to make broader claims about learning linguistic
structure in many types of models [27, 67, 68]. In our work, we probe for
concepts that are taught to new players of Hex, like the bridge (Fig. 2a), and
test that the model is able to use them to win games. We investigate how
concepts are represented within AZ, when concepts are learned during training,
and where concepts are represented within AZ’s neural network.

Overall, our findings suggest that there are some regular dynamics to how AZ
learns concepts with the game of Hex, and generate interesting predictions
about how AZ behaves in general, which could be tested in other games. (In
fact, concurrent work on chess [43] and Go [65] already begin to provide
convergent evidence that some trends we see here generalize elsewhere.) We
introduce a novel way of analyzing deep RL models on which such subsequent
work can easily build.

In summary, our main contributions are:

  1. 1.

We adapt several evaluation techniques from NLP to the RL setting, and
illustrate how evaluations other than task performance can be used to provide
a more complete picture of a model’s strengths and weaknesses.

  2. 2.

We analyze a top-performing model from Jones [31], and find that (1) short-
term end-game concepts are best represented in the final layers of the
network, whereas long-term concepts are best represented in the middle layers
of the network; (2) concepts appear to originate with MCTS—with MCTS
overriding the deep learning policy prediction early in training—but later in
training these concepts are incorporated directly into the model’s network.

Figure 2:  Hex templates exemplifying game concepts. Concepts within the game
of Hex are templates on the board formed by a player’s pieces with known
strategic and tactical implications. Positive concepts provide the player with
the concept with multiple ways to connect the pieces within the concept
together, despite possible attacks from the opponent. An example of such a
concept is the bridge (a). If white plays move 1, black can connect the two
pieces of the bridge by playing move 2. Negative concepts change the strategic
value of specific open spots of the board, such that the opponent is
disincentivized to play those open spots, such as move A in (i). Each concept
is further described in our Supplementary Material. Arrows indicate that the
piece is connected to the opposite side of the board; the lines show the
bridge concept within the other concepts.

##  2 Concepts in Hex

We study AlphaZero (AZ) agents trained to play Hex [18], a game where two
players take turns filling cells until one player builds a chain across the
board. Hex has well-studied rules, reasonable computational costs, and it can
be evaluated against perfect play, making it an ideal experimental vehicle for
model probing. Unlike Go, there are no captures; once a cell is filled with a
piece, the pieces stays there for the remainder of the game. For example, in
Fig. 1(a), white must connect pieces from left to right (marked on the edges),
and black top to bottom. Hex cannot end in a tie [16], and given perfect play,
black, the first player, will win [18]. 222Hex is often played with a “swap
rule” that makes the game more even between black and white. See Jones [31],
whose implementation we use, for further discussion on the swap rule. Jones
did not include it to simplify the game implementation.

In Hex, certain templates – patterns of cells – have been recognized as
useful. Because building up a chain from one side of the board to the other is
easily thwarted, a key part of learning how to play Hex is recognizing when it
is possible to connect groups of pieces together. We consider these templates
to be concepts within the game. Concepts in Hex have different move
implications depending on the condition of the board. We discuss two
conditions, long- and short-term, in detail and provide additional discussion
of conditions in the Supplementary Material.

While the properties of concepts are debated [40], here, in a board game
setting, we consider a concept to be a useful template that generalizes across
board configurations. For our purposes, “understanding” a concept amounts to
recognizing it and leveraging its implications during gameplay (§2.2).

###  2.1 Long-term vs short-term Concepts

We define a concept in Hex to be short-term if its use is sufficient to win
the game. Concepts are typically short-term when there exists a connection
between the concept and the player’s board edges. For example, in Fig. 1(b),
moves A and B belong to the bridge concept (see Fig. 2a). In the left board,
the board edges are connected, and all that is required for black to win is to
play moves A or B. Conversely, long-term concepts are insufficient to winning
the game if immediately used. In the right board of Fig. 1(b), playing the
bridge concept is useful but insufficient for winning immediately; the concept
is not connected to the edges of the board. Empirically, we find that whether
the concept is short- or long-term has a significant impact on AlphaZero’s
representations (Fig. 4).

###  2.2 Concept Taxonomy

From Seymour [58] and King [34], we identify the nine concepts that we use in
our analysis, summarized in Fig. 2. These concepts fall into four categories,
as described below.

#### Positive Concepts

With the goal of Hex being to build a chain across the board, it is helpful to
recognize when cells are virtually connected, that is, even in response to
perfect adversarial play, the cells are guaranteed to connect [24, 50]. There
are a few different types of positive concepts. All the positive concepts
favor the player that owns the concept on the board.

Internal concepts are templates that appear within the interior of the board.
The bridge (Fig. 2(a)) is the simplest such concept. The larger internal
templates – crescent, trapezoid, span (Fig. 2(b,c,d)) – provide several
possibilities to connect a player’s pieces. Edge concepts concern connecting a
single cell to a given edge. Ladders in Hex are similar to ladders in Go.
There are two different ladder concepts, bottleneck (g) and escapes (h). A
bottleneck favors the defender, because the attacking player cannot break
through. An escape, however, allows the attacker to break through.

#### Negative Concepts

Negative concepts do not inform one on which actions to play, but rather,
which actions not to play. Dead cells (Fig. 2(i)) cannot impact the outcome of
the game regardless of the color with which they are filled. While it is in
general difficult to compute if a cell is dead [7], there are some known
templates where it is easier to deduce. If a player can make a cell dead, that
cell is captured. Both captured and dead cells should not be filled.

##  3 Designing Probing Tasks and Behavioral Tests for Hex

To understand the concepts encoded within AlphaZero, we probe its internal
representations; to evaluate if these concepts are used by AZ, we test its
behavior on tailored board configurations. By evaluating AZ across training
checkpoints, and across neural network layers, we can build up an
understanding of how and where the model recognizes these concepts.
Specifically, we evaluate the top-performing agent trained by Jones [31]
across 21 training checkpoints. We additionally evaluate other publicly
available agents [31] from that differ by width and depth and we report on
those results in the Supplementary Material. Code from Jones is available
under the MIT License.

###  3.1 Reproducibility

Our code and results are publicly available [39]. Furthermore, we release
example images of boards created for our probing classifiers and videos of the
behavioral tests. The code, results and examples can be found at
https://bit.ly/alphatology. Our repository is also available on GitHub at
https://github.com/jzf2101/alphatology. We report hyperparameters in the
Supplementary Material. All error bars presented in plots are one standard
deviation above and below the mean. We used NVIDIA GeForce RTX 3090. The total
compute across all experiments was about 24 GPU hours. We present a breakdown
of the compute in the Supplementary Materials.

###  3.2 Representational Probing

Model probing measures how well a model’s learned representations encode a
known concept [1]. To make a model probe, one labels examples, such as Hex
boards, with the presence or absence of a concept, such as the bridge concept
(see Figure Fig. 2). Next, one collects the model’s activations for each
example, and then trains a linear classifier (the _probe_) to predict the
presence of the concept based on activations. The linear classifier’s test
performance is used to interpret how well the original model encoded the
concept.

We train a linear probe for each concept over each layer of AZ’s network body.
We follow a procedure similar to Tenney et al. [62]: $H^{(0)}$ is the state of
the board that is used as input into AZ. For each board, we record the label
$y_{k}$ to indicate the presence or absence of the concept $k$ on the board.
$H^{(l)},$ $l\in 1..L$ is the activation of the layer $l$ of AZ’s network
body.333We never use activations from multiple layers at once, layer weights ,
nor AZ’s value/policy outputs. We then train linear classifiers
$\mathcal{P}^{(l)},l\in 0..L$ per layer to predict the presence vs. absence of
a concept in a given board. These classifiers are our concept probes.

It is important to compare probing results against a baseline. We follow
Hewitt and Liang [25]’s procedure to measure concept selectivity, the delta
between probing accuracy over a concept and random control. To form the random
control, for each board $H^{(0)}$ in the probing dataset, we map each cell in
that board to a random cell in a consistent manner to form the transposed
board, ${H}^{(0)}_{s}$. In this way, the same information is encoded in the
original boards, but we expect the shuffled boards to be meaningless in Hex.
Next, we train a set of linear probes ${\mathcal{P}}^{(l)}_{s},l\in 0..L$ over
the control boards ${H}^{(0)}_{s}$ to predict $y$. Now, finally, we can
compute the concept selectivity by finding the delta in accuracy between
${\mathcal{P}}^{(l)}_{s}$ and $\mathcal{P}^{(l)}$. Concept selectivity is the
performance of a probe beyond the performance of a probe on a control task,
adding context for interpreting the results.

#### Implementation Details.

Each concept is defined by a set of boards with vs. without that concept. We
train and evaluate probing classifiers over AlphaZero’s encoding of these
boards. To generate a set of ($N=2500$) boards for each concept, we translate
the minimal templates across an empty board. Then, we add random enemy pieces
to the board. Negative instances of a given concept match the statistics of
the positive examples, except that the pieces pertaining to the concept
template are randomly moved across the board. This constitutes the long-term
version of a concept. To form the short-term version of a concept, we connect
the template to the edges of the board.

###  3.3 Behavioral Tests

Where model probing asks if concepts are represented within the model,
behavioral tests asks if the model knows how to use the concept in gameplay.
To interpret the behavioral tests, they must have clear behavioral
expectations. We construct our behavioral tests for positive concepts (§2) to
be forced: If AZ understands the concept and plays the expected moves, AZ will
win and pass the test; otherwise, AZ will lose the game and fail the test. For
negative concepts (§2), we have clear behavioral expectations. Dead and
captured cells should never be filled. Thus, the behavioral test for negative
cells checks that during a selfplay continuation of a board containing a dead
(or captured) cell, the agent does not fill that cell.

Success on these behavioral tests are necessary but are alone insufficient to
establish that the model has the concept. A negative result means that AZ is
unable to use the concept, whereas a positive result means that AZ can use the
concept to win games in forced situations. This approach has been used to test
large language models. Specifically, we are inspired by Ettingers [14, 48] who
uses simplified language to ask if the model is able to use a concept like
negation or syntax when needed. If the model still fails to use the concept,
then this good evidence that the concept is not represented.

#### Implementation Details.

For each concept, we create behavioral tests that comprise a board, forcing
moves, and expected moves. (For the dead and captured cells there are no
forcing or expected moves, only the moves to avoid). We discuss the motivation
for our behavioral test setup and its connection to AlphaZero’s style of
gameplay in the Supplementary Material. By way of example, see Fig. 3. To
generate a set ($N=100$ samples) of boards, we translate the templates to a
sampled valid board position. We then connect the concept to the edges of the
board. Finally, we add connections for the defending player up to the region
of the concept such that if the attacking player fails to complete the
behavioral test, the other play would win. Finally, we add the appropriate
number of random pieces such that the board position is valid. The behavioral
tests determine when/if AZ learns to navigate these situations correctly.

Figure 3: Creating behavioral tests from concept templates. To evaluate
AlphaZero’s ability to utilize concepts during game play, we build synthetic
boards where utilizing the strategic advantages of the given concepts allows
the player to win the game. In this example, we demonstrate the building of a
behavioral test for the bridge concept (Figure 2a). The minimal template (a)
is translated to a random position on the board (b). Then both players’ pieces
are connected to their respective edges they need to utilize to win the game
(c). Finally, the minimum number of noise pieces necessary to form a valid
board are added (d). Cells A, B are used to define the behavioral test. If
white plays A, black must play B to win the game. (Only half a 5x5 board is
shown for space.)

###  3.4 Considerations

Limitations. While we find a consistent relationship between the probing and
behavioral tests in Section 4.3, we do not run a counterfactual study. For
example, we do not show that mistakes in recognizing a concept on a given
board, lead to mistakes in using that concept. Studying the causal mechanisms
of how the concept representations detected by model probing impact downstream
model behavior is a rich direction for future work.

In our behavioral tests, all the concepts we tested share the property that
they are about to be connected. (They share this property because we connect
the concept so that the behavioral expectations are clear, Fig. 3.) All the
concepts being tested could be interpreted as “interrupt the opponent’s soon-
to-be-winning chain.” However, the behavioral tests of different concepts
report different performance levels (though admittedly similar), suggesting
that the differences of concept are still relevant. Furthermore, the agent
would still have had to use the targeted concepts as a constituent of
“interrupt the opponent’s soon-to-be-winning chain.”

Societal Impact. Deep reinforcement learning models such as AZ are not
interpretable [13], and yet are being applied to impactful, real world domains
[22, 54, 19, 6, 32, 45]. In this work, we start to analyze how AZ comes to its
decisions. Understanding a model’s decisions is critical for accountability,
but it does open the door to some avenues for exploitation. If it is known
that a given algorithm does not reason about a concept well, this could be
leveraged for ill. However, this risk only strengthens the argument for
uncovering such problems and fixing them to prevent such risks.

(a) AlphaZero successfully encodes long-term and short-term concepts. The
selectivity [25], indicated by the colored bars, are the accuracy of a probe
trained to identify a concept based on network activations, minus the accuracy
of a selectivity baseline. The selectivity baseline randomly maps board pieces
so that the new boards do not contain structures known to be relevant to Hex.
We report selectivity based on the layer with the highest test accuracy.

(b) Long-term concepts are best represented in the middle layers of the
network whereas short-term concepts are best represented in the final layers
of the network. Each distribution shows the layer in which probes had the
highest accuracies.

Figure 4: Probing performance on long- and short-term concepts.

##  4 Results

To understand which concepts AlphaZero (AZ) learns, we examine if its neural
network activations encode the concepts (probing tests) and if AZ can use the
concepts to win games (behavioral tests).

###  4.1 AlphaZero Recognizes and Uses Concepts

AZ successfully encodes short-term concepts, with high selectivity scores
(Fig. 4(a)). The long-term concept scores are also learned, but with slightly
lower scores. By the end of training AZ is able to use all the positive
concepts to win games (Fig. 5a).

AZ improves on the behavioral tests 50% of the way through training.
Unsurprisingly, the MCTS passing rates increase before the policy network
passing rates (Fig. 5), though it need not have been the case. It is possible
for AZ to represent the concepts before MCTS used them – possibly via the
signal through the value prediction.

Interestingly, the relative magnitude of the correct action logits initially
increases earlier. To specify how we measure this, we need to cover two
definitions. First, the logits are the outputs of the modules (MCTS or policy
prediction head). Second, we use a Z-score, which reports the number of
standard deviations higher a given value is than the mean of the population.
In our case, the blue line in Fig. 5a, reports the proportion of cases where
the Z-score of the correct action is greater than 1. So, this value captures
when the correct action becomes more likely throughout training.

The trend in Fig. 5a suggests “pre-conceptual” information is learned, and
coalesces (for bridge) 60% of the way through training into an actionable
understanding of the concept. (In Section 4.4, we investigate further and find
that this “pre-conceptual” information is not board structure.)

Figure 5: (a): AlphaZero learns to use positive concepts. At each checkpoint,
we present AlphaZero (AZ) with a set of example boards that test its ability
to utilize each concept. MCTS and the policy network both select actions that
pass our behavioral tests with increasing frequency throughout training. We
additionally report the rate at which the logit score of the action that
passes our behavioral test is one standard deviation above the mean logit
score (z score $>1$).
(b): AZ does not fully use the negative concepts. Passed denotes the rate at
which AZ avoids the negative concept throughout selfplay rollouts. So, at the
end of training, AZ plays moves in 25% of our behavioral tests that will not
impact the game [7].

AZ also improves behaviorally upon negative concepts. However, it does not
reach a perfect passing rate (Fig. 5b). The probing performance for the
negative concepts, shown in Fig. 4(a), is also lower than for other concepts.
This aligns with evidence that AZ wastes moves at the end of the game. This
highlights a weakness in AlphaZero and a risk: Some concepts may be “provable”
and useful to people, but “deemed” less important by AZ – an agent that plays
remarkably well. We will have to consider this dynamic as people begin to try
to learn concepts from machines.

###  4.2 Long-term and Short-term Concepts are Best Represented in Different
Layers

Fig. 4(b) highlight that short and long-term concepts are best represented at
different layers. Long-term concepts, by the end of training, are best
represented in the middle layers of the network. Short-term concepts,
throughout training, are best represented in the upper layers of the network.
We have two conjectures, which are not mutually exclusive, for why this may be
the case. We leave the verification/refutation to future work. (1) Short-term
concepts generally require more global information and so require more depth;
(2) Short-term concepts factor directly into action selection and so are more
proximal to the final task-specific layer of the network.

We find that two and four layer networks demonstrate the same pattern; see our
Supplementary Material. Lastly, McGrath et al. [43]’s results in chess are
similar, although they did not directly study short- vs long-term concepts.
The following is our interpretation of the results shown in their plots: “in
check” (short-term) was best represented higher in the network and “material
imbalance” (long-term) was largely represented lower in the network.
(Informally categorized, the short-term concepts (McGrath et al.’s Fig.
2)[c,e,f] are better represented in higher layers than are the long-term
concepts (Fig. 2)[a,g,h,i].)

###  4.3 Improvements in Behavioral Tests Occur Before Improvements in Probing
Accuracy

Where the network body processes board configurations, MCTS directly governs
the decision-making procecess. In principle, either module could be the first
to discover the game concepts. For instance, the network body could start to
represent concepts via updates to the value function, later enabling MCTS to
successfully navigate the concept templates. We find that the first
improvements in behavioral tests precede the first improvements in probing
accuracy (Fig. 6), where we consider first improvement as the epoch with a 5%
increase over the baseline value. MCTS seems to discover concepts, especially
the internal concepts. Then, as the policy network is trained to match the
MCTS logits, the concept representation is absorbed into the network.

We find evidence that the structure of the board is first learned at about the
same time other concepts are learned. In Section 4.4, we discuss how we probe
for this structure, determining if AZ encodes the relative distance between
all cells on the board. The last column of Fig. 6, labeled structural, shows
that improvements on this concept occur at a similar time as to other
concepts. This suggests that AZ does not learn concepts according to an
obvious order or curriculum, but rather, concepts of differing levels of
complexity develop in parallel.

The results shown in Fig. 6 outline the relationship between the concepts as
they are learned during training, but does not establish a causal relationship
between how the concept representation (as detected by the probing models)
impacts how the model uses that concept.

Figure 6: Improvements in behavioral tests occur before improvements in
probing accuracy. Each point marks the mean checkpoint in training that AZ
started to learn (or converge upon) the behavioral (or probing) test. Error
bars are standard deviation across random seeds and short- vs long-term. We
group the concepts as in Fig. 2. While behavioral tests start to improve
before the probing, they both converge near the end of training. Exception:
the ladder escape and bottleneck concepts (Fig. 2h) are easy for the probes to
detect, consequently having low selectivity (Fig. 4(a)), perhaps because they
occur along the edges of the board, and as a result, have fewer possible
configurations. The concept structural, (§4.4), which evaluates how well AZ’s
cell embeddings capture Hex’s neighborhood structure, is learned and converges
in a similar time frame as the probing task.

###  4.4 AlphaZero’s Cell Embeddings Capture the Structure of the Board

Understanding Hex’s concepts requires understanding the board’s structure,
that is, which cells connect to which other cells. AlphaZero (AZ), with its
feed forward network architecture, does not a priori represent this structure.
Fig. 5 suggests that some information is learned before the model is able to
use the concepts. A possibility is that AZ spends the initial portions of
training building up a representation of the board. However, we find no
evidence that the neighborhood structure is learned in the initial stages of
training, rather, it appears to be learned only after the first improvements
in behavioral tests (Fig. 6).

Figure 7: Implicit board structure. Arrows mark the learned nearest neighbors
of each cell.

To study if Hex’s board is represented in AZ, we hypothesized that the
structure of Hex’s board is implicitly learned by AZ’s first layer. For each
Hex cell, we extract a cell embedding from the first layer of AZ.444AZ’s first
layer takes a flattened 1-hot encoding of the board and matrix multiplies it
with a weight matrix. The embedding of each cell can be spliced out of that
weight matrix. We only extract the cell embeddings for the current player.
This constitutes a structural probe [26]. A structural probe tests the
relationship between neural network activations (or weights). Next, we compute
the dot-products between each cell embedding. The dot-product score between
ground-truth neighbors increases throughout AZ’s training.

The nearest-neighbors (according to the dot-product scores) nearly match the
ground-truth by the 15th of 20 checkpoints, and eventually match the ground-
truth before deviating slightly. We evaluate how well the dot product scores
align with the ground-truth cell distances via a ranking metric, Normalized
Discounted Cumulative Gain (NDCG). The NDCG first improves about 50% of the
way through training as highlighted in Fig. 6. Details on the learned
structure are in the Supplementary Material.

##  5 Related Work

#### Applying MCTS and Deep Learning to the Game of Hex.

Jones [31], whose trained agents we use, studied scaling laws between various
parameters, finding a mathematical relationship between compute, board size,
and agent performance. This type of result can help others make informed
tradeoffs when training board-game-playing agents. Where Gao et al. [17] and
Takada et al. [61] both use value functions in concert with MCTS to play Hex,
MoHex [28] combines programmatic connection detection, pattern matching, and
MCTS, attacking Hex for the 9$\times$9 grid.

#### AlphaZero, anecdotally, uses concepts, but only achieves a partial
mastery.

Domain experts have observed that AlphaZero [59] and related agents that
combine Monte Carlo tree search [8] with deep reinforcement learning use
identifiable concepts within board games. Michael Redmond identifies several
common gameplay concepts demonstrated by AlphaZero [12] in AlphaZero’s Go
matches against Lee Sedol. Silver et al. [60] noted that common human-played
corner moves in Go—joseki—were used by AlphaZero during self-play training
before being abandoned, presumably as other more effective moves were found.
Additional analysis provided by Tian et al. [64] note that Elf OpenGo only
partially mastered ladder sequences within the game. Chess commentator Antonio
Radić [55] detailed how AlphaZero used zugzwang [69] in the course of
defeating Stockfish [56]. Experts have already incorporated some of
AlphaZero’s innovations into their play [46, 57].

#### Probing neural networks for human concepts.

A range of linguistic concepts have been detected in NLP models using probing
models [9, 52, 41, 63, 26]. For example, Tenney et al. [63], with probing
models, found that BERT appears to best encode linguistic concepts in the same
order those concepts might be processed by the typical NLP pipeline. There has
been some discussion on what good probing accuracy signifies. Hewitt and Liang
[25] calls for baseline controls, and to measure only the gain in accuracy
compared to these baselines. Voita and Titov [66] found that measures beyond
accuracy, namely Minimum Description Length (MDL)—which is used to measure how
easy it to detect a given concept—provided more stable results.

#### Understanding reinforcement-learning agents trained to play board games.

Sadler and Regan [57] cover how some particulars from AZ’s gameplay has
impacted high-level chess. Concurrent to our work, McGrath et al. [43] also
looked at how AZ acquires game knowledge (which we term _concepts_) in chess.
Using similar probing techniques, and the original (and larger) AZ, they find
that it learns to encode many of the prototypical chess concepts. Related, but
not focused on model understanding per se, Jhamtani et al. [29] collected an
annotated set of chess games. This type of resource is similar to what is used
by McGrath et al. [43] for their probing task. In our work, we focus on
controlled programmatic generation of boards with (and without) concepts
present. While these board instances may not occur during selfplay, the human
annotated games are also off-distribution with respect to AZ. Beyond finding
similar results in a different game (Hex vs chess), we also leveraged
behavioral tests, tying the concept representation to agent behavior.

##  6 Discussion

Our analyses suggest that AlphaZero (AZ) learned to both represent and use
concepts that humans consider important when playing Hex. However, we found
that AZ is sometimes either blind or agnostic to a winning move. This had
interesting ramifications. For instance, the negative concepts, especially
dead cells, were not as well-encoded or used compared to other concepts. This
may be because AZ has no “qualms” with playing wasted moves, like dead cells,
if doing so doesn’t change the outcome of the game.

A layerwise analysis showed that the same concept is represented most strongly
in different layers, depending on its context: short-term concepts that inform
actions at the end of the game are encoded in the upper layers of the model,
whereas long-term concepts are absorbed deeper into the network. This
absorption mirrors how AZ’s policy head was trained to predict the policy
outputs of MCTS.

Combining both representational and behavioral approaches to analyze
reinforcement-learning agents allows for a fuller understanding of how agents
learn. Studying the representations of concepts allows us to ask (and answer)
a rich set of questions about where those concepts reside. Studying the
behavior of the model with respect to a given concept tests that this
representation can be translated into action. Behavioral tests can also
determine whether the model may be using known heuristics. They are
complementary approaches. In future work, applying a causal approach to the
study of agents’ policies will further illustrate how well these agents
understand these concepts.

## Acknowledgements

We would like to thank the reviewers across different iterations of this work;
they helped us clarify our work and findings. This research was conducted
using computational resources and services at the Center for Computation and
Visualization, Brown University. Also, special thanks to Matthew Seymour for
his Hex drawing software: http://www.mseymour.ca/hex_draw/hexdraw.html.
Charles Lovering was supported in part by the DARPA GAILA program. This work
received support from the ONR PERISCOPE MURI award N00014-17-1-2699.

## References

  * Alain and Bengio [2017] G. Alain and Y. Bengio.  Understanding intermediate layers using linear classifier probes.  _ICLR Workshops_ , 2017.
  * Arneson et al. [2018] B. Arneson, P. Henderson, J. Pawlewicz, A. Huang, K. Young, and C. Gao.  Benzene, 2018.  https://github.com/cgao3/benzene-vanilla-cmake/blob/d450c01eb38803b1766ed9abea51568c4672f46b/src/hex/EndgameUtil.cpp.
  * Badgeley et al. [2019] M. A. Badgeley, J. R. Zech, L. Oakden-Rayner, B. S. Glicksberg, M. Liu, W. Gale, M. V. McConnell, B. Percha, T. M. Snyder, and J. T. Dudley.  Deep learning predicts hip fracture using confounding patient and healthcare variables.  _NPJ Digit Med_ , 2:31, Apr. 2019.
  * Belinkov [2022] Y. Belinkov.  Probing classifiers: Promises, shortcomings, and advances.  _Computational Linguistics_ , 48(1):207–219, 2022\.
  * Belinkov et al. [2020] Y. Belinkov, S. Gehrmann, and E. Pavlick.  Interpretability and analysis in neural nlp.  In _Proceedings of the 58th annual meeting of the association for computational linguistics: tutorial abstracts_ , pages 1–5, 2020.
  * Bellemare et al. [2020] M. G. Bellemare, S. Candido, P. S. Castro, J. Gong, M. C. Machado, S. Moitra, S. S. Ponda, and Z. Wang.  Autonomous navigation of stratospheric balloons using reinforcement learning.  _Nature_ , 588(7836):77–82, Dec. 2020.
  * Björnsson et al. [2006] Y. Björnsson, R. Hayward, M. Johanson, and J. van Rijswijck.  Dead cell analysis in Hex and the Shannon game.  In _Graph Theory in Paris_ , pages 45–59. Springer, 2006.
  * Brügmann [1993] B. Brügmann.  Monte Carlo go.  Technical report, Max Planck Institute of Physics, 1993.
  * Conneau et al. [2018] A. Conneau, G. Kruszewski, G. Lample, L. Barrault, and M. Baroni.  What you can cram into a single $&!#* vector: Probing sentence embeddings for linguistic properties.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 2126–2136, Melbourne, Australia, July 2018. Association for Computational Linguistics.  doi: 10.18653/v1/P18-1198.  URL https://www.aclweb.org/anthology/P18-1198.
  * Cooper et al. [2021] A. F. Cooper, Y. Lu, J. Forde, and others.  Hyperparameter optimization is deceiving us, and how to stop it.  _Adv. Neural Inf. Process. Syst._ , 2021.
  * Cooper et al. [2022] A. F. Cooper, E. Moss, B. Laufer, and others.  Accountability in an algorithmic society: relationality, responsibility, and robustness in machine learning.  _2022 ACM Conference on_ , 2022.
  * DeepMind [2016] DeepMind.  Match 1—Google DeepMind challenge match: Lee Sedol vs AlphaGo, Mar. 2016.
  * Doshi-Velez and Kim [2017] F. Doshi-Velez and B. Kim.  Towards a rigorous science of interpretable machine learning.  _arXiv_ , Feb. 2017.
  * Ettinger [2020] A. Ettinger.  What bert is not: Lessons from a new suite of psycholinguistic diagnostics for language models.  _Transactions of the Association for Computational Linguistics_ , 8:34–48, 2020.
  * Forde et al. [2021] J. Z. Forde, A. F. Cooper, K. Kwegyir-Aggrey, and others.  Model selection’s disparate impact in Real-World deep learning applications.  _arXiv preprint arXiv_ , 2021.
  * Gale [1979] D. Gale.  The game of hex and the brouwer Fixed-Point theorem.  _Am. Math. Mon._ , 86(10):818–827, Dec. 1979\.
  * Gao et al. [2017] C. Gao, R. Hayward, and M. Müller.  Move prediction using deep convolutional neural networks in hex.  _IEEE Transactions on Games_ , 10(4):336–343, 2017.
  * Gardner [1961] M. Gardner.  _The 2nd Scientific American Book of Mathematical Puzzles and Diversions_.  Simon & Schuster, 1961.
  * Gauci et al. [2018] J. Gauci, E. Conti, Y. Liang, K. Virochsiri, Y. He, Z. Kaden, V. Narayanan, X. Ye, Z. Chen, and S. Fujimoto.  Horizon: Facebook’s open source applied reinforcement learning platform.  Nov. 2018.
  * Gauthier et al. [2020] J. Gauthier, J. Hu, E. Wilcox, P. Qian, and R. P. Levy.  Syntaxgym: An online platform for targeted evaluation of language models.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , page 70–76, 2020.
  * Geva et al. [2020] M. Geva, R. Schuster, J. Berant, and O. Levy.  Transformer feed-forward layers are key-value memories.  _arXiv preprint arXiv:2012.14913_ , 2020.
  * Gu et al. [2017] S. Gu, E. Holly, T. Lillicrap, and S. Levine.  Deep reinforcement learning for robotic manipulation with asynchronous off-policy updates.  In _2017 IEEE International Conference on Robotics and Automation (ICRA)_ , pages 3389–3396. ieeexplore.ieee.org, May 2017.
  * Gururangan et al. [2018] S. Gururangan, S. Swayamdipta, O. Levy, R. Schwartz, S. R. Bowman, and N. A. Smith.  Annotation artifacts in natural language inference data.  _arXiv preprint arXiv:1803.02324_ , 2018.
  * Hayward et al. [2005] R. Hayward, Y. Björnsson, M. Johanson, M. Kan, N. Po, and J. Van Rijswijck.  Solving 7$\times$ 7 hex with domination, fill-in, and virtual connections.  _Theoretical Computer Science_ , 349(2):123–139, 2005.
  * Hewitt and Liang [2019] J. Hewitt and P. Liang.  Designing and interpreting probes with control tasks.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 2733–2743, Hong Kong, China, Nov. 2019. Association for Computational Linguistics.  doi: 10.18653/v1/D19-1275.  URL https://www.aclweb.org/anthology/D19-1275.
  * Hewitt and Manning [2019] J. Hewitt and C. D. Manning.  A structural probe for finding syntax in word representations.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 4129–4138, Minneapolis, Minnesota, June 2019. Association for Computational Linguistics.  doi: 10.18653/v1/N19-1419.  URL https://www.aclweb.org/anthology/N19-1419.
  * [27] J. Hu, J. Gauthier, P. Qian, E. Wilcox, and R. Levy.  A systematic assessment of syntactic generalization in neural language models.  In _Proc. of NAACL_.  URL https://www.aclweb.org/anthology/2020.acl-main.158.
  * Huang et al. [2014] S.-C. Huang, B. Arneson, R. B. Hayward, M. Müller, and J. Pawlewicz.  MoHex 2.0: A Pattern-Based MCTS hex player.  In _Computers and Games_ , pages 60–71. Springer International Publishing, 2014.
  * Jhamtani et al. [2018] H. Jhamtani, V. Gangal, E. Hovy, G. Neubig, and T. Berg-Kirkpatrick.  Learning to generate move-by-move commentary for chess games from large-scale social forum data.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1661–1671, 2018\.
  * Jones [2021a] A. Jones.  LICENSE at master · andyljones/boardlaw, 2021a.
  * Jones [2021b] A. L. Jones.  Scaling scaling laws with board games.  _arXiv preprint arXiv:2104.03113_ , 2021b.
  * Jumper et al. [2021] J. Jumper, R. Evans, A. Pritzel, T. Green, M. Figurnov, O. Ronneberger, K. Tunyasuvunakool, R. Bates, A. Žídek, A. Potapenko, et al.  Highly accurate protein structure prediction with alphafold.  _Nature_ , 596(7873):583–589, 2021.
  * Kim and Linzen [2019] N. Kim and T. Linzen.  Compositionality as directional consistency in sequential neural networks.  In _Workshop on Context and Compositionality in Biological and Artificial Neural Systems_ , 2019.
  * King [2004] D. King.  Hall of hexagons.  https://www.drking.org.uk/hexagons/index.html, 2004.  Accessed: 2021-11-12.
  * Lake and Baroni [2018] B. Lake and M. Baroni.  Generalization without systematicity: On the compositional skills of sequence-to-sequence recurrent networks.  In _Proc. of ICML_ , 2018.  URL https://arxiv.org/abs/1711.00350.
  * Linzen et al. [2016a] T. Linzen, E. Dupoux, and Y. Goldberg.  Assessing the ability of LSTMs to learn syntax-sensitive dependencies.  _Transactions of the Association for Computational Linguistics_ , 4:521–535, 2016a.  doi: 10.1162/tacl_a_00115.  URL https://www.aclweb.org/anthology/Q16-1037.
  * Linzen et al. [2016b] T. Linzen, E. Dupoux, and Y. Goldberg.  Assessing the Ability of LSTMs to Learn Syntax-Sensitive Dependencies.  _Transactions of the Association for Computational Linguistics_ , 4:521–535, 2016b.  URL http://aclweb.org/anthology/Q16-1037.
  * Lovering et al. [2021] C. Lovering, R. Jha, T. Linzen, and E. Pavlick.  Predicting inductive biases of pre-trained models, 2021.
  * Lucic et al. [2022] A. Lucic, M. Bleeker, S. Bhargav, J. Forde, K. Sinha, J. Dodge, S. Luccioni, and R. Stojnic.  Towards reproducible machine learning research in natural language processing.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics: Tutorial Abstracts_ , pages 7–11, Dublin, Ireland, May 2022. Association for Computational Linguistics.
  * Margolis et al. [1999] E. Margolis, S. Laurence, et al.  _Concepts: core readings_.  Mit Press, 1999.
  * Marvin and Linzen [2018] R. Marvin and T. Linzen.  Targeted syntactic evaluation of language models.  _arXiv preprint arXiv:1808.09031_ , 2018.
  * McCoy et al. [2020] R. T. McCoy, E. Pavlick, and T. Linzen.  Right for the wrong reasons: Diagnosing syntactic heuristics in natural language inference.  In _57th Annual Meeting of the Association for Computational Linguistics, ACL 2019_ , pages 3428–3448. Association for Computational Linguistics (ACL), 2020.
  * McGrath et al. [2021] T. McGrath, A. Kapishnikov, N. Tomašev, A. Pearce, D. Hassabis, B. Kim, U. Paquet, and V. Kramnik.  Acquisition of chess knowledge in alphazero.  _arXiv preprint arXiv:2111.09259_ , 2021.
  * Meng et al. [2022] K. Meng, D. Bau, A. Andonian, and Y. Belinkov.  Locating and editing factual knowledge in gpt.  _arXiv preprint arXiv:2202.05262_ , 2022.
  * Mirhoseini et al. [2021] A. Mirhoseini, A. Goldie, M. Yazgan, J. W. Jiang, E. Songhori, S. Wang, Y.-J. Lee, E. Johnson, O. Pathak, A. Nazi, J. Pak, A. Tong, K. Srinivasa, W. Hang, E. Tuncer, Q. V. Le, J. Laudon, R. Ho, R. Carpenter, and J. Dean.  A graph placement methodology for fast chip design.  _Nature_ , 594(7862):207–212, June 2021.
  * Nielsen [2019] P. H. Nielsen.  The exciting impact of a game changer: When Magnus met AlphaZero.  _New In Chess_ , 2019.
  * Ormerod [2016] D. Ormerod.  _AlphaGo shows its true strength in 3rd victory against Lee Sedol_.  2016\.
  * Pandia and Ettinger [2021] L. Pandia and A. Ettinger.  Sorting through the noise: Testing robustness of information processing in pre-trained language models.  In _EMNLP (1)_ , 2021.
  * Pawlewicz and Hayward [2014] J. Pawlewicz and R. B. Hayward.  Scalable parallel DFPN search.  In _Computers and Games_ , pages 138–150. Springer International Publishing, 2014.
  * Pawlewicz et al. [2014] J. Pawlewicz, R. Hayward, P. Henderson, and B. Arneson.  Stronger virtual connections in hex.  _IEEE Transactions on Computational Intelligence and AI in Games_ , 7(2):156–166, 2014.
  * Pawlewicz et al. [2015] J. Pawlewicz, R. Hayward, P. Henderson, and B. Arneson.  Stronger virtual connections in hex.  _IEEE Trans. Comput. Intell. AI Games_ , 7(2):156–166, June 2015.
  * Poliak et al. [2018a] A. Poliak, A. Haldar, R. Rudinger, J. E. Hu, E. Pavlick, A. S. White, and B. Van Durme.  Collecting diverse natural language inference problems for sentence representation evaluation.  _arXiv preprint arXiv:1804.08207_ , 2018a.
  * Poliak et al. [2018b] A. Poliak, J. Naradowsky, A. Haldar, R. Rudinger, and B. Van Durme.  Hypothesis only baselines in natural language inference.  _arXiv preprint arXiv:1805.01042_ , 2018b.
  * Popova et al. [2018] M. Popova, O. Isayev, and A. Tropsha.  Deep reinforcement learning for de novo drug design.  _Science Advances_ , 4(7):eaap7885, July 2018\.
  * Radić [2017] A. Radić.  AlphaZero’s “immortal zugzwang game” against Stockfish, 2017.  URL https://www.youtube.com/watch?v=lFXJWPhDsSY.
  * Romstad et al. [2008] T. Romstad, M. Costalba, J. Kiiski, and others.  Stockfish, 2008.
  * Sadler and Regan [2019] M. Sadler and N. Regan.  Game changer.  _AlphaZero’s Groundbreaking Chess Strategies and the Promise of AI. Alkmaar. The Netherlands. New in Chess_ , 2019.
  * Seymour [2019] M. Seymour.  _Hex: A Strategy Guide_.  2019\.  URL http://www.mseymour.ca/hex_book/hexstrat.html.
  * Silver et al. [2016] D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. van den Driessche, J. Schrittwieser, I. Antonoglou, V. Panneershelvam, M. Lanctot, S. Dieleman, D. Grewe, J. Nham, N. Kalchbrenner, I. Sutskever, T. Lillicrap, M. Leach, K. Kavukcuoglu, T. Graepel, and D. Hassabis.  Mastering the game of go with deep neural networks and tree search.  _Nature_ , 529(7587):484–489, Jan. 2016.
  * Silver et al. [2018] D. Silver, T. Hubert, J. Schrittwieser, I. Antonoglou, M. Lai, A. Guez, M. Lanctot, L. Sifre, D. Kumaran, T. Graepel, T. Lillicrap, K. Simonyan, and D. Hassabis.  A general reinforcement learning algorithm that masters chess, shogi, and go through self-play.  _Science_ , 362(6419):1140–1144, Dec. 2018.
  * Takada et al. [2017] K. Takada, H. Iizuka, and M. Yamamoto.  Reinforcement learning for creating evaluation function using convolutional neural network in hex.  In _2017 Conference on Technologies and Applications of Artificial Intelligence (TAAI)_ , pages 196–201. IEEE, 2017.
  * Tenney et al. [2019a] I. Tenney, D. Das, and E. Pavlick.  BERT rediscovers the classical NLP pipeline.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 4593–4601, Florence, Italy, July 2019a. Association for Computational Linguistics.  doi: 10.18653/v1/P19-1452.  URL https://aclanthology.org/P19-1452.
  * Tenney et al. [2019b] I. Tenney, P. Xia, B. Chen, A. Wang, A. Poliak, R. T. McCoy, N. Kim, B. V. Durme, S. Bowman, D. Das, and E. Pavlick.  What do you learn from context? Probing for sentence structure in contextualized word representations.  In _International Conference on Learning Representations_ , 2019b.  URL https://openreview.net/forum?id=SJzSgnRcKX.
  * Tian et al. [2019] Y. Tian, J. Ma, Q. Gong, S. Sengupta, Z. Chen, J. Pinkerton, and L. Zitnick.  Elf opengo: An analysis and open reimplementation of alphazero.  In _International Conference on Machine Learning_ , pages 6244–6253, 2019.
  * Tomlin et al. [2022] N. Tomlin, A. He, and D. Klein.  Understanding game-playing agents with natural language annotations.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , pages 797–807, 2022\.
  * Voita and Titov [2020] E. Voita and I. Titov.  Information-theoretic probing with minimum description length.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 183–196, Online, Nov. 2020. Association for Computational Linguistics.  doi: 10.18653/v1/2020.emnlp-main.14.  URL https://www.aclweb.org/anthology/2020.emnlp-main.14.
  * Warstadt et al. [2020a] A. Warstadt, A. Parrish, H. Liu, A. Mohananey, W. Peng, S.-F. Wang, and S. R. Bowman.  BLiMP: The benchmark of linguistic minimal pairs for English.  _Transactions of the Association for Computational Linguistics_ , 8:377–392, 2020a.
  * Warstadt et al. [2020b] A. Warstadt, Y. Zhang, X. Li, H. Liu, and S. R. Bowman.  Learning which features matter: RoBERTa acquires a preference for linguistic generalizations (eventually).  In _Proc. of EMNLP_ , 2020b.  URL https://www.aclweb.org/anthology/2020.emnlp-main.16.
  * Winter [1997] E. Winter.  Zugzwang.  https://www.chesshistory.com/winter/extra/zugzwang.html, 1997.  Accessed: 2021-11-12.
  * Witty et al. [2018] S. Witty, J. K. Lee, E. Tosch, A. Atrey, M. Littman, and D. Jensen.  Measuring and characterizing generalization in deep reinforcement learning.  _arXiv preprint arXiv:1812.02868_ , 2018.
  * Witty et al. [2021] S. Witty, J. K. Lee, E. Tosch, A. Atrey, K. Clary, M. L. Littman, and D. Jensen.  Measuring and characterizing generalization in deep reinforcement learning.  _Applied AI Letters_ , 2(4):e45, Dec. 2021.
  * Zech et al. [2019a] J. Zech, J. Forde, J. J. Titano, D. Kaji, A. Costa, and E. K. Oermann.  Detecting insertion, substitution, and deletion errors in radiology reports using neural sequence-to-sequence models.  _Ann Transl Med_ , 7(11):233, June 2019a.
  * Zech et al. [2019b] J. R. Zech, J. Z. Forde, and M. L. Littman.  Individual predictions matter: Assessing the effect of data ordering in training fine-tuned CNNs for medical imaging.  Dec. 2019b.
  * Zhang et al. [2018] A. Zhang, Y. Wu, and J. Pineau.  Natural environment benchmarks for reinforcement learning.  _arXiv preprint arXiv:1811.06032_ , 2018.

## Checklist

  1. 1.

For all authors…

    1. (a)

Do the main claims made in the abstract and introduction accurately reflect
the paper’s contributions and scope? [Yes]

    2. (b)

Did you describe the limitations of your work? [Yes]  See Section 3.4

    3. (c)

Did you discuss any potential negative societal impacts of your work? [Yes]
See Section 3.4

    4. (d)

Have you read the ethics review guidelines and ensured that your paper
conforms to them? [Yes]

  2. 2.

If you are including theoretical results…

    1. (a)

Did you state the full set of assumptions of all theoretical results? [N/A]

    2. (b)

Did you include complete proofs of all theoretical results? [N/A]

  3. 3.

If you ran experiments…

    1. (a)

Did you include the code, data, and instructions needed to reproduce the main
experimental results (either in the supplemental material or as a URL)? [Yes]
See 3.1

    2. (b)

Did you specify all the training details (e.g., data splits, hyperparameters,
how they were chosen)? [Yes]  See Section 3.2

    3. (c)

Did you report error bars (e.g., with respect to the random seed after running
experiments multiple times)? [Yes]  We report one standard deviation above and
below the mean in Fig. 4(a) and Fig. 6.

    4. (d)

Did you include the total amount of compute and the type of resources used
(e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]  Our hardware
used and compute estimates is described in Section 3.1. We will include a
breakdown of compute costs in the Supplementary Materials.

  4. 4.

If you are using existing assets (e.g., code, data, models) or
curating/releasing new assets…

    1. (a)

If your work uses existing assets, did you cite the creators? [Yes]  We
acknowledge the work of Jones [31] in Section 3

    2. (b)

Did you mention the license of the assets? [Yes]  See Section 3.

    3. (c)

Did you include any new assets either in the supplemental material or as a
URL? [Yes]  See Section 3.1

    4. (d)

Did you discuss whether and how consent was obtained from people whose data
you’re using/curating? [N/A]

    5. (e)

Did you discuss whether the data you are using/curating contains personally
identifiable information or offensive content? [Yes]  See Section 3.4

  5. 5.

If you used crowdsourcing or conducted research with human subjects…

    1. (a)

Did you include the full text of instructions given to participants and
screenshots, if applicable? [N/A]

    2. (b)

Did you describe any potential participant risks, with links to Institutional
Review Board (IRB) approvals, if applicable? [N/A]

    3. (c)

Did you include the estimated hourly wage paid to participants and the total
amount spent on participant compensation? [N/A]

## Supplementary Materials

Appendix A reports implementation details, hyperparameters and compute
requirements.
Appendix B gives more details on each concept introduced in the main body of
the paper.
Appendix C demonstrates how AlphaZero often wastes moves.
Appendix D has additional results across the different architectures.

##  Appendix A Implementation Details

We use agents trained by Jones [31]. See Table 1 for hyperparameters and
relative agent strengths. We used NVIDIA GeForce RTX 3090, to generate boards
and encode them. The compute is reported in Table 2 For all results in the
main body of the paper we use the model grubby. We report additional results
with other models below in Appendix D. The code, results and examples can be
found at https://bit.ly/alphatology.

agent run |  Jones [31] full agent run name | depth | width | MCTS nodes | train ckpts |  win rate against MoHex as black | Elo
---|---|---|---|---|---|---|---
grubby |  2021-02-20 22-35-41 grubby-wrench | 8 layers | 512 neurons | 64 | 20 |  0.922 | -0.345
recent |  2021-02-20 21-33-42 recent-annex | 8 layers | 256 neurons | 64 | 19 |  0.77 | -0.361
baggy |  2021-02-20 22-18-43 baggy-cans | 4 layers | 512 neurons | 64 | 20 |  0.922 | -0.388
vital |  2021-02-20 22-55-43 vital-bubble | 2 layers | 1024 neurons | 64 | 20 |  0.922 | -0.400
Table 1: Agent hyperparameters. The win rate is the agent’s win rate as black vs MoHex [28] without the swap rule. Under perfect play in Hex, black cannot lose. The Elo rating for each agent is calculated based on trials against MoHex and against the subset of agent runs Jones [31] evaluated against against MoHex. Because Jones [31] fixes the number of MCTS nodes used to compare against MoHex at 64, we do not consider alternate agent configurations that expand or contract the number of nodes when calculating the Elo rating. script | time | concepts | seeds | parallel | total
---|---|---|---|---|---
encode |  8.34 $\pm$ 4 m | x9 | x3 | - | 216 m
probing |  21.75 $\pm$ 16.35 m | x9 | x3 | /4 | 146 m
positive |  14.31 $\pm$ 8.23 m | x7 | x3 | /4 | 75 m
negative |  23.48 $\pm$ 5.46 m | x2 | x3 | /4 | 35 m
Table 2: Compute. For grubby model, the total is about 8GPU hours. The other models take less time than this model. The total run time is about 24GPU hours. We used NVIDIA GeForce RTX 3090.  experiment | parameter | $N$
---|---|---
probing | training examples | O(2000)
| test examples | O(500)
| seeds | 3
behavioral tests | examples | 100
| seeds | 3
Table 3: Experiment hyperparameters per concept.

Figure 8:  Hex templates exemplifying game concepts. Concepts within the game
of Hex are templates on the board formed by a player’s pieces with known
strategic and tactical implications. Positive concepts provide the player with
the concept with multiple ways to connect the pieces within the concept
together, despite possible attacks from the opponent. An example of these
properties is the bridge (a). If white plays move 1, black can connect the two
pieces of the bridge by playing move 2. Negative concepts change the strategic
value of specific open spots of the board, such that the opponent is
disincentived to play those open spots, such as move A in (i). Each concept is
further described in our Supplementary Material. Arrows indicate that the
piece is connected to the opposite side of the board; the lines show the
bridge concept within the other concepts.

##  Appendix B Concepts in Hex

#### Internal Concepts

With the goal of Hex being to build a chain across the board, it is helpful to
recognize when cells are virtually connected, that is, even in response to
perfect adversarial play, the cells are guaranteed to connect [24, 50]. The
bridge (Fig. 8a) is the simplest such concept. The larger internal templates –
crescent, trapezoid, span (Fig. 8(b,c,d)) – provide several possibilities to
connect a player’s pieces.

#### Edge Concepts

An edge template guarantees a connection from a single cell to a given edge
[34, 58]. Recognizing these edge templates is important for building effective
strategies. In this work, we consider the edge concept to be the two templates
shown in Fig. 8(e, f). In Fig. 8(e, f), black can connect to the bottom wall
irrespective of how white attempts to sever the connection.

#### Ladder Concepts

Ladders are common in Hex. While similar in spirit to ladders in Go, there are
some technical differences. We analyze two different ladder concepts.
Bottlenecks are a defensive concept that leads to the ladder. The defender
holds off the attacker (in Fig. 8g white successfully defends against black).
If the attacking player (here black) continues the ladder, the defending
player (here white) must block each move or lose the game. However, the
defending player will eventually win, as each defensive move builds up a chain
across the board. Ladder escapes have a different outcome. If there is already
a cell in path of the ladder, like A in Fig. 8h, then the attacking player
will win. When black plays B connecting to A, white cannot defend against both
C and D.

#### Dead Cells (Useless Triangles).

Some empty cells cannot impact the outcome of the game regardless of with
which color they are filled. A cell being dead is a global fact of the board,
and is difficult in general to compute [7]. However, there are known templates
where it is relatively easy to deduce that a cell is dead, and it is these
templates with which we test the model. Among the simplest is the “useless
triangle”, which is the precursor of the more general notion of dead cells
(Fig. 8e). If white plays A, she does not restrict black’s territory. To do so
she would have to play both other empty cells, after which her move into A
would not have any use. For black, playing A doesn’t hinder white, nor provide
any new territory.

#### Captured Cells.

An empty cell is considered captured when it is effectively filled by a
player. The templates have (at least) two empty cells A and B (Fig. 8f). If
the cells are black-captured, it means that if white intrudes into the
template (playing A), then black can respond by playing B and making A dead.

##  Appendix C Characterizing AlphaZero’s Gameplay of Hex

AlphaZero (AZ) uses both deep learning and MCTS. The deep network,
$\textit{f}_{\theta}({s})$, takes in boardgame input, $s$, and produces two
forms of output: the value estimate of the board, $v$, and a move prior, p.
These prior probabilities are then used for MCTS, which outputs the MCTS
probability distribution over actions, $\boldsymbol{\pi}$. In the game of Hex,
rewards, $z$, and value estimates are scaled within $[-1,1]$ and a reward of
$-1$ or $1$ is only recorded to the loser or winner of a match [31]. AZ is
optimized to minimize the mean square error of the value estimate and reward,
$v$ and $z$, and the cross entropy loss of the policy outputs of the deep
network and MCTS, p and $\boldsymbol{\pi}$:

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

MCTS balances exploration, search, and value estimates to pick the action that
leads to the highest probability of winning. The loss does not intrude any
term (or discount factor) to encourage winning more quickly. Consequently, the
value estimates and action probabilities produced by the deep network and MCTS
solely consider the actions that will eventually result in a win, regardless
of the number of moves necessary to achieve that win. This is in contrast to
similar Hex-playing agents such as MoHex [28, 49, 51], which is hard-coded to
connect the winning player’s pieces [2].

MoHex has been demonstrated to play perfectly on boards up to 9x9, and the AZ
agent we utilize has been demonstrated to play competitively with MoHex [31].
We observe, however, that AZ does not always end the game in the fewest
possible moves.

In practice, AZ sometimes delays winning. Figure 10 provides a hand-derived
example of AZ delaying the end of a game. Black has nearly won the game, and
must play its next move. By playing B, it can end the game; because B forms
the shortest connection for black, MoHex is hard-coded to select B. When AZ’s
MCTS is run 100 times on this board, however, AZ places higher probability on
selecting A a majority of those games (Figure 12). While playing A is a
perfectly fine move, as it forms a bridge with cells B and C, it unnecessarily
extends the length of the game.

Figure 9: Conditions. We generate boards from all combinations of these
conditions. Only “connect” (d) makes a significant impact on the results.

Figure 10: Example end game board to test efficiency of last moves. Black is
close to winning the game and must decide its next move. Selecting the B ends
the game, but AlphaZero instead selects A. While selecting A gives AlphaZero
the ability to win the game on the next round, it unnecessarily extends the
game. Right: While action B leads to a value of 1, action A also has a high
value. See Appendix Fig. 12 for the per action MCTS logits.

When AZ’s value estimates are all high, it often takes actions that
unnecessarily extend the length of the game. In Fig. 11, we present an
additional example of AZ’s behavior during an endgame from a selfplay rollout.
AZ has three bridges (Figure 8a) that will allow it to win the game: one with
the top edge, one in the middle of the board, and one with the bottom edge.
Thus, AZ is virtually connected to both edges, and guaranteed a win. However,
all possible moves for black result in value estimates greater than 0.99,
leading AlphaZero’s MCTS to not produce significantly higher logit scores for
the moves that lead to the win with fewest moves. The flatness of these value
estimates suggests a lack of distinction between efficient and inefficient
paths to victory.

This phenomena may have also occurred in AlphaGo’s match against Lee Sedol. In
game two, AlphaGo, the predecessor to AlphaZero (AZ), played a move the
commentators deemed “slack” [47]. This occurred towards the end of the game
(move 167 out of 211). Given that AlphaGo (and AZ) only consider the
probability of winning, not the margin (nor the timeframe), again, it seems
that it will sometimes waste moves when it it believes the game to be won. So,
was move 167 a mistake? Was playing A in Fig. 10 or G in Fig. 11 a mistake?
They are not (necessarily) mistakes, because AZ can still win. AZ may
understand it can use the relevant concepts to win the game, and may
eventually do so. This has ramifications for how we test AZ’s behavioral
understanding of concepts. To determine if AZ uses a concept, we present it
with a situation where understanding the concept and using it is the only way
to win.

Because AZ does not prefer faster routes, as described in the main paper, we
test the agents in forced situations. In Fig. 13, not connecting the defender
– i.e., testing the agent in unforced situations, the passing rate of the
behavioral test is lower. This is because the agent takes a longer route to
victory, not necessarily because the agent does not evaluate the
concept/correct-behavior as winning.

Figure 11: Additional example endgame from selfplay. There are six actions
that move towards ending the game for black, (A-F). Sometimes, AZ instead
plays G, which doesn’t meaningful impact the game state. Right: Most the
action values are above 0.98. Thus, the values have less impact on the MCTS
logits. In 49 of 100 selfplay playouts continued from this position, AZ takes
more actions than necessary. See App Fig. 12 for the per action MCTS logits.
Figure 12: Boxplot of MCTS logit values of example board presented in Figure
10. While move 19 has high probability of being selected as the action for
this board, AlphaZero places higher probability on move 20. Move 19 results in
an immediate win, while move 20 results in a win in the following round of
gameplay. Figure 13: Comparing behavioral results for connected vs. not
connected defenders. The passing results are lower than the connected instance
because the model does not always choose the fastest route to victory.

##  Appendix D Additional Results

Fig. 14 reports key figures from the main paper replicated across
architectures. Fig. 15 shows the same board structure from the main body of
the paper, along with some of the quantative measures of the board structure.
Fig. 16, Fig. 17, Fig. 18, Fig. 19 report the behavioral test scores (as well
as “elo”).

Figure 14: Key figures from the main paper replicated across architectures.

Figure 15: Left: Dot-product scores between cell embeddings recover board
structure, with modifications on the upper and lower edges. Each grey circle
corresponds to the same cell on the Hexboard; the black arrows correspond to
its nearest neighbors according to dot-product scores between cells’
embeddings. This diagram shows the neighborhood structure for the final
checkpoint in training. See the evolution of the board structure here:
https://drive.google.com/file/d/1UV6mhnJ_FJOP3fEiHITp0bUDC7lUMJx9/view?usp=sharing.
Right: Cell embeddings encode the board structure of the game only 50$\%$ of
the way through training. We measure how well dot-product scores between cells
align with the ground truth cell distance using a ranking metric Normalized
Discounted Cumulative Gain (NDCG). Bottom: This chart partitions the scoring
of the neighbors by cell location (bot, top, left, right, internal, center),
as well as, by player. Interestingly, there is a slight deviation from the
increase in neighorhood structure aligning with the underlying grid for a
player’s own edge cells. This appears to be from the edge pieces “connecting”
to each other at distances of two–the extra loops along the bottom and top
rows.

Figure 16: Improvements in gameplay ability, as measured by Elo, coincide with
improvements in concept recognition, as measured by the test accuracy of the
linear probe on the highest performing layer.

Figure 17: AlphaZero learns to use the positive concepts; Model Code = (left)
grubby, (right) recent. See Table 1 for architecture details of the models. At
each checkpoint, we present AlphaZero with a set of example boards that test
its ability to utilize each concept. MCTS (yellow) and the deep policy network
(red) select actions that pass our behavioral tests with increasing frequency
throughout training. We additionally report the rate at which the action that
passes our behavioral test is one standard deviation above the mean (z score
$>1$). The Agent Elo (dark green) measures AZ’s general gameplaying ability;
it increases as AlphaZero starts to use the concepts.

Figure 18: AlphaZero learns to use the positive concepts; Model Code = (left)
baggy, (right) vital. See Table 1 for architecture details of the models. At
each checkpoint, we present AlphaZero with a set of example boards that test
its ability to utilize each concept. MCTS (yellow) and the deep policy network
(red) select actions that pass our behavioral tests with increasing frequency
throughout training. We additionally report the rate at which the action that
passes our behavioral test is one standard deviation above the mean (z score
$>1$). The Agent Elo (dark green) measures AZ’s general gameplaying ability;
it increases as AlphaZero starts to use the concepts.  Figure 19: AlphaZero
does not fully “use” the negative concepts. At the end of training, it plays
moves in 25% of our behavioral tests that cannot impact the outcome of the
game [7]. To pass these behavioral tests, AlphaZero must avoid playing cells
on the board associated with the dead and captured concepts throughout a full
selfplay rollout.