The Flappy Bird Bot - Survival of the Fittest Bird

I det nevrale nettverket til “Flappy Bird”-bot’en vil input være sensordata som representerer det fuglen ser, mens output vil være hvilken handling som bør utføres. Det nevrale nettverket skal løse det binære problemet: flakse med vingene eller ikke flakse med vingene.

For at et nevralt nettverk skal kunne løse en bestemt oppgave er vi først nødt til å “trene” det. Å “trene” i denne sammenhengen går ut på å justere kantvektene i nettverket. Dette er verdier som ligger på kantene, eller koblingene mellom nodene i nettverket, som bestemmer hvor mye et signal skal påvirkes når det passerer. En høy verdi betyr at signalet skal forsterkes og en lav verdi at signalet skal reduseres. Før disse er justert er ikke nettverket brukbart til noen ting.

For å få justert kantvektene bruker man ofte en algoritme kalt “Backpropagation”, som krever store mengder treningsdata. Treningsdataen kan ses på som en rekke oppgaver med tilhørende fasit. Oppgaven representerer input inn i nettverket og fasit hva output skal være. Hver oppgavene sendes én og én gjennom nettverket og nettverkets svar (output) sammenlignes med fasit. Deretter beregnes feilen, eller avviket mellom faktisk output og ønsket output, som så propageres bakover gjennom nettverket. Når man har gjort dette mange nok ganger vil kantvektene være justert slik at nettverket kan løse nye tilsvarende oppgaver uten fasit.

Evolusjonsalgoritmen

Men hva gjør man så om man ikke har nok eller ingen treningsdata? Hva hvis vi ikke vet hva rett output skal være for en gitt input? I slike tilfeller kan man ikke benytte seg av tradisjonelle metoder for å trene opp nettverket. For “Flappy Bird”-bot’en er dette tilfellet. Vi har ikke trengingsdata, og det kan være vanskelig å si hva som er rett handling i en hver situasjon. Det er her evolusjonsalgoritmen kommer inn i bildet. Hva om vi ser på det nevrale nettverket som et individ som eksisterer i et miljø. I dette miljøet skal individet gjøre en oppgave. Vi har mulighet til å innhente sensor data (input) fra miljøet og vi har mulighet til å måle hvor dyktig individet er til å løse oppgaven. Med disse forutsetningene på plass kan vi benytte evolusjonsalgoritmen til å simulere evolusjon av individer (nevrale nettverk) og dermed finne gode nettverk med kantvekter som løser oppgaven.

Søket etter et godt nevralt nettverk for “Flappy Bird”-bot’en ved hjelp av evolusjonsalgoritmen vil bestå av følgende steg. Først må vi generere en populasjon av nevrale nettverk med lik topologi, men med ulike kantvekter. Altså har vært nettverk (individ) like mange input noder, skjulte noder og output noder, mens kantvektene som styrer oppførsel/intelligens er ulike. Deretter lar vi populasjonen forsøke å løse oppgaven, som i dette tilfellet er å spille “Flappy-Bird”. Hvert individ (nettverk) blir så tildelt en “fitness”-score som sier noe om hvor flink individet var til å løse oppgaven. Individene formerer seg deretter gjennom krysning hvor det er størst sannsynlighet for at individer med høy “fitness”-score får avkom. Individene med lavest “fitness”-score blir fjernet fra populasjonen og den nye populasjonen prøver å løse problemet på nytt. Ved å gjøre dette generasjon etter generasjon skal individene, i teorien, bli bedre og bedre egnet til oppgaven. Evolusjonsalgoritmen kan derfor ses på som et søk etter en optimal løsning gjennom naturlig utvalg, hvor vi i dette tilfellet søker etter et optimalt nevralt nettverk.

Før jeg kunne bruke evolusjonsalgoritmen som beskrevet over til å skape en god “Flappy Bird”-bot måtte jeg definere en fornuftig nettverkstopologi. Det første jeg måtte bestemme var hvilken informasjon fra omgivelsene til den virtuelle fuglen det ga mening å bruke som input. Etter litt eksperimentering landet jeg etterhvert på disse fire:

• Horisontal avstand til nærmeste åpning
• Vertikal avstand til topp av nærmeste åpning
• Vertikal avstand til bunn av nærmeste åpning
• Vertikal hastighet

I og med at det er et binært problem jeg skulle løse trengte jeg kun én output-node, som enten var av eller på representert med verdiene 0 (reduser høyde) og 1 (øk høyde).

Å finne et fornuftig antall lag og noder i hvert lag i det skjulte laget, kan være litt vanskelig og krever ofte litt prøving og feiling. Kort fortalt vil et nettverk med få noder trenes opp raskere enn et nettverk med mange noder, men et nettverk med mange noder kan lære seg mer komplekse situasjoner. I og med at problemet nettverket skulle løse ikke er alt for komplekst og jeg kun hadde 4 input-noder og 1 output-node landet jeg på ett skjult lag med 3 noder. Altså ble nettverkets topologi følgende:

Når topologien var på plass måtte jeg definere en fitness-funksjon. En funksjon som beregner hvor godt egnet hvert nettverk er til å spille “Flappy Bird”. I og med at hele målet med spillet “Flappy Bird” er å overleve så lenge som mulig ble også fitness-funksjonen enkel. Nemlig horisontal-avstand fløyet før krasj, minus vertikal avstand til nærmeste åpning.

Til slutt måtte jeg bestemme hvilke individer som fikk formere seg og hvilke individer som overlever til neste generasjon. Til dette lagde jeg meg et virtuelt ruletthjul hvor sannsynligheten for å “lande” på et bestemt individ var styrt av individets fitness-score. To og to individer ble deretter valgt ut til formering ved å spinne hjulet 2 ganger. For vært utvalgte foreldrepar ble 2 nye individer skapt gjennom krysning av kantvektene basert på et tilfeldig krysningspunkt:

Ved at man bruker et ruletthjul som beskrevet over fremfor å kun la de beste individene formere seg, beholder man en sannsynlighet for at et svakere individ også får formere seg. Selv om et individ får en lav fitness-score kan det hende at noen av kantvektene allikevel har gode verdier, som kombinert med kantvektene fra et annet nettverk kan gi gode resultater.

Hver nye generasjon består av nye individer + en prosentandel av de beste individene fra forrige generasjon. I og med at man ikke er garantert at nye individer er bedre enn gamle, sikrer man seg derfor at gode individer fra forrige generasjon får muligheten til å formere seg på ny og potensielt skape bedre avkom.

Med alle delene av evolusjonsalgoritmen på plass kunne evolusjonsprosessen starte:

Som man kan se i videoen fra evolusjonsprosessen over evalueres alle individene samtidig i hver generasjon. Størrelsen på populasjonen i hver generasjon er 300 individer, og etterhvert som de krasjer beregnes fitness-scoren. Når alle individene har krasjet, genereres neste generasjon av individer før neste evaluering starter. Denne evolusjonsloopen går helt til et individ har klart å passere 20 åpninger. Da lagres kantvektene til nettverket og bot’en er klar til bruk.

Hvordan gikk det?

Utfordringen og det som kan være både fasinerende og frustrerende med en slik tilnærming til “trening” av et nevralt nettverk er at man aldri vet hvor mange generasjoner som skal til før man har et godt nettverk og om man i det hele tatt vil finne et. Det inngår nemlig en del tilfeldigheter i algoritmen som kan føre til at man “låser” seg fast i suboptimale løsninger. I mine gjennomkjøringer av algoritmen for å finne en god “Flappy-Bird”-bot har det tatt alt fra 7 til 100 generasjoner før jeg har funnet et individ som løser problemet feilfritt.

Selv om akkurat dette prosjektet ikke løser et “problem” som er direkte nyttig for noen, tror jeg det finnes problemer hvor samme tilnærmingsmåte kan brukes. For meg er det ihvertfall fasinerende å se hvordan man kan bruke ideer fra hvordan mennesker og dyr utvikler seg til å skape bot’er som kan oppfattes intelligente.

Hvordan gjorde jeg det?

For å få gjennomført dette prosjektet var det en god del som måtte utvikles. For det første trengte jeg en versjon av spillet “Flappy-Bird” hvor jeg enkelt kunne hente ut den informasjonen jeg trengte, samt mulighet til å styre bot’ene ved hjelp av nevrale nettverk. For å løse det problemet så jeg ingen annen løsning enn å implementere min egen versjon, noe jeg gjorde ved hjelp av spillrammeverket MonoGame.

Med spillet på plass trengte jeg en implementasjon av nevrale nettverk jeg kunne bruke inne i spillet samt en implementasjon av evolusjonsalgoritmen. Begge disse endte jeg også opp med å implementere selv da det ga meg full innsikt i hvordan de fungerte samt at jeg enkelt kunne integrere implementasjonene i spillet. Alle delene ble skrevet i språket C#.

Om det skulle være interessant ligger all kode åpent på GitLab.