Monte-Carlo-fakeresés

Az informatikában a Monte-Carlo-fakeresés (angolul rövidítve: MCTS) egy heurisztikus keresési algoritmus bizonyos típusú döntési folyamatokhoz, leginkább a társasjátékokat játszó szoftverekben használtakhoz. Ebben az összefüggésben az MCTS-t a játékfa megoldására használják.

Az MCTS-t 2016-ban neurális hálózatokkal kombinálták a számítógépes góhoz. Ezt használták más társasjátékokban is, például a sakkban és a sógiban, hiányos információkat tartalmazó játékokban, például a bridzsben és a pókerben, valamint a körökre osztott stratégiai videojátékokban (mint például a Total War: Rome II implementációjában a magas szintű kampány AI-jában). Az MCTS-t önvezető autókban is alkalmazták, például a Tesla Autopilot szoftverben.

Történet

Monte-Carlo-módszer

Az 1940-es évekre nyúlik vissza a Monte-Carlo-módszer, amely véletlenszerű mintavételt alkalmaz olyan determinisztikus problémákra, amelyeket más megközelítéssel nehéz vagy lehetetlen megoldani. 1987-es PhD disszertációjában Bruce Abramson a szokásos statikus kiértékelési funkció helyett a végére kombinálta a minimax keresést egy véletlenszerű játéklejátszásokon alapuló várható eredmény modellel. Abramson elmondta, hogy a várható eredménymodell "precíznek, pontosnak, könnyen becsülhetőnek, hatékonyan kiszámíthatónak és tartományfüggetlennek bizonyult". Mélyrehatóan kísérletezett a tic-tac-toe-val, majd az Othello és a sakk gépi kiértékelési funkcióival.

Az ilyen módszereket aztán W. Ertel, J. Schumann és C. Suttner 1989-ben az automatizált tételbizonyítás területén vizsgálta és sikeresen alkalmazta a heurisztikus keresésre, javítva ezzel a nem informált kereső algoritmusok, mint például a szélességi keresés, a mélység keresés vagy az iteratív mélyítés exponenciális keresési idejét.

B. Brügmann 1992-ben alkalmazta először egy goprogramban. 2002-ben Chang és társai a Markov-döntési folyamatok modelljére kidolgozott Adaptive Multi-stage Sampling (AMS) algoritmusukban "adaptív" mintavételi döntésekkel "rekurzív kigurulás és visszalépés" ötletét javasolták. Az AMS volt az első olyan munka, amely a mintavételezett/szimulált (Monte-Carlo-) fák építésénél az UCB-alapú feltárás és kiaknázás ötletét vizsgálta, és ez volt az UCT (Upper Confidence Trees) fő magja.

Monte-Carlo-fakeresés (MCTS)

A legjobb goprogramok értékelése a KGS szerveren 2007 óta. 2006 óta az összes legjobb program a Monte-Carlo-fakeresőt használja.

Rémi Coulom 2006-ban, ezen elődök által inspirálva, leírta a Monte-Carlo-módszer alkalmazását a játékfakeresésre, és megalkotta a Monte-Carlo-fakeresés nevet, L. Kocsis és Cs. Szepesvári kidolgozta az UCT (Upper Confidence bounds applied to Trees) algoritmust, S. Gelly és társai pedig az UCT-t implementálták MoGo programjukban. A MoGo 2008-ban elérte a dan (mester) szintet 9×9-es góban, és a Fuego program 9×9-es góban erős amatőr játékosok ellen kezdett győzni.

2012 januárjában a Zen program 3:1-re nyert egy 19×19-es táblán játszott gomérkőzésen egy 2 danos amatőr játékos ellen. A Google Deepmind fejlesztette ki az AlphaGo programot, amely 2015 októberében az első olyan számítógépes goprogram lett, amely egy teljes méretű 19x19-es táblán hátrány nélkül legyőzött egy profi gojátékost. 2016 márciusában az AlphaGo tiszteletbeli 9 dan (mester) fokozatot kapott 19×19-es góban, mivel egy ötjátszmás mérkőzésen négy az egyhez arányban legyőzte Lee Sedolt. Az AlphaGo jelentős előrelépést jelent a korábbi goprogramokhoz képest, valamint mérföldkövet jelent a gépi tanulásban, mivel Monte-Carlo-fakeresést használ mesterséges neurális hálózatokkal (egy mély tanulási módszer) a lépésválasztáshoz és az értékhez, így hatékonysága messze felülmúlja a korábbi programokat.

Az MCTS algoritmust olyan programokban is használták, amelyek más társasjátékokat játszanak (például Hex, Havannah, Game of the Amazons, és Arimaa), valós idejű videojátékokban (például Ms. Pac-Man és Fable Legends), és nem determinisztikus játékok (mint például skat, póker, Magic: The Gathering, vagy Settlers of Catan).

Működési elv

Az MCTS fókuszában a legígéretesebb lépések elemzése áll, a keresési tér véletlenszerű mintavétele alapján bővítve a keresési fát. A Monte-Carlo-fakeresés alkalmazása a játékokban sok kijátszáson, más néven roll-outon alapul. Minden egyes játékmenetben a játékot a legvégéig játsszák véletlenszerű lépések kiválasztásával. Az egyes kijátszások végeredményét ezután a játékfa csomópontjainak súlyozására használjuk, hogy a jövőbeli kijátszások során nagyobb valószínűséggel válasszunk jobb csomópontokat.

A kijátszások használatának legalapvetőbb módja az, hogy az aktuális játékos minden egyes legális lépése után ugyanannyi kijátszást alkalmazunk, majd kiválasztjuk azt a lépést, amelyik a legtöbb győzelemhez vezetett. Ennek az úgynevezett Pure Monte Carlo Game Search (tiszta Monte-Carlo-játékkeresés) módszernek a hatékonysága gyakran nő az idő múlásával, mivel több kijátszást rendelünk azokhoz a lépésekhez, amelyek a korábbi kijátszások szerint gyakran vezettek az aktuális játékos győzelméhez. A Monte-Carlo-fakeresés minden egyes fordulója négy lépésből áll:

• Kiválasztás: Kezdje az Sablon:Math gyökértől, és válassza ki az egymást követő gyermek csomópontokat, amíg el nem éri az Sablon:Math levél csomópontot. A gyökér az aktuális játékállapot, a levél pedig minden olyan csomópont, amelynek potenciális gyermeke van, és amelyről még nem indult el a szimuláció (playout). Az alábbi szekcióban többet mondunk a gyermekcsomópontok kiválasztásának olyan előfeszítési módjáról, amely lehetővé teszi, hogy a játékfa a legígéretesebb lépések felé terjeszkedjen, ami a Monte-Carlo-fakeresés lényege.
• Bővítés: Hacsak L nem döntő módon (pl. győzelem/veszteség/döntetlen) nem fejezi be a játékot bármelyik játékos számára, hozzon létre egy (vagy több) gyermek csomópontot, és ezek közül válassza ki a C csomópontot. A gyermek csomópontok az L által meghatározott játékhelyzetből kiinduló bármely érvényes lépés.
• Szimuláció: Végezzen el egy véletlenszerű lejátszást a Sablon:Math csomópontból. Ezt a lépést néha lejátszásnak (playout) vagy közzétételnek (rollout) is nevezik. A kijátszás lehet olyan egyszerű, mint az egységes véletlenszerű lépések kiválasztása, amíg a játszma el nem dől (például a sakkban a játszma megnyerése, elvesztése vagy döntetlen).
• Visszaterjesztés: Használja a lejátszás eredményét a Sablon:Math-től Sablon:Math-ig tartó útvonal csomópontjaiban lévő információk frissítésére.

Monte-Carlo-fakeresés lépése

Ez a grafikon egy döntés lépéseit mutatja, minden egyes csomópont a győzelmek és az összes kijátszás arányát mutatja a játékfa adott pontjától a játékos számára, akit a csomópont képvisel. A kiválasztási diagramon a fekete éppen lépni készül. A gyökércsomópont azt mutatja, hogy ebből az állásból eddig 21 kijátszásból 11 győzelem jutott a fehérnek. Ez kiegészíti az alatta lévő három fekete csomópont mentén látható 10/21 fekete győzelmet, amelyek mindegyike egy-egy lehetséges fekete lépést jelent. Megjegyzendő, hogy ez a gráf nem követi az alább ismertetett UCT algoritmust.

Ha a fehér elveszíti a szimulációt, akkor a kiválasztás mentén lévő összes csomópont szimulációs száma növekszik (a nevező), de közülük csak a fekete csomópontok kaptak győzelmet (a számláló). Ha ehelyett a fehér nyer, a kiválasztás mentén lévő összes csomópont továbbra is növeli a szimulációszámát, de közülük csak a fehér csomópontok kapnak győzelmet. Azokban a játékokban, ahol döntetlen is lehetséges, a döntetlen hatására mind a fekete, mind a fehér számlálója 0,5-tel, a nevezője pedig 1-gyel növekszik. Ez biztosítja, hogy a kiválasztás során minden játékos választása az adott játékos számára legígéretesebb lépések felé bővüljön, ami tükrözi minden játékos azon célját, hogy maximalizálja lépésének értékét.

A keresési körök addig ismétlődnek, amíg a lépésre szánt idő tart. Ezután a legtöbb szimulációt (azaz a legnagyobb nevezőt) tartalmazó lépés lesz a végső válasz.

Tiszta Monte-Carlo-játékkeresés

Ez az alapeljárás bármely olyan játékra alkalmazható, amelynek pozíciói szükségszerűen véges számú lépéssel és véges hosszúsággal rendelkeznek. Minden egyes álláshoz meghatározzuk az összes lehetséges lépést: k véletlenszerű játszmát játszunk le a végsőkig, és feljegyezzük a pontszámokat. A legjobb pontszámhoz vezető lépést választjuk ki. A döntetleneket igazságos pénzfeldobással oldjuk a tiszta Monte-Carlo-játékkeresés számos véletlen elemeket tartalmazó játékban erős játékot eredményez, mint például az EinStein würfelt nicht! játékban. Az optimális játékhoz konvergál (ahogy k a végtelen felé közelít) a véletlenszerű fordulósorrenddel rendelkező táblafeltöltő játékokban, például a Hex játékban véletlenszerű fordulósorrenddel.

Feltárás és kiaknázás

A gyermekcsomópontok kiválasztásának fő nehézsége a magas átlagos nyerési aránnyal rendelkező lépések utáni mély változatok kihasználása és a kevés szimulációval rendelkező lépések feltárása közötti egyensúly fenntartása. A játékokban a kihasználás és a felfedezés egyensúlyának megteremtésére szolgáló első képletet, az UCT-t (Upper Confidence Bound 1 fákra alkalmazva) Kocsis Levente és Szepesvári Csaba vezette be. Az UCT az Auer, Cesa-Bianchi és Fischer által levezetett UCB1 képleten és a bizonyíthatóan konvergens AMS (Adaptive Multi-stage Sampling) algoritmuson alapul, amelyet először Chang, Fu, Hu és Marcus alkalmazott többlépcsős döntéshozatali modellekre (konkrétan Markov-döntési folyamatokra). Kocsis és Szepesvári azt javasolják, hogy a játékfa minden egyes csomópontjában azt a lépést válasszuk ki, amelyre a kifejezés $\frac{w_i}{n_i}+c\sqrt{\frac{\ln N_i}{n_i}}$ a legnagyobb értékkel bír. Ebben a képletben:

• Sablon:Math az i-edik lépés után a figyelembe vett csomópont győzelmeinek számát jelöli
• Sablon:Math az i-edik lépés után a figyelembe vett csomópontra vonatkozó szimulációk számát jelöli.
• Sablon:Math a vizsgált csomópont szülői csomópontja által végrehajtott i-edik lépés utáni szimulációk teljes számát jelöli.
• Sablon:Math a feltárási paraméter elméletileg egyenlő √2-vel; a gyakorlatban általában empirikusan választják meg.

A fenti képlet első összetevője a kihasználásnak felel meg; ez magas a magas átlagos nyerési aránnyal rendelkező lépések esetében. A második összetevő a felfedezésnek felel meg; a kevés szimulációval rendelkező lépéseknél magas.

A Monte-Carlo-fakeresés legtöbb modern megvalósítása az UCT valamilyen változatán alapul, amely a Chang és munkatársai által bevezetett AMS szimulációs optimalizálási algoritmusra vezeti vissza az értékfüggvény becslését a véges horizontú Markov döntési folyamatokban (MDP). (2005) in Operations Research. (Az AMS volt az első olyan munka, amely feltárta az UCB-alapú feltárás és kiaknázás ötletét a mintavételezett/szimulált (Monte-Carlo-) fák felépítésében, és ez volt az UCT fő magva.)

Előnyök és hátrányok

Bár bebizonyosodott, hogy a lépések kiértékelése a Monte-Carlo-fakeresésben a minimaxhoz konvergál, a Monte-Carlo-fakeresés alapváltozata csak az úgynevezett "Monte Carlo Perfect" játékokban konvergál. A Monte-Carlo-fakeresés azonban jelentős előnyöket kínál az alfa-béta metszéssel és hasonló, a keresési teret minimalizáló algoritmusokkal szemben.

A tiszta Monte-Carlo-fakeresésnek nincs szüksége explicit kiértékelő függvényre. A keresési tér (azaz a megengedett lépések generálása egy adott pozícióban és a játék végi feltételek) feltárásához elegendő a játék mechanikájának egyszerű végrehajtása. Mint ilyen, a Monte-Carlo-fakeresés alkalmazható olyan játékokban, amelyeknek nincs kidolgozott elmélete, vagy általános játékmenetben.

A Monte-Carlo-fakereső játékfa aszimmetrikusan növekszik, mivel a módszer az ígéretesebb részfákra koncentrál. Így jobb eredményeket ér el, mint a klasszikus algoritmusok a magas elágazási tényezővel rendelkező játékokban.

Hátránya, hogy bizonyos pozíciókban lehetnek olyan lépések, amelyek felületesen erősnek tűnnek, de valójában egy finom játszmavonalon keresztül veszteséghez vezetnek. Az ilyen "csapdaállapotok" alapos elemzést igényelnek a helyes kezeléshez, különösen, ha szakértő játékos ellen játszunk, az MCTS azonban a szelektív csomópontbővítés politikája miatt nem biztos, hogy "látja" az ilyen vonalakat. Úgy vélik, hogy részben ez lehetett az oka annak, hogy az AlphaGo a Lee Sedol elleni negyedik játszmában vereséget szenvedett. Lényegében a keresés megkísérli a kevésbé releváns szekvenciák selejtezését. Bizonyos esetekben egy játszma egy nagyon speciális játszmavonalhoz vezethet, amely jelentős, de a fa metszésekor figyelmen kívül hagyják, és ezért ez az eredmény "kikerül a keresés radarjáról".

Fejlesztések

A keresési idő lerövidítésére az alapvető Monte-Carlo-fakeresési módszer különböző módosításait javasolták. Egyesek szakterület specifikus szakértői tudást használnak, mások nem.

A Monte-Carlo-fakeresés használhat könnyű vagy nehéz lejátszást. A könnyű lejátszások véletlenszerű lépésekből állnak, míg a nehéz lejátszások különböző heurisztikákat alkalmaznak a lépések kiválasztásának befolyásolására. Ezek a heurisztikák felhasználhatják a korábbi kijátszások eredményeit (pl. az utolsó jó válasz heurisztika) vagy az adott játékra vonatkozó szakértői ismereteket. Például sok goprogramban a tábla egy részén található bizonyos kőminták befolyásolják az adott területre való lépés valószínűségét. Paradox módon a szimulációkban való szuboptimális játék néha összességében erősebb játékra késztet egy Monte-Carlo-fakereső programot.

Hane (ellenfél köveket körülvevő) minták, amelyeket a MoGo program a játék során használ. Fekete és fehér esetében is előnyös, ha követ tesz a középső négyzetre, kivéve a jobb szélső mintát, ahol csak a feketét részesíti előnyben.

A játékfa építése során a tartományspecifikus ismeretek felhasználhatók egyes változatok kiaknázásának elősegítésére. Az egyik ilyen módszer az egyes gyermekcsomópontok létrehozásakor nem nulla priort rendel a megnyert és a lejátszott szimulációk számához, ami mesterségesen megemelt vagy csökkentett átlagos nyerési arányt eredményez, ami miatt a csomópontot gyakrabban, illetve ritkábban választják ki a kiválasztási lépésben. Egy kapcsolódó, progresszív torzításnak nevezett módszer lényege, hogy az UCB1 képlethez hozzáadunk egy $\frac{b_i}{n_i}$ elemet, ahol bi az i-edik lépés heurisztikus pontszáma.

Az alapvető Monte-Carlo-fakeresés elegendő információt gyűjt össze ahhoz, hogy csak sok kör után találja meg a legígéretesebb lépéseket; addig mozgásai lényegében véletlenszerűek. A RAVE (Rapid Action Value Estimation) használatával a játékok bizonyos osztályaiban ez a felfedező szakasz jelentősen lecsökkenhet. Ezekben a játékokban a mozdulatsorok permutációi ugyanabba a pozícióba vezetnek. Jellemzően olyan társasjátékok, amelyekben egy mozdulat egy darab vagy egy kő elhelyezésével jár a táblán. Az ilyen játékokban az egyes lépések értékét gyakran csak kis mértékben befolyásolják más lépések.

A RAVE-ben egy adott N csomóponthoz tartozó játékfa Ci gyermekcsomópontjai nemcsak az N csomópontban megkezdett játszmák győzelmi statisztikáit tárolják, hanem az N csomópontban és alatta megkezdett összes játszma győzelmi statisztikáit is, ha azok tartalmazzák az i lépést (akkor is, ha a lépést a fában játszották le, az N csomópont és egy játszma között). Ily módon a fa csomópontjainak tartalmát nemcsak az adott pozícióban azonnal kijátszott lépések befolyásolják, hanem a később kijátszott ugyanilyen lépések is.

RAVE a tic-tac-toe példáján. A piros csomópontokban a RAVE statisztikák a b1-a2-b3 szimuláció után frissülnek.

RAVE alkalmazásakor a kiválasztási lépés kiválasztja azt a csomópontot, amelyre a módosított UCB1 képlet szerint $(1-\beta (n_i,{\tilde{n}}_i))\frac{w_i}{n_i}+\beta (n_i,{\tilde{n}}_i)\frac{{\tilde{w}}_i}{{\tilde{n}}_i}+c\sqrt{\frac{\ln t}{n_i}}$ a legnagyobb értékkel rendelkezik. Ebben a képletben ${\tilde{w}}_i$ és ${\tilde{n}}_i$ az i. lépést tartalmazó nyertes kijátszások számát és az i. lépést tartalmazó összes kijátszás számát jelöli, és a$\beta (n_i,{\tilde{n}}_i)$ függvénynek közel egynek kell lennie viszonylag kicsi és közel nullának viszonylag nagy $n_i$ és ${\tilde{n}}_i$ esetén. A sok formula közül az egyik $\beta (n_i,{\tilde{n}}_i)$ függvénynek, amelyet D. Silver javasolt, azt mondja, hogy kiegyensúlyozott pozíciókban vehetünk $\beta (n_i,{\tilde{n}}_i)=\frac{{\tilde{n}}_i}{n_i+{\tilde{n}}_i+4b^2{n}_i{\tilde{n}}_i}$, ahol b egy empirikusan választott konstans.

A Monte-Carlo-fakeresésben használt heurisztikák gyakran sok paramétert igényelnek. Vannak automatizált módszerek a paraméterek beállítására a nyerési arány maximalizálása érdekében.

A Monte-Carlo-fában végzett keresést egyszerre több szál vagy folyamat is végrehajthatja. Párhuzamos végrehajtásának számos alapvetően eltérő módszere létezik:

• Levélpárhuzamosítás, azaz sok játék párhuzamos végrehajtása a játékfa egy leveléből.
• Gyökérpárhuzamosítás, azaz független játékfák párhuzamos felépítése és a lépés végrehajtása az összes ilyen fa gyökérszintű ágai alapján..
• Fapárhuzamosítás, azaz ugyanazon játékfa párhuzamos építése, az adatok egyidejű írástól való védelme akár egy, globális mutexszel, akár több mutexszel, akár nem blokkoló szinkronizálással.