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) bélyegkép|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 gyökértől, és válassza ki az egymást követő gyermek csomópontokat, amíg el nem éri az 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 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 -től -ig tartó útvonal csomópontjaiban lévő információk frissítésére.
középre|bélyegkép|800x800px| 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 a legnagyobb értékkel bír. Ebben a képletben:
az i-edik lépés után a figyelembe vett csomópont győzelmeinek számát jelöli az i-edik lépés után a figyelembe vett csomópontra vonatkozó szimulációk számát jelöli. 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. 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.