Dominated Actions in Imperfect-Information Games

Dit artikel introduceert een polynomiaal-tijdsalgoritme voor het efficiënt identificeren en iteratief verwijderen van gedomineerde acties in imperfecte-informatiespellen met twee spelers en publiek waarneembare acties, waardoor de grootte van de spelboom als voorbewerkingsstap voor het berekenen van een Nash-evenwicht aanzienlijk kan worden gereduceerd.

De kern

Stel je voor dat je een enorm, ingewikkeld labyrint voor je hebt. In dit labyrint zitten talloze doolhoven, valkuilen en afgeleide paden. Je doel is om de kortste en veiligste route naar de uitgang te vinden (in de wereld van de game-theorie heet dit een "Nash-evenwicht" vinden).

Dit artikel van Sam Ganzfried gaat over een slimme manier om dit labyrint te versimpelen voordat je überhaupt begint met zoeken. Het gaat over het vinden van "dominante acties" in spelletjes waar je niet alles ziet (imperfect information), zoals poker.

Hier is de uitleg in simpele taal, met een paar creatieve vergelijkingen:

1. Het Probleem: Een te grote puzzel

In de wereld van spelletjes (zoals schaak of poker) proberen computers vaak de perfecte strategie te berekenen.

• Bij simpele spelletjes (waar iedereen alles ziet, zoals schaak) is dit al best goed opgelost. Je kunt makkelijk zien welke zetten "dom" zijn en die weglaten.
• Bij complexe spelletjes (waar je niet alles ziet, zoals poker) wordt het een nachtmerrie. Als je probeert het spel om te zetten naar een simpele lijst met alle mogelijke zetten, wordt die lijst exponentieel groter. Het is alsof je probeert een heel universum in je hoofd te houden. Het wordt te groot om te berekenen.

2. De Oplossing: Het "Snoeien" van de boom

De auteur zegt: "Wacht even, we hoeven niet het hele labyrint te doorzoeken. We kunnen eerst de dode hoekjes en de paden die nooit slim zijn, gewoon afknippen."

In de wiskunde noemen we dit dominantie:

• Strikte dominantie: Stel je voor dat je twee routes hebt. Route A brengt je altijd 10 minuten sneller aan dan Route B, ongeacht wat er gebeurt. Dan is Route B "strak gedomineerd". Je zou gek zijn om Route B te kiezen.
• Zwakke dominantie: Route A is meestal sneller, en op zijn minst nooit langzamer dan Route B. Ook hier kun je Route B veilig weglaten.

Het probleem in complexe spelletjes (zoals poker) is dat het lastig is om te bepalen of een zet "dom" is, omdat het afhangt van wat de tegenstander doet en wat je op dat moment weet.

3. De Nieuwe Methode: Een slimme filter

De auteur ontwikkelt een nieuwe definitie en een algoritme (een recept voor een computer) om deze "domme" zetten te vinden, zelfs in spelletjes waar je niet alles ziet.

De Analogie van de "Openbare Straat":
Stel je een spel voor waarbij spelers hun zetten doen op een openbare straat waar iedereen ze kan zien (dit noemen ze "publiek waarneembare acties").

• De auteur bedacht een slimme manier om te kijken: "Als ik deze specifieke zet doe, kan ik er altijd beter uitkomen dan als ik die andere zet doe, alleen maar op de momenten dat we überhaupt op dat punt in het spel zijn?"
• Het algoritme gebruikt wiskundige formules (lineaire programmering) om dit in polynomiale tijd te doen. Dat klinkt ingewikkeld, maar betekent simpelweg: "Het duurt niet eeuwen, maar een paar seconden, zelfs bij grote spelletjes."

4. Het Experiment: Poker "All-In of Fold"

Om te bewijzen dat dit werkt, heeft de auteur dit getest op een populair poker-tijdstip: "All-In or Fold".

• De situatie: Twee spelers, een beperkt aantal fiches. Je kunt alleen maar "All-in" (alle fiches inzetten) of "Fold" (opgeven).
• Het resultaat:
  • In een spel met 169 mogelijke handen per speler, bleek dat het computerprogramma honderden van deze handen als "dom" kon bestempelen.
  • Het spel werd van 169 opties per speler teruggebracht tot slechts 70 of 84.
  • De winst: Het spel werd meer dan 50% kleiner. Het is alsof je een berg papier hebt die je in één keer tot een klein boekje hebt gereduceerd.

5. Waarom is dit belangrijk?

Stel je voor dat je een gigantische bibliotheek moet doorzoeken om één boek te vinden.

• Zonder deze methode: Je moet elke hoek van elke plank controleren. Het duurt dagen.
• Met deze methode: Je gooit eerst alle boeken weg die duidelijk niet het juiste zijn (de "dominante acties"). Plotseling is de bibliotheek half zo groot. Nu kun je het juiste boek (de perfecte strategie) veel sneller vinden.

Dit is cruciaal voor het ontwikkelen van superieure poker-bots en het oplossen van andere complexe strategische problemen. Het maakt het mogelijk om spelletjes op te lossen die voorheen te groot waren om zelfs maar te proberen.

Samenvatting in één zin

Sam Ganzfried heeft een slimme manier bedacht om in complexe spelletjes (zoals poker) alle "domme" zetten eruit te knippen voordat je begint met rekenen, waardoor het spel zo klein wordt dat computers het perfect kunnen oplossen.

Technische samenvatting

Titel: Gedomineerde Acties in Spellen met Imperfecte Informatie

Auteur: Sam Ganzfried (Ganzfried Research)

---

1. Probleemstelling

In de speltheorie is het concept van dominantie fundamenteel. In normale-vormspellen (simultane zetten) kunnen gedomineerde strategieën in polynomiale tijd worden geïdentificeerd en iteratief verwijderd om de spelgrootte te reduceren voordat een Nash-evenwicht wordt berekend.

Het probleem ontstaat bij spellen met imperfecte informatie in uitgebreide vorm (extensive-form games), zoals poker:

• Het converteren van een spel in uitgebreide vorm naar normale vorm leidt vaak tot een exponentiële toename in de grootte van het spel, waardoor het verwijderen van gedomineerde strategieën via conversie onpraktisch wordt.
• Bestaande definities van dominantie voor acties in uitgebreide vorm zijn ofwel te zwak (ze houden geen rekening met de context van de informatie-set) of te sterk (ze vereisen dat een actie in alle mogelijke eindtoestanden beter is, wat zelden voorkomt).
• Er ontbreekt een efficiënt algoritme om te bepalen of een specifieke actie in een informatie-set gedomineerd wordt door een gemengde strategie (behavioral strategy) binnen de context van het uitgebreide spel, zonder het spel eerst te converteren.

2. Methodologie

Definities van Gedomineerde Acties

De auteur analyseert eerst enkele kandidaat-definities en toont aan waarom deze tekortschieten:

• Sterke dominantie (Strong Dominance): Een actie is gedomineerd als de uitbetaling in elk bladknooppunt dat volgt op die actie strikt lager is dan die van een andere actie. Dit is te streng; een actie kan rationeel zijn in sommige scenario's ondanks slechte uitkomsten in andere.
• Kandidaat-definitie 3: Een actie is gedomineerd als er een strategie bestaat die die actie nooit speelt en altijd beter presteert. Het probleem hiermee is dat deze strategieën het spel kunnen verlaten voordat de relevante informatie-set wordt bereikt, wat de vergelijking ongeldig maakt.

De auteur introduceert nieuwe, robuuste definities voor strikt en zwak gedomineerde acties:

• Een actie $a_i$ in informatie-set $I_i$ is strikt gedomineerd als er een behaviorale strategie $\sigma_{-a_i}$ bestaat die $a_i$ met waarschijnlijkheid 0 speelt, maar altijd de weg naar $I_i$ bereikt (zodanige acties worden geselecteerd), en die voor elke tegenstanderstrategie $\sigma_{-i}$ (die ook $I_i$ bereikt) een strikt hogere verwachte uitbetaling oplevert dan elke strategie die $a_i$ met waarschijnlijkheid 1 speelt.
• Deze definities zorgen ervoor dat de vergelijking alleen plaatsvindt binnen de context van sporen die daadwerkelijk de informatie-set bereiken.

Het Algorithmische Framework

De kern van de bijdrage is een polynomiaal tijd-algoritme om gedomineerde acties te detecteren in twee-speler spellen met perfecte herinnering en publiek waarneembare acties.

• Representatie: Het spel wordt gemodelleerd met de sequence form (sequentievorm), waarbij elke rij een informatie-set voorstelt en elke kolom een actie-sequentie. Dit vermijdt de exponentiële blow-up van de normale vorm.
• Linear Programming (LP): Het probleem wordt geformuleerd als een reeks lineaire programmeringsproblemen.
  • Om te testen of actie $c$ strikt gedomineerd is, wordt een LP-oplossing gezocht die de maximale uitbetaling vergelijkt tussen een strategie die $c$ vermijdt en een strategie die $c$ speelt, onder de beperking dat alleen tegenstander-sequenties die $I_i$ bereiken worden overwogen.
  • Het algoritme lost twee sub-problemen op (voor strikte dominantie) en eventueel twee extra (voor zwakke dominantie) door de optimalisatie te splitsen in een deel voor de tegenstander en een deel voor de speler zelf.
• Iteratief Verwijdering: Het proces kan herhaald worden om gedomineerde acties iteratief te verwijderen totdat er geen meer zijn.

3. Belangrijkste Bijdragen

1. Nieuwe Definitie: Een rigorieuze definitie van gedomineerde acties in uitgebreide vormspellen die rekening houdt met de beperkingen van imperfecte informatie en de noodzaak om de informatie-set te bereiken.
2. Polynomiaal Tijd Algoritme: Bewijs dat het bepalen van strikte en zwakke dominantie voor een actie in een twee-speler spel met perfecte herinnering en publieke acties in polynomiale tijd kan worden gedaan.
   • Stelling 1 & 2: Er bestaan polynomiale algoritmen voor strikte en zwakke dominantie.
   • Stelling 3: Iteratief verwijderen van gedomineerde acties is ook polynomiaal.
3. Generalisatie: Het algoritme werkt voor behaviorale strategieën (gemengde acties binnen een informatie-set), niet alleen voor pure acties.
4. Empirische Validatie: Toepassing op "All-In or Fold" No-Limit Texas Hold'em poker om de praktische bruikbaarheid te demonstreren.

4. Resultaten

De auteur testte het algoritme op een 2-speler No-Limit Texas Hold'em spel waarbij spelers alleen kunnen "All-in" (shove) of "Folden" (met stackgroottes van 5 tot 8 big blinds).

• Stackgrootte 8x Big Blind:
  • Initieel: 169 handen per speler.
  • Na verwijdering: Speler 1 heeft 84 handen over, Speler 2 heeft 70 handen.
  • Resultaat: Meer dan 50% reductie in het aantal beslispunten.
• Stackgrootte 5x Big Blind:
  • Na 5 rondes van iteratieve verwijdering: Speler 1 heeft 25 handen over, Speler 2 heeft 16 handen.
• Kleinere Stacks (3-4x BB): Het spel kan volledig worden opgelost (tot een klein aantal acties gereduceerd) na slechts 2-4 rondes.
• Tabel 1 & 2: De paper presenteert gedetailleerde tabellen die aangeven welke handen (bijv. A-K suited) in welke iteratie worden gedomineerd en verwijderd.

De resultaten tonen aan dat iteratief verwijderen van gedomineerde acties de grootte van realistische imperfecte-informatiespellen aanzienlijk kan verkleinen.

5. Significantie en Toekomstperspectief

• Efficiënte Preprocessing: Het verwijderen van gedomineerde acties dient als een krachtige preprocessing-stap voor het berekenen van Nash-evenwichten. Het verkleint de zoekruimte aanzienlijk, wat essentieel is voor complexe spellen.
• Impact op Meerdere Spelers: Hoewel dit werk zich richt op twee spelers, wordt verwezen naar recent werk waarbij het verwijderen van gedomineerde acties het mogelijk maakte om een drie-speler imperfecte-informatiespel in minder dan 3 seconden op te lossen, terwijl een algoritme zonder deze reductie 24 uur nodig had zonder het spel op te lossen.
• Open Vragen: De complexiteit van het vinden van gedomineerde acties in spellen zonder perfecte herinnering of zonder publiek waarneembare acties blijft een open probleem. Ook de complexiteit voor $n > 2$ spelers vereist verder onderzoek.

Conclusie:
Dit artikel vult een belangrijke lacune in de speltheorie door een efficiënte methode te bieden om de complexiteit van imperfecte-informatiespellen te reduceren via dominantie-analyse, zonder de noodzaak van een onpraktische conversie naar normale vorm. Dit maakt het berekenen van evenwichten in realistische scenario's zoals poker veel haalbaarder.