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.

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.

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,^[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]).

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

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.

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.

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 ${\displaystyle {\frac {w_{i}}{n_{i}}}+c{\sqrt {\frac {\ln N_{i}}{n_{i}}}}}$ a legnagyobb értékkel bír. Ebben a képletben:

• w_i az i-edik lépés után a figyelembe vett csomópont győzelmeinek számát jelöli
• n_i az i-edik lépés után a figyelembe vett csomópontra vonatkozó szimulációk számát jelöli.
• N_i 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.)

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

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.

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 ${\displaystyle {\frac {b_{i}}{n_{i}}}}$ 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 alkalmazásakor a kiválasztási lépés kiválasztja azt a csomópontot, amelyre a módosított UCB1 képlet szerint ${\displaystyle (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 ${\displaystyle {\tilde {w}}_{i}}$ és ${\displaystyle {\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${\displaystyle \beta (n_{i},{\tilde {n}}_{i})}$ függvénynek közel egynek kell lennie viszonylag kicsi és közel nullának viszonylag nagy ${\displaystyle n_{i}}$ és ${\displaystyle {\tilde {n}}_{i}}$ esetén. A sok formula közül az egyik ${\displaystyle \beta (n_{i},{\tilde {n}}_{i})}$ függvénynek, amelyet D. Silver javasolt, azt mondja, hogy kiegyensúlyozott pozíciókban vehetünk ${\displaystyle \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:^[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.

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.