Overview: Reinforcement Learning voor het vinden van bugs.

Door Andreas Veeckman

Inleiding

In deze overview post tonen we aan hoe Reinforcement Learning (RL) kan toegepast worden voor het testen van games. Dit doen we a.d.h.v. verscheidene papers en use cases. We tonen hoe u op deze manier fouten in het level design en game breaking bugs kan opsporen. Het kan handig zijn om eerst onze inleiding over RL te lezen indien u niet vertrouwd bent met het concept.

Testen van levels

De onderzoeksgroep SEED, deel van EA, bracht het afgelopen jaar een aantal papers naar buiten waar RL wordt toegepast om level issues op te sporen. Denk hierbij aan plekken waar een speler niet mag komen, niet kan komen of vast komt te zitten. Traditioneel worden levels getest door menselijke testers. De motivatie om dit automatisch te laten doen is meerledig:

  • Menselijke testers zijn duur
  • Het is eentonig en saai werk
  • Menselijke testers kunnen hun tijd beter besteden aan het testen van mechanics en speelervaring.

Bots doen dit zonder morren en ook nog eens heel effici├źnt. We bespreken in dit hoofdstuk een methodiek voorgesteld in twee papers die we hieronder bespreken.

Augmenting automated game testing with deep reinforcement learning

Deze paper legt de basis om een RL-agent te gebruiken om automatische tests meer flexibel te maken. In een development proces veranderen levels continu. Dit maakt het gebruik van scripts soms moeilijk. Agents die geleerd hebben om te navigeren kunnen ingezet worden om ook in veranderende omgevingen nuttig te blijven.

De methode

De auteurs stellen vier verschillende omgevingen op corresponderend met enkele uitdagingen:

  • Exploit: In deze omgeving ontbreekt een collision mesh op een stuk muur. De uitdaging voor de agent bestaat erin deze exploit te vinden.
  • Stuck Player: Een omgeving waarin bepaalde trigger volumes ervoor zorgen dat de speler niet meer kan bewegen. Dit bootst geometrie aan waarin de speler vast kan komen te zitten.
  • Navigation: Een omgeving waarin de agent de taak krijgt om van punt A naar punt B te navigeren.
  • Dynamic Navigation: Een omgeving gelijkaardig aan Navigation, maar met bewegende platformen.

De observatie is opgebouwd uit:

  • Agent info (locatie, rotatie, velocity, state)
  • Doel info (locatie)
  • Vision array: 12 ray casts in evenveel richtingen om de omgeving te observeren

De auteurs vergelijken verschillende algoritmes (PPO, SAC, TD3 en DDPG).

Omgeving voor Exploit en Stuck Player

Omgeving voor Navigation en Dynamic Navigation

Resultaten

De vier omgevingen worden ge├źvalueerd a.d.h.v. heatmaps en visualisaties.De agent start altijd op dezelfde plek. Hij krijgt een reward op basis van het bereiken van doelen. Een doel is een plek in het level. Wanneer een agent een doel bereikt verkrijgt hij een nieuw doel.

Exploit

Als we de heatmaps vergelijken van de scripted speler (a) en de volledig getrainde RL agent (d) zien we dat de RL agent duidelijk de exploit gevonden heeft voor de route naar de doelen rechtsonder.

Stuck Player

De oranje blokjes geven de locaties weer waar een agent zich bevond op het einde van een run. De paarse vierkanten geven de locaties aan van de volumes waar de controle van de agent uitgeschakeld wordt. Met het blote oog kunnen we zien dat dit overeenkomt met concentraties van eindposities. Een cluster algoritme kan deze automatisch gaan detecteren.

Navigation en Dynamic Navigation

De witte punten in de afbeeldingen rechts komen overeen met de verschillende doelen die een agent krijgt. In de rechterafbeelding zien we 2 doelen op de linkerzijde die we niet terugvinden in de linkerafbeelding. Deze doelen zijn moeilijker te bereiken en vereisen dus meer training.

Moeilijkheidsgraad

De bevinding dat meer trainingstijd nodig is om complexere taken uit te voeren motiveerde de auteurs om het data van het trainingsproces te gebruiken om een moeilijkheidsgraad te schatten. In de tabel hiernaast wordt een identieke taak uitgevoerd in de verschillende omgevingen. We lezen het aantal frames dat nodig is om een aandeel van de maximum beloning te verkrijgen. Hieruit is af te leiden dat de omgeving met bewegende platformen meer trainingstijd vereist.

Improving playtesting coverage via curiosity driven reinforcement learning agents

Het DRL model

De RL-lus indachtig defini├źren we hier de observatie, output en reward signal van de agents. Belangrijk is dat de bots net zoals echte spelers in interactie gaan met de applicatie. Daarom maken ze geen gebruik van een navigatie graaf of navmesh. Een Deep Neural Network vertaald de observatie naar een juiste actie.

De observatie is opgebouwd uit verschillende orientatie features (positie, velocity, rotatie), player states (is climbing, on ground, jump cool-down time) en een zichtsveld (12 raycasts die een afstand tot collision weergeven en een semantische mening over het oppervlak). De auteurs bespreken ook een variant waarbij een additioneel first-person view meegegeven wordt.

Mogelijke acties komen overeen met input acties die de speler kan nemen. Zo zijn er 3 continue acties (vooruit/achteruit, draai links/draai rechts en stap links/stap rechts) en 1 discrete actie (jump).

De reward signal bepaalt het gedrag van de agent. Het gewenste gedrag in dit geval is een agent die de map gaat exploreren. Het maakt dus niet uit goed de agent het spel speelt maar wel op hoeveel plekken in de map de agent zich begeeft. Om dit te bereiken krijgt de agent een beloning wanneer hij op onontdekt terrein komt.

Het gekozen trainingsalgoritme is Proximal Policy Optimization (PPO). Een populair algoritme door de robuustheid en ook geïmplementeerd in Unity ml-agents.

Resultaten

In onderstaande video tonen de auteurs hun resultaten:

Opinie over beide papers

De implementatie van de agents in beide gevallen lijkt zeer intuïtief (inputs en outputs). De coverage van het level is zeer groot en de agents zijn in staat ook op plekken te komen die een zekere skill vereisen. Het belang van een goede visualisatie van wat de agent doet wordt hier ook nog maar eens duidelijk. Door de verschillende visualisies is het duidelijk hoe een agent een bepaalde plek bereikt en waar er dus mogelijke fouten in het level zitten. Agents kunnen een waardevolle aanvulling zijn op bestaande scripts om deze eenvoudige taken uit te voeren. Het PPO algoritme blijkt hier een uitstekende keuze voor te zijn.

Zoeken naar bugs in de applicatie

Bovenstaande methode spoort fouten op in het level design maar kan niet gebruikt worden om fouten in de applicatie zelf op te sporen. Hieronder tonen we aan hoe RL ook daarvoor kan ingezet worden. De auteurs stellen het Wuji framework voor om on-the-fly games te testen. Ze focussen hierbij op het opsporen van crashes en het vastzitten (stuck/hang) van de applicatie. Andere types van fouten (logisch, balans of speler ervaring) zijn moeilijker om herkend te worden door een algoritme.

Het Wuji framework

Test omgeving

De auteurs werkten samen met het bedrijf NetEase. Op die manier hadden ze beschikking tot echte data en konden ze nauw samenwerken met de ontwikkelaars van games. Wuji werd getest op 2 online combat games: A Chinese Ghost story en Treacherous Water Online.

Architectuur

Het Wuji framework is een combinatie van verschillende AI technieken. De centrale idee is om policies te genereren die meer gamestates gaan verkennen waar mogelijks bugs voorkomen. Een policy is de manier waarop een agent gaat interageren met het spel.

Een agent is geïmplementeerd met een Deep Neural Network met een advantage actor critic architectuur (welkgeen ook aan de basis ligt van PPO). De agent wordt getrained opdat hij zo hoog mogelijk scoort in het spel.

In een mondvol woorden gebruikt Wuji een genetisch multi-objective optimalisatie algoritme om zoveel mogelijk game states te testen. Een populatie aan DNN agents wordt elke iteratie getrained waarop elke agent ge├źvalueerd wordt op basis van 2 doelstellingen: game score en bezochte game states. Op basis van deze evaluaties gebeurt de crossover binnen de populatie. Hierna worden de nieuwe species getrained waarop de populatie klaar is voor de volgende iteratie.

De kans dat een fout gevonden wordt doorheen dit proces is aanzienlijk hoger aangezien er tegelijk wordt ingezet op exploratie (verschillende speelstijlen) en exploitatie (geldige speelstijlen die daadwerkelijk de game spelen). Om de fouten te detecteren worden 2 soorten orakels geimplementeerd. Het eerste orakel houdt in de gaten of de applicatie nog draait. Dit orakel dient om crashes op te sporen. Het tweede orakel houdt de verandering van de game state in de gaten. Hierdoor wordt het mogelijk om te detecteren of de applicatie vast zit.

https://ieeexplore.ieee.org/abstract/document/8952543

Resultaten

Een testomgeving werd opgesteld met behulp van de ontwikkelaars van beide games. Zo werden er fouten geïntroduceerd in het spel. Alle fouten werden gevonden door Wuji. Meer zelfs: 3 bugs werden gevonden die eerder onbekend waren.

Opinie

Voor simpele games is Wuji waarschijnlijk overkill. Voor meer complexe games, zoals diegen gebruikt in de experimenten, lijkt Wuji een methode die zal presteren. Het vinden van fouten in de game logica is echter niet mogelijk hier. Het implementeren van een orakel dat dergelijke fouten detecteerd is hier de grootste uitdaging.

Conclusie

Reinforcement Learning zet grote stappen vooruit in de game wereld. 2 jaar geleden heerste nog twijfel hoe toegankelijk de technologie was om zelf mee aan de slag te gaan. De games hier voorgesteld zijn niet even complex als Starcraft maar bieden toch een ferme uitdaging. Dat RL-agents ook hier redelijk intuïtief voor te implementeren zijn is opmerkelijk. Indien in Unity gewerkt wordt is het zeker te overwegen om eens de ml-agents plugin te installeren en aan de slag te gaan met PPO.