💻 computer science

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

Dit artikel introduceert Stochastic Answer Set Programming (SQASP) als de eerste ASP-gebaseerde aanpak voor het oplossen van twee-speler beurtelings General Game Description Language (GDL)-spellen met onzekerheid, waarbij wordt aangetoond dat het concurrerend is met voorwaartse zoekopdrachten op kleine stochastische spellen en potentieel heeft voor eindspelbeoordeling.

Oorspronkelijke auteurs: Yifan He, Michael Thielscher

Gepubliceerd 2026-05-25

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Yifan He, Michael Thielscher

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je probeert een computer te leren hoe een bordspel te spelen. Meestal zijn deze spellen zoals schaken: je doet een zet, je tegenstander doet een zet, en het bord verandert op een voorspelbare manier. Maar wat als het spel ook een "wildcard" bevat? Wat als, nadat je hebt gezet, een magische worp met een dobbelsteen bepaalt of je zet werkt, of dat een derde onzichtbare speler (laten we hem "Toeval" noemen) een steen in de wielen gooit?

Dit artikel gaat over het leren aan computers om deze lastige, onvoorspelbare spellen op te lossen. De auteurs, Yifan He en Michael Thielscher, hebben een nieuwe wiskundige toolkit gebouwd om de best mogelijke strategie te bepalen wanneer geluk een rol speelt.

Hier is de uiteenzetting van hun aanpak met behulp van eenvoudige analogieën:

1. Het Probleem: De "Toeval"-speler

In de standaard speltheorie zijn computers uitstekend in het berekenen van de perfecte zet tegen een slimme tegenstander. Maar wanneer je toeval toevoegt (zoals dobbelstenen gooien of kaarten trekken), wordt de wiskunde rommelig.

De Oude Manier: Eerdere computerprogramma's konden spellen met twee slimme spelers (zoals Schaken) of spellen met één speler en een toevallig element (zoals Patience) aan. Ze konden geen spel aan dat twee slimme spelers EN een toevallig element tegelijkertijd bevatte.
Het Doel: De auteurs wilden "Algemene Stochastische Tweespeler-spellen" oplossen. Denk hierbij aan een spelletje Drie-op-een-rij waarbij, elke keer dat je probeert een X te plaatsen, er 30% kans is dat het vakje verandert in een O, of 50% kans dat de zet volledig wordt geblokkeerd.

2. Het Nieuwe Gereedschap: SQASP (De "Magische Blauwdruk")

De auteurs hebben een nieuwe taal uitgevonden genaamd Stochastic Answer Set Programming (SQASP).

De Analogie: Stel je voor dat je een architect bent die een huis ontwerpt. Je hebt een blauwdruk (de spelregels). In het verleden kon je alleen huizen ontwerpen voor twee specifieke soorten bouwers: één die een genie-strateeg is (de tegenstander) en één die een robot is die strikte regels volgt.
De Innovatie: SQASP is als een nieuw type blauwdruk dat een bouwplaats kan beschrijven waar een Genie-strateeg, een Robot en een Gokker allemaal samenwerken.
- De Genie (Speler X) wil winnen.
- De Tegenstander (Speler O) wil Speler X stoppen.
- De Gokker (Toeval) gooit een munt om te beslissen wat er als volgende gebeurt.
SQASP stelt de computer in staat om te vragen: "Wat is de hoogst mogelijke kans dat ik win, ervan uitgaande dat mijn tegenstander perfect speelt om mij te stoppen, en de Gokker doet wat hij wil?"

3. De Vertaler: Blauwdrukken Omzetten in een Puzzel

Computers spreken geen "Blauwdruk". Ze spreken "Logische Puzzels".

Het Proces: De auteurs bouwden een vertaler (een tool genaamd sqasp2xssat). Deze neemt hun verfijnde SQASP-blauwdruk en zet deze om in een enorme logische puzzel genaamd Extended Stochastic Satisfiability (XSSAT).
De Metafoor: Denk aan SQASP als een complex recept voor een taart. De vertaler is een machine die dat recept omzet in een gigantische, meerlagige Sudoku-puzzel. Zodra de puzzel is opgelost, vertelt het antwoord je de exacte kans om het spel te winnen.
De Oplosser: Ze gebruikten een bestaande oplosser (SharpSSAT) om deze Sudoku te kraken. Als de oplosser zegt "Ja, deze puzzel kan worden opgelost", betekent dit dat de speler een winnende strategie heeft. Als het een kans van 67% berekent, is dat het best mogelijke resultaat.

4. De "Quantifier Shifting"-truc

Het artikel testte ook een specifieke optimalisatietechniek genaamd Quantifier Shifting.

De Analogie: Stel je voor dat je een toernooi organiseert.
- Methode A (Basislijn): Je lijst elke speler's zet op, controleer vervolgens of de zetten legaal zijn, en controleer daarna of het spel is afgelopen.
- Methode B (Shifting): Je controleert of de zetten legaal zijn voordat je zelfs maar de zetten opschrijft. Dit lijkt sneller omdat je geen tijd verspilt aan het plannen van zetten die illegaal zijn.
Het Resultaat: Bij spellen met twee slimme spelers (deterministische spellen) is deze "Shifting"-truc een enorme snelheidswinst. Echter, de auteurs ontdekten dat bij spellen met de "Gokker" (stochastische spellen) deze truc niet veel verschil maakte.
Waarom? De oplosser die ze gebruikten (SharpSSAT) is zeer slim. Het heeft een ingebouwde "detective" (genaamd unit propagation) die illegale zetten zelfstandig opspoort, ongeacht de volgorde waarin je de instructies gaf. De verfijnde herordening was dus niet nodig voor deze specifieke oplosser.

5. De Resultaten: Hoe presteerde het?

Het team testte hun systeem op variaties van klassieke spellen zoals Drie-op-een-rij, Connect-4 en Nim, maar dan met de "Toeval"-speler toegevoegd.

Prestatie: Hun nieuwe methode was concurrerend met de standaard "forward search"-methoden (die zijn als een computer die het spel miljoenen keren in zijn hoofd speelt om te zien wat er gebeurt).
De Haken: Het werkte uitstekend op kleine borden (zoals 3x3 of 4x4). Echter, toen het spel te groot werd (zoals een stapel van 100 stukken in Nim), werd de logische puzzel te groot voor de computer om in een redelijke tijd op te lossen.
De Conclusie: De methode is uitstekend voor eindspel-evaluatie. Als een spel bijna voorbij is, kan dit systeem een algemene spel-AI vertellen: "Hé, als je deze zet doet, heb je 99% kans om te winnen", waardoor het de uiteindelijke beslissing kan nemen.

Samenvatting

De auteurs creëerden een nieuwe manier om spellen wiskundig te beschrijven waar geluk en strategie botsen. Ze zetten deze beschrijvingen om in logische puzzels die een computer kan oplossen om de "best mogelijke kansen" op winst te vinden. Hoewel het geen wondermiddel is voor elke spelgrootte, bewijst het dat we logisch programmeren kunnen gebruiken om complexe, onzekere spellen op te lossen, waardoor computers een betere manier krijgen om na te denken over de toekomst in een chaotische wereld.

Wat ze NIET beweerden:

Ze beweerden niet dat dit werkt voor spellen waarbij je niet het hele bord kunt zien (zoals Poker of Krieg-Tic-Tac-Toe). Ze stellen expliciet dat hun methode is voor spellen waarbij iedereen het hele bord ziet (perfecte informatie).
Ze beweerden niet dat dit alle andere AI-methoden direct zal vervangen; ze merkten op dat het een alternatief is voor specifieke scenario's, met name eindspelen.

Technische Samenvatting: Een ASP-gebaseerde Aanpak voor het Oplossen van Algemene Stochastische Tweespelersspellen

Probleemstelling

Algemene Spel Spelende (GGP) systemen hebben tot doel strategische spellen te spelen op basis van runtime-beschrijvingen zonder voorafgaande kennis van de regels. De Game Description Language (GDL) en haar uitbreiding GDL-II zijn de standaard formalismen voor het specificeren van dergelijke spellen, waarbij GDL-II ondersteuning biedt voor willekeur (stochasticiteit) en gedeeltelijke waarneembaarheid. Hoewel Answer Set Programming (ASP) met succes is toegepast op het oplossen van deterministische één- en tweespeler GDL-spellen, missen bestaande ASP-kaders de mogelijkheid om zowel adversariele (minimax) als stochastische gedragingen simultaan tot uitdrukking te brengen. Bijgevolg bestaat er een gat in het gebruik van ASP-gebaseerde methoden om tweespeler-spellen met beurten in GDL op te lossen die onzekerheid inhouden.

Methodologie

De auteurs stellen een nieuwe aanpak voor om tweespeler stochastische GDL-spellen op te lossen door een nieuwe taal en een vertalingsgebaseerde solver te introduceren.

1. Stochastisch Gequantificeerd Answer Set Programming (SQASP)

Om het gat tussen ASP en het oplossen van stochastische spellen te overbruggen, introduceert het artikel SQASP, een taal die QASP (Gequantificeerd ASP) uitbreidt met kansquantoren.

Syntaxis: Een SQASP-programma heeft de vorm $Q_1.x_1 \dots Q_n.x_n \ P$ , waarbij $P$ een normaal logisch programma is en de quantoren $Q_i$ existentieel ( $\exists$ ), universeel ( $\forall$ ) of kans ( $\mathcal{R}_{p}$ ) kunnen zijn.
Semantiek: De maximale waarschijnlijkheid om een SQASP-programma te voldoen, wordt recursief gedefinieerd. De kansquantor $\mathcal{R}_{p}$ wijst een waarschijnlijkheid $p$ toe aan een variabele die waar is, en berekent de verwachte waarde op basis van de kansen van de subformules.
Vertaling: De auteurs implementeren een tool, sqasp2xssat, die SQASP-programma's vertaalt naar Extended Stochastic Satisfiability (XSSAT)-formules. XSSAT breidt Gequantificeerde Booleaanse Formules (QBF) uit met kansquantoren. De vertaling maakt gebruik van bestaande tools (zoals lp2sat) om het logische programma $P$ om te zetten in een CNF-formule $\psi$ waarvan de modellen overeenkomen met de stabiele modellen van $P$ .

2. Het Encoderen van GDL-spellen in SQASP

De kernbijdrage is de constructie van een SQASP-programma $\Psi$ zodat zijn maximale vervullingswaarschijnlijkheid gelijk is aan de maximale winstkans van speler $x$ binnen $n$ stappen ( $P_x^w(S_0, n)$ ). De codering verloopt in twee hoofdfasen:

Coöperatieve Baseline: Eerst wordt een logisch programma $P_c$ geconstrueerd onder de aanname dat alle spelers (inclusief de tegenstander $o$ en de willekeurige speler $r$ ) samenwerken om een terminale staat te bereiken waarin $x$ wint. Dit zorgt voor een geldige spelvoortgang, terminatie binnen $n$ stappen en het bereiken van de doelstaat.
Adversariele en Stochastische Modellering: Het programma wordt vervolgens uitgebreid om de specifieke gedragingen van de tegenstander en de omgeving vast te leggen:
- Adversariele Speler ( $o$ ): Gemodelleerd met behulp van universele kwantificering ( $\forall$ ) over beslissingsvariabelen (dec_o). Dit dwingt de solver om het worst-case scenario te overwegen waarin de tegenstander de winstkans van $x$ minimaliseert. De codering maakt gebruik van een logaritmische representatie van acties om het aantal regels te verminderen.
- Stochastische Speler ( $r$ ): Gemodelleerd met behulp van kansquantoren ( $\mathcal{R}_{1/i}$ ). De codering zorgt ervoor dat, als het spel niet is geëindigd, de willekeurige speler precies één legale actie uniform selecteert uit de beschikbare legale zetten. Dit wordt bereikt door het tellen van legale acties en het toepassen van waarschijnlijkhedsbeperkingen op beslissingsvariabelen (dec_r).

3. Kwantificeringsstrategieën

Het artikel onderzoekt twee kwantificeringsstrategieën voor de resulterende XSSAT-formule:

Baseline-methode ( $Q_b$ ): Alle niet-keuze-atomen (bijv. legal, terminal) worden geplaatst in het innerste existentiële blok, volgens een strikte temporele volgorde van keuze-atomen.
Afhankelijkheidsgebaseerde Methode ( $Q_d$ ): Geïnspireerd door technieken voor deterministische spellen, verplaatst deze methode niet-keuze-atomen om zo vroeg mogelijk in de quantor-prefix te verschijnen, direct na de keuze-atomen waarvan ze afhankelijk zijn. Dit beoogt de zoekruimte te verminderen door waarden zoals legal vast te leggen voordat er wordt gebranch op does.

Belangrijkste Bijdragen

Eerste ASP-gebaseerde Solver voor Stochastische GDL: Het artikel presenteert de eerste aanpak om tweespeler, stochastische, beurten GDL-spellen op te lossen met behulp van ASP.
SQASP-taal: De introductie van Stochastisch Gequantificeerd Answer Set Programming, dat adversariele en stochastische redenering verenigt binnen een logisch programmeerkader.
Vertalingsgebaseerde Solver: De ontwikkeling van sqasp2xssat, die SQASP-programma's converteert naar XSSAT-formules, waardoor het gebruik van bestaande XSSAT-solvers (specifiek SharpSSAT) voor speloplossing mogelijk wordt.
Theoretische Correctheid: De auteurs leveren formele bewijzen (Stellingen 2 en 3) die de equivalentie vaststellen tussen de maximale winstkans in het GDL-spel en de maximale vervullingswaarschijnlijkheid van de gegenereerde SQASP/XSSAT-formule.

Experimentele Resultaten

De auteurs evalueerden hun aanpak op stochastische variaties van Tic-Tac-Toe, Connect-4 en Nim, waarbij ze de op SQASP gebaseerde methode (met zowel $Q_b$ als $Q_d$ kwantificering) vergeleken met een forward search Expected Minimax (EMM) solver.

Prestaties: De ASP-gebaseerde aanpak is concurrerend met forward search bij kleine stochastische spellen. In veel gevallen (bijv. Tic-Tac-Toe, Connect-3) berekent de ASP-solver winstkansen die vergelijkbaar zijn met EMM, vaak binnen vergelijkbare tijdsbestekken.
Kwantorverschuiving: Verrassend genoeg leverde de afhankelijkheidsgebaseerde kwantificering ( $Q_d$ ) geen significante prestatieverbeteringen op ten opzichte van de baseline ( $Q_b$ ) bij gebruik van de SharpSSAT solver. De auteurs schrijven dit toe aan SharpSSAT's interne eenheidspropagatiemechanisme, dat waarden van atomen (zoals legal) kan afleiden ongeacht de quantorvolgorde, waardoor de behoefte aan expliciete verschuiving effectief wordt geminimaliseerd.
Schaalbaarheidsbeperkingen: De aanpak heeft moeite met grotere toestandsruimtes, zoals Stochastisch Nim met grote stapelgroottes. De resulterende XSSAT-formules worden te groot (meer dan één miljoen clausules) voor huidige solvers om efficiënt te verwerken, terwijl EMM goed schaalt dankzij dynamische programmering en transpositietabellen.

Betekenis en Beweringen

Het artikel beweert dat de voorgestelde ASP-gebaseerde aanpak een levensvatbaar alternatief biedt voor eindspel-evaluatie in Algemene Spel Spelende systemen. Door de succesvolle toepassing van ASP op deterministische spellen uit te breiden naar het stochastische domein, toont het werk aan dat logisch programmeren onzekerheid en adversariele redenering effectief kan hanteren.

De auteurs merken nederig op dat hoewel de aanpak niet in alle gevallen de forward search domineert (met name voor spellen met zeer grote toestandsruimtes of specifieke structuren zoals Nim), het eerdere resultaten voor deterministische spellen met succes generaliseert naar stochastische spellen. Zij identificeren de uitbreiding naar gedeeltelijke waarneembaarheid (bijv. Poker, Krieg-Tic-Tac-Toe) als een kritieke richting voor toekomstig werk, en erkennen dat de huidige methode beperkt is tot spellen met perfecte informatie.