Eine 2-ply-Minimax-Schach-Engine, implementiert mit 84.688 regulären Ausdrücken

 (nicholas.carlini.com)
4 Punkte von GN⁺ 2025-01-08 | 1 Kommentare | Auf WhatsApp teilen
  • Regex Chess ist eine 2-ply-Minimax-Engine, die ausschließlich 84.688 Ersetzungen mit regulären Ausdrücken der Reihe nach ausführt, um auf dem Schachbrett einen legalen und „nicht völlig miserablen“ Zug auszuwählen
  • Der Zustand enthält Stack und Variablen gemeinsam in einem einzigen String; Befehle wie push, pop sowie das Lesen und Zuweisen von Variablen werden per Regex-Ersetzung verarbeitet
  • Bedingte Verzweigungen werden simuliert, indem ein %%-Marker für den aktiven Zustand geändert wird; dank globaler Ersetzungen wird eine SIMD-artige parallele Ausführung möglich, bei der mehrere Zustände auf einmal verarbeitet werden
  • Die Engine erzeugt alle legalen Züge als parallele Zustände und bewertet auch die Antworten des Gegners, führt aber keine depth-3-Suche durch, die auch die Legalität der gegnerischen Antwort vollständig validieren würde
  • Anfangs dauerte eine Antwort auf einen Zug etwa 30 Minuten; durch das Löschen temporärer Variablen, Matching-Optimierungen, Spezialbefehle und Parallelisierung sank die finale Implementierung je nach Stellung auf etwa 1–10 Sekunden

Grundstruktur von Regex Chess

  • Regex Chess besteht als vollständige Schach-Engine aus einer Liste von 84.688 regulären Ausdrücken
  • Die Ausführungsstruktur ist einfach
    • Die Liste der regulären Ausdrücke wird der Reihe nach durchlaufen
    • Auf den aktuellen Schachbrett-Zustandsstring werden jeweils das Muster und der Ersetzungsstring angewendet
    • Der letzte Zustand wird auf dem Bildschirm angezeigt
  • Die Eingabe ist nicht PGN, sondern ein Koordinatenformat aus Startfeld und Zielfeld wie e2e4
  • Der Projektcode ist auf GitHub veröffentlicht

Eine CPU aus regulären Ausdrücken

  • Statt die Schachregeln direkt als reguläre Ausdrücke zu schreiben, wird zuerst ein kleiner Computer gebaut, der mit regulären Ausdrücken arbeitet
  • Dieser Computer nutzt einen Befehlssatz mit bedingter Ausführung ohne Branches, Single-Instruction-Multiple-Data-Ausführung sowie Stack- und Variablenmanipulation
  • Der aktuelle Zustand wird als ein einziger String dargestellt
    • %% markiert den Beginn eines aktiven Ausführungszustands
    • Unter #stack: werden Stack-Einträge abgelegt
    • Variablen werden in der Form #variable: value gespeichert

  • Stack- und Variablenmanipulation

    • push sucht den Header %%\n#stack:\n und fügt darunter einen Wert ein, also oben auf den Stack
    • pop entfernt die Zeile direkt unter #stack: und löscht damit den obersten Stack-Wert
    • Ein Variablen-Lookup findet #Variablenname: im Zustandsstring, kopiert den Wert und legt ihn oben auf den Stack
    • Eine Variablenzuweisung behandelt sowohl den Fall, dass die Variable bereits existiert, als auch den Fall, dass sie noch nicht existiert
      • Existiert sie bereits, wird der bisherige Variablenwert durch den Stack-Wert ersetzt
      • Existiert sie nicht, wird eine neue Variablenzeile hinzugefügt
    • Temporäre Marker wie Backticks sorgen dafür, dass derselbe Befehl nicht fälschlich erneut in der falschen Reihenfolge angewendet wird

Bedingte Ausführung ohne Branches und Begrenzung von Schleifen

  • Bedingte Ausführung wird mit cond(tag) und reactivate(tag) implementiert
  • Ist der oberste Stack-Wert False, wird der aktive Marker %% in die Form %tag geändert, sodass spätere Befehle nicht mehr auf diesen Zustand angewendet werden
  • Später ändert reactivate(tag) %tag wieder in %% und aktiviert den Zustand erneut
  • So wird bedingte Ausführung ohne explizite Branches simuliert
  • Da das Programm eine sequenzielle Liste regulärer Ausdrücke ist, können Schleifen nicht direkt ausgeführt werden
    • Turing-vollständige Berechnungen sind damit nicht möglich
    • Begrenzte Berechnungen wie die Berechnung des nächsten Schachzugs lassen sich jedoch durch Entrollen von Schleifen verarbeiten

Parallele Ausführung mit globalen Ersetzungen

  • Weil Regex-Ersetzungen global auf den gesamten String angewendet werden, kann derselbe Befehl gleichzeitig auf mehrere Zustände angewendet werden, wenn ein Zustandsstring mehrere %%-Ausführungszustände enthält
  • Wenn zum Beispiel zwei Stacks jeweils zwei Ganzzahlen enthalten und binary_add() ausgeführt wird, werden beide Additionen gleichzeitig durchgeführt
  • fork_inactive(tag) dupliziert den aktuell aktiven Zustand und belässt die Kopie in einem inaktiven Tag-Zustand
  • fork_bool(variable) teilt einen Zustand in zwei Zustände auf, einen mit dem Wert True und einen mit dem Wert False
  • Diese Struktur wird genutzt, um viele im Schach mögliche Brettzustände nicht einzeln nacheinander zu verarbeiten, sondern gleichzeitig zu bewerten

Makro-Assembler und symbolische Ausführung

  • Die Engine schreibt nicht alle regulären Ausdrücke direkt von Hand, sondern verwendet einen Makro-Assembler, der Python-artige Programme in kleine Befehlssequenzen übersetzt
  • Python-artiger Code wie fib() wird in Befehlslisten wie push, lookup, binary_add und assign_pop umgewandelt
  • Statt eines klassischen Parsers und Codegenerators wird symbolische Ausführung (symbolic execution) verwendet
    • Variablenobjekte sind keine echten Dictionaries, sondern spezielle Objekte, die die ausgeführten Operationen protokollieren
    • a = b + 1 wird als lookup('b'), push(1), binary_add(), assign_pop('a') aufgezeichnet
  • if-Anweisungen zeichnen sowohl den Pfad für die wahre als auch den Pfad für die falsche Bedingung auf und führen sie anschließend wieder zusammen
    • Beim Antreffen einer bedingten Verzweigung werden im Aufrufbaum zwei Pfade erzeugt
    • Durch mehrfaches Tracing wird jeweils der seltener besuchte Zweig gewählt, um beide Pfade zu füllen
    • Zusammenführungspunkte werden in reactivate-Befehle übersetzt

Wie Schachzüge erzeugt werden

  • Die Entwicklung der Schach-Engine selbst ähnelt einer Schach-Engine in einer normalen Sprache, entscheidend ist aber die parallele Verarbeitung vieler Zustände
  • Die Erzeugung von Bauernzügen folgt diesem Ablauf
    • Alle Positionen weißer Bauern werden gesucht
    • Für jeden Bauern wird ein paralleler Zustand erzeugt
    • Der ursprüngliche Hauptzustand wird angehalten und die bauernspezifischen Zustände werden aktiviert
    • Ein-Feld-Vorrücken, Zwei-Feld-Vorrücken und diagonale Schlagkandidaten werden in allen Bauernzuständen gleichzeitig geprüft
    • Die Kandidatenlisten der einzelnen Zustände werden wieder zusammengeführt
  • Die erklärenden Beispiele arbeiten direkt mit FEN-Strings, die tatsächliche Implementierung erweitert das Schachbrett jedoch zu 64 feldspezifischen Variablen, die gelesen und geschrieben werden
  • Gleitende Figuren wie Läufer, Turm und Dame sowie Rochade und En passant sind separat implementiert
  • Die Details der Implementierung finden sich in chess_engine.py

Verarbeitung eines Zugs und Zugvalidierung

  • Ein Zug besteht daraus, den menschlichen Eingabezug zu lesen, seine Legalität zu prüfen und anschließend den Antwortzug des Computers zu erzeugen
  • from_pretty_utf8_to_fen() wandelt die Unicode-Schachbrettdarstellung in FEN-Notation um und extrahiert Start- und Zielfeld der Eingabe
  • Die Legalität des menschlichen Zugs wird nicht durch separaten Regelprüfcode validiert, sondern durch Erzeugen aller legalen Folgebretter und anschließenden Vergleich
    • make_move erzeugt das Brett, das sich aus der Anwendung des Eingabezugs ergibt
    • compute_legal_boards erzeugt alle aus der aktuellen Stellung möglichen legalen Bretter
    • fork_on_list trennt jedes Brett in einen parallelen Zustand auf
    • Zustände, die nicht dem Ergebnis des Eingabezugs entsprechen, werden mit destroy_active_thread() entfernt
  • Gibt es keinen legalen Zug, wird die gesamte Ausgabe durch den hartcodierten Text "Illegal Move" ersetzt
  • Für die Computerantwort werden die möglichen Antwortbretter für Schwarz samt Punktzahlen erzeugt; anschließend lässt keep_best_scoring_board(score) nur das Brett mit der besten Punktzahl übrig

2-ply-Minimax und bewusste Vereinfachung

  • compute_and_score_legal_boards bildet den Kern der depth-2-Minimax-Suche
  • Zunächst werden Kandidatenzüge erzeugt, die der Computer spielen kann; anschließend werden mögliche Antworten des Gegners erzeugt, um zu prüfen, ob der König geschlagen werden kann
  • Da wegen der Schachprüfung auch gegnerische Antworten erzeugt werden, entsteht bereits eine depth-2-Suchstruktur
  • Jede Kandidatenstellung wird mit der Punktzahl bewertet, die sie hätte, wenn der Gegner die beste Antwort spielt
  • Es ist kein vollständiges depth-2-Minimax
    • Es wird nicht geprüft, ob ein gegnerischer Antwortzug illegal ist, weil er den eigenen König im Schach lässt
    • Eine vollständige Behandlung würde eine depth-3-Suche erfordern und die Kosten stark erhöhen
  • Die vom Computer erzeugte Antwort selbst ist kein illegaler Zug, in manchen Fällen kann er jedoch Züge berücksichtigen, die der Gegner gar nicht spielen darf, und deshalb eine schwächere Antwort wählen, als tatsächlich nötig wäre

Performance-Optimierung

  • Die anfängliche Implementierung brauchte etwa 30 Minuten, um eine Antwort auf einen menschlichen Zug zu erzeugen
  • Die finale Implementierung benötigt auf dem Rechner des Autors je nach Stellung etwa 1–10 Sekunden
  • Die etwa 100-fache Beschleunigung ist das Ergebnis mehrerer Optimierungen

  • Löschen temporärer Variablen

    • Variablen-Lookups müssen den Variablenwert im gesamten Zustandsstring finden und kosten daher O(n)
    • Beim Forken eines Ausführungszustands werden auch die Variablen mitkopiert, wodurch der Speicherverbrauch steigt
    • Nicht mehr benötigte Variablen werden konsequent gelöscht und Variablennamen wiederverwendet, um Zeit und Speicher zu sparen
    • Der interne Zustand zur Bewertung eines Zugs schrumpfte dadurch von 10 GB vor der Optimierung auf etwa 300 MB

  • Optimierung des Regex-Matchings

    • Allein das Einbeziehen des vorhergehenden Zeilenumbruchs in eine Aufräum-Regex für bedingte Befehle machte diesen Befehl etwa doppelt so effizient
    • Da im Zustand viele True- und False-Strings vorkommen, müssen Muster so eingeschränkt werden, dass sie nur den obersten Stack-Wert schnell finden
    • Kleine Musterunterschiede, die unnötige Kandidaten-Matches reduzieren, beeinflussen die gesamte Laufzeit

  • Spezialbefehle und Parallelisierung

    • Langsame Stellen wie Schleifen zur Suche nach Figurenpositionen werden nicht durch Kombination bestehender Befehle umgesetzt, sondern zu einem einzigen spezialisierten Regex-Befehl zusammengefasst
    • Bei der Erzeugung von Turmzügen werden die Richtungen nicht nacheinander geprüft; stattdessen werden mehrere parallele Zustände erzeugt und auf einmal verarbeitet
    • Auch die Stellungsbewertung wird gleichzeitig ausgeführt, indem für jedes Kandidatenbrett ein paralleler Zustand erzeugt wird
    • Parallele Ausführung ist besonders effektiv bei Aufgaben, bei denen dieselbe Operation in vielen Zuständen wiederholt wird, etwa bei der Berechnung von Figurenwerten

Weitere Implementierungen im Quellcode

  • Der Quellcode enthält auch Implementierungselemente, die im Text nicht ausführlich erklärt werden
    • Parallele Zugerzeugung für gleitende Figuren wie Läufer, Turm und Dame
    • Eine Prozedur für die Rochade, die prüft, ob ein bestimmtes Feld angegriffen wird
    • Umwandlung zwischen FEN-Schachbrett und feldspezifischer Variablendarstellung
    • Erkennung von Rochaderechten durch Tracking der Königs- und Turmpositionen
    • Erkennung und Tracking von En passant
    • Etwa 2000 Zeilen Tests, die die Korrektheit der Engine über Tausende Partien hinweg validieren
  • Der Text endet mit der Aussage, dass solche zweckfreien Projekte dabei helfen, viele Informatikthemen außerhalb des eigenen Fachgebiets zu lernen
  • Als verwandte Projekte werden außerdem printf-tac-toe, ein Tic-Tac-Toe-Spiel mit Cs printf, und ein 13-kB-JavaScript-Doom-Klon erwähnt

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2025-01-08
Hacker-News-Kommentare

  • Das stammt von derselben Person, die gezeigt hat, dass printf() Turing-vollständig ist, und einen Ego-Shooter in 13 kB JavaScript gebaut hat
    https://github.com/HexHive/printbf
    https://github.com/carlini/js13k2019-yet-another-doom-clone

    • Als ich den Satz „hat gezeigt, dass printf() Turing-vollständig ist, und einen Ego-Shooter …“ las, dachte ich ehrlich gesagt, am Ende würde herauskommen, dass auch der Shooter in printf implementiert wurde
    • Der Doom-Entwicklungsbericht ist wegen der vielen Details interessant: https://nicholas.carlini.com/writing/2019/javascript-doom-cl...
      Für den Wettbewerb hatte man einen Monat Zeit, aber offenbar durfte vorhandener Code wiederverwendet werden
      Die Arbeit selbst muss ziemlich viel Spaß gemacht haben, und es macht mich ein bisschen traurig, dass ich heute wegen Familie und Arbeit niemals einen freien Monat für so etwas aufbringen könnte
    • Bei „Ego-Shooter in 13 kB JavaScript“ hatte ich gewisse Erwartungen, war dann aber etwas enttäuscht, als ich erfuhr, dass fürs Grafik-Rendering WebGL verwendet wurde

  • An diesem Punkt hatte ich das Gefühl, dass diese Arbeit über verrückten Spaß hinausging und völlig außergewöhnlich wurde. Die Berechnung vieler möglicher Positionen lief komplett parallel ab, indem reguläre Ausdrücke über eine wachsende Menge von Zuständen und Variablen, also über Threads, ausgeführt wurden
    „Jetzt kommt mein Lieblingsteil der Sprache, die wir gebaut haben. Dank der Magie regulärer Ausdrücke und der Tatsache, dass wir eine globale Ersetzung über den gesamten String ausführen, können wir mehrere Threads gleichzeitig laufen lassen!“
    Auch das Fazit war gut. „Was erwarten Sie als Fazit eines solchen Blogposts? Es gibt eigentlich kein Fazit. Ich wünschte nur, mehr Leute würden solche völlig nutzlosen Dinge tun. Es macht wirklich Spaß, niemand kümmert sich darum, wie lange man zum Fertigwerden braucht, niemand kümmert sich darum, ob es funktioniert oder nicht, und als Bonus lernt man über mehrere Bereiche der Informatik außerhalb des eigenen Fachgebiets mehr, als einem lieb ist.“
    Eine wirklich großartige Haltung

    • Wenn man all die anderen Sorgen beiseiteräumt, frage ich mich, ob ich so etwas auch schaffen könnte
      Was man daraus mitnimmt, ist die Kraft der Erkenntnis, dass man nicht weiß, wie weit man kommen kann, wenn man sich hinsetzt und sich auf eine Sache konzentriert; zugleich ist der Autor eindeutig ein unglaublich talentierter und geübter kreativer Mensch

  • Irgendwo scheint es einen Bug zu geben. Die folgende Partie endet mit „Illegal move, you lose“, obwohl der Zug nicht illegal ist

    1. e2e4, e7e5
    2. d2d4, e5d4
    3. d1d4, a7a5
    4. g1f3, b7b5
    5. b1c3, a5a4
    6. c3b5, a4a3
    7. b5a3, a8a3
    8. b2a3 -->
      Illegal Move
      You Lose.
      Game over.
      FEN der obigen Partie:
      1nbqkbnr/2pp1ppp/8/8/3QP3/P4N2/P1P2PPP/R1B1KB1R b KQk - 0 8
    • Auch wenn man als ersten Zug a2a3 spielt oder nach e2e4 als zweiten Zug a2a3, wird es als illegaler Zug angezeigt
      Aber beides sind legale Züge, also ist es tatsächlich ein Bug
    • Dasselbe passiert schon, wenn man als ersten Zug nur a2a4 spielt

  • Ich fürchte niemanden, der mit 84.688 regulären Ausdrücken Schach spielt, aber ich fürchte jemanden, der mit einem einzigen regulären Ausdruck Schach spielt

    • Wenn es eine allgemeine Heuristik gäbe, um nacheinander angewendete reguläre Ausdrücke zu linearisieren, also zwei beliebige reguläre Ausdrücke zu einem zusammenzuführen, könnte man sie wohl hier anwenden
      Hilfe, ich bin Opfer von Nerd-Sniping geworden
      Das potenzielle Problem, das mir sofort einfällt, sind Backreferences
      Der reguläre Ausdruck würde extrem lang werden, aber im Grunde kodiert man ja ohnehin eine Schach-Engine …

  • Bei so etwas möchte man den Hut ziehen und den wahren Helden der Menschheit feierlich danken

  • Der Bug bei Zügen auf der a-Linie wurde behoben: https://github.com/carlini/regex-chess/issues/1

  • Frühere Variante: Schach in sed https://news.ycombinator.com/item?id=6261314
    Natürlich verwendet die sed-Version die Kontrollflussbefehle von sed und sucht vermutlich nur einen Zug voraus, unterscheidet sich in dieser Hinsicht also deutlich von dieser Version

  • Das ist nicht nur eine Schach-Engine, sondern auch ein Computer samt Assemblersprache, der ausschließlich mit regulären Ausdrücken gebaut wurde

  • Normalerweise verliert man nicht so schnell, nur weil man mit a2a4 beginnt!

    • Ich bin auf einen ähnlichen Bug auf der a-Linie gestoßen. Die Zugfolge war e2e4-d2d4-d1d4-g1f3-f1b5-d4e5-e5c5-e1g1-b2a3

  • Auch das ist einen Vergleich wert: https://codegolf.stackexchange.com/q/3503/32575

    • Alle Teilbarkeitsregeln sind zwangsläufig reguläre Sprachen, daher ist das nicht allzu überraschend. Wenn sie komplexer wären, wären es keine „Regeln“ mehr, die ein Mensch ausführen kann