Monte Carlo tree search

Monte Carlo tree search (tsz. Monte Carlo tree searches)

1. (informatika, mesterséges intelligencia) Monte-Carlo-fakeresés

A Monte Carlo Tree Search (MCTS) egy sztochasztikus, heurisztikus keresési algoritmus, amelyet leginkább játékok és döntési problémák megoldására alkalmaznak. Népszerűsége a számítógépes Go játékban való áttörő sikere után nőtt meg, és azóta számos más területen is alkalmazzák, például mesterséges intelligenciában, robotikában, tervezésben, vagy általános problémamegoldásban. Az MCTS hatékonyságát annak köszönheti, hogy intelligens módon egyesíti a valószínűségi szimulációkat és a faalapú keresést.

A Monte Carlo Tree Search fő célja, hogy a döntési lehetőségek közül a legjobbat válassza, anélkül, hogy az összes lehetőséget teljesen végigelemezné. Ehelyett a valószínűségek és mintavételezés (Monte Carlo szimulációk) alapján becslést ad az egyes döntések jövőbeli eredményességére.

Ez úgy működik, hogy a lehetséges állapotokat egy fa struktúrában képviseli, és különböző játékmeneteket (szimulációkat) futtat, hogy megtudja, mely ágak vezetnek a legjobb eredményekhez.

Az MCTS iteratív folyamatként működik. Minden iteráció négy fő lépésből áll:

A fa gyökércsomópontjától indulva követjük azokat az ágakat, amelyek ígéretesnek tűnnek. A kiválasztás során egy felfedezés–kihasználás egyensúlyt alkalmazó heurisztikát, például az UCB1 formulát (Upper Confidence Bound) használják. Ez a lépés addig tart, amíg el nem érünk egy olyan csomópontot, amely vagy:

• még nem teljesen bővített, vagy
• terminális (végállapot).

Ha a kiválasztott csomópont nem terminális, bővítjük a fát egy vagy több gyermekcsomópont hozzáadásával, amely új lehetőséget reprezentál.

A kiválasztott új csomópontból véletlenszerűen lejátszunk egy játékot vagy végrehajtunk egy döntéssorozatot a végállapotig. Ez a Monte Carlo-szimuláció. A végén megkapjuk a játék eredményét vagy a döntés “hasznosságát”.

A szimuláció eredményét visszaterjesztjük azokon a csomópontokon, amelyeken keresztül a kiválasztás történt. Frissítjük az egyes csomópontok statisztikáit: pl. győzelmek száma, látogatások száma. Így egyre pontosabb becslést kapunk a csomópont hasznosságáról.

A kiválasztás lépéséhez az egyik legismertebb formula az UCB1 (Upper Confidence Bound):

$${\displaystyle UCB1={\frac {w_{i}}{n_{i}}}+C\cdot {\sqrt {\frac {\ln N}{n_{i}}}}}$$

• ${\textstyle w_{i}}$ – győzelmek száma a csomópontban
• ${\textstyle n_{i}}$ – látogatások száma a csomópontban
• ${\textstyle N}$ – látogatások száma a szülőcsomópontban
• ${\textstyle C}$ – felfedezési együttható (általában ${\textstyle {\sqrt {2}}}$)

Ez a képlet biztosítja, hogy ne csak a jól teljesítő csomópontokat vizsgáljuk, hanem néha újakat is felfedezzünk, hiszen a gyakorlatban nem garantált, hogy a jelenlegi legjobb a valóban legjobb.

• Go – itt ért el igazán áttörő eredményt (pl. AlphaGo)
• Sakk, Hex, Othello, General Game Playing
• Videojátékok, például valós idejű stratégiai játékok (pl. StarCraft AI)

• Mozgástervezés (motion planning)
• Döntési fa alapú vezérlés (robot navigáció, autonóm járművek)

• Optimalizálási problémák
• Menetrendkészítés
• Gazdasági szimulációk

• Nem kell teljesen ismert modell: A szimulációhoz nem szükséges tökéletes tudás az egész problématérről.
• Rugalmas és általános: Könnyen adaptálható különféle problémákhoz.
• Fokozatos pontosság: Minél több időt adunk neki, annál jobb döntéseket hoz.

• Nagy számítási igény: Sok szimulációra van szükség a jó döntésekhez.
• Véletlenszerűség érzékenysége: Ha a szimulációs politika túl primitív, rossz döntésekhez vezethet.
• Nem determinisztikus: Mivel a szimulációk sztochasztikusak, az eredmény nem mindig megismételhető.

Az alapsémát az idők során többféleképpen módosították, hogy gyorsabb, okosabb vagy megbízhatóbb legyen:

1. UCT (Upper Confidence bounds applied to Trees) – a legnépszerűbb variáns, UCB1-t alkalmazza.
2. RAVE (Rapid Action Value Estimation) – gyorsabb konvergenciát céloz meg.
3. Progressive Widening – csak fokozatosan bővíti a fát, ha már elég látogatás történt.
4. Nested MCTS – a faépítés közben újabb MCTS-algoritmusokat futtat.
5. Parallel MCTS – több szálon/számítógépen futtatott verzió.

function MCTS(root):
    for i in 1 to N:
        leaf = select(root)
        child = expand(leaf)
        result = simulate(child)
        backpropagate(child, result)
    return best_child(root)

function select(node):
    while node is fully expanded and not terminal:
        node = best_uct_child(node)
    return node

function expand(node):
    if node is terminal:
        return node
    else:
        return add_random_untried_child(node)

function simulate(node):
    while not terminal(node):
        node = select_random_action(node)
    return outcome(node)

function backpropagate(node, result):
    while node != null:
        node.visits += 1
        node.wins += result
        node = node.parent

struct Node {
    State state;
    Node* parent;
    std::vector<Node*> children;
    int wins = 0, visits = 0;
    std::vector<Action> untriedMoves;
};

Node* select(Node* node) {
    while (!node->untriedMoves.empty() && !isTerminal(node->state)) {
        node = bestUCTChild(node);
    }
    return node;
}

// expand, simulate, backpropagate stb. ugyanígy

A Monte Carlo Tree Search egy rendkívül erős és adaptív algoritmus, amely megtalálta helyét az MI világában. Azáltal, hogy a tapasztalati tanulást és a keresést kombinálja, képes komplex, nem determinisztikus környezetekben is jó döntéseket hozni.

• Ha a probléma túl nagy egy teljes kereséshez,
• Ha nem áll rendelkezésre tökéletes modell,
• Ha sztochasztikus környezetben kell döntést hozni,

akkor az MCTS kiváló választás lehet.

• Monte Carlo tree search - Szótár.net (en-hu)
• Monte Carlo tree search - Sztaki (en-hu)
• Monte Carlo tree search - Merriam–Webster
• Monte Carlo tree search - Cambridge
• Monte Carlo tree search - WordNet
• Monte Carlo tree search - Яндекс (en-ru)
• Monte Carlo tree search - Google (en-hu)
• Monte Carlo tree search - Wikidata
• Monte Carlo tree search - Wikipédia (angol)