Erweiterte Erkundung in Monte-Carlo-Baum-Suche durch Fokussierung auf das Unbekannte

Die Monte-Carlo-Baum-Suche (MCTS) ist ein effektiver Anytime-Algorithmus mit einer Vielzahl von Anwendungen. Sie weist rechnerische Ressourcen strategisch zu, um sich auf vielversprechende Segmente des Suchbaums zu konzentrieren, wodurch sie ein sehr attraktiver Suchalgorithmus in großen Suchräumen ist. Allerdings verwendet sie oft ihre begrenzten Ressourcen zur Neubewertung zuvor erkundeter Regionen, wenn diese den vielversprechendsten Pfad darstellen. Unsere vorgeschlagene Methodologie, die als AmEx-MCTS bezeichnet wird, löst dieses Problem durch die Einführung einer neuartigen MCTS-Formulierung. Zentral für AmEx-MCTS ist die Entkopplung von Wertaktualisierungen, Besuchszählaktualisierungen und dem ausgewählten Pfad während der Baumsuche, wodurch die Ausschluss von bereits erkundeten Teilbäumen oder Blättern ermöglicht wird. Diese Trennung bewahrt den Nutzen der Besuchszahlen sowohl für das Gleichgewicht zwischen Exploration und Exploitation als auch für Qualitätsmetriken innerhalb der MCTS. Die resultierende Erweiterung ermöglicht eine erheblich breitere Suche unter Verwendung identischer rechnerischer Ressourcen und bewahrt die wesentlichen Merkmale der MCTS. Die erweiterte Abdeckung liefert nicht nur genauere Schätzungen, sondern erweist sich auch als äußerst hilfreich bei größeren und komplexeren Problemen. Unsere empirische Bewertung zeigt die überlegene Leistung von AmEx-MCTS, die die klassische MCTS und verwandte Ansätze erheblich übertrifft.