Computer ontdekt ultieme pokerstrategie
Wie begint met vier op een rij en perfect speelt wint altijd. Dammen eindigt dan weer altijd in een gelijkspel indien geen van de spelers fouten maakt. Beide spellen werden ‘opgelost’ door computers. Dat wil zeggen dat er een computer de optimale strategie heeft uitgedokterd. Datzelfde is nu gebeurd met Texas Hold’em poker, al was daar wel wat rekenkracht voor nodig.
Imperfecte informatie
Vier op een rij en dammen zijn zogenoemde spellen met perfecte informatie. Iedere speler weet ten allen tijde alles wat er te weten valt. Poker is het ultieme voorbeeld van een spel met imperfecte informatie. Een deel van de relevante gegevens om beslissingen te maken, is verborgen. Dat maakt het oplossen van het spel moeilijk. “Poker is al meer dan 40 jaar een uitdaging voor AI-onderzoekers”, aldus Michael Bowling. Hij loste heads-up limit Texas Hold’em op samen met zijn team aan de universiteit van Alberta en een kamer boordevol computers. Hun onderzoek noemden ze het Cepheus Poker Project.
[related_article id=”160734″]
Flinke boom
Het uitdokteren van een perfecte strategie vereist flink wat rekenwerk. Alles begint met een boomdiagram dat niet bepaald op een A4-tje past. Alle mogelijke combinaties van gekregen kaarten en acties worden daarop uitgewerkt. De getallen die daar met gepaard gaan zijn hallucinant. Het uitwerken van heads-up limit Texas Hold’em levert 1,38×10^13 datasets op.
De klassieke manier om aan de hand van zo’n diagram de beste strategie te destilleren heet counterfactual regret minimization (CFR). Daarbij worden alle mogelijke pokerspellen gespeeld. Op elk moment in al die mogelijke spellen dat de speler een beslissing moest maken (pass, call of raise), kijkt men op welke manieren die beslissing kon uitdraaien. Zo weten de onderzoekers van iedere keuze of ze statistisch goed of slecht is, om zo uiteindelijk voor ieder pokerhand tot de beste actie te komen (rekening houdend met de acties van andere spelers). Een computersysteem dat CFR moet toepassen op Texas Hold’em heeft 262 terabyte aan geheugen nodig. Om nog niet te spreken van de rekenkracht vereist om tot een resultaat te komen. Dus Bowling en de zijnen gingen op zoek naar een efficiëntere methode.
Maanden rekenwerk
CFR+ verfijnt CFR door niet zomaar alle mogelijke pokersituaties af te lopen. Het algoritme is slimmer en weet sneller welke spelbeslissingen niet goed zullen uitdraaien. Zelfs met CFR+ had het team 200 computers nodig met elk 24 2,1 GHZ AMD-kernen, 32 GB RAM en een HDD van 1 TB. De eerste computer keek welke openingsscenario’s mogelijk waren en verdeelde het rekenwerk per scenario onder de 199 andere systemen. Ook met die techniek duurde het 68 en een halve dag om de optimale pokerstrategie te berekenen.
De dealer doet zijn voordeel
Het resultaat bevestigde alvast één wijsheid onder de pokerspelers: de dealer heeft een significant voordeel. Verder bleek dat het geen goed idee is om te callen als eerste actie. Ook het hoogst toegestane bod uitbrengen, leidt in de meeste gevallen niet tot de beste resultaten. Verder hangt de optimale strategie natuurlijk af van de situatie. De universiteit zette een website online waar je voor alle handen de beste actie kan ontdekken. De website reageert niet echt snel: de server moet zoeken naar het juiste antwoord in twaalf terabyte aan voorgerekende data, maar dat is nog steeds beduidend sneller dan de twee maanden die nodig waren om de dataset samen te stellen. (Leuk detail: met één rekenkern zou het werk 900 jaar geduurd hebben).
Toepassingen
Wie wil vals spelen om de grote pot van het lokale pokertoernooi te winnen heeft bij deze de link naar de juiste tool. Hoewel Bowling en zijn team toegeven dat het oplossen van Texas Hold’em vooral een persoonlijke uitdaging was, is het onderzoek bijzonder interessant voor de ontwikkeling van artificiële intelligentie. De algoritmes gebruikt om spellen met imperfecte informatie op te lossen zijn immers erg belangrijk in processen waarbij computers beslissingen moeten maken gebaseerd op beperkte gegevens. Denk hierbij aan geautomatiseerde beveiligingssystemen of medische applicaties.
Wie begint met vier op een rij en perfect speelt wint altijd. Dammen eindigt dan weer altijd in een gelijkspel indien geen van de spelers fouten maakt. Beide spellen werden ‘opgelost’ door computers. Dat wil zeggen dat er een computer de optimale strategie heeft uitgedokterd. Datzelfde is nu gebeurd met Texas Hold’em poker, al was daar wel wat rekenkracht voor nodig.
Imperfecte informatie
Vier op een rij en dammen zijn zogenoemde spellen met perfecte informatie. Iedere speler weet ten allen tijde alles wat er te weten valt. Poker is het ultieme voorbeeld van een spel met imperfecte informatie. Een deel van de relevante gegevens om beslissingen te maken, is verborgen. Dat maakt het oplossen van het spel moeilijk. “Poker is al meer dan 40 jaar een uitdaging voor AI-onderzoekers”, aldus Michael Bowling. Hij loste heads-up limit Texas Hold’em op samen met zijn team aan de universiteit van Alberta en een kamer boordevol computers. Hun onderzoek noemden ze het Cepheus Poker Project.
[related_article id=”160734″]
Flinke boom
Het uitdokteren van een perfecte strategie vereist flink wat rekenwerk. Alles begint met een boomdiagram dat niet bepaald op een A4-tje past. Alle mogelijke combinaties van gekregen kaarten en acties worden daarop uitgewerkt. De getallen die daar met gepaard gaan zijn hallucinant. Het uitwerken van heads-up limit Texas Hold’em levert 1,38×10^13 datasets op.
De klassieke manier om aan de hand van zo’n diagram de beste strategie te destilleren heet counterfactual regret minimization (CFR). Daarbij worden alle mogelijke pokerspellen gespeeld. Op elk moment in al die mogelijke spellen dat de speler een beslissing moest maken (pass, call of raise), kijkt men op welke manieren die beslissing kon uitdraaien. Zo weten de onderzoekers van iedere keuze of ze statistisch goed of slecht is, om zo uiteindelijk voor ieder pokerhand tot de beste actie te komen (rekening houdend met de acties van andere spelers). Een computersysteem dat CFR moet toepassen op Texas Hold’em heeft 262 terabyte aan geheugen nodig. Om nog niet te spreken van de rekenkracht vereist om tot een resultaat te komen. Dus Bowling en de zijnen gingen op zoek naar een efficiëntere methode.
Maanden rekenwerk
CFR+ verfijnt CFR door niet zomaar alle mogelijke pokersituaties af te lopen. Het algoritme is slimmer en weet sneller welke spelbeslissingen niet goed zullen uitdraaien. Zelfs met CFR+ had het team 200 computers nodig met elk 24 2,1 GHZ AMD-kernen, 32 GB RAM en een HDD van 1 TB. De eerste computer keek welke openingsscenario’s mogelijk waren en verdeelde het rekenwerk per scenario onder de 199 andere systemen. Ook met die techniek duurde het 68 en een halve dag om de optimale pokerstrategie te berekenen.
De dealer doet zijn voordeel
Het resultaat bevestigde alvast één wijsheid onder de pokerspelers: de dealer heeft een significant voordeel. Verder bleek dat het geen goed idee is om te callen als eerste actie. Ook het hoogst toegestane bod uitbrengen, leidt in de meeste gevallen niet tot de beste resultaten. Verder hangt de optimale strategie natuurlijk af van de situatie. De universiteit zette een website online waar je voor alle handen de beste actie kan ontdekken. De website reageert niet echt snel: de server moet zoeken naar het juiste antwoord in twaalf terabyte aan voorgerekende data, maar dat is nog steeds beduidend sneller dan de twee maanden die nodig waren om de dataset samen te stellen. (Leuk detail: met één rekenkern zou het werk 900 jaar geduurd hebben).
Toepassingen
Wie wil vals spelen om de grote pot van het lokale pokertoernooi te winnen heeft bij deze de link naar de juiste tool. Hoewel Bowling en zijn team toegeven dat het oplossen van Texas Hold’em vooral een persoonlijke uitdaging was, is het onderzoek bijzonder interessant voor de ontwikkeling van artificiële intelligentie. De algoritmes gebruikt om spellen met imperfecte informatie op te lossen zijn immers erg belangrijk in processen waarbij computers beslissingen moeten maken gebaseerd op beperkte gegevens. Denk hierbij aan geautomatiseerde beveiligingssystemen of medische applicaties.
