Monte-Carlo-fakeresés

Magyar

Kiejtés

• IPA: [ ˈmontɛt͡sɒrlofɒkɛrɛʃeːʃ]

Főnév

Monte-Carlo-fakeresés

1. (matematika, algoritmusok)

Monte-Carlo-fakeresés (Monte Carlo Tree Search, MCTS)

Definíció

A **Monte-Carlo-fakeresés (MCTS)** egy sztochasztikus keresési algoritmus, amelyet döntési problémákban, különösen játékokban használnak. Az algoritmus egy döntési fát épít, és szimulációk segítségével értékeli a lehetséges lépéseket, hogy meghatározza az optimális stratégiát.

Fő Lépések

Az MCTS négy fő lépésből áll, amelyeket iteratívan hajt végre:

1. Kiválasztás (Selection):

  Kezdés az aktuális gyökércsúcsból. A már meglátogatott csúcsokon belül egy „legjobb” gyermeket választunk ki az **UCT (Upper Confidence Bound for Trees)** formulával:  
  $UCT(v)={\frac {w_{i}}{n_{i}}}+C{\sqrt {\frac {\ln N}{n_{i}}}}$  
  ahol:
  * $w_{i}$: Az $i$-edik csúcs nyeresége.
  * $n_{i}$: Az $i$-edik csúcs látogatásainak száma.
  * $N$: Az aktuális csúcs látogatásainak száma.
  * $C$: Egy állandó, amely az explorációt szabályozza.

1. Bővítés (Expansion):

  Ha egy kiválasztott csúcs nincs teljesen kifejtve, bővítjük egy új gyermekcsúccsal, amely egy lehetséges lépést reprezentál.

1. Szimuláció (Simulation):

  Véletlenszerűen játszuk le a játékot a bővített csúcsból kiindulva. A végeredmény alapján becslést készítünk a lépés hasznosságáról.

1. Visszaterjesztés (Backpropagation):

  A szimuláció eredményét visszaterjesztjük a döntési fán, frissítve a látogatások és a nyereségek számát az érintett csúcsokon.

Előnyök

• Nem igényel előzetes tudást a problémáról, csak a szimulációk eredményeit használja.
• Hatékony nagy állapottérrel rendelkező problémák esetén.

Python Implementáció

Az alábbi példa bemutatja az MCTS algoritmus alapvető implementációját egy absztrakt döntési problémára.

import math
import random

class Node:
    def __init__(self, state, parent=None):
        self.state = state
        self.parent = parent
        self.children = []
        self.visits = 0
        self.wins = 0

    def is_fully_expanded(self):
        return len(self.children) > 0

    def best_child(self, exploration_weight=1.4):
        # UCT formula alkalmazása
        return max(
            self.children,
            key=lambda child: child.wins / (child.visits + 1e-6) +
            exploration_weight * math.sqrt(math.log(self.visits + 1) / (child.visits + 1e-6))
        )

    def expand(self, child_state):
        child = Node(state=child_state, parent=self)
        self.children.append(child)
        return child

    def update(self, result):
        self.visits += 1
        self.wins += result


def mcts(root, iterations, simulate):
    """
    Monte Carlo Tree Search.

    Args:
        root: A döntési fa gyökércsúcsa.
        iterations: Az MCTS iterációinak száma.
        simulate: Szimulációs függvény, amely meghatározza a játék eredményét egy adott állapotból.

    Returns:
        A legjobb gyermekcsúcs az MCTS alapján.
    """
    for _ in range(iterations):
        # 1. Kiválasztás
        node = root
        while node.is_fully_expanded() and node.children:
            node = node.best_child()

        # 2. Bővítés
        if not node.is_fully_expanded():
            new_state = random.choice(generate_possible_states(node.state))
            node = node.expand(new_state)

        # 3. Szimuláció
        result = simulate(node.state)

        # 4. Visszaterjesztés
        while node is not None:
            node.update(result)
            node = node.parent

    return root.best_child(exploration_weight=0)  # Legjobb gyermek kiválasztása


def generate_possible_states(state):
    """
    Példafüggvény: generálja a lehetséges következő állapotokat.
    """
    # Itt helyettesítsd a problémádhoz illő állapotgenerálással
    return [state + random.randint(1, 10)]


def simulate(state):
    """
    Példafüggvény: visszaadja a szimuláció végeredményét.
    """
    # Itt helyettesítsd a problémádhoz illő szimulációval
    return random.choice([0, 1])  # Győzelem vagy vereség


# Példa használat
initial_state = 0
root = Node(state=initial_state)

best_move = mcts(root, iterations=1000, simulate=simulate)
print("Legjobb lépés állapota:", best_move.state)

Alkalmazások

1. Játékok:

  * Olyan játékokban, mint a Go, sakk, vagy Othello, ahol hatalmas állapottérrel dolgozunk.
  * Példa: Az **AlphaGo** mesterséges intelligencia a Monte-Carlo-fakeresést használta.

1. Adatfeldolgozás:

  Heurisztikus keresés optimalizálási problémákban.

1. Mesterséges intelligencia:

  Szimuláció-alapú döntéshozatal.

1. Robotika:

  Mozgástervezési problémák sztochasztikus környezetben.

Összegzés

A Monte-Carlo-fakeresés egy hatékony algoritmus komplex problémák megoldására, különösen akkor, ha a probléma strukturált, de determinisztikus megoldás nem érhető el. Pythonban könnyen implementálható, és szimulációs környezetekben jól alkalmazható. Az MCTS nagy előnye, hogy az exploráció és az exploitáció közötti egyensúlyt dinamikusan szabályozza az UCT formula segítségével.

Fordítások

Tartalom

angol: Monte Carlo tree search (en)

További információk

• Monte-Carlo-fakeresés - Értelmező szótár (MEK)
• Monte-Carlo-fakeresés - Etimológiai szótár (UMIL)
• Monte-Carlo-fakeresés - Szótár.net (hu-hu)
• Monte-Carlo-fakeresés - DeepL (hu-de)
• Monte-Carlo-fakeresés - Яндекс (hu-ru)
• Monte-Carlo-fakeresés - Google (hu-en)
• Monte-Carlo-fakeresés - Helyesírási szótár (MTA)
• Monte-Carlo-fakeresés - Wikidata
• Monte-Carlo-fakeresés - Wikipédia (magyar)