Univerza v Ljubljani
Fakulteta za raˇ cunalniˇ stvo in informatiko
Jan Urankar
Strojno uˇ cenje v pokru
DIPLOMSKO DELO
UNIVERZITETNI ˇSTUDIJSKI PROGRAM PRVE STOPNJE
RA ˇCUNALNIˇSTVO IN INFORMATIKA
Mentor : prof. dr. Janez Demˇsar
Ljubljana, 2021
Copyright. Rezultati diplomske naloge so intelektualna lastnina avtorja in Fakultete za raˇcunalniˇstvo in informatiko Univerze v Ljubljani. Za objavo in koriˇsˇcenje rezultatov diplomske naloge je potrebno pisno privoljenje avtorja, Fakultete za raˇcunalniˇstvo in informatiko ter mentorja.
Besedilo je oblikovano z urejevalnikom besedil LATEX.
Fakulteta za raˇcunalniˇstvo in informatiko izdaja naslednjo nalogo:
Tematika naloge:
Counterfactual Regret Minimization je algoritem, ki spada med algoritme spodbujevanega uˇcenja in je primeren za uˇcenje igranja iger. Algoritem deluje tako, da velikokrat odigra igro proti samemu sebi in postopno izboljˇsuje strategijo, pri ˇcemer ga vodi ”obˇzalovanje”(regret), ki predstavlja razliko rezultatom posamezne akcije in uteˇzenim popreˇcjem rezultatov vseh moˇznih akcij v tej poziciji.
V diplomski nalogi sprogramirajte algoritem in ga preskusite na poeno- stavljeni razliˇcici igre poker.
Zahvaljujem se prof. dr. Janezu Demˇsarju za mentorstvo in strokovno pod- poro pri pripravi diplomskega dela. Prav tako bi se mu rad zahvalil, ker mi je omogoˇcil dostop do ustrezne strojne opreme na fakulteti, brez katere simu- lacija v tem diplomskem delu ne bi bila mogoˇca.
Prav tako bi se rad zahvalil svojim starˇsem, ki so me v ˇcasu ˇstudija pod- pirali in spodbujali.
Kazalo
Povzetek Abstract
1 Uvod 1
2 No Limit Texas Holde’m 3
2.1 Pravila in potek igre . . . 6
2.2 Tipi igralcev . . . 10
3 Uporabljeni algoritmi 11 3.1 Strojno uˇcenje . . . 11
3.2 Counterfactual regret minimization . . . 12
3.3 Delovanje algoritma CFR pri pokru . . . 15
3.4 Uporaba CFR za igranje pokra . . . 21
4 Izgradnja agenta 25 4.1 Osnovno delovanje algoritma za uˇcenje agenta . . . 25
4.2 Problem izbire parametrov pri uˇcenju . . . 26
4.3 Uporabljene optimizacije . . . 27
5 Izvedba poskusov 31 5.1 Pridobitev podatkov iger, kjer je igral ˇclovek . . . 32
5.2 Generiranje podatkov igre naˇsega agenta . . . 32
5.3 Analiza igre naˇsega agenta in ˇcloveka . . . 32
5.4 Primerjava igre ˇcloveka in agenta . . . 34
6 Zakljuˇcek 39
6.1 Moˇzni alternativni pristopi . . . 40
Literatura 43
Seznam uporabljenih kratic
CFR Counterfactual regret minimi- zation
Protidejstvena minimizacija izgube
Povzetek
Naslov: Strojno uˇcenje v pokru Avtor: Jan Urankar
Cilj diplomskega dela je raziskati razlike med igro agentov, nauˇcenih s pomoˇcjo umetne inteligence, in ˇcloveka v pokru.
Prva koraka sta bila uˇcenje razliˇcice pokra, imenovane No Limit Texas Holde’m, in spoznavanje pravil igre. Naslednji korak je bil izgradnja poker agenta, ki bi ga lahko s pomoˇcjo strojnega uˇcenja nauˇcili igranja igre. Odloˇcili smo se za algoritem, ki spada v druˇzino algoritmov spodbujevanega uˇcenja, imenovan counterfactual regret minimization.
Agenta smo nauˇcili igre poker. Zatem smo inicializirali dva agenta, ki sta igrala drug proti drugemu, pri ˇcemer smo beleˇzili njune poteze. Ko smo generirali dovolj iger agentov, smo poiskali podatke o igrah ljudi. V naslednjem koraku smo pripravili skripto za analizo med podatki igre agentov in podatki igre ljudi. V tej skripti smo analizirali veˇc vidikov, ki so bili osnova za sklep o slogu igre doloˇcenega igralca ali agenta.
Na podlagi poskusa smo priˇsli do sklepa, da so agenti, nauˇceni s pomoˇcjo naˇsega algoritma, veliko dejavnejˇsi in agresivnejˇsi od ljudi. Dejavna igra v tem kontekstu pomeni, da igralec igra veliko iger, agresivna igra pa, da veliko stavi in da tudi pogosto zavaja ali ’blefira’. Te ugotovitve se ujemajo z ugo- tovitvami drugih ekip, ki so s pomoˇcjo umetne inteligence uˇcili inteligentne agente na podroˇcju pokra z algoritmom counterfactual regret minimization.
Kljuˇcne besede: strojno uˇcenje, big data, poker, counterfactual regret mi-
nimization.
Abstract
Title: Machine learning in poker Author: Jan Urankar
The goal of this diploma thesis is finding the differences betwen human and artifical agent in poker.
The first step was preforming research on the specific version of poker, named No Limit Texas Holde’m and learning the rules of the game. The next step was a creation of an intelligent poker agent, which is trained to play the specified version of poker, using machine learning. We decided to use an algorithm, which belongs in the family of machine learning algorithms, known as reinforcement learning. The algorithm is called counterfactual regret minimization. After the selection of the algorithm we trained the intelligent agent and created two instances of the same agent. Those two agents than played poker against each other and we were monitoring and noting every move they made. When we generated enough games between agents, we created a script for analysing the data. In the script we analysed several aspects of the game, which were the basis for our conclusion on the game style of certain virtual agent versus human player.
Our conclusion on the basis of the experiment is, that virtual agents, trained with our algorithm, play much more actively and more aggressively than humans. Active game in this context means, that a player plays many games. Aggressive game means that the player bets a lot and often bluffs.
These findings are in line with the other researchers findings, which used counter- factual regret minimization for creating an intelligent agent.
Keywords: machine learning, big data, poker, counterfactual regret mini- mization.
Poglavje 1 Uvod
Strojno uˇcenje se je v igrah izkazalo kot uspeˇsno. Prva odmevna zmaga raˇcunalnikov proti ˇcloveku se je zgodila ˇze leta 1997 v klasiˇcni namizni igri ˇsah, ko je podjetje IBM izdelalo raˇcunalnik z imenom Deep Blue, ki je pre- magal takratnega svetovnega prvaka Garija Kasparova. Od takrat naprej so ljudje ustvarili programe, ki so prevladali tudi v drugih igrah, kot sta na pri- mer zmaga raˇcunalnika proti svetovnemu prvaku v namizni igri Go leta 2016, in zmaga raˇcunalnika proti svetovnemu prvaku priljubljene raˇcunalniˇske igre Dota 2 leta 2017.
Ena izmed iger, ki je bila prav tako velik izziv za programerje, je namizna igra poker. Posebnost pokra je, da igralcem niso razkrite vse informacije, kot so v zgoraj naˇstetih igrah, zato tradicionalni algoritmi tu ne pridejo v poˇstev.
Pri drugih igrah vedno vemo, kako so nasprotnikove figure postavljene, kako moˇcan je njegov bojevnik v raˇcunalniˇski igri itd. Teh informacij pri pokru ni, saj je kljuˇcna informacija o tem, kakˇsne so nasprotnikove karte, skrita.
V tem diplomskem delu smo se odloˇcili raziskati, kako inteligentni agenti igrajo v primerjavi s ˇclovekom. Ljudje smo namreˇc, ˇce si priznamo ali ne, do neke mere navezani na denar, obremenjeni s preteklimi izkuˇsnjami in ˇcustvi ter se lahko zato pri igrah, kot je poker, odzovemo napaˇcno. Agent s tem nima teˇzav, saj ne pozna ˇcustev, kot sta strah ali jeza zaradi izgubljanja, temveˇc upoˇsteva zgolj statistiko.
1
2 Jan Urankar Moˇzno je, da so igralci po veˇc letih igranja pokra ˇze na temelju svojih izkuˇsenj naˇsli pribliˇzek matematiˇcno pravilne strategije. V kolikor temu ni tako, to pomeni, da ljudje ne igramo optimalno in smo ˇse vedno inferiorni v primerjavi s pametnimi agenti.
V naslednjih poglavjih bomo najprej opisali razliˇcico pokra, ki smo jo uporabljali v tem diplomskem delu. Sledilo bo poglavje, v katerem bomo opisali, kako smo uˇcili agenta in kateri algoritem smo pri tem uporabili. V istem poglavju bomo prav tako podrobneje opisali delovanje naˇsega algo- ritma. Temu bo sledilo poglavje o izgradnji agenta in na koncu ˇse izvedba ter rezultati poskusa, ki smo ga izvedli.
Poglavje 2
No Limit Texas Holde’m
Poker je igra s kartami, pri kateri soigralˇceve karte ostanejo skrite v celoti ali delno. Poker je stara igra, vendar je ˇse danes ena izmed najbolj priljubljenih iger na svetu. Veliko ljudi poker uvrˇsˇca med igre na sreˇco, vendar je v veliki meri tudi igra znanja in ocenjevanja verjetnosti. Glede na svoje karte in karte na mizi se lahko vpraˇsamo, kakˇsna je verjetnost, da so naˇse karte boljˇse od nasprotnikovih ali kakˇsna je verjetnost, da nasprotnik blefira. Lahko bi rekli, da je poker igra, katere pravil se lahko nauˇcimo zelo hitro. Da postanemo resniˇcno dobri v njej, potrebujemo ogromno ur vaje in izkuˇsenj.
Obstaja veliko variacij pokra, ena izmed najbolj priljubljenih je Texas No Limit Hold’em. Za to diplomsko delo smo izbrali to razliˇcico pokra.
3
4 Jan Urankar
Slovar pojmov
Pojem Opis
Agent Agent v sklopu strojnega uˇcenja pomeni sistem, ki igra na te- melju strojnega uˇcenja oziroma umetne inteligence. Ti sistemi so pred uporabo uˇceni s pomoˇcjo raznih algoritmov za izbrano domeno in odloˇcitve izbirajo na temelju predhodnega uˇcenja.
Blinds Blinds je angleˇski izraz za stave v pokru. V pokru poznamo dve osnovni stavi, big blind in small blind, ki ju igralca, ki sta jima stavi dodeljeni, morata poloˇziti na mizo.
Big blind Angleˇski izraz za veliko stavo.
Small blind Angleˇski izraz za malo stavo. Ta je obiˇcajno vredna polovico velike stave
Faza Vsaka igra pokra je razdeljena na ˇstiri faze: preflop, flop, turn, river.
Preflop To je prva faza, pri kateri na mizi ˇse ni nobenih kart, ampak igralci lahko kljub temu stavijo ali odstopijo od igre, preden poloˇzijo v igro kakrˇsno koli koliˇcino denarja, ˇce s svojimi kar- tami niso zadovoljni. To ne velja za igralca, ki imata tisti krog big in small blind. Navedena igralca morata v skladu s pravili, preden prejmeta karte, na mizo poloˇziti ti dve stavi.
Flop Flop je druga faza v pokru, pri ˇcemer se na mizo dodelijo prve tri izmed petih kart.
Turn Turn je tretja faza v pokru, pri ˇcemer na mizo dodamo dodatno, in sicer ˇcetrto karto.
Diplomska naloga 5
Pojem Opis
River River je ˇcetrta in hkrati zadnja faza v pokru, ko na mizo poloˇzimo ˇse zadnjo, peto karto.
Pot Trenutna koliˇcina denarja, ki je v igri, kar je skupek vseh dose- danjih stav v igri.
Akcija V pokru imamo veˇc moˇznih akcij. Odstop, izenaˇcenje, ˇcek in viˇsanje. Igralec se na svoji potezi odloˇci za eno izmed teh akcij.
Katero akcijo izbere, je odvisno od poteka igre ter kako dobre karte in kombinacijo ima.
Odstop Odstop (angl. fold) je akcija, pri kateri se igralec odloˇci, da bo odstopil od igre in ne bo veˇc igral v trenutni igri. S tem igralec izgubi denar, ki ga je do tedaj stavil.
Izenaˇcenje Izenaˇcenje pomeni, da igralec izenaˇci stavo, ki jo je poloˇzil eden izmed igralcev pred njim (angl. ’call’).
Viˇsanje Ko igralec viˇsa (angl. ’raise’), poloˇzi stavo v igro, ki jo morajo nato tisti igralci, ki ˇzelijo nadaljevati igro, izenaˇciti.
Cekˇ V primeru, da igralec, ki je na potezi in ˇse noben igralec pred njim ni viˇsal, potem izenaˇcenje ni potrebno, saj ni stave, ki bi jo moral izenaˇciti. V tem primeru igralec lahko naredi ˇcek (angl. check), kar pomeni, da ne viˇsa, ampak vseeno nadaljuje igro, ne da bi v igro vplaˇcal dodaten denar.
All in Tip viˇsanja, ko igralec stavi ves svoj preostali denar.
Heads up Tip poker igre, ko igrata zgolj dva igralca, drug proti drugemu.
6 Jan Urankar
2.1 Pravila in potek igre
2.1.1 Potek igre
V izbrani variaciji pokra se vsakemu igralcu dodelita dve karti. To sta karti, ki sta skriti drugim igralcem. Po delitvi kart se na mizo v ˇstirih fazah poloˇzi pet kart, ki so vidne in skupne vsem igralcem. Te faze imenujemo preflop, flop, turn, river. Igralec nato iz kart na mizi in kart v roki sestavi najboljˇso moˇzno kombinacijo. Moˇc posameznih kombinacij kart je predstavljena v naslednjem poglavju.
Preflop je faza, ki se zgodi po deljenju kart igralcem in pred deljenjem kart na mizo. Tukaj imajo vsi igralci moˇznost, da stavijo, preden se pokaˇzejo prve karte. Naslednja stopnja je flop, ko delivec na mizo poloˇzi prve tri karte.
Nato sledi turn, ko delivec poloˇzi na mizo eno karto in nato ˇse river, ko delivec pokaˇze ˇse zadnjo karto.
Razlog, da se karte na mizo pokaˇzejo v treh fazah je, da imajo igralci v vsaki fazi moˇznost, da stavijo in nato lahko drugi igralci stavo predhodnih igralcev viˇsajo, izenaˇcijo ali stave ne izenaˇcijo in odstopijo od igre. Obstaja ˇse ena moˇzna akcija, in sicer ˇcek. To lahko igralci uporabijo, ˇce nihˇce pred njimi ˇse ni stavil. S tem nakaˇzejo, da ne bodo stavili, ampak bodo vseeno nadaljevali igro. To akcijo si lahko predstavljamo kot izenaˇcenje, ko se iz- enaˇcuje stavo igralcev pred posameznim igralcem, ker pa v tem primeru nihˇce pred njim ˇse ni stavil, to izenaˇci stavo na 0.
Ce pridemo v doloˇˇ ceni igri do konca, kar pomeni, da smo ˇsli skozi vse ˇstiri faze in so igralci izenaˇcili vse stave, potem igralci razkrijejo svoje karte.
Zmagovalec igre je tisti, ki ima najboljˇso kombinacijo kart. Kakˇsne so kom- binacije in kakˇsen je njihov vrstni red moˇci, je prikazano v tabeli 2.1, kjer na vrhu zaˇcnemo z najmoˇcnejˇso kombinacijo, ki ji nato po vrsti sledijo ˇsibkejˇse.
Posamezni igralec ima pred koncem igre na voljo sedem kart: dve v roki in pet na mizi. Izmed teh sedmih kart si izbere pet kart, ki mu najbolje ustrezajo in iz njih naredi kombinacijo. Tisti izmed igralcev, ki ima naj- boljˇso kombinacijo, pobere ves denar, ki je bil vloˇzen. To je vsota vseh stav
Diplomska naloga 7 vseh igralcev za to igro. V primeru da je pri veˇc igralcih teh pet kart enakih po moˇci, se denar na mizi razdeli med te igralce.
Pozicija Ime Primer kombinacije Opis kombinacije
1. Kraljeva
lestvica
♥ 10♥ J ♥ Q♥ K♥ A Kraljeva lestvica je najmoˇcnejˇsa moˇzna kombinacija v pokru. Da se jo doseˇze, se potrebuje karte 10, J, Q, K, A, ki so prav tako vse v isti barvi.
2. Barvna
lestvica
♥ 9♥ 10 ♥J ♥ Q ♥K Za to kombinacijo je potrebnih pet zaporednih kart, ki so prav tako vse v isti barvi.
3. Poker ♣ J ♥J ♦ J ♠ J ♥8 Za poker so potrebne ˇstiri enake karte, ki so seveda vse drugaˇcnih barv.
4. Polna hiˇsa ♣ J ♥J ♦ J ♠ 8♥ 8 Za polno hiˇso ali bolj upora- bljano ’full house’ so potrebne tri enake karte in pa dve drugi enaki karti.
5. Barva ♠ 10♠ 4 ♠J ♠ K ♠6 Za barvo ali ’flush’ potrebujemo pet kart enake barve, a ni po- trebno, da so zaporedne.
6. Lestvica ♥ 7♠ 8 ♠ 9♥ 10♦ J Za to kombinacijo potrebujemo 5 zaporednih kart, ki niso enake barve. Ce so enake barve,ˇ imamo barvno lestvico.
7. Tris ♠10♥10♦10♥K♠J Za tris potrebujemo tri enake
karte.
8 Jan Urankar
Pozicija Ime Primer kombinacije Opis kombinacije 8. Dva para ♠ 6 ♦6 ♥ 10♦ 10♥ K Za dva para potrebujemo dva-
krat po dve enaki karti.
9. Par ♠ 10♥ 10 ♦9 ♥ K♦ 4 Za par potrebujemo dve enaki
karti.
10. Najviˇsja karta
♠ A ♥ 10♦ J ♥ 4♦ 3 Ceˇ igralec nima nobene iz- med zgornjih kombinacij, po- tem se upoˇsteva njegova naj- boljˇsa karta. Ce drugi igralciˇ prav tako nimajo nobene kom- binacije, potem bo igro zmagal tisti, ki ima najviˇsjo karto.
Tabela 2.1: Tabela kombinacij
2.1.2 Stave
V vsaki igri sta doloˇcena dva tipa stave, ki ju dva igralca poloˇzita na mizo, preden se igra zaˇcne. Imenujemo ju ’big blind’ in ’small blind’. Kako visoki sta ti dve stavi, je odvisno od tega, za katero mizo ali v kateri sobi igramo.
Small blind je obiˇcajno velik polovico big blinda.
Ti dve stavi sta vsako igro doloˇceni dvema igralcema. Po vsaki igri se ti dve stavi premakneta za eno polje v smeri urinega kazalca. Na primer: ˇce je za mizo pet igralcev in ˇce za smer vzamemo smer urinega kazalca, bosta najprej ti dve stavi morala na mizo poloˇziti igralec 1 in igralec 2. Igralec 1 bo dal na mizo small blind, igralec 2 pa big blind.
Naslednjo igro se bosta ti dve stavi premaknili za eno mesto, tako da bo naslednjo igro imel igralec 2 small blind in igralec 3 big blind. Drugi igralci, ki pridejo za igralcem z big blindom, morajo nato izenaˇciti ali viˇsati big blind,
Diplomska naloga 9
Slika 2.1: Tipi stav
ˇce ˇzelijo igrati v igri. Nadaljnji igralci morajo nato prav tako izenaˇciti big blind in prav tako izenaˇciti kakrˇsne koli stave, ki so jih igralci pred njimi viˇsali.
Najniˇzji moˇzen small in big blind za doloˇceno mizo sta obiˇcajno 1 cent za small blind in 2 centa za big blind. Najveˇcji big blind in small blind v realnem svetu nimata zgornjega limita, saj so v doloˇcenih igrah lahko te stave visoke tudi nekaj tisoˇc evrov ali tudi veˇc. Razlog za big blind in small blind je, da je v vsaki igri vedno nekaj denarja na mizi. ˇCe teh stav ne bi bilo, igralci ne bi imeli nobene motivacije, da bi igrali igro, temveˇc bi zgolj ˇcakali, da dobijo v roke izjemno dobre karte, kot na primer par asov, ter samo takrat ˇsli v igro.
Katero sobo izberemo, glede na velikost big blinda in small blinda, je odvisno od tega, s kako veliko vsoto denarja ˇzelimo igrati. ˇCe ˇzelimo igrati igre, v katerih so poti veˇcji, bomo izbrali sobe z viˇsjimi blindi. Sploˇsno pravilo je, da moramo v igro vstopiti z vsaj toliko denarja, kot je vsota 40 do 70 big blindov. Na primer: ˇce igramo igro, v kateri je big blind 1 EUR, je priporoˇcljivo, da igramo vsaj s 40 EUR do 70 EUR. Priporoˇcljivo je ˇse veˇc, kajti z veˇc denarja bomo lahko igrali bolj dinamiˇcno.
10 Jan Urankar
2.2 Tipi igralcev
Vsak igralec ima svojo strategijo pri igri. Strategijo ali slog igre naˇceloma de- limo na ˇstiri kategorije: loose-passive, loose-agressive, tight-passive in tight- agressive. [6]
Da igralec igra ’Loose’ pomeni, da igra veliko rok in da ne ˇcaka na dobre karte, da gre v igro. Za ˇcloveka je veliko, ˇce igra od 30 % do 100 % rok.
Igralec igra ’Tight’, ˇce igra redko in raje poˇcaka na dobre karte in igra takrat. Taki igralci obiˇcajno igrajo od 10 % do 25 % rok.
’Passive’ ali pasiven igralec je tisti, ki ne stavi veliko. Obiˇcajno je zado- voljen z izenaˇcenjem ali odstopom in redko sam viˇsa stave.
’Aggressive’ igralci obiˇcajno stavijo veliko veˇc od povpreˇcja. Obiˇcajno nimajo teˇzav s polaganjem velikih stav, tudi ˇce sami drˇzijo zgolj par in veli- kokrat niti tega ne, saj so taki igralci bolj nagnjeni k tveganju in blefiranju.
Veˇcina igralcev se naˇceloma najde preteˇzno v eni izmed teh kategorij.
Kljub temu obiˇcajno uporabljajo strategijo, ki je meˇsanica vseh ˇstirih kate- gorij. Obstajajo tudi bolj opredeljeno doloˇcene kategorije, kot so ’River Rat’,
’Rocks’ in tako naprej. [7]
Poglavje 3
Uporabljeni algoritmi
Pri uˇcenju naˇsega agenta smo se odloˇcili za uporabo strojnega uˇcenja, po- drobnejˇse za spodbujevano uˇcenje. Spodbujevano uˇcenje je smiselna izbira za naˇse diplomsko delo, saj imamo na voljo igro, ki jo lahko poljubno velikokrat simuliramo, kar je bistveno za spodbujevano uˇcenje.
Algoritem, ki smo ga izbrali, imenujemo ’counterfactual regret minimiza- tion’. Razlog za izbiro je, da ta algoritem deluje zelo dobro pri igrah, kjer nam niso razkrite vse informacije in poker spada v to kategorijo iger.
3.1 Strojno uˇ cenje
Poznamo veˇc vrst strojnega uˇcenja: nadzorovano, nenadzorovano in spod- bujevano. Pri nadzorovanem imamo podane primere z neko ciljno spremen- ljivko. Iˇsˇcemo funkcijo, ki bo znala ˇcim bolje napovedovati konˇcno spremen- ljivko na novih primerih.
Pri nenadzorovanem uˇcenju imamo podane primere, ki niso oznaˇceni. Pri nenadzorovanem uˇcenju iˇsˇcemo zakonitosti ali vzorce v podatkih, na primer gruˇcenje ali angleˇsko ’clustering’.
Pri spodbujevanem uˇcenju nimamo dejanskih primerov. Imamo zgolj oko- lje in naˇsega agenta ˇzelimo ˇcim bolje nauˇciti, da bo s pridobivanjem izkuˇsenj naˇsel ˇcim boljˇso strategijo za odloˇcanje v doloˇcenem okolju. To okolje je
11
12 Jan Urankar lahko neka igra, samovozeˇci avtomobil, doloˇcen robot in tako naprej.
Spodbujevano uˇcenje to doseˇze s pomoˇcjo uporabe nagrad in kazni. Agenta postavimo v neko stanje in mu doloˇcimo kazni in nagrade. V pokru sta kazen in nagrada vezana na to, koliko denarja je agent dobil ali izgubil v primerjavi s tem, koliko bi ga dobil ali izgubil, ˇce bi v tej situaciji igral drugaˇce.
Pametno je, da nagrade veˇzemo glede na to, kakˇsen bi bil izid v isti situaciji, ˇce bi uporabili druge akcije in ne gledamo zgolj na zasluˇzek ali izgubo. Velikokrat se zgodi, da so vse moˇznosti slabe in zgolj poskuˇsamo minimizirati slab vpliv. Tako se bomo nauˇcili, katera izmed moˇznosti nam bo povzroˇcila najmanj ˇskode in tej dali najveˇcjo nagrado.
Za najslabˇso moˇzno odigrano igro bo dobil najveˇcjo kazen in za najboljˇso moˇzno odigrano igro najveˇcjo nagrado. Glede na dobljene nagrade in kazni bo agent v prihodnosti prilagodil, kako igrati v doloˇceni situaciji.
3.2 Counterfactual regret minimization
Algoritem, na katerem smo osnovali program, se imenuje counterfactual re- gret minimization [2][9]. Algoritem spada v vrsto spodbujevanega uˇcenja.
Algoritem deluje na temelju nagrad in kazni. Agent igra proti samemu sebi in se na ta naˇcin uˇci. Dve instanci algoritma oziroma dva agenta igrata drug proti drugemu. Na zaˇcetku agent izbira akcije nakljuˇcno oziroma z enako verjetnostjo, kar je seveda precej slaba strategija. S ˇcasom, ko simuliramo veˇc tisoˇc iger, agent postopoma prilagaja svojo igro. Igro prilagaja tako, da pogosteje izbira akcije, ki so mu v preteklosti v enaki situaciji prinesle viˇsjo nagrado. 1
1Intuitivna razlaga avtorja algoritma je dosegljiva na povezavi https://www.quora.com/What-is-an-intuitive-explanation-of-counterfactual-regret- minimization
Diplomska naloga 13
3.2.1 Reˇ sena igra
To, da je igra reˇsena, ne pomeni, da bo agent zmagal in dobil denar vsako igro, ampak pomeni, da agent na dolgi rok ne bo izgubil. V najslabˇsem primeru bo, ˇce upoˇstevamo povpreˇcje vseh iger, vedno imel vsaj nevtralno stanje. To bi se verjetno zgodilo zgolj, ˇce bi proti njemu igral ˇse en agent, ki je prav tako reˇsil igro, ampak v veˇcini primerov, ˇce bi z njim igrali ljudje, bi ta agent na dolgi rok skoraj zagotovo vedno zmagal.
Dober primer reˇsene igre je Blackjack. V blackjacku imamo na voljo ˇstiri akcije: ’hit’, ’stand’, ’double down’ in ’split’. S tem, ko reˇcemo, da je igra
’reˇsena’, mislimo, da je bila optimalna strategija za doloˇceno igro ˇze mate- matiˇcno izraˇcunana. Pri blackjacku to pomeni, da za vsako situacijo vemo, katera moˇznost izmed naˇstetih je najbolj optimalna, ˇce ˇzelimo maksimizirati dobiˇcek.
Blackjack je reˇsen ˇze dlje ˇcasa, saj so ’reˇsitve’ ˇze pred ˇcasom objavili razliˇcni avtorji in so sploˇsno znane. Optimalna strategija, ki ji v angleˇsˇcini reˇcemo ’blackjack basic strategy’[1], za igranje igre Blackjack, je prikazana v spodnji tabeli 3.1. V prvem stolpcu pogledamo, kakˇsna je naˇsa kombinacija kart, v prvi vrstici pa pogledamo, katera je prva karta delivca. Glede na izbrano polje v stolpcu in vrstici, lahko v tabeli dobimo ’reˇsitev’ oziroma matematiˇcno najboljˇso akcijo glede na naˇso trenutno situacijo.
14 Jan Urankar
Slika 3.1: Optimalna strategija za blackjack [1]
Diplomska naloga 15
3.3 Delovanje algoritma CFR pri pokru
No limit holde’m je velika igra, ki je morda nikoli ne bomo popolnoma reˇsili, ker je razpon stav ogromen. Vsako stavo doloˇcenega igralca lahko drugi igralci viˇsajo dokler ˇzelijo. Z doloˇcenimi poenostavitvami se lahko precej pribliˇzamo reˇsitvi igre.
Izbrali smo algoritem, ki se uˇci glede na to, v kateri situaciji smo trenutno in katera akcija se nam je prejˇsnjiˇc v tej situaciji najbolj splaˇcala. Vedno se zavedamo, v katerem stanju smo. Najbolj logiˇcna izbira podatkovne struk- ture za tovrstne probleme je drevo, vendar kot bomo pojasnili v naslednjem poglavju, to ni edina moˇzna implementacija.
3.3.1 Moˇ zne akcije
V roki imamo dve karti, na primer kraljico in sedmico. V tej toˇcki smo ˇze v prvem stanju. Na voljo imamo veˇc akcij. Med katerimi akcijami bomo izbi- rali, doloˇcimo sami. Veˇc moˇznih akcij damo raˇcunalniku na voljo, natanˇcnejˇsi bo algoritem, vendar bo hkrati porabil veliko veˇc ˇcasa in prostora za uˇcenje.
Moˇzne akcije pri pokru, ki so obvezne, so odstop, ˇcek, izenaˇcenje, viˇsanje.
Akcijo viˇsanje moramo razdeliti na veˇc podakcij, glede na to, koliko bomo stavili. V teoriji bi bil algoritem najnatanˇcnejˇsi, ˇce bi za moˇzne akcije dali vse moˇzne stave, kar zaradi ogromne prostorske kompleksnosti ni mogoˇce.
Zato vnaprej doloˇcimo moˇzne akcije in nato stave zaokroˇzimo na najbliˇzjo izmed teh akcij.
Moˇzne akcije so lahko na primer ’odstopi’, ’izenaˇci’, ’ˇcek’, ’viˇsaj 1’, ’viˇsaj 2’, ’viˇsaj 5’, ’viˇsaj 10’, ’viˇsaj 20, viˇsaj 50’, ’all in’. ˇCe bo nasprotnik pri teh moˇznih akcijah stavil 37, bomo to umestili v akcijo, ki je temu najbljiˇzja in v tem primeru je to ’viˇsaj 50’. Nasprotnik v resnici ni stavil 50, ampak ustvarjalci algoritma so predpostavili, da je doloˇcena mera posploˇsevanja stav skoraj neˇskodljiva. ˇCe nekdo stavi 201, ne bomo naredili velike napake, ˇce ga klasificiramo v ’viˇsaj 200’.
Kljub temu poenostavljanje ali zaokroˇzevanje stav ne smeta biti prevelika,
16 Jan Urankar saj bi to preveˇc vplivalo na igro. ˇCe imamo moˇzne akcije ’odstopi’, izenaˇci’,
’ˇcek’, ’viˇsaj 10’, ’viˇsaj 300’ in nasprotnik stavi 100, bi to stavo umestili v akcijo ’viˇsaj 10’, kar je ˇze velika razlika.
Tu se sreˇcamo s teˇzavo. ˇZelimo sicer imeti ˇcim veˇc akcij, da bo agent lahko igral ˇcim bolj dinamiˇcno, vendar ˇce jih imamo preveˇc, bosta prostorska in ˇcasovna kompleksnost preveliki, da bi agenta lahko dobro nauˇcili.
3.3.2 Postopek delovanja algoritma
Osnovna podatkovna struktura naˇsega algoritma je drevo, ki ga sestavljajo vozliˇsˇca. Korensko vozliˇsˇce drevesa je prazno in ne vsebuje nobenih podatkov, razen povezave na svoje sinove. Sinovi korenskega vozliˇsˇca so vse moˇzne kombinacije dveh kart, ki jih igralec lahko dobi. Sinovi teh vozliˇsˇc in vozliˇsˇc pod njimi so oznaˇceni z moˇznimi akcijami, ki jih lahko izvedemo, ˇce smo v tistem vozliˇsˇcu.
Po drevesu se pomikamo glede na to, kako se igra odvija. ˇCe imamo v roki osmico in kraljico, se iz korena drevesa pomaknemo v sina, ki ima za oznako osmico in kraljico. Od tu naprej se premikamo glede na to, kakˇsen je potek igre. ˇCe smo igralec 0 in smo na zaˇcetku igre, potem se odloˇcimo za neko potezo in se premaknemo v drevo, ki oznaˇcuje to akcijo. ˇCe smo igralec 1, se prav tako pomaknemo v sina, ki ga oznaˇcuje akcija, ki jo je naredil igralec 0. Ko igralec 0 opravi potezo, se vloge obrnejo. Igralec 1 se odloˇci za eno izmed akcij in nato se tako igralec 0 kot igralec 1 pomakneta v sina, ki oznaˇcuje tisto akcijo, ki jo je naredil igralec 1.
Z izjemo korenskega vozliˇsˇca v vseh vozliˇsˇcih hranimo dve tabeli, in sicer tabelo, ki hrani vsoto dosedanje izgube, in tabelo, ki hrani vsoto dosedanje strategije. Izguba je kljuˇcni del naˇsega algoritma, in sicer nam pove, kako dobri ali slabi so bili rezultati v preteklosti, ˇce smo izbrali doloˇceno akcijo v primerjavi, z izbiro druge akcije. Iz izgube nato ugotovimo, s kakˇsno verje- tnostjo bomo igrali posamezne akcije, ˇce pridemo v to vozliˇsˇce. Strategijo, kako bomo igrali v vozliˇsˇcu, dobimo tako, da seˇstejemo vse pozitivne vredno-
Diplomska naloga 17
Slika 3.2: Struktura drevesa
sti v tabeli, kjer hranimo dosedanjo izgubo in tako dobimo N. Verjetnost, s katero bomo igrali posamezno akcijo, dobimo tako, da izgubo za to akcijo, ki jo hranimo v tabeli, delimo z N. ˇCe ima akcija negativno dosedanjo izgubo, je verjetnost, da igramo to akcijo, 0. Izguba je lahko pozitivna ali negativna.
Pozitivna izguba nam pove, da je bila akcija v preteklosti dobra in viˇsja, kot je pozitivna izguba, boljˇsa je bila akcija v preteklosti. Enako velja za negativno izgubo, in sicer bolj, kot je izguba negativna, slabˇsa je bila akcija v preteklosti.
Vzemimo primer, da je nova tabela izgube posodobljena in ima vredno- sti ’ˇcek’:5, ’izenaˇcenje’:15, ’viˇsaj 5’:10, ’viˇsaj 20’:-5, ’viˇsaj 100’:-10. Najprej seˇstejemo vse pozitivne vrednosti, kar v naˇsem primeru znaˇsa 30. Temu reˇcemo N. Verjetnost vsake akcije dobimo tako, da izgubo te akcije delimo z normalizacijsko uteˇzjo, torej za prvo akcijo bi bil izraˇcun 5/30=0,167. Ta izraˇcun nam pove, da bomo akcijo ’ˇcek’, ko bo agent igral igro, pri ˇcemer se
18 Jan Urankar bo moral odloˇcati, katero akcijo bo izbral, igral z verjetnostjo 0,167 oziroma 16.7 % ˇcasa, ko se bo nahajal v tem doloˇcenem vozliˇsˇcu.
Negativnim vrednostim dodamo verjetnost 0. Tabela naˇse strategije s temi izgubami bi bila strategy=’ˇcek’: 0.167, ’izenaˇci’: 0.5, ’viˇsaj 5’: 0,333,
’viˇsaj 20’: 0.0, ’viˇsaj 100’: 0.0. To strategijo nato priˇstejemo tudi v naˇso tabelo dosedanje strategije v tem vozliˇsˇcu.
Slika 3.3: Struktura drevesa za naˇs primer
Na zaˇcetku uˇcenja v vseh vozliˇsˇcih elemente v obeh tabelah nastavimo na 0. Na zaˇcetku bo strategija, ki jo dobimo v doloˇcenem vozliˇsˇcu, nakljuˇcna in bomo vse akcije igrali z enako verjetnostjo.
Vsako vozliˇsˇce ima doloˇceno pozitivno ali negativno izgubo. Ta izguba je, ˇce smo v konˇcnem vozliˇsˇcu (vozliˇsˇce, ko se igra zakljuˇci, torej smo pokazali karte ali pa je nekdo odstopil), enaka znesku, ki smo ga trenutno dobili ali izgubili. Ce smo odstopili, smo izgubili vse kar smo do sedaj prispevali.ˇ Obratno velja, ˇce je odstopil nasprotnik. V tem primeru mi dobimo denar,
Diplomska naloga 19 ki je trenutno na mizi. Prav tako, ˇce smo pokazali karte: tisti, ki ima boljˇso kombinacijo, pobere vse, kar je na mizi. Torej, ˇce smo do nekega trenutka na mizo poloˇzili tri ˇzetone in smo nato odstopili ter poslediˇcno izgubili, bo izguba v tem vozliˇsˇcu za nas -3, za naˇsega nasprotnika pa 3.
Pri vozliˇsˇcih, ki niso konˇcna, izgubo izraˇcunamo s pomoˇcjo vzvratne funk- cije. Izguba vozliˇsˇca je vsota izgub vseh vozliˇsˇc, v katera pridemo, ko izbe- remo posamezno akcijo v naˇsem vozliˇsˇcu, pomnoˇzeno z verjetnostjo, da bi to akcijo izbrali. Vrednost, ki jo dobimo, je izguba trenutnega vozliˇsˇca v tej iteraciji.
Potem, ko izraˇcunamo izgubo naˇsega vozliˇsˇca, posodobimo ˇse vrednosti v naˇsi tabeli izgub, ki jo hranimo v naˇsem vozliˇsˇcu. Vsem akcijam v tabeli, kjer hranimo izgube, priˇstejemo vrednost: (vrednost, ki jo priˇstejemo tabeli izgub za trenutno akcijo) = (Izguba sina, ki je oznaˇcen z doloˇceno moˇzno akcijo) - (izguba trenutnega vozliˇsˇca).
To nam omogoˇca, da med vsemi akcijami vedno izberemo najboljˇso. V primeru, da so vse akcije slabe, potem na ta naˇcin ugotovimo, katera je naj- boljˇsa izmed slabih akcij.
Tabela vsot dosedanjih izgub je v trenutnem vozliˇsˇcu ’ˇcek’: 5, ’izenaˇcenje’:15,
’viˇsaj 5’:10, ’viˇsaj 20’:-5, ’viˇsaj 100’:-10. Tabela vsote dosedanjih strategij je
’ˇcek’: 0,167, ’izenaˇcenje’: 0,5, ’viˇsaj 5’: 0,333, ’viˇsaj 20’: 0.0, ’viˇsaj 100’: 0,0.
Vrednosti iz te tabele moramo najprej normalizirati, ampak v tem primeru to ni potrebno, saj je vsota verjetnosti enaka 1. Izguba, ki smo jo dobili iz posameznih sinov v tej iteraciji, je za akcijo ’ˇcek’ enaka 0, za akcijo ’iz- enaˇcenje’ -5, za akcijo ’viˇsaj 10’ 5, za akcijo ’viˇsaj 20’ 30 in za akcijo ’viˇsaj 100’ enak 10. Izguba v trenutnem vozliˇsˇcu bi tako bila 0,167*0 + 0,5*(-5) + 0,333*5 + 0*30 + 0*10 = -0.83.
Sedaj ˇse posodobimo tabelo vsot dosedanjih izgub. Za akcijo ’izenaˇcenje’
je vrednost izgube v tabeli pred posodobitvijo 5. Tej vrednosti priˇstejemo vrednost (0 - (-0.83)) = 0.83. Posodobljena vrednost je sedaj 5 + 0,83 = 5,83. Enako naredimo za druge. Tabela izgub po posodobitvi vsebuje: ’ˇcek’:
20 Jan Urankar 5,83, ’izenaˇcenje’: 10,83, ’viˇsaj 5’:15,83, ’viˇsaj 20’:25,83, ’viˇsaj 100’:0,83.
Ce bi nato ponovno priˇsli v isto vozliˇsˇˇ ce in ˇzeleli izraˇcunati posodobljeno strategijo glede na tabelo ’ˇcek’:5,83, ’izenaˇcenje’:10,83, ’viˇsaj 5’:15,83, ’viˇsaj 20’:25,83, ’viˇsaj 100’:0,83, bi dobili N=59,15, kar bi nam dalo strategijo ’ˇcek’:
0,099, ’izenaˇcenje’: 0,18, ’viˇsaj 5’: 0,268, ’viˇsaj 20’: 0,44, ’viˇsaj 100’: 0,01 in zatem bi te vrednosti dodali v tabelo, kjer hranimo vsoto dosedanjih strategij in bi dobili ’ˇcek’: 0,266, ’izenaˇcenje’: 0,68, ’viˇsaj 5’: 0,601, ’viˇsaj 20’: 0,44,
’viˇsaj 100’: 0,01.
Ko ponovno pridemo v isto vozliˇsˇce, bomo uporabili posodobljene verje- tnosti, ki bodo sedaj drugaˇce vplivale na razporeditev izgub. Skozi veliko iteracij bomo, z veˇc kombinacijami nasprotnikovih kart in kart, ki padejo na mizo, naˇsli optimalno strategijo za igranje v tem doloˇcenem vozliˇsˇcu.
3.3.3 Implementacija
Poznamo veˇc naˇcinov implementacije algoritma. En naˇcin je implementacija s pomoˇcjo slovarja in drug naˇcin s pomoˇcjo drevesa.
Maksimalna globina drevesa v naˇsi implementaciji je 13, maksimalno ˇstevilo akcij pa je 6. Vseh moˇznih kombinacij dveh kart v roki je 169 in imamo dva igralca, ki igrata drug proti drugemu. Za vsak par zaˇcetnih kart za vsakega igralca ustvarimo sina korenskega vozliˇsa. Vse skupaj ima zato koren drevesa 169*2 sinov. Sin korena vsebuje maksimalno 6ˆ12 vozliˇsˇc. To pomeni, da skupaj hranimo okoli 2*169*6ˆ12 vozliˇsˇc.
To je ogromno ˇstevilo vozliˇsˇc, ki jih v realnosti teˇzko hranimo v naˇsem pomnilniku in zato veˇcji del stanj hranimo na lastnem disku.
3.3.4 Implementacija z drevesom
Drevo hrani vse podatke v vozliˇsˇcih. V vsakem vozliˇsˇcu hranimo podatke o ’izgubah’, ki nam pove, katere akcije so bile v preteklosti boljˇse in katere slabˇse, iz ˇcesar potem izpeljemo verjetnosti v tem stanju. Prav tako v vsakem
Diplomska naloga 21 vozliˇsˇcu hranimo tudi vse njegove sinove, ki so prav tako vozliˇsˇca. Ko bomo izbrali eno izmed akcij, bomo preˇsli v enega izmed teh vozliˇsˇc. Casovnaˇ zahtevnost za to je O(1).
Na disku ne hranimo celega drevesa, ampak hranimo sinove korenskega vozliˇsˇca. Preden zaˇzenemo simulacijo, v delovni pomnilnik naloˇzimo tiste sinove korenskega vozliˇsˇca, ki jih potrebujemo.
3.3.5 Implementacija s slovarjem
Pri implementaciji s slovarjem vsakiˇc, ko pridemo v novo stanje, dostopamo do novega vozliˇsˇca. Ob vsaki menjavi vozliˇsˇc dostopamo do slovarja in s pomoˇcjo kljuˇca poiˇsˇcemo vozliˇsˇce, v katerem so shranjene verjetnosti za po- samezne akcije.
Casovna zahtevnost te implementacije je v praksi dobra. Za vsako vozliˇsˇˇ ce naredimo kljuˇc, ki ga sestavljata njegova zgodovina h in karte, ki jih igralec trenutno drˇzi. V tem primeru bi do vsakega vozliˇsˇca dostopali s hitrostjo O(1).
Velika prednost te implementacije je, da nam v delovni pomnilnik ni po- trebno nalagati celotnih poddreves za posamezni zaˇcetni karti, ampak zgolj vozliˇsˇce, ki ga trenutno potrebujemo. To moˇcno pohitri algoritem, saj pri simulaciji igre, ˇceprav naloˇzimo celotno drevo, obiˇcajno uporabljamo zgolj nekaj izmed naloˇzenih vozliˇsˇc.
3.4 Uporaba CFR za igranje pokra
Nekaj ekip raziskovalcev je ˇze uporabljalo algoritem CFR na podroˇcju stroj- nega uˇcenja pri pokru. Eden izmed veˇcjih doseˇzkov, ne le pri pokru, ampak tudi pri strojnem uˇcenju na podroˇcju iger na sploˇsno, je bil, ko je leta 2015 Univerza v Alberti objavila program Cepheus. Ta je v celoti reˇsil eno izmed razliˇcic pokra, imenovano Texas Limit Holde’m. Za Texas Limit Holde’m bi lahko rekli, da je podobna igri Texas No Limit Holde’m, le da je naˇcin stav
22 Jan Urankar precej bolj omejen, kar igro naredi precej bolj preprosto za reˇsevanje, saj je ˇstevilo moˇznih stanj precej manjˇse.
Nekaj ekip je ˇze doseglo precej dobre rezultate v igri agentov proti ˇcloveku, celo profesionalnim igralcem pokra. Dva izmed najboljˇsih projektov sta Li- bratus in Pluribus. Oba sta za jedro programa uporabljala CFR, vendar so algoritem CFR nekoliko prilagodili.
3.4.1 Libratus
Libratus je agent, ki je narejen za igro No Limit Holde’m heads up. Heads up pomeni, da poker igrata le dva igralca, drug proti drugemu. Izdelali so ga na univerzi Carnegie Mellon v Pittsburghu. Uˇcili so ga okoli 15 milijonov jedrnih ur. Za uˇcenje Libratusa so uporabljali 100 CPE-jev.
Leta 2017 so organizirali turnir, na katerem je Libratus igral proti ˇstirim profesionalnim igralcem pokra. Do takrat umetna inteligenca ˇse ni premagala najboljˇsih igralcev pokra na svetu in tudi takrat, glede na kvote na stavnicah, tega niso priˇcakovali in so bili veˇcinoma prepriˇcani, da bo ˇclovek zmagal.
V nasprotju s priˇcakovanji, je Libratus zmagal. Turnir Libratusa proti ˇcloveku je trajal 20 dni. Libratus je zmagoval ˇze po prvem dnevu in tako na- daljeval do konca turnirja. Po vsakem dnevu so programerji agenta ponovno nauˇcili, da je upoˇsteval tudi tisto, kar se je dogajalo tisti dan. Poudarek je bil predvsem na uˇcenju iz porazov. S tem se je Libratus vsak dan izboljˇseval.
Do konca turnirja je Libratus v povreˇcju zasluˇzil 14,7 big blindov na 100 iger, kar je pri pokru veliko.
Programerji so za agenta uporabljali algoritem CFR+, ki je nadgradnja algoritma CFR. Prva razlika je, da se izgube posodabljajo izmeniˇcno, kar pomeni, da v eni igri posodobimo izgubo igralcu 0 in v naslednji igralcu 1. V trenutni razliˇcici CFR-algortima posodabljamo izgubo obema hkrati. Poleg tega ta algoritem drugaˇce uporablja izgube. Namesto hranjenja dejanskih izgub hrani vrednosti, podobne izgubam, ki jih izraˇcuna na temelju prejˇsnjih vrednosti in trenutne izgube. Izboljˇsan algoritem tipiˇcno deluje bolje kot prejˇsnji algoritmi, in sicer z vidika ˇcasovne in prostorske kompleksnosti.
Diplomska naloga 23
3.4.2 Pluribus
Pluribus je bil prav tako razvit na univerzi Carnegie Mellon, pri katerem so sodelovali z raziskovalci iz oddelka Facebook AI. Libratus je bil odliˇcen doseˇzek, ampak je bil omejen zgolj na dva igralca. Pluribus si je zadal ambi- ciozno nalogo, da razvije inteligentnega agenta za ˇsest igralcev. Bili so precej uspeˇsni. [4]
Algoritem, ki so ga uporabili, je bil Monte Carlo Counterfactual Re- gret Minimization, pri ˇcemer pri opisu igre uporabljajo veˇc abstrakcij in poslediˇcno upravljajo manj podatkov.
Na turnirju, ki je trajal 12 dni in je bilo na njem odigranih veˇc kot 10 tisoˇc iger, je Pluribus premagal 15 profesionalnih igralcev pokra. Hkrati jih je igralo ˇsest za eno mizo.
Zanimivo pri Pluribusu je bilo tudi, kako malo raˇcunske moˇci je bilo po- trebno, da so ga uspeˇsno nauˇcili. Pluribus je potreboval zgolj dva Intelova Haswell E5-2695 v3 CPE-ja in je porabljal manj kot 128 GB delovnega po- mnilnika. Za primerjavo, AlphaGo je leta 2016 v namizni igri Go proti Leeju Sedolu uporabljal 1920 CPE-jev. Deep Blue je leta 1997 proti Gariju Kaspa- rovu uporabljal 480 posebno izdelavnih ˇcipov.
Pluribus je obiˇcajno porabil 20 sekund za vsako igro. To je pribljiˇzno polovico manj ˇcasa, kot v povpreˇcju porabijo profesionalni igralci pokra.
24 Jan Urankar
Poglavje 4
Izgradnja agenta
V sklopu diplomskega dela smo tudi sami razvili agenta, ki za jedro pro- grama uporablja counterfactual regret minimization. Pri programiranju ni- smo uporabljali nobene knjiˇznice za strojno uˇcenje, ampak smo vse pro- gramirali roˇcno, s pomoˇcjo numpy tabel in statistike. Prav tako smo dodali moˇznost igre z agentom in izdelali GUI, da lahko z njim igramo, ko ga uspeˇsno nauˇcimo igre. 1
4.1 Osnovno delovanje algoritma za uˇ cenje agenta
Algoritem deluje po klasiˇcnem naˇcelu CFR. Za implementacijo smo uporabili drevo. Agentu sta dodani dve karti. Glede na karti in glede na to, ali je na potezi igralec 0 ali igralec 1, mu je dodeljen sin korena drevesa. To vozliˇsˇce je poddrevo, ki je nauˇceno, kako igrati z dodeljenimi kartami.
Ko smo na potezi mi, gremo v tisto vozliˇsˇce, ki ustreza izvedeni potezi.
Ce je na vrsti nasprotnik, se pomaknemo v sina glede na nasprotnikovo ak-ˇ cijo. Tako rekurzivno nadaljujemo, dokler ne pridemo do konˇcnega stanja.
Obstajata dva tipa konˇcnih stanj: prvi je, da eden izmed igralcev odstopi ali
1Projekt je dosegljiv na naˇsem github profilu: https://github.com/jurankar
25
26 Jan Urankar
’fold’, drugi pa je, da oba igralca igrata igro do konca, ko se pokaˇzejo karte.
Obiˇcajno je veˇcina konˇcnih stanj, da igralec odstopi, preden se pokaˇzejo karte.
4.2 Problem izbire parametrov pri uˇ cenju
Pri strojnem uˇcenju je izbira parametrov kljuˇcna pri uˇcenju naˇsega agenta.
Algoritem smo najprej zagnali s parametri, ki smo jih naˇsli v objavljeni literaturi. Literatura nam je svetovala, naj tabele z izgubami nastavimo na vrednost 0. Opazili smo, da uˇcenje s temi parametri poteka relativno poˇcasi.
Poskusi so pokazali, da bi uˇcenje s takˇsnimi nastavitvami trajalo predolgo, zato smo s poskuˇsanjem poiskali boljˇse zaˇcetne nastavitve.
Sprva smo, kot je omenjeno v originalni publikaciji, nastavili tabele izgub na 0. To ni bila optimalna izbira, saj je, po simulaciji prvih nekaj iger, ena izmed akcij dobila verjetnost skoraj 1, ˇcetudi ni bila najboljˇsa. ˇCeprav bi lahko algoritem med uˇcenjem to popravil, smo odkrili, da lahko uˇcenje pospeˇsimo tako, da tabele izgub inicializiramo na neko vrednost, ki je bila veˇcja od 0. Poskusili smo veˇc vrednosti. Na koncu je vrednost 20 delovala najbolje od vseh.
Naslednje, kar smo spremenili, je, da pri doloˇcenih stanjih (pri stanjih, ko se agent/igralec odloˇca, ali bo odstopil ali ne) izgube nikoli niso negativne.
Namesto da enemu stanju odˇstejemo izgubo, smo jo priˇsteli drugemu stanju.
S tem nobena akcija ni imela negativnih izgub in poslediˇcno nobena akcija ni imela verjetnost igranja 0. To je prav tako imelo pozitiven uˇcinek na hitrost uˇcenja in je tudi razreˇsilo teˇzavo veˇcnih ’all-in-ov’, ki jo bomo opisali v nadaljevanju.
4.2.1 Napake zaradi slabo nastavljenih parametrov
Teˇzava ’all-in-ov’ je bila s prva precej nerazloˇzljiva, saj je kazalo, da agent deluje, kot bi moral. Agent je takoj, ko je bilo to mogoˇce, poloˇzil na mizo all- in. Sprva smo predpostavljali, da je morda teˇzava zgolj v igralcu 0, ampak ko smo ’prisilili’ igralca 0, da igra ˇcek, je igralec 1 prav tako vedno stavil
Diplomska naloga 27 all-in.
Sprva je kazalo, da gre za nekakˇsno napako v programu, ampak po dolgem analiziranju in debagiranju programa je postalo jasno, da program deluje ustrezno. Teˇzava je bila, da so se parametri prilagajali zelo poˇcasi. Razlog za to je bil, da vozliˇsˇce na zaˇcetku incializiramo z enakimi verjetnostmi, kar pomeni, da bo agent z enako verjetnostjo igral vse moˇznosti.
Napaka je bila, da je po prvih nekaj iteracijah algoritem skoraj eliminiral precej akcij, saj so le-te v prvih nekaj igrah imele negativno izgubo, kar je pomenilo, da jih igramo z verjetnostjo 0. Algoritem je ustvarjen, da to sˇcasoma popravi, vendar bi bilo za to potrebno, da se najprej popravijo vsa poddrevesa, kar lahko traja precej ˇcasa.
4.3 Uporabljene optimizacije
Algoritem je v osnovi poˇcasen in precej prostorsko potraten. V veliki meri je ta program sˇcasoma postal optimizacijska teˇzava. Bolj, kot lahko program optimiziramo, veˇc moˇznih akcij mu lahko dodamo in bolje bo agent igral, saj lahko igra bolj dinamiˇcno.
Uvedli smo veliko manjˇsih optimizacij, kot je to, da najprej globalno izraˇcunamo, kdo je zmagovalec, ˇce se bodo na koncu pokazale karte, namesto da vsakiˇc posebej raˇcunamo, kdo je zmagal, in druge. Najpomembnejeˇse optimizacije opisujemo v nadaljevanju.
Teˇzava tega algoritma je velika poraba prostora in ˇcasa, saj je moˇznosti v pokru resniˇcno veliko. ˇZe pri opisu o dosedanjih doseˇzkih smo omenili, kakˇsne koliˇcine virov porabljajo taki algoritmi. Nauˇceni sinovi korena drevesa so v naˇsem algoritmu, preden poreˇzemo drevo, vsak porabili okoli 5 GB do 10 GB. Podobno slabost so do neke mere odpravili v ’nadgrajenih razliˇcicah’
algoritma, kot sta CFR+ ali Deep CFR. Tudi mi smo jo z rezanjem neupo- rabljenih vej poddreves do neke mere omejili.
28 Jan Urankar
4.3.1 Shranjevanje sinov korena drevesa na disk
V praksi je celotna igra preprosto prevelika, da bi jo hranili v delovnem pomnilniku. Vsako vozliˇsˇce je pred rezanjem porabilo okoli 5 GB, kar bi pomenilo, da pri 338 sinovih korena drevesa program zasede okoli 1,5 TB spomina. Reˇsitev za to je bila, da smo sinove korena drevesa shranjevali na disk, kar je moˇcno sprostilo delovni pomnilnik, saj sta bila hkrati v delovnem pomnilniku potem naloˇzena zgolj dva sinova korena drevesa, in sicer en za agenta 0 in en za agenta 1. To je zmanjˇsalo zasedenost pomnilnika na pri- bliˇzno eno stodevetinˇsesdesetino prvotno uporabljenega. Slabost je bila, da smo s tem moˇcno poveˇcali ˇcasovno zahtevnost.
4.3.2 Veˇ cje ˇ stevilo simuliranih iger na sinovih korena drevesa
Ko smo zaˇceli shranjevati sinove korena drevesa na disk, se je ˇcasovna kom- pleksnost moˇcno poveˇcala, saj je program sedaj veˇcino ˇcasa porabil za branje in zapisovanje sinov korena drevesa na disk. To teˇzavo smo reˇsili tako, da smo vsakiˇc, ko smo naloˇzili sinova korena drevesa za oba agenta, na teh vo- zliˇsˇcih simulirali veˇc iger. Namesto da bi naloˇzili obe vozliˇsˇci, odigrali eno igro in zapisali vozliˇsˇce nazaj na disk, smo sedaj po tem, ko smo naloˇzili obe vozliˇsˇci, simulirali okoli sto iger.
Igralca sta tako imela enake zaˇcetne karte in preostali del kupˇcka smo na novo premeˇsali. Ugotovili smo, da je najbolj optimalno, da na zaˇcetku, ko so vozliˇsˇca ˇse precej majhna in se hitro berejo in zapisujejo, simuliramo deset iger na enkrat; kasneje smo to ˇstevilko poveˇcali na 100 iger za vsako vozliˇsˇce.
Prav tako smo poskusili s simuliranjem 1000 iger, kar je bilo preveˇc, saj so se vozliˇsˇca nato preveˇc prilagodila na tisti par zaˇcetnih kart.
Diplomska naloga 29
4.3.3 Rezanje vej dreves po dovoljˇ snem ˇ stevilu simu- lacij
Kljub opisani optimizaciji je bila prostorska zahtevnost ˇse vedno prevelika.
Algoritem je izdelan tako, da kljub temu, da sˇcasoma ugotovi katera je naj- boljˇsa akcija v doloˇceni situaciji in to akcijo nato igra veˇcino ˇcasa, ˇse vedno simulira druga poddrevesa, kar pobere ogromno ˇcasa. Ce smo na primerˇ doloˇcili ˇsest moˇznih akcij, kljub temu, da bo agent igral moˇznost 1 z verje- tnostjo 0,995, bo kljub temu simuliral ˇse vsa druga poddrevesa in uˇcinkovito porabil 5/6 veˇc ˇcasa za akcije, ki jih v realnosti ne bo skoraj nikoli uporabil.
Odloˇcili smo se, da taka poddrevesa izbriˇsemo. To je moˇcno zmanjˇsalo prostor na delovnem polnilniku in disku, ki ga vozliˇsˇca zasedejo. Toda op- timizacija nam na zaˇcetku ne pomaga, saj moramo na teh vozliˇsˇcih najprej simulirati dovolj iger, da lahko z zadostno verjetnostjo doloˇcimo, katero pod- drevo je tisto, ki je najbolj optimalno. Ko izraˇcunamo, katero poddrevo je optimalno, igramo zgolj ˇse to poddrevo. To pomeni, da verjetnost, da igramo to poddrevo, nastavimo na 1 in verjetnost za vsa ostala poddrevesa na 0.
Ta optimizacija, po zadostnem ˇstevilu iteracij, tako rekoˇc ’izraˇcuna’ drevo do te mere, da moramo na koncu namesto 612 vozliˇsˇc hraniti zgolj maksi- malno 12 vozliˇsˇc za posameznega sina korena drevesa. Te ravni ni mogoˇce preprosto doseˇci, ker je za to potrebno dovolj veliko ˇstevilo iteracij. Kljub tej optimizaciji bo zato na zaˇcetku prostorska kompleksnost vseeno ekspo- nentno naraˇsˇcala, dokler se ne bo rast upoˇcasnila in nato konˇcno zaˇcela sta- gnirati. Ko bomo simulirali dovolj iger in bomo lahko zaˇceli rezati drevesa, bo temu sledil padec v prostorski kompleksnosti. Prostorska kompleksnost skozi ˇstevilo iteracij je prikazana na spodnjem grafu.
4.3.4 Optimizacija Pythonove izrabe pomnilnika
Najveˇcja teˇzava pri optimizaciji je bilo ogromno ˇstevilo vozliˇsˇc. ˇCeprav po- samezno vozliˇsˇce ni porabilo veliko spomina, je njihova ogromna koliˇcina po-
30 Jan Urankar rabila veliko prostora. Atributi Pythonovih objektov so obiˇcajno shranjeni v slovarjih. Pri tako ogromnem ˇstevilu vozliˇsˇc slovarji zasedejo ogromno pro- stora. Temu se izognemo tako, da vnaprej doloˇcimo in s tem omejimo atribute razreda, saj Pythonu to omogoˇca shranjevanje v bolj kompaktni strukturi.
Poleg tega nam ta pristop omogoˇca, da lahko do atributov v vozliˇsˇcih dosto- pamo od 10 % do 20 % hitreje.
Poglavje 5
Izvedba poskusov
Poskuse smo izvajali na opremi Laboratorija za bioinformatiko na Fakulteti za raˇcunalniˇstvo in informatiko. Razlog je bil, da sprva uporabljen osebni raˇcunalnik ni bil dovolj zmogljiv, da bi lahko uˇcil agenta, ne da bi preveˇc poenostavil igro.
Prvi korak je bilo uˇcenje agenta. Agenta smo inicializirali in uˇcili s pomoˇcjo algoritma, ki smo ga ustvarili. Prvi poskus uˇcenja ni bil uspeˇsen, saj parametri za uˇcenje niso bili ustrezni. Doloˇcili smo, da naj agenta od- igrata 1000 iger za vsak par zaˇcetnih kart, ki jih imata. To je vodilo do prevelikega prilagajanja tej posamiˇcni kombinaciji kart. Nato smo ponovno nastavili parametre in zaˇceli uˇcenje od zaˇcetka.
Pri drugem poskusu uˇcenja smo zmanjˇsali ˇstevilo iger na 100 in ta poskus je bil uspeˇsen. Uˇcenje agenta s pravimi parametri je trajalo 25 dni.
Naslednji korak je bila pridobitev podatkov o igri, ki smo jih lahko nato analizirali. Najprej je bila potrebna pridobitev podatkov o igri ˇcloveka. Te podatke smo pridobili s spleta. Zatem smo potrebovali podatke o igrah, ki jih je igral naˇs agent. Generiranje iger je trajalo okoli 30 dni.
31
32 Jan Urankar
5.1 Pridobitev podatkov iger, kjer je igral ˇ clovek
Roˇcno beleˇzenje iger in potez igralcev je ˇcasovno potratno. Namesto tega je bila prvotna ideja strganje podatkov iz iger, ki se igrajo na spletu. Po krajˇsi analizi spletnih strani, kjer se igra poker, je bilo jasno, da bi bila to precej nelagodna naloga. Spletne strani niso ponujale zgodovine iger ali doloˇcenega API-ja, s katerim bi lahko zbirali podatke iger. Tudi igre v ˇzivo bi bilo teˇzko beleˇziti in treba bi bilo uporabljati veliko raˇcunalniˇskega vida, s katerim bi lahko brali stave in karte igralcev.
Po krajˇsi raziskavi smo ugotovili, da te spletne strani in aplikacije verje- tno namenoma oteˇzijo spremljanje in igranje iger s pomoˇcjo programov. S tem namreˇc poskusijo onemogoˇciti agente umetne inteligence, ki jih ljudje uporabljajo za igranje na strani.
Odkrili smo boljˇso alternativo za zbiranje podatkov o igri ˇcloveka. Odloˇcili smo se, da bomo najprej preiskali ˇze obstojeˇce podatkovne baze s podatki o ˇcloveˇski igri pokra. Naˇsli smo kar nekaj podatkovnih baz, najbolj set podat- kov pa smo dobili na spletni strani [5]. Podatkovna baza vsebuje okoli 50 tisoˇc No Limit Texas Holde’m iger, kar je dovolj za podrobno analizo.
5.2 Generiranje podatkov igre naˇ sega agenta
Igre naˇsega agenta smo generirali s pomoˇcjo Pythona. Najprej smo zagnali algoritem za uˇcenje, kjer so se agenti nauˇcili igre. Uˇcenje je trajalo 25 dni.
Zatem je sledilo ˇse generiranje iger. Igre smo generirali tako, da smo inicializirali dva agenta, ki sta igrala drug proti drugemu. Generiranje iger je trajalo okoli 14 dni in generirali smo okoli 1000 iger.
5.3 Analiza igre naˇ sega agenta in ˇ cloveka
V tem poskusu smo analizirali slog igre.
Za analizo igre smo napisali program, ki je analiziral veˇc podroˇcji igre agenta in ˇcloveka, da bi na temelju tega lahko ugotovili, kako se slogi igre
Diplomska naloga 33 razlikujejo.
ˇStevilo igranih iger Ali igralec igra igro ali ne, je ena izmed pomemb- nejˇsih statistik, ki kaˇze, kako dejaven je igralec v igri. To, da igralec igra igro, pomeni, da izenaˇci zaˇcetno stavo. Igralec, ki nima big blinda, lahko od igre odstopi, preden v igro poloˇzi kakrˇsno koli vsoto denarja. To naˇceloma naredi, ˇce mu dodeljeni karti ne ustrezata.
Ce igralec dobi visok par, na primer par asov ali kraljev, bo igralec sko-ˇ raj vedno igral. ˇCe igralec dobi zelo slabe karte, kot sta na primer 2 in 7 razliˇcne barve, ki je statistiˇcno najslabˇsa zaˇcetna kombinacija kart, bo igralec naˇceloma odstopil.
All in ’All in’ v pokru pomeni, da stavimo na mizo ves denar, ki ga imamo.
To se v pokru redko zgodi in velja kot izjemno agresivna poteza. Obiˇcajno to pomeni, da je igralec prepriˇcan, da ima boljˇse karte, ali pa se pretvarja in ˇzeli z all in-om prestraˇsiti nasprotnika, da ta nato odstopi. V analizi ocenjujemo, kako pogosto se zgodi all in.
Dokonˇcane igre Z dokonˇcano igro smo definirali igre, v katerih se zma- govalec odloˇci ˇsele takrat, ko se pokaˇzejo karte. To se v pokru dogaja v manjˇsem ˇstevilu primerov, saj v veˇcini iger igralci odstopijo prej, preden se pokaˇzejo karte. Analizirali smo, kakˇsen je deleˇz iger, kjer se igra odigra do konca.
Povpreˇcen deleˇz viˇsanja stav V tem delu smo ocenjevali, kako velik je obiˇcajno deleˇz viˇsanj v igri. Ocenjevali smo, kako velika je stava pri viˇsanju v razmerju z denarjem, ki je trenutno v igri oziroma kako visoke stave polagajo igralci v primerjavi z velikostjo pota.
Stave v posamezni fazi V tem delu smo ocenjevali, katera faza (preflop, flop, turn, river) je najdejavnejˇsa. Za vsako fazo posebej smo analizirali,
34 Jan Urankar koliko vsi igralci skupaj povpreˇcno stavijo in koliko dejansko stavijo. Anali- zirali smo igre z enakimi big in small blindi, tako da so ti podatki med seboj neposredno primerljivi.
5.4 Primerjava igre ˇ cloveka in agenta
Podatki o igrah, ki jih je igral ˇclovek, so veˇcinoma igre, v katerih je igralo od ˇstiri do devet igralcev, medtem ko naˇs agent igra variacijo pokra ’heads up’, pri ˇcemer igrata zgolj dva igralca. To niti ni kritiˇcna razlika, saj tudi pri igri ˇcloveka veˇcina igralcev odstopi takoj in niti ne igrajo igre. Kasneje, po flopu, naˇceloma ostanejo zgolj ˇse dva do trije igralci. To je teˇzava neskladnosti in vpliva na podatke, vendar verjetno ne bistveno.
Veˇcja neskladnost se pojavi zaradi moˇci kart. ˇCe igramo z veˇc igralci, obiˇcajno potrebujemo precej moˇcnejˇse karte, saj je poleg nas ˇse osem igralcev.
Statistiˇcno bomo tako imeli najboljˇse karte le okoli 12,5 % ˇcasa. ˇCe igro igrata zgolj dva igralca, potem bomo imeli boljˇse karte okoli 50 % ˇcasa.
Poslediˇcno je slog igre drugaˇcen. To pomeni, da je moˇc kombinacij, pri katerih se bodo igralci odloˇcili za igro, pri heads up precej viˇsji in bodo igrali agresivneje na slabˇse kombinacije, saj vedo, da je statistiˇcno precej bolj verjetno, da imajo najboljˇse karte za mizo preprosto zato, ker imajo pri heads up manj nasprotnikov.
Kljub temu primerjavo lahko naredimo, vendar moramo upoˇstevati, da bosta agenta verjetno igrala nekoliko agresivneje in nekoliko veˇc iger kot ˇclovek.
Igro agentov in ˇcloveka smo primerjali po metrikah, opisanih zgoraj. Re- zultati so presenetljivo pokazali precejˇsnje razlike v igri ˇcloveka in agentov.
5.4.1 Znaˇ cilnosti igre ˇ cloveka
Igralci so v povpreˇcju igrali vsako ˇcetrto igro in v okoli 6,5 % iger je eden od igralcev vloˇzil ’all in’.
Diplomska naloga 35
Slika 5.1: Znaˇcilnosti igre ˇcloveka
Pribliˇzno vsaka osma igra je bila odloˇcena tako, da sta vsaj dva igralca igrala vse ˇstiri faze igre, preflop, flop, turn, river, in na koncu pokazala karte, pri ˇcemer je bil zmagovalec tisti, ki je imel boljˇso kombinacijo kart. Ostalih sedem od osmih iger je bilo zakljuˇcenih tako, da so odstopili vsi z izjemo enega igralca, ki je nato dobil vloˇzeni denar v tisti igri.
Igralci so v povpreˇcju v preflopu stavili 11,66 USD, na flopu 7,32, na turnu 10,38 in na riverju 8,84 USD. Vidimo, da so koliˇcine stav naˇceloma precej enakomerno razporejene in ˇceprav je flop v povpreˇcju nekoliko dejavnejˇsi od drugih faz, ta ne izstopa preveˇc.
Povpreˇcno viˇsanje v igri je bilo okoli 130 %. Npr. ˇce je trenutno na mizi 10 EUR, je igralec, ki viˇsa, dal stavo 13 EUR.
Rezultati analize se skladajo s priˇcakovanji. Igralci, ki smo jih analizirali, so igrali po nekih standardnih smernicah igre pokra, ki so tudi danes prisotne v veˇcini iger.
36 Jan Urankar
5.4.2 Znaˇ cilnosti igre agenta
Slika 5.2: Znaˇcilnosti igre agenta
Izmed 900 simuliranih iger je agent igral vsako, kar pomeni, da je igral 100 % iger in v pribliˇzno vsaki tretji igri je eden izmed igralcev naredil ’all in’. Vidimo, da je agent igral precej agresivneje kot ˇclovek in vloˇzil ’all in’
skoraj ˇsestkrat bolj pogosto.
Agentovo agresivno igranje se prav tako vidi pri deleˇzu konˇcanih iger, pri ˇcemer sta agenta do konca odigrala zgolj 3 % iger, kar je veˇc kot polovico manj kot ljudje.
Prav tako je vzorec stavljenja precej drugaˇcen. Medtem ko so bile faze, glede na koliˇcino stavljenega denarja, pri ˇcloveku precej izenaˇcene, so pri agentih bolj neenakomerne. Najdejavnejˇsa faza pri agentih je bila flop, pri ˇcemer sta agenta v povpreˇcju na mizo poloˇzila 28 EUR. Po koliˇcini stavljenega denarja flopu sledi preflop, pri ˇcemer je bilo povpreˇcno stavljeno malo manj od 19 EUR. Na turnu sta agenta stavila v povpreˇcju okoli 8 EUR in na riverju nekoliko veˇc kot 1 EUR.
Povpreˇcna stava ob viˇsanju je bila okoli 516 % glede na pot, kar je okoli
Diplomska naloga 37 ˇstirikrat veˇc od ˇcloveka. Npr. ˇce je trenutno na mizi 10 EUR, je agent v povpreˇcju viˇsal za 51 EUR.
Ce bi agenta ˇˇ zeleli umestiti v eno izmed kategorij igralcev, bi agent spa- dal v kategorijo ’Loose-Agressive’, igralca, ki igra veliko iger in je hkrati pripravljen veliko tvegati ter se pretvarjati med igrami.
Pri tem zakljuˇcku moramo upoˇstevati, da pri agentih igra manj igralcev kot pri ljudeh, zato so razlike nekoliko pretirane. Ne glede na to ostaja sklep, da agent igra precej agresivneje in precej veˇc iger.
38 Jan Urankar
Poglavje 6 Zakljuˇ cek
Pri izdelavi diplomskega dela smo ugotovili, da je algoritem CFR odliˇcen in ima ogromen potencial pri reˇsevanju podobnih problemov in iger, pri ˇcemer nam vse informacije niso dostopne. Kljub temu je njegova velika prostorska kompleksnost velika ovira pri njegovi uporabi.
Naˇs agent se je uˇcil in nauˇcil tehnik, ki so smiselne za igro, ki jo igra.
Kljub temu se nismo ognili veliki prostorski in ˇcasovni kompleksnosti tega algoritma ter smo za njegov trening porabili veliko ˇcasa in dela. Osnovna razliˇcica algoritma, ki je uporabljena v tem diplomskem delu, je izˇsla leta 2007.
Od takrat so raziskovalci razvili nove in naprednejˇse uporabe algoritma CFR, ki so precej zmanjˇsali njegovo prostorsko in ˇcasovno zahtevnost. To so naˇceloma dosegli v kombinaciji z drugimi algoritmi. ˇCe bi namesto naˇsega osnovnega algoritma CFR uporabili naprednejˇse oblike CFR-algoritma, bi se agent lahko precej hitreje uˇcil in bi za izvedbo akcij potreboval manj virov.
Pri navadnem CFR za vsako moˇzno situacijo ustvarimo svoje stanje, zato je potrebna abstrakcija igre, kot je omejevanje ˇstevila akcij oziroma velikosti stav. Take poenostavitve lahko pomembno vplivajo na kakovost igre agenta.
Deep CFR to teˇzavo reˇsi s pomoˇcjo uporabe nevronskih mreˇz, kar precej zmanjˇsa prostorsko kompleksnost in je v veˇcini primerov enakovredno ali boljˇse od obiˇcajnega CFR-algoritma.
39
40 Jan Urankar V primeru, da bi naˇs algoritem dodelali v enega izmed naprednejˇsih al- goritmov, bi verjetno dobili rezultate hitreje in z manj dela.
Prav tako bi lahko poleg drugega algoritma spremenili naˇcin uˇcenja naˇsega agenta. Naˇs agent igra zelo agresivno, kar ni napaˇcno, vendar obstaja moˇznost, da bi lahko agent razvil boljˇso strategijo, ˇce bi imel na voljo veˇc ˇcasa za uˇcenje in moˇcnejˇse raˇcunalnike. ˇCe bi lahko ˇcas uˇcenja bistveno podaljˇsali, bi lahko ustvarili veˇc agentov in vsakemu izmed njih nastavili drugaˇcne parametre pri uˇcenju.
Na koncu bi nato primerjali agente med seboj, ki bi igrali drug proti drugemu in izbrali tistega, katerega strategija je bila v primerjavi z drugimi agenti najboljˇsa.
Uporaba podatkov z enakim ˇstevilom igralcev
Trenutni rezultati in ugotovitve naˇsega poskusa so deloma relevantni, saj obstaja nekolikˇsna neskladnost med igrami, ki jih je igral ˇclovek, in igrami, ki smo jih generirali z agenti.
Reˇsitev te teˇzave je preprosta, pridobiti bi morali zadostne koliˇcine podat- kov, ko ˇclovek igra heads up, ampak to na ˇzalost ni bilo izvedljivo. Verjeten razlog za to je, da ljudje naˇceloma raje igrajo poker z veˇc igralci, saj je potencial za nagrado veˇcji, kot ˇce igrajo zgolj z enim igralcem.
6.1 Moˇ zni alternativni pristopi
Obstaja veˇc moˇznosti za programiranje agentov v pokru, in to smo ˇze spo- znali, ko smo pisali o projektih, na katerih so delale druge ekipe na podroˇcju pokra. Tudi mi smo morali sprejeti nekaj odloˇcitev, kako graditi svojega agenta. Obstaja pa ˇse veˇc drugaˇcnih razliˇcic algoritma CFR in tudi drugih algoritmov, ki bi jih lahko izbrali za grajenje svojega agenta.
Diplomska naloga 41
6.1.1 Implementacija s slovarjem
Naˇsa razliˇcica algoritma uporablja drevesno strukturo, vendar je algoritem CFR moˇzno implementirati tudi s slovarjem. Implementacija s slovarjem ima svoje prednosti in slabosti.
Ce bi vsakiˇˇ c igrali zgolj eno igro in nato zamenjali sinove vozliˇsˇc, bi bila ta implementacija precej boljˇsa. V naˇsem primeru za vsak par zaˇcetnih sinov vozliˇsˇc generiramo 100 iger, kjer nam celoten sin korenskega vozliˇsˇca precej koristi, saj nam ni treba ob vsaki akciji ponovno nalagati vozliˇsˇc, ker so vozliˇsˇca ˇze naloˇzena v delovnem pomnilniku.
Ne moremo trditi, katera implementacija je v sploˇsnem boljˇsa, saj nismo implementirali razliˇcice s slovarjem, vendar sta obe dobri moˇznosti.
6.1.2 Veˇ cje upoˇ stevanje zgodovine
Algoritem CFR zgolj upoˇsteva situacijo za posamezno igro in kaj je stati- stiˇcno najboljˇsa akcija v tisti igri. Slabost je, da ne upoˇsteva zgodovine iger za tisto mizo. Igralec, ki igra v ˇzivo, lahko druge igralce uvrsti v neke kate- gorije. Lahko doloˇci, kateri igralci so konservativni, kateri blefirajo, kateri so izjemno agresivni in glede na njihov slog igre prilagodi svojo igro.
Ce je neki igralec vloˇˇ zil all in, in smo v dvomih, ali bi izenaˇcili ali odstopili, lahko upoˇstevamo njegov slog igre. ˇCe je to igralec, ki malo igra in je precej konservativen ter igra obiˇcajno le, ko ima dobre karte, bomo dobro premislili, ali bomo izenaˇcili. ˇCe je ta igralec zelo agresiven in pogosto blefira, se bomo laˇzje odloˇcili za izenaˇcenje stave, saj obstaja veˇcja moˇznost, da nasprotnik nima dobre kombinacije.
Reˇsitev za upoˇstevanje tega bi morala biti precej korenita. Morali bi izbrati drugaˇcen algoritem, po moˇznosti tak, ki ni poˇzreˇsen. Morda bi zado- stovalo, ˇce bi izbrali doloˇceno nadgradnjo oziroma optimizacijo trenutnega CFR-algoritma, ki bi poleg statistiˇcno najboljˇse roke uporabljal tudi zgodo- vino igre.
42 Jan Urankar
Literatura
[1] Blackjack basic strategy [Online]. https://www.blackjackclassroom.com/blackjack- basic-strategy-charts.
[2] Michael Bowling Carmelo Piccione Martin Zinkevich, Michael Johanson.
Regret minimization in games with incomplete information. NeurIPS, 25(3):1–8, 2008.
[3] Marc Lanctot profile imageMarc Lanctot Richard G Gibson profile ima- geRichard Gibson Michael H Bowling profile imageMichael Bowling Mi- chael Johanson, Nolan Bard profile imageNolan Bard. Efficient nash equi- librium approximation through monte carlo counterfactual regret minimi- zation. International Conference on Autonomous Agents and Multiagent Systems, 2(12):837–846, 2012.
[4] Tuomas Sandholm Noam Brown. Superhuman ai for multiplayer poker.
Science, 365(6456):885–890, 2019.
[5] Poker Hold’Em Games [Online]. https://www.kaggle.com/smeilz/poker- holdem-games.
[6] Poker/Personality [Online]. https://en.wikibooks.org/wiki/poker/personality.
[7] Understanding Different Types Of Poker Players [Online].
https://www.cardplayer.com/poker-news/24202-understanding- different-types-of-poker-players.
43
44 Jan Urankar
[8] How to Play Texas Hold’em Poker [Online].
https://www.pokernews.com/poker-rules/texas-holdem.htm.
[9] Marc Lanctot Todd W. Neller. An introduction to counterfactual regret minimization. Technical report, Gettysburg college, 2013.
