[PYTHON] IA à cinq yeux en recherchant les arbres de Monte Carlo

Cinq lignes dans le bloc-notes Jupyter

Dans le bloc-notes Jupyter, les cadres sont affichés et vous pouvez les organiser sur cinq lignes. L'IA à cinq yeux est réalisée en recherchant des arbres de Monte Carlo et est conçue pour jouer contre les humains.

La taille du plateau est de 5x5, et si quatre pièces sont alignées verticalement, horizontalement et en diagonale, le gagnant gagne. ..

Télécharger le fichier programme

gomoku.ipynb Environnement d'exploitation confirmé: Microsoft Azure Notebooks Pour savoir comment exécuter, regardez la première cellule après avoir lu le fichier ci-dessus avec le notebook jupyter.

Exploration des arbres de Monte Carlo

La recherche d'arbre de Monte Carlo est une méthode de simulation de la qualité de chaque planche tout en faisant pousser un arbre dont la planche est un nœud (feuille) et la main qui peut être touchée à partir de cette planche est une arête (branche).

En gros, c'est une méthode de pré-lecture autant que possible sur le tableau qui est susceptible d'être une meilleure main, mais aussi d'examiner le tableau qui n'a pas été beaucoup essayé. La question de savoir si un certain tableau est bon ou mauvais pour l'IA est décidé en prenant des mesures au hasard à partir de ce tableau et lequel gagne. Cette méthode d'action aléatoire pour connaître la fin est appelée lecture.

Plus en détail, procédez comme suit:

1. Supposons qu'il y ait une planche (1).
2. Créez un arbre de recherche (2) à (5) avec une longueur d'avance sur (1). Pour le moment, ne créez pas le même tableau.
3. Sélectionnez l'un de (2) à (5) selon les critères suivants. S'il s'agit d'un nœud de branche tel que (2) et (3), il répète la sélection d'un de ses nœuds enfants.
4. Si le nombre de sélections du nœud feuille sélectionné est égal ou supérieur à n, créez une arborescence de recherche plus loin à partir de là. Sinon, jouez au hasard pour déterminer le gagnant.
5. Lorsque la lecture est effectuée, le résultat est propagé au nœud supérieur.
6. Revenez au traitement 3 pour le nombre de fois spécifié.
7. Après le nombre de fois spécifié, sélectionnez le mouvement avec le plus de sélections parmi les nœuds enfants (2) à (5) sur la carte (1) et frappez-le.

AI effectue le traitement ci-dessus afin de sélectionner un mouvement. En particulier, exécutez 3 à 5 fois autant de fois que le temps le permet. On dit que plus le nombre de fois est élevé, plus l'IA est forte. Dans le cas de cette IA à cinq yeux, on sait empiriquement qu'une IA forte peut être créée en répétant les étapes 3 à 5 1000 fois. De plus, le mouvement que l'IA effectue réellement après des simulations répétées est le mouvement vers la carte qui a été simulée le plus fréquemment, comme dans la référence [^ 1].

Critères de sélection d'un nœud parmi les nœuds enfants: La formule suivante sélectionne le nœud avec la valeur maximale.

Q(s,a)+C_p\frac{\sqrt{2\log{n_s}}}{n_{s,a}}

$ Q (s, a) $: Valeur d'évaluation correspondant au taux de gain lorsque vous effectuez un mouvement sur une certaine surface de plateau s $ C_p $: Un coefficient qui équilibre le taux de gain et le nombre de sélections $ n_ {s} $: Nombre de fois qu'un tableau est sélectionné $ n_ {s, a} $: Nombre de fois où a a été frappé d'un certain tableau s

Vue d'ensemble du traitement dans Jupyter Notebook

L'écran est écrit en JavaScript et affiché dans le Jupyter Notebook par HTML d'IPython.

from IPython.display import HTML
html = '''
<div id="dialog" title="Gomoku">
    <div id="canvas-wrapper">
        <canvas id="dlg-canvas"></canvas>
    </div>
    <button id="start">Start</button>
    <div id="status"></div>
</div>
<script>
    $("#dialog").dialog();
</script>
'''
HTML(html)

Créez une fonction pour déterminer lequel est gagnant (ou si le gagnant ou la défaite n'a pas encore été décidé) sur un certain plateau

L'état de la carte est représenté sous forme de tableau, et il est déterminé si les cadres sont disposés verticalement, horizontalement et en diagonale en manipulant l'index du tableau. Les détails seront expliqués dans un autre article qui n'a pas encore été publié.

#Jugement du gagnant
def judge(cells,length=params["length"],n_pieces=params["n_pieces"]):
    # ....
    return 0

Créez une classe pour juger de l'arrangement qui sera le même tableau

La même planche est une planche qui a la même disposition de cadre lorsqu'une certaine planche est vue du côté opposé. Lorsque l'IA recherche un mouvement, l'arrangement qui devient le même tableau a le même résultat lors du déplacement plus loin, donc pour l'efficacité, le même tableau qui apparaît en deuxième est celui Ne traitez pas la destination. Les détails de ce processus seront décrits dans un autre article qui n'a pas encore été publié.

#Créez à l'avance un tableau d'index de tous les mêmes cartons
#Une classe qui vérifie si le tableau est le même
class cell_comparator:
    # ....
    pass

Séparez le processus de recherche dans l'arbre de Monte Carlo et la partie du jeu à cinq yeux

Les détails seront donnés dans un autre article qui n'a pas encore été publié.

La partie qui dépend du type de jeu est implémentée par la classe Game. En échangeant ce jeu de classe, vous pouvez implémenter la recherche d'arbre Monte Carlo pour différents jeux.

#La partie qui change en fonction du type de jeu
class Game():
    #Prenez une décision de victoire. Le numéro du joueur est 1-Réglez sur 1 et affichez le numéro du gagnant. Renvoie 0 s'il n'est pas dans un état gagnant.
    def judge(self,state):
        return 0

    #Comparez si les deux tableaux sont identiques. Renvoie True s'ils sont identiques, False s'ils sont différents.
    def compare(self,state0,state1):
        return False

    #Obtenez le mouvement efficace du tableau de l'argument. Les mains qui ont la même surface de planche n'ont pas besoin d'être considérées ici.
    #MTCS est un jeu.Utilisez comparer pour exclure les coups qui ont le même tableau des coups valides et poursuivez le processus.
    #la lecture mélange ce mouvement efficace et le fait avancer de manière aléatoire.
    def actions(self,state):
        return []

    #Faites un pas par rapport au tableau actuel
    # state:Conseil, joueur:Numéro de joueur pour agir, action:que vas-tu faire(Où frapper dans le cas de cinq yeux)
    def move(self,state,action):
        return state2
    
    # playout
    def playout(self,state):
        return 0.0 #dessiner

    #L'état du plateau est créé à partir de l'expression de caractère.
    def str2state(self,state_str):
		return {}
game = Game()

Il s'agit du code de la partie de recherche d'arbre Monte Carlo. Le traitement d'écran JavaScript appelle la méthode next_ai de python. Ce processus effectue une recherche dans l'arborescence Monte Carlo et renvoie le coup suivant. Le nombre de simulations est déterminé par n, qui a un argument par défaut de 1000 pour next_ai. L'augmentation de ce nombre augmentera le nombre de simulations et renforcera l'IA.

#
#Exploration des arbres de Monte Carlo
#Utilisez le contrôle de victoire et le contrôle d'identité à bord dans la cellule précédente.
#

#La carte a sélectionné ce nombre de fois pour créer des nœuds enfants en tant que processus d'expansion pour développer l'arborescence.
exp_limit = 8
#Dans la phase de sélection, la valeur d'évaluation de la sélection q+c(n) (q:Valeur d'évaluation du tableau, c(n)Valeur d'évaluation du nombre de sélections)de
#Coefficient sur le nombre de sélections
cp = 1.0

#Afin de réutiliser l'objet State, préparez un tableau dans la variable globale et enregistrez-le tout là-bas.
#L'index de ce tableau est le css de l'objet State_Il est détenu par index.
css = []


# class a state representing an condition of all stones on the borad
class State():
    # ....
    pass

# next ai interface
def next_ai(state_str,n=1000):
    #État actuel de la carte(cells), Prochain tour(-1), Parce que le premier État se développe inconditionnellement
    # expand=Créez un objet State avec True.
    cs = State(game.str2state(state_str),expand=True)
    cs.set_css_index(0)
    
    #Ajoutez le premier état à la liste d'état des variables globales.
    global css
    css = [cs]

    #Select est exécuté le nombre de fois spécifié. Dans select,
    # evaluate, expand, (Implicitement)Vous exécutez une sauvegarde.
    for epoch in range(n):
        cs.select()
        pass
    return cs.solution()

Force de l'IA

Empiriquement, l'IA avec 1000 simulations est plus puissante que les humains. Si le premier coup est l'IA, la deuxième personne perd souvent face à l'IA si le premier coup est faux. Cependant, l'IA de 1000 simulations fait parfois des mouvements faibles, de sorte que les humains peuvent gagner à ce moment-là.

L'IA, qui a 2000 simulations, ne fait presque aucune erreur. Par conséquent, si l'IA est le premier joueur, même s'il y a égalité, l'IA ne perdra presque jamais.

Que fait cette IA?

Quoi qu'il en soit, je choisis au hasard les meilleurs. Tout ce que l'IA sait, c'est que (1) le plateau avec quatre pièces d'affilée est une victoire pour l'IA ou les humains, et (2) de nouvelles pièces ne peuvent pas être placées sur les cases où les pièces ont déjà été placées. Les gens pensent que c'est une stratégie pour le jeu, par exemple, dans ce jeu, si vous faites trois pièces consécutives avec des espaces aux deux extrémités, l'adversaire empêchera une extrémité mais frappera l'extrémité restante au tour suivant. L'IA ne sait rien de la stratégie de décision du jeu. En conséquence, l'IA se comporte comme si elle connaissait ces connaissances humaines sans les mettre en œuvre.

Possibilité et limites de l'exploration des arbres de Monte Carlo

À moins qu'il ne soit possible de rechercher complètement l'espace de recherche qui représente tous les états du plateau, une méthode sera utilisée pour rechercher des mains de manière limitée. À ce moment, la différence dans la détermination de ce qui doit être recherché et de ce qui ne doit pas être recherché est la différence dans la méthode de recherche. Par exemple, avec une méthode telle que la recherche αβ, il n'est pas possible de savoir combien de temps est nécessaire pour effectuer une recherche sans effectuer une recherche réelle. En d'autres termes, si la recherche est arrêtée au milieu, ce n'est souvent pas la solution optimale à ce stade. D'autre part, la recherche arborescente de Monte Carlo recherche essentiellement à partir de l'endroit où la possibilité de la solution optimale est élevée. Par conséquent, même si la recherche est arrêtée au milieu, on peut considérer que la solution optimale est obtenue à ce stade. Cette performance de recherche proportionnelle au temps est une très bonne caractéristique lorsqu'elle est réellement utilisée comme une IA de jeu ou autre.

D'autre part, bien que ce soit naturel, la recherche d'arbre de Monte Carlo ne peut pas être utilisée efficacement pour le problème que la fin du jeu ne peut pas être obtenue (difficile à obtenir) à partir d'un certain plateau appelé playout. Dans cette partie de lecture, une technique comme l'apprentissage en profondeur telle que l'apprentissage de la fin à partir d'un certain tableau peut être utilisée [^ 1].