MiniMax-Schach-Engine, implementiert mit regulären Ausdrücken

 (nicholas.carlini.com)
4 Punkte von GN⁺ 2025-01-08 | 1 Kommentare | Auf WhatsApp teilen

MiniMax-Schach-Engine mit Tiefe 2

  • Schach und reguläre Ausdrücke: Der Autor hat ein Schachprogramm erstellt, das ausschließlich mit regulären Ausdrücken spielt. Dieses Programm nimmt eine Schachstellung als Eingabe und besteht aus 84.688 regulären Ausdrücken, die gültige Züge erzeugen.

  • Entwurf einer Regex-CPU: Der Autor entwirft mit regulären Ausdrücken eine CPU mit verzweigungsfreier Ausführung und einem Single Instruction Multiple Data (SIMD)-Befehlssatz. Dadurch kann ein Schachprogramm geschrieben werden.

  • Datenstruktur: Der aktuelle Zustand des Rechners wird als ein einziger String dargestellt, der den Programm-"Stack" und alle Variablen enthält. Jede Anweisung manipuliert entweder Stack-Variablen oder führt Lese-/Schreiboperationen für eine bestimmte Variable aus.

  • Grundlegende Stack-Operationen:

    • Push-Befehl: Fügt einen Wert oben auf den Stack.
    • Pop-Befehl: Entfernt das oberste Element vom Stack.

  • Variablen <-> Stack-Befehle:

    • Variablenzugriff: Lädt den Inhalt einer Variablen auf die Spitze des Stacks.
    • Variablenzuweisung: Schreibt einen Wert in eine Variable; je nach Existenz der Variable wird sie aktualisiert oder neu angelegt.

  • Bedingte Anweisungen: Durch bedingte Anweisungen wird der Kontrollfluss des Programms gesteuert. Je nach Bedingung werden bestimmte Teile des Programms aktiviert oder deaktiviert.

  • Unmöglichkeit von Schleifen: Da mit regulären Ausdrücken keine Schleifen implementiert werden können, müssen alle iterativen Berechnungen vorab vollständig ausgeklappt werden.

  • Mehrfach-Thread-Ausführung: Mithilfe der globalen Ersetzungsfunktion von regulären Ausdrücken können mehrere Threads gleichzeitig ausgeführt werden.

  • Schreiben der Schach-Engine: Die Schachengine wird ähnlich wie in anderen Programmiersprachen implementiert und läuft dank Parallelisierung schnell.

  • Zugabwicklung:

    • Lesen des Spielerzugs: Liest den eingegebenen Zug und validiert ihn.
    • Generieren der Computerantwort: Erzeugt alle möglichen Antworten und wählt den besten Zug aus.

  • MiniMax-Suche: Mit einer MiniMax-Suche der Tiefe 2 wird der optimale Zug ausgewählt. Dieser Prozess wird effizient durch Parallelisierung durchgeführt.

Dieses Projekt zeigt anhand einer ungewöhnlichen Nutzung regulärer Ausdrücke die Umsetzung einer Schachengine und demonstriert die Ausdruckskraft regulärer Ausdrücke sowie ein kreatives Computerkonzept.

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2025-01-08
Hacker News Kommentar

  • Dieser Entwickler hat gezeigt, dass printf() turingvollständig ist, und ein First-Person-Shooter-Spiel in 13kB JavaScript geschrieben.

  • Das Projekt ist bemerkenswert, weil die Berechnung über mehrere mögliche Positionen parallel läuft.

    • Mit regulären Ausdrücken können mehrere Threads gleichzeitig ausgeführt werden.

  • Zur Schlussfolgerung des Blogposts habe ich nichts Weiteres beizutragen, aber ich würde mir wünschen, dass mehr Leute solche scheinbar sinnlosen Projekte ausprobieren.

    • Es macht Spaß, ohne Druck hinsichtlich Aufwand oder Erfolg, und man lernt dabei eine Menge über verschiedene Bereiche der Informatik.

  • Im Schachspiel gibt es einen Fehler „illegal move, loss“.

    • In einem Beispielspiel endet die Partie trotz eines nicht illegalen Zugs.

  • Ich fürchte mehr einen Spieler, der mit nur einem regulären Ausdruck Schach spielt, als jemanden mit 84.688 regulären Ausdrücken.

  • Bei solchen Projekten möchte ich einfach nur Respekt zollen.

  • Der Bug beim a-file-Zug wurde behoben.

  • Dieses Projekt ist nicht nur eine Schach-Engine, sondern auch ein mit regulären Ausdrücken aufgebauter Rechner und eine Assemblersprache.

  • Es gab bereits ein Schachprojekt, das in sed geschrieben wurde.

    • Die sed-Version nutzt Kontrollflussanweisungen und sucht nur 1 ply tief.

  • Wenn man mit a2a4 beginnt, geht es nicht so schnell kaputt.

  • Etwas zu versuchen, ohne ein klares „produktives“ Ziel, kann neue Wege entdecken und Innovation fördern.

    • Die Engine verliert in der Eröffnung ein Stück.
    • Bei der Eingabe von Großbuchstaben wird es als illegaler Zug gewertet.

  • Ich versuche, innovativ zu sein und produktiv zu werden.