- Selbst KataGo mit übermenschlicher durchschnittlicher Spielstärke brach in bestimmten Situationen zusammen, und eine adversariale Policy erzielte selbst unter übermenschlichen Einstellungen eine Gewinnrate von über 97 %
- Der Angreifer musste nicht allgemein gut Go spielen, sondern brachte KataGo dazu, früh zu passen und große zyklische Steingruppen unverteidigt zu lassen, wodurch die Bewertung von KataGo aus dem Takt geriet
- Für das Training des Angriffs wurden weniger als 14 % des Trainingsaufwands von KataGo benötigt; gegen no-search KataGo lag die Gewinnrate bei über 99 %, gegen KataGo mit 4096 visits bei 95,7–97,3 % und selbst gegen KataGo mit 10⁷ visits noch bei 72 %
- Dieselbe Schwachstelle ließ sich auch auf andere übermenschliche Go-AIs wie Leela Zero und ELF OpenGo ohne zusätzliches Training (zero-shot) übertragen, und auch menschliche Go-Experten lernten die Strategie ohne algorithmische Hilfe und besiegten mehrere Bots
- Eine kleine Menge adversarialen Trainings stoppte einen festen Angreifer, wurde aber durch weiteres Fine-Tuning erneut umgangen; hohe durchschnittliche Leistung allein garantiert daher keine Robustheit im Worst Case
Adversarialer Policy-Angriff auf KataGo
- Anhand einer Go-AI wird gezeigt, dass selbst AI-Systeme mit schnell steigender Durchschnittsleistung bei der Worst-Case-Performance verwundbar sein können
- Ziel des Angriffs ist KataGo, die zum Zeitpunkt der Veröffentlichung stärkste öffentlich verfügbare Go-AI
- KataGo nutzt Self-Play und ein AlphaZero-artiges Trainingsverfahren
- Es wird ein neuronales Netz mit Policy-Head und Value-Head verwendet, und die Züge werden mit Monte-Carlo Tree Search (MCTS) ausgewählt
- Die neuesten Netze wurden mit mehr als 15.000 V100-equivalent GPU days trainiert
- Wenn sich eine übermenschlich starke KataGo erfolgreich angreifen lässt, ist das ein Beispiel für die Verwundbarkeit breiterer AI-Systeme
- Der Angreifer darf nur wie ein normaler Spieler Steine setzen oder passen und hat keine besonderen Rechte über die Spielregeln
Bedrohungsmodell und Trainingsverfahren
- Der Angreifer hat Gray-Box-Zugriff und kann das neuronale Netz des Zielagenten für beliebige Eingaben auswerten
- Es gibt keinen direkten Zugriff auf die Netzwerkgewichte
- Es wird angenommen, dass die Policy des Opfers fest ist
- Das passt natürlich zu Fällen, in denen eine kommerzielle oder Open-Source-Go-AI lokal ausgeführt werden kann
- Das Ziel ist nicht einfach, eine stärkere Go-AI zu bauen, sondern Nicht-Transitivität (non-transitivity) auszunutzen, also eine spezifische Schwäche des Opfers offenzulegen
- Der Adversary schlägt KataGo
- KataGo schlägt menschliche Profis
- Menschliche Amateure schlagen den Adversary
- Statt Self-Play wird mit victim-play trainiert
- Adversary und festes Opfer spielen gegeneinander
- Für das Training des Adversary werden nur Daten aus dessen eigenen Zügen verwendet
- Die Forschenden führen Adversarial MCTS (A-MCTS) ein
- Normales MCTS modelliert die gegnerischen Züge mit der eigenen Policy
- A-MCTS modelliert in den Zügen des Opfers dessen Verhalten mit dem Netzwerk des Opfers
- A-MCTS-S sampelt aus dem Policy-Head des Opfers
- A-MCTS-S++ verwendet Mittelung über Brettsymmetrien
- A-MCTS-R modelliert rekursiv sogar die Suche des Opfers, ist aber rechnerisch teuer
Zwei Angriffe: pass-adversary und cyclic-adversary
- pass-adversary ist ein Angriff, der no-search KataGo dazu verleitet, viel zu früh zu passen
- Mit 600 visits wurde gegen die neueste no-search KataGo eine Gewinnrate von 99,9 % erreicht
- Das Training benötigte 20,4 V100 GPU days, also 0,13 % des Trainingsbudgets von Latest
- Unter den Tromp-Taylor-Regeln wird KataGo dazu gebracht, früh zu passen, wenn der Adversary nach Punkten vorne liegt
- Diese Strategie verliert auch gegen menschliche Amateure
- Der gegen ein no-search-Opfer trainierte pass-adversary überträgt sich teilweise auf Opfer mit sehr geringer Suche
- Mit A-MCTS-R erreicht er 88 % Gewinnrate gegen Latest mit 8 visits
- Mit A-MCTS-S unter denselben Bedingungen nur 15 %
- cyclic-adversary ist ein zweiter Angriff, der nach Einführung einer Pass-Verteidigung erneut gegen KataGo entwickelt wurde
- Nachdem eine pass-alive-Verteidigung eingeführt wurde, damit das Opfer nicht mehr durch frühes Passen verliert, wurde neu trainiert
- Gegen Latestdef no-search gewann er 1048 von 1048 Partien, also 100 %
- Auch gegen Latest no-search ohne Verteidigung gewann er 1000 von 1000 Partien
- Das Training benötigte 2223,2 V100 GPU days, etwa 14,0 % des Trainingsaufwands von Latest
Auch übermenschliche KataGo mit Suche wird geschlagen
- cyclic-adversary erzielt auch gegen KataGo mit Suche hohe Gewinnraten
- Gegen Latestdef mit 4096 visits 95,7 % über 1052 Partien
- Gegen Latest ohne Verteidigung mit 4096 visits 97,3 % über 1000 Partien
- Gegen Latest mit 10⁶ visits/Zug 82 % über 50 Partien
- Gegen Latest mit 10⁷ visits/Zug 72 % über 50 Partien
- 10⁷ visits bedeuten selbst auf leistungsfähiger Consumer-Hardware mehr als eine Stunde Auswertung pro Zug und sind daher in vielen Anwendungen keine praktikable Verteidigung
- Mit steigender Suchmenge des Opfers sinkt die Gewinnrate des Adversary
- Suche kann also ein Mittel zur Erhöhung der Robustheit sein
- Vollständige Robustheit entsteht dadurch aber nicht
- Auf Seiten des Adversary lag die beste Leistung bei 128–600 visits
- Über 600 visits hinaus verbesserte sich die Leistung nicht und konnte sogar schlechter werden
- A-MCTS-S++ war nicht besser als das günstigere A-MCTS-S
Wie die zyklische Schwachstelle funktioniert
- Der cyclic-adversary bringt KataGo dazu, große Steingruppen in ringförmigen Mustern zu bilden, und kippt dann durch deren Schlagung die Punktzahl entscheidend
- Das Opfer KataGo sagt während fast der gesamten Partie mit über 99 % Wahrscheinlichkeit einen eigenen Sieg voraus und erkennt die Niederlage erst kurz bevor die große Gruppe geschlagen wird
- In manchen Partien schwankt die Siegprognose während eines Ko-Kampfs stark und konvergiert dann zur sicheren Niederlage
- Die eigene Vorhersage des Adversary ändert sich langsamer und bleibt weniger sicher
- In der Analyse der Aktivierungen zeigt sich der Unterschied zwischen zyklischen und fast identischen nichtzyklischen Positionen in bestimmten Schichten
- In layer 25 ist kein großer Unterschied zu sehen
- In einigen Kanälen von layer 26 erscheint ein klarer Unterschied
- Auch der Unterschied zwischen dem adversarial trainierten Checkpoint cp580 und Latest zeigt ein ähnliches Muster, was darauf hindeutet, dass diese Kanäle mit der zyklischen Verwundbarkeit zusammenhängen könnten
- Hardcodierte Baseline-Angriffe funktionierten gegen Latestdef nicht gut
- Die Edge-Baseline gewann als Weißer gegen Latest ohne Verteidigung fast die Hälfte der Partien
- Das zeigt, dass Latestdef robuster ist als Latest und dass der cyclic-adversary einen vergleichsweise ausgefeilten Exploit gelernt hat
Verteidigungsexperimente und Grenzen
- Mitte Dezember 2022 enthielt das offizielle verteilte Training von KataGo 0,08 % Self-Play-Partien, die aus Positionen mit laufendem cyclic exploit starteten
- Das ist eine schwache Form von adversarialem Training, die das Verständnis zyklischer Positionen verbessern soll, ohne die normale Spielstärke zu beeinträchtigen
- Nach dieser Verteidigung sank die Leistung des bisherigen cyclic-adversary schrittweise
- Gegen b60-s7702m 32 visits KataGo: 0 Siege in 50 Partien
- Gegen b60-s7702m 1 visit: 119 Siege in 2050 Partien
- Nach zusätzlichem Fine-Tuning des cyclic-adversary gegen das adversarial trainierte Netz mit weiteren 1154,9 V100 GPU days erholte sich die Angriffsstärke jedoch teilweise
- Gegen b60-s7702m 4096 visits 47 % Gewinnrate über 400 Partien
- Gegen b60-s7702m 100.000 visits 17,5 % Gewinnrate über 40 Partien
- Die Siege beruhen weiterhin auf dem cyclic exploit, werden aber auf leicht andere Weise erzielt
- Training auf einer kleinen Menge adversarialer Positionen kann einen festen Angreifer stoppen, die Verteidigung generalisiert aber nicht
- Es bleibt möglich, dass mehr adversariales Training den Exploit gegen KataGo rechnerisch infeasible machen könnte, doch dafür wären präzisere scaling laws nötig
Übertragung auf andere Go-AIs und menschliche Spieler
- Der cyclic-adversary wurde nur gegen KataGo trainiert, überträgt sich aber ohne weiteres Training auch auf andere übermenschliche Go-AIs
- 6,1 % Gewinnrate gegen Leela Zero
- 3,5 % Gewinnrate gegen ELF OpenGo
- Da A-MCTS den Gegner als KataGo modelliert, ist das eine schwierige Bedingung, weil Züge von Leela oder ELF fortlaufend unerwartet auftreten
- Einer der Autoren, ein Go-Experte, lernte den Angriff allein aus den Partien des Adversary und ohne algorithmische Hilfe
- Auf dem KGS-Go-Server erzielte er über 90 % Gewinnrate gegen starke KataGo-Bots, die nichts mit den Autoren zu tun hatten
- Er gewann sogar mit einem Vorgabespiel von 9 Steinen
- Er gewann auch gegen KataGo und Leela Zero, die jeweils mit 100k visits spielten
- Später besiegten weitere Menschen mit dem cyclic attack verschiedene starke Go-AIs wie KataGo, ELF OpenGo, FineArt, Leela Zero und Sai
- Der Angreifer konnte die Übertragung durchführen, ohne Gewichte des Zielmodells, Policy-Ausgaben oder große Mengen an Spielprotokollen zu kennen
- Das deutet darauf hin, dass auf Open-Source-Systemen trainierte Angriffe auch auf geschlossene Modelle übertragbar sein können
Reproduzierbarkeit und Fazit
- Code, containerisierte Laufzeitumgebung und Ausführungsanleitungen wurden auf GitHub veröffentlicht
- Beispielpartien sind unter goattack.far.ai verfügbar
- Auf dem KGS-Go-Server wurde einen Monat lang der Bot Adversary0 öffentlich betrieben, der den neuesten Checkpoint des cyclic-adversary ausführt
- Die wichtigsten Ergebnisse wurden auf mehrere Arten reproduziert
- Der KataGo-Entwickler David Wu bestätigte unabhängig die Verwundbarkeit durch passing attack und cyclic attack
- Mehrere Personen aus der Computer-Go-Community bestätigten die zyklische Schwachstelle
- In normalen Partien gegen den KGS-Bot wurden sowohl die zyklische Schwachstelle als auch das Ergebnis reproduziert, dass ein unerfahrener Mensch gegen den Adversary gewinnt
- Auch der menschliche Sieg mit cyclic attack gegen KataGo und mehrere andere Go-AIs wurde reproduziert
- Das Versagen einer übermenschlichen Go-AI ist ein interessantes Beispiel, doch ähnliche Fehler in sicherheitskritischen Systemen wie automatischem Finanzhandel oder autonomen Fahrzeugen könnten schwerwiegende Folgen haben
- Höhere Leistung führt nicht automatisch zu ausreichender Robustheit; nötig sind Investitionen in robustes Training und adversariale Verteidigungstechniken
1 Kommentare
Hacker-News-Kommentare
Zur Einordnung: Das ist eine Arbeit aus Juli 2023, und die Abwehr-Arbeit von September 2024 ist https://arxiv.org/abs/2406.12843
Auf den ersten Blick wirkt es beeindruckend, aber obwohl ich ein wenig über Go und Go-AIs weiß und viel über Schach und Schach-AIs, ist die Arbeit ziemlich schwer zu verstehen.
Es wirkt, als hätte man sich nur die minimale Mühe gemacht zu erklären, was getan wurde und wie das funktionieren kann, und als würde die Kernaussage durch unerklärten Fachjargon verdeckt.
Ich habe das Gefühl, dass die verborgene Idee in Wahrheit erstaunlich einfach sein könnte, aber ganz erkennen kann ich sie nicht.
Im Go gibt es auffallend lange Phasen, die ich als eigentlich schon tot, aber noch lange unterwegs bezeichnen würde. Eine Steingruppe kann im 30. Zug bereits tot sein, aber der Gegner schlägt sie vielleicht erst nach dem 150. Zug tatsächlich.
Wenn der Gegner die Wahrheit schon ab Zug 30 kennt und ich danach über Hunderte Züge in die falsche Richtung gelenkt werde, verliere ich fast sicher.
Diese adversariale AI bringt AlphaGo/KataGo genau in so eine Lage und konzentriert sich nicht darauf, den Vorteil sofort einzustreichen, sondern darauf, die Täuschung aufrechtzuerhalten, damit KataGo die Stellung weiter missversteht. Das heißt: Wenn der beste Zug KataGo aus seinem Irrtum aufwecken würde, ist es besser, den zweitbesten Zug zu spielen und KataGo weiter in diesem verbuggten Zustand zu halten.
Auch adversariales Training hilft nicht: Selbst wenn KataGo diesen Fehler lernt, bleibt er bestehen, und warum, ist nicht klar.
Dieser Bug mit der kreisenden Steingruppe scheint so einfach zu sein, dass sogar Amateure ihn verstehen können. Ich bin ungefähr 10 kyu, also auf einem Niveau, das vom Aufwand her vielleicht Schach mit 1500 Elo entspricht; ich habe also etwas geübt, bin aber nichts Besonderes.
Daher wirkt es so, als könnte selbst ich als Mensch mit etwas Training auf 10-kyu-Niveau AlphaGo/KataGo schlagen.
Wie fast alles andere hat auch Fachjargon offenbar eine Nutzenfunktion, und wenn das Ziel ist, Informationen möglichst klar zu vermitteln, scheint ab einem gewissen Wendepunkt der Ertrag sogar zu sinken. Bei anderen Zielen kann die Nutzenfunktion natürlich auch exponentiell wachsen.
Auch im Schach gibt es solche Grenzfälle, sogenannte Festungsstellungen. Die ersten drei sind „0.0“, und die vierte ist gewonnen für Schwarz.
8/8/8/1Pk5/2Pn3p/5BbP/6P1/5K1R w - - 0 1— Weiß kann den Turm nicht befreien.1B4r1/1p6/pPp5/P1Pp1k2/3Pp3/4Pp1p/5P1P/5K2 b - - 0 1— Der Turm kann nicht in das weiße Lager eindringen.kqb5/1p6/1Pp5/p1Pp4/P2Pp1p1/K3PpPp/5P1B/R7 b - - 0 1— Wenn der Turm nach h1 geht und der König nach g1, kann die Dame nicht über a6 eindringen.2nnkn2/2nnnn2/2nnnn2/8/8/8/3QQQ2/3QKQ2 w - - 0 1— Die Springer rücken wie ein Block vor, sodass ein angegriffener Springer doppelt gedeckt ist.In der ersten Stellung bewerten Stockfish und Lc0 beide Weiß als leicht besser. In der zweiten und dritten sehen sie Schwarz als gewonnen. Die vierte versteht Lc0, Stockfish jedoch nicht.
https://lichess.org/analysis/standard/8/8/8/1Pk5/2Pn3p/5BbP/...
https://lichess.org/analysis/fromPosition/1B4r1/1p6/pPp5/P1P...
https://lichess.org/analysis/fromPosition/kqb5/1p6/1Pp5/p1Pp...
https://lichess.org/analysis/fromPosition/2nnkn2/2nnnn2/2nnn...
Im Go kann es manchmal knifflig sein, gegen völlige Anfänger zu spielen, weil ihre Züge so unvorhersehbar sind und ihre Formen so weit von allem Normalen entfernt liegen. Sehr bizarre Spielweisen funktionieren gelegentlich.
Ich bin europäischer 4-Dan, und egal welchen unorthodoxen Zug ein schwächerer Spieler spielt, ich fege das Brett mit ihm auf. Umgekehrt werde ich von stärkeren Spielern meist noch schneller zerlegt als sonst, wenn ich seltsame Züge wähle. Das funktioniert vielleicht im zweistelligen Kyu-Bereich.
Dann wird die Partie taktisch, und am Ende landet der Gegner in einem schlechten Endspiel. Unglücklicherweise ist dieser Gegner dann gegen Magnus.
Es ist eine Arbeit von 2022, die 2023 überarbeitet wurde, also habe ich sie vielleicht schon einmal gesehen und wieder vergessen. Ziemlich interessant, und ich frage mich, wie gut dieser Ansatz gegen Schach-Engines funktionieren würde, zumindest gegen Engines im Leela-Stil.
Das erinnert mich daran, dass Schachspieler auch nach Deep Blue bessere Strategien gegen Computer gelernt haben. Der Zustandsraum im Go ist viel größer, daher gibt es davon vermutlich deutlich mehr.
Im Grunde nutzt man die Bewertungsfunktion auf ähnliche Weise aus.
Wie im Schach wird letztlich mehr Rechenleistung gewinnen, und genau das hat sich bereits gezeigt. Man sollte sich daran erinnern, dass Elo ein Maß für Sieg und Niederlage ist, nicht für Schwierigkeit. Wenn man beides verwechselt, verschlechtert das die Schlussfolgerungen.
Zur Einordnung: Eine Diskussion über diesen Angriff von Ende 2022 gibt es in [1]. Darin findet sich insbesondere ein längerer Beitrag des Entwicklers von KataGo, hexahedron / lightvector, das wohl die am weitesten verbreitete übermenschliche Go-AI ist.
Der Link führt mitten in einen Thread, weil die spätere überarbeitete Fassung der Arbeit interessanter war als die frühe Version.
[1] https://forums.online-go.com/t/potential-rank-inflation-on-o...
Wenn man raffinierte Fallen entwerfen kann, scheint das zu bedeuten, dass man ein ähnlich hohes Wissensniveau über das Spiel hat, und ich hätte erwartet, dass eine hochqualifizierte AI adversariale Strategien implizit bereits mit abdeckt. Ein interessantes Ergebnis.
Leitern sind eine einfache Form, die selbst lockere Amateure lernen müssen, wenn sie die niedrigsten Grade hinter sich lassen wollen.
KataGo erkennt diesen Fehler und hat einen expliziten Leiter-Löser, der in klassischem Code geschrieben ist. Das neuronale Netz scheint Leitern nie zuverlässig zu erkennen. Warum tiefe neuronale Netze ein so einfaches Muster nicht erfassen, ist nicht klar.
Deshalb wäre es nicht überraschend, wenn diese AIs noch weitere, tiefere Muster übersehen.