💻 computer science

An ASP-based approach to Solving General Stochastic Two-Player Games

Dieser Beitrag stellt das Stochastische Antwortmengenprogrammieren (SQASP) als ersten auf ASP basierenden Ansatz zur Lösung von Zwei-Spieler-Zug-für-Zug-Spielen mit Unsicherheit in der General Game Description Language (GDL) vor und zeigt dessen Wettbewerbsfähigkeit gegenüber der Vorwärtssuche bei kleinen stochastischen Spielen sowie sein Potenzial für die Endspielbewertung auf.

Ursprüngliche Autoren: Yifan He, Michael Thielscher

Veröffentlicht 2026-05-25

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Yifan He, Michael Thielscher

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie versuchen einem Computer beizubringen, ein Brettspiel zu spielen. Normalerweise ähneln diese Spiele dem Schach: Sie machen einen Zug, Ihr Gegner macht einen Zug, und das Brett verändert sich auf vorhersehbare Weise. Aber was, wenn das Spiel auch einen „Wildcard"-Zug beinhaltet? Was, wenn nach Ihrem Zug ein magischer Würfelwurf entscheidet, ob Ihr Zug funktioniert, oder ob ein dritter unsichtbarer Spieler (nennen wir ihn „Zufall") einen Keil in die Zahnräder wirft?

Dieser Artikel handelt davon, Computern beizubringen, diese kniffligen, unvorhersehbaren Spiele zu lösen. Die Autoren, Yifan He und Michael Thielscher, haben ein neues mathematisches Werkzeug entwickelt, um die bestmögliche Strategie zu ermitteln, wenn Glück im Spiel ist.

Hier ist die Aufschlüsselung ihres Ansatzes mit einfachen Analogien:

1. Das Problem: Der Spieler „Zufall"

In der klassischen Spieltheorie sind Computer hervorragend darin, den perfekten Zug gegen einen klugen Gegner zu berechnen. Doch wenn Sie Zufälligkeit hinzufügen (wie das Würfeln oder das Ziehen von Karten), wird die Mathematik unübersichtlich.

Der alte Weg: Frühere Computerprogramme konnten Spiele mit zwei klugen Spielern (wie Schach) oder Spiele mit einem Spieler und einem Zufallselement (wie Solitär) bewältigen. Sie konnten jedoch kein Spiel mit zwei klugen Spielern UND einem Zufallselement gleichzeitig bewältigen.
Das Ziel: Die Autoren wollten „Allgemeine Stochastische Zwei-Spieler-Spiele" lösen. Stellen Sie sich ein Spiel wie Tic-Tac-Toe vor, bei dem jedes Mal, wenn Sie versuchen, ein X zu setzen, eine 30%ige Chance besteht, dass das Feld stattdessen zu einem O wird, oder eine 50%ige Chance, dass der Zug vollständig blockiert wird.

2. Das neue Werkzeug: SQASP (Der „magische Bauplan")

Die Autoren erfanden eine neue Sprache namens Stochastic Answer Set Programming (SQASP).

Die Analogie: Stellen Sie sich vor, Sie sind ein Architekt, der ein Haus entwirft. Sie haben einen Bauplan (die Spielregeln). In der Vergangenheit konnten Sie nur Häuser für zwei spezifische Arten von Bauarbeitern entwerfen: einen, der ein genialer Strategist ist (der Gegner), und einen, der ein Roboter ist, der strikten Regeln folgt.
Die Innovation: SQASP ist wie ein neuer Bauplan, der eine Baustelle beschreiben kann, auf der ein Genialer Strategist, ein Roboter und ein Glücksspieler gemeinsam arbeiten.
- Der Genie (Spieler X) möchte gewinnen.
- Der Gegner (Spieler O) möchte Spieler X aufhalten.
- Der Glücksspieler (Zufall) wirft eine Münze, um zu entscheiden, was als Nächstes passiert.
SQASP ermöglicht es dem Computer zu fragen: „Wie hoch ist die höchstmögliche Wahrscheinlichkeit, dass ich gewinne, unter der Annahme, dass mein Gegner perfekt spielt, um mich aufzuhalten, und der Glücksspieler tut, was immer er will?"

3. Der Übersetzer: Baupläne in ein Rätsel verwandeln

Computer sprechen keine „Bauplan"-Sprache. Sie sprechen „Logikrätsel".

Der Prozess: Die Autoren bauten einen Übersetzer (ein Werkzeug namens sqasp2xssat). Es nimmt ihren ausgeklügelten SQASP-Bauplan und wandelt ihn in ein riesiges Logikrätsel namens Extended Stochastic Satisfiability (XSSAT) um.
Die Metapher: Denken Sie an SQASP als ein komplexes Rezept für einen Kuchen. Der Übersetzer ist eine Maschine, die dieses Rezept in ein riesiges, mehrschichtiges Sudoku-Rätsel verwandelt. Sobald das Rätsel gelöst ist, verrät die Antwort die genaue Gewinnwahrscheinlichkeit des Spiels.
Der Löser: Sie verwendeten einen bestehenden Löser (SharpSSAT), um dieses Sudoku zu knacken. Wenn der Löser sagt „Ja, dieses Rätsel ist lösbar", bedeutet dies, dass der Spieler eine Gewinnstrategie hat. Wenn er eine Wahrscheinlichkeit von 67 % berechnet, ist dies das bestmögliche Ergebnis.

4. Der Trick der „Quantorenverschiebung"

Der Artikel testete auch eine spezifische Optimierungstechnik namens Quantifier Shifting (Quantorenverschiebung).

Die Analogie: Stellen Sie sich vor, Sie organisieren ein Turnier.
- Methode A (Basis): Sie listen jeden einzelnen Zug eines Spielers auf, prüfen dann, ob die Züge legal sind, und prüfen dann, ob das Spiel beendet ist.
- Methode B (Verschiebung): Sie prüfen, ob die Züge legal sind, bevor Sie überhaupt die Züge auflisten. Dies scheint schneller zu sein, da Sie keine Zeit damit verschwenden, illegale Züge zu planen.
Das Ergebnis: Bei Spielen mit zwei klugen Spielern (deterministische Spiele) ist dieser „Verschiebungs"-Trick eine enorme Geschwindigkeitssteigerung. Die Autoren stellten jedoch fest, dass dieser Trick bei Spielen mit dem „Glücksspieler" (stochastische Spiele) nicht viel ausmachte.
Warum? Der verwendete Löser (SharpSSAT) ist sehr intelligent. Er verfügt über einen eingebauten „Detektiv" (genannt Unit Propagation), der illegale Züge unabhängig von der Reihenfolge Ihrer Anweisungen selbstständig erkennt. Daher war die aufwendige Neuordnung für diesen spezifischen Löser nicht notwendig.

5. Die Ergebnisse: Wie hat es funktioniert?

Das Team testete ihr System an Varianten klassischer Spiele wie Tic-Tac-Toe, Connect-4 und Nim, jedoch mit dem zusätzlichen Spieler „Zufall".

Leistung: Ihre neue Methode war mit den Standardmethoden der „Vorwärtssuche" (bei denen ein Computer das Spiel Millionen von Malen in seinem Kopf spielt, um zu sehen, was passiert) konkurrenzfähig.
Der Haken: Es funktionierte hervorragend bei kleinen Brettern (wie 3x3 oder 4x4). Wenn das Spiel jedoch zu groß wurde (wie ein Stapel mit 100 Steinen in Nim), wurde das Logikrätsel zu groß, als dass der Computer es in angemessener Zeit lösen könnte.
Das Fazit: Die Methode ist hervorragend für die Endspielbewertung. Wenn ein Spiel fast zu Ende ist, kann dieses System einem allgemeinen KI-Spieler sagen: „Hey, wenn Sie diesen Zug machen, haben Sie eine 99%ige Chance zu gewinnen", was ihm hilft, die endgültige Entscheidung zu treffen.

Zusammenfassung

Die Autoren entwickelten eine neue Möglichkeit, Spiele mathematisch zu beschreiben, bei denen Glück und Strategie kollidieren. Sie verwandelten diese Beschreibungen in Logikrätsel, die ein Computer lösen kann, um die „bestmöglichen Chancen" auf einen Sieg zu ermitteln. Obwohl es kein Allheilmittel für jede Spielgröße ist, beweist es, dass wir Logikprogrammierung nutzen können, um komplexe, unsichere Spiele zu lösen, und Computern einen besseren Weg geben, in einer chaotischen Welt über die Zukunft nachzudenken.

Was sie NICHT behauptet haben:

Sie behaupteten nicht, dass dies für Spiele funktioniert, bei denen man das gesamte Brett nicht sehen kann (wie Poker oder Krieg-Tic-Tac-Toe). Sie stellen ausdrücklich fest, dass ihre Methode für Spiele gilt, bei denen alle das gesamte Brett sehen (vollständige Information).
Sie behaupteten nicht, dass dies alle anderen KI-Methoden sofort ersetzen wird; sie stellten fest, dass es eine Alternative für spezifische Szenarien ist, insbesondere für Endspiele.

Technische Zusammenfassung: Ein ASP-basierter Ansatz zur Lösung allgemeiner stochastischer Zwei-Spieler-Spiele

Problemstellung

Systeme für Allgemeines Spielespielen (General Game Playing, GGP) zielen darauf ab, strategische Spiele basierend auf Laufzeitbeschreibungen ohne Vorwissen über die Regeln zu spielen. Die Game Description Language (GDL) und ihre Erweiterung GDL-II sind die Standardformalismen zur Spezifikation solcher Spiele, wobei GDL-II Zufälligkeit (Stochastik) und teilweise Beobachtbarkeit unterstützt. Obwohl Answer Set Programming (ASP) erfolgreich zur Lösung deterministischer Ein- und Zwei-Spieler-GDL-Spiele eingesetzt wurde, fehlt es bestehenden ASP-Frameworks an der Fähigkeit, sowohl adversative (Minimax-) als auch stochastische Verhaltensweisen gleichzeitig auszudrücken. Folglich besteht eine Lücke bei der Verwendung von ASP-basierten Methoden zur Lösung von Zwei-Spieler-Zug-für-Zug-GDL-Spielen, die Unsicherheit beinhalten.

Methodik

Die Autoren schlagen einen neuartigen Ansatz zur Lösung von Zwei-Spieler-stochastischen GDL-Spielen vor, indem sie eine neue Sprache und einen übersetzungsbasierten Solver einführen.

1. Stochastische Quantifizierte Antwortmengenprogrammierung (SQASP)

Um die Lücke zwischen ASP und der Lösung stochastischer Spiele zu schließen, führt das Papier SQASP ein, eine Sprache, die QASP (Quantified ASP) um Chancenquantoren erweitert.

Syntax: Ein SQASP-Programm hat die Form $Q_1.x_1 \dots Q_n.x_n \ P$ , wobei $P$ ein normales Logikprogramm ist und die Quantoren $Q_i$ existenziell ( $\exists$ ), universell ( $\forall$ ) oder Chancen-Quantoren ( $\mathcal{R}_{p}$ ) sein können.
Semantik: Die maximale Wahrscheinlichkeit, ein SQASP-Programm zu erfüllen, wird rekursiv definiert. Der Chancenquantor $\mathcal{R}_{p}$ weist einer Variable eine Wahrscheinlichkeit $p$ zu, wahr zu sein, und berechnet den Erwartungswert basierend auf den Wahrscheinlichkeiten der Teilformeln.
Übersetzung: Die Autoren implementieren ein Werkzeug, sqasp2xssat, das SQASP-Programme in Extended Stochastic Satisfiability (XSSAT)-Formeln übersetzt. XSSAT erweitert Quantifizierte Boolesche Formeln (QBF) um Chancenquantoren. Die Übersetzung nutzt bestehende Werkzeuge (wie lp2sat), um das Logikprogramm $P$ in eine KNF-Formel $\psi$ zu konvertieren, deren Modelle den stabilen Modellen von $P$ entsprechen.

2. Kodierung von GDL-Spielen in SQASP

Der Kernbeitrag ist die Konstruktion eines SQASP-Programms $\Psi$ , sodass seine maximale Erfüllbarkeitswahrscheinlichkeit der maximalen Gewinnwahrscheinlichkeit eines Spielers $x$ innerhalb von $n$ Schritten entspricht ( $P_x^w(S_0, n)$ ). Die Kodierung erfolgt in zwei Hauptphasen:

Kooperatives Basisszenario: Zuerst wird ein Logikprogramm $P_c$ konstruiert, das davon ausgeht, dass alle Spieler (einschließlich des Gegners $o$ und des Zufallsspielers $r$ ) kooperieren, um einen Endzustand zu erreichen, in dem $x$ gewinnt. Dies gewährleistet einen gültigen Spielverlauf, eine Terminierung innerhalb von $n$ Schritten und das Erreichen des Zielzustands.
Adversative und stochastische Modellierung: Das Programm wird dann erweitert, um das spezifische Verhalten des Gegners und der Umgebung zu erfassen:
- Adversativer Spieler ( $o$ ): Wird mittels universeller Quantifizierung ( $\forall$ ) über Entscheidungsvariablen (dec_o) modelliert. Dies zwingt den Solver, das Worst-Case-Szenario zu berücksichtigen, in dem der Gegner die Gewinnwahrscheinlichkeit von $x$ minimiert. Die Kodierung verwendet eine logarithmische Darstellung von Aktionen, um die Anzahl der Regeln zu reduzieren.
- Stochastischer Spieler ( $r$ ): Wird mittels Chancenquantoren ( $\mathcal{R}_{1/i}$ ) modelliert. Die Kodierung stellt sicher, dass, falls das Spiel nicht terminiert hat, der Zufallsspieler genau eine legale Aktion gleichverteilt aus den verfügbaren legalen Zügen auswählt. Dies wird erreicht, indem legale Aktionen gezählt und Wahrscheinlichkeitsbeschränkungen auf Entscheidungsvariablen (dec_r) angewendet werden.

3. Quantifizierungsstrategien

Das Papier untersucht zwei Quantifizierungsstrategien für die resultierende XSSAT-Formel:

Basismethode ( $Q_b$ ): Alle Nicht-Auswahl-Atome (z. B. legal, terminal) werden im innersten existenziellen Block platziert, wobei eine strikte zeitliche Reihenfolge der Auswahl-Atome eingehalten wird.
Abhängigkeitsbasierte Methode ( $Q_d$ ): Inspiriert von Techniken für deterministische Spiele, verschiebt diese Methode Nicht-Auswahl-Atome so, dass sie so früh wie möglich im Quantorenpräfix erscheinen, unmittelbar nach den Auswahl-Atomen, von denen sie abhängen. Dies zielt darauf ab, den Suchraum zu reduzieren, indem Werte wie legal festgelegt werden, bevor über does verzweigt wird.

Hauptbeiträge

Erster ASP-basierter Solver für stochastische GDL-Spiele: Das Papier stellt den ersten Ansatz zur Lösung von Zwei-Spieler-stochastischen Zug-für-Zug-GDL-Spielen unter Verwendung von ASP vor.
SQASP-Sprache: Die Einführung der Stochastischen Quantifizierten Antwortmengenprogrammierung, die adversatives und stochastisches Schließen innerhalb eines Logikprogrammierungsrahmens vereint.
Übersetzungsbasierter Solver: Die Entwicklung von sqasp2xssat, das SQASP-Programme in XSSAT-Formeln konvertiert und damit die Nutzung bestehender XSSAT-Solver (insbesondere SharpSSAT) zur Spiellösung ermöglicht.
Theoretische Korrektheit: Die Autoren liefern formale Beweise (Sätze 2 und 3), die die Äquivalenz zwischen der maximalen Gewinnwahrscheinlichkeit im GDL-Spiel und der maximalen Erfüllbarkeitswahrscheinlichkeit der generierten SQASP/XSSAT-Formel herstellen.

Experimentelle Ergebnisse

Die Autoren bewerteten ihren Ansatz an stochastischen Variationen von Tic-Tac-Toe, Connect-4 und Nim und verglichen die SQASP-basierte Methode (unter Verwendung sowohl der $Q_b$ - als auch der $Q_d$ -Quantifizierung) mit einem Expected Minimax (EMM)-Solver für Vorwärtssuche.

Leistung: Der ASP-basierte Ansatz ist bei kleinen stochastischen Spielen mit der Vorwärtssuche konkurrenzfähig. In vielen Fällen (z. B. Tic-Tac-Toe, Connect-3) berechnet der ASP-Solver Gewinnwahrscheinlichkeiten, die mit EMM vergleichbar sind, oft innerhalb ähnlicher Zeiträume.
Quantorenverschiebung: Überraschenderweise erzielte die abhängigkeitsbasierte Quantifizierung ( $Q_d$ ) keine signifikanten Leistungsverbesserungen gegenüber der Baseline ( $Q_b$ ) bei Verwendung des SharpSSAT-Solvers. Die Autoren führen dies auf den internen Unit-Propagation-Mechanismus von SharpSSAT zurück, der Werte von Atomen (wie legal) unabhängig von der Quantorenreihenfolge ableiten kann, was die Notwendigkeit einer expliziten Verschiebung effektiv aufhebt.
Skalierbarkeitsgrenzen: Der Ansatz hat Schwierigkeiten mit größeren Zustandsräumen, wie beispielsweise stochastischem Nim mit großen Stapelgrößen. Die resultierenden XSSAT-Formeln werden zu groß (über eine Million Klauseln), als dass aktuelle Solver sie effizient verarbeiten könnten, während EMM aufgrund von dynamischer Programmierung und Transpositionstabellen gut skaliert.

Bedeutung und Behauptungen

Das Papier behauptet, dass der vorgeschlagene ASP-basierte Ansatz eine gangbare Alternative für die Endspielbewertung in Systemen für Allgemeines Spielespielen darstellt. Durch die Erweiterung der erfolgreichen Anwendung von ASP auf deterministische Spiele in den stochastischen Bereich zeigt die Arbeit, dass Logikprogrammierung Unsicherheit und adversatives Schließen effektiv handhaben kann.

Die Autoren vermerken bescheiden, dass der Ansatz die Vorwärtssuche nicht in allen Fällen dominiert (insbesondere bei Spielen mit sehr großen Zustandsräumen oder spezifischen Strukturen wie Nim), aber er generalisiert die vorherigen Ergebnisse für deterministische Spiele erfolgreich auf stochastische. Sie identifizieren die Erweiterung auf teilweise Beobachtbarkeit (z. B. Poker, Krieg-Tic-Tac-Toe) als eine kritische Richtung für zukünftige Arbeiten und räumen ein, dass die aktuelle Methode auf Spiele mit perfekter Information beschränkt ist.