Afgelopen februari won de AI Libratus tijdens een pokertoernooi van professionele menselijke spelers. Gisteren werd de werking van Libratus onthuld door de Amerikaanse Carnegie Mellon University.

Libratus is niet de eerste AI die een spel wint; in oktober won AlphaZero van Google van de menselijke kampioen in het spel Go. Bij spellen zoals Go zijn echter alle gegevens van de spelers bekend, terwijl het bij poker de vraag is wat voor kaarten spelers in de hand hebben en of ze bluffen. In februari werd Libratus de eerste kunstmatige intelligentie die professionele, menselijke pokerspelers versloeg. Deze week publiceerde het wetenschappelijke tijdschrift Science een artikel waarin de betrokken onderzoekers de werking van Libratus uitleggen. Libratus bestaat uit drie modules, die we hieronder één voor één doornemen.

 

I: Abstractie

De eerste module van Libratus berekent zogenoemde abstracties. Bij poker kunnen spelers elke ronde met een andere inzet spelen. Als elke mogelijke inzet ($100, $102, $103, etc.) zou worden meegenomen in de berekening zou een AI eindeloos bezig zijn, dus hier is een oplossing voor bedacht. Er zit bijvoorbeeld weinig verschil tussen een inzet van $101 en $102. Door alleen met meervouden van $100 rekenen, wordt de berekening een stuk makkelijker. Dit is een voorbeeld van een abstractie: een simpelere versie van een spel, die de strategische aspecten van het oorspronkelijke spel zoveel mogelijk behoudt. Een abstractie zorgt ervoor dat het spel een stuk minder complex wordt. De abstracties die Libratus tijdens het spel gebruikte bestonden uit fracties of meervouden van de pot.

Een andere vorm van abstractie die Libratus gebruikt, heeft te maken met de verschillende kaarten in het spel. Vergelijkbare handen worden gegroepeerd en als hetzelfde beschouwd. Op deze manier worden bijvoorbeeld een heren en vrouwenflush (een flush is een reeks van vijf kaarten van dezelfde kleur, waarbij de hoogste kaart de winnaar bepaalt als meerdere spelers een flush hebben) bij elkaar gezet. Deze abstractie maakt het spel minder complex, waardoor de berekening makkelijker wordt.

 

Credit: sourceforge.net

 

Blauwdruk

Nadat de abstracties geconstrueerd waren, berekende het algoritme een zogenaamde blueprint strategy: de oplossing voor de abstractie. De blueprint strategy werd gemaakt door Libratus gesimuleerde pokerspellen tegen zichzelf te laten spelen. Hierbij werd het Monte Carlo Counterfactual Regret Minimization (MCCRM) algoritme gebruikt. Dit algoritme berekent en onthoudt ‘spijtwaarden’ voor elke actie in het spel; de spijtwaarde geeft weer hoeveel spijt de AI heeft van het niet uitvoeren van een bepaalde actie in het verleden.

Wanneer een AI een keuze moet maken tijdens het gesimuleerde spel, is de kans groot dat hij een actie met een hoge spijtwaarde kiest. Hierdoor vallen de hoge spijtwaarden als het ware weg tijdens volgende spellen (de AI heeft immers geleerd om deze acties wel uit te voeren) en blijven acties met lagere spijtwaarden over. Na een groot aantal spellen zorgt dit ervoor dat de gemiddelde spijtwaarde per actie bijna nul wordt. Hierdoor verbetert de gemiddelde strategie van de AI naarmate er meer gesimuleerde spellen worden gespeeld.

Tijdens het spel zijn er veel acties die duidelijk onvoordelig zijn. Het zou een verspilling van rekenkracht zijn als deze acties elke keer verkend werden; daarom rekent het MCCRM algoritme slechts met een deel van de mogelijke acties. Dit houdt in dat onvoordelige acties worden overgeslagen naarmate het spel vordert. Door deze techniek kan het MCCRM algoritme driemaal sneller werken.

 

II: Subgame solving

De tweede module van Libratus wordt gebruikt tijdens latere spelrondes en maakt gebruik van subgame solving; dit houdt in dat de AI een gedetailleerde strategie uitdenkt, gebaseerd op de huidige status van het spel (de subgame). Daarbij zorgt Libratus ervoor dat de strategie voor de subgame binnen de overkoepelende blueprint strategy voor de oorspronkelijke abstractie past. Op deze manier wordt de blueprint strategy gedetailleerder, waardoor de huidige strategie kan worden verbeterd.

 

Credit: Eingescannt durch Nyks

III: De zelfverbeteraar

De derde module van Libratus is de zelfverbeteraar. Het verbetert de blueprint strategy door missende onderdelen toe te voegen en strategieën te bedenken voor deze onderdelen; als Libratus een spel verliest door een bepaalde tactiek van een tegenstander, berekent hij een nieuwe strategie voor het volgende spel. Dit houdt in dat tegenstanders een goeie tactiek maar één keer kunnen gebruiken voordat Libratus er een oplossing voor verzint. Libratus kan dus compleet van strategie veranderen tussen twee spellen en blijft daardoor onvoorspelbaar voor zijn tegenstanders.

'Het was net of Libratus mijn kaarten kon zien, zó goed was hij', aldus één van de menselijke pokerspelers

Het bijzondere aan Libratus is dat zijn makers hem niet hebben geleerd hebben hoe hij goed kan pokeren. Libratus kende aan het begin enkel de regels van poker, en leerde vervolgens zichzelf welke strategie het beste werkte. Bovendien gedraagt Libratus zich heel anders dan een mens: een mens heeft vaak een vaste tactiek voor bepaalde handen, maar Libratus is in staat om verschillende acties te ondernemen met dezelfde hand. Verder doet Libratus soms dingen die door mensen als ‘raar’ worden beschouwd, zoals ver onder of juist ver boven de waarde van de pot inzetten. Dit draagt bij aan de onvoorspelbaarheid van Libratus.

Afgelopen februari won Libratus het 20-daagse heads-up no-limit Texas hold’em pokertoernooi. Eén van de tegenspelers van Libratus vertelde dat het net was alsof Libratus zijn kaarten kon zien; zó goed was hij. Dankzij de overwinning won Libratus $200,000. Hij mocht het ook opnemen tegen andere AI pokerspelers. Hierbij versloeg Libratus onder andere Baby Tartanian8, een AI ontwikkeld door Sandholm en Brown, die in 2016 de Annual Computer Poker Competition won.

Tekst: Maaike Lambers

Openingsfoto: pixabay.com