AlphaZero: Googles KI meistert Schach und Go in 24 Stunden

Brettspiele (wie Schach) sind ein seit Langem untersuchtes Feld in der Geschichte der künstlichen Intelligenz. Pioniere wie Turing, Babbage, von Neumann und Shannon entwickelten Theorien, Algorithmen und Hardware zur Analyse und zum Spielen von Schach. In den letzten Jahren sahen wir ähnliche Programme, die Menschen in weit komplexeren Spielen wie Go und Shogi (japanisches Schach) übertreffen.

Googles DeepMind hat eine phänomenale Erfolgsbilanz, wenn es darum geht, Menschen bei Brettspielen zu schlagen. 2015 wurde ihr Projekt AlphaGo das erste Computer-Go-Programm, das einen Menschen (einen professionellen Go-Spieler) besiegte. Nun entwickelten sie ein AlphaGo-Programm, das Schach selbstständig lernt und Menschen oder jedes andere Computerprogramm (einschließlich Stockfish und Deep Blue) in fast 4 Stunden schlägt.

Konventionelle KI-Programme (für Brettspiele) sind hochgradig auf ihre Domäne optimiert und lassen sich ohne menschlichen Eingriff nicht auf andere Probleme verallgemeinern. AlphaZero hingegen erreicht übermenschliche Leistung in mehreren anspruchsvollen Domänen. Ohne Vorwissen außer den Spielregeln und aus zufälligem Spiel beginnend, erreichte AlphaZero innerhalb von 24 Stunden ein übermenschliches Spielniveau in Schach, Shogi und Go und besiegte jeweils das weltweit beste Programm. Wie haben sie das gemacht und was sind die genauen Ergebnisse? Finden wir es heraus.

Methodik

Im Oktober 2017 verkündete DeepMind, dass ihr AlphaGo-Zero-Algorithmus übermenschliche Leistung mittels Deep Convolutional Neural Network und reinem Reinforcement Learning erzielte. Ingenieure nutzten denselben Ansatz, um einen generischen Algorithmus namens AlphaZero zu bauen, der die domänenspezifischen Augmentierungen und handgefertigten Kenntnisse konventioneller Spielalgorithmen durch tiefe neuronale Netze und einen tabula-rasa-Reinforcement-Learning-Algorithmus ersetzt.

AlphaZero verwendet den allgemeinen MCTS (Monte-Carlo Tree Search) anstelle von Alpha-Beta-Suche. Es lernt Werteschätzungen und Zugwahrscheinlichkeiten, indem es gegen sich selbst spielt, und nutzt die gelernten Informationen, um seine Suche zu leiten.

Unterschied zum AlphaGo-Zero-Algorithmus

Der AlphaGo-Zero-Algorithmus schätzt und optimiert die Gewinnwahrscheinlichkeit, wobei binäre Gewinn-oder-Verlust-Ergebnisse berücksichtigt werden. AlphaZero hingegen schätzt und optimiert den erwarteten Ausgang, wobei Unentschieden und andere potenzielle Ergebnisse einbezogen werden.

Die Go-Spielregeln sind invariant gegenüber Spiegelung und Rotation. Dies wird in AlphaGo und AlphaGo Zero auf zwei Arten genutzt:

• Trainingsdaten werden durch Erzeugen von 8 Symmetrien für jede Position augmentiert.
• Position wird vor der Berechnung durch das neuronale Netz im MCTS-Algorithmus durch zufällige Spiegelung oder Rotation transformiert, sodass die Berechnung über verschiedene Biases gemittelt wird.

Bei Schach und Shogi sind die Regeln asymmetrisch; man kann keine Symmetrien allgemein annehmen. In AlphaZero werden Trainingsdaten nicht augmentiert und Brettpositionen während MCTS nicht transformiert.

AlphaGo Zero nutzt den besten Spieler früherer Iterationen zur Generierung von Self-Play-Spielen. Nach jeder Iteration wird die Leistung des neuen Spielers gegen den besten Spieler evaluiert. Gewinnt er mit 55 % Marge, wird der beste Spieler ersetzt und Self-Play-Spiele werden vom neuen Spieler generiert. AlphaZero hingegen unterhält ein einzelnes neuronales Netz (kontinuierlich aktualisiert) statt zu pausieren, bis eine Iteration abgeschlossen ist.

AlphaZero Optimierung und Training

AlphaZero nutzt Hyperparameter für alle Spiele ohne spielspezifische Optimierung. Zur Erkundung wird ein Rauschfaktor integriert, der proportional zur Anzahl legaler Züge für diesen Spieltyp skaliert wird.

Wie bei AlphaGo Zero wird der Brettzustand durch räumliche Ebenen kodiert und Aktionen durch räumliche Ebenen oder einen flachen Vektor, basierend auf den Grundregeln jedes Spiels.

Entwickler wandten AlphaZero auf Schach, Shogi und Go an. Dieselbe Netzwerkarchitektur, Hyperparameter und Einstellungen wurden für alle 3 Spiele verwendet. Eine individuelle Instanz des Algorithmus wurde für jedes Spiel trainiert. Ausgehend von zufällig initialisierten Parametern dauerte das Training 700.000 Schritte, wobei 5.000 Tensor Processing Units (TPUs) erster Generation für Self-Play-Spiele und 64 TPUs zweiter Generation zum Trainieren der neuronalen Netze genutzt wurden.

Referenz: arxiv.org

Ergebnisse

Wie in der Abbildung zu sehen, übertraf AlphaZero Stockfish nach 300.000 Schritten (nach 4 Stunden) im Schach; es übertraf Elmo in 110.000 Schritten (innerhalb 2 Stunden); und es übertraf AlphaGo Lee in 165.000 Schritten (nach 8 Stunden).

Die vollständig trainierten Instanzen (3 Tage Training) von AlphaZero wurden gegen AlphaGo Zero, Elmo und Stockfish getestet, jeweils 100 Partien bei einer Bedenkzeit von 1 Minute pro Zug. Die Ergebnisse waren beeindruckend (siehe Tabelle unten).

AlphaGo Zero und AlphaZero nutzten eine einzelne Maschine mit 4 TPUs; Elmo und Stockfish performten optimal mit 64 Threads und 1 GB Hash-Größe. AlphaZero besiegte alle, verlor 8 Partien gegen Elmo und keine gegen Stockfish.

Google-Entwickler untersuchten auch die Performance der MCTS-Suche in AlphaZero. Es sucht 40.000 Positionen pro Sekunde im Shogi und 80.000 im Schach, verglichen mit 35.000.000 für Elmo und 70.000.000 für Stockfish. AlphaZero nutzt sein tiefes neuronales Netz, um sich selektiver auf die vielversprechendsten Optionen zu konzentrieren – einen eher menschlichen Ansatz.

Lesen Sie auch: 15 beste Schachengines basierend auf ihren Ratings

Obwohl AlphaZero noch in den Kinderschuhen steckt, stellt es einen wichtigen Schritt in Richtung seines Ziels dar. Wenn ähnliche Ansätze auf andere strukturierte Probleme angewendet werden können – wie Protein-Folding, Entdeckung neuer Materialien oder Reduzierung des Energieverbrauchs – könnten die Ergebnisse unsere Zukunft positiv beeinflussen.