Hoe kunstmatige intelligentie Ms. Pac-Man leerde spelen
Met 999.990 punten heeft een kunstmatige intelligentie de absolute high-score gehaald op het inmiddels 36 jaar oude spel Ms. Pac-Man. De PCM-redactie moest met 13.160 punten genoegen nemen. Wij vroegen de leider van het team achter deze kunstmatige intelligentie hoe ze een computer Ms. Pac-Man hebben leren spelen en waarom.
Kunstmatige Intelligentie is een zeer breed studieveld binnen de informatica. Doel is computers te ontwikkelen die zich bewust zijn van hun omgeving, beslissingen kunnen nemen en aan de hand daarvan leren. Dat hoeft niet te leiden tot zelfdenkende machines die – in de Hollywood-stijl – de wereld overnemen. Realistischer zijn de intelligente computers die zelfrijdende auto’s bedienen. Die zijn zich bewust van de weg, andere auto’s, voetgangers en overige obstakels. Aan de hand daarvan nemen ze stuurbeslissingen en ze leren steeds beter te rijden.
Het in Canada opgerichte bedrijf Maluuba ontwikkelt kunstmatige intelligentie om taal te begrijpen. Het bedrijf is grofweg verdeeld in drie teams. Eén team zorgt dat computers teksten kunnen lezen en daar vervolgens vragen over kunnen beantwoorden. Deze divisie heeft een computer het boek Harry Potter en de Steen der Wijzen laten lezen. Daarna kon de computer inhoudelijke vragen over het boek beantwoorden.
Een tweede team binnen Maluuba richt zich op ‘dialog’. Dat zijn systemen die proberen het juiste antwoord te geven als er tegen ze gepraat wordt. Dat kan bijvoorbeeld gebruikt worden in de telefooncentrale van de eerste hulp. De beller geeft aan wat het probleem is, en de computer zorgt door vragen te stellen dat deze met de juiste hulppost wordt verbonden.
Reinforcement learning
Harm van Seijen (research manager bij Microsoft) werkt voor het derde team in Maluuba, dat zich richt op Reinforcement Learning. Een fundamenteel onderzoeksveld waar de andere twee teams hun voordeel mee doen. Kunstmatige Intelligentie is onderverdeeld in verschillende subvelden waaronder Machine Learning. Binnen dit subveld proberen onderzoekers machines te leren leren. Daar zijn weer onderliggende velden in, bijvoorbeeld Neurale Netwerken die leren op basis van voorbeelden. Daar leert een computer bijvoorbeeld katten op de foto te herkennen door foto’s met en zonder kat te bekijken.
Het veld Reinfocement Learning laat computers leren door beloningen aan beslissingen toe te kennen. De computer probeert door verschillende beslissingen te nemen de hoogst mogelijke score te halen. Dat kan ingezet worden in combinatie met het dialog-systeem van het andere team bij Maluuba, bijvoorbeeld om een systeem te bouwen dat telefonische verkopers argumenten geeft om een product te verkopen.
Volgt na een argument een aankoop, dan genereert dat een positieve beloningsscore. Wordt er niet gekocht, dan is de score nul. Gooit de klant de hoorn op de haak, dan volgt er een negatieve score. Op den duur leert de computer zo welke argumenten goed zijn voor de verkoop en welke minder.
In 2015 is bij de University of Toronto een Reinforcement Learning-onderzoek uitgevoerd met behulp van computerspellen van de (antieke) Atari 2600. Het onderzoeksteam gebruikte daar een zogenaamde Deep Reinforcement Learning techniek om de computer spellen te leren spelen. Met deze nieuwe aanpak wist de computer na training bij zes van de zeven geteste spellen een betere score neer te zetten dan welke andere computer ook. In drie gevallen was de computer zelfs beter dan de beste menselijke spelers.
Verschil met Pac-Man
Het in 1981 gelanceerde spel Ms. Pac-Man zat niet bij de titels die in dit onderzoek met succes gespeeld zijn. Harm: “De techniek bij dat onderzoek doet het heel goed bij zo’n 75 procent van de spellen. Maar bij andere titels, waaronder Ms. Pac-Man, werkte het heel slecht. Waarom was niet duidelijk. We hebben geprobeerd dat uit te leggen, maar konden het niet verklaren. Een doelstelling van ons onderzoek was daarom uitvinden waarom het zo moeilijk was en dat vervolgens op te lossen.”
Ms. Pac-Man is de opvolger van het in 1980 verschenen spel Pac-Man. Voor wie het niet kent (wat we ons nauwelijks kunnen voorstellen): in beide spellen moet de speler het titelkarakter door een doolhof sturen om zo pellets, die in de gangen liggen, op te eten. Is het doolhof leeg, dan begint het volgende level. Vier spoken proberen de speler op zijn beurt op te eten. Door één van de vier in het doolhof aanwezige power pellets op te eten, kan de speler tijdelijk de rollen omdraaien en extra punten scoren door spoken op te eten. Af en toe verschijnt er tijdelijk een stuk fruit in het doolhof. Weet de speler dit op te eten, dan levert dat bonuspunten op.
In werkelijkheid zitten er behoorlijke verschillen tussen Pac-Man en Ms. Pac-Man
-
Op het eerste gezicht lijkt Ms. Pac-Man niet meer aan Pac-Man toe te voegen dan een strik, een oog, lippenstift en een schoonheidsvlek. In werkelijkheid zitten er behoorlijke verschillen tussen de twee titels. Zo beweegt Ms. Pac-Man zich door vier verschillende doolhoven terwijl Pac-Man steeds in hetzelfde doolhof verschijnt. Het fruit beweegt in Ms. Pac-Man, terwijl het in de vorige titel stil lag. Zeker belangrijk voor lerende machines: de spoken in Pac-Man verplaatsen zich relatief aan hoe de speler loopt. Dat maakt het mogelijk om bewegingspatronen te ontdekken en daar de speelstijl op aan te passen. In Ms. Pac-Man bewegen de spoken zich met meer willekeur, waardoor een patroon niet te ontwaren is.
Hoogst mogelijke Pac-Man-score
Pac-Man en Ms. Pac-Man zijn over de afgelopen 37 jaar in een onwaarschijnlijke hoeveelheid varianten op de markt gebracht. De website highscore.com houdt wereldwijd de hoogste scores van computerspellen bij. Een snelle zoektocht op deze site geeft 568 varianten van het spel Ms. Pac-Man. Voor de Atari 2600-variant (die in dit onderzoek gebruikt is) kunnen we kiezen uit een high-score geboekt op een originele Atari 2600 spelcomputer (154.630) of op computer die de Atari emuleert (266.330). Kortom, de score van het team van Harm is 3,75 keer zo hoog als de hoogst genoteerde score in Ms. Pac-Man ooit. Harm: “Dit is de hoogst mogelijke score omdat deze daarna reset naar 0 punten.”
Om dit te bereiken is er een creatieve aanpak van de Reinforcement Learning techniek gebruikt. Het team van Maluuba noemt dit de Hybrid Reward Architecture. Harm: “In Reinforcement Learning heb je te maken met een beloningsfunctie. Normaal heb je één agent die probeert de beloning te maximaliseren. Wij hebben die functie opgesplitst in een hoeveelheid kleinere deelfuncties. We hoeven daarom niet met één agent een complex probleem op te lossen, maar hebben een grote verzameling agents die kleine problemen proberen op te lossen.”
Binnen Ms. Pac-Man maakte het team van allerlei losse onderdelen in het spel een agent. Onder meer de pellets in het doolhof, de spoken, de power-pellets en de ‘eetbare spoken’ (na het eten van een power-pellet) werden agents. In totaal gaven 163 verschillende agents aan of ze vonden dat Ms. Pac-Man omhoog, omlaag, linksaf of rechtsaf moest bewegen.
De beslissing van iedere agent kreeg ook een eigen gewicht. Harm: “Iedere agent spreekt een voorkeur voor actie uit en geeft aan hoe belangrijk hij is. Wat een spook wil is van meer belang dan wat een pellet wil.” Op basis van een zogenaamde ‘lineaire combinatie van Q-waarden’ gebruikt de computer die meningen om een afgewogen beslissing te nemen.
4000 uur later
Hoe beter die beslissing in de eindscore uitpakt, hoe eerder de computer die in een volgend spelletje opnieuw zal nemen. Op die manier leert de machine een steeds hogere score op Ms. Pac-Man te noteren. De computer heeft in totaal bijna 4.000 uur Ms. Pac-Man moeten spelen om de topscore te kunnen noteren. Uitgaande van de vuistregel dat iemand met een 40-urige werkweek gemiddeld per jaar 1.650 uur werkt, vertaalt zich dat naar bijna 2,5 jaar trainen voor een mens. Het spelletje waarbij de topscore behaald werd nam 1 uur en 16 minuten in beslag.
In werkelijkheid heeft het vanzelfsprekend geen 2,5 jaar geduurd voor deze score bereikt werd. Voor het experiment was het niet nodig om de computer op menselijke snelheid te laten spelen. Met behulp van een standaard PC met Intel Core i7-processor is de 4.000 uur training uitgevoerd in 30 uur. Daarvoor was eerst een 20 uur durende optimalisatie nodig in een parallel rekenend netwerk van computers. De totaal benodigde ‘werkelijke’ tijd om Ms. Pac-Man te verslaan werd zo teruggebracht naar 50 uur.
De computer heeft in totaal bijna 4.000 uur Ms. Pac-Man moeten spelen om de topscore te kunnen noteren.
-
Natuurlijk investeren Microsoft en Maluuba niet in Reinforcement Learning om de hoogste score op een computerspel te kunnen claimen. Het team van Harm voert voor de bedrijven fundamenteel onderzoek uit. Op basis van hun bevindingen kunnen de andere twee teams van Maluuba hun toepassingen verder optimaliseren.
Harm: “In het algemeen probeer je met Reinforcement Learning uit data goed gedrag te leren. Dat kun je potentieel voor veel dingen gebruiken. Binnen taal bijvoorbeeld om in dialogs de juiste respons te berekenen. Dat kan bij simpele taken gewoon met de hand gecodeerd worden. Maar als het om ingewikkeld gedrag gaat, kan dat niet meer. Dan wil je dat er zelf geleerd wordt aan de hand van data. Daar wordt Reinforced Learning voor gebruikt.”
Zelf aan de slag
Wil je zelf met kunstmatige intelligentie aan de slag, dan volgen hier enkele tips:
Stap 1: Bezoek de Arcade Learning Environment
De Arcade Learning Environment biedt een framework waarmee onderzoekers en hobbyisten AI agents voor Atari 2600 spellen kunnen bouwen. Om hiermee aan de slag te gaan is Linux of OS X nodig. Daarnaast dien je over kennis van Python en C++ te beschikken.
Stap 2: Bezoek OpenAI Gym
Op de website van OpenAI Gym kun je het gereedschap vinden om zelf een Reinforcement Learning algoritme te ontwikkelen. Om dit gereedschap te gebruiken is kennis van de programmeertaal Python praktisch. Naast de mogelijkheid om te ontwikkelen, biedt de OpenAI Gym ook opties om resultaten van je werk te vergelijken met die van anderen. De site bevat daarnaast documentatie en een forum om vragen te stellen.
Stap 3: Kies je project
OpenAI Gym biedt een keur aan omgevingen om je eigen kunstmatige intelligentie voor te ontwikkelen. Daar zitten beginnersprojecten bij en mogelijkheden om met de standaard bordspellen aan de gang te gaan. Je kunt zelfs je eigen 2D- en 3D-robotsimulaties maken. Eén van de mogelijke omgevingen waar je voor kunt kiezen zijn de klassieke Atari-computerspellen.
Stap 4: Breid je omgeving uit
Een handig aspect van OpenAI Gym is dat het kan overweg met algoritmes die in andere frameworks gemaakt zijn. Zo kun je de deeplearning Python libraries die Theano biedt inzetten. Ook de open-source Machine Intelligence-uitbreidingen van TensorFlow werken goed met OpenAI Gym samen.
