Monte-Carlo-Baum Suchen der UCT-Implementierung

Können Sie mir erklären, wie zu bauen, der Baum?

Ich ganz verstanden, wie die Knoten ausgewählt werden, aber eine schönere Erklärung würde mir wirklich helfen, die Umsetzung dieses Algorithmus. Ich habe bereits ein Brett, die das Spiel Stand, aber ich weiß nicht, (verstehen), wie zu generieren der Baum.

Kann jemand mir eine gut kommentierte Implementierung des Algorithmus (ich brauche es für die KI)? Oder besser Erläuterung/Beispiele dafür?

Habe ich nicht gefunden, eine Menge von Ressourcen auf dem Netz, ist dieser Algorithmus ist Recht neu...

InformationsquelleAutor der Frage Makers_F | 2012-01-29

  1. 23

    Den besten Weg zu erzeugen, der Baum ist eine Reihe von zufälligen playouts. Der trick ist, in der Lage, um die balance zwischen exploration und exploitation (dies ist, wo die UCT kommt). Es gibt einige gute code-Beispiele und viel der Forschung Papier-Referenzen hier : https://web.archive.org/web/20160308043415/http://mcts.ai:80/index.html

    Wenn ich implementiert den Algorithmus, den ich verwendet zufällige playouts, bis ich auf einen Endpunkt oder eine Kündigung Zustand. Ich hatte eine statische Auswertung-Funktion, die die Berechnung der Belohnung an diesem Punkt, dann das Ergebnis von dieser Stelle weitergegeben wird, zurück auf den Baum. Jeder Spieler oder "team" meint, dass das andere team spielen wird der beste Zug für sich, und das Schlimmste, bewegen Sie möglich für Ihre Gegner.

    Ich würde auch empfehlen die überprüfung der Papiere durch Chaslot und seine phd-Arbeit sowie einige der Forschung, die Referenzen seiner Arbeit (im Grunde alle die MCTS arbeiten seitdem).

    Zum Beispiel: Spieler 1 die erste Bewegung könnte simulieren, 10 Züge in der Zukunft abwechselnd Spieler 1 bewegt und Spieler 2 bewegt. Jedes mal, wenn Sie davon ausgehen müssen, dass der gegnerische Spieler werden versuchen, Sie zu minimieren Sie Ihre Kerbe, während die Maximierung Ihrer eigenen Partitur. Es gibt ein ganzes Feld auf der Basis dieses bekannt als Spiel-Theorie. Sobald Sie simulieren, um das Ende der 10 Spiele, die Sie Durchlaufen vom Startpunkt wieder (weil es keinen Punkt gibt, nur die Simulation einer Reihe von Entscheidungen). Jeder dieser Zweige des Baumes muss bewertet werden wo die Gäste weitergegeben wird, bis der Baum und der score stellt die bestmögliche Belohnung für die Spieler tun die Simulation unter der Annahme, dass der andere Spieler auch die Wahl der besten Züge für sich.

    MCTS besteht aus vier strategischen Schritte, die solange wiederholt wie es ist Zeit übrig. Die Schritte sind wie folgt.

    1. In der Auswahl Schritt die Struktur ist durchzogen von der
      root-Knoten bis zu einem Knoten E, in denen wir wählen Sie eine position, die nicht Hinzugefügt, um den Baum noch.

    2. Nächsten, während der play-out Schritt bewegt werden gespielt, im sich-selbst-spielen, bis das Ende des Spiels erreicht ist. Das Ergebnis R von diesem "simulierten" Spiel ist +1 im Fall von einem Gewinn für Schwarz (der erste Spieler, der im LOA), 0 im Falle eines Unentschieden, und -1 im Fall von einem Gewinn für Weiß.

    3. Später, in den Schritt der expansion Kinder E werden dem Baum Hinzugefügt.

    4. Endlich, R ist vermehrt zurück auf dem Pfad von E zu den root-Knoten im backpropagation Schritt. Wenn die Zeit abgelaufen ist, die bewegen, spielt das Programm ist Kind der Wurzel mit dem höchsten Wert.
      (Dieses Beispiel stammt aus diesem Papier - PDF

    http://www.ru.is/faculty/yngvi/pdf/WinandsBS08.pdf

    Hier sind einige Implementierungen:

    Einer Liste von Bibliotheken und Spiele, die mit einigen MCTS-Implementierungen
    http://senseis.xmp.net/?MonteCarloTreeSearch

    ist und ein Spiel unabhängige open-source-Produkt MCTS-Bibliothek namens Fuego
    http://fuego.sourceforge.net/fuego-doc-1.1/smartgame-doc/group__sguctgroup.html

    InformationsquelleAutor der Antwort danielbeard

  2. 3

    Vom http://mcts.ai/code/index.html:

    Below are links to some basic MCTS implementations in various
programming languages. The listings are shown with timing, testing
and debugging code removed for readability.

    Java

    Python

    InformationsquelleAutor der Antwort Thomas Ahle

  3. 2

    Schrieb ich das man wenn man interresiert : https://github.com/avianey/mcts4j

    InformationsquelleAutor der Antwort avianey

Schreibe einen Kommentar