mcts
1.0.0
En este tutorial explicaremos el algoritmo de búsqueda de árboles de Monte Carlo y cada parte del código. Recientemente aplicamos MCTS para desarrollar nuestro juego.
El código es general y sólo supone familiaridad con Python básico. Lo hemos explicado con respecto a nuestro juego. Si quieres usarlo para tu proyecto o juego, tendrás que modificar ligeramente las funciones que mencioné a continuación.
Aquí está el enlace de la tienda de juegos al juego: Sudo Tic Tac Toe.
Las reglas de nuestro juego (modo 1) son las siguientes:
Como habrás visto, este juego tiene un factor de ramificación muy alto. Para el primer movimiento, todo el tablero está vacío. Entonces hay 81 espacios vacíos. Para el primer turno tiene 81 movimientos posibles. Para el segundo turno aplicando la regla 4 tiene 8 o 9 movimientos posibles.
Para los primeros 2 movimientos, esto da como resultado 81*9 = 729 combinaciones posibles. Por tanto, el número de combinaciones posibles aumenta a medida que avanza el juego, lo que da como resultado un factor de ramificación elevado. Para ambos modos de nuestro juego, el factor de ramificación es muy alto. Para juegos con un factor de ramificación tan alto no es posible aplicar el algoritmo minimax. El algoritmo MCTS funciona para este tipo de juegos.
Además, como habrás visto al jugar, el tiempo que le toma a la IA hacer un movimiento es aproximadamente un segundo. Por tanto, MCTS funciona rápido. MCTS se ha aplicado a ambos modos del juego.
A continuación demostramos el código MCTS en Python. Primero necesitamos importar numpy y defaultdict.
import numpy as np
from collections import defaultdictDefina la clase MCTS como se muestra a continuación.
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 ()
returnLa clase consta de las siguientes funciones miembro. Todas las funciones siguientes son funciones miembro excepto la función main().
def untried_actions ( self ):
self . _untried_actions = self . state . get_legal_actions ()
return self . _untried_actionsDevuelve la lista de acciones no intentadas de un estado determinado. Para el primer turno de nuestro juego hay 81 acciones posibles. Para el segundo turno es 8 o 9. Esto varía en nuestro juego.
def q ( self ):
wins = self . _results [ 1 ]
loses = self . _results [ - 1 ]
return wins - losesDevuelve la diferencia de victorias - derrotas
def n ( self ):
return self . _number_of_visitsDevuelve el número de veces que se visita cada nodo.
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 A partir del estado actual se genera el siguiente estado dependiendo de la acción que se realice. En este paso, todos los estados posibles se agregan a la matriz secundaria y se devuelve el nodo_infantil. Todos los estados que son posibles a partir del estado actual se agregan a la matriz secundaria y se devuelve el nodo_infantil correspondiente a este estado.
def is_terminal_node ( self ):
return self . state . is_game_over ()Esto se utiliza para comprobar si el nodo actual es terminal o no. Se alcanza el nodo terminal cuando termina el juego.
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 ()A partir del estado actual, se simula todo el juego hasta que se obtiene un resultado. Este resultado del juego se devuelve. Por ejemplo, si resulta en una victoria, el resultado es 1. De lo contrario, es -1 si resulta en una pérdida. Y es 0 si hay empate. Si todo el juego se simula aleatoriamente, es decir, en cada turno, el movimiento se selecciona aleatoriamente de un conjunto de movimientos posibles, se denomina juego ligero.
def backpropagate ( self , result ):
self . _number_of_visits += 1.
self . _results [ result ] += 1.
if self . parent :
self . parent . backpropagate ( result )En este paso se actualizan todas las estadísticas de los nodos. Hasta que se alcanza el nodo principal, el número de visitas para cada nodo se incrementa en 1. Si el resultado es 1, es decir, resultó en una ganancia, entonces la ganancia se incrementa en 1. De lo contrario, si el resultado es una pérdida, entonces se pierde. se incrementa en 1.
def is_fully_expanded ( self ):
return len ( self . _untried_actions ) == 0Todas las acciones surgen de _untried_actions una por una. Cuando queda vacío, es decir, cuando el tamaño es cero, se expande por completo.
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 )]Una vez completamente expandida, esta función selecciona al mejor hijo de la matriz de hijos. El primer término de la fórmula corresponde a explotación y el segundo término corresponde a exploración.
def rollout_policy ( self , possible_moves ):
return possible_moves [ np . random . randint ( len ( possible_moves ))]Selecciona aleatoriamente un movimiento entre posibles movimientos. Este es un ejemplo de reproducción aleatoria.
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_nodeSelecciona el nodo para ejecutar la implementación.
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. )Esta es la función de mejor acción que devuelve el nodo correspondiente al mejor movimiento posible. Los pasos de expansión, simulación y retropropagación se llevan a cabo mediante el código anterior.
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 Esta es la función principal(). Inicialice el nodo raíz y llame a la función best_action para obtener el mejor nodo. Esta no es una función miembro de la clase. Todas las demás funciones son funciones miembro de la clase.
MCTS consta de 4 pasos:
La idea es seguir seleccionando los mejores nodos secundarios hasta llegar al nodo hoja del árbol. Una buena forma de seleccionar dicho nodo secundario es utilizar la fórmula UCT (límite de confianza superior aplicado a los árboles):
wi/ni + c*sqrt(t)/ni
wi = número de victorias después del i-ésimo movimiento
ni = número de simulaciones después del i-ésimo movimiento
c = parámetro de exploración (teóricamente igual a √2)
t = número total de simulaciones para el nodo principal
Cuando ya no puede aplicar UCT para encontrar el nodo sucesor, expande el árbol del juego agregando todos los estados posibles del nodo hoja.
Después de la expansión, el algoritmo elige un nodo secundario arbitrariamente y simula el juego completo desde el nodo seleccionado hasta que alcanza el estado resultante del juego. Si los nodos se seleccionan aleatoriamente durante la reproducción, se denomina reproducción ligera. También puede optar por un juego intenso escribiendo heurísticas de calidad o funciones de evaluación.
Una vez que el algoritmo llega al final del juego, evalúa el estado para determinar qué jugador ganó. Atraviesa la raíz e incrementa la puntuación de visita de todos los nodos visitados. También actualiza la puntuación de victorias para cada nodo si el jugador de esa posición ganó el playout.
Si planeas crear tu propio juego, tendrás que pensar en las siguientes preguntas.
Sudo tres en raya
Si tiene alguna pregunta o sugerencia, no dude en contactarnos en [email protected]
