Inleiding
Voor mijn opleiding moest ik een complex ICT-vraagstuk beantwoorden via Python. Nu heb ik niet zozeer een vraagstuk beantwoord, maar mijn verzoek om een project te maken met AI werd goedgekeurd, iets waar ik al tijden meer van wilde weten. Ik had besloten een simpele variant van het spel Doodle Jump te maken en vervolgens een AI te implementeren om het spel te leren spelen. Omdat het project met een ruim voldoende werd beoordeeld, wil ik mijn onderzoek graag met jullie delen! In mijn onderzoek ben ik terecht gekomen bij NEAT, een Neural Network algoritme die via de package neat-python is geïmplementeerd in Python. Omdat ik deze package tegen kwam in een video van Tech With Tim op YouTube (playlist is hier te vinden). Vanuit deze playlist ben ik de tutorial gaan volgen om NEAT te implementeren in het spelletje Flappy Bird. Nadat ik via deze video's was geïntroduceerd met zowel NEAT als Python, kon ik aan de slag. In deze blogpost ga ik niet zozeer diep in het ontwikkelen van het spel, maar meer in het kort de werking en de implementatie van de AI. Voor informatie over de ontwikkeling kun je de publieke repository bekijken of kijken naar de YouTube video's die ik zal ontwikkelen later deze zomer.De werking
Input / Output
De AI werkt in generaties, waarbij elke generatie een populatie (van bijvoorbeeld 30) heeft. Deze generatie speelt het spel en creëert een Neural Network per genoom (speler). De ontwikkelaar geeft de AI input en de AI genereert output op basis van de gemaakte keuzes. Deze keuzes zijn bij de eerdere generaties volledig willekeurig en worden doelmatiger naarmate de AI meer leert. De AI leert door de beste genomen (genomen met de hoogste fitness) te laten paren en het resultaat te gebruiken in de nieuwe generatie. Als input gaf ik de AI 18 waardes (wat aardig veel is). Het spel heeft per frame 7 platformen in beeld en elk platform heeft X en Y coördinaten. Omdat elk platform even groot is, geef ik deze niet mee. Dit vormt dus al 14 waardes (7 keer X en Y). Daarbij geef ik ook de X en Y coördinaten van de speler mee, evenals de snelheid (velocity) op de X en Y as. Dat maakt in totaal 18 waardes. Deze waardes ontvangt de AI en creëert output. De output die ik laat genereren is in de vorm van een hyperbolische tangens. Dit betekent dat de AI een output levert van -1 tot 1. Bij een waarde van onder de -0.5 laat ik de speler naar links bewegen, bij een waarde van boven de 0.5 laat ik de speler naar rechts bewegen. De vorm van de hyperbolische tangens is hieronder te zien.
Bron: https://commons.wikimedia.org/wiki/File:Hyperbolic_Tangent.svg
Fitness
Vervolgens moet ik in de code de fitness bepalen. Fitness is de score waarmee de genoom weet of die het wel of niet goed doet. Elk frame wordt er gecontroleerd of de fitness moet worden verhoogd of verlaagd. Dat gebeurt op basis van de volgende keuzes:
Deze fitness staat nog niet vast en verandert continu om de AI te verbeteren. De AI bepaald de sterkte van een genoom dus op basis van de verkregen fitness. In simpele woorden: hoe hoger de genoom komt, hoe sterker deze is.
Configureren
Het idee is dus dat de AI met de verkregen data (locaties van de platformen, speler en de snelheid van de speler) een link gaat leggen met de verkregen fitness en op basis daarvan, per frame, de keuze maakt of de genoom naar links, naar rechts of niet moet bewegen. Omdat enkel de sterkste genomen overblijven, zal de AI in theorie dus steeds betere keuzes maken. De moeilijkheid hiervan komt terug in het instellen van de configuraties. Hoe vaak muteren genomen (dus wanneer gaan ze een andere keuze maken om iets nieuws te proberen), hoeveel fitness krijgt de genoom per handeling, hoe groot is de elite (de sterkste genomen). Hierbij kreeg ik een handige grafiek van een goede vriend van mij ((MSc.) Folkersma) die zelf een master in AI heeft. Hij legde uit dat er een gulden midden is bij de hoogte van de learning rate, op basis van het verlies van genomen.
Bron: https://miro.medium.com/max/459/0*C5kIkoBwht0fXRgs.jpeg
Hierbij ook de informatie, geleverd vanuit (MSc.) Folkersma:
“Mutatie heeft een soort gulden midden; te weinig mutatie en het wil niet, te veel mutatie en je overschiet alleen maar; vaak als een algoritme heel snel vooruitgang maakt en dan direct vastloopt heb je te veel mutatie of te hoge learning rate. Zie bovenstaande afbeelding, hetzelfde geldt voor mutatie grootte en andere soorten automatische aanpassing.
2e belangrijke is je selectiestrategie; veel zijn geneigd om echt super selectief te zijn, maar wat soms veel beter werkt is een redelijk lage druk; Deel de populatie op in paren, en selecteer van elk paar de de beste; dan houdt je dus gewoon 50% van je populatie, maar is vaak al genoeg en komt variatie ten goede wat erg handig is als je crossover gebruikt, brengt me op het laatste punt.
Een goede crossover is vaak enorm impactvol; dus als je een crossover operatie kan definiëren op jouw soort populatie (ik weet niet wat het is, neural nets?) dan kan dat wel eens de boel enorm veel sneller laten gaan.”
Samengevat heb ik de volgende keuzes gemaakt voor het ontwikkelen van de AI:
Implementatie AI
Na het ontwikkelen van het spel en het toevoegen van de neat-python library ben ik de AI gaan draaien en op basis van de resultaten de configuraties en fitness rewards aan gaan passen. Wanneer de AI te snel leerde en op een gegeven moment uitsterft, gaat de mutatiesnelheid omlaag. Wanneer een AI niks lijkt te leren, gaat de mutatiesnelheid omhoog. Wanneer ik thuis werk op mijn PC, gaat de populatie omhoog. Wanneer de genomen telkens doodgaan, gaat de fitness vermindering omhoog. Zo ben ik telkens onderdelen gaan aanpassen tot ik bij een redelijk resultaat kwam. Alleen hier bleef het bij. Het viel mij op dat de AI na lange tijd tot redelijke hoogtes kon komen, maar daarna vast liep en uiteindelijk een uitsterving veroorzaakte. Ik heb toen besloten met (MSc.) Folkersma te zitten en de AI door te nemen met hem. Zo ben ik telkens onderdelen gaan aanpassen tot ik bij een redelijk resultaat kwam. Alleen hier bleef het bij. Het viel mij op dat de AI na lange tijd tot redelijke hoogtes kon komen, maar daarna vast liep en uiteindelijk een uitsterving veroorzaakte. Ik heb toen besloten met (MSc.) Folkersma te zitten en de AI door te nemen met hem. Een AI vind het erg lastig te rekenen, in dit geval bijvoorbeeld het berekenen van de afstand tussen de speler en de omliggende platformen. Wat een AI wel heel goed kan, is 0 en 1 logica, waar of niet waar. Het eerste idee was om rondom de speler een radius te maken en deze op te delen in segmenten. Deze segmenten controleren of zij een platform in zich hebben en geven op basis van die informatie een 1 terug als er een platform aanwezig is, of een 0 wanneer er geen platform aanwezig is. Hierna kwamen we met een beter idee, namelijk raycasting. Om de speler heen worden er rays (stralen) gecast (gevolgd) om te kijken of er een object wordt geraakt. Links zijn deze raycasts te zien. In debug modus worden de rays als blauw getoond en worden groen wanneer deze in aanraking met een platform komen. Hetzelfde als met de segmenten wordt een 1 teruggegeven als er een platform wordt gedetecteerd en een 0 wanneer er niks wordt gedetecteerd.
Omdat de speler wordt gespiegeld wanneer deze het scherm verlaat op de horizontale as, gebeurt dit ook met de rays die worden gecast. Uiteindelijk zal de bovenstaande situatie (bij de meest linker genoom) het volgende worden gegeven aan het Neural Network:
[0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0]
Het Neural Network kan dan veel makkelijker een verband leggen waar een object zou staan, in plaats van dat deze een hele berekening moet uitvoeren om daaruit te concluderen dat de speler in de buurt van een platform staat.
Ook heeft (MSc.) Folkersma aangegeven dat ik dit voor nu ook met de speler kan doen, namelijk met de belangrijkste informatie, de velocity. De AI moet namelijk weten of de speler aan het stijgen of dalen is. Ik geef in dit geval nog vier extra waardes mee, namelijk antwoord op de volgende vragen:
- Stijgt de speler?
- Daalt de speler?
- Gaat de speler naar links?
- Gaat de speler naar rechts?
[1, 0, 0, 1]
Dit, gecombineerd met de raycast data, geeft de volgende input voor de AI:
[0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1]
Door extra hidden layers te geven (extra lagen aan neurons), kan de AI met deze data links gaan leggen. Uiteindelijk zal er een link worden gelegd, waarbij de AI weet dat wanneer deze stijgt en er een platform rechtsboven zit, de AI naar rechts moet bewegen.
Ook de output is aangepast, namelijk naar een sigmoïde output. Ik genereer nu twee outputs (naar links of naar rechts). Beide deze outputs krijgen een waarde van 0 tot 1 en op basis van welk van deze waardes hoger is, wordt er een actie uitgevoerd. Als output 1 hoger is, gaat de speler naar links en als output 2 hoger is, gaat de speler naar rechts. Ik heb expres de actie “stilstaan” niet meegerekend, aangezien dit eigenlijk een heel bewuste actie moet zijn (dus dan zou de AI bijvoorbeeld elke frame moeten wisselen van links en rechts).
Bron: https://en.wikipedia.org/wiki/Sigmoid_function
Ik merk wel dat de AI nog vaak fouten maakt en dit heeft te maken met het verbeteren van de inputs en configuraties. Qua inputs zou ik graag de raycasts aanpassen zodat deze de lengte hebben van hoe ver de speler kan komen. Op die manier hoef ik enkel de raycast output als input te geven en kan ik de inputs van de speler achterwege laten.