Großmeister-Niveau im Schach ohne Suche

 (github.com/google-deepmind)
2 Punkte von GN⁺ 2024-10-19 | 1 Kommentare | Auf WhatsApp teilen
  • searchless_chess von Google DeepMind ist die Implementierung des NeurIPS-2024-Papers Amortized Planning with Large-Scale Transformers und bewertet anhand von Schach, wie gut große Transformer Planungsprobleme ohne explizite Suche bewältigen können
  • Der zentrale Datensatz ChessBench besteht aus 10 Millionen Schachpartien mit von Stockfish 16 bereitgestellten Annotationen zu legalen Zügen und Bewertungen, insgesamt 15 Milliarden Datenpunkten
  • Es werden Transformer mit bis zu 270 Millionen Parametern per überwachtem Lernen trainiert; dabei werden die Auswirkungen von Datensatzgröße, Modellgröße, Architekturtyp und Vorhersageziel verglichen
  • Das größte Modell sagt auf neuen Brettern action-value recht genau voraus, löst schwierige Schachrätsel ohne explizite Suche und erreicht gegen menschliche Gegner auf Lichess eine Blitz-Elo von 2895
  • Der suchbasierte Algorithmus von Stockfish lässt sich in großem Maßstab recht gut in große Transformer destillieren, eine vollständige Destillation wurde aber noch nicht erreicht, sodass ChessBench als Benchmark für Folgeforschung bestehen bleibt

Projektziel und Kontext des Papers

  • searchless_chess ist die Implementierung von Amortized Planning with Large-Scale Transformers: A Case Study on Chess
  • Schach dient als klassisches Planungsproblem in der KI, und dieses Projekt bewertet die Leistung von Transformern bei Aufgaben, die selbst im großen Maßstab nicht sinnvoll durch Auswendiglernen lösbar sind
  • Die Forschung prüft am Beispiel Schach, ob sich das Verhalten suchbasierter Schach-Engines per überwachtem Lernen in Transformer destillieren lässt

Der ChessBench-Datensatz

  • ChessBench enthält von Stockfish 16 bereitgestellte Annotationen zu legalen Zügen und Bewertungen
    • Anzahl der Schachpartien: 10 Millionen
    • Gesamte Datenpunkte: 15 Milliarden
    • Stockfish 16 wird als Schach-Engine auf aktuellem Spitzenniveau verwendet
  • Der Datensatz ist nach Vorhersagezielen aufgeteilt

    • Action-Value

    • Behavioral Cloning

    • State-Value

      • puzzles.csv zur Auswertung von Rätseln
      • Beispiele für Download-Größen:
      • Train Action-Value: erster Shard 1.2GB, insgesamt 1.1TB, insgesamt 2148 Shards
      • Train Behavioral Cloning: 34GB
      • Train State-Value: 36GB
      • Test Action-Value: 141MB
      • Test Behavioral Cloning: 4.1MB
      • Test State-Value: 4.4MB
      • Puzzles: 4.5MB

Modelle und Versuchsaufbau

  • Transformer werden mit bis zu 270M Parametern trainiert
  • Das Training erfolgt als überwachtes Lernen auf Basis von ChessBench
  • Die Experimente vergleichen den Einfluss der folgenden Faktoren
    • Datensatzgröße
    • Modellgröße
    • Architekturtyp
    • Vorhersageziel: state-values, action-values, behavioral cloning
  • Das größte Modell sagt action-values auf neuen Brettern recht genau voraus und zeigt damit Generalisierung über bloßes Auswendiglernen hinaus

Leistung ohne Suche und Vergleichssysteme

  • Die finale Schach-Policy löst schwierige Schachrätsel ohne explizite Suche
  • Gegen menschliche Gegner auf Lichess im Blitz erreicht sie Elo 2895 und damit Leistung auf Großmeister-Niveau
  • Zu den Vergleichssystemen gehören Leela Chess Zero und AlphaZero
    • Beide Systeme werden als per Self-Play trainierte Modelle verglichen
    • Es werden sowohl Varianten mit als auch ohne Suche verglichen
  • Der suchbasierte Algorithmus von Stockfish lässt sich in großem Maßstab sehr gut durch große Transformer approximieren und destillieren, eine vollständige Destillation ist jedoch noch nicht möglich

Aufbau des Repositories und Ausführungsablauf

  • Die wichtigsten Verzeichnisse und Dateien haben folgende Rollen
    • src/engines: Schnittstellen für Stockfish, Leela Chess Zero und neuronale Engines
    • src/transformer.py: Decoder-only-Transformer
    • src/train.py: Beispielskript für Training und Evaluation
    • src/puzzles.py: Skript zur Auswertung von Rätseln
    • src/tournament.py: Skript für Elo-Turniere
    • src/searchless_chess.ipynb: Notebook zur Analyse des Modellverhaltens
    • src/tokenizer.py: Tokenisierung des Schachbretts
  • Vorgefertigte Checkpoints werden für die Modelle 9M, 136M und 270M bereitgestellt
  • Im Notebook zur Analyse des Modellverhaltens lassen sich Auswertungen wie die Berechnung der Gewinnwahrscheinlichkeit für alle legalen Züge durchführen

Installation und Abhängigkeiten

  • Die Laufzeitumgebung setzt Python 3.10 voraus
  • Die benötigten Abhängigkeiten werden mit pip install -r requirements.txt installiert
  • Wenn eine GPU vorhanden ist, wird für schnelleres Training eine CUDA-fähige JAX-Installation empfohlen
    • Im Beispiel wird der Installationsbefehl für jax[cuda12_pip] unter CUDA 12 verwendet
    • Die JAX-Version muss zur verwendeten CUDA-Installation passen
  • Externe Engines und Werkzeuge müssen zusätzlich installiert werden

Bewertung und Verwendung

  • Lokales Training wird in src mit python train.py ausgeführt
    • Checkpoints werden unter /checkpoints/local gespeichert
  • Die Auswertung von Rätseln wird in der Form python puzzles.py --num_puzzles 10 --agent=local ausgeführt
  • Von puzzles.py unterstützte Agents sind:
    • lokal trainiertes Modell: local
    • vortrainierte Modelle: 9M, 136M, 270M
    • Stockfish: stockfish, stockfish_all_moves
    • Lc0: leela_chess_zero_depth_1, leela_chess_zero_policy_net, leela_chess_zero_400_sims
  • Die Elo-Berechnung erfolgt, indem mit python tournament.py --num_games=200 Partien erzeugt und anschließend mit BayesElo aus data/tournament.pgn ausgewertet werden

Lizenz und Einschränkungen

  • Die Software wird unter der Apache License 2.0 veröffentlicht
  • Die Modellgewichte stehen unter der Lizenz Creative Commons Attribution 4.0
  • Teile des Datensatzes folgen der Creative-Commons-CC0-Public-Domain-Lizenz von lichess.org, der Rest steht unter CC-BY
  • Die Distribution wird ohne ausdrückliche oder stillschweigende Gewährleistung auf "AS IS"-Basis bereitgestellt
  • Dieses Projekt ist kein offizielles Google-Produkt

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2024-10-19
Meinungen auf Hacker News

  • Etwas off-topic, aber ich frage mich, wo Computerschach auf einem Niveau unterhalb von GM heute steht.
    Manchmal möchte ich gegen einen Gegner spielen, der etwa auf meinem Niveau ist, oder zu Trainingszwecken gegen jemanden, der ungefähr 100 Ratingpunkte stärker ist als ich.
    Die meisten Engines kann man schwächer machen, indem man die Suchtiefe reduziert, aber das funktioniert meist nicht gut. Wenn man sie stark genug reduziert, gewinnt man zwar ungefähr die Hälfte der Partien, aber die meisten Partien fühlen sich so an, als stünde ich die ganze Zeit schlechter und die Engine macht dann ein oder zwei grobe Fehler, durch die ich gewinne.
    Was ich möchte, ist ein Computergegner, der auf dem von mir gewählten Niveau spielt, sich aber wie ein typischer menschlicher Spieler dieser Ratingklasse anfühlt. Ich frage mich, ob es so eine Engine gibt.

    • Maia ist ziemlich gut darin. Man kann auf Lichess dagegen spielen.
      Es gab ein paar Momente, die sich wirklich „menschlich“ anfühlten, etwa wenn sie in Fallen tappte, die ein klassischer Suchalgorithmus leicht vermeiden würde, in die Menschen aber geraten könnten.
      Einstellbar ist sie nicht, aber es gibt ein paar Versionen mit unterschiedlichen Ratings. Der Bereich ist allerdings nicht sehr groß.
      https://www.maiachess.com/
      https://lichess.org/@/maia1
    • Ich habe einmal etwas Ähnliches gebaut: chessmate.ai. Solange das Rating nicht zu hoch ist, funktioniert es gut.
      Je höher das Rating eines Spielers wird, desto schwieriger wird es, den nächsten Zug vorherzusagen, weil man nicht nur die intuitive Zugwahl, sondern den Suchprozess selbst modellieren muss.
      Man kann es auch stärker personalisieren, indem man es nur mit den Partien eines bestimmten Spielers trainiert.
      Es nutzt einen ähnlichen Ansatz wie Maia, aber ein anderes neuronales Netz; dadurch war die Zugübereinstimmung etwas besser. Darüber habe ich noch einen Algorithmus zur Maximierung des Erwartungswerts gelegt, damit der Bot meine Fehler ausnutzt.
    • Genau darum geht es beim Gewinnen im Schach letztlich: Fehler minimieren.
    • Vor langer Zeit habe ich die Fritz-Engine von ChessBase genutzt, die eine Sparringsfunktion hatte. Wenn man solide spielte, bot sie mitten in der Partie taktische Puzzle-artige Chancen an, und man konnte Warnungen ein- oder ausschalten.
      Wenn man nicht stabil genug spielte, verlor man einfach.
      Soweit ich sehe, ist diese Funktion verschwunden. Sie fühlte sich so an, als mache sie unter Druck menschliche Fehler; im Gegensatz zu einer Engine, die wie ein Computer spielt und dann zufällig einen dummen Zug macht, war das der einzige Computer, der sich für mich wirklich wie ein Gegner anfühlte.
    • Deshalb mag ich es nicht besonders, Multiplayer-Spiele zu gewinnen. Wenn man gewinnt, fühlt es sich meistens so an, als hätte der Gegner mehrfach lächerlich schlecht gespielt, oder als hätte der Gegner gut gespielt, ich aber ein paar Mal übermäßig viel Glück gehabt.
      Das Gefühl, dass der Gegner ebenfalls gut gespielt hat, ich aber insgesamt ein bisschen besser war und deshalb verdient gewonnen habe, ist sehr selten.
      Fast immer sieht es weniger so aus, als hätte ich gewonnen, sondern eher so, als hätte der Gegner verloren. Das ist kein Problem, das nur KI betrifft.
      Wenn man eine KI bauen könnte, die in symmetrischen Spielen befriedigend verliert und bei der auch Niederlagen befriedigend lehrreich sind, wäre das ein Milliardengeschäft. Ohne ernsthafte psychologische Forschung halte ich das für schwierig.

  • Ich habe zu diesem Thema einen Vortrag gehalten und den Inhalt auch als Artikel aufbereitet[1]. Dieses Paper ist ein gutes Beispiel für Knowledge Distillation.
    Es ist weniger ein Paper über Schach an sich, sondern zeigt eher, dass sich eine von Experten abgestimmte, komplexe nichtlineare Suchfunktion bei standardisierten Eingaben wie im Schach in ein nahezu lineares Transformer-Modell destillieren lässt.
    [1]: https://hlfshell.ai/posts/deepmind-grandmaster-chess-without...

    • Die Ergebnisse gegen menschliche Gegner sollte man meines Erachtens mit einiger Vorsicht betrachten. Das waren Blitzpartien, und die Elo dieser Engine war gegen Menschen deutlich höher als gegen andere Bots.
      Daher ist Zeit wahrscheinlich ein Faktor. Menschen verlieren eher auf Zeit oder machen Fehler, wenn sie wenig Zeit haben.
      Dass sie auch ohne Suche eine sehr gute Bewertungsfunktion gelernt hat, ist trotzdem beeindruckend. Ich hätte allerdings gern gesehen, dass Partien, in denen der Stockfish-Fallback aktiv wurde, herausgerechnet werden. Für Menschen ist ein Matt in 2 und ein Matt in 10 unter dem Gesichtspunkt des Zeitverlusts der Unterschied zwischen Sieg und Remis/Niederlage.
      Ich hätte auch gern ein direktes Match gegen Stockfish mit begrenzter Suchtiefe gesehen. Dann hätte man grob abschätzen können, wie viel vom Suchbaum diese Bewertungsfunktion destilliert hat.

  • Wer in neuronale Netze für Schach einsteigen möchte, dem kann ich dieses Repository sehr empfehlen: https://github.com/sgrvinod/chess-transformers
    Es folgt mit gut lesbarem PyTorch-Code einem typischen Implementierungsstil, und die Architektur ähnelt den derzeit leistungsfähigen neuronalen Schachnetzen.

  • https://lczero.org/blog/2024/02/how-well-do-lc0-networks-com...
    Ein Artikel der Autoren der besten neuronalen Schach-Engine zu diesem DeepMind-Paper.

    • Seit Stockfish 2020 NNUE hinzugefügt hat, war LC0 nicht mehr die beste neuronale Schach-Engine.

  • Der riesige synthetische Datensatz, der fürs Training verwendet wurde, wurde letztlich mit sehr viel klassischer Suche erzeugt. Das hat also etwas Komisches, ist aber trotzdem beeindruckend.

    • Das ist Knowledge Distillation. Danach kann man ein kleineres und effizienteres Modell anstelle des großen Modells verwenden.
    • Es zeigt eher die Grenzen neuronaler Netze. Das menschliche Gehirn kann mit viel weniger Beispielen lernen.
    • Die Suche wurde nur einmal durchgeführt. Wenn sich diese Effizienz auf anderes Wissen übertragen lässt, dann ist das etwas Bedeutendes.

  • Ich meine mich zu erinnern, dass Matthew Sadler, GM und Schachautor, Leela Zero für Trainingspartien praktisch nur nach Intuition spielen ließ, mit kaum oder gar keiner Suche.
    Meistens gewann er, aber nicht immer. Ich glaube, das stand in The Silicon Road to Chess Improvement.

    • Er veröffentlicht auch sehr unterhaltsame Videos auf YouTube. Darin stellt er Contempt sehr hoch ein, sodass Leela Remis möglichst vermeidet, zeigt, welche merkwürdigen Eröffnungsentdeckungen dabei entstehen, und liefert dazu Kommentare auf 2700+-Niveau.
    • Bei lczero kann man einfach die maximale Tiefe zum Beispiel auf 1 ply setzen.

  • Wenn man für jede Brettstellung in jeder Partie Stockfish laufen lässt, um Trainingsdaten zu erzeugen, kodiert man dann am Ende nicht einfach den Suchbaum in ein Transformer-Modell?
    Dann könnte das Modell mit zunehmender Zahl an Parametern mehr vom Suchbaum aufnehmen und die Leistung würde besser, aber besonders interessant wirkt das nicht.

    • Ich verstehe nicht, wie es möglich sein soll, einen Suchbaum auf diese Weise zu kodieren.

  • Dieses Repository stellt die Implementierung unseres Papers Grandmaster-Level Chess Without Search bereit: https://arxiv.org/abs/2402.04494
    Die jüngsten Durchbrüche im Machine Learning kamen vor allem durch Skalierung zustande, also durch große attention-basierte Architekturen und Datensätze in bislang unerreichter Größe. Dieses Paper untersucht den Einfluss großskaligen Lernens im Schach.
    Anders als traditionelle Schach-Engines, die auf komplexe Heuristiken, explizite Suche oder eine Kombination aus beidem setzen, trainieren wir ein Transformer-Modell mit 270 Millionen Parametern per Supervised Learning auf einem Datensatz aus 10 Millionen Schachpartien.
    Jede Brettstellung im Datensatz wurde mit Aktionswerten annotiert, die von der starken Engine Stockfish 16 bereitgestellt wurden; so ergeben sich etwa 15 Milliarden Datenpunkte.
    Das größte Modell erreichte gegen menschliche Gegner ein Lichess-Blitz-Elo von 2895 und löste schwierige Schachrätsel ohne domänenspezifische Anpassungen oder explizite Suchalgorithmen.
    Außerdem übertraf es das Policy- und Value-Netzwerk von AlphaZero ohne MCTS sowie GPT-3.5-turbo-instruct. Eine systematische Untersuchung von Modell- und Datensatzgröße zeigt, dass starke Schachleistung erst bei ausreichender Skalierung entsteht. Zudem wurden umfangreiche Ablationsstudien zu Designentscheidungen und Hyperparametern durchgeführt.

    • Gegen Bots ist das Lichess-Blitz-Elo allerdings etwa 700 Punkte niedriger als gegen Menschen.

  • Es wäre schön, eine Engine zu haben, die eher wie ein Mensch denkt. Da dieser Ansatz von Stockfish annotierte Partien verwendet, wird sie im Grunde wohl eher wie ein Computer denken.
    Wenn sie wie ein Mensch dächte, wäre sie in Partieanalysen sehr nützlich, um bei jeder Stellung passend zu meinem Elo darauf hinzuweisen, worauf ich achten sollte.

    • Oder auch ein Modell, das Leistung über Lerneffizienz misst. Mit anderen Worten: Wie viele Partien muss man spielen, um auf Niveau X zu kommen?
      Magnus Carlsen ist deshalb so außergewöhnlich, weil er im Vergleich zu Computern unter enormen Zeit- und Rechenbeschränkungen sein heutiges Schachniveau erreicht hat. Seine Lerneffizienz ist im Vergleich zu jeder Schach-Engine außergewöhnlich.
    • Am anderen Ende des Spektrums gibt es ebenfalls etwas: extrem begrenzter Speicher, Programmgröße und Rechenzeit: https://rlc-chess.com/
      Es fühlt sich wie ein Demoscene-Programm an. Es gibt tatsächlich auch ein funktionierendes 1-KB-Schachprogramm.

  • Wenn man Schach vollständig löst, entsteht ein Baum, der derzeit viel zu groß zum Berechnen ist. Ich habe ungefähr 10^80 im Kopf, könnte mich aber irren.
    Annotiert man diesen Baum mit Sieg/Niederlage/Remis, ist ein optimaler Spieler auch ohne Suche möglich.
    Die zwei naheliegenden Ansätze für Kompression und Optimierung sind, entweder den Baum zu approximieren oder die Annotationen zu approximieren. Wie gut diese beiden Methoden funktionieren, hängt stark von der Baumstruktur ab.
    Dieses Ergebnis scheint weniger die absolute Stärke des Lernansatzes an sich zu zeigen, sondern eher, wie gut der Schach-Spielbaum zu diesen beiden Ansätzen passt. Meine Schlussfolgerung daraus ist, dass eine vernünftige Approximation dieses Baums mit Daten im Umfang von 270 Millionen Wörtern möglich ist.