Monte-Carlo-fakeresés

A Monte-Carlo-fakeresés, röviden MCTS, nem próbál minden változatot azonos mélységig megvizsgálni. Fokozatosan épít fel egy fát, és az összegyűlt eredmények alapján dönti el, hová kerüljön a következő számítási adag. Egy sokszor meglátogatott lépés nem automatikusan jó, de a becslését rendszerint több keresési adat támasztja alá.

Egy MCTS-ciklus

1. Kiválasztás: a kezdőállásból indulva a már létező ágakat követi, és egyensúlyt keres a már erősnek látszó, illetve a még bizonytalan lehetőségek között.
2. Kibővítés: hozzáad a fához egy olyan állást vagy lépést, amelyet az még nem bontott ki.
3. Értékelés: megbecsüli az eredményt az új állásból. A klasszikus módszerek szimulált játszmákat játszhatnak végig, a modern rendszerek pedig neurális hálózatot, vagyis mintázatok felismerésére betanított modellt is használhatnak az állás megítélésére.
4. Visszaterjesztés: a kapott eredményt visszavezeti a bejárt útvonalon, és frissíti a látogatásszámokat és a becsléseket.

A ciklus ismétlése egyensúlyt teremt a kiaknázás és a feltárás között. A kiaknázás azt jelenti, hogy több erőforrás jut oda, ahol a jelek már kedvezők. A feltárás bizonytalan alternatívákat ellenőriz, hogy egy meglepetést ne vessenek el túl korán. A kettő egyensúlyának pontos szabálya a megvalósítástól függ.

A minimaxtól eltérően az MCTS rendszerint a keresés közben összegyűlt bizonyítékok alapján dönti el, mennyit vizsgáljon egy ágat, nem csupán egységes mélység szerint. Egyes neurális hálózatokra épülő sakkprogramokban a hálózat egy lépéspolitikát ad, amely valószínű lépéseket javasol, valamint egy értéket, amely megbecsüli az eredményt. Ez az érték a értékelőfüggvényhez hasonló szerepet tölt be, bár a teljes keresési folyamat eltérő.