Algoritam AlphaZero nudi elegantan pristup rješavanju problema igranja igara na ploči, gdje su pravila igre fiksirana, aktualni položaj u igri je u potpunosti poznat te postoji protivnik, kojemu je primarni cilj spriječiti igrača da pobijedi u igri. Postojanje protivnika upravo je ono što takve igre čini kompliciranima—pravila igre obično su dosta jednostavna i kompaktna, ali je otežavajući faktor prisutnost protivnika s nepoznatom strategijom, koji nastoji pobijediti u igri. Preciznije, algoritam AlphaZero pogodan je za tzv. kombinatorne igre za dva igrača, a takve igre imaju sljedeća svojstva:

Kombinatorne igre se tipično modeliraju pomoću stabla, poput onog prikazanog na slici 1. Vrhovi (čvorovi) u stablu označavaju različita stanja tijekom igre. Stanje u potpunosti opisuje neki trenutak u igri: primjerice, položaj svih figura na ploči u šahu, zajedno s informacijom o tome koji je igrač na redu. Ako analiziramo situaciju u nekom danom trenutku igre, onda se u korijenu stabla nalazi opis stanja u tom trenutku. Djeca nekog vrha predstavljaju sva ona stanja do kojih se može doći jednim potezom u igri, a završna stanja u igri (ona koja predstavljaju kraj igre) su listovi u stablu. Svakom završnom stanju je pridružena nagrada koju pojedini igrač dobije ako igra završi u tom stanju; kao što smo naveli gore, suma tih nagrada za svako stanje je nula.

Prirodno pitanje koje si svaki igrač postavlja tijekom igre jest: koja je najveća moguća nagrada koju mogu ostvariti svojim potezima iz stanja s u kojem se igra trenutno nalazi, bez obzira na to kako igra drugi igrač? Tu najveću moguću nagradu zovemo vrijednost stanja s za danog igrača i, te označavamo sa v_{i}(s). Lako se, indukcijskim argumentom počevši od listova stabla, vidi da za svako stanje s vrijedi v_{\operatorname{\textbf{1}}}(s) = -v_{\operatorname{\textbf{2}}}(s). Označimo sa \operatorname{\mathcal{A}}(s) skup dozvoljenih poteza (akcija) koji se smiju napraviti u stanju s, a sa \operatorname{\mathcal{N}}(s) = \lbrace \operatorname{\mathsf{next}}(s, a) : a \in \operatorname{\mathcal{A}}(s) \rbrace skup svih stanja u koja igra može prijeći nakon stanja s. Promotrimo situaciju u kojoj je igrač \operatorname{\textbf{1}} na potezu u igri koja je u stanju s. Njegov optimalni potez vodi ga u stanje u kojem je njegova nagrada najveća moguća, odnosno, vrijedi:

No, na potezu u stanju \tilde{s} je igrač {\operatorname{\textbf{2}}}. Iz njegove perspektive,

pa uvrštavajući u (1) dobivamo

Iz ove jednakosti slijedi rekurzivni algoritam minimax koji, barem u teoriji, može pronaći pobjedničku strategiju ako ona postoji. Algoritam generira stablo igre, pri čemu korijen opisuje trenutno stanje s u igri, te izračunava vrijednost stanja za svaki čvor koristeći vrijednosti stanja njegove djece i formulu (2). Pretpostavimo, bez smanjenja općenitosti, da je u stanju s na potezu igrač \operatorname{\textbf{1}}. Optimalna akcija koju on može napraviti je ona koja vodi do djeteta korijena maksimalne vrijednosti. Problem s ovim pristupom jest taj što se stablo svake imalo složenije igre izuzetno brzo grana—ako u svakom stanju možemo odabrati između n akcija, onda analiza prvih \ell poteza u igri vodi na stablo sa \operatorname{\mathcal{O}}(n^{\ell}) čvorova. To znači da računalo u praksi ne može provesti ovaj algoritam u razumnom vremenu, nego je nužno ograničiti dubinu stabla; u čvorovima na najvećoj dubini treba nekom heuristikom pronaći aproksimaciju vrijednosti pripadnog stanja. Time dobivamo Algoritam 1 koji nazivamo minimax\ell}, gdje je \ell ta unaprijed zadana najveća dubina. Za čvor u smo u algoritmu sa \operatorname{\mathsf{state}}(u) označili pripadno stanje, a sa \operatorname{\mathsf{value}}(u) \approx v_{\operatorname{\textbf{1}}}(\operatorname{\mathsf{state}}(u)) aproksimaciju vrijednosti tog stanja za igrača \operatorname{\textbf{1}} koji je na potezu u korijenu. Računalne programe koji vuku poteze slijedeći strategiju opisanu nekim algoritmom još nazivamo i agentima.

Kako odrediti aproksimativnu vrijednost nekog stanja? Jedna mogućnost je napraviti jednu ili više simulacija igre od tog stanja nadalje, koristeći pritom neku trivijalnu strategiju (na primjer, u nedostatku bolje ideje, posve slučajno odabirati poteze), te vratiti prosječnu nagradu koju je u svim simulacijama ostvario igrač \operatorname{\textbf{1}}. Alternativno, za konkretnu igru moguće je procijeniti situaciju u kojoj se nalazi igrač: na primjer, u šahu aproksimativna vrijednost stanja bi mogla biti 0.9 ako igrač \operatorname{\textbf{1}} svojim potezom može zaprijetiti šahom, a -0.9 ako je u takvoj situaciji protivnik i slično. Ove ideje navodimo samo za ilustraciju; u praksi se, naravno, koriste nešto složenije aproksimacije.

Pretraživanje stabla Monte Carlo metodom (engl. Monte Carlo Tree Search, MCTS) je alternativna metoda rješavanja problema s prevelikim brojem čvorova u stablu igre. Promotrimo ponovno situaciju u kojoj trebamo odabrati akciju za igrača \operatorname{\textbf{1}} na potezu u stanju s. Umjesto da napravi potpuno stablo igre u čijem korijenu je stanje s, MCTS nastoji usmjeriti izgradnju stabla tako da otkriva stanja za koje je izglednije da imaju veću vrijednost za igrača \operatorname{\textbf{1}}. To se postiže formiranjem vjerojatnosnog modela igre: MCST želi odrediti broj \pi(a) koji predstavlja vjerojatnost da je a \in \operatorname{\mathcal{A}}(s) optimalna akcija za igrača \operatorname{\textbf{1}}. Tu vjerojatnost će aproksimirati statistikom dobivenom simulacijama velikog broja partija koje sve započinju stanjem s. Tijekom simulacija se postupno gradi stablo igre, a akcije u simulacijama se biraju na dva načina, politikom stabla (eng. tree policy) i zadanom politikom (eng. default policy):

U svakom čvoru u MCTS stabla čuvamo sljedeće informacije: N(u) je broj simulacija koje su prošle kroz čvor u (tj. simulacija koje su u nekom trenutku bile u stanju iz tog čvora), a Q(u) je suma svih (aproksimacija) vrijednosti stanja \operatorname{\mathsf{state}}(u) u svim simulacijama za onog igrača čiji potez vodi na to stanje. U svakoj simulaciji ove se vrijednosti osvježe za sva stanja kroz koje simulirana igra prođe. Pseudokod osnovnog MCTS algoritma je dan u Algoritmu 2.

Preostaje još pitanje kako implementirati politiku stabla. Jasno je da su, iz perspektive igrača koji je na potezu u stanju \operatorname{\mathsf{state}}(u), perspektivnija ona djeca c tog čvora za koja je u ranijim simulacijama ostvario veću prosječnu nagradu \frac{Q(c)}{N(c)}. S druge strane, nužno je povremeno odigrati akciju koja ranije nije bila često ili uopće igrana kako ne bismo propustili otkriti neki novi, obećavajući smjer u igri. Taj balans između iskorištavanja postojeće statistike za maksimizaciju nagrade i istraživanja novih akcija postiže se politikom tzv. gornje pouzdane ograde za stabla (eng. UCT, Upper Confidence Bound for trees): ako sa \operatorname{\mathcal{C}}(u) označimo skup djece čvora u, onda politika stabla UCT odabire onu akciju iz čvora u koja vodi u dijete

Akcije koje su se u prethodnim simulacijama pokazale boljima će imati veći prvi pribrojnik, a akcije koje ranije nisu bile često birane će imati veći drugi pribrojnik; tipična vrijednost koeficijenta \alpha je \sqrt{2}. Teorijsko opravdanje formule (3) može se pronaći u člancima [??]ctssurvey,Kocsis06banditbased,Kocsis2006ImprovedMS}.

Nakon što je napravljen dovoljan broj simulacija, igrač \operatorname{\textbf{1}} treba odabrati akciju dozvoljenu u stanju zapisanom u korijenu MCTS stabla. To se najčešće obavlja na jedan od sljedećih načina:

Nakon što i protivnički igrač odigra svoj potez, igrač \operatorname{\textbf{1}} bi mogao graditi posve novo MCTS stablo s korijenom u novonastaloj situaciji. Bolji pristup je zadržati odgovarajuće podstablo postojećeg MCTS stabla jer ono već sadrži dio statistike za simulacije iz prethodnog stanja igre.

Najizraženiji problem koji preostaje u algoritmu opisanom u prethodnoj cjelini je definicija smislene zadane politike, odnosno, što bolje aproksimacije vrijednosti stanja za listove do sada izgrađenog MCTS stabla. AlphaZero taj problem rješava korištenjem duboke neuronske mreže f_{\theta}. Implementacija iz [13] sugerira da neuronska mreža na ulazu dobije kodirano stanje s, a da joj izlaz, uz aproksimaciju \hat{v} vrijednosti tog stanja bude i tzv. vektor politike (eng. policy vector) \hat{\pi}:

Vektor politike svakoj akciji a pridružuje vjerojatnost \hat{\pi}(a) odigravanja te akcije u stanju s; uočimo analogiju ove ideje s motivacijom za algoritam MCTS. Neuronska mreža izgrađuje svoj vjerojatnosni model igre temeljem vjerojatnosti \hat{\pi}, dok istovremeno MCTS algoritam izgrađuje svoj model temeljem vjerojatnosti \pi. Cilj treniranja neuronske mreže je da, osim dobivanja što realnijih aproksimacija vrijednosti stanja koje odgovaraju stvarnim ishodima igara, izgradi vjerojatnosni model koji se podudara s onim dobivenim MCTS stablom.

Opišimo sada proces treniranja neuronske mreže, čiji pseudokod je prikazan i u Algoritmu 3. Težine neuronske mreže na početku se inicijaliziraju na nasumične vrijednosti \theta_{0}. U svakoj iteraciji treniranja program igra nekoliko igara protiv samoga sebe, od kojih se pojedina igra sastoji od niza stanja s_{1}, \ldots, s_{T}. Za svako stanje s_{t}, bez obzira na to je li na potezu igrač \operatorname{\textbf{1}} ili \operatorname{\textbf{2}}, poziva se algoritam pretraživanja stabla Monte Carlo metodom sa s_{t} u korijenu stabla. Formula (3) je pri tome malo prilagođena da uzima u obzir i vektor politike neuronske mreže: u svakom čvoru c se dodatno pamti i vrijednost P(c):=\hat{\pi}(a), gdje je a akcija koja nas je dovela u taj čvor iz njegovog roditelja. Ova vrijednost se zapiše u čvor prilikom njegovog stvaranja u Algoritmu 2, tj. nakon poziva funkcije zadana_politika koja sada evaluira neuronsku mrežu i odmah se, uz N(c)=0, Q(c)=0 inicijalizira i P(c) za svako dijete c čvora u. Nova politika stabla PUCT (eng. Polynomial UCT) glasi:

Ovdje su c_{\text{base}} i c_{\text{init}} konstante; vidimo da je izbor akcije koja ranije nije bila često birana dodatno ponderiran s vjerojatnosti koju joj je pridružila neuronska mreža. Po izgradnji stabla, MCST algoritam vraća procjenu vjerojatnosti odigravanja pojedinih akcija iz korijena stabla (označimo ga s k) u obliku vektora \pi_{t},

Ovdje je \tau tzv. parametar temperature koji se u prvih nekoliko (na primjer, 10) poteza svake igre postavlja na 1, a zatim se uzima \tau \to 0. U stanju s_{t} program će slučajno odabrati neku akciju a s vjerojatnosti \pi_{t}(a), te ju odigrati—uočimo da izbor parametra temperature ima za posljedicu to da je u početku igre vjerojatnost odabira akcije proporcionalna posjećenosti djeteta korijena MCTS stabla, dok se kasnije uvijek odabire najposjećenije (robusno) dijete. Pripadno podstablo MCTS stabla izgrađenog za stanje s_{t} zadržava se i u narednom koraku.

Igra završava u koraku T, kada se dosegne završno stanje s_{T}, a kojemu pripada nagrada r_{T}. Iz svakog pojedinog koraka 1\le t \lt T pohranjuje se uređena trojka (s_{t},\pi_{t},v_{t}), gdje je v_{t} = \pm r_{T} nagrada iz perspektive igrača koji igru dovodi u stanje s_{t}. Po završetku iteracije i, novi parametri neuronske mreže \theta_{i} dobivaju se treniranjem neuronske mreže na temelju primjera za učenje oblika \left(s, \pi, v\right), dobivenih uzimanjem uzorka iz diskretne uniformne distribucije na skupu uređenih trojki (s_{t}, \pi_{t}, v_{t}) iz svih koraka t svih odigranih igara u iteraciji i. Ažurirani parametri \theta_{i} potom se koriste u igrama algoritma samog protiv sebe u narednoj iteraciji (odnosno, kao zadana politika u narednoj iteraciji).

Samo treniranje na temelju primjera \left(s, \pi, v\right) provodi se ovako: neuronska mreža se evaluira za ulaz s, te vraća (\hat{v}, \hat{\pi}) = f_{\theta}(s), a njezini parametri \theta se ažuriraju s ciljem minimizacije funkcije greške (eng. loss function)

Analizirajmo malo gornji izraz. Primjer \left(s, \pi, v\right) predstavlja jedan ishod odigrane igre koja je prošla kroz stanje s: ona je završila nagradom v, a MCTS stablo je procijenilo vjerojatnosti akcija vektorom \pi. S druge strane, neuronska mreža će aproksimirati vrijednost tog stanja sa \hat{v}, a vjerojatnosti vektorom \hat{\pi}. Minimizacijom prvog pribrojnika u (6) nastojimo prilagoditi parametre mreže tako da njezina aproksimacija vrijednosti stanja bude što bliža stvarnoj nagradi v. Drugi pribrojnik mjeri sličnost vjerojatnosnih distribucija \pi i \hat{\pi} pomoću tzv. cross-entropy funkcije

koja postiže minimum (za fiksni \pi) kada je \hat{\pi} = \pi, pa je cilj minimizacije funkcije L postići da neuronska mreža daje što sličniju prognozu vjerojatnosti igranja pojedinih akcija kao što ih daje MCTS stablo. Treći pribrojnik u (6) je tzv. regularizacijski član—minimizacija norme vektora parametara \theta je standardna tehnika kojom se smanjuje opasnost od tzv. overfittinga, tj. pojave da mreža daje ispravna predviđanja za podatke kojima ju treniramo, a loša za podatke koje ne vidi u procesu treninga. Optimizacijski algoritam za minimizaciju izraza (6) koristi gradijentni spust. Po završetku procesa treniranja, dobivenu neuronsku mrežu možemo pohraniti, a MCTS algoritam koji ju koristi kao zadanu politiku zatim primjenjivati kao AlphaZero agenta.

Opisani proces učenja ilustriran je slikom 5. Na slici 5 prikazan je proces igranja igara algoritma samog protiv sebe, odnosno prolazak kroz stanja s_{1},\ldots,s_{T}, u svakom od kojih se poziva MCTS algoritam, a koji pak koristi aktualnu neuronsku mrežu f_{\theta} kao zadanu politiku. Ilustrirani su odabiri akcija na temelju vjerojatnosti proizašlih iz pretraživanja stabla Monte Carlo metodom (odabir akcije a_{t}\sim\pi_{t} u koraku t) te pridjeljivanje nagrade završnom stanju s_{T}, na temelju koje se računaju ishodi za pojedine trenutke. Na slici 5 ilustrirano je treniranje neuronske mreže na temelju primjera za učenje, od kojih se svaki sastoji od reprezentacije stanja kao ulazne varijable te vjerojatnosti proizašlih iz pretraživanja i ishoda igre za trenutak koji odgovara ulaznom stanju kao ciljnim varijablama. Neuronska mreža ulazno stanje transformira pomoću brojnih konvolucijskih slojeva s parametrima \theta te vraća vektor \hat{\pi}_{t} i skalar \hat{v}_{t}. Arhitektura same neuronske mreže je također važna za uspjeh opisanog algoritma; ideja je slična za većinu igara na ploči pa ćemo ju u idućoj cjelini opisati za igru Connect Four.

Za ilustraciju algoritma AlphaZero, napravili smo implementaciju za igru Connect Four pomoću programskog jezika Python i dodatnih biblioteka za njega. Vjerujemo da su čitatelji upoznati s ovom igrom, no opišimo ju ukratko. Connect Four je društvena igra za dva igrača, u kojoj je svakome od njih dodijeljena jedna boja (žuta ili crvena) te u kojoj oni naizmjence ubacuju diskove pripadajuće boje u rešetku, obično sa šest redaka i sedam stupaca. Kada dođe red na pojedinog igrača, on mora ubaciti disk svoje boje u neki od stupaca rešetke s barem jednim praznim mjestom. Kada jedan od igrača ubaci disk u rešetku, disk upada u nju na najniže slobodno mjesto—diskovi ubačeni u isti stupac slažu se vertikalno jedan na drugog. Cilj pojedinog igrača je biti prvi koji će formirati vodoravni, okomiti ili dijagonalni niz od četiri diska svoje boje.

Igru Connect Four intuitivno bismo mogli okarakterizirati kao jednostavnu—pogotovo ako ju promatramo u odnosu na kompleksne igre poput igre Go. Međutim, ukupan broj različitih stanja igre, prema [1], iznosi 4 531 985 219 092\approx 4.5\cdot 10^{12}, što predstavlja izazov računalima u smislu rješavanja igre brute-force metodama poput algoritma minimax, odnosno sistematičnim pretraživanjem svih mogućnosti. Upravo zbog neposrednosti svojih pravila, jednostavnosti, koja se ogleda u manjim (u odnosu na npr. Go) zahtjevima na resurse prilikom implementacije AlphaZero algoritma za njeno savladavanje, popularnosti, ali ujedno i netrivijalnosti, igra Connect Four dobar je kandidat za demonstraciju mogućnosti AlphaZero metode. Naša implementacija je izvedena po uzoru na [9, Poglavlje 23], a koristili smo biblioteku Keras [4] te Tensorflow [2]. Keras je programsko sučelje (API) za duboko strojno učenje napisan u programskom jeziku Python, koji sadrži implementacije brojnih “građevnih blokova” neuronskih mreža, poput slojeva i aktivacijskih funkcija, te raznovrsnih često upotrebljavanih optimizacijskih algoritama.

Arhitektura neuronske mreže za algoritam AlphaZero je skicirana na slici 9. Ulazni sloj reprezentira stanje u igri kao tenzor dimenzije (2, 6, 7), odnosno, dvije matrice dimenzije ploče za igru (6 \times 7). Svaki element tenzora je 0 ili 1: na mjestu (0, i, j) piše 1 ako i samo ako igrač na potezu ima svoj žeton na mjestu (i, j) ploče za igru, a na mjestu (1, i, j) piše 1 ako i samo ako igrač koji nije na potezu ima svoj žeton na mjestu (i, j) ploče za igru. Takva reprezentacija stanja omogućuje invarijantnost na igrača koji u stanju povlači potez, odnosno, omogućava da neuronska mreža stanje analizira uvijek iz perspektive igrača koji u njemu odlučuje o akciji. Složenije igre, poput šaha, imale bi po jedan sloj za svaku vrstu figure (top, pješak, \dots) svake boje, te dodatne slojeve za specijalna stanja (na primjer, sloj pun jedinica ako je igrač na potezu napravio rokadu, a nula ako nije i slično). Nakon ulaznog sloja neuronske mreže slijede skriveni slojevi: prvi je konvolucijski sa 64 filtera, a zatim slijede 4 identična rezidualna bloka. Svaki blok se sastoji od po dva konvolucijska sloja sa 64 filtera, čiji izlaz se zbraja s ulazom u taj blok. Nakon toga se mreža račva u dvije grane: value head, čiji izlaz će biti \hat{v}, te policy head, čiji izlaz će biti \hat{\pi}. Ranije verzije algoritma AlphaZero su imale odvojene neuronske mreže za \hat{v} i \hat{\pi}, no pokazalo se boljim i efikasnijim imati samo jednu mrežu—ideja je logiku igre pohraniti u slojevima prije grananja i nema potrebe te informacije dva puta odvojeno trenirati. Kao funkciju aktivacije u cijeloj mreži koristimo LeakyReLU, a nakon svakog konvolucijskog sloja se radi normalizacija batch-a (treniranje se provodi odjednom za više primjera (s, \pi, v) koje zajednički nazivamo batch). Za dodatne informacije oko raznih tipova slojeva, aktivicijskih funkcija, kao i ostalih bitnih odluka koje treba donijeti kod dizajna neuronskih mreža čitatelja upućujemo na izvrsnu knjigu [6].

 

Slika 9: Rezidualna konvolucijska neuronska mreža za igru Connect4. Svaki sloj je opisan nazivom koji mu je dodijelila biblioteka Keras (na primjer, conv2d_11), tipom sloja (na primjer, Conv2D za 2D-konvolucijski sloj), te dimenzijama ulaznog i izlaznog tenzora (na primjer, (?, 2, 6, 7) za tenzor reda 4 čija je prva dimenzija proizvoljna (veličina batcha), a preostale su redom 2, 6 i 7). Niz slojeva unutar iscrtkanog pravokutnika ponavlja se 4 puta.

Proces treniranja izvršavan je na računalnom klasteru Isabella smještenom u Sveučilišnom računskom centru Sveučilišta u Zagrebu (SRCE). Isabella se sastoji od 135 računalnih čvorova, koji sadrže 3100 procesorskih jezgri i 12 grafičkih procesora, te je zajednički resurs svih znanstvenika u Hrvatskoj. Svaki proces učenja izvodili smo samo na jednom specijaliziranom čvoru tipa Dell EMC PowerEdge C4140, pomoću jednog od četiri dostupna grafička procesora NVIDIA Tesla V100-SXM2-16GB. Program je izvršavan nekoliko dana (oko 100 sati), a tijekom izvršavanja obavljeno je 150 iteracija algoritma.

Tijekom učenja težine modela pohranjuju se svaki put kad se neuronska mreža dobivena treniranjem unutar pojedine iteracije pokaže boljom od najuspješnije neuronske mreže. Dvije mreže, odnosno, pripadne agente, uspoređujemo tako da odigraju jedna protiv druge određen broj igara, a novu mrežu proglašavamo boljom ako pobijedi dosad najbolju mrežu u 55% tih igara. Na taj način smo nakon 150 iteracija dobili niz od ukupno 57 neuronskih mreža (i pridruženih agenata) stvorenih u različitim trenucima učenja, koji stoga imaju različitu uspješnost u igranju igre. Očekujemo da su agenti čije su neuronske mreže nastale u kasnijim trenucima učenja uspješniji od onih kojima odgovaraju ranije neuronske mreže.

Napredak tijekom učenja praćen je mjerenjem uspješnosti pojedinih agenata u igrama protiv sljedećih algoritama za igranje igre Connect Four:

Slika 10 prikazuje napredak u uspješnosti naših agenata naspram algoritma minimax-3. Ovdje održavamo “turnir” u kojemu svaka pojedina verzija agenta (odnosno, svaka pojedina verzija neuronske mreže—na osi apscise) igra 50 igara protiv minimax agenta. Uspješnost mjerimo omjerom broja pobjeda pojedinog našeg agenta i ukupnog broja odigranih igara—taj omjer je prikazan na osi ordinate slike 10. Kako bismo bolje vizualizirali i naglasili dugoročne trendove te “izgladili” kratkoročne fluktuacije, na slici 10 prikazujemo takozvane pokretne prosjeke (engl. moving average) udjela pobjeda. Za svaku verziju neuronske mreže (osim prvih pet) računamo srednju vrijednost mjera uspješnosti pridruženih njoj te pet prethodnih verzija (za prvih pet verzija računamo srednju vrijednost udjela pobjeda te i svih prethodnih neuronskih mreža). Na toj slici možemo vidjeti da zaista postoji trend povećanja udjela pobjeda pojedinih agenata, odnosno da agenti postaju sve uspješniji u igrama protiv minimax agenta. Najuspješniji agenti, kojima odgovaraju neke od najkasnijih verzija neuronskih mreža, pobjeđuju gotovo u svakoj odigranoj igri. Također, možemo uočiti veliku razliku između uspješnosti agenata kojima odgovaraju prve verzije neuronskih mreža te onih kojima odgovaraju posljednje: dok su omjeri pobjeda prva tri agenta (onih kojima odgovaraju prve tri verzije neuronske mreže) i ukupnog broja igara manji ili približno jednaki 0.3, ti su omjeri za agente kojima odgovaraju neke od najkasnijih verzija neuronskih mreža ponekad veći i od 0.9.

a: Uspješnost pojedinih AlphaZero agenata protiv algoritma minimax-3.

 

b: Pokretni prosjeci uspješnosti pojedinih AlphaZero agenata protiv algoritma minimax-3.

Slika 10: Turniri AlphaZero agenata protiv algoritma minimax-3.

Napredak tijekom učenja utvrđujemo i promatranjem rezultata igara u kojima suprotstavljamo sve verzije AlphaZero agenata jedne protiv drugih. Održavamo “turnir” u kojemu svaki AlphaZero agent igra 2 igre protiv svakog drugog. Sada svakom agentu za svaku pobjedu dajemo jedan bod, a za svaki poraz oduzimamo jedan bod. Budući da imamo ukupno 57 AlphaZero agenata, maksimalan broj bodova koji je moguće ostvariti je 112, a minimalan -112. Na slici 13 možemo uočiti da prve dvije verzije ostvaruju manje od -80 bodova, dok posljednje dvije ostvaruju oko 60. Dakle, razlika u uspješnosti u kontekstu ove metrike može se kvantificirati vrijednošću od oko 140 bodova. Ponovno, radi boljeg uočavanja dugoročnih trendova na slici 13 prikazujemo pokretne prosjeke brojeva bodova pojedinih agenata. Očito, broj ostvarenih bodova raste kako treniranje odmiče.

a: Brojevi bodova pojedinih AlphaZero agenata u igrama protiv svih drugih.

b: Pokretni prosjeci brojeva bodova pojedinih AlphaZero agenata u igrama protiv svih drugih.

Slika 13: Turniri u kojima sudjeluju sve varijante AlphaZero agenata.

Konačno, uspješnost raznih agenata za igru Connect Four uspoređujemo ispunjavanjem tablice 1 na sljedeći način. Svaki od 7 odabranih algoritama odigrao je turnir od 50 igara sa svakim od preostalih 6. U pripadnom retku tablice piše koliko pobjeda je taj agent ostvario protiv agenta iz odgovarajućeg stupca. Dok agenta s pridruženom prvom verzijom neuronske mreže nadmoćno pobjeđuju i minimax-3 i minimax-4, agent kojemu pripada posljednja verzija neuronske mreže pobjeđuje u čak 42 igre protiv minimax-4. Zanimljivo je uočiti i trend napretka algoritama minimax-\ell s rastućim \ell; no već za \ell=5 vrijeme njihovo izvršavanja postaje preveliko. Također, ponovno možemo uočiti sličan trend kakav su pokazale slike 13 i 13, odnosno, da se agenti kojima su pridružene kasnije verzije neuronskih mreža pokazuju uspješnijima u igrama protiv agenata s pripadnim ranijim verzijama.

Tablica 1: Tablica ostvarenih brojeva pobjeda pojedinih agenata u igrama protiv svih ostalih.

 

U ovom članku smo opisali arhitekturu algoritma AlphaZero, koja je svojim spojem Monte Carlo stabla pretraživanja i duboke neuronske mreže donijela revoluciju u sposobnosti umjetne inteligencije za igranje kombinatornih igara. Iako je igra Connect Four na kojoj smo ilustrirali ovaj algoritam jednostavna u usporedbi s šahom ili igrom Go, a računalni hardver na kojem je izvršeno treniranje za red veličine slabiji od onog pomoću kojeg je DeepMind [14, 12] trenirao svoje algoritme za šah i Go, osnovna ideja algoritma, kao i njegova implementacija je posve ista—i primjenjiva za praktički bilo koju kombinatornu igru. Jedina informacija koju AlphaZero algoritmi dobivaju jesu pravila igre, odnosno, popis dozvoljenih akcija u danom trenutku. Idući korak bi bilo uklanjanje i te informacije, te davanje potpune slobode algoritmu da istraživanjem otkrije i njih te ovlada okruženjem čija dinamika mu je posve nepoznata: algoritam MuZero [11]. {10}