EMZETT.Suchverfahren und Planung: A* und Monte-Carlo-Baumsuche
Kurz: Planen heißt: aus vielen möglichen Handlungsfolgen eine gute finden. Dafür gibt es klassische Suchverfahren wie A* und die Monte-Carlo-Baumsuche, die auch hinter Spiele-KI steckt.
A* (A-Stern)
A* findet den kürzesten Weg in einem Graphen, zum Beispiel auf einer Karte. Für jeden Knoten wird bewertet:
f(n) = g(n) + h(n)
g(n): bisherige Kosten vom Start.h(n): geschätzte Restkosten bis zum Ziel (die Heuristik, zum Beispiel Luftlinie).
A* untersucht immer den Knoten mit dem kleinsten f. Ist die Heuristik nie zu optimistisch, ist der gefundene Weg garantiert der kürzeste. Siehe auch Dijkstra-Algorithmus (A* ohne Heuristik).
Monte-Carlo-Baumsuche (MCTS)
Bei Spielen mit riesigem Zustandsraum geht vollständiges Durchsuchen nicht. MCTS baut einen Suchbaum Schritt für Schritt auf, in vier Phasen:
- Auswahl: vom Startzustand zu einem vielversprechenden Blatt hinabgehen (Balance aus Ausprobieren und Ausnutzen, Regel UCT).
- Erweiterung: einen neuen Zug hinzufügen.
- Simulation: das Spiel mit zufälligen oder gelernten Zügen zu Ende spielen.
- Rückmeldung: das Ergebnis entlang des Pfads nach oben zurückgeben.
Nach vielen Wiederholungen ist der am häufigsten besuchte Zug der beste.
Mit neuronalen Netzen
Moderne Systeme ersetzen die zufällige Simulation und die Zugauswahl durch Netze, die Stellungen bewerten. Das ist der Kern von AlphaGo, siehe Spiele-KI: Schach, Go und Poker.
Siehe auch: Breitensuche und Tiefensuche (BFS und DFS), Verstärkungslernen (Reinforcement Learning)