Machine Learning: Computer lernt Atari Spiel zu spielen

Machine Learning: Computer lernt Atari Spiel zu spielen


Fotoquelle: Link


Deep Q Learning

In dem wegweisenden Paper „Playing Atari with Deep Reinforcement Learning“ aus 2013 schaffte es das Startup DeepMind sehr viel Aufmerksamkeit zu erregen, so dass sie später von Google übernommen wurden.
In dem Paper zeigten sie, dass es möglich ist, einem Computer beizubringen, Atari Spiele zu spielen nur indem die Bildschirmpixel beobachtet werden und Rewards (Belohnungen) über den Spielstand (Score) erlangt wurde während des Spielens.
Das beeindruckende daran war, dass sie mit der gleichen Architektur 7 verschiedene Spiele gelöst haben, in 6 der 7 Spiele eine bessere Performance als alle vorherigen Ansätze hatten und in 3 Spielen sogar besser als menschliche Spieler wurden.

Im heutigen Blogbeitrag möchte ich aufzeigen wie das mit Hilfe von Deep Q Learning gelingen kann und das an Hand eines sehr einfachen Spiels – einen Stab auf einem Podest balancieren – demonstrieren.

Das Podest kann sich dabei von links nach rechts bewegen und der Stab kann sich nach links und rechts neigen und ist sehr instabil. Wenn er zu weit zu einer Seite geneigt wird, fällt er und das Spiel endet.
Das Ziel der Spieler*innen ist es folglich, den Stab nicht fallen zu lassen und so lange wie möglich zu balancieren.

Open AI Gym

Glücklicherweise muss ich das Spiel nicht selber programmieren, sondern kann die Implementierung von Open AI Gym nutzen.
Diese Bibliothek stellt mehrere solcher Spiele zur Verfügung, so dass Du bei Interesse auch versuchen kannst, das hier gelernte auf andere Spiele zu übertragen (z.B. Pacman!).

Auf geht’s mit unserer Stabbalance. Um ein erstes Gefühl für das Spiel zu bekommen, führe ich zunächst zufällige Aktionen aus. Eine Aktion ist immer die Entscheidung, den Stab minimal nach links oder rechts zu neigen (das Video unten zeigt das Ergebnis der Codeausführung):

In [24]:
seed = 1234

import random
import numpy as np
np.random.seed(seed)
random.seed(seed)

import time
import gym

delay = True

env = gym.make('CartPole-v1')
env.seed(seed)
stateSize = env.observation_space.shape[0]
actionSize = env.action_space.n

state = env.reset()
rewards = 0
for _ in range(1000):
    env.render()
    if (delay):
        time.sleep(0.1)
    action = env.action_space.sample()
    state, reward, gameOver, _ = env.step(action)
    rewards += reward
    if gameOver:
        env.render(close=True)
        env.close()
        env.reset()
        print rewards
        break
18.0

Erklärung des Codes

Wir nutzen gym um die Spielumgebung (CartPole environment – env) einzurichten und ermitteln die Größe des Spielzustandes (das sind die Werte, die den aktuellen Zustand des Spiels beschreiben) –  das schauen wir uns gleich noch näher an.
Außerdem ermitteln wir die Größe der Aktionen (actionSize), die wir ausführen können.
In diesem Fall wird die Umgebung durch 4 Werte beschrieben und wir haben 2 mögliche Aktionen (0 um den Stab nach links zu neigen, 1 um ihn nach rechts zu neigen).

Wir starten ein neues Spiel mit env.reset(), was den initialen Spielzustand zurückgibt.

In [25]:
state
Out[25]:
array([ 0.15498404,  1.13317843, -0.21134686, -1.85186706])

Wie man gut sehen kann, wird der Zustand über 4 Werte beschrieben, die hier reelle Zahlen sind und sowohl negativ als auch positiv sein können.
Sie beschreiben die Position und Geschwindigkeit der Plattform sowie die Neigung und Neigungsgeschwindigkeit des Stabes.

In der for Schleife, wähle ich eine zufällige Aktion mittels der $sample()$ Methode und rufe $env.step(action)$ auf, um gym mitzuteilen, dass ich diese Aktion ausführe.
Diese Ausführung liefert zugleich den Folgezustand des Spiels, eine Belohnung (reward) sowie die Angabe, ob das Spiel nun beendet ist, oder noch weiterläuft (gameOver).

Die Rewards werden über die Zeit summiert und mittels $print$ bei Spielende ausgegeben.
Die Methode $env.render()$ wird verwendet, um das Spiel zu visualisieren – so bekommt man einen guten Eindruck, was vor sich geht.

Wie man sieht, funktionieren zufällige Aktionen nicht besonders gut. Man erhält in diesem Fall 1 Punkt (Reward) pro ausgeführter Aktion, so dass eine Gesamtsumme von 11.0 bedeutet, dass der Softwareagent nur 11 Schritte überlebt hat.

Und das wollen wir nun wesentlich besser machen!

Q Learning – Theorie

Wie kann ein Softwareagent lernen, das Spiel besser zu spielen?

Die Idee ist die folgende: zunächst hat der Agent überhaupt keine Ahnung und spielt zufällig, beobachtet dabei aber (und merkt sich) was passiert.
Genaugenommen spiechern wir nach jeder ausgeführten Aktion das Tupel aus (Zustand, Aktion, Reward, Folgezustand, Spielende).
Später nutzen wir diese gespeicherten Werte, um immer wieder daraus zu lernen.

Q Learning versucht eine so genannte Policy zu lernen, d.h. gegeben einen Spielzustand zu lernen, welche Aktion die beste ist.
Wir wollen also den Wert einer Aktion $a$ ermitteln wenn wir uns im Spielzustand $s$ befinden.
Angenommen wir haben $Q(s, a_{links}) = 1.2$ and $Q(s, a_{rechts}) = 1.5$
Das bedeutet, dass im Zustand $s$ die Aktion nach links zu gehen ($a_{links}$) einen Wert von 1.2 hat während die Aktion nach rechts zu gehen einen Wert von 1.5 hat. Wenn das so wäre, würden wir im Zustand $s$ folglich nach rechts gehen, um den höheren Wert zu erreichen.

Wie können wir diese Q Funktion / Q Werte nun lernen?

Wir können das mittels der folgenden Gleichung tun:

$$Q(s,a) = r + \gamma \max\limits_{a‘} Q(s‘,a‘)$$

Die Gleichung besagt, dass der Wert der Aktion $a$ im Zustand $s$ aus dem Reward $r$ sowie der bestmöglichen Aktion $a’$ im Folgezustand $s’$ besteht.
$\gamma$ ist dabei ein Rabattparameter, der die Zukunft rabattiert – das ist ähnlich wie mit Geld- und Zinsraten, da es in der Regel besser ist 100 € jetzt als 100 € in 2 Jahren zu erhalten.
$\gamma$ ist üblicherweise ein Wert etwas kleiner als 1, denn 1 würde bedeuten, dass die Zukunft genauso wichtig ist wie die Gegenwart.
Anfangs haben wir natürlich keine Ahnung und führen eine zufällige Aktion $a$ aus. Wir erhalten dadurch einen Reward $r$ und landen im Folgezustand $s’$, so dass wir dann schauen können was unser Q Wert $Q(s,a)$ derzeit aussagt und ihn mittels der erhaltenen Informationen aktualisieren.

Deep Q learning

Und wie verknüpfen wir das nun mit Deep Learning und neuronalen Netzwerken?
Für das einfache Cart Pole Beispiel hier könntest du Q Learning auch ohne neuronale Netze einsetzen. Die Stärke neuronaler Netze kommt vor allem dann zum Tragen, wenn der Zustandsraum sehr groß wird.

Trotzdem werden wir es hier mit neuronalen Netzen angehen, damit Du siehst wie es funktioniert und es dann auch für schwierigere Probleme einsetzen kannst.

Wir nutzen dafür die Bibliothek Keras, die die Definition eines neuronalen Netzwerkes sehr einfach macht.
Es kommt hier ein kleines Netz mit 5 Neuronen in der Eingabeschicht zum tragen.
Diese 5 Neuronen erhalten die 4 Zustandsvariablen als Input und sind zu einer Zwischenschicht mit weiteren 5 Neuronen verbunden.
Die Ausgabeschicht am Ende besteht dann aus 2 Werten (ein Wert für die Aktion $a_{links}$ und ein Wert für $a_{rechts}$):

In [26]:
from keras.models import Sequential
from keras.optimizers import Adam
from keras.layers import Dense, BatchNormalization, Activation

numNeurons = 5
learningRate = 0.001

player = Sequential()
player.add(Dense(numNeurons, input_dim=stateSize, kernel_initializer='glorot_uniform'))
player.add(Activation('relu'))
player.add(Dense(numNeurons, kernel_initializer='glorot_uniform'))
player.add(Activation('relu'))
player.add(Dense(actionSize, activation='linear', kernel_initializer='glorot_uniform'))
player.compile(optimizer=Adam(lr=learningRate), loss='mse')

Nun brauchen wir ein paar Hilsfunktionen, die wir später für das Lernen verwenden.
Die erste sucht die Aktion aus und nennt sich daher chooseAction().
Als Eingabe erhält die Funktion die Q Werte (für unseren aktuellen Zustand) sowie einen Parameter epsilon, der kontrolliert wie wahrscheinlich es ist, dass die Funktion zufällig auswählt.
Das ist sinnvoll, da unsere Q Werte anfangs zufällig sind und noch keine sinnvolle Auswahl ermöglichen. Später ist es aber auch sinnvoll, ab und zu zufällige Aktionen zu probieren, um neue Zustände zu entdecken und Neues zu lernen.
Mit der Zeit reduzieren wir epsilon, so dass wir nach und nach immer weniger zufällig handeln, sondern unseren gelernten Q Werten mehr vertrauen.

In [27]:
def chooseAction(qValues, epsilon):
    numActions = len(qValues)
    if (np.random.random() <= epsilon):
        return np.random.choice(numActions, 1)[0]
    else:
        return np.argmax(qValues)

Um das besser nachvollziehen zu können, schauen wir uns die Hilfsfunktion im Einsatz an.
Zunächst soll völlig zufällig gehandelt werden ($\epsilon=1$):

In [28]:
chooseAction([0.2,1.2], 1)
Out[28]:
0

Unsere Q Werte sind hier für $a_{links}$ (Index 0) 0.2 und für $a_{rechts}$ (Index 1) 1.2.
Dass hier zufällig gewählt wird, ist leicht sichtbar, da die Aktion 0 ausgewählt wurde, obwohl Aktion 1 (mit dem Wert 1.2) einen wesentlich höheren Q Wert hat als Aktion 0 (0.2).
Nachfolgend schalten wir den Zufall komplett aus (epsilon=0):

In [29]:
chooseAction([0.2,1.2], 0)
Out[29]:
1

Jetzt bekommen wir natürlich Aktion 1, da 1.2 > 0.2 ist.

Die nächste Hilfsfunktion wird benötigt, um unsere Erlebnisse zu speichern.
Sie ist recht einfach verständlich. Der einzig erklärenswerte Teil ist reward = -50 für Zustände in denen das Spiel zu Ende (GameOver) ist.
Das sorgt dafür, dass wir hier einen negativen Reward erhalten und der Agent lernen kann, dass es schlecht ist, das Spiel zu beenden, denn wir wollen ja möglichst lange im Spiel bleiben.

In [30]:
from collections import deque

queueSize = 100000
storage = deque([], queueSize)

def storeObservation(state, action, reward, nextState, gameOver):
    if (gameOver):
        reward = -50 # Treat finish as bad event
        storage.append([state.reshape(4), action, reward, nextState, gameOver])
    storage.append([state.reshape(4), action, reward, nextState, gameOver])

Die letzte Hilfsfunktion sorgt für den Abruf der gespeicherten Erlebnisse.
Wir übergeben als Argument wie viele Spiele wir abrufen möchten und erhalten diese als Array zurück.

In [31]:
def getReplays(numPlays):
    replays = random.sample(storage, numPlays)
    cols = [[],[],[],[],[]]
    for memory in replays:
        for col, value in zip(cols, memory):
            col.append(value)
    cols = [np.array(col) for col in cols]
    return (cols[0], cols[1].reshape(-1, 1), cols[2].reshape(-1, 1), cols[3], cols[4].reshape(-1,1))

Auch das können wir schnell ausprobieren:

In [32]:
storeObservation(np.array([0.1, 0.1, 0.1, 0.1]), 0, 1.0, np.array([0.2, 0.2, 0.2, 0.2]), 0)
storeObservation(np.array([0.1, 0.1, 0.1, 0.1]), 1, 1.0, np.array([0, 0, 0, 0]), 0)
In [33]:
getReplays(2)
Out[33]:
(array([[ 0.1,  0.1,  0.1,  0.1],
        [ 0.1,  0.1,  0.1,  0.1]]), array([[1],
        [0]]), array([[ 1.],
        [ 1.]]), array([[ 0. ,  0. ,  0. ,  0. ],
        [ 0.2,  0.2,  0.2,  0.2]]), array([[0],
        [0]]))

Zeit zu lernen!

Jetzt haben wir alles zusammen, um unseren Agenten zu trainieren, die Stabbalance zu lernen.

Der Agent erhält den Spielzustand, den er nutzt, um die Q Werte für diesen Zustand vorherzusagen.
Basierend auf den Q Werten nutzen wir die Hilfsfunktion chooseAction(), um die beste (oder eine zufällige) Aktion in diesem Zustand auszuwählen.
Per env.step(action) führen wir die Aktion durch und erhalten den Folgezustand, den Reward und eine Information, ob das Spiel nun beendet ist.
Die Rewards summieren wir über die Zeit eines Spiels (einer Episode) und speichern die Informationen mittels storeObservation().

qValues = player.predict(state.reshape(1, stateSize))[0]
    action = chooseAction(qValues, epsilon)
    nextState, reward, gameOver, _ = env.step(action)
    currentRewards += reward
    storeObservation(state, action, reward, nextState, gameOver)

Nachdem wir einige Beobachtungen gespeicherten haben, können wir daraus lernen.
Wir holen uns also eine gewisse Anzahl an gespeichterten Beobachtungen (replayBatchSize) und ermitteln die Q Werte der Folgezustände (nextStates) dieser Beobachtungen, um daraus die jeweils besten per np.max() auszuwählen.
Wir erinnern uns an die Gleichung $Q(s,a) = r + \gamma \max\limits_{a‘} Q(s‘,a‘)$ und wenden sie hier an, um die erwarteten Werte (expectedValues) zu berechnen.
Unser Netz weicht eventuell von den erwarteten Werten ab, daher schauen wir, was die bisherigen Q Werte sind, die unser Netz vorhersagt.
In jeder Beobachtung haben wir nur eine Aktion ausgeführt und können folglich auch nur für eine Aktion etwas lernen, daher sorgt die $for$ Schleife hier dafür, für die korrekte Aktion die bisherigen Werte durch die erwarteten Werte zu ersetzen.
Sofern das Spiel zu Ende war, erhalten wir nur den Reward, denn es gibt ja keinen Folgezustand.
Mittels Keras Funktion $fit()$ lernt das Netz dann, die Gewichte im neuronalen Netz so anzupassen, dass das Ergebnis näher an den erwarteten Werten liegt.

states, actions, rewards, nextStates, gameOvers  = getReplays(replayBatchSize)
    qValuesNext = player.predict(np.array(nextStates))
    maxQValues = np.max(qValuesNext, axis=1, keepdims=True)
    expectedValues = rewards + discountRate * maxQValues
    actualValues = player.predict(np.array(states))
    for idx,i in enumerate(actions): # Put expectations for actions
        if (gameOvers[idx]):
            actualValues[idx, i] = rewards[idx]
        else:
            actualValues[idx, i] = expectedValues[idx]
    player.fit(states, actualValues, verbose=0)

Nun können wir alles zusammenpacken und das Netzwerk über einige Episoden trainieren (ein paar Minuten auf meinem Computer).
Während des Trainings kann man auch render = True setzen, um zu beobachten, was der Agent lernt, aber dann dauert das Lernverfahren natürlich länger.

In [37]:
gameOver = True
currentRewards = 0

minEpsilon = 0.05
maxEpsilon = 0.9
totalSteps = 20000
replayBatchSize = 32
trainingInterval = 1
discountRate = 0.95
maxScore = 500

render = False

for i in range(totalSteps):
    epsilon = max(minEpsilon, maxEpsilon - (maxEpsilon - minEpsilon) * i/totalSteps)
    if (gameOver):
        print("Game episode: {}/{}, rewards: {}, epsilon: {:.2}".format(i, totalSteps, currentRewards, epsilon))
        currentRewards = 0
        env.close()
        state = env.reset()
    else:
        state = nextState

    if (render):
        env.render()

    qValues = player.predict(state.reshape(1, stateSize))[0]
    action = chooseAction(qValues, epsilon)
    nextState, reward, gameOver, _ = env.step(action)
    currentRewards += reward
    storeObservation(state, action, reward, nextState, gameOver)

    if (i < replayBatchSize or i % trainingInterval != 0):
        continue

    states, actions, rewards, nextStates, gameOvers  = getReplays(replayBatchSize)
    qValuesNext = player.predict(np.array(nextStates))
    maxQValues = np.max(qValuesNext, axis=1, keepdims=True)
    expectedValues = rewards + discountRate * maxQValues
    actualValues = player.predict(np.array(states))
    for idx,i in enumerate(actions): # Put expectations for actions
        if (gameOvers[idx]):
            actualValues[idx, i] = rewards[idx]
        else:
            actualValues[idx, i] = expectedValues[idx]
    player.fit(states, actualValues, verbose=0)

    if (currentRewards >= maxScore):
        gameOver = True # stop if the agent played for a long time

if (render):
    env.render(close=True)
Game episode: 0/20000, rewards: 0, epsilon: 0.9
Game episode: 69/20000, rewards: 69.0, epsilon: 0.9
Game episode: 848/20000, rewards: 35.0, epsilon: 0.86
Game episode: 3483/20000, rewards: 119.0, epsilon: 0.75
Game episode: 3524/20000, rewards: 41.0, epsilon: 0.75
Game episode: 3560/20000, rewards: 20.0, epsilon: 0.75
Game episode: 3987/20000, rewards: 57.0, epsilon: 0.73
Game episode: 4153/20000, rewards: 166.0, epsilon: 0.72
Game episode: 4299/20000, rewards: 146.0, epsilon: 0.72
Game episode: 4356/20000, rewards: 57.0, epsilon: 0.71
Game episode: 8265/20000, rewards: 37.0, epsilon: 0.55
Game episode: 8291/20000, rewards: 26.0, epsilon: 0.55
Game episode: 9800/20000, rewards: 174.0, epsilon: 0.48
Game episode: 9978/20000, rewards: 178.0, epsilon: 0.48
Game episode: 10079/20000, rewards: 101.0, epsilon: 0.47
Game episode: 10245/20000, rewards: 166.0, epsilon: 0.46
Game episode: 10613/20000, rewards: 368.0, epsilon: 0.45
Game episode: 10771/20000, rewards: 158.0, epsilon: 0.44
Game episode: 11016/20000, rewards: 245.0, epsilon: 0.43
Game episode: 11261/20000, rewards: 245.0, epsilon: 0.42
Game episode: 18073/20000, rewards: 235.0, epsilon: 0.13
Game episode: 18472/20000, rewards: 399.0, epsilon: 0.11
Game episode: 18799/20000, rewards: 327.0, epsilon: 0.1
Game episode: 19286/20000, rewards: 487.0, epsilon: 0.08

Nachdem das neuronale Netz nun die Gewichte angepasst hat, ist der Agent trainiert und wir können ihn beim Spielen beobachten.
Hier setzen wir $\epsilon = 0$, da wir nun nicht mehr zufällig handeln möchten, sondern nach der von uns gelernten Q Policy:

In [38]:
from gym import wrappers

state = env.reset()
rewards = 0
for _ in range(1000):
    env.render()
    qVals = player.predict(state.reshape(1, stateSize))[0]
    action = chooseAction(qVals, 0)
    state, reward, gameOver, _ = env.step(action)
    rewards += reward
    if gameOver:
        env.render(close=True)
        env.close()
        env.reset()
        print rewards
        break
491.0

 

Blog Kategorien

Kontaktieren Sie uns

Kontaktieren Sie uns - Ihre E-Commerce Agentur, Magento & Adobe Agentur, Online Marketing Agentur
Ihr Ansprechpartner
Philip Günther
Telefon: 040 / 22 868 300
Kostenlose Beratung anfordern

Unsere Partner

Google Premium Partner Agentur Hamburg / Stuttgart
Meta Facebook Instagram Agentur Partner Hamburg Stuttgart
Adobe Partner Agentur Silver Hamburg Stuttgart
shopware Agentur partner e-commerce plattform

Gemeinsam
können wir
Großes
bewegen.

Philip Günther

Philip Günther

Geschäftsführer

Aktuelle Blog Beiträge

Über den Autor / die Autorin: M.Paepper

Marc Päpper ist Leiter der Entwicklung bei Lemundo und offiziell zertifizierter Magento Entwickler. Je komplexer die Herausforderungen an die Programmierung, desto größer leuchten seine Augen. Sie haben ein anspruchsvolles Projekt – fordern Sie ihn heraus und Sie bekommen das bestmögliche Ergebnis. Sein Wissensdurst führte ihn über ein Informatik-Studium in Hamburg zur Uni nach Berkeley in Kalifornien sowie ein Masterstudium Neuro-Cognitive Psychology in München. Neben den herkömmlichen Programmiersprachen spricht er auch fließend Englisch und Französisch. IT-untypisch wird die Freizeit entweder Outdoor oder mit einem gutem Buch verbracht.