Megalkották a tökéletes pókerjátékost

LAS VEGAS - JULY 30: Poker player Greg "Fossilman" Raymer, the 2004 World Series of Poker champion, wears his holographic glasses as he competes on the third day of the first round of the WSOP no-limit Texas Hold 'em main event at the Rio Hotel & Casino July 30, 2006 in Las Vegas, Nevada. More than 8,600 players have registered to play in the main event. The final nine players will compete for the top prize of more than USD 11.7 million on the final table which begins August 10.

Kanadai és finn kutatók lényegében verhetetlen pókerjátékost konstruáltak. Hogyan játszanak a matematikusok, és mit nyer, aki gyengén nyer? Tudathasadásos bolyongás a játékok erdejében, élethosszig tartó pókerjátszma és egy nyitott fekete doboz homályos tartalma.

A számítógépprogramok már eddig is komoly eredményeket mutattak fel, amikor emberi ellenfelek legyőzéséről volt szó különféle játékokban. Talán az eddigi legfájdalmasabb ilyen esemény az akkori világbajnok, Garri Kaszparov veresége volt 1997-ben, amikor az IBM Deep Blue nevű szuperszámítógépe 3,5-2,5 arányban legyőzte egy hatjátszmás mérkőzésen. Kisebb visszhangja volt annak a tíz évvel későbbi bejelentésnek, mely szerint egy Chinook nevű program megoldotta a dámajátékot.

Megnyerni vagy megoldani?

A játékelmélet szempontjából nagy különbség van a Kaszparovot megverő számítógép és a dámában győzedelmeskedő algoritmus között. Előbbi egy okosan megírt stratégiai program, amely hatalmas számítási kapacitással a háta mögött rengeteg lépést lát előre. A dámanyertes program azonban több ennél. Ez a játék matematikai értelemben vett megoldását használja.

Képzeljünk el egy turistát, aki eltévedt az erdőben, és szeretne valahogy kikeveredni onnan, mielőtt beköszönt az éjszaka, és jönnek a farkasok. Szegény vándort azonban még a genetika is terheli, ugyanis tudata csak a bal agyféltekéjét, ezzel jobb lábát irányítja – a másik, gonosz jobb félteke pedig mindent megtesz, hogy a pusztulásba vigye tulajdonosát.

Kaszparov a Deep Blue ellen 1997-ben. Nem örül Forrás: AFP/Stan Honda

A Deep Blue megoldásának egy Bear Grylls-túlélőkönyv felel meg: turistánk okos és előrelátó stratégiákat tudhat meg belőle, melyek segítségével egyre közelebb juthat a civilizációhoz, ügyesen reagálva a terep változásaira és a jobb agyfélteke fondorlataira. A dámanyertes program megfelelője egy GPS, mely minden bal lépés után ellentmondást nem tűrően megmutatja a következő jobb lépést, és biztosan kalauzol ki az erdőből.

Hogyan oldhatunk meg egy játékot?

Egy két ellenfél között zajló játéknak a matematikusok világában különböző szintű megoldásai léteznek.

• Ultragyenge megoldásról akkor beszélünk, ha bebizonyítható, hogy ha a felek tökéletesen játszanak - vagyis visszatekintve egyik lépésük sem lehetett volna jobb -, a kezdő játékos eredménye biztosan vesztés/döntetlen/nyerés. Adott játékos esetében ezt nevezzük a játék értékének.

• Gyenge megoldás egy olyan algoritmus, mellyel a játék kezdőhelyzetéből indulva (bármely játékost is tekintsük) elérhető a játék értéke.

• Erős megoldás egy algoritmus, mely a játék minden szabályos helyzetére képes megmondani, hogy onnan mi a játék értéke adott játékos számára.

Látható, hogy az erősből következik a gyenge, a gyengéből pedig az ultragyenge megoldás létezése. A matematikusok számára gyakran az ultragyenge megoldás a legizgalmasabb, ugyanis ez sokat elárul a játék alapvető szerkezetéről. A gyenge megoldás esetében meg kell követelni, hogy az algoritmus értelmes időben lefusson - sok esetben ismerünk valamilyen faék egyszerűségű módszert, melynek véghezviteléhez azonban a legjobb számítógépekkel is évezredekre lenne szükség. Végül, az erős megoldás rendszerint “túl erős”, vagyis a játék összes lehetséges állapotának algoritmikus átfésülésén alapul, ami sok esetben nem segít megérteni a játék mélyebb lényegét - mintha egy mindentudó orákulum lépésenként megsúgná a megoldást. Ha egy játék megoldásáról beszélnek, általában a gyenge megoldást értik alatta.

Ezek a definíciók az olyan teljes információs játékokra vonatkoznak, mint a sakk vagy a dáma, ahol a játékosok minden pillanatban tisztában vannak a játék pontos állapotával. A nem teljes információs játékokra, mint például a póker, csak némi módosítással alkalmazhatók, lényegében azonban hasonló a cél.

Hogyan képzeljük el ezt a játékelméleti „erdőt”?

Ha elkezdünk nézegetni egy sakktáblát, megeshet, hogy nem látjuk a lótól az erdőt, és beismerem, a hasonlat némi magyarázatra szorul. Képzeljük el, hogy elkezdünk egy sakkjátszmát – ott áll egymással szemben a fehér és a fekete sereg, és a fehér következik. Ez a játék egy állapota. A fehér most az egyik parasztjával lép egyet, legyen mondjuk E2->E4, és a fekete következik. Amit kapunk, az a játék egy következő állapota. A sakk játékelméleti “erdejében” minden ilyen állapotnak egy pont felel meg, és azok közt a pontok közt vezet út, amelyek egymásból egy, a játék szabályainak megfelelő lépéssel elérhetők.

A játék innentől kezdve leírható úgy, mint lépkedés az állapotok között, a cél pedig az, hogy elérjünk egy olyan állapotot, amely a játék végét jelenti. A sakk „megoldása” egy olyan algoritmus lenne, mely fehérként (vagy feketeként) egy képzeletbeli, tökéletesen játszó játékos ellen biztosan nyer vagy legalábbis döntetlent hoz ki. A „tökéletesen játszó” ellenfél (vagyis a rakoncátlan jobb agyfélteke) itt egy matematikai konstrukció, amiről a játék végén mindig bebizonyosodik, hogy jobban nem játszhatott volna.

A tic-tac-toe játékban az O ügyes játékkal mindig ki tudja harcolni a döntetlent, akárhogy is kezd az X. Nagyobb méretért kattintson a képre! Forrás: Wikimedia Commons

A sakk annyira bonyolult, hogy jelenleg még nem ismert ilyen megoldása, a go esetében még távolabb vannak tőle a kutatók. Egyszerű, házilag is megoldható játék a tic-tac-toe, a legtöbb állapottal rendelkező megoldott játék pedig jelenleg a jól ismert dáma.

A póker sötét erdejében

A póker és legtöbb kártyajáték lényegében tér el a sakktól, a dámától és a hozzájuk hasonló játékoktól. Itt ugyanis a játékosok nem láthatják át teljesen a játék aktuális állását, hiszen az ellenfelek lapjai a legutolsó pillanatig rejtve maradnak. Erdős hasonlatunkat némileg erőltetve itt úgy vihetjük tovább, ha elképzeljük, hogy hősünk agyféltekéi még csak nem is ugyanúgy látják az erdőt. Egyikük előtt rejtve maradnak bizonyos útelágazások, másikuk előtt pedig mások (kezdetben más lapokat húztak a játékosok, és egymáséit sosem láthatják). Megoldásként ilyen esetben nem várhatunk egy olyan magabiztos GPS-útvonaltervezőt, mint a dámajátéknál, hiszen a szerencse eleve durván torzíthatja az agyféltekék erőviszonyait. Egy olyan szerkezetre azonban áhítozhatunk, mely az esetek túlnyomó többségében segít kijutni az erdőből, akárhogy is kapálódzik ellenféltekénk.

Rövid pókertan

A szóban forgó “megoldott” játék a póker egy némiképp egyszerűsített, azonban a valóságban is játszott változata. A játék a Texas hold’em nevű, igen népszerű pókervariánson alapul, melyben a játékosok egy pakli (52 lapos) franciakártyából két-két lapot kapnak a játék kezdetén. Az asztalra a későbbiekben még öt további, mindenki számára látható kártyalap kerül majd. A játékot az nyeri, aki az utolsó licit lezárása után még játékban van, és meghatározott szabályok szerint a legnagyobb értékű lapötöst tudja összerakni saját két lapjából és a nyilvános ötből.

Az első licitkör során a játékosok csak saját két lapjukat ismerik, és ezek alapján teszik meg tétjeiket, ezt követően az osztó három, majd egy és még egy lapot húz a pakliból, melyeket az összes játékos láthat. A húzásokat rendre újabb licitkörök követik. Miután valaki emelte a tétet, a következő játékosnak legalább tartania kell - ha erre nem hajlandó, ki kell szállnia a játékból.

A megoldott, egyszerűbb játékban két játékos vesz részt (heads-up), továbbá a tétek nagysága és az emelések száma korlátozott (limit). Így a játék neve heads-up limit Texas hold’em poker, vagy rövidítve HULHE.

Lényegében tökéletes játékos

A matematikusok imádják az egyszerűsítéseket, melyekben sokszor a bonyolultabb rendszerek törvényszerűségei villannak fel, ötleteket adva a nagyobb problémák megoldásaihoz. Ennek a rajongásnak köszönhetünk olyan játékokat, mint a minisakk vagy az 5 x 5-ös go (a “rendes” játékot 19 x 19-es táblán játsszák). A pókernek is kitalálták különféle egyszerű, a matematikusok igényeihez szabott változatait, ilyen például a Kuhn-póker, amelyben mindössze három kártya van a pakliban, és egyetlen licitkört játszanak. Ezúttal azonban egy nagyon is valós játék megoldásáig jutottak el – a Texas hold’em póker HULHE nevű változatát vették górcső alá (lásd keretes írásunkat).

Greg "Fossilman" Raymer pókervilágbajnok arcán feltehetően sosem látszik az "utólagos megbánás" Forrás: Getty Images/AFP/Ethan Miller

Michael Bowling és társai egy viszonylag új algoritmussal estek neki a feladatnak, mely a CFR+ nevet viseli (counterfactual regret minimization – kb. "utólagos megbánás minimalizálása", a + pedig az eredeti algoritmus fejlesztett változatára utal). Ez az algoritmus azonban nem maga a nyerő stratégia volt, hanem egy tanulási eljárás, amely egy sor gépi játék lejátszása során a teljesen véletlenszerű működéstől indulva finomította a viselkedését. Végül nem sokkal több, mint 1500 edzőmérkőzés után lényegében legyőzhetetlenné vált, miközben teljes természetességgel belejött a blöffölésbe is. A tanulás lényegét az adta, hogy az algoritmus minden játék végén kiértékelte a döntéseit, és ha valami ballépésnek bizonyult, valamekkora “megbánásértéket” rendelt hozzá. A stratégia (ellenfél általi) “kihasználhatóságát” folyamatosan mérték, míg egy olyan kicsiny érték alá szorult, hogy statisztikai értelemben verhetetlennek nyilváníthatták.

Az algoritmus legnagyobb kihívása az volt, hogy átlássa a játék lehetséges állapotait, melyek száma 10¹⁷ nagyságrendű. Ez ugyan nagyságrendekkel kevesebb a dámajátékban kapott állapotszámhoz képest, a véletlenszerűség azonban rengeteg többletszámítást igényel, mivel az állapotok bizonytalanságot is tartalmaznak. (Az erdőben: emberünk jobb szeme csak előre lát viszonylag tiszta utat, azonban számolnia kell azzal, hogy bizonyos valószínűséggel indulhat jobbra és balra is ösvény, és esetleg megéri vállalni a kockázatot, és belépni az ismeretlen homályba.)

A számítások alapjául szolgáló adattömeg nagyjából 262 terabájtot tett ki, és az adatokat gyorsan kellett elérni, így a kutatók ügyes tömörítési eljárással 11 terabájtra csökkentették az adatok mennyiségét némi processzorterhelés árán. A számítás még így is több mint 2 hónapig tartott 200 számítógépen, melyek mindegyike 24 darab 2,1 GHz-es processzormaggal és 32 GB memóriával aprította a biteket.

Nyitott fekete doboz

Fontos megérteni, hogy amit végül kaptak, az nem egy egyszerű túlélőkönyv pókerjátékosok számára, hanem egy valódi nyerő stratégia, egy orákulum, amely a játék minden helyzetében megmondja, mit érdemes tennün. (Azért nem számít mégsem erős megoldásnak, mert bizonyítottan csak akkor működik, ha a játékot a legelején kezdjük – ha két ember játszik a maga tökéletlen módján, és a gép pár licit után beszáll az egyik helyére, semmi sem garantált.)

Cepheus, a tökéletes pókerjátékos minden titkát feltárja az Albertai Egyetem oldalán. A képre kattintva meg is mérkőzhetünk vele, de a legjobb, ha tanulunk tőle Forrás: University of Alberta

A döntések megismerhetők, az orákulum semmit sem titkol előttünk a működéséből (itt ki is próbálható), ugyanakkor, amit a kutatók kaptak, az nem stratégia abban az értelemben, hogy könnyen megérthető lenne. A kifejlesztői sem értik a szó hétköznapi értelmében, legfeljebb statisztikailag képesek mérni a hatékonyságát. (Mindez rámutat a számítógéppel segített matematika egyik érdekes kérdésére, mely szerint lehetnek problémáknak olyan megoldásai, melyek ott állnak előttünk leírva, matematikailag tökéletesen helytállóak, mégsem feltétlenül látjuk át őket.)

A stratégia nem tökéletesen verhetetlen, de lényegében az. Ez azt jelenti, hogy ha valaki találna is egy tökéletes ellenstratégiát, és azt hiba nélkül, folyamatosan, hetven éven át alkalmazná a szuperstratégia ellen (ez több mint 60 millió játszmát jelent), még akkor sem lehetne statisztikai értelemben meggyőződve arról, hogy valóban nyertes a stratégiája (elvileg nem tudták kizárni ezt a lehetőséget, és az emberélet hossza jó mércének tűnik). A játék lényegéből következik persze, hogy egy játékosnak akár sok-sok játszmán keresztül is hatalmas szerencséje lehet, és ennek köszönhetően átlagos játékkal is sorozatban nyer, azonban hosszú távon ezeket a hatásokat a véletlen erői kiegyenlítik.

Hol segít a készséges orákulum?

Ha a stratégia közvetlenül nem is fordítható le emberi gondolatokra, rengeteg értékes információ nyerhető ki belőle, melyeket érdekes lehet összevetni hús-vér profi pókerjátékosok jellemző játékstílusával – így lehet tőle tanulni. A stratégiát megszülő algoritmus pedig továbbfejleszthető, és alkalmazható más, nem teljes információs játékok megoldására. Márpedig a való életben ezek az igazán izgalmas problémák.

Ha ez így megy tovább, bottal üthetjük az online póker nyomát Forrás: Photononstop/Nathan Alliard

A kutatók gyorsan lehűtik azok lelkesedését, akik a tőzsde felé kacsingatnának, mivel ott – Michael Bowling, az első szerző szerint – „túl sok az ismeretlen tényező”, viszont az orvosi döntéshozatalban komoly lehetőségeket látnak.

Ha pedig valaki az online póker világában próbálná kiaknázni az orákulum lehetőségeit, már most sincs sok esélye, hiszen a HULHE népszerűsége pusztán az emberi játékosok tudásának fejlődése révén jelentősen csökkent, a stratégia pedig nem alkalmas több ellenfél elleni, illetve limit nélküli játékra. Az azonban valószínű, hogy újra fellángol a vita a pókerrobotok körül.