12 juli 2019

“Pluribus, het computerprogramma dat in 2015 Texas Hold’m poker leerde door tegen 5 kopieën van zichzelf te spelen, is nu (juli 2019) zo goed dat hij ook de beste menselijke pokerspelers verslaat. Hoewel 6-persoons poker in wiskundige zin niet is ‘opgelost’, bleek Pluribus in de praktijk, over vele speelrondes, meer geld te verdienen dan de professionele pokerspelers tegen wie hij speelde. Ook Pluribus doet aan counter factual regret minimalisation, het minimaliseren van spijt achteraf.”

Je leest:

Bluffen werkt niet meer

Bluffen werkt niet meer

Bepaalde variant van poker nu volledig doorgerekend

Auteur: | 10 januari 2015

Een spel met volledige informatie, zoals vier-op-een-rij of schaken, is voor een computer veel makkelijker te behappen dan een spel met onvolledige informatie, zoals poker. Toch is het nu gelukt om een onverslaanbare strategie te berekenen voor Heads up Limit Hold’em.

Computerprogramma’s die menselijke pokerspelers van wereldklasse soms verslaan, zoals Polaris, bestaan al een aantal jaren. Maar dit betekent niet dat het spel poker als zodanig is ‘opgelost’. In vakblad Science rapporteren onderzoekers van de universiteit van Alberta, Canada nu dat dit met een beperkte variant van poker wel gelukt is. Om een optimale strategie te bepalen, waren wel 200 computers, 17 terabyte geheugen en 68 dagen rekenen nodig.

Een spel geldt pas als ‘opgelost’ als je een strategie hebt gevonden waarvan je kunt bewijzen dat die altijd tot winst leidt, of minstens tot het best mogelijke resultaat. Neem als voorbeeld boter-kaas-en-eieren. Als beide spelers optimaal spelen, eindigt dit altijd in gelijkspel. Bewijzen dat er een optimale strategie bestaat is in dit geval triviaal: je kunt zelfs met de hand een complete lijst van mogelijke spelverlopen maken en nagaan, dat je voor elke mogelijke zet van je tegenstander bij een gelijkspel uit kunt komen, en dat voor je tegenstander hetzelfde geldt.

Zephyr03, CC by-sa 4.0 via Wikimedia Commons

Vier-op-een-rij is al een stuk gecompliceerder, maar daarvan werd in 1988 bewezen dat zelfs God van je verliest als jij mag beginnen en je de eerste fiche in de middelste kolom gooit. Het meest serieuze spel dat tot nu toe volledig was doorgerekend was checkers, de Amerikaanse variant van dammen, op een 8×8 bord en met beperktere slagregels voor zowel stenen als dammen. Checkers eindigt bij optimaal spel in remise, en er is een computerprogramma (Chinook) dat inderdaad niet kan verliezen.

Onvolledige informatie

Maar dit betreft allemaal spellen met volledige informatie: beide spelers weten van elkaar precies hoe ze er voor staan. Dat is een ingrijpend verschil met een spel als poker, waarbij je de kaarten van de tegenstander niet ziet en bluf een rol speelt. Uiteraard bestaat bij poker geen deterministische strategie waarmee je elk spelletje poker kunt winnen, daarvoor is de invloed van welke kaarten je toevallig krijgt veel te groot. Bij het zoeken naar een winnende strategie gaat het om het optimaliseren van je inzetten, afhankelijk van je eigen kaarten en informatie die je tijdens het spel verkrijgt over de kaarten van je tegenspelers. Dat levert pas over honderden spelletjes gerekend kleine statistische voordeeltjes op waardoor je, als het goed is, meer – dus niet per se vaker – wint dan je opponenten.

Passen of verhogen: diagram van de strategie voor de dealer in de eerste biedronde, als er nog geen kaarten open liggen. Elke speler heeft dan twee eigen kaarten, die van gelijke of ongelijke ‘kleur’ (harten, ruiten, schoppen, klaver) kunnen zijn, totaal 13 × 13 mogelijkheden. Rood betekent passen, groen betekent verhogen (raise, overbieden).
Michael Bowling

Ook in die optimale strategie speelt toeval een wezenlijke rol, want een strategie die in dezelfde situatie altijd hetzelfde doet, is voorspelbaar voor de tegenstander. En dat is bij poker funest: als de tegenstander zeker weet wanneer je zult passen, wordt je keer op keer weggebluft. Dus zo’n strategie bevat recepten als: met deze kaarten in mijn hand en op tafel, en deze inzetten van de tegenstander, moet ik 7 op de 10 keer passen, 2 op de 10 keer meegaan en 1 op de 10 keer de inzet verhogen. De computer begeeft zich dus niet in redenaties als ‘ik denk dat hij nu denkt dat ik denk dat hij bluft, dus ik zal maar passen’, want er is een optimale kansverdeling die op de lange termijn altijd minstens zo goed scoort.

Texas Hold’em

Canadese onderzoekers onder leiding van computerwetenschapper Michael Bowling, zijn al jaren bezig poker speltheoretisch onder de knie te krijgen, een formidabele klus die minstens zo moeilijk is als het bouwen van Deep Blue II, de schaakcomputer die in 1997 wereldkampioen Gary Kasparov versloeg.

Er zijn veel varianten van poker, maar in dit geval gaat het om Texas Hold’em. Dit is de variant die het vaakst op televisie is en ook online veel gespeeld wordt. Bij Texas Hold’em krijgt iedereen in het begin twee kaarten, waarna er later nog drie kaarten open op tafel komen, daarna nog een vierde, en ten slotte nog een vijfde. Iedereen vormt – in gedachten – de hoogst mogelijke combinatie van vijf kaarten uit zijn eigen en de openliggende kaarten. Er zijn drie rondes waar de spelers passen, meegaan of de inzet verhogen, afhankelijk van hoe ze hun kansen en die van hun tegenstander inschatten.

Passen, meegaan of verhogen: strategie voor een speler als er nog geen kaarten open liggen en de dealer verhoogd heeft. Rood is passen, blauw is meegaan, groen is verhogen. Als een blokje een mengkleur heeft, moet de speler met een zekere kansverdeling kiezen tussen deze twee acties.
Michael Bowling

Texas Hold’em kan gespeeld worden met wel negen spelers tegelijk en met vrij te bepalen inzetten, maar dat gaat de mogelijkheden van de computer nu nog verre te boven. De onderzoekers analyseerden daarom de meest beperkte variant die door mensen serieus gespeeld wordt, namelijk Heads up Limit Hold’em, met maar twee spelers en vaste inzetten per ronde. Niettemin heeft dit spel ruim driehonderdduizend miljard (namelijk 3,19 × 10^14) mogelijke toestanden waarin de spelers een beslissing moeten nemen over passen, meegaan of overbieden.

Spijt minimaliseren

Heel kort samengevat, komt het er op neer dat een computerprogramma zo ongeveer alle mogelijke spellen tegen zichzelf speelt, en dan counter factual regret minimalisation doet. Dat is het minimaliseren van spijt over ‘had ik met wijsheid achteraf toch maar iets anders gedaan’. Iedere keer levert dat een iets betere strategie op, waarmee de computer de volgende uitputtende ronde van spellen in gaat.

Na dit proces 1579 keer herhaald te hebben, is een strategie ontstaan die zeer dicht bij een zogenaamd ‘Nash-evenwicht’ ligt. Een Nash-evenwicht is een fundamentele eigenschap van een brede categorie spellen. In een Nash-evenwicht hebben alle spelers een optimale strategie, in die zin dat geen van de spelers een beter resultaat kan bereiken door in zijn eentje een afwijkende strategie te kiezen. Een Nash-evenwicht betekent dus niet, dat het resultaat voor alle spelers gezamenlijk optimaal is; het is best mogelijk dat ze met z’n allen beter af waren als ze elkaar vertrouwden en samenwerkten, maar in veel spellen – en de echte wereld – krijg je dat niet voor elkaar, omdat er altijd profiteurs zijn die dan gebruik maken van de kwetsbaarheden van een ander om zichzelf asociaal te verrijken.

In zwakke zin, maar wezenlijk opgelost

Bowling en zijn team konden bewijzen, dat ze een strategie hebben waarmee Heads up Limit Hold’em ‘essentially weakly solved’ is: deze strategie ligt zo dicht bij een Nash-evenwicht, dat een menselijke speler die 70 jaar lang iedere dag twaalf uur lang poker speelt, er geen statistisch significant voordeel tegen kan behalen. Deze strategie bestaat dus niet uit een paar slimme regels, maar uit enorme tabellen met gegevens over wat te doen met welke set kaarten in je hand en op tafel, gegeven een zeker biedgedrag van je tegenstander.

Heeft een menselijke speler daar nog wat aan? Toch wel. Ten eerste is nu bewezen, dat de dealer (degene die het laatst aan de beurt is met bieden) een flink voordeel heeft, iets wat al lang vermoed werd. Een ander discussiepunt is nu ook beslist: als dealer moet je eerste actie óf passen, óf overbieden zijn; alleen maar meegaan is vrijwel nooit het beste (zie de eerste illustratie, waarin geen enkel vakje blauw is). Ook blijkt de optimale strategie meer kaarten (ook zwakke) speelbaar te vinden dan professionele spelers, dus past hij relatief weinig in de eerste ronde.

Twee of meer spelers

In hoeverre deze conclusies overdraagbaar zijn op het volledige Texas Hold’em is onzeker. Met maar twee spelers is het verlies van de één gelijk aan de winst van de ander, maar met drie of meer spelers zijn allerlei verdelingen mogelijk, waardoor het aantal mogelijke spellen verveelvoudigt. Ook kunnen spelers dan met elkaar samenspannen om de meest succesvolle speler beentje te lichten. Dan is niet eens meer zeker of het Nash-evenwicht een zinvol concept is om een optimale strategie op te baseren. Toch stellen de onderzoekers dat dit type uitputtende analyse mogelijk ook toepasbaar is op kwesties in de echte wereld, zoals politieke onderhandelingen, veiligheidschecks op vliegvelden en beslissingen over medische behandelingen.

Bron

Dit artikel is een publicatie van NEMO Kennislink.
© NEMO Kennislink, sommige rechten voorbehouden
Dit artikel publiceerde NEMO Kennislink op 10 januari 2015

Discussieer mee

0

Vragen, opmerkingen of bijdragen over dit artikel of het onderwerp? Neem deel aan de discussie.

NEMO Kennislink nieuwsbrief
Ontvang elke week onze nieuwsbrief met het laatste nieuws uit de wetenschap.