Is "Adversarial Policies Beat Professional-Level Go AIs" simply wrong?

Question

Since 2016, when AlphaGo beat Lee Sedol, probably the world's strongest player, humans have essentially not had a chance against a well-trained AI.

Now, a paper "Adversarial Policies Beat Professional-Level Go AIs" has been uploaded to the ArXiv. Ars Technica provides a nontechnical account: "New Go-playing trick defeats world-class Go AI—but loses to human amateurs". If I understand correctly, the idea is that the adversary takes a small territory in the corner, leaving the larger part to the victim AI, but the adversary plays dead stones in the larger rest of the board. The victim AI, on the one hand, sees these stones as dead, and therefore does not invest moves in killing them. But during scoring, the victim AI apparently does not see them as dead and therefore does not count the large territory as territory.

Here is an example from the Ars Technica article:

Note on the right that the AI believes that black wins by 49.5 points. There are 6.5 points komi, so black should win by 56 points on the board. For the life of me, I can't figure this out - the top right corner is 52 points large and there are no captures. And more importantly, any player of 20-kyu strength or stronger immediately sees that the black stones scattered in the huge white territory are simply, unquestionably, dead - so prior to counting, they should be removed and count as captures for white under any reasonable set of rules.

For instance, the 2002 English language Chinese rules per the link on this page at sensei's say that "After all dead stones are removed from the board, count...". The complete AGA rules say that the players must agree on the status of all stones, and agreed-upon dead stones are removed.

Thus, it seems to me like this does not exploit a weakness in KataGo's go playing ability, but a bona fide bug in its game-end territory counting algorithm. It's rather obviously a bug, because the rules are clear on what should happen in this situation when we count the score, and KataGo obviously does not follow the rules.

The paper notes that they are following the rules of go as codified by John Tromp. I am not conversant with these rules, but it seems to me that if under this codification, the situation above is scored as a win for black, that reflects a weakness in this codification.

It does not make sense to me to publish this under a headline of "beating" KataGo, rather as "we found a bug in the game-end scoring of KataGo" or "we found a surprising consequence of a common codification of the rules of go".

What am I missing?

Answer 1

One of the authors of the paper here. It might shock you to find that I believe the paper was not "simply wrong". I do however think that we did a poor job explaining our evaluation setting, and we plan to rectify that in a paper revision soon. This rule set issue has tripped a lot of people up.

First, I want to clarify what we were trying to investigate in the paper was whether AI systems that in typical situations can outperform humans can still suffer from surprising and non-human failure modes. As another answer to this post notes, machine learning systems in general are often vulnerable to adversarial attack. But in many cases these machine learning systems are vulnerable to, well, a lot of other things: e.g. image classifiers often fail when you change the camera angle, lighting, etc. So it's natural to wonder whether these failures just reflect the system not really being "smart enough" and that it'd go away with more data, bigger models, etc.

We picked Go as an evaluation environment because there are very strong Go-playing AI systems, that can beat the best human players. Moreover, these AI systems haven't just been strong in "the lab" in a controlled tournament setting. They're also used in the real world by many thousands of Go afficionados as a teaching aid, a fun opponent to play against, etc. As any software developer can tell you, a large user base is an excellent (if sometimes painful) way of discovering bugs in your system. So, it's notable that people have for the most part not found many ways of beating these AI systems by hand -- although there are some, e.g. one of the authors of KataGo in his excellent response on Reddit describes "Mi Yuting's flying dagger" opening pattern that some earlier otherwise very strong Go AI systems struggled to handle.

This preamble is to say: our primary focus was to learn something about machine learning, not about Go. Because of this, we aimed to pick an evaluation setting that is fair for KataGo, but not one that necessarily corresponds to human play. This I think is the root of the confusion you and many others experienced. In retrospect we should have expected this, and we're actually working on a follow-up attack now that also wins under standard Chinese/Japanese rule sets.

With that out of the way, what is our evaluation setting, and why do we think it's a reasonable thing to do? We used Tromp-Taylor rules, modified to remove opponent stones from within groups that can be shown to be unconditionally alive via Benson's algorithm. This is the same as "Tromp-Taylor Rules" with "SelfPlay Opts" turned on at the KataGo rules page.

We picked this ruleset as it was the one used during KataGo's original training run reported on in their paper. Our understanding is that later training runs randomized the ruleset to enable KataGo to better transfer to play under human rules, but it still made up a significant fraction of later training data. Crucially, KataGo does know the ruleset it's playing under: it's a configuration option.

A human player might wonder why these strange AI researchers are obsessed with Tromp-Taylor rules. They're often called the "logical rules of Go" because they're simple, which is appealing to a certain kind of person obsessed with Kolmogorov complexity. But the main reason is that it allows for automatic scoring of board games.

Under typical human play, players will decide which stones are dead or alive at the end of the game. That works well for players who know what they're doing. But systems like KataGo learn to play Go from scratch. What does a randomly initialized neural network do here? It'll make completely random predictions about which stones are dead or alive. If we then use these nonsense predictions to train the system -- well, garbage in, garbage out. So, this human convention has a serious bootstrapping problem.

Of course, once the system has learned something about Go, you could switch to a more human style of play. And indeed KataGo configured to play against humans does do this -- it has an auxiliary head of the network that predicts what stones are dead or alive, that it's learned from experience over many games. But it's still risky to use it as an optimization target. If KataGo has a particular blindspot in its dead/alive evaluation, then that blindspot will just get reinforced as it plays against itself.

Tromp-Taylor avoids this problem by, well, just forcing the game to be played out to the end. That'd be annoying to a human, but AI's are quite good at not getting bored. It is a waste of compute and slows down training, which is where KataGo's SelfPlayOpts kicks in. If it can show (not predict, but actually have a guarantee) that a particular group of stones is unconditionally alive (under any sequence of future legal moves) then it'll remove opposing stones within that group. These are stones that are provably dead.

Let's look at the game from the ArsTechnica article quoted in the OP:

Under Tromp-Taylor rules (whether the original, or the "modified" version used by KataGo) this is a win for black, the adversary. But if they were playing in any human tournament, it'd surely be called a win for white. What's the difference here?

Well, the black stones in the lower-left are clearly very weak. They could be captured by white with little work. Black's territory in the top-right looks fairly secure, but it's pretty small. So, a polite pair of human players would agree the black stones in the lower-left are dead, and declare a win for white. If they really couldn't agree, a referee might be called, or the match might restart.

However, the white territory in the lower-left isn't "unconditionally alive" in the sense of Benson's algorithm. If the white player plays sufficiently badly (you can imagine it's trying to lose, even), then it could lose that territory. So, the black stones in the lower-left territory don't get removed under KataGo's "SelfPlayOpts".

Scoring then proceeds with regular Tromp-Taylor rules. This scoring rule gives points for each stone of the color (which is about even between black and white), plus the number of empty points that reach only that color (this is none for white, but black gets all of the top-right). So, black wins.

Now this does all feel rather contrived from a human perspective. But remember, KataGo was trained with this rule set, and configured to play with it. It doesn't know that the "human" rules of Go are any more important than Tromp-Taylor. In general, we want AI systems to do well at the thing we trained them to do: if they fail at that, but do great at some unrelated task, that's interesting, but not very reassuring.

However, it's an interesting question whether we can find attacks that work under human rules, too. After all, our adversary wasn't trying to win under human rules -- what if we just train it do so? Our provisional results suggest we can, with around a 98% win rate (a bit lower than the 99% in the original paper, but not too bad!) Here's a sneak peek of one game (white is victim, black is adversary). We definitely need to dig more into this before we're confident in the results, but wanted to share it as it may be more interesting from a Go perspective.

Although I can't quite argue for this paper being simply wrong, I do think there is one major limitation: the problem we discover disappears if the victim does enough search. Now even without search KataGo is very strong (we estimate top-1000 professional). So, it's interesting an AI can be so strong and so weak at the same time. But, we've certainly not broken all of computer Go, although we plan to see how far we can push the attack against victims with search (they may still be vulnerable, but it just be harder to find the attack).

Answer 2

Regardless of the validity of this particular strategy, the general technique seems quite valid.

They did not simply discover a bug in KataGo and then write a program to exploit the bug. Rather, they trained another AI to beat KataGo.

It's well known that neural networks used for image classification are vulnerable to adversarial inputs. Given an image classification AI, an attacker can train an image to be strongly recognized as, say, a banana. The image is likely to look nothing like a banana, but nonetheless is strongly recognized as one by the AI. The paper linked in the first sentence includes many example pictures. These pictures are called "adversarial inputs" or "adversarial examples."

This problem seems to be inherent to neural networks as nobody has found a surefire way to avoid it. It's concerning for self-driving cars, because a piece of paper taped to a STOP sign could cause the car to think it's a 150kmph speed limit instead.

Normally these classifiers are pretty good because adversarial examples are very specific random-looking images which nobody would stumble across by accident - but we know how to create them. Adversarial examples can be created by a similar procedure to AI training, but instead of updating the AI at each step to make the AI output more correct, you update the image that it is trying to classify, to make the AI output more incorrect.

The authors of the paper you referred to applied a similar idea to a Go AI, instead of an image classifier. They used AI training techniques to train an AI that would defeat KataGo, and nothing else. If it did not find this way to trick KataGo, it would find some other way to trick KataGo.

Just like some adversarial images look random but are actually quite specific, it's likely that their AI is placing random-looking stones in very particular places at very particular times in order to trick KataGo into playing more poorly, and you wouldn't get good results by randomly playing stones in this section of the board.

Answer 3

In the Tromp–Taylor rules, the concept of dead stones is left out—all stones on the board at the end of the game are treated as being alive. The KataGo AI was trained primarily using the Tromp–Taylor rules (see the KataGo paper, p. 10). Therefore, the KataGo AI should have captured all of the enemy stones in its territory; the fact that it didn't do so is a failure of the AI.

As you note, one hypothesis is that, in some sense, the KataGo AI thought that it was playing under rules where it didn't need to capture dead stones. However, from reading the adversary paper, I don't see any evidence that the AI was given false information about the rules that it was playing under. If the AI had been given false information, that would have been an enormous blunder on the part of the authors of that paper. Since there's no evidence that the authors made this serious mistake, my belief is that they did not.

You also make the hypothesis that KataGo has a bug in its game-end territory counting algorithm. I don't think that the KataGo AI (the part that decides what move to make, and whether or not to pass) has a game-end territory counting algorithm, so that explanation is impossible.

Furthermore, as you point out, under the standard rules for Go, passing would have been a win for White here. Under the Tromp–Taylor rules, however, it's a loss.

Someone might argue that the Tromp–Taylor rules are flawed, or that they're not really Go, and I don't have any desire to argue against such statements. What seems true, though, is that the adversarial AI successfully beats the KataGo AI at the game that the AI is designed to play.

Answer 4

I think you're right - this isn't much of a weakness in KataGo. It looks like there's a mismatch between the way KataGo plays, and the scoring method they're using. In Tromp-Taylor scoring, White doesn't get any points because there are black stones in White's territory, but KataGo doesn't play this way - it knows none of those stones can live, so it passes. This would be trivial to fix - make KataGo keep playing until the stones are captured.

Answer 5

Of course, anyone with knowledge of Go will think the Black loses a lot in the game shown.
However, the Tromp-Taylor rules are reasonable rules for Go, which is translation of Chinese rule "stones and empty are both territory". Of course, in Chinese rules, the dead stones should be removed before counting points, however, it is just for convenience. On the one hand, the Go game can be ended naturally when both sides are unwilling to play stone on board, though it seems like a waste of time. On the other hand, the conception dead stone is not clear though it is clear to players at most time, therefore Chinese rules preserve dispute resolution through combat.
In fact, in the older rules of Go, the outcome of game only depends on the stones, which is more troublesome than Tromp-Taylor rules because it means players need to fill stones in his own empty. Of course, in actual operation, it evolved into tax rule that is every living group need to deduct two points because all empty can be filled except for two eyes or the group will die. The Japanese rule "seki has no territory" is also from this rule because neither the shared liberty nor eyes can be filled.
Back to the paper, The katago AI is trained accroding to the Tromp-Taylor rules, so I think it is a victory from the perspective of adversarial attack, but this kind of victory is meaningless from perspective of Go.