Are AlphaZero-like Agents Robust to Adversarial Perturbations?
Authors: Li-Cheng Lan
Huan Zhang
Ti-Rong Wu
Meng-Yu Tsai
I-Chen Wu
Cho-Jui Hsieh
Venue: NeurIPS 2022 Accept (2022)
Keywords: Reinforcement Learning
AlphaGo
AlphaZero
Robustness

Abstract: The success of AlphaZero (AZ) has demonstrated that neural-network-based Go AIs can surpass human performance by a large margin. 
Given that the state space of Go is extremely large and a human player can play the game from any legal state, we ask whether adversarial states exist for Go AIs that may lead them to play surprisingly wrong actions.
In this paper, we first extend the concept of adversarial examples to the game of Go: we generate perturbed states that are ``semantically'' equivalent to the original state by adding meaningless moves to the game, and an adversarial state is a perturbed state leading to an undoubtedly inferior action that is obvious even for Go beginners. However, searching the adversarial state is challenging due to the large, discrete, and non-differentiable search space. To tackle this challenge, we develop the first adversarial attack on Go AIs that can efficiently search for adversarial states by strategically reducing the search space. This method can also be extended to other board games such as NoGo. Experimentally, we show that the actions taken by both Policy-Value neural network (PV-NN) and Monte Carlo tree search (MCTS) can be misled by adding one or two meaningless stones; for example, on 58\% of the AlphaGo Zero self-play games, our method can make the widely used KataGo agent with 50 simulations of MCTS plays a losing action by adding two meaningless stones. 
We additionally evaluated the adversarial examples found by our algorithm with amateur human Go players, and 90\% of examples indeed lead the Go agent to play an obviously inferior action. Our
code is available at \url{https://PaperCode.cc/GoAttack}. 

Are AlphaZero-like Agents Robust to Adversarial Perturbations?
Li-Cheng Lan'
Huan Zhang
Ti-Rong Wu²
Meng-Yo Yu Tsai"
I-Chen Wu" 3.4
Cho-Jui Hsieh
UCLA
CCMU
AAademia Sinica, Taiwan
"NYCU
Iclan0cs ucla. edu
huanChuan- zaaannhhng.-... com com
tirongwudiis sinica. edu. icwuêcs. nctu. edu.tx chohsiehâcs www..cllc.... edu
adam09223886333@gma1l com
Abstract
The success of AlphaZero (AZ.) has demonstrated that neural-network- Als can surpass human performance by large margin. However, do these superhu- man AZ agents truly learn some general basic knowledge that can be applied any legal state? In this paper, first extend the concept of adversarial examples to the game of Go: we generate perturbed states that are "semantically" equivalent to the original state by adding meaningless actions to the game, and adversarial state is perturbed state leading to an undoubtedly inferior action that obvious even for amateur players. However, searching the adversarial state is challeng- ing due to the large, discrete, and non-differentiable search space. To tackle this challenge, develop the first adversarial attack on Go AIs that efficiently search for adversarial states by strategically reducing the search space. This method also be extended to other board games such NoGo. Experimentally, show that both Policy-Vane Value neural network (PV-NN) and Monte Carlo tree search (MCTS) can be misled by adding one
Go
meaningless stones; for example, on 58% of the AlphaGo Zero self-play games, our method can make the widely used KataGo agent with 50 simulations of MCTS plays a losing action by adding two meaningless stones. We additionally evaluated the adversarial examples found by our algorithm with amateur human Go players, and 90% of examples indeed lead the Go agent to play an obviously inferior action. Our code is available at http://pperoooccc//oottoooo
Introduction
AlphaZero (AZ) [1] like algorithms have achieved state-of-the-art in Go- one of the most challenging the use
games for artificial intelligence. The success of Go AIs like AZ be contributed of Policy-Value Neural Networks (PV-NN), and Monte Carlo tree search (MCTS) 2 3). Silver al. 4 demonstrated that pure PV-NN can achieve human professional level (Elo 3055) even without any lookahead using MCTS. It has been widely believed that AZ- -zzbased agents significantly outperform humans, and even professional Go players can often learn novel strategies from these Go Als. However, we question if the agents truly learn some basic but general knowledge that can be applied to any legal state.
On the other hand, is well-known that deep neural networks can be easily fooled by "adversarial examples", which created by adding small and semantically invariant perturbations benign inputs [5] 6). This naturally leads to the following question: are AZ-like Go agents robust to adversarial perturbations? Although adversarial examples have been well-studied in many applications
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

(a) KataGo plays black at E1 before perturbation.
(b) KataGio plays black at E11 + after adding two meaningless stones marked as and 2.
Figure 1: Fig. 1b is an adversarial state perturbed from an AlphaGo Zero self-play record (Fig. lap. After adding two meaningless stones (marked as and 2), a well-trained KataGo agent with 50 MCTS simulations will switch its best action from playing black at + (EI) to human players can tell that playing at is wrong since playing black at can kill the white stones marked with triangles. However, confused by the adversarial perturbation, KataGo ends up playing to save the four black stones marked with squares and gives up the opportunity to occupy much more territories by playing at +
(E11), Even amateur
of deep neural networks, they have not been thoroughly explored in Go agents because of several challenges. First, the states of Go are discrete. We cannot directly apply gradient-bart based attacks in this setting, and efficiently searching large combinatorial space challenging. Second, Go agents use MCTS to systematically search for the best action, which can be much harder to mislead in fact, an agent would be able to always find the best action by enumerating all possible outcomes if infinite steps of MCTS simulations were allowed. Third, unlike computer vision and NLP, humans can not serve the oracle for superhuman Go agents. Hence, even if the target agent does make mistake, we may not be able to identify it. Because of these challenges, adversarial attack algorithms that have been developed for computer vision (6), NLP 7 8 and reinforcement learning 9 10
[2] can
hardly be applied to attacking Go agents.
In this paper, first give the definition of adversarial perturbations for Go. We restrict the adversary to perturb the state (game board) by only playing one or two "meaningless" actions that do not affect the win rate and the game's best action. That is, the perturbed state is "semantically similar" to the original one. An adversarial example is defined as a perturbed state leading to an undoubtedly inferior action from the Go agent that is obvious even for Go beginners. Then, proposed novel method to systematically find adversarial states where the AZ agents perform much worse than usual. We carefully designed the constraints similar to the original states and are also easy enough for human players to verify the correct move. If Go agent cannot find the correct move for this perturbed state, say found adversarial example. Finally, we test A7-based agents with thousands of these perturhed states. Surprisingly, we find that agents make trivial mistakes on these adversarial examples, even when MCTS is used.
perturbed states during the search that they semantically
Fig. Tb shows one the perturbed states found by our algorithm that AZ agents will fail. B19 and PI (marked in purple) are the two "meaningless" stones added as adversarial perturbations. Adding them won't i change the turn player's best action and win rate. However, those actions can mislead KataGo [13, well-known Go agent with 50 MCTS simulations, to "forget" to kill the white stones marked with squares (action A) and instead want to save the black stones marked with triangles (action B), even if doing will be big disadvantage and likely to lose the game. This mistake is very trivial such that even amateur human players can identify it.
The contributions of this paper can be summarized below:

---

For the first time, we reveal the vulnerability of both PV-NN and MCTS- based AZ agents. Our proposed attack found adversarial examples (e.g.. Fig. [b) that are semantically equivalent to a "natural" state (from a real game record) while leading to catastrophic behavior of the target agent. The mistakes made by a super-human agent can be identified by Go amateur players.
Our attack involves an efficient method to speed up the search of adversarial states in the large discrete state space without relying on gradients and is usually more than 100 times faster than brute force search.
We conduct a comprehensive study on the robustness of four oftte-of-thh-arr public AZ agents with six different datasets for the game of Go. By generating adversarial states with two meaningless moves, our attack can consistently achieve over 90% success rates on PV-NNs and achieve over 58% success rates on MCTS agents with 50 simulations. Moreover, our method can also be applied to other games: we found adversarial examples on 50% of data in our NoGo [4] experiment.
2 Background and Related Works
Terminology Games like Go can be described as a two-player zero-sum deterministic game [S and can be defined as a tuple (S. A, T, R), where S is the state space, A is the action space, T x A + the transition function and R : + {1, 0, -1) the reward. Each game starts from an initial state So E S (empty board) at time 0. At the current state st, the turn-player, defined as Sr.C, can play an action 0 E A(s)). In Go, players take turns placing a stone of their color on the board. Therefore, all actions are composed of color and a position p. indicating placing c stone on p. The only exception is the pass move apass which means the turn-player does not place any stone (gives up on his turn). After playing action ag on state St, can get the next state by 81-1 = (s,,, a.). The game ends when reaching a terminal state ST, where we can determine who wins the game and each player receives reward. Since the games are zero-sum, the reward of the opponent player is - -R(s). For the non-terminal states, the reward is R(s) = for any player.
Policy Value Neural Network (PV-NN) and Policy Value MCTS (PV-MCTS) PV-NN is proposed in AlphaGo Zero paper (4) PV-NN takes a state as input and outputs a value v(s) and a policy p(s). Value 0 s vs)) s 1 is a scalar from O to that indicates the estimated win-rate of current state. For example, u(s) < 0.5 means that PV-NN believes the turn- turn-player of state 8 is losing. Note that if the value output range is -1 S v(s) S 1. the win-rate can be calculated by (u(s) + 1)/2. Policy p(s) is vector that indicates each action o's probability 0 S p(als) s 1. A high probability for an action, e.g.. p(als) > 0.9, indicates that the the PV-NN highly recommends action state Besides PV-NN, AlphaGo Zero 4 also adopted Policy Value MCTS (PV-MCTS) to choose the best action. Unlike MCTS, PV-MCTS uses the value output of PV-NN instead of Monte Carlo simulation to evaluate the selected state values. Moreover, PV-MCTS utilized the policy of PV-NN to narrow down the search space with the PUCT algorithm [16]. The search efficiency of PUCT highly depends on the prior probability P(s, aa" of best action a Therefore, if the root's prior policy is incorrect, the search efficiency will drop dramatically. Take Fig. 1b as an example; even after 50 MCTS simulations, KataGo still hasn't 't discovered action E1 + is a good action because the prior probability of action El + is too small. As more states have been evaluated by PV-NN, PV-MCTS can provide stronger policy ग (s), value V (s), and action values ((s, a) of given root state s.
Adversarial Example It has been observed that many neural networks used in computer vision, NLP, and reinforcement learning are vulnerable to adversarial examples 5 17 9. Traditionally, an adversarial example, created by minimally modifying natural example, is semantically equivalent to the original natural example for humans but can make the target model produce a totally different output. Note that the perturbed state should also look natural [18]. To define an adversarial example for a particular task, one has to define a reasonable perturbation set around original examples and design an algorithm find an example within the set that leads to incorrect behavior of the model (e.g., misclassification). In computer vision, the perturbation set is usually defined as a small ép norm ball, as small perturbations to images are usually imperceptible to humans. And due to the continuous search space, existing image attacks often rely on gradient- gradient-based optimization to find adversarial examples 19 20, 21 22). On the other hand, for discrete models like text, there exists multiple definitions for the perturbation set such as synonym substitution 23 24 edit distance (5) or language model-based scores (26). For example, if the maximum edit distance one, given natural sentence, "This movie had terrible acting." adversarial example can be "This movie
3

---

had awful acting." where we only change one word in the sentence to its synonym. Note that such examples are not humanly imperceptible, and the synonyms are defined by humans. Due to the discrete nature of the text domain, finding an adversarial example leads to combinatorial search problem, and several attacks have been proposed for this [27 28 23 However, none of these attack methods can be directly applied to attack AZ agents for the following reasons: 1) Unlike the image or NLP domain, the semantically invariant perturbation in Go is difficult to define (see Sec. 3.1. 2) Unlike other applications, the Al's ability is much stronger than humans in Go. it is non-obvious how to find adversarial examples that can be understood by humans. Although some recent works
have studied perturbations to states [12], actions [29], observations [9] 10 30 31 or rewards [32 in the reinforcement learning setting, none of them consider discrete input domains like Go or against
super-human planning based agent like AZ agents.
Studies on the weaknesses of Go agents Go Al agents have several weaknesses. First, it is well-known that the existence of several patterns such as ladders and long dragons will confuse the agents. This is due to the local nature of convolutional neural networks (CNN). Second, when researchers use Go Al to study Tesuji problems [33, they observe that some of the problems require millions of simulations to find the correct action. Third, some researchers [33 find some states that the agent will ignore the best action (prior probability almost equal to zero). which sometimes refer as "blind spots" of the agents. Our work is different from those works in the following ways. First, our adversarial examples caused by ladders and long dragons are some bugs the model will make in normal states. Second, we find the adversarial examples automatically and systematically. We show that z 58% of the games we selected exist adversarial examples that normal humans can be better than state-of-the-an Als. By finding "bugs" efficiently, researchers may have enough training data to improve their Als.
find bugs at which the model (agent) is used to be good. The mistakes
3 Method
Given a state s, a target agent (c.g., PV-NN or AZ agents), and a much weaker verifier (c.g.. humans), our goal is to find an adversarial example s' that satisfies the following conditions:
C The perturbed state s' is very close to the original state s terms of &o distance.
C2 The perturbed state s' is semantically equivalent to s, and the verifier can verify that.
C3 The target agent performs correctly on s but wrongly on s', and the verifier can identify that.
Both C₁ and C2 define a set of perturbed states, B(s), for a given natural state The problem of finding adversarial examples is then equivalent to finding a s' E B(s) that satisfies the success criterion (Cg). In previous image attacks, B(s) is a small Ep ball 6 19] and in text attacks Bss) is
usually defined by word substitutions with synonyms 23 However, in our case, the definition of ((s) is much more sophisticated and computationally expensive to check.
The existence of much weaker verifier is to define the adversarial examples we want to find. We hope that the target agent's mistake on the adversarial examples verifiable to the verifier. Hence, the playing strength of the verifier determines the difficulty of finding adversarial examples. The weaker the verifier is, the harder it is to find example. In addition, our method finds the s' without the help of verifiers since verifiers, like humans, are hard to include an automatic process. Therefore, we need to carefully design the B(s) and the success criterion so that the s' satisfies the conditions automatically. In the following, we will discuss how to define B(s) and the success criterion in Subsections 3.1 and 3.2, respectively. A search algorithm will then be introduced in Subsection 3.3 to speed up the search.
3.1 Defining the Perturbation Set
We detine the perturbation set (B(s) of given state based on conditions C₁ and Cz. For C₁, we use actions as perturbation and the number of actions we added as distance. In our experiments, we set distance Eo as 2. Since each state in Go can be represented by its trajectory (a list of actions),
the perturbed state s' can be presented as dg 01, , 14-1. by by where ag. 0t-1 is the trajectory of and by. by are the extra actions. For ISTEP attack, one of the by, by has to be the pass action (denoted as d. This means we place an additional stone on the board without changing the turn
player. On the other hand, for 2STEP attack, both bo, by are not the pass action, which means we add

---

one black and one white stone on the board. We do not include states created by replacement like word substitution in text attacks since there are no similar actions Games like Go.
For condition C2. we aim to maintain the semantic meaning after perturbation. Since there is no ground truth in Go, we resort to "examiner" agent to verify the equivalence of states. The examiner should be able to provide an accurate value (s),, the policy ((s), and the action values Q(s, a) for given state s. For example, the examiner we used is the strongest PV-MCTS agent that runs 800 simulations. To distinguish the oulput of the examiner and the target agent, we use v(s) and s) as the output of the target agent. With the examiner, we define two states s, s are semantically equivalent the two states have the same turn players and similar winrate according to the examiner, which is shown in the following equation.
s.c = s s' and (V(s) - V(s)) S Ney
(I)
where s.c denotes the turn player (e for color) of state a and Tey is the threshold used to define that the win rate is close.
Although the examiner is normally better than the target agent, is still not perfect. The examiner may also make a low-level mistake on s' since the PV-NN it uses wrong on s'. To improve the examiner on 8', we provide with its best action og on 8 as a hint. That is, we evaluate the examiner value of s by forcing the examiner to evaluate the state a.) Since T(s', a.) has a different turn player, so the new V(s') is
max (
Note that one can provide more hints to the examiner by forcing it to consider more actions even paths that are reasonable in 8. This method makes it possible to find adversarial examples even if the target agent is the same as the examiner.
Besides ensuring s. s' to be semantically equivalent, such equivalence should be verifiable to the much weaker verifier like humans. Unlike standard image or text applications where humans are treated as oracles, the Al agents for Go are much more powerful than a human. When the game is too complicated, humans cannot even tell who has the advantage. Therefore, even though both states s and s are semantically equivalent (Eq. to the examiner, the verifier may not be able to tell.
Fortunately, we observe that humans can identify most of the "meaningless" actions which do not help their turn players to gain any benefits. Here, we define an action as meaningless its effect on the winrate is equal to playing pass action. The following is the formal definition:
IV(s) - V(F(ss)) S Mlg
where F(s, a) : -SXA+ S returns the state after playing action a on state without changing the turn player by playing an additional pass action (Appendix (P) Based on this definition, all the actions that satisfy Eq. ii the 1STEP attack are already "meaminless"" since one of by. b, is a pass action. Therefore, humans can verify that s and s' are semantically equivalent the 1STEP attack. For 2STEP attack, we require both bo, by to be meaningless (Eq. 3 In this way, humans can verify that and s' are semantically equivalent by checking that both by and 6, are meaningless.
In addition, in the game of Go, we found that most meaningless actions are in one of the player's territories (Appendix EE). Also, humans can usually verify such actions faster. Therefore, in the experiments of Go, we further restrict the perturbation action's position a.p within one of the territories a.p E Terrw U Terrg, where Terry and Terry is the territory of each color. The results show that we can find adversarial examples even with this stronger constraint. See Appendix G for the comparison without the territory constraint.
3.2 Success Criteria of Adversarial Attack
Next, we define our attack's 's success criteria (C3). We consider two types of attacks: value attacks and policy attacks. For value attack, the goal is to change the prediction of the target agent's value network. Therefore, we define the attack to be successful if
(u(s) - [()) Mocreet and lu(s') v(s')) Tadv
(4)
5

---

The first criterion ensures that the target agent produces the correct value on the original state s, and the second criterion ensures that the target value network becomes incorrect after the perturbation.
Note that we already enforce (s) = (s') in Subsection 3.1 so implies that the perturbation will change the target agent's s value but not the examiner's value. Constants Tocmreet and Tudv are the thresholds to define "correct" and "wrong" in C3. For example, if we want to find an example that PV-NN misclassified the winner of state, we can set 1/ddv = 0.5. We can further increase Vlav if we want the target's 's output to be wrong by a larger margin. In addition, the verifier can easily tell that target is wrong since 8, 8 are supposed to have the same winrate (C2) but (ss) and u(s') are different.
For policy attack, we aim to fool the policy output. However, unlike classification settings, there is more than one best action for state. Therefore, even when the perturbation can significantly change the output policy, doesn't mean the new policy incorrect. We thus have to define the successfulness of the policy attack by checking whether the value (computed by the examiner) will be changed after playing the predicted action. With these in mind, we say the policy attack leads to a "wrong" move if
V()]| s 7oooreet and IQ(s', v(s')) 2 Vady
(5)
where a, arg max, (p(als) and a. arg max, max, (p(als') are the target agent's recommended actions on s and s'. The first criterion in (5) ensures that the target agent can predict a proper action for the original state s, and the second criterion checks whether the target agent will output significantly worse action in the perturbed state s'. With Eq (5), although the examiner can verify that the target agent plays a losing action on the perturbed state; the verifier may be uncertain that the action a is truly bad. Luckily, in our qualitative study, by providing o to humans as a hint, humans can immediately tell that og is much more important to play than ag in the state s' and certify that the target agent is wrong on most pairs (s, 8') we found. Hence, we add two more restrictions: 1Q(s', ) - V(s') s Tey and [Q(s, a V())] 2 'advv These restrictions ensure that ag is a good action and a is a bad action for both and s', so that the verifier can use them as an anchor.
3.3 An Efficient Attack Algorithm
Like other adversarial attacks reinforcement learning 9 10), we apply our attack to perturb state in a given game since it only takes one mistake for an agent to lose a game. Formally, given a game G {sp. .1......T].. if we can find one pair of (s,, where S; is an adver- sarial example of s;, then we have successfully attacked the agent on that game. We will first apply the ISTEP attack to a game, and if it fails, we then conduct the 2STEP attack.
Algorithm 1 Two-Step Value Attack
1: Input: a game 81, 12,,,,...,,8 8r, target agent I, examiner
2: for i = TT to do
3: if (s:V - (s;)) Momrrat then
4: continue
5: cands = =gettMeminglesssccioon (c, 8;)
6:
for bo in cands[ 00] do
Since the search space is countable, a naive way to find an adversarial example is con- duct a brute-force search to check all states in the search space. However, this will lead to very high complexity, and the search cannot be finished in practice. Taking the 2STEP attack as an example, let T = 300 denote the game length, N = 150 denote the average number of actions for state, and M 2 800 denote the sim- ulation count of the examiner. Then, we need M(TNM) time to obtain the search space for all i i E (0. 1, I,..,,T) T) by checking which actions are meaningless. Furthermore, assume that there are averagely N meaningless moves for each state.
7:
for b, in cands[1] do
8:
= T(= bo), if [t.u(s') e. (s:)) 2 IMav Teyyl then
9:
10:
if (t.u(s)) e.((s') 2 Bndy and
(e.V(s) e. v(s')l s 1lcg then
return s'
12: return NULL
Then, we need ((TN*M) M) to check the success criteria of each perturbation. Note that in both stages, the running time of the examiner will dominate, as we need to run the examiner with much more MCTS steps. Hence, we propose the following two approaches to reduce the search complexity.

---

Table 1:
Our attack results on Go agents, av- eraged over all datasets. EXECUTED NUM shows the average number of target and exam- iner calls for the attack, and SPEEDUP indicates the speedup of the proposed method over the brute-force search. High attack success rates are observed in all settings.
Table 2:
Our attack results on datasets, aver- aged over all Go agents. EXECUTED NUM shows the average number of target and exam- iner calls for the attack. The first five datasets are described in experiment settings. FOX the dataset of non-professional players.
SUCCESS
RATB
EXECUTED
SUCCISS RATH
EXICUTED NUM
GAMES
1STEP
2STEP
TARGET
EXAMINER
AGENT
ISTEP
25T13P
TAKGETT
EXAMINER
SPEEDUP
2Z
0.78
0.89
14691
316
KATAGO
0.50
1400
6152
30
ZM
0.90
0.95
12977
19?
VALUE
LEELA
0.90
0.98
37533
182
163
VALUE
MH
(1500
0.81
173841
663
Nut 0.5
ELF
0.92
180
11108
106
90
O..
LG
12650
161
CGI
1.00
1.00
40
14988
KATAGO
0:86
0.4
44638
125
FOX
0.94
53792
213
VALUE Mur 0..
FRLA
0.20
0.84
96154
140
ELF
0.65
0.27
42503
398
94
ZZ
0.57
0.82
33314
502
CGI
1.00
180
45
15
7M
0.84
0.94
13574
178
KATAGO
POLICY 0.7
MH
0151
0.80
2272012
258
LG
0.84
0.96
52055
274
0.81
0.7
16387
123
ATV
79688
CGI
0:87
0.9
16495
103
133
FOX
141120
225
KATAGO
0:55
0.83
231895
707
POLICY
LEELA
0:35
0.93
36438
24915
First, we reduce the time of finding meaningless actions by the following observation. If an action is a meaningful action (not meaningless) of state st, then it is likely that a is also a meaningful action of state 8t-1- Intuitively, if an action is a meaningful action st, means that a can occupy some extra territory that is not occupied at 8.. Hence, if a position is not occupied in st, it is likely that the position is not occupied in St-1 and can be occupied by action too. So action is also meaningful action for s,-1. We formally prove this property under some assumptions in Appendix A Based on this observation, we run the search in a backward manner from the final state ST to the initial state $1. Once an action is identified as meaningful at state 9,, we do not need to check it again on any state (&, : t). This will significantly save the computational time to enumerate B(s). The details of getting meaningless actions are shown in Appendix C
Second, for the part of checking the attack success criterion, we derive bound to filter out unsuc- cessful perturbations quickly. Taking the value attack as an example, checking ( and (4) requires running the examiner on the perturbed state s', which is the bottleneck of the algorithm. To reduce this cost, we show that the condition of (L) and (4) implies
lu(s') V(+) ((v(s)) - V(5') - (V(s) v(s'))
2 (u(s') (V(s)
Yaavv
Vloy-
(6)
Since (6))
only requires running examiner on the original state instead of s', we can check (6) first before checking (1) and (4). We observe this step can filter out more than 99% of the s'.
The overall attack algorithm is presented in Algorithm|] [ The input includes game 81, 82, ..... 8r, target agent f, and an examiner agent e. As mentioned before, the search is conducted in backward manner from ST back $1 (line 2). For each s,, we first check whether s; is too hard for the target (line 3). If so, we will skip this state (line 4). We then compute all the meaningless actions of state s; using the examiner with the efficient implementation mentioned above and store the meaningless actions separately in cands[O] and cands[1] according to their color (line 5) as the candidates of successful attack (lines 9-11). Note that line 9 is based on (6). and the examiner does not need to compute e. vs;)) again since has evaluated it on line 3. For policy attack, we can skip all the states that are losing V(s) 'aavv
perturbation. We then check whether each 2STEP perturbation will lead
since for those states, there is no correct answer to attack. (More details in Appendix B)
4 Experiments
Experiment Settings We evaluate our method on 19x19 Go. The four open-source programs we used are KataGo [3]. Leela Zero [34], ELF OpenGo (35). and CGI (36.. The strengths of these
7

---

VALUE ISTEP
VALUE 2STEP
ISTEP
Table KataGo with different simulations on ZZ dataset. EXECUTED NUM shows the average number of target and examiner calls for the attack.
0.75
0.5
SUCCESS RATE
EXECUTED NUM
SIM
ISTEP
2STEP
TARGET
EXAMINER
1.00
1.00
1016
41
0.89
0.95
4454
2322
VALUE
0.89
100
Rosl
25
0.84
0.89
18516
13903
Kanatlo 20 bloccks simulation count
50
0.53
0.58
76426
41914
1,00
1.00
1.00
3309
1318
Figure 2: The attack success rate of 7adv = 0.7 on datasets that generated by KataGo 40 blocks with 800 simulations vs KataGo 20 blocks with different numbers of simulations.
POLICY
0.95
1.00
6666
2662
0.79
1.00
12466
50
0.21
0.68
89512
41702
AI agents are KataGo Leela ELF CGI, where KataGo has more than 99% winrate against Lecla. We use KataGo (40 blocks) with 800 simulations as our examiner, For the thresholds, we set "lo 0.1, 'oooeeet 0.15, since after testing several different Tlog and ecooect values, this pair leads to more human- sumaan-understandable results. For the datasets, we selected 99 games from five different sources, which are AlphaGo Zero 40 blocks training self-play record (ZZ.) AlphaGoo Zero vs AlphaGo Master (ZM), AlphaGo Master vs Human champions (MH), the final games of LG Cup World Go Championship (2001-2020) (LG), and the final games of Asian TV Cup (001120200) (ATV). Note that the thinking time for ATV Cup is much shorter than LG Cup, we expect them to reflect human games with different strengths. All the datasets have 20 games, except ZZ has 19 games since the first game is played by two random agents.
Results on Different PV-NNs We first evaluate the robustness of the four agents' PV-NNs since PV-MCTS is much slower. The results are shown in Table T. where we attack each agent's 's PV-NN with both ISTEP and 2STEP attacks with various Tlav-- We also present the average number of evaluations required for the target agent and the examiner agent to show the speedup. The first two groups in Table [ demonstrate the robustness of these agents against the value attack. Group one (7av 0.5) shows that even the 1STEP attack can achieve above 90% success rate on all agents and mostly achieve 100% on the 2STEP attack. For those that have the same attack success rate, we can still compare the attack difficulties by the number of target evaluations. For example, although the 2STEP success rates of KataGo, ELF, and CGI are all 100%, the number of states that they have visited is totally different. For CGI, we are able to find an adversarial example after visiting 40 states, while ELF requires visiting 11, 108 states. Hence, we conclude that Leela ELF > KataGo > CGI in terms of their robustness against value attack when Badv 0.5 and 7ndy = 0.7. Interestingly. this ranking does not match the playing strength of each agent. The third and fourth groups of Table show the results of the policy attacks. In general, we observe that it is harder to attack the policy than the value. Interestingly, the ranking of four agents in terms of their policy's robustness is KataGio Leela ELF = CGI, which aligns with the playing strengths of those agents.
In Table D we also demonstrate our algorithm's speedup in the SPEEDUP column compared the brute force algorithm. In the brute force algorithm, the examiner must evaluate all the states the target agent has evaluated. Hence, the speed up is almost equal to (Nearger TM (Trragt + Mexaminer X mMCts). where 'sageet and Pexaminer are the numbers of states that the target and the examiner have executed. MCTS is the number of simulations that the examiner use for the PV-MCTS. The results show that the proposed efficient search method is usually more than hundred times faster than brute-force search, especially for harder problems that require the 2STEP attacks to succeed.
Results on Different Datasets We also study the robustness of all agents on different types of game records. We consider the 5 datasets used in the previous subsection, plus additional FOX dataset, to represent amateur players and see if the games played by weaker players are harder to attack
'naps:/wwww.foxw.ccoml
8

---

(a)
(b)
(a)
(b)
Figure 3: Adversarial example of policy attack (a) and value attack (b) on FOX. Both examples are ISTEP attacks with turn player white. Their perturbation actions are marked as 1. For (a), the agent plays B instead of A. For (b), the agent predicts very different winrate (> 0.9) on the original state and the perturbed state,
Figure 4: Adversarial examples generated by pol- icy attack (a) and value attack (b) that cannot be easily verified by humans. For (a), it is hard for humans to verify that playing white on B is a bad action even if A is provided. For (b), perturba- tion action marked as does help white get some benefits, but not enough change the winrate. Hence, it is meaningless. However, humans can not verify it unless they thoroughly calculate both sides' territories.
since those games are easier for humans to understand. The results in Table 2 show that PV-NNs vulnerable to all levels of games, regardless of AI agents, professional players, or non-professional players. We observe that the AlphaGo Master vs. Human champions (MH) dataset has the lowest success rate on both policy and value attacks compared to other datasets. Since AlphaGo Master much stronger than human champions (60 0), we hypothesize that "when one player is much stronger than the other, the winner of the game may be too obvious and easy for agents to judge." To support this hypothesis, we generate games of KataGo 40 blocks (K40) with 800 simulations vs. KataGo 20 blocks (K20) with different simulations to simulate games played by players with different strengths. Note that K20 already much weaker than K40. Fig. shows the results of attacking KataGo's 's PV-NN with those games. We can see that when the games have larger gaps, both the policy and value output of KataGo's 's PV-NN will be harder to attack. This suggests that the playing strength between game players will likely affect the difficulty of finding adversarial examples.
Robustness of PV-MCTS In this paragraph, we investigate the robustness of PV-MCTS with different simulations. Since PV-MCTS is much slower than PV-NN, we only test KataGo on the AlphaGo Zero self-play (ZZ) dataset with Badv 0.5. The results are shown in Table The first column is the simulation count of KataGo. When the simulation equals one, it is the same as using PV-NN directly. The first group shows the results of the value attack. Even with 25 simulations, the 2STEP success rate is still 89%. For group two, we observe that the policy of small simulations is even less robust than PV-NN's policy. For example, when the simulations of KataGo is 10, the 1STEP success rate is 95%, while the policy of PV-NN is 84%. Therefore, we conclude that with small number of MCTS simulations, the agent will not be able recover from the bad PV-NN outputs and will still be fooled by adversarial examples. However, when using more MCTS simulations, the attack success rates will still drop since the agent has more chances to discover correct actions.
Quality of adversarial examples Although the AZ agents do make mistakes on the adversarial examples we found, still need to make sure that those mistakes can verify them. Hence, we randomly selected 100 examples from all the experiments and conducted the following two human studies to see how many percent of mistakes are human verifiable mistakes. Fig. 3 show four examples that we samples, and more can be found in Appendix H In the first study, we examine whether humans can verify that perturbed state s' is semantically equal to the original state 8. For each adversarial example, we present both the original board and the additional stones to three amateur human players (with level 2K, 3D, 5D) who served as verifiers. For 90% of those perturbations, they can certify that the perturbations are meaningless with short thinking time. Fig. 4 (right) shows one of the fail examples, where the meaningless action J3 seems meaningful to
low-level that even humans

---

humans since it can capture the black stone J2. However, with longer thinking time and discussion with each other, verifiers can understand that the rest 10% of actions are meaningless.
In the second study, we examine whether the "wrong" actions resulting from our policy attack can be verified by humans. Similar the previous experiment, we present the original board, original action, perturbed board, and the action after perturbation to the examiners. When the target agent is a PV-NN, humans can identify 100% that the recommended actions after perturbation will change the result from winning to losing. However, for the adversarial examples where the target is PV-MCTS agents, only 70% of the recommended actions after perturbation can be identified as wrong by humans. The main reason is that as PV-MCTS agents are able to lookahead, they tend to avoid actions that are clearly wrong, so the errors become more subtle humans. Fig. [ (left) shows one of the states, where the white should play at A to save the stones marked with squares, but with two meaningless moves added the PV-MCTS agent with 100 simulations will play at B. Although after playing B all the stones marked with squares will be dead, it is hard for humans to verify the outcome of this play.
Agents are sensitive to the ordering of actions in the trajectory Finally, after viewing those adversarial examples, we find that the policy attack succeeds often because the target agents are too reliant on the information of the last action. For example, if KataGo knows the last action of Fig. [6] besides the actions we add is white playing E3, even PV-NN knows that it needs to play EI. Based on this observation, we can improve the robustness of PV-NNs using the following method. Given a state with trajectory (o d1...., .,, we define augmented state do, d1 a2 ..., (0g-1, at at- 4z-3- If & is a legal state, we can define a robust policy p, (aas) = (p(als) + p(a[s))/2. With this method, PV-NNs evaluate the state with different actions being the last. We evaluated this method on the same setting as Table [ (attacking KataGo's 's PV-NN with ZZ dataset and Budy = 0.5). The success rate of 1STEP and 2STEP policy attacks dropped to 58% and 89%, even better than the original PV-NN and PV-MCTS with 25 simulations.
Experiments on the game of NoGo Our "action perturbation" method can also be used to find severe bugs automatically on other games by removing the territory constraint. We use the following 9x9 NoGo [4] experiments to demonstrate it. We use an AZ agent (37] with 800 simulations the examiner and use its PV-NN as the target agent. Since NoGo is a game without any human experts, we use a traditional MCTS agent 38 with 1000 simulations as the weaker verifier. Note that the target agent has a 100% winrate against the verifier in 1000 games. Intuitively, the target network will not make a critical mistake that the verifier will not make. However, on 20 self-play games of the target network (the average search space is about 10000), 50% of the games exist adversarial policy examples with Made 0.5 that the verifier can verify. Moreover, our proposed efficient search method based on Eq. 6 is 307x faster than the brute force search.
5 Conclusion and Future Works
In this paper, we first properly define the perturbation set BBs) and the success criteria with the help of an examiner, which become even more reliable after giving it some hints. The adversarial examples we find are understandable to much weaker verifier like amateur human players. We also proposed a new efficient search algorithm by reducing the usage of the examiner. Our experiments found that even the strongest AZ agent with small number of simulations is vulnerable to our adversarial attack. We hope our work can raise the attention that even for Al agents that surpass humans by a large margin, they still can easily make simple mistakes that humans will not. We also hope that the examples we found can he used to improve Al agents. For example, for Go, we have shown that the agents are sensitive to the ordering of actions in the trajectory.
A limitation of this paper is that we are only able to identify adversarial states but haven't been able to guide the AZ agents to those states systematically. Potentially, this can be done by training an agent to play against a particular target agent and incorporating some blind spots found by our attacks. Although [39] try this after our publication, their agents cannot beat KataGo under realistic judgments, so this is still an interesting open problem to pursue in the future.
Finally, we hope our work can serve as a generalization benchmark for Go AL If Go Al is generalized enough, should be able to provide a decent action on any state Go, just like humans. One of the solutions is to use the numerous examples we found to train a better agent.
10

---

Acknowledgments and Disclosure of Funding
This work is supported in part by NSF under IIS-2008173, I1S-2048200, and by Army Research Laboratory under W911NF-20-2-0158.
References
[1] David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play, Science, 162(6419):1140-111 1144, 2018.
[2] Cameron B Browne, Edward Powley, Daniel Whitehouse, Simon M Lucas, Peter Cowling, Philipp Rohlfshagen, Stephen Tavener, Diego Perez, Spyridon Samothrakis, and Simon Colton. A survey of monte carlo tree search methods. IEEE Transactions Compulational Intelligence and Al in games, 4(1):1-43 2012.
[3] Levente Koesis and Csaba Szepesvári. Bandit based monte-carlo planning. In European conference on muchine learning, pages 282-293. Springer, 2006.
[4] David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, al. Mastering the game of go without human knowledge. Nature, 550(7676)3354-355 2017.
[5] Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfel- low, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint 1xXix:3312.6999 2013.
[6] Ian Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversar- ial examples. arXiv preprint
2014.
[7] Takeru Miyato, Andrew M Dai, and Goodfellow. Adversarial training methods for semi- supervised text classification. arXiv preprint 16Xiv:1605.07725. 2016.
[8] Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. Semantically equivalent adversarial rules for debugging nlp models. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 856 856-865, 2018
[9] Sandy Huang, Nicolas Papernot, Ian Goodfellow, Yan Duan, and Pieter Abbeel. Adversarial attacks on neural network policies. arXiv preprint arXiv:1702.02233 2017.
[10] Yen-Chen Lin, Zhang-Wai Wei Hong, Yuan-Hong Liao, Meng-Li Shih, Ming- Yu Liu, and Min Sun. Tactics of adversarial attack on deep reinforcement learning agents. arXiv preprint 17330:1703.06748, 2017.
[11] Jernej Kos and Dawn Song. Delving into adversarial attacks deep policies. arXiv preprint arXiv:1705.06455 2017.
[12] Adam Gleave, Michael Dennis, Cody Wild, Neel Kant, Sergey Levine, and Stuart Russell. Adversarial policies: Attacking deep reinforcement learning. arXiv preprint arXiv:1905.10615. 2019.
[13] David Wu. Accelerating self-play learning in go. arXiv preprint Ariiv: 2019.
[14] Martin Müller. Nogo history and competitions. https://uebdocs cs
caa.sdocs.cc..aabbaaaa.. wwwberta.a...... ca/
nmmelleer/nogohhistoryy.t
(visited 2021/03/14), 2015.
[15] Michael L Littman. Markov games as a framework for multi-agent reinforcement learning. In Machine Learning Proceedings 1994, pages 157-163. Elsevier, 1994.
[16] Christopher D Rosin. Multi-armed bandits with episode context, Annals of Mathematics and Artificial Intelligence, 61(3):203-230, 2011.

---

[17] Robin Jia and Percy Liang. Adversarial examples for evaluating reading comprehension systems. arXiv preprint arXiv: 17X.007777.,3328, 2017.
[18] Dan Hendrycks, Kevin Zhao, Steven Basart, Jacob Steinhardt, and Dawn Xiaodong Song. Natural adversarial examples. 2021 IEEE/CVF Conference Computer Vision and Puttern Recognition (CVPR), pages 15257-15266, 2021.
[19] Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In 2017 ieee symposium on security and privacy (sp). pages 39-57. IEEE, 2017.
[20] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv: /01.0000660083 2017.
[21] Pun-Yu Chen, Yash Sharma, Huan Zhang. Jinfeng Yi, and Cho-Jui Hsieh. Ead: elastic-net attacks to deep neural networks via adversarial examples. In Thirty-second AAAI conference on artificial intelligence, 2018.
[22] Francesco Croce and Matthias Hein. Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks. In International conference on machine learning, pages 2206-2216 PMLR, 2020.
[23] Moustafa Alzantot, Yash Sharma, Ahmed Elgohary, Bo-Jhang Ho, Mani Srivastava, and Kai-Wei Chang. Generating natural language adversarial examples. arXiv preprint arXXiv:884.00P 2018.
[24] Shuhuai Ren, Yihe Deng, Kun He, and Wanxiang Che. Generating natural language adversarial examples through probability weighted word saliency. In Proceedings of the 57th annual meeting of the association for computational linguistics, pages 1085-1097, 2019.
[25] Ji Gao, Jack Lanchantin, Mary Lou Soffa, and Yanjun Qi. Black-box generation of adversarial text sequences evade deep learning classifiers. In 2018 IEEE Security and Privacy Workshops (SPW), pages 50-56. IEEE, 2018.
[26] Linyang Li, Ruotian Ma, Qipeng Guo, Xiangyang Xue, and Xipeng Qiu. Bert-attack: Adversar- ial attack against bert using bert. arXiv preprint arXiv:2004. 09994, 2020.
[27] Qi Lei, Lingfei Wu, Pin- Yu Chen, Alexandros G Dimakis, Inderjit S Dhillon, and Michael Witbrock. Discrete adversarial attacks and submodular optimization with applications to text classification. arXiv preprint / 18/2.00/5/, 2018.
[28] Puyudi Yang, Jianbo Chen, Cho-Jui Hsieh, Jane-Ling Wang, and Michael Jordan. Greedy attack and gumbel attack: Generating adversarial examples for discrete data. J. Mach. Learn. Res., 21(43):1 2020.
[29] Chen Tessler, Yonathan Efroni, and Shie Mannor. Action robust reinforcement learning and applications in continuous control. In International Conference Machine Learning, pages 6215-6224. PMLR, 2019.
[30] Chaowei Xiao, Xinlei Pan, Warren He, Jian Peng, Mingjie Sun, Jinfeng Yi, Mingyan Liu, Bo Li, and Dawn Song. Characterizing attacks deep reinforcement learning. arXiv preprint arXiv: 190700990,,09470 2019.
[31] Huan Zhang, Hongge Chen, Chaowei Xiao, Bo Li, Mingyan Liu, Duane Boning, and Cho- Jui Hsich. Robust deep reinforcement learning against adversarial perturbations on state observations. arXiv preprint arXiv:2003.089338 2020.
[32] Amin Rakhsha, Goran Radanovic, Rati Devidze, Xiaojin Zhu, and Adish Singla. Policy teaching in reinforcement learning via environment poisoning attacks. Journal of Machine Learning Research, 22(210):1-44 45, 2021.
[33] Chung-Chin Shih, Ti-Rong Wu, Ting Han Wei, and I-Chen Wu. A novel approach to solving goal-achieving problems for board games. Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 10362-10369, 2022.
12


Reviews:
[{"review_id": "pfvJaUfAk2b", "reviewer": "Reviewer_nfAu", "summary": "The author proposes the first adversarial attack on AlphaZero, including value attack and policy attack, to fool the target agent’s value and the policy output respectively. The paper also develops an efficient trick and a bound rule to reduce the time complexity. By adding one or two meaningless stones, agents on different datasets are vulnerable to those “adversarial examples”.", "questions": "N/A", "limitations": "Please refer to the weaknesses.", "rating": 3, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n1. It is the first paper to discuss how Go agents perform against adversarial examples.\n2. The paper is in good shape and it is easy to follow.\n3. The method is technically sound.\n\nWeaknesses\n1. Although this paper is the first one that investigates the robustness of Go agents, I am more concerned about whether the definition of adversarial example in fooling Go agents is different from that in other fields, and this difference determines whether it is meaningful to investigate. As we all know, remarkable characteristics of the adversarial example in the traditional field are the wrong prediction of the model and the meaningless but inconspicuous disturbance itself. I know the authors repeatedly emphasize that using the proposed method will generate meaningless stones and make the agents behave abnormally, but these actions do not conform to the traditional sense of imperceptibility. Moreover, the most surprising point of adversarial examples at present is that there seemingly exists an inevitable phenomenon between the robustness and accuracy of the ML model, that is, adversarial training will reduce the performance of any model in identifying clean samples. But considering the case given in this paper, I tend to believe the lack of appropriate training strategy is the main reason for the misprediction given by the agent, rather than the so-called “adversarial example”.\n2. For the evaluation experiments, I am a little confused why these works [1][2][3] cannot be good baselines for evaluating the performance of the proposed method to attack AZ agents.\n\n[1] Zhang, Xuezhou, et al. \"Adaptive reward-poisoning attacks against reinforcement learning.\" ICML, 2020.\n\n[2] Zhang, Huan, et al. \"Robust deep reinforcement learning against adversarial perturbations on state observations.\" NeurIPS, 2020.\n\n[3] Gleave, Adam, et al. \"Adversarial policies: Attacking deep reinforcement learning.\" ICLR, 2020.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "hyjdYU8zhEY", "reviewer": "Reviewer_9kDD", "summary": "The paper investigates the vulnerability of AlphaZero (AZ) agents against adversarial attacks. The paper first defines an adversarial example for AZ agents as a state that is perturbed by adding a small number of meaningless actions, which can be verified to be semantically similar to the original state. Then, the paper defines an adversarial attack on a state as successful if the policy-value neural network (PV-NN)s produces wrong predicted values, which leads to suboptimal behavior of the agents in the future. The paper proposes an efficient attack method by exploiting the observation that a meaningful action of a state is also a meaningful action of the prior states and reducing the search space for meaningless actions. The paper empirically shows that PV-NNs are vulnerable to adversarial attacks across different AZ agents.", "questions": "**Some condition for defining the similarity between two states seems artificial.**\n\nAs mentioned in line 182, the authors evaluate the value of s' by $\\max(V(s'), 1-V(\\mathcal{T}(s', a_s^*)))$. However, it is unclear why we should consider the latter term. If the examiner's prior policy outputs an action different from $a_s^*$ as the optimal action for $s'$ (the authors say the policy \"forgets\" to consider the best action), then it implies that the examiner, which is much stronger than the target agent, is fooled by $s'$. So, it is natural to expect that $s'$ will also fool the target agent. I think a clearer explanation of why we consider $a_s^*$ to compute the value of $s'$ is needed. Also, it would be better to report the statistics of the difference between the actual value $V(s')$ and the modified value $\\max(V(s'), 1-V(\\mathcal{T}(s', a_s^*)))$.\n\nAdditional question: Does $a_s^*$ denote the action sampled from the prior policy of the target agent or the action sampled after the MCTS? \n\n**The proposed adversarial scenario seems unrealistic.**\n\nThe paper generates adversarial examples by adding two meaningless (or pass) moves, but I think this does not occur in reality. For example, a Go player who is playing against an AZ-like agent can not utilize this type of attack to fool the opponent since this attack requires both players to do meaningless moves.\n\n", "limitations": "The paper clearly states its limitation in Section 5.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- To the best of my knowledge, it is the first work that examines the adversarial vulnerability of AZ agents and I think it is novel.\n- The paper is well-organized and provides an appropriate figure (Fig. 1) to help readers to understand the new concept of adversarial attacks against AZ agents.\n- The experimental design is good and the paper provides very interesting results (e.g., Results on Different Datasets, Robustness of PV-MCTS).\n\nWeaknesses\n- Some condition for defining the similarity between two states seems artificial (see Questions below).\n- The proposed adversarial scenario seems unrealistic (see Questions below).\n- The paper does not provide any quantitative results showing that the proposed attack method degrades the performance of the target agent, though the paper says that the attacked agent will make mistakes way below their level (line 19).\n- Some grammatical errors: achieve -> achieves (line 4), indicate -> indicates (line 97), denote -> denotes (line 177), Base -> Based (line 264), .", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "d6gP7aNVLvb", "reviewer": "Reviewer_6PMq", "summary": "The authors study the robustness of Alphazero-like agents to adversarial attacks in the game of Go and (to a lesser extent) the game of NoGo. The kind of adversarial attack they focus on are 'semantically invariant' or 'meaningless' perturbations, which are moves toward game states that are legal states but that would normally not (significantly) affect either player's win rate. The perturbations are therefore discrete, which rules out standard gradient-based methods for finding adversarial examples. They formally define 'semantically invariance' and use human verifiers to confirm a move's semantic-meaninglessness, since this is usually hard to define. They find such perturbations within a restricted perturbation set (defined using the value function of an 'examiner', which is a strong player that uses deep MCTS search). They further constrain the perturbation set to moves that were not meaningful in past moves during the game and, finally, by confirming whether each remaining move in the candidate perturbation set passes an attack success criterion. The authors verify their method succeeds through several experiments on different agents, datasets, and MCTS depths (0 vs non-zero).", "questions": "Lines 190-191: I don't understand why it's easier for a human verifier to verify the 1STEP attack than 2STEP attacks. If it's the case, it isn't explained in a way that's easy to understand. \n\nline 197: The implication here seems to be that not both 1STEP and 2STEP moves are constrained to be meaningless. Based on the introduction, I thought meaningless perturbations were the class that the authors were concerned with producing? The text should be clarified here.\n\nline 245: Why do the authors assume that there are N ≈ 150 (the average number of actions for a state) meaningless moves for each state? Is it not likely to be less than the average number of moves? At very least, perhaps N-1 is more justified? ", "limitations": "The authors don't extensively discuss the limitations of their work. How easy is it to apply this method to games such as chess or shogi? Are other methods better for those games, which are less combinatorially challenging than Go? What is the use of this method? Is it applicable for adversarial training to improve the robustness of Go-playing agents, or does it have limitations that prevent this? ", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper addresses a somewhat novel problem: How can we efficiently (with limited computation) find meaningless adversarial moves against superhuman opponents in a discrete turn-based game? The authors aptly demonstrate that their method works, not just for Go, but also for a similar game, NoGo, too.\n\nThat the moves are found efficiently (which is challenging due to the combinatorial nature of the game) is noteworthy. However, it is unclear how the author's method compares with prior approaches, in particular Gleave et al. (2019). It isn't obvious to me why Gleave et al.'s method would compare disfavourably in terms of computation (though I'm open to an explanation from the authors as to why they think their method is likely an improvement over Gleave et al.'s). This raises a broader point: given the existence of at least one comparable method, the authors ought to have compared their method with it. This said, it's possible that the authors chose not to compare because the compute requirements would be too great; if so, an explanation about this decision should be added to the paper. \n\nThe paper is sometimes verbose and is occasionally hard to follow. Some of this is due to occasional grammatical errors (which are rare for the most part). My general advice to the authors would be to make the paper easier to skim. Paragraph headings are one way to achieve this and help to break up dense pages of text, of which this paper has a considerable amount. \n\nI also find myself asking why the authors chose 'semantically invariant/meaningless' moves rather than adversarial moves in general. An explanation about this should be given. Nevertheless, a strength of the paper is that it opens up potential future work such that a network may be adversarially trained to be robust against such attacks. \n\nSince the authors constrain their method to legal board states, they should relate their work to \"Natural Adversarial Examples\" (Hendrycks et al. 2021).\n\nOverall I expect the significance of the work to be moderate: Go-like games are a very limited set and lessons aren't readily transferable to real world problems (but if they are, then the authors should discuss this). Nevertheless, the paper is well carried out and solves a tough, albeit narrow, problem. \n\nMinor comments:\n- Consider changing the title to a question that isn't so trivial a priori. Currently, the title is not descriptive of the actually interesting parts of the paper.\n- Please fix the grammar or incomplete sentences in lines 136-138, line 184, line 189, line 194, 264, 566. This is not a complete list; I encourage the authors to look for other errors. \n- Fix the sentence: line 193 \"Hence, if the actual win rate does not change much, even a much weaker verifier like humans can tell does the extra action benefit a player or not.\"\n- I advise giving a brief formal definition of Q(\\cdot) beyond 'action value'. \n- Consider hyphenating \"turn player\" to \"turn-player\" in line 95\n- Line 317: be consistent with Leela capitalization. \n- Unless the authors have good reason not to, I weakly recommend making terminology consistent with prior work (Gleave et al. 2019) by replacing 'target agent' with 'victim'. This would also make the term more informative.\n- The authors should more clearly state at the start that they do most of their experiments on Go, with minimal experiments on one other game, NoGo. \n- The figure would greatly benefit from coloring the perturbation moves. It requires much more effort to understand the figures if one has to look for a tiny letter, whereas it's very easy with color.  \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "G60-DKPejRU", "reviewer": "Reviewer_W67q", "summary": "This work proposed to evaluate the robustness of AlphaZero trained agents for games like Go. The main challenge is that it is hard to define semantically invariant perturbation in discrete games like Go. Therefore, the authors proposed to use action perturbation instead of directly manipulating states to perform attack. The authors constructed two kinds of attack, 1STEP attack and 2STEP attack, and defines what is a qualifying perturbed states given the target agent and a weaker verifier. Realizing the brutal force approach to find an adversarial example is too time-consuming, the authors proposed to make reasonable assumptions that if an action is meaningful for a state, then it is also meaningful for any state before that. Given this assumption, the author proposed a method to reduce the time complexity of finding an adversarial example. The results show that the proposed attack can perform efficient attack on several trained AZ agents under different scenarios. ", "questions": "1. what is exactly the state space? and how do you calculate the L0 distance between states?\n2. intuitively, how to verify that two states s and s' are semantically equivalent? does verifying this require human expertise in the game Go? \n3. condition C3 seems quite strong, requiring the verifier to be able to identify a wrong state. How hard is this for a human player to do?\n4. In line 235, the authors mentioned \"since it only takes on mistake for an agent to lose a game\", why is this true? It seems to me if a normal human player makes a small mistake, they would still be able to save the game with some possibility. Also, please define what is a \"mistake\". \n5. Is there a possibility to completely get rid of human participation in training the attacker?", "limitations": "The authors mentioned that the limitation of the work is that they are only able to identify the adversarial states but haven't been able to guide the AZ agents to those states. This could be a future work to train an attacker which is also an RL agent to attack the AZ agent.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "originality: the paper proposed to solve an interesting problem that is different from existing types of attacks. The proposed solution also seem to work on the mentioned game. This is a strength of the paper. \n\nquality: since the test is done on a challenging AZ game, and the attack success rates are pretty high, I think the paper is of good quality in terms of its experiments and results. However, since this study would involve real humans to verify the results, it can be hard to scale this research, and involving real human to evaluate the results also makes it show to train. \n\nclarity: Some of the description in the paper are kind of confusing for me. First, some mathematical terms are given without any mathematical descriptions. For example, there is no definition of the state space of the game, is that an image or is that a vector containing positions of existing stones of both colors? Second, there are some obscurity in the experiment part, the research involves human participation, however, there is no mentioning of the level of these humans in terms of their expertise level of the game Go, which makes it less convincing. The reason is that not everyone knows the game Go, and even if they know, they may not be experts on this game, and whether an action is meaningless usually also depends on the expertise level of the human. \n\nsignificance: I believe this result is significant for the AZ model itself as it is different from traditional continuous state space RL attack, and the problem is nontrivial, requiring a lot of computation. On the other hand, an adversarial example for an image is easily understandable for a human, but this is not the case for this game since computers can be better than humans at playing the game. The proposed acceleration reduces the attack computation significantly compared with brute-force approach, which makes a big difference.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept