Hacker News Reader

Comment by billforsternz | Hacker News Reader

This seems amazing at first sight. It's probably just me, but I find the paper to be very hard to understand even though I know a little bit about Go and Go AI and a lot about chess and chess AI. They seem to expend the absolute minimum amount of effort on describing what they did and how it can possibly work, unnecessarily using unexplained jargon to more or less mask the underlying message. I can almost see through the veil they've surrounded their (remarkable and quite simple?) ideas with, but not quite.

View on HN

https://slideslive.com/39006680/adversarial-policies-beat-su...

Seems to be a good intro.

Go uniquely has long periods of dead-man walking, as I like to call it. Your group might be dead on turn 30, but your opponent won't formally kill the group until turn 150 or later.

If your opponent knows the truth all the way back in turn30, while you are led down the wrong path for those hundreds of turns, you will almost certainly lose.

This adversarial AI tricks AlphaGo/KataGo into such situations. And instead of capitalizing on it, they focus on the trickery knowing that KataGo reliably fails to understand the situation (aka it's better to make a suboptimal play to keep KataGo tricked / glitched, rather than play an optimal move that may reveal to KataGo the failure of understanding).

Even with adversarial training (IE: KataGo training on this flaw), the flaw remains and it's not clear why.

------

It appears that this glitch (the cyclical group) is easy enough for an amateur player to understand (I'm ranked around 10kyu, which is estimated to be the same level of effort as 1500Elo chess. Reasonably practiced but nothing special).

So it seems like I as a human (even at 10kyu) could defeat AlphaGo/KataGo with a bit of practice.

Aji is the concept of essentially making lemonaid from lemons by using the existence of the dead stones to put pressure on the surrounding pieces and claw back some of your losses.

Because they haven’t been captured yet they reduce the safety (liberties) of nearby stones. And until those are fully settled an incorrect move could rescue them, and the effort put into preventing that may cost points in the defense.

The statement that the flaw remains is wrong. We included a few cyclical groups in the training data and the flaw disappeared rather quickly. It is even less of an issue after the move to a slightly larger DCNN.

The current consensus in the community is, as far as I can tell, that there will always be some (other) flaws. But finding and exploiting them is becoming so difficult that it is perhaps impossible for human ingenuity. Automated approaches could succeed, but it is not clear that their effort is less than "simply" training a second, inherently stronger DCNN instead.

The Go community will of course be more interested in performance on Go, but the paper mainly contributes to the debate about the real capabilities of deep neural net models. From the abstract:

Our results demonstrate that even superhuman AI systems may harbor surprising failure modes.

This should be read as a general observation and not just specific to Go as is made clear by reading the paper. So you can patch up Go-specific flaws but the problem remains that deep neural net performance is inconsistent and unreliable.

Thank you. So the attack somehow sets up a situation where AlphaGo/KataGo is the dead man walking? It doesn't realise at move 30 it has a group that is dead, and continues not to realise that until (close to the time that?) the group is formally surrounded at move 150?

I still don't really understand, because this makes it sound as if AlphaGo/KataGo is just not very good at Go!

To be clear, this is an adversarial neural network that automatically looks for these positions.

So we aren't talking about 'one' Deadman walking position, but multiple ones that this research group searches for, categorizes and studies to see if AlphaGo / KataGo can learn / defend against them with more training.

I'd argue that Go is specifically a game where the absurdly long turn counts and long-term thinking allows for these situations to ever come up in the first place. It's why the game is and always fascinated players.

-------

Or in other words: if you know that a superhuman AI has a flaw in its endgame calculation, then play in a deeply 'dead man walking' manner, tricking the AI into thinking it's winning when in truth its losing for hundreds of moves.

MCTS is strong because it plays out reasonable games and foresees and estimates endgame positions. If the neural nets oracle is just plain wrong in some positions, it leads to incredible vulnerabilities.

I think I'm starting to see after reading these replies and some of the linked material. Basically the things that confused me most about the rules of go when I first looked at it are playing a role in creating the attack surface: How do we decide to stop the game? How do we judge whether this (not completely surrounded) stone is dead? Why don't we play it out? Etc.

Most rulesets allow you to "play it out" without losing points. Humans don't do it because it's boring and potentially insulting or obnoxious.

Judging whether something "is dead" emerges from a combination of basic principles and skill at the game. Formally, we can distinguish concepts of unconditionally alive or "pass-alive" (cannot be captured by any legal sequence of moves) and unconditionally dead (cannot be made unconditionally alive by any sequence of moves), in the sense of Benson's algorithm (https://en.wikipedia.org/wiki/Benson%27s_algorithm_(Go) , not the only one with that name apparently). But players are more generally concerned with "cannot be captured in alternating play" (i.e., if the opponent starts first, it's always possible to reach a pass-alive state; ideally the player has read out how to do so) and "cannot be defended in alternating play" (i.e., not in the previous state, and cannot be made so with any single move).

Most commonly, an "alive" string of stones either already has two separate "eyes" or can be shown to reach such a configuration inevitably. (Eyes are surrounded points such that neither is a legal move for the opponent; supposing that playing on either fails to capture the string or any other string - then it is impossible to capture the string, because stones are played one at a time, and capturing the string would require covering both spaces at once.)

In rarer cases, a "seki" (English transliteration of Japanese - also see https://senseis.xmp.net/?Seki) arises, where both player's strings are kept alive by each others' weakness: any attempt by either player to capture results in losing a capturing race (because the empty spaces next to the strings are shared, such that covering the opponent's "liberty" also takes one from your own string). I say "arises", but typically the seki position is forced (as the least bad option for the opponent) by one player, in a part of the board where the opponent has an advantage and living by forming two eyes would be impossible.

Even rarer forms of life may be possible depending on the ruleset, as well as global situations that prevent one from reducing the position to a sum of scores of groups. For example, if there is no superko restriction, a "triple ko" (https://senseis.xmp.net/?TripleKo) can emerge - three separate ko (https://senseis.xmp.net/?Ko) positions, such that every move must capture in the "next" ko in a cycle or else lose the game immediately.

It gets much more complex than that (https://senseis.xmp.net/?GoRulesBestiary), although also much rarer. Many positions that challenge rulesets are completely implausible in real play and basically require cooperation between the players to achieve.

Sorry this is mostly way over my head, but perhaps you can explain something to me that puzzled me when I looked at go 50 odd years ago now.

(Please note, I absolutely do understand life requires two eyes, and why that is so, but my knowledge doesn't extend much further than that).

So hypothetically, if we get to the point where play normally stops, why can't I put a stone into my opponent's territory? I am reducing his territory by 1 point. So he will presumably object and take my "dead" stone off, first restoring the balance and then penalising me one point by putting the newly captured stone in my territory. But can't I insist that he actually surrounds the stone before he takes it off? That would take four turns (I would pass each time) costing him 4 points to gain 1. There must be a rule to stop this, but is it easily formally expressed? Or is it a) Complicated or b) Require some handwaving ?

> So hypothetically, if we get to the point where play normally stops, why can't I put a stone into my opponent's territory? I am reducing his territory by 1 point. So he will presumably object and take my "dead" stone off, first restoring the balance and then penalising me one point by putting the newly captured stone in my territory. But can't I insist that he actually surrounds the stone before he takes it off? That would take four turns (I would pass each time) costing him 4 points to gain 1. There must be a rule to stop this, but is it easily formally expressed? Or is it a) Complicated or b) Require some handwaving ?

There are multiple scoring systems (American, Chinese, and Japanese and a couple of others).

* In Chinese scoring, stones do NOT penalize your score. So they capture your stone and gain +1 point, and lose 0 points.

* In American scoring, passing penalizes your score. So you place a stone (ultimately -1 point), they place 4 stones (-4 points), but you pass a further 4 points (4x passes == -4 more points). This ends with -4 points to the opponent, but -5 points to you. Effectively +1 point differential.

* In Japanese scoring, the player will declare your stone dead. Because you continue to object the players play it out. Once it has been played out, time is rewound and the state of the stones will be declared what both players now agree (ie: I need 4 stones to kill your stone, if you keep passing I'll kill it).

---------

So your question is only relevant to Japanese scoring (in the other two systems, you fail to gain any points). And in Japanese scoring, there is the "time rewind" rule for post-game debate. (You play out positions only to determine alive vs dead if there's a debate. This is rarely invoked because nearly everyone can instinctively see alive vs dead).

IE: In Japanese scoring, the game has ended after both players have passed. Time "rewinds" to this point, any "play" is purely for the determination of alive vs dead groups.

In all three cases, playing out such a position is considered a dick move and a waste of everyone's time.

Thanks - I've had to do basically this exact explanation countless times before. It'd be nice if there were an obvious place to refer people for this info.

That said, when I teach beginners I teach them Chinese scoring and counting. If they understand the principles it'll be easy enough to adapt later, and it doesn't change strategy in a practical way. They can play it out without worry, it makes more sense from an aesthetic standpoint ("you're trying to have stones on the board and keep them there, or have a place to put them later" - then you only have to explain that you still get points for the eyes you can't fill).

It's also IMX faster to score on 9x9: you can shift the borders around (equally benefiting both players) to make some simple shapes and easily see who has the majority of the area and you aren't worrying about arranging territories into rectangles.

Than you, a longstanding mystery (for me) solved!

Amusingly, the endgame ritual is the same for all styles.

You play every good move. Then you traditionally play the neutral moves (+0 points to either player) to make counting easier. Then the game ends as both players pass.

In Chinese, American, or Japanese scoring, this process works to maximize your endgame score.

Chess is Python and Go is, uh, Go?

This is not a reasonable summary. The adversarial AI is not finding some weird position that relies on KataGo not understanding the status. It's relying, supposedly, on KataGo not understanding the ruleset which uses area scoring and doesn't include removing dead stones (because in area scoring you can always play it out without losing points, so this is a simple way to avoid disputes between computers, which don't get bored of it).

I assume that KataGo still has this "flaw" after adversarial training simply because it doesn't overcome the training it has in environments where taking dead stones off the board (or denying them space to make two eyes if you passed every move) isn't expected.

See https://boardgames.stackexchange.com/questions/58127 which includes an image of a position the adversarial AI supposedly "won" which even at your level should appear utterly laughable. (Sorry, I don't mean to condescend - I am only somewhere around 1dan myself.)

(ELO is sometimes used in Go ranking, but I don't think it can fairly be compared to chess ranking nor used as a metric for "level of effort".)

There are multiple examples from this research group.

I believe my discussion above is a reasonable survey of the cyclic attack linked to at the beginning of the website.

https://goattack.far.ai/game-analysis#contents

What we need are more sides to the argument. I'm pretty sure you're both off.

zahlman doesn't seem to have read the part of the paper dealing with cyclic adversaries, but the cyclic adversary strategy doesn't depend on KataGo mis-classifying alive or dead groups over long time horizons. If you watch the example games play out, KataGo kills the stones successfully and is trivially winning for most of the game. It makes a short term & devastating mistake where it doesn't seem to understand that it has a shortage of liberties and lets the adversary kill a huge group in a stupid way.

The mistake KataGo makes doesn't have anything to do with long move horizons, on a long time horizon it still plays excellently. The short horizon is where it mucks up.

I don't suppose you could directly link to a position? It would be interesting to see KataGo make a blunder of the sort you describe, because traditional Go engines were able to avoid them many years ago.

Consider the first diagram in the linked paper (a, pg 2). It is pretty obvious that black could have killed the internal group in the top-right corner at any time for ~26 points. That'd be about enough to tip the game. Instead somehow black's group died giving white ~100 points and white wins easily. Black would have had ~50 moves to kill the internal group.

Or if you want a replay, try https://goattack.far.ai/adversarial-policy-katago#contents - the last game (KataGo with 10,000,000 visits - https://goattack.far.ai/adversarial-policy-katago#10mil_visi...} - game 1 in the table) shows KataGo with a trivially winning position around move 200 that it then throws away with a baffling sequence of about 20 moves. I'm pretty sure even as late as move 223 KataGo has an easily winning position, looks like it wins the capture race in the extreme lower left. It would have figured out the game was over by the capture 8 moves later.

I see what you mean.

So dead man walking is a bad description. From your perspective it's still KataGo winning but a series of serious blunders that occurs in these attacks positions.

Some amount of jargon is needed (in general, not just for this) to optimize communication among experts, but still, your comment reminded me of Pirsig’s concept (IIRC introduced in his second book, “Lila”) of the “cultural inmune system”, as he did bring jargon up in that context too.

I guess, unsurprisingly, for jargon it is as for almost anything else: there’s a utility function with one inflection point past which the output value actually becomes less (if the goal is to convey information as clearly as possible, for other goals, I guess the utility function may be exponential …)

Reply on news.ycombinator.com