DeepStack pobeđuje u pokeru

Krajem prošle godine, poker je dodat na spisak igara u kojima računar može da pobedi najbolje ljudske igrače.

Kartaške igre su sastavni deo elektronske zabave. Od kockarskih aparata i programa za poker, preko raznih verzija pasijansa koji je bio obavezni deo osnovne ponude igara na raznim verzijama Windowsa, sve do aktuelnog buma popularnosti online kartaških igara, bilo u realan novac, bilo radi čiste zabave i adrenalina. Ipak, do nedavno je važilo da ili pravila igre moraju biti takva da je računar u blagoj prednosti ili je kompjuter bio samo sredstvo za povezivanje ljudskih igrača koji su onda mogli da odmere svoju umešnost. Tokom novembra i decembra 2016. godine odigrano je nekoliko mečeva između nekolicine profesionalnih igrača pokera i veštačke inteligencije (AI) nazvane DeepStack, koja je razvijena u Kanadi na Univerzitetu u Alberti. Tom prilikom je bez sumnje utvrđeno da računarima više nisu potrebna specifična pravila da bi pobedili ljudske protivnike, i to one koji spadaju među najbolje igrače na svetu. Za mnoge stručnjake koji se bave razvojem veštačke inteligencije, taj događaj je jednako značajan kao što je pobeda Deep Bluea nad Kasparovom u šahu.

Hold’em!

Tokom poslednjih dvadesetak godina, zahvaljujući „nemilosrdnoj propagandi” u filmovima, na televiziji i, naravno, internetu, poker je postao opšteprisutan u modernoj kulturi i njegova popularnost vinula se do istorijski rekordnih visina. To je pak dovelo do sve većeg broja turnira, sa sve više učesnika i sve većim nagradama, što je samo nastavilo ciklus rasta popularnosti. Knjige o taktici, kompjuterske igre, online servisi i sve veći broj TV emisija sa prenosima napetih mečeva samo su nastavili da jačaju ovu subkulturu. Iako se poker smatra igrom na sreću, njegova najpopularnija varijanta, Texas hold’em, vremenom se dokazala i kao igra veštine, jer određeni igrači imaju osetno više uspeha od proseka, i to bez obzira na karte koje im sreća dodeljuje. Ako se ne radi o čistoj sreći, da li je moguće naučiti računar da savlada tu veštinu?

Većina ljudi je ubeđena da su za dobro igranje potrebni poznavanje psihologije, hrabrost i instinkt. Profesionalni igrači će vam pak reći da je za uspešno igranje na visokom nivou neophodno da dobro „čitate” protivnike. To se sastoji iz nekoliko komponenata. Postoje brojni, sitni detalji ljudskog ponašanja, kao što su mimika lica, držanje tela, pa čak i nesvesni detalji kao širenje i skupljanje zenica, promene u disanju ili pulsiranje vratnih arterija. Kako bi eliminisali ove komponente koje protivnicima pružaju prednost, mnogi igrači nose naočari, kapuljače i šalove, čine sve kako bi maskirali što veći deo glave koja otkriva najviše. Ipak, postoji jedan deo igre koji ne može da se sakrije – način na koji tokom igre ulažete novac, a on se prati matematikom i teorijom igara. Upravo taj deo je ono na šta se usredsređuju najbolji igrači, pa je to postao predmet interesovanja rada tima koji je razvijao DeepStack.

U Hold’emu je bitnija veština od sreće jer se tokom svake ruke nekoliko puta ulaže novac na osnovu karata koje držite (svaki igrač ima po dve karte koje samo on vidi), kao i na osnovu zajedničkih karata koje su vidljive svim igračima na stolu. Logika pobeđivanja je jednostavna u teoriji, ali u praksi razlikuje šampiona od rekreativnog igrača – Kako da na osnovu protivničkih uloga prilagodite svoj na takav način da protivnika ili naterate da odustane kada ima jače karte od vas ili da ga privolite da vas prati, iako ima slabije karte? Najbolji igrači na svetu odlično barataju verovatnoćom i statistikom. Standardni francuski špil ima 52 karte i svaka specifična kombinacija ima određenu verovatnoću. Sa druge strane, tu je statistika praćenja uloga tokom svake ruke koju neki igrač igra tokom partije. Svaki dobar igrač pokušava da prati te podatke i na osnovu njih pronađe šablone u ponašanju protivnika kako bi ih iskoristio u kritičnom trenutku.

Varijante

Sam Hold’em ima nekoliko varijanti, ali najbitnija stavka je da li postoji limit u veličini podizanja uloga ili ne. Sem toga, bitno je koliko igrača učestvuje u partiji. Kako se svaka partija uglavnom svede na obračun dva igrača, takozvani heads-up, mnogi stručnjaci se usredsređuju upravo na taj dramatični deo igre, a postoje i posebni turniri gde se igraju isključivo heads-up partije. Za računar je, zapravo, takva situacija najlakša, jer mora da prati poteze samo jednog igrača. Sa druge strane, limit veličine uloga je toliko bitna stavka jer ograničenje uloga daje jasnije vrednosti sa kojima mogu da barataju AI rutine za procenjivanje rizika. Tačnije, kada se uzmu u obzir sve moguće kombinacije rasporeda karata i postavljenih uloga u limit hold’emu, dobija se 10¹⁴ ili 100,000 triliona mogućih varijanti odluka, iz kojih je samo potrebno da se izabere ona koja odgovara situaciji na stolu. Iako to zvuči kao prilično veliki problem, tim sa Univerziteta u Alberti je još pre dve godine razvio AI sistem zvan Cepheus koji je bio skoro nepobediv kada igra heads-up limit Texas hold’em. Zašto im je trebalo toliko vremena da prenesu svoja znanja i rešenja na no-limit varijantu? Odsustvo limita prilikom postavljanja ili podizanja uloga naduvava broj kombinacija karata i uloga na astronomske vrednosti. Tako u no-limit hold’emu broj potencijalnih odluka iznosi neverovatnih 10¹⁶⁰, što je veća vrednost od broja atoma u celom svemiru!

Deset matematičara radilo je preko godinu dana na prilagođavanju sistema razvijenog za Cepheus za otvorenu, no-limit varijantu. Oba sistema su utemeljena na Nešovom ekvilibrijumu, jednom od osnovnih koncepata teorije igara, nazvanom po matematičaru Džonu Forbsu Nešu. Njegova suština je da u nekooperativnoj igri svaki igrač pretpostavlja strategije svojih protivnika i pridržava se sopstvene strategije, pri čemu nastaje ravnotežno stanje. Cepheus i DeepStack na osnovu ove teorije pokušavaju da igraju savršenu defanzivnu igru dovoljno dugo, dok protivnik ne napravi grešku. Problem kod ovakve strategije je tipičan za kompleksnu igru kao što je poker. Treba ostati u igri dovoljno dugo kako bi prikupili podatke o protivniku na osnovu kojih bi mogla da se postavi jaka defanzivna strategija.

Pošto AI sistem vrši najveća prilagođavanja strategije kada izgubi ruku, tim je došao na ideju da pusti dve kopije Cepheusa da igraju veliki broj partija jedan protiv drugog. Rešenje je bilo u pažljivom smanjivanju reagovanja sistema na „pogrešne” odluke. Za tačno računanje parametara po kojima Cepheus „donosi odluke” bilo je potrebno da klaster od 200 servera radi tri meseca. Tako je dobijena finalna baza strategija za odlučivanje koja pokriva sve mogućnosti i „teška” je 11 terabajta. Kada je bilo potrebno da se obavi prelaz na no-limit verziju, nije bilo moguće pravljenje baze svih mogućih situacija jer je problem bio kompleksniji za 146 redova veličine. To je značilo pravljenje potpuno novog sistema koji računa verovatnoće i rizike u realnom vremenu.

DeepStack

Prvi korak u postavljanju novog sistema bio je definisanje akcija koje AI može da obavi svaki put kada je na potezu: da baci karte, da prati ulog, da ga podigne, da podigne podignuti ulog ili da uloži sve čipove koje ima. Zatim su potkresane grane na kompleksnom drvetu donošenja odluka. Dok je sistem pokušavao da pokrije sve moguće ishode u svakom trenutku, broj grananja bi eksponencijalno rastao do vrednosti za koje nije bilo moguće obaviti proračun u realnom vremenu. Ograničavanjem DeepStacka da predviđa samo četiri koraka unapred dobijena je neophodna brzina, ali da bi stepen uspešnosti pri odabiru bio što veći, bilo je potrebno pravljenje aproksimacija, i to zahvaljujući dubokim neuronskim mrežama, softverskim rutinama koje oponašaju sinapse u mozgovima živih bića. Mreža sa samo hiljadu virtuelnih neurona bila je u stanju da brzo nauči da ispravno proceni situaciju na osnovu podataka kojim raspolaže. Kada se „pretpostavka” dobijena iz neuronske mreže primeni na model donošenja odluka u partiji no-limit Hold’ema, kompleksnost odlučivanja pada sa 10¹⁶⁰ na samo 10⁷, to jest 10 miliona. Takav proračun može da se obavi za pet sekundi na modernom desktop PC-ju sa grafičkom karticom GeForce GTX 1080.

Sledeći korak bilo je istovremeno testiranje sistema i njegovo obučavanje na najvišem stepenu igre. Tim iz Alberte je angažovao više od trideset profesionalnih igrača pokera, svakog sa zadatkom da online odigra 3000 partija no-limit Texas hold’ema protiv DeepStacka. Da bi igrači bili motivisani, dodata je i specijalna novčana nagrada za troje najuspešnijih. Ovaj specifičan turnir održan je između 7. novembra i 12. decembra prošle godine, i samo jedanaest igrača uspelo je da odigra traženih 3000 partija. Tokom ovog merenja snaga, uspešnost je utvrđivana na osnovu vrednosti mbb/g (milli-big-blind/game), odnosno hiljaditom delu većeg obaveznog uloga po odigranoj ruci. Čisto radi orijentacije, da bi profesionalni igrač bio smatran kompetentnim, mora da postiže preko 50 mbb/g. DeepStack je tokom ovih mečeva imao prosek od 394 mbb/g, pozitivan skor protiv svih jedanaest, a apsolutnu pobedu protiv osmoro protivnika.

Jedan od igrača koji je učestvovao u ovom online turniru protiv DeepStacka, irski profesionalac i inženjer elektrotehnike Dara O’Kirni bio je impresioniran i izjavio da ne bi prepoznao da igra protiv bota da mu to nije rečeno.

• • •

U drugim igrama u kojima su računari uspeli da pobede ljude, kao što su šah, go ili bekgamon, sve informacije su poznate obojici igrača. Sa druge strane, u partiji pokera neophodno je donošenje odluka na osnovu analiza nepotpunih informacija. Ovo znači da algoritmi razvijeni za DeepStack mogu da imaju mnogo bitniju praktičnu primenu u realnim ljudskim delatnostima, gde se ne raspolaže dovoljnom količinom informacija, kao što su medicinska dijagnostika, ekonomija ili odbrambeni sistemi. Upravo to je sledeći korak za DeepStack – ulaženje u koštac sa kompleksnijim izazovima, a ako nastavi da bude uspešan, kao što se očekuje, samo je pitanje vremena kada će njegovi algoritmi postati deo sistema koji olakšavaju našu svakodnevicu ili čak spašavaju živote.

Dragan KOSOVAC