38

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:

go board

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?

5
  • 1
  • 2
    @user253751: trust me, they are. Of course, a 9p (professional 9th dan player) playing against a 30-kyu (someone who has just learned the rules) would probably get some of them to live, e.g., the three ones in the middle, so "dead" always depends to a degree on the relative strength of the two players. But in a situation where someone/-thing plays an even game against KataGo, these stones are stone dead. (I have been playing go for 30 years and am about 1-kyu.) Nov 10, 2022 at 7:40
  • 1
    I don't think there is a clear boundary where players above a certain strength know they are dead; I would expect most beginners to think the stones can live, and most dan players to know they can't. Many in between might think either or be unsure. I think most players learn this just by being told, or by specifically practicing trying to live or kill in such circumstances. It's hard for a kyu player to learn this knowledge from actual play, because against other kyu players they can live sometimes, and against dan players, their stones' death is easily explained by the opponent's strength.
    – kaya3
    Nov 11, 2022 at 20:57
  • 1
    It was not mentioned here yet, but I think it is critically important: The paper says "We were only able to perform a manual exploit when the friendlyPassOk flag in KataGo was set to true. This flag makes KataGo more willing to pass. However, this flag is set to false in all of our training and evaluation runs."
    – mafu
    Nov 16, 2022 at 13:50
  • I would rather hear from the KataGo team about this than the team that wrote the paper, frankly. Dec 28, 2023 at 2:59

5 Answers 5

68
+100

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:

Example adversarial Go game

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

8
  • 23
    Adam, thanks a lot for taking the time to write up such a long and detailed answer. I truly appreciate this and now think I understand better where you are coming from and where I got confused. I particularly like your explanation about just why the Tromp-Taylor ruleset does what it does in the context of computer go. I apologize for the clickbaity title ("wrong") and hope you won't hold it against me. All the best for your paper, I'm looking forward to reading future or published versions (maybe you'd like to mention any such here?)! Nov 10, 2022 at 7:52
  • 6
    I'm glad you found the response useful! We have a somewhat clickbaity paper title so I think we deserve clickbait questions about us :) I'll be sure to post paper updates to this thread. Nov 10, 2022 at 17:18
  • 3
    So the bug is not in the evaluation of the end situation, but in deciding to stop playing here (as by just continuing, it could have killed thos stones). Nov 11, 2022 at 0:43
  • 4
    @PaŭloEbermann, which raises the question of why exactly it decides to stop playing? The article mentions "tricking KataGo into ending the game prematurely", even though it "predicts a high win probability for itself". But if it knows the rules, it should know that the current immediate position is losing, however positive an outlook it has. Well, at least if it bothers to actually evaluate the current position to begin with. And with the explicit mention that this is the ruleset it was trained on, I'm not sure I really get it, why does it pass?
    – ilkkachu
    Nov 11, 2022 at 8:41
  • 2
    "We have a somewhat clickbaity paper title" - uh, understate much? I can't even make heads or tails of the title: "New Go-playing trick defeats world-class Go AI—but loses to human amateurs". Meaning, KataGo can defeat AlphaGo but humans can still beat KataGo? ... @OP, An "open source Go-playing AI" has bugs? Say it ain't so....
    – Mazura
    Nov 11, 2022 at 23:43
15

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.

5
  • 2
    "Adversarial" inputs can sometimes arise without deliberate malicious intent. I recall a seeing a video of a self-driving car that was completely flumoxed by a road services vehicle that was carrying a bunch of traffic signals for installation. The person who put the traffic signals in the truck wasn't trying to flummox self-driving cars, but thought it would be obvious that the signals in the back of the truck weren't active. The AI, however, had no notion that signals might appear in such circumstances.
    – supercat
    Nov 11, 2022 at 15:18
  • 3
    @supercat Back in the late 90s, the professor teaching intro-to-neural-networks at CSU Chico (she also taught logic-programming classes, the other AI flavor) brought up an example of an AI having been trained on examples of US and Russian tanks having instead learned to distinguish between arial photos taken under ideal circumstances (the "friendly" tanks' training data was all taken under clear skies from optimal angles &c) and those taken under suboptimal circumstances. I'm not so sure I would call every place where an AI takes the wrong lesson from its training data adversarial, though. Nov 11, 2022 at 17:57
  • 1
    I don't agree that it would have found some other way to beat KataGo. They should fix this trivial bug in KataGo, and run their adversarial strategy again. If it actually can win a game, that would be an impressive result.
    – TimK
    Nov 12, 2022 at 21:46
  • 1
    It does not “trick KataGo into playing more poorly”, unless you including deciding when to pass in “playing”. KataGo set up a won position but stopped playing too soon.
    – PJTraill
    Nov 24, 2022 at 22:44
  • @PJTraill in general, an adversarial AI attack will find some completely unexpected weakness. Nobody can predict that particular random noise picture will cause the AI to think it's a dog, before running the attack. Nov 25, 2022 at 12:09
11

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.

3
  • 1
    @Kevin That doesn't make a difference. For the example game that's pictured in the question, neither player has any pass-alive territory at all, so KataGo should have played on. Nov 10, 2022 at 2:52
  • @Kevin: see senseis.xmp.net/?PassAlive : pass-alive means “cannot be captured even if the owner makers no further move”, so Tanner is right.
    – PJTraill
    Nov 10, 2022 at 8:12
  • "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." - AIs don't know what rulesets are. They only know their own evaluation of the position; and as far as I know, KataGo simply can't be configured to evaluate the position in a way compatible with Tromp-Taylor - as this ruleset practically requires capturing stones that it has been (correctly, for its normal application) trained to consider irrelevant. May 14 at 12:28
6

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.

6
  • 2
    Hm. But per the screenshot above, it apparently doesn't know the stones are dead during scoring. Because then it would remove them and give a huge win for white. It looks like there is a disconnect on detection of dead opponent stones during the game (where KataGo seems to understand the situation and doesn't invest moves in capturing dead stones) and after the game. I'd call this a bug, but I don't think the solution would be to have KataGo play on to capture all these stones. The solution should be to correctly detect and treat dead stones at scoring. Nov 9, 2022 at 13:20
  • 2
    Since the setup for this experiment involves one AI (KataGo) playing against a different AI (the one created by the experimenters), it seems likely that the scoring is not being done by KataGo itself, but by another system that is separate from both of those. Unless I'm missing something, I don't see any indication that the scores there are produced by KataGo itself.
    – murgatroid99
    Nov 9, 2022 at 15:52
  • Then again, under Japanese rules, playing until the stones are captured would lose points... (assuming the other player keeps passing in the meanwhile). Instead, there's that separate step of verifying whether some set of stones is dead or not. All of which just goes to show that it's just an issue of a mismatch between the rules the AI thinks it's playing under, and the rules actually used by the system to determine the result.
    – ilkkachu
    Nov 9, 2022 at 17:23
  • 4
    Do you have any additional evidence that "KataGo doesn't play this way"? The original paper about KataGo states that it was trained using Tromp–Taylor scoring. Nov 9, 2022 at 19:08
  • 1
    @TimK That only proves that under Tromp-Taylor scoring it was playing badly. This seems a weak piece of evidence when weighted against the fact that the KataGo team specifies that it is trained under Tromp-Taylor.
    – Taemyr
    Nov 11, 2022 at 13:08
1

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.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .