Monte-Carlo-fakeresés

A Wikipédiából, a szabad enciklopédiából

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[szerkesztés]

Monte-Carlo-módszer[szerkesztés]

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.[1] 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".[2] 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)[szerkesztés]

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

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 nevű 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,[4] Havannah,[5] Game of the Amazons,[6] és Arimaa[7]), valós idejű videojátékokban (például Ms. Pac-Man[8][9] és Fable Legends[10]), és nem determinisztikus játékok (mint például skat,[11] póker,[12] Magic: The Gathering,[13] vagy Settlers of Catan[14]).

Működési elv[szerkesztés]

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) nevű 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 R gyökértől, és válassza ki az egymást követő gyermek csomópontokat, amíg el nem éri az L 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 C 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 C-től R-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[szerkeszté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[szerkeszté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 a legnagyobb értékkel bír. Ebben a képletben:

  • wi az i-edik lépés után a figyelembe vett csomópont győzelmeinek számát jelöli
  • ni az i-edik lépés után a figyelembe vett csomópontra vonatkozó szimulációk számát jelöli.
  • Ni 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.
  • c 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[szerkesztés]

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[szerkesztés]

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.[15]

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 elemet, ahol bi az i-edik lépés heurisztikus pontszáma.[16]

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.[17] 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 a legnagyobb értékkel rendelkezik. Ebben a képletben és 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 függvénynek közel egynek kell lennie viszonylag kicsi és közel nullának viszonylag nagy és esetén. A sok formula közül az egyik függvénynek, amelyet D. Silver javasolt, azt mondja, hogy kiegyensúlyozott pozíciókban vehetünk , 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:[18]

  • 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.

Jegyzetek[szerkesztés]

  1. ↑ Nicholas (1949. április 25.). „The monte carlo method”. Journal of the American Statistical Association 44 (247), 335–341. o. DOI:10.1080/01621459.1949.10483310. PMID 18139350.  
  2. ↑ Abramson, Bruce. The Expected-Outcome Model of Two-Player Games. Technical report, Department of Computer Science, Columbia University (1987). Hozzáférés ideje: 2013. december 23. 
  3. ↑ Sensei's Library: KGSBotRatings. (Hozzáférés: 2012. május 3.)
  4. ↑ Broderick Arneson (2009. június 1.). „MoHex Wins Hex Tournament”. ICGA Journal 32 (2), 114–116. o. DOI:10.3233/ICG-2009-32218.  
  5. ↑ Timo Ewalds. Playing and Solving Havannah. Master's thesis, University of Alberta (2011) 
  6. ↑ Richard J. Lorentz. Amazons Discover Monte-Carlo, Computers and Games, 6th International Conference, CG 2008, Beijing, China, September 29 – October 1, 2008. Proceedings, H. Jaap van den Herik, Xinhe Xu, Zongmin Ma, Mark H. M. Winands (eds.), Springer, 13–24. o. (2008). ISBN 978-3-540-87607-6 
  7. ↑ Tomáš Kozelek. Methods of MCTS and the game Arimaa. Master's thesis, Charles University in Prague (2009) 
  8. ↑ Xiaocong Gan (2011. december 1.). „Real-Time Search Method in Nondeterministic Game – Ms. Pac-Man”. ICGA Journal 34 (4), 209–222. o. DOI:10.3233/ICG-2011-34404.  
  9. ↑ Tom Pepels (2014. szeptember 1.). „Real-Time Monte Carlo Tree Search in Ms Pac-Man”. IEEE Transactions on Computational Intelligence and AI in Games 6 (3), 245–257. o. DOI:10.1109/tciaig.2013.2291577.  
  10. ↑ Mountain: Tactical Planning and Real-time MCTS in Fable Legends, 2015 [2019. június 8-i dátummal az eredetiből archiválva]. (Hozzáférés: 2019. június 8.) „.. we implemented a simulation based approach, which involved modelling the game play and using MCTS to search the potential plan space. Overall this worked well, ...”
  11. ↑ Michael Buro. Improving State Evaluation, Inference, and Search in Trick-Based Card Games, IJCAI 2009, Proceedings of the 21st International Joint Conference on Artificial Intelligence, Pasadena, California, USA, July 11–17, 2009, Craig Boutilier (ed.), 1407–1413. o. (2009) 
  12. ↑ Jonathan Rubin (2011. április 1.). „Computer poker: A review”. Artificial Intelligence 175 (5–6), 958–987. o. DOI:10.1016/j.artint.2010.12.005.  
  13. ↑ C.D. Ward. Monte Carlo Search Applied to Card Selection in Magic: The Gathering, CIG'09 Proceedings of the 5th international conference on Computational Intelligence and Games. IEEE Press (2009) 
  14. ↑ István Szita.szerk.: Jaap Van Den Herik: Monte-Carlo Tree Search in Settlers of Catan, Advances in Computer Games, 12th International Conference, ACG 2009, Pamplona, Spain, May 11–13, 2009. Revised Papers. Springer, 21–32. o. (2010). ISBN 978-3-642-12992-6 
  15. ↑ Sylvain Gelly. Modification of UCT with Patterns in Monte Carlo Go. Technical report, INRIA (2006. november 1.) 
  16. ↑ G.M.J.B. Chaslot (2008). „Progressive Strategies for Monte-Carlo Tree Search”. New Mathematics and Natural Computation 4 (3), 343–359. o. DOI:10.1142/s1793005708001094.  
  17. ↑ Gelly, Sylvain. Combining Online and Offline Knowledge in UCT, Machine Learning, Proceedings of the Twenty-Fourth International Conference (ICML 2007), Corvallis, Oregon, USA, June 20–24, 2007, Zoubin Ghahramani (ed.), ACM, 273–280. o. (2007). ISBN 978-1-59593-793-3 
  18. ↑ Guillaume M.J-B. Chaslot, Mark H.M. Winands, Jaap van den Herik. Parallel Monte-Carlo Tree Search, Computers and Games, 6th International Conference, CG 2008, Beijing, China, September 29 – October 1, 2008. Proceedings, H. Jaap van den Herik, Xinhe Xu, Zongmin Ma, Mark H. M. Winands (eds.), Springer, 60–71. o. (2008). ISBN 978-3-540-87607-6 

Fordítás[szerkesztés]

Ez a szócikk részben vagy egészben a Monte Carlo tree search című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

A lap eredeti címe: „https://hu.wikipedia.org/w/index.php?title=Monte-Carlo-fakeresés&oldid=26087162”