Matematikeres computerprogram spiller perfekt poker

Canadiske matematikere har udviklet computerprogrammet Cepheus, som spiller Texas Hold'em-poker med den optimale strategi. Det er umuligt at vinde mod programmet - prøv selv.

Det pokerprogram, som matematikere fra University of Alberta i Canada har udviklet, er ikke værd at spille imod. Man har nemlig ikke en chance.

Computeren er ikke til at slå, for den har gennemskuet spillet. Programmet Cepheus spiller Heads-up Limit Texas Hold'em på den mest optimale måde, så selv den stærkeste pokerspiller vil højst kunne drømme om at spille lige op mod computeren.

I samme ombæring har de canadiske matematikere bekræftet, at kortgiveren har en lille fordel i spillet. Resultaterne præsenteres i en videnskabelig artikel i tidsskriftet Science.

Michael Bowling og hans forskerhold på University of Alberta har fundet frem til den bedste pokerstrategi. (Foto: John Ulan, University of Alberta)

En strategi uden svagheder

Troels Bjerre Sørensen, der er adjunkt på IT-Universitetet i København, har beskæftiget sig med spilteori i mange år, og har da også været med til at finde frem til gode strategier for poker. Han forklarer det nye resultat sådan her:

»De har beregnet en minimax-strategi for spillet. Det betyder, at de har fundet den strategi, som klarer sig bedst muligt imod de stærkeste modstandere. Selv hvis strategien offentliggøres, og modstanderen studerer den og vælger den bedste modstrategi overhovedet, kan han ikke forvente at slå programmet.«

»Det er en strategi uden svagheder - uden huller. Der er intet, en modstander kan udnytte.«

Billiarder af muligheder

Texas Hold'em er verdens mest populære form for poker. Her får hver spiller to kort på hånden, og så gælder dem om at få den bedste pokerhånd med fem kort blandt sine egne kort kombineret med de fem fælleskort, der vendes på bordet.

Når der kun er to deltagere i spillet, og man kun kan satse faste beløb, kaldes spillet for Heads-up Limit Texas Hold'em, og det er dette spil, forskerne har fundet den bedste strategi for.

Læs også: 27 millioner pokerspil analyseret: Par to bedre end et par knægte

Heads-up Limit Texas Hold'em er et simplere spil end varianten uden loft og med flere deltagere, men der er immervæk stadig omkring 316.000.000.000.000.000 forskellige måder, kortene kan blive uddelt og satsningerne kan foretages.

De overvældende mange muligheder betyder, at forskerne trods alt ikke har fundet det helt præcise matematiske svar på, hvad den bedste strategi er. Men ved hjælp af en supercomputer, der har kørt i et par måneder, har de fundet en strategi, som er så tæt på at være optimal, at computeren ikke kan forventes slået, om så man er verdens bedste pokerspiller, der har fundet den optimale modstrategi, og som spiller mod den uafbrudt igennem et helt liv.

Ikke en pengemaskine

Selvfølgelig kan man være heldig at få gode hænder, så man kommer foran mod Cepheus. Men i længden har man altså ikke en chance for at vinde. Det betyder dog ikke nødvendigvis, at man får læsterlige klø af computeren. Den er nemlig ikke programmeret til at vinde stort, men kun til at undgå nederlag.

»Strategien har ikke særlig meget frihed til at udnytte modstanderens svagheder. Det er en meget sikker strategi at bruge. Men det ikke en, man kan bruge til at vinde en masse penge fra en svag modstander,« fortæller Troels Bjerre Sørensen.

Med lidt held kan man godt komme foran mod pokerprogrammet Cepheus, men i længden har man ikke en chance.

»Med denne strategi sikrer man sig mod tab - der en ingen huller i skjoldet. Man kan ikke tabe, men omvendt er der ingen garanti for, at man vinder. Mod en stærk modstander går man højst sandsynligt i nul.«

»Man skal bruge en anden strategi, hvis man vil udnytte svage spillere. Men sådan en strategi vil kunne blive udnyttet af stærke spillere. Når du sænker dit skjold for at hæve sværdet, så viser du dine egne svagheder.«

Manglende information er en udfordring

Som pokerspiller har man ikke overblik over, hvilke kort de øvrige spillere sidder med eller tidligere har smidt. På den måde adskiller poker sig fra spil som kryds-og-bolle, fire på stribe, dam eller backgammon, hvor begge spillere har adgang til al information om spillet. Man siger, at poker er et spil med uperfekt information.

Rent matematisk er det sværest at finde den bedste strategi for spil med uperfekt information, og derfor er det noget af en bedrift, at det nu er lykkedes.

Ifølge professor Michael Bowling, der stod i spidsen for den canadiske forskergruppe, har poker været en udfordring for forskere inden for kunstig intelligens i mere end 40 år, men det er altså først nu, det er lykkedes at knække spillet - eller i hvert fald varianten Heads-up Limit Texas Hold'em.

Kan give bedre sikkerhed

Resultatet kan ikke kun anvendes i forbindelse med poker. For spilteori bruges i mange sammenhænge. De metoder, forskerne anvendte for at komme frem til den optimale strategi for poker, kan for eksempel også føre til bedre strategier inden for sikkerhed, forklarer Troels Bjerre Sørensen:

»Denne type algoritmer bliver i stor stil anvendt i security-sammenhænge. I en lufthavn råder man over et begrænset antal vagter, og så gælder det om at sørge for, at de bliver placeret bedst muligt. Her kan man anvende algoritmer som denne til at finde ud af, hvordan vagter skal anbringes i lufthavnsområdet. Det er for eksempel sket i den store lufthavn i Los Angeles.»

»Den amerikanske kystbevogtning har også brugt lignende algoritmer til at bestemme de mest optimale ruter for skibe, der bevogter havne. Og for nyligt har man taget matematikken i brug for at finde de bedste arbejdsplaner for billetkontrollører i tog og busser, så de kan fange flest muligt, der rejser uden billet.«

»Det er alt sammen virkelige situationer med alt for meget information. Og så gælder det om at filtrere uvigtig information fra, så man får en kompakt model, der kan analyseres.«

Men her i første omgang er det altså et pokerprogram, der har fået lov til at udnytte den nye optimeringsmetode. Hvis man selv vil prøve kræfter mod det uovervindelige pokerprogram, kan man besøge Cepheus-gruppens website. En overbelastet server kan dog gøre det svært at få adgang til sitet.

Kommentarer (19)

Så ville det ende næsten uafgjort, med lige stor sandsynlighed for at den ene ender foran som at den anden gør. Det er faktisk sådan den har lært at spille poker; ved at "spille mod sig selv".

  • 0
  • 0

Troels,

Er der publiseret yderligere detaljer om projektet og CFR+ algorithmen?

Har leget en del med den 'traditionelle' CFRM metode, som jo er ganske godt beskrevet af Michael Johanson i hans afhandling fra 2007 "Robust Strategies and Counter-Strategies: Building a Champion Level Computer Poker Player"

Mvh.

  • 0
  • 0

Der er ikke så blevet publiceret så meget om CFR+ endnu, da det er en relativt ny algoritme. Det er en kun en lille ændring af den CFR fra Johanson's afhandling. Hvis du allerede kender CFR, så kan du nøjes med at læse den her artikel: http://arxiv.org/pdf/1407.5042v1.pdf
CFR+ er kort sagt at man ikke lader regret blive negativ. Det har den effekt at en strategi hurtigt kan komme i brug igen, selvom den tidligere har samlet sig en masse negativ regret. I almindelig CFR ville den opsparede negative regret først skulle betales af, inden strategien ville kunne blive spillet igen.

  • 0
  • 0

Det lyder lidt som tv-serien Numbers.
Så er den altså ikke helt så urealistisk.
"Jeg kører lige en modificeret ashton-peters-matrix til at forudse hvor forbryderen slår til næste gang."

  • 0
  • 0

Jeg kender ikke meget (noget) til spil teori og har ikke beskæftiget mig regelmæssigt med sandsynlighedsregning og statestik siden DTU, men jeg tænker alligevel på: Hvis en god spiller kan "spille op" mod denne algoritme ved man så hvordan et menneske håndtere dette? Jeg mener, der er vel ingen som bevidst kan overskue omkring 316.000.000.000.000.000 forskellige måder, kortene kan blive uddelt og satsningerne kan foretages. Så "intuitionen" som denne spiller bruger må altså alligevel give et præciest nok billede for disse personer til at det er "godt nok" til at klare sige lige så godt?

  • 0
  • 0

Princippet er lidt som sten, saks, papir.

Hvis en spiller har tendens til at vælge sten oftest, slår du ham let ved selv at vælge papir oftest.

Den perfekte strategi er derfor at vælge sten, saks, papir med 33/33/33% sandsynlighed. Så bliver du umulig at slå (men du vinder heller ikke uanset hvor dårlig modstanderen er).
Man siger at det er en nash equilibrium strategi.

Det samme gør sig gældende her, bare på et meget stort dataset, hvor det er praktisk umuligt at finde løsningen matematisk. Man bruger så denne CFR metode til at finde en tilnærmet løsning gennem tilpas mange iterationer.
Der er som sådan ikke noget nyt i det, ud over at tilgængelig regnekraft og memory efterhånden har gjort det muligt at lave en tilnærmet løsning, der er så tæt på en 'rigtig' løsning, at den i praksis ikke kan slåes...

Bagsiden er så, at du heller ikke vinder (ret meget) mod de fleste spillere. Det er kun når modstanderen laver deciderede spille fejl, at du har en reel fordel.

  • 1
  • 0

en strategi, som er så tæt på at være optimal, at computeren ikke kan forventes slået, om så man er verdens bedste pokerspiller, der har fundet den optimale modstrategi, og som spiller mod den uafbrudt igennem et helt liv

Artiklen præsenteres med budskabet om, at man har fundet "den optimale strategi", men ender alligevel med, ar strategien er "god nok" i praksis. Det er principielt noget helt andet end at spille perfekt poker.

Den perfekte "optimale strategi" er først fundet, når man kan påvise, at den statistisk ikke kan slås (over lang tid) - heller ikke af stærkere computere med andre strategier i fremtiden.

  • 0
  • 0

Så "intuitionen" som denne spiller bruger må altså alligevel give et præciest nok billede for disse personer til at det er "godt nok" til at klare sige lige så godt?


Muligvis er det lige som gode skakspillere. De analyserer ikke nødvendigvis masser af træk og muligheder systematisk. En skakspiller ser derimod 'mønstre' af brikker, som hjernen arbejder langt mere effektivt med.

Mennesker med fantastisk hukommelse bruger også en 'mønsterteknik', når de skal huske for eksempel 40 genstande på et billede, de ser i kort tid. De opstiller ikke lister i hovedet med emnerne.

  • 0
  • 0

Den perfekte "optimale strategi" er først fundet, når man kan påvise, at den statistisk ikke kan slås (over lang tid) - heller ikke af stærkere computere med andre strategier i fremtiden.

Jeg vil umiddelbart antage at de har påvist det (uden dog at have gransket ret meget materiale om det pågældende projekt).
Når først man har en fast defineret strategi, er det relativt trivielt matematisk at undersøge om der kan findes en mod-strategi, der vil kunne slå den.

  • 0
  • 0

Har ikke læst den originale artikel, men det er nok korrekt, når de i summary skriver "Texas hold’em is now essentially weakly solved" hvilket ikke er helt det samme som "Heads-up limit hold’em poker is solved"...

  • 0
  • 0

Mht. "god nok": Det de har beregnet er en strategi, der er så tæt på at være uudnyttelig, at selv hvis du spiller hele dit liv imod den, så kan du ikke være sikker på at være foran, ligegyldigt hvilken strategi du bruger.

Mht. "weakly solved": Det betyder at strategien er god, så længe du følger den, men at der muligvis er svagheder i de dele af spillet, som strategien aldrig selv ville rode sig ud i.

  • 1
  • 0

Bluf er et ord som mennesker bruger. Computeren kender kun til sandsynligheden for forskellige handlinger. Ja, computeren vil nogen gange bette med dårlige kort, men kun fordi den har lært at det kan betale sig. Det er meget interessant at se den slags opstå ud af rene optimeringsproblemer.

  • 2
  • 0

Jeg er egentlig lidt i tvivl om hvor imponeret jeg skal være.

Heads up poker har betydeligt færre variable end med flere spillere, og limit poker har betydeligt færre variable end no-limit poker.

Reelt set har du et beslutningstræ med kun 3 mulige outputs til hver situation, fold, call, raise. Du kan spille dine egne kort næsten helt optimalt uden at tænke på modstanderen bare på odds mod en gennemsnitlig hånd. Du kan så imødegå en aggresivt eller passivt spillende modstander ved at holde en dynamisk værdi for modstanderens gennemsnits håndstyrke kørende.

På rigtig mange måder kan det sammenlignes med blackjack, hvor det også er meget enkelt at fastsætte en næsten optimal strategi.

Så kan man grine lidt af den her vending:

I samme ombæring har de canadiske matematikere bekræftet, at kortgiveren har en lille fordel i spillet.

Imponerende at det krævede en matematiker at finde ud af det :)

  • 0
  • 0

Heads up poker har betydeligt færre variable end med flere spillere, og limit poker har betydeligt færre variable end no-limit poker.

Reelt set har du et beslutningstræ med kun 3 mulige outputs til hver situation, fold, call, raise.

Selvom der kun er tre muligheder ved hvert træk, så er tilstandsrummet stadig ufatteligt stort. Størstedelen kommer fra de mange muligheder kortene kan komme på. Her er et hurtigt overslag på størrelsen:

(52 choose 2) måder at give kort til spiller 1
(50 choose 2) måder at give kort til spiller 2, blandt de resterende kort
7 måder at komme videre fra 1. betting runde (uden at nogen folder)
(48 choose 3) måder som floppet kan komme
9 måder at komme videre fra 2. betting runde (uden at nogen folder)
(45 choose 1) måder som floppet kan komme
9 måder at komme videre fra 3. betting runde (uden at nogen folder)
(44 choose 1) måder som floppet kan komme
15 måder som sidste betting runde kan slutte på.

Ganger man overstående sammen, så får man et konservativt overslag på antallet af måder en hånd kan spilles på. overslaget giver lidt over 470,000,000,000,000,000 måder at spille på.

Du kan spille dine egne kort næsten helt optimalt uden at tænke på modstanderen bare på odds mod en gennemsnitlig hånd. Du kan så imødegå en aggresivt eller passivt spillende modstander ved at holde en dynamisk værdi for modstanderens gennemsnits håndstyrke kørende.

Det er alt for upræcist at regne modstanderens hånd som bare at være gennemsnitlig. Det har man prøvet i mange afskygninger for mange år siden, og det virkede ikke særlig godt.

På rigtig mange måder kan det sammenlignes med blackjack, hvor det også er meget enkelt at fastsætte en næsten optimal strategi.

Poker har ikke meget til fælles med Blackjack fra et spilteoretisk synspunkt. Blackjack er et meget simplere spil, hvor dealeren ikke foretager sig noget før end spilleren er færdig med alle sine træk, hvorefter dealeren kan se alle de givne kort og følger en fast strategi. I praksis gør det Blackjack til et 1-spiller spil, og ikke et 2-spiller spil som poker.

Imponerende at det krævede en matematiker at finde ud af det :)

Her er forskellen på om at man tror noget gælder, eller om man kan bevise at det gælder.

  • 1
  • 0

CFR+ er kort sagt at man ikke lader regret blive negativ. Det har den effekt at en strategi hurtigt kan komme i brug igen, selvom den tidligere har samlet sig en masse negativ regret. I almindelig CFR ville den opsparede negative regret først skulle betales af, inden strategien ville kunne blive spillet igen.

Har genoplivet mit CFR projekt, og implementeret min forståelse af CFR+ baseret på dette.

Har samtidig droppet at holde styr på average strategi'en, så der bliver dobbelt memory til rådighed for regret tabellerne (min server har "kun" 72 GB RAM, så det skal udnyttes bedst muligt).
Efter et par ugers CPU tid, og ca. 3 mia. simulerede hænder, ser det meget lovende ud. Lader til at konvergere lidt hurtigere end min tidligere implementation, på trods af det 2x størrer dataset jeg nu bruger.

Bare lige i det (utænkelige) tilfælde, at det har nogens interesse... :-)

  • 0
  • 0