mcts
1.0.0
In diesem Tutorial erklären wir den Monte-Carlo-Baumsuchalgorithmus und jeden Teil des Codes. Kürzlich haben wir MCTS zur Entwicklung unseres Spiels eingesetzt.
Der Code ist allgemein gehalten und setzt lediglich Vertrautheit mit grundlegendem Python voraus. Wir haben es in Bezug auf unser Spiel erklärt. Wenn Sie es für Ihr Projekt oder Spiel verwenden möchten, müssen Sie die unten genannten Funktionen leicht modifizieren.
Hier ist der Playstore-Link zum Spiel: Sudo Tic Tac Toe.
Die Regeln für unser Spiel (Modus 1) lauten wie folgt:
Wie Sie gesehen haben, hat dieses Spiel einen sehr hohen Verzweigungsfaktor. Beim ersten Zug ist das gesamte Spielbrett leer. Es gibt also 81 freie Plätze. Für die erste Runde stehen ihm 81 mögliche Züge zur Verfügung. Für die zweite Runde hat er bei Anwendung von Regel 4 8 oder 9 mögliche Züge.
Für die ersten 2 Züge ergeben sich somit 81*9 = 729 mögliche Kombinationen. Dadurch steigt die Zahl der möglichen Kombinationen im Laufe des Spiels, was zu einem hohen Verzweigungsfaktor führt. Für beide Modi unseres Spiels ist der Verzweigungsfaktor sehr hoch. Bei Spielen mit einem so hohen Verzweigungsfaktor ist es nicht möglich, den Minimax-Algorithmus anzuwenden. Der MCTS-Algorithmus funktioniert für diese Art von Spielen.
Wie Sie beim Spielen des Spiels gesehen haben, beträgt die Zeit, die die KI für einen Zug benötigt, nur etwa eine Sekunde. Somit läuft MCTS schnell. MCTS wurde auf beide Spielmodi angewendet.
Nachfolgend demonstrieren wir den MCTS-Code in Python. Zuerst müssen wir Numpy und Defaultdict importieren.
import numpy as np
from collections import defaultdictDefinieren Sie die MCTS-Klasse wie unten gezeigt.
class MonteCarloTreeSearchNode ():
def __init__ ( self , state , parent = None , parent_action = None ):
self . state = state
self . parent = parent
self . parent_action = parent_action
self . children = []
self . _number_of_visits = 0
self . _results = defaultdict ( int )
self . _results [ 1 ] = 0
self . _results [ - 1 ] = 0
self . _untried_actions = None
self . _untried_actions = self . untried_actions ()
returnDie Klasse besteht aus den folgenden Mitgliedsfunktionen. Alle unten aufgeführten Funktionen sind Mitgliedsfunktionen mit Ausnahme der Funktion main().
def untried_actions ( self ):
self . _untried_actions = self . state . get_legal_actions ()
return self . _untried_actionsGibt die Liste der nicht versuchten Aktionen aus einem bestimmten Zustand zurück. Für die erste Runde unseres Spiels gibt es 81 mögliche Aktionen. Für die zweite Runde ist es 8 oder 9. Das variiert in unserem Spiel.
def q ( self ):
wins = self . _results [ 1 ]
loses = self . _results [ - 1 ]
return wins - losesGibt die Differenz zwischen Gewinnen und Verlusten zurück
def n ( self ):
return self . _number_of_visitsGibt die Häufigkeit zurück, mit der jeder Knoten besucht wird.
def expand ( self ):
action = self . _untried_actions . pop ()
next_state = self . state . move ( action )
child_node = MonteCarloTreeSearchNode (
next_state , parent = self , parent_action = action )
self . children . append ( child_node )
return child_node Aus dem aktuellen Zustand wird abhängig von der durchgeführten Aktion der nächste Zustand generiert. In diesem Schritt werden alle möglichen Zustände an das Children-Array angehängt und der child_node zurückgegeben. Die aus dem aktuellen Zustand möglichen Zustände werden alle an das Children-Array angehängt und der diesem Zustand entsprechende child_node zurückgegeben.
def is_terminal_node ( self ):
return self . state . is_game_over ()Dies wird verwendet, um zu überprüfen, ob der aktuelle Knoten ein Terminal ist oder nicht. Der Endknoten wird erreicht, wenn das Spiel beendet ist.
def rollout ( self ):
current_rollout_state = self . state
while not current_rollout_state . is_game_over ():
possible_moves = current_rollout_state . get_legal_actions ()
action = self . rollout_policy ( possible_moves )
current_rollout_state = current_rollout_state . move ( action )
return current_rollout_state . game_result ()Vom aktuellen Stand aus wird das gesamte Spiel simuliert, bis es ein Ergebnis für das Spiel gibt. Dieses Ergebnis des Spiels wird zurückgegeben. Wenn es beispielsweise zu einem Sieg kommt, ist das Ergebnis 1. Ansonsten ist es -1, wenn es zu einer Niederlage führt. Und es ist 0, wenn es ein Unentschieden ist. Wenn das gesamte Spiel zufällig simuliert wird, das heißt, in jeder Runde wird der Zug zufällig aus der Menge möglicher Züge ausgewählt, spricht man von einem leichten Playout.
def backpropagate ( self , result ):
self . _number_of_visits += 1.
self . _results [ result ] += 1.
if self . parent :
self . parent . backpropagate ( result )In diesem Schritt werden alle Statistiken für die Knoten aktualisiert. Bis der übergeordnete Knoten erreicht ist, wird die Anzahl der Besuche für jeden Knoten um 1 erhöht. Wenn das Ergebnis 1 ist, also zu einem Sieg geführt hat, wird der Gewinn um 1 erhöht. Andernfalls, wenn das Ergebnis ein Verlust ist, dann Verlust wird um 1 erhöht.
def is_fully_expanded ( self ):
return len ( self . _untried_actions ) == 0Alle Aktionen werden nacheinander aus _untried_actions entfernt. Wenn es leer wird, das heißt, wenn die Größe Null ist, ist es vollständig erweitert.
def best_child ( self , c_param = 0.1 ):
choices_weights = [( c . q () / c . n ()) + c_param * np . sqrt (( 2 * np . log ( self . n ()) / c . n ())) for c in self . children ]
return self . children [ np . argmax ( choices_weights )]Sobald diese Funktion vollständig erweitert ist, wählt sie das beste untergeordnete Element aus dem untergeordneten Array aus. Der erste Term in der Formel entspricht der Ausbeutung und der zweite Term entspricht der Erkundung.
def rollout_policy ( self , possible_moves ):
return possible_moves [ np . random . randint ( len ( possible_moves ))]Wählt zufällig einen Zug aus möglichen Zügen aus. Dies ist ein Beispiel für eine zufällige Ausspielung.
def _tree_policy ( self ):
current_node = self
while not current_node . is_terminal_node ():
if not current_node . is_fully_expanded ():
return current_node . expand ()
else :
current_node = current_node . best_child ()
return current_nodeWählt den Knoten aus, um den Rollout auszuführen.
def best_action ( self ):
simulation_no = 100
for i in range ( simulation_no ):
v = self . _tree_policy ()
reward = v . rollout ()
v . backpropagate ( reward )
return self . best_child ( c_param = 0. )Dies ist die beste Aktionsfunktion, die den Knoten zurückgibt, der der bestmöglichen Bewegung entspricht. Die Schritte der Erweiterung, Simulation und Backpropagation werden durch den obigen Code ausgeführt.
def get_legal_actions ( self ):
'''
Modify according to your game or
needs. Constructs a list of all
possible states from current state.
Returns a list.
''' def is_game_over ( self ):
'''
Modify according to your game or
needs. It is the game over condition
and depends on your game. Returns
true or false
''' def game_result ( self ):
'''
Modify according to your game or
needs. Returns 1 or 0 or -1 depending
on your state corresponding to win,
tie or a loss.
''' def move ( self , action ):
'''
Modify according to your game or
needs. Changes the state of your
board with a new value. For a normal
Tic Tac Toe game, it can be a 3 by 3
array with all the elements of array
being 0 initially. 0 means the board
position is empty. If you place x in
row 2 column 3, then it would be some
thing like board[2][3] = 1, where 1
represents that x is placed. Returns
the new state after making a move.
''' def main ():
root = MonteCarloTreeSearchNode ( state , None , action )
selected_node = root . best_action ()
return Dies ist die Funktion main(). Initialisieren Sie den Wurzelknoten und rufen Sie die Funktion best_action auf, um den besten Knoten zu erhalten. Dies ist keine Mitgliedsfunktion der Klasse. Alle anderen Funktionen sind Mitgliedsfunktionen der Klasse.
MCTS besteht aus 4 Schritten:
Die Idee besteht darin, so lange die besten untergeordneten Knoten auszuwählen, bis wir den Blattknoten des Baums erreichen. Eine gute Möglichkeit, einen solchen untergeordneten Knoten auszuwählen, ist die Verwendung der UCT-Formel (Upper Confidence Bound Applied to Trees):
wi/ni + c*sqrt(t)/ni
wi = Anzahl der Siege nach dem i-ten Zug
ni = Anzahl der Simulationen nach dem i-ten Zug
c = Explorationsparameter (theoretisch gleich √2)
t = Gesamtzahl der Simulationen für den übergeordneten Knoten
Wenn UCT nicht mehr angewendet werden kann, um den Nachfolgeknoten zu finden, erweitert es den Spielbaum, indem es alle möglichen Zustände vom Blattknoten anhängt.
Nach der Erweiterung wählt der Algorithmus willkürlich einen untergeordneten Knoten aus und simuliert das gesamte Spiel vom ausgewählten Knoten bis zum Erreichen des resultierenden Spielzustands. Wenn während des Ausspielens zufällig Knoten ausgewählt werden, spricht man von einem leichten Ausspielen. Sie können sich auch für eine umfassende Auslastung entscheiden, indem Sie hochwertige Heuristiken oder Bewertungsfunktionen schreiben.
Sobald der Algorithmus das Ende des Spiels erreicht, wertet er den Status aus, um herauszufinden, welcher Spieler gewonnen hat. Es wandert nach oben zum Stamm und erhöht die Besuchsbewertung für alle besuchten Knoten. Außerdem wird die Siegpunktzahl für jeden Knoten aktualisiert, wenn der Spieler für diese Position das Playout gewonnen hat.
Wenn Sie vorhaben, Ihr eigenes Spiel zu entwickeln, müssen Sie über die folgenden Fragen nachdenken.
Sudo Tic Tac Toe
Wenn Sie Fragen oder Anregungen haben, können Sie uns gerne unter [email protected] kontaktieren
