mcts

Tutoriel sur l'algorithme Monte Carlo Tree Search (MCTS) avec du code Python. Application de MCTS pour créer une IA pour un jeu simple.

Dans ce didacticiel, nous expliquerons l'algorithme de recherche arborescente de Monte Carlo et chaque partie du code. Récemment, nous avons appliqué MCTS pour développer notre jeu.

Le code est général et suppose uniquement une connaissance de Python de base. Nous l'avons expliqué par rapport à notre jeu. Si vous souhaitez l'utiliser pour votre projet ou jeu, vous devrez modifier légèrement les fonctions que j'ai évoquées ci-dessous.

Voici le lien playstore vers le jeu : Sudo Tic Tac Toe.

Les règles de notre jeu (mode 1) sont les suivantes :

1. Le jeu se joue sur une grille de 9 par 9 comme le Sudoku.
2. Cette grande grille 9 par 9 est divisée en 9 grilles plus petites 3 par 3 (tableau local).
3. Le but du jeu est de gagner n'importe quel plateau local parmi les 9 disponibles.
4. Votre mouvement détermine sur quel plateau local l’IA doit agir et vice versa.
5. Par exemple, vous effectuez un mouvement en position 1 du plateau local numéro 5. Cela forcera l'IA à effectuer un mouvement sur le plateau local numéro 1.
6. Les règles du Tic Tac Toe normal sont appliquées au tableau local.

Pourquoi MCTS ?

Comme vous l'avez peut-être vu, ce jeu a un facteur de branchement très élevé. Pour le premier coup, tout le plateau est vide. Il y a donc 81 places vides. Pour le premier tour, il y a 81 mouvements possibles. Pour le deuxième tour en appliquant la règle 4 il a 8 ou 9 coups possibles.

Pour les 2 premiers coups, cela donne 81*9 = 729 combinaisons possibles. Ainsi, le nombre de combinaisons possibles augmente à mesure que le jeu progresse, ce qui entraîne un facteur de branchement élevé. Pour les deux modes de jeu, le facteur de branchement est très élevé. Pour les jeux avec un facteur de branchement aussi élevé, il n'est pas possible d'appliquer l'algorithme minimax. L'algorithme MCTS fonctionne pour ce genre de jeux.

De plus, comme vous l'aurez constaté en jouant au jeu, le temps nécessaire à l'IA pour agir n'est que d'environ une seconde. Ainsi, MCTS fonctionne rapidement. MCTS a été appliqué aux deux modes de jeu.

Ci-dessous, nous démontrons le code MCTS en Python. Nous devons d’abord importer numpy et defaultdict.

 import numpy as np
from collections import defaultdict

Définissez la classe MCTS comme indiqué ci-dessous.

 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 ()
        return

Le constructeur est utilisé pour initialiser les variables suivantes.

• state : Pour notre jeu, il représente l’état du plateau. Généralement, l'état de la carte est représenté par un tableau. Pour un Tic Tac Toe normal, il s'agit d'un tableau de 3 x 3.
• parent : Il vaut None pour le nœud racine et pour les autres nœuds, il est égal au nœud dont il est dérivé. Pour le premier tour, comme vous l'avez vu dans le jeu, c'est Aucun.
• children : Il contient toutes les actions possibles du nœud actuel. Pour le deuxième tour de notre jeu, c'est 9 ou 8 selon l'endroit où vous effectuez votre déplacement.
• parent_action : Aucun pour le nœud racine et pour les autres nœuds il est égal à l'action effectuée par son parent.
• _number_of_visits : Nombre de fois que le nœud actuel est visité
• résultats : C'est un dictionnaire
• _untried_actions : Représente la liste de toutes les actions possibles
• action : Déplacement qui doit être effectué.

La classe comprend les fonctions membres suivantes. Toutes les fonctions ci-dessous sont des fonctions membres à l'exception de la fonction main().

 def untried_actions ( self ):

    self . _untried_actions = self . state . get_legal_actions ()
    return self . _untried_actions

Renvoie la liste des actions non tentées à partir d'un état donné. Pour le premier tour de notre jeu il y a 81 actions possibles. Pour le deuxième tour, c'est 8 ou 9. Cela varie selon notre jeu.

 def q ( self ):
    wins = self . _results [ 1 ]
    loses = self . _results [ - 1 ]
    return wins - loses

Renvoie la différence entre les victoires et les pertes

 def n ( self ):
    return self . _number_of_visits

Renvoie le nombre de fois que chaque nœud est visité.

 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 de l'état présent, l'état suivant est généré en fonction de l'action effectuée. Dans cette étape, tous les états possibles sont ajoutés au tableau children et le child_node est renvoyé. Les états possibles à partir de l'état actuel sont tous ajoutés au tableau children et le child_node correspondant à cet état est renvoyé.

 def is_terminal_node ( self ):
    return self . state . is_game_over ()

Ceci est utilisé pour vérifier si le nœud actuel est terminal ou non. Le nœud terminal est atteint lorsque le jeu est terminé.

 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 ()

À partir de l’état actuel, le jeu entier est simulé jusqu’à ce qu’il y ait un résultat pour le jeu. Ce résultat du jeu est renvoyé. Par exemple, s’il en résulte une victoire, le résultat est 1. Sinon, il est de -1 s’il en résulte une perte. Et c'est 0 en cas d'égalité. Si l'ensemble du jeu est simulé de manière aléatoire, c'est-à-dire qu'à chaque tour le mouvement est sélectionné au hasard parmi un ensemble de mouvements possibles, on parle alors de jeu léger.

 def backpropagate ( self , result ):
    self . _number_of_visits += 1.
    self . _results [ result ] += 1.
    if self . parent :
        self . parent . backpropagate ( result )

Au cours de cette étape, toutes les statistiques des nœuds sont mises à jour. Jusqu'à ce que le nœud parent soit atteint, le nombre de visites pour chaque nœud est incrémenté de 1. Si le résultat est 1, c'est-à-dire qu'il en résulte une victoire, alors la victoire est incrémentée de 1. Sinon, si le résultat est une perte, alors la perte est incrémenté de 1.

 def is_fully_expanded ( self ):
    return len ( self . _untried_actions ) == 0

Toutes les actions sont extraites de _untried_actions une par une. Lorsqu'il devient vide, c'est-à-dire lorsque la taille est nulle, il est entièrement développé.

 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 )]

Une fois entièrement développée, cette fonction sélectionne le meilleur enfant parmi le tableau des enfants. Le premier terme de la formule correspond à l'exploitation et le deuxième terme correspond à l'exploration.

 def rollout_policy ( self , possible_moves ):
    
    return possible_moves [ np . random . randint ( len ( possible_moves ))]

Sélectionne au hasard un mouvement parmi les mouvements possibles. Ceci est un exemple de diffusion aléatoire.

 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_node

Sélectionne le nœud pour exécuter le déploiement.

 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. )

Il s'agit de la meilleure fonction d'action qui renvoie le nœud correspondant au meilleur mouvement possible. Les étapes d'expansion, de simulation et de rétropropagation sont réalisées par le code ci-dessus.

 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 

C'est la fonction main(). Initialisez le nœud racine et appelez la fonction best_action pour obtenir le meilleur nœud. Ce n'est pas une fonction membre de la classe. Toutes les autres fonctions sont des fonctions membres de la classe.

Le MCTS comprend 4 étapes :

SÉLECTION

L'idée est de continuer à sélectionner les meilleurs nœuds enfants jusqu'à ce que nous atteignions le nœud feuille de l'arborescence. Un bon moyen de sélectionner un tel nœud enfant consiste à utiliser la formule UCT (Upper Confidence Bound appliquée aux arbres) :

	wi/ni + c*sqrt(t)/ni

wi = nombre de victoires après le i-ème coup
ni = nombre de simulations après le i-ème coup
c = paramètre d'exploration (théoriquement égal à √2)
t = nombre total de simulations pour le nœud parent

EXPANSION:

Lorsqu'il ne peut plus appliquer l'UCT pour trouver le nœud successeur, il développe l'arborescence du jeu en ajoutant tous les états possibles à partir du nœud feuille.

SIMULATION:

Après l'expansion, l'algorithme sélectionne arbitrairement un nœud enfant et simule l'intégralité du jeu à partir du nœud sélectionné jusqu'à ce qu'il atteigne l'état résultant du jeu. Si les nœuds sont choisis au hasard pendant la lecture, on parle de lecture légère. Vous pouvez également opter pour un jeu intensif en écrivant des heuristiques ou des fonctions d'évaluation de qualité.

RÉTROPROPAGATION :

Une fois que l’algorithme atteint la fin du jeu, il évalue l’état pour déterminer quel joueur a gagné. Il monte jusqu'à la racine et incrémente le score de visite pour tous les nœuds visités. Il met également à jour le score de victoire pour chaque nœud si le joueur de cette position a remporté le playout.

CONCEPTION DE VOTRE JEU :

Si vous envisagez de créer votre propre jeu, vous devrez réfléchir aux questions suivantes.

1. Comment allez-vous représenter l’état de votre jeu ? Pensez à l'état initial de notre jeu.
2. Quelle sera la condition de fin de jeu pour votre jeu ? Comparez-le avec la condition de fin de jeu de notre jeu.
3. Comment obtiendrez-vous les actions en justice dans votre jeu ? Essayez d'obtenir les actions en justice pour le premier coup de notre jeu.

Sudo Tic Tac Toe

Si vous avez des questions ou des suggestions, n'hésitez pas à nous contacter à [email protected]