Résolvez votre propre labyrinthe avec Q Learning

Aperçu

En utilisant Q-learning, qui fait partie de l'apprentissage par renforcement, j'ai essayé de résoudre un labyrinthe simple de mon propre travail. L'implémentation a été faite avec python.

Renforcer l'apprentissage

L'apprentissage intensifié est l'une des méthodes d'apprentissage automatique avec l'apprentissage supervisé et l'apprentissage non supervisé. En bref, il forme des «agents» à maximiser la «valeur» dans un «environnement» donné. Dans l'apprentissage par renforcement, les trois éléments d'état * s *, d'action * a * et de récompense * r * sont généralement utilisés. Voici une description de chaque élément.

State * s *: Indique l'état de "l'environnement". Action * a *: Indique l'action entreprise par "l'agent" dans un "environnement" donné. Récompense * r *: indique la récompense obtenue suite à l'exécution d'une action par «l'agent».

Si vous connaissez la "valeur de l'exécution d'une action * a * dans un certain état * s *", vous pouvez entraîner l'agent à maximiser la valeur.

Apprentissage Q

La méthode d'apprentissage Q est une méthode dans laquelle la "valeur lorsqu'une action * a * est effectuée dans un certain état * s *" dans la section précédente est appelée la valeur Q, et l'apprentissage est effectué en mettant à jour cette valeur. La valeur Q lors de l'exécution de l'action $ a_t $ dans l'état $ s_t $ est exprimée par $ Q (s_t, a_t) . Il sera mis à jour en fonction de la récompense * r * qui peut recevoir cette valeur Q, mais pas seulement l'action directe qui peut effectivement recevoir la récompense, mais aussi l'action précédente et l'action précédente ・ On peut dire qu'il est précieux dans la mesure où il s'approche pour obtenir une récompense. Par conséquent, en incorporant et en mettant à jour la valeur attendue de la récompense qui sera finalement obtenue en effectuant cette action, nous calculerons combien elle vaut à chaque instant. La formule spécifique est la suivante. $ Q(s_t,a_t)=Q(s_t,a_t)+\alpha(r_{t+1}+\gamma \text{max}Q(s_{t+1},a_{t+1})-Q(s_t,a_t)) $$

La prochaine récompense t + 1 $ r_ {t + 1} $ et la valeur Q maximale dans l'état $ s_ {t + 1} $ $ \ text {max} lors de la mise à jour de $ Q (s_t, a_t) $ Utilisez Q (s_ {t + 1}, a_ {t + 1}) $. $ \ Alpha $ et $ \ gamma $ sont des hyper paramètres.

environnement

python 3.5.2

Mise en œuvre (partie labyrinthe)

La mise en œuvre de la partie labyrinthe est la suivante. La structure du labyrinthe est une grille de 5 $ \ fois 5 $. (Voir les commentaires dans le code pour plus de détails)

tresure.py


import numpy as np

class Game():
    def __init__(self):
        self.x_size = 5
        self.y_size = 5
        self.init_position = np.array([4,0])
        self.game_board = np.zeros((self.x_size,self.y_size))
        """
Structure du labyrinthe
        0 0 0 0 G
        0 D 0 D D
        0 0 D 0 0
        D 0 0 0 0
        S 0 D 0 0

        G = 1
        D = -1
        """
        self.game_board[0][4] = 1
        self.game_board[1][1] = -1
        self.game_board[3][0] = -1
        self.game_board[2][2] = -1
        self.game_board[1][3] = -1
        self.game_board[1][4] = -1
        self.game_board[4][2] = -1
    
    def judge(self,x,y):
        #Jugement si le jeu est terminé
        if self.game_board[x][y] == 0:
            return 0
        elif self.game_board[x][y] == 1:
            return 1
        else:
            return -1
    
    def check_size(self,x,y):
        #Déterminez s'il est hors du labyrinthe
        if x < 0 or y < 0 or x >= self.x_size or y >= self.y_size:
            return 0
        else:
            return 1
    
    def move(self,position,direction):
        if direction == 'up':
            position[0] -= 1
        elif direction == 'down':
            position[0] += 1
        elif direction == 'right':
            position[1] -= 1
        elif direction == 'left':
            position[1] += 1
        
        return position

La règle est que le joueur peut partir de la case S et se déplacer vers n'importe quelle case vers le haut, le bas, la gauche ou la droite pour chaque état. Si vous atteignez G, vous obtiendrez un objectif et une récompense, et si vous passez à D, le jeu est terminé et vous recevrez une récompense négative en guise de punition.

Mise en œuvre (partie d'apprentissage)

Le code ressemble à ceci <détails>

Code de la pièce d'apprentissage complet </ résumé>

train.py


import numpy as np
from treasure import Game
import copy
import matplotlib.pyplot as plt

#board proscess
game = Game()
game_board = game.game_board
print(game_board)
game_direction = ['up','down','left','right']

def get_action(Q_table,dire,epsilon,x,y):

    #random choice
    if np.random.rand() < epsilon:
        return np.random.choice(dire)

    else:
        return dire[np.argmax(Q_table[x,y])]

def game_init():
    #init process
    game = Game()
    position= game.init_position
    
    return game,position

def game_reward(game,position):
    #result print
    if game.judge(position[0],position[1]) == 1:
        #print('You got a goal!')
        return 1
    elif game.judge(position[0],position[1]) == -1:
        #print('You died..')
        return -1
    else:
        return 0

def game_step(game,position,Q_table,dire,epsilon):
    while(True):
        pos = copy.deepcopy(position)
        direction = get_action(Q_table,dire,epsilon,pos[0],pos[1])
        index_dire = dire.index(direction)
        move_position = game.move(pos,direction)
        if game.check_size(pos[0],pos[1]):
            break
    reward = game_reward(game,move_position)

    return move_position,index_dire,reward

def Q_koushin(Q,state_x,state_y,state_a,s_next_x,state_next_y,alpha,reward,gamma):
    Q[state_x,state_y,state_a] += alpha*(reward + gamma*np.max(Q[s_next_x,state_next_y]) - Q[state_x,state_y,state_a])
    return Q[state_x,state_y,state_a]


if __name__ == '__main__':
    #hyper parameter
    epsilon = 0.01
    alpha = 0.5
    gamma = 0.8
    Q_table = np.zeros((game_board.shape[0],game_board.shape[1],len(game_direction)))
    episode = 200
    sucess = []

    for i in range(episode):
        game,position = game_init()
        while(not game.judge(position[0],position[1])):
            next_position,dire,reward = game_step(game,position,Q_table,game_direction,epsilon)
            Q_table[position[0],position[1],dire] = Q_koushin(Q_table,position[0],position[1],dire,next_position[0],next_position[1],alpha,reward,gamma)
            position = next_position
        
        if i % 10 == 0:
            count = 0
            heatmap = np.zeros((game_board.shape[0],game_board.shape[1]))
            for j in range(100):
                game,position = game_init()
                while(not game.judge(position[0],position[1])):
                    next_position,dire,reward = game_step(game,position,Q_table,game_direction,epsilon)
                    position = next_position
                    heatmap[next_position[0]][next_position[1]] += 1
                if reward == 1:
                    count += 1
            sucess.append(count)
            print(i)
            print(heatmap)
    print(sucess)

J'expliquerai chaque partie ci-dessous.

** Mesures par la méthode epsilon-gourmande **

train.py


def get_action(Q_table,dire,epsilon,x,y):
    #random choice
    if np.random.rand() < epsilon:
        return np.random.choice(dire)

    else:
        return dire[np.argmax(Q_table[x,y])]

Il se déplace de manière aléatoire avec une probabilité de $ \ epsilon $, et sinon sélectionne celui avec la valeur Q la plus élevée.

** Paramètres de la fonction de récompense **

train.py


def game_reward(game,position):
    #result print
    if game.judge(position[0],position[1]) == 1:
        #print('You got a goal!')
        return 1
    elif game.judge(position[0],position[1]) == -1:
        #print('You died..')
        return -1
    else:
        return 0

Lorsque l'objectif était atteint, la récompense était de 1, lorsque le jeu était terminé, la punition était de -1 et à d'autres moments, elle était de 0.

** Mettre à jour la valeur Q **

train.py


def Q_koushin(Q,state_x,state_y,state_a,s_next_x,state_next_y,alpha,reward,gamma):
    Q[state_x,state_y,state_a] += alpha*(reward + gamma*np.max(Q[s_next_x,state_next_y]) - Q[state_x,state_y,state_a])
    return Q[state_x,state_y,state_a]

Mettez à jour la valeur Q selon la formule.

** Déplacer le joueur **

train.py


def game_step(game,position,Q_table,dire,epsilon):
    while(True):
        pos = copy.deepcopy(position)
        direction = get_action(Q_table,dire,epsilon,pos[0],pos[1])
        index_dire = dire.index(direction)
        move_position = game.move(pos,direction)
        if game.check_size(pos[0],pos[1]):
            break
    reward = game_reward(game,move_position)

    return move_position,index_dire,reward

Faites un mouvement pendant la partie. Il juge s'il est sorti du labyrinthe, et s'il est correct, renvoie la position de la destination, la direction du mouvement et la récompense obtenue. Puisque la liste est passée par référence en python, j'ai fait une copie complète pour que la liste d'origine ne soit pas modifiée.

** Partie d'apprentissage **

train.py


if __name__ == '__main__':
    #hyper parameter
    epsilon = 0.01
    alpha = 0.5
    gamma = 0.8
    Q_table = np.zeros((game_board.shape[0],game_board.shape[1],len(game_direction)))
    episode = 200
    sucess = []

    for i in range(episode):
        game,position = game_init()
        while(not game.judge(position[0],position[1])):
            next_position,dire,reward = game_step(game,position,Q_table,game_direction,epsilon)
            Q_table[position[0],position[1],dire] = Q_koushin(Q_table,position[0],position[1],dire,next_position[0],next_position[1],alpha,reward,gamma)
            position = next_position
        
        if (i+1) % 20 == 0:
            count = 0
            heatmap = np.zeros((game_board.shape[0],game_board.shape[1]))
            for j in range(100):
                game,position = game_init()
                while(not game.judge(position[0],position[1])):
                    next_position,dire,reward = game_step(game,position,Q_table,game_direction,epsilon)
                    position = next_position
                    heatmap[next_position[0]][next_position[1]] += 1
                if reward == 1:
                    count += 1
            sucess.append(count)
            print('%d fois' %(i+1))
            print(heatmap)

La Q_table est une matrice de $ 5 \ times5 \ times4 $ in (carrés de labyrinthe) $ \ times $ (direction de déplacement vers le haut, le bas, la gauche et la droite). La valeur Q a été mise à jour pour chaque coup jusqu'à ce que l'objectif soit atteint ou que la partie soit terminée. De plus, chaque fois que j'ai fini le jeu 20 fois, j'ai joué le jeu 100 fois en utilisant le Q_table à ce moment-là, et j'ai enquêté sur le nombre de buts que j'avais et où j'ai passé.

résultat

Le résultat est le suivant.

#Diagramme de structure de labyrinthe
[[ 0.  0.  0.  0.  G.]
 [ 0. -1.  0. -1. -1.]
 [ 0.  0. -1.  0.  0.]
 [-1.  0.  0.  0.  0.]
 [ S.  0. -1.  0.  0.]]
À 20 fois
[[4.500e+01 1.800e+01 1.500e+01 6.000e+00 3.000e+00]
 [4.000e+01 1.400e+01 5.000e+00 3.000e+00 5.000e+00]
 [9.000e+00 4.148e+03 8.000e+00 8.270e+02 5.000e+00]
 [6.700e+01 4.172e+03 1.100e+01 8.350e+02 3.000e+00]
 [0.000e+00 4.900e+01 0.000e+00 2.000e+00 0.000e+00]]
40 fois
[[1.600e+01 1.000e+01 5.000e+00 2.000e+00 2.000e+00]
 [1.300e+01 1.000e+01 2.000e+00 3.000e+00 3.000e+00]
 [7.000e+00 4.105e+03 9.000e+00 6.400e+02 3.000e+00]
 [7.300e+01 4.132e+03 7.000e+00 6.450e+02 2.000e+00]
 [0.000e+00 4.900e+01 0.000e+00 2.000e+00 0.000e+00]]
À 60 fois
[[1.900e+01 8.000e+00 3.000e+00 3.000e+00 3.000e+00]
 [1.700e+01 1.600e+01 0.000e+00 2.000e+00 4.000e+00]
 [6.000e+00 3.754e+03 8.000e+00 2.120e+02 4.000e+00]
 [6.700e+01 3.783e+03 6.000e+00 2.140e+02 2.000e+00]
 [0.000e+00 5.600e+01 0.000e+00 0.000e+00 0.000e+00]]
À 80 fois
[[1.100e+01 6.000e+00 6.000e+00 6.000e+00 6.000e+00]
 [1.100e+01 1.200e+01 0.000e+00 6.000e+00 4.000e+00]
 [6.000e+00 3.544e+03 1.300e+01 2.069e+03 1.107e+03]
 [5.900e+01 3.571e+03 1.500e+01 2.080e+03 1.109e+03]
 [0.000e+00 5.700e+01 0.000e+00 3.000e+00 2.000e+00]]
À 100 fois
[[8.000e+00 8.000e+00 8.000e+00 8.000e+00 8.000e+00]
 [8.000e+00 1.600e+01 0.000e+00 5.000e+00 2.000e+00]
 [8.000e+00 4.783e+03 1.500e+01 3.083e+03 1.225e+03]
 [5.400e+01 4.824e+03 2.300e+01 3.100e+03 1.224e+03]
 [0.000e+00 7.100e+01 0.000e+00 1.000e+01 1.000e+00]]
À 120 fois
[[1.100e+01 1.100e+01 1.100e+01 1.100e+01 1.100e+01]
 [1.100e+01 6.000e+00 0.000e+00 6.000e+00 3.000e+00]
 [1.100e+01 4.215e+03 1.500e+01 2.403e+03 1.660e+03]
 [5.900e+01 4.251e+03 1.900e+01 2.416e+03 1.665e+03]
 [1.000e+00 6.400e+01 0.000e+00 4.000e+00 4.000e+00]]
140 fois
[[ 99. 100.  98.  96.  96.]
 [100.   4.   1.   0.   0.]
 [101. 101.   0.   0.   0.]
 [  0. 102.   0.   0.   0.]
 [  0. 102.   0.   0.   0.]]
À 160 fois
[[ 96.  95.  96.  96.  95.]
 [ 97.   2.   0.   0.   0.]
 [ 97. 100.   1.   0.   0.]
 [  0.  99.   0.   0.   0.]
 [  0. 100.   2.   0.   0.]]
180 fois
[[101. 100. 100. 100.  99.]
 [101.   0.   0.   1.   0.]
 [100. 101.   0.   0.   0.]
 [  0. 101.   0.   0.   0.]
 [  0. 100.   0.   0.   0.]]
À 200 fois
[[ 99.  99. 101. 100.  99.]
 [100.   1.   1.   0.   0.]
 [100. 100.   0.   0.   0.]
 [  0. 101.   0.   0.   0.]
 [  0. 101.   0.   0.   0.]]

#Nombre de buts(100 fois)
[3, 2, 3, 6, 8, 11, 96, 95, 99, 99]

En regardant les résultats, au début, lorsque l'apprentissage ne progressait pas, le jeu était souvent terminé en dehors de la masse près du début, mais après 140 fois d'apprentissage, il semble que presque la bonne voie puisse être trouvée. Je vois.

Résumé

J'ai essayé de résoudre mon propre labyrinthe en utilisant Q-learning. C'était une bonne occasion de pratiquer la mise en œuvre. À l'avenir, j'aimerais jouer à des jeux plus compliqués en utilisant une autre méthode d'apprentissage par renforcement.

Les références

Blog Platinum Data par BrainPad Introduction au renforcement de l'apprentissage ~ Connaissances de base pour ceux qui veulent apprendre Renforcement de l'apprentissage ~ 2017 https://blog.brainpad.co.jp/entry/2017/02/24/121500

Recommended Posts

Résolvez votre propre labyrinthe avec Q Learning
Résolvez votre propre labyrinthe avec DQN
Résolvez OpenAI Gym Copy-v0 avec Q Learning
Entraînez UGATIT avec votre propre jeu de données
Votre propre client Twitter réalisé avec Django
[Renforcer l'apprentissage] DQN avec votre propre bibliothèque
Créez votre propre serveur DNS avec Twisted
Créez votre propre valeur composite avec SQLAlchemy
Pour importer votre propre module avec jupyter
Publiez votre propre bibliothèque Python sur Homebrew
Essayez de créer votre propre AWS-SDK avec bash
Créez rapidement votre propre module avec setuptools (python)
Entraînez Stanford NER Tagger avec vos propres données
Créez votre propre lecteur de musique avec Bottle0.13 + jPlayer2.5!
Étapes pour installer votre propre bibliothèque avec pip
Flux de création de votre propre package avec setup.py avec python
Créez votre propre exception
Mémo pour créer votre propre Box avec le Python de Pepper
Appelez votre propre bibliothèque de langage C avec Go en utilisant cgo
Résolvez AtCoder 167 avec python
Écrivez votre propre fonction d'activation avec Pytorch (sigmoïde dur)
Appelons votre propre bibliothèque C ++ avec Python (Préférences)
Définissez votre propre fonction de distance avec k-means de scikit-learn
Résoudre des maths avec Python
Résoudre des maths avec PuLP
Résolvez POJ 2386 avec python
Essayez de trier vos propres objets avec des files d'attente prioritaires en Python
Exécutez l'intelligence de votre propre bibliothèque python avec VScode.
Apprenez «l'architecture x86 apprise avec votre propre émulateur» avec Manjaro (Linux)
Apprentissage par renforcement 23 Créez et utilisez votre propre module avec Colaboratory
Résolvez AtCoder ABC166 avec python
Travailler avec des sites Web à l'aide de Python_Webbrowser
Créez votre propre middleware Django
Créez votre propre VPC avec un seul sous-réseau public uniquement avec boto
[Introduction au style GAN] Apprentissage unique de l'animation avec votre propre machine ♬
Comment créer votre propre site de domaine avec heroku (plan gratuit)
Introduction au Deep Learning (2) - Essayez votre propre régression non linéaire avec Chainer-
Dessinez votre propre indicateur de chute avec PySide (réalisez QProxyStyle avec la magie noire)