Poker maar niet meer tegen de computer

Een veel gespeelde pokervariant is gekraakt. Eén tegen één kan de computer nu spelen zonder te verliezen. Tegen meerdere opponenten nog niet.

Foto Bloomberg
Foto Bloomberg

Een pokerface en bluffen komt er niet aan te pas, wel erg veel rekenwerk: voor het eerst kan een computer het pokerspel Limit Texas Hold’em zo goed spelen dat de machine niet verliest, al zou een pokeraar er levenslang tegen spelen.

Dat melden computerwetenschapper Michael Bowling en collega’s van de University of Alberta, samen met de Finse programmeur Oskari Tammelin, in Science.

Boter, kaas en eieren? 765 posities

Texas Hold’em is daarmee het nieuwste slachtoffer van de speltheorie. Om simpele spellen voorgoed te doorgronden, zijn niet altijd zware computers nodig. Het spel boter, kaas en eieren kent maar 765 wezenlijk verschillende posities. Weergegeven in een ‘spelboom’ passen die op een fors vel papier. Een computer put ze moeiteloos uit zijn geheugen.

In elke positie zijn een aantal verschillende zetten mogelijk, die je kunt weergeven als vertakkingen in de spelboom. Met zo’n schema is de optimale spelstrategie te bepalen. Optimaal gespeeld eindigt boter, kaas, en eieren altijd in gelijkspel.

Met de komst van computers kwam het onderzoek naar ingewikkelder spellen op gang. Cruciaal is het idee van het Nash-evenwicht, genoemd naar de Amerikaanse wiskundige John Nash (gespeeld door Russell Crowe in de film A Beautiful Mind). Het Nash-evenwicht is een strategie waarbij geen speler zijn uitkomst kan verbeteren door iets anders te doen.

Vier op een rij? 4.531.985.219.092

In 1988 werd met dat instrumentarium het spel vier-op-een-rij doorgerekend, met 4.531.985.219.092 mogelijke spelposities. De speler die de eerste zet doet, kan altijd winnen. De volgende prooi was Amerikaans dammen of checkers (op een 8x8-bord, 500 miljard miljard posities, optimaal spel leidt tot gelijkspel).

Bijzonder moeilijk te kraken zijn kaartspellen waarbij de spelers niet over alle beschikbare informatie beschikken. Waar een dammer het hele bord kan overzien, houden pokerspelers hun eigen kaarten angstvallig buiten het zicht van de tegenstanders.

Zulke ‘incomplete informatie’-spellen maken het vinden van een Nash-evenwicht veel lastiger: twee spelposities die voor de ene speler niet te onderscheiden zijn, zijn dat voor de andere speler juist wel, en andersom.

Bowling en collega’s lukte het toch met hun Counterfactual Regret Minimization, een algoritme dat getraind wordt om de ‘spijt’ te minimaliseren. Dat is het verschil in uitkomst tussen de werkelijk gespeelde strategie en de (pas achteraf precies bekende) optimale strategie.

Uitrekenen bij poker duurde ‘900 jaar’

Iemand die volgens die optimale strategie 70 jaar lang elke dag 2.400 spellen poker speelt, berekenen de onderzoekers, heeft statistisch geen significante kans om te verliezen. Het opstellen van de spelboom waar een computer bij het spelen voortaan uit kan putten, kostte meer dan 900 processorjaren aan rekentijd. Verdeeld over 200 computers met ieder 24 processoren kwam dat neer op 69 dagen. Het doorrekenen van poker met meer dan twee spelers is daardoor voorlopig praktisch onmogelijk.

Tegenstanders op de jaarlijkse Annual Computer Poker Competition, een toernooi waarbij computerprogramma’s tegen elkaar spelen, kunnen dus wel inpakken. Maar menselijke pokerspelers hoeven zich nog geen zorgen te maken: de doorgerekende variant wordt op wedstrijden en in casino’s wel gespeeld, zegt pokerjournalist Mark Roovers van de website Pokercity.nl, „maar eigenlijk nooit in de Heads-up variant met twee personen.” Online kan dat wel, zegt hij, „maar daar wordt vrij streng gecontroleerd op het gebruik van computeralgoritmes. Die verraden zich uiteindelijk toch in de speelstijl.”