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

Résolvez votre propre labyrinthe avec Q Learning

Aperçu

Renforcer l'apprentissage

Apprentissage Q

environnement

Mise en œuvre (partie labyrinthe)

tresure.py

Mise en œuvre (partie d'apprentissage)

train.py

train.py

train.py

train.py

train.py

train.py

résultat

Résumé

Les références

`tresure.py`

`train.py`

`train.py`

`train.py`

`train.py`

`train.py`

`train.py`