Két magyar kutatónak is jelentős szerepe volt abban, hogy 10 évvel ezelőtt a gép legyőzte az embert góban

Tíz éve, hogy a mesterséges intelligencia történetében váratlanul korai, döntő jelentőségű áttörés született, amire annak idején nem sokan számítottak – legalább tíz évvel későbbre várták ezt az áttörést. Ez az esemény jól szimbolizálja a ma is zajló AI-forradalmat, amelyet nemcsak az állandó meglepetések jellemeznek, de az is, hogy ma már természetesnek vesszük, hogy az adat a meghajtó üzemanyag, és megfelelő számítási kapacitással az adatokból olyan összefüggések is feltárhatók a gépi tanulás segítségével, amelyekre olykor még az ember sem képes, így a gépek egyre több területen kezdik meghaladni az emberi képességeket.

De mi is történt tíz éve?

2015. október 5. és 9. között a DeepMind által kifejlesztett AlphaGo, pontosabban annak az elosztott számítási kapacitást használó verziója, amely abban az időben 1202 központi processzort (CPU-t) és 176 grafikus processzort (GPU-t) használt, 5-0-ra legyőzte Fan Huj kínai származású 2 danos profi Európa-bajnok gojátékost. Ez volt az első alkalom, hogy egy számítógépes goprogram profi játékos ellen nyert előnykő nélkül, teljes méretű (19×19 mezős) táblán. A hír nyilvánosságra hozásával 2016. január 27-ig vártak, hogy az egybeessen az algoritmust közzétevő Nature-cikk megjelenésével.

Az esemény jelentős mérföldkő volt a gépi tanulás fejlődésében, mivel a go rendkívül komplex játék: a játszható állások száma 10^170, ami több, mint a megfigyelhető világegyetemben lévő atomok száma (10^80). Ellentétben az IBM Deep Blue-jának teljesítményével, ami 1997-ben sakkban legyőzte Garri Kaszparovot, az akkori világbajnokot, itt nem volt elég az, hogy a gép nagyon gyors legyen, mert a Föld összes számítógépe több millió év alatt sem boldogulna még az értelmesnek tűnő lehetőségek számbavételével sem. A megoldásban a gépi tanulást kellett ötvözni egy okos keresési algoritmussal, és kevesen tudják, de ez utóbbi hozzájárulás két magyar kutatótól származik. Kocsis Levente és Szepesvári Csaba ugyanis az általuk kitalált UCT algoritmussal nagy mértékben hozzájárultak ahhoz, hogy a goalgoritmusok, köztük az AlphaGo, robbanásszerű fejlődésnek indulhattak annak idején.

A magyar szál

A UCT algoritmus (ami az Upper Confidence bounds applied to Trees rövidítése) tulajdonképpen arra a kérdésre ad okos választ, hogy miként döntsön egy gép akkor, amikor rengeteg lehetősége van, de nincs ideje mindet kipróbálni. Az önálló tanulás során ugyanis az egyik legfontosabb kérdés, hogy hogyan használjuk fel a leghatékonyabban a rendelkezésünkre álló időt és számítási kapacitást. A tanuló rendszerek mindig két, egymással versengő cél között próbálnak egyensúlyt találni: a kihasználás (exploitation) és a felfedezés (exploration) között. A kihasználás a játék esetében azt jelenti, hogy a gép a korábbról már ismert és többnyire bevált lépésekre koncentrál, és azokat elemzi tovább még mélyebben. A felfedezés ezzel szemben azt jelenti, hogy a gép új, esetleg kockázatos lehetőségek elemzésébe kezd bele – nem feltétlenül élesben, hanem szimulálva, de jelentős erőforrásokat ráfordítva.

Kicsit tágabb értelemben minden tanulásra képes intelligens ágens lényegében modellt épít, amely modell többnyire csak közelítés, ezért egyensúlyt kell találni aközött, hogy az ágens a meglévő modellt, azaz annak paramétereit finomítja a rendelkezésre álló adatok alapján, vagy pedig újfajta modellel vagy modellekkel próbálkozik, ami esetleg jobban illeszkedik az adatokra. Általában véve a két véglet mindig problémás: ha egy rendszer csak a jól ismert utakat járja, könnyen beleragad egy helyi optimumba, és nem találhat rá jobb megoldásokra, ha viszont állandóan csak új dolgokat próbál ki, akkor nem használja ki a megszerzett tudást, nem mélyíti el azt, és rengeteg erőforrást pazarol el kísérletezgetésekre. A siker kulcsa tehát az, hogy okosan válasszuk meg, mikor és mennyi erőforrást áldozunk felfedezésre, és mikor mélyítjük el a már meglévő ismereteket.

A probléma valójában még ennél is sokkal általánosabb. A dilemma nem csak a természetes vagy mesterséges intelligencia világában létezik — magát az evolúciót is ez az egyensúly mozgatja. Egy faj, amely kizárólag a bevált túlélési stratégiáit ismétli, kiszolgáltatottá válik a változó környezetnek. Ugyanakkor egy populáció, amely túl sokat kísérletezik új irányokkal, szétszórja erőforrásait, és mások kiszoríthatják, mielőtt valamelyik új megoldás valóban működőképesnek bizonyulna. Az élet hosszú távú sikere is abból fakad, hogy a stabilitás és a változás, a biztonság és a kockázat közötti kényes egyensúlyt megtaláljuk.

Erre a problémára adott nagyon hatékony választ a két magyar kutató, Kocsis és Szepesvári olyan problémák esetére, ahol a lehetőségek száma óriási, például játékokban vagy bonyolult döntési folyamatok során. Az ötlet valójában egyszerű: minden döntési lehetőséghez ki kell számolni az ahhoz tartozó átlagos eredményt és a bizonytalanságot, ezek összege pedig ad egy optimista becslést (ún. felső konfidenciahatár) arra, hogy mennyire lehet jó egy döntés. Ha egy lépést már sokszor kipróbáltunk (exploitation), az átlagos eredménye valószínűleg nagyobb, a bizonytalansága pedig kicsi. Ha egy lépést ritkán próbáltunk ki (exploration), átlagos eredménye valószínűleg kisebb, bizonytalansága pedig nagyobb. Az algoritmus mindig azt a lépést választja, amelyiknek a legnagyobb az aktuális optimista becslése, azt pedig néha az új lehetőségek magas bizonytalansága, néha pedig a bevált lehetőségek magas átlagos eredménye fogja dominálni. Az UCT algoritmus tehát matematikailag kimért „kíváncsiságot” ad a gépnek. A rendszer nem véletlenszerűen kísérletezik, hanem statisztikailag megalapozottan dönti el, mikor éri meg egy kockázatosabb lépést is kipróbálni.

A szerzők 2006-os cikkükben nemcsak elméletileg igazolták, hogy algoritmusuk közel optimális megoldást ad elegendő mintavételezés mellett, hanem azt is megmutatták, hogy mindezt számítási szempontból is hatékonyan teszi, ráadásul a praktikus alkalmazásokhoz szükséges hibabecsléssel is szolgáltak. Az UCT felhasználási lehetőségei ugyanakkor messze túlmutatnak a go játékon, hiszen ma már az önvezető autók valós idejű útvonaltervezésben, az erőforrás-optimalizáló rendszerekben, sőt még az új gyógyszermolekulák felfedezésében is alapvető szerepet játszanak. Akit még ennél is bővebben érdekel téma, annak ajánlom figyelmébe a MIcsoda világ! című rádióműsor legutóbbi adását, amelyben az évforduló kapcsán Kocsis Leventével, az egyik szerzővel beszélgettem.

A go játékról dióhéjban

Visszatérve magára a go játékra, feltételezésem szerint az AlphaGo története azért sem vált igazán ismertté a laikus közönség körében, mert maga a játék Nyugaton kevésbé elterjedt. Pedig valójában a legősibb, ma is tízmilliók által játszott táblajátékról van szó, amely több mint négyezer éves múltra tekint vissza. A go különlegessége abban rejlik, hogy miközben a szabályai rendkívül egyszerűek, a játék mégis elképesztő mélységű és komplexitású. Nem valószínű, hogy létezik még egy olyan játék, amely ilyen mértékben ötvözi az egyszerűséget a stratégiai mélységgel.

A go szabályai néhány mondatban összefoglalhatók. A játékosok felváltva helyeznek fekete és fehér köveket egy 19×19 mezős rács metszéspontjaira, céljuk pedig az, hogy minél nagyobb területet vegyenek körül a táblán. Kövek csak akkor kerülnek le a tábláról, ha teljesen körbezárják őket az ellenfél kövei, vagyis „elfogják” őket. A játszma végén az győz, akinek több területe és elfogott köve van. Van még egy, a csiki-csuki helyzetekre vonatkozó, valamint egy az „öngyilkosság” megengedését szabályozó rövid kiegészítés – és ezzel vége is a szabályoknak. A lehetőségek azonban gyakorlatilag végtelenek. A góban nincsenek különböző típusú bábuk, mint a sakkban, ezért minden kő jelentőségét az határozza meg, hogyan viszonyul a többihez. A játék így különösen erősen támaszkodik a játékos geometriai érzékére, intuíciójára és stratégiai előrelátására.

A go mélységét jól mutatja egy objektív mérce is, amellyel Mérő László szokta szemléltetni a különbséget a sakkhoz képest. Lehet azt mondani például, hogy két játékos között „egy klasszis” különbség van, ha az egyik nagyjából 75 százalékos valószínűséggel legyőzi a másikat. Ez a sakkban körülbelül 200 Élő-pontnyi különbségnek felel meg, ami azt jelenti, hogy nagyjából kilenc klasszis választja el a világbajnokot attól, aki épp most tanulja a játékot. A go játékban ezzel szemben 13–15 klasszis mélység van, ami jól érzékelteti, mennyivel nagyobb fejlődési tartományt és stratégiai gazdagságot kínál.

Ez a rendkívüli mélység az, ami évezredek óta életben tartja a játékot, és ami miatt ma is élő, tanuló közösségek ápolják világszerte. Hazánkban is aktív goélet zajlik: tucatnyi klub működik, amelyek gyakran megjelennek különféle társasjátékos rendezvényeken – például a Társasjátékok Ünnepén –, ahol bárkit szívesen megtanítanak az alapokra, de rendszeresen rendeznek komoly versenyeket is.

A go egyik különleges sajátossága ráadásul az, hogy eltérő szintű játékosok is élvezetes partikat játszhatnak egymással. A játék ugyanis lehetőséget ad előny (handicap) adására; ilyenkor a gyengébb játékos néhány követ előre letehet a táblára, így kiegyenlítettebbé válik a küzdelem. Ennek köszönhetően kezdők és profik, gyerekek és felnőttek egyaránt tudnak vele úgy játszani, hogy tudásszinttől függetlenül tanulhatnak a játékból. Ez az előnyadási lehetőség különösen érdekes abban a tekintetben is, hogy ma már a legjobb goprogramok ellen csakis előnykövekkel lehet esélye egy embernek, de hogy hogyan jutottunk el idáig, azt nézzük sorjában.

Az AlphaGo történetének folytatása

Miután az AlphaGo 2015-ben legyőzte az Európa-bajnok Fan Hujt, újabb kihívás elé nézett: 2016-ban Szöulban megmérkőzött Lee Sedollal, a tizennyolcszoros dél-koreai világbajnokkal. A gép 4-1-re nyert, és a világ döbbenten figyelte, ahogy a gép olyan lépéseket tesz, amelyeket a legnagyobb mesterek is „kreatívnak” neveztek. A második játszma híres 37. lépése például olyannyira szokatlan volt, hogy Lee Sedol percekig csak döbbenten nézte. Erről a történelmi párharcról, amit világszerte 200 millió ember követett, egy díjnyertes dokumentumfilm is készült, ami 2017-ben jelent meg, a győztesnek felajánlott egy millió dollár jutalmat pedig karitatív szervezeteknek, köztük az UNICEF-nek adományozták.

Azt tudni kell, hogy az AlphaGo nem csak emberi partikon, de szimulált gép-gép elleni játszmákon keresztül is tanult. Így fordulhatott elő, hogy nemcsak egyre erősebbé vált, de olyan megoldásokat talált, amelyekre az ember sem számított. 2017 májusában a kínai Vucen (Wuzhen) városban megrendezett Future of Go Summit című rendezvényen az AlphaGo továbbfejlesztett változata három játszmából álló mérkőzésen játszott a világ legerősebb gojátékosának tartott 9 danos profi, Ko Csie ellen. Az első játékban fél ponttal nyert az AlphaGo, a másik kettőt feladta Ko Csie, aki a vereség után úgy nyilatkozott, hogy az AlphaGo úgy játszik, mint a go istene.

Nem sokkal ezután a DeepMind kifejlesztette még az AlphaGo Zerót, amelyet úgy tanítottak, hogy egyetlen emberi partit sem látott, csak önmagával játszott, és tudása 40 nap alatt meghaladta az összes korábbi verzióét. A Google ezt követően létrehozta az AlphaZero nevű általánosított változatot, amely a go mellett megtanult sakkozni és más játékokkal játszani is, és legyőzte a legjobb sakkprogramot, a Stockfisht. Az AlphaGo ma már „visszavonult” – több partit nem játszik –, a DeepMind csapata pedig a mesterséges intelligencia más területeire összpontosít. Azóta újabb rendszerek – például a Fine Art, Golaxy, KataGo, ELF OpenGo – vitték tovább az örökségét, mind jóval az emberi világbajnokok szintje fölé emelkedve.

Az AlphaGo története ezért nem csupán egy játék története. Az a pillanat, amikor egy gép először legyőzte az embert a góban, a mesterséges intelligencia egyik legnagyobb „ébredése” volt: bizonyíték arra, hogy a gépek nemcsak követni tudnak bennünket, hanem olykor megmutathatják, hogy másképp is lehet gondolkodni. Az AlphaGo jelentősége a Deep Blue-hoz képest nem pusztán abban rejlik, hogy újabb mérföldkövet jelentett, hanem abban is, hogy az általa használt algoritmusok és komponensek azóta számos más területen is hasznosultak. Így az AlphaGo nemcsak látványos siker volt, hanem valóban tovább is lendítette a mesterséges intelligencia fejlődését – ahogy azt a DeepMind újabb projektjei és eredményei is mutatják.