Soldaten voor het virtuele slagveld

Op de middelbare school stak Jan Paul van Waveren al meer tijd in computerspelletjes dan in huiswerk. Toch liep het niet slecht met hem af, zelfs niet toen hij aan de universiteit bezig bleef om met wat vrienden computers aan elkaar te koppelen teneinde elkaar in een spelletje Doom virtueel overhoop te knallen. Binnenkort studeert hij af op de kunstmatige intelligentie die hij voor het schietspelletje Quake III Arena ontwikkelde.

Beeld uit Quake

Meestal heet Jan Paul van Waveren, Jan Paul van Waveren, maar soms waart hij rond in duistere kelders, een onwaarschijnlijk groot wapen in zijn handen, schietend op alles wat beweegt. Dan heet hij Mr. Elusive. De laatste tijd heeft Mr. Elusive echter niet zoveel kills meer gemaakt.

Dat komt niet alleen omdat hij als zesdejaars zijn studie Technische Informatica aan de TU Delft nu maar eens moet afmaken. Het komt ook omdat hij het aanbod van een baan door een Amerikaanse spelletjesfabrikant niet afwees. Nu programmeert hij de spellen die hij ooit speelde. En zoals iedere programmeur weet: spelletjes behoren tot de meest veeleisende software die er bestaat. Kantoorsoftware mag best wel eens een seconde haperen, bij spelletjes is dat uit den boze.

Op de middelbare school speelde Mr. Elusive reeds de spelletjes van zijn huidige werkgever id Software: Wolfenstein en Doom. Dit zijn zogenaamde first-person games. Je kijkt door de ogen van een commando, die met een bepaalde opdracht een doolhof ingestuurd wordt. Je taak is het doolhof te verkennen, geheime deuren op te sporen, verstopte schatten, wapens en andere voorwerpen op te sporen en iedereen die je tegenwerkt genadeloos af te maken. Die tegenstanders, meestal monsters genoemd, zijn niet echt intelligent: ze staan altijd op dezelfde plek te wachten en mikken niet erg nauwkeurig. Natuurlijk kun je ook geraakt worden: een gezondheidsmetertje in beeld geeft aan of het niet weer eens tijd wordt een verbanddoos op te sporen.

Doom was indertijd revolutionair. Niet alleen was de grafische kwaliteit beter dan alles daarvoor, fanatieke spelers konden zelf levels maken. Computerspelletjes van dit type bestaan namelijk uit verschillende onderdelen, bijvoorbeeld een onderdeel voor de grafische representatie van het doolhof en een ander voor de mogelijke bewegingen van de commando. Een level is een datastructuur die onder meer de vorm van het doolhof, de locatie van de schatten en de aantallen tegenstanders vastlegt. De makers van Doom besloten het format van die datastructuur openbaar te maken. Daardoor kon iedereen zijn eigen doolhoven ontwerpen. Fanatieke spelers die de meegeleverde doolhoven uitgespeeld hadden, konden hun eigen exemplaren maken en die uitwisselen via internet. Zo werd Doom een spel dat je nooit helemaal ‘uit’ had.

Skin

‘Voor Doom heb ik veel levels gemaakt’, vertelt Van Waveren. ‘Toen kwam de opvolger, Quake 1. Dat kon je via een lokaal netwerk of via internet tegen elkaar spelen. Dat heb ik veel gedaan. Nu is de hele spelletjeswereld veel groter en commerciëler geworden, maar toen was het een relatief kleine Quake 1 gemeenschap. Ik zat bij een clan, we hadden een eigen skin en zo.’

Skin, dat woord vraagt om toelichting. Een figuur in een computerspelletje bestaat uit een draadmodel. De vlakjes in dat model worden gevuld met een textuur, een patroon van kleuren. Al die vlakken samen, de skin, bepalen het uiterlijk van de figuur. In Quake 1 was het mogelijk zelf een skin te maken. Monsters met het hoofd van Microsoft-voorman Bill Gates werden al snel populair.

‘Regelmatig brachten we onze computers bij elkaar’, gaat Van Waveren verder. ‘Alleen was je uren bezig om ze aan elkaar te koppelen. Dan konden we nog net een uurtje spelen voor het tijd werd om de zaak weer op te breken. Via het Internet kon je meteen aan de slag. Dat had echter ook nadelen. Ten eerste krijg je een hoge telefoonrekening. Ten tweede kan een langzame verbinding met het Internet het spel moeilijk speelbaar maken. Daarnaast houd je het niet lang uit, als je niet goed geoefend hebt.

Beeld uit Quake

Oefenen tegen de niet al te intelligente monsters die in Quake 1 ingebouwd zaten, had echter niet zoveel zin. Wat zou het toch mooi zijn als je kon oefenen tegen de computer, maar dan met slimmere tegenstanders, bedacht Van Waveren. Hij bleek niet de eerste. Op internet was een groot aantal bots te vinden. Bots (het woord is afgeleid van robots) zijn programmaatjes die intelligent gedrag vertonen. De programmaatjes die namens zoekmachines het internet afstruinen om informatie te catalogiseren heten ook bots. In Quake 1 is een bot een programma dat zich gedraagt als een menselijke tegenstander. Daardoor wordt het oefenen stukken realistischer.

‘Van de beschikbare artificiële spelers was er eentje duidelijk de beste’, aldus Van Waveren. ‘Toch gingen me daaraan op den duur dingen opvallen. In de moeilijkste stand kon je er niet van winnen. De bot vertoonde welliswaar intelligent gedrag, maar hij schoot meteen raak op het moment dat hij tevoorschijn kwam. In een lagere stand schoot de bot minder nauwkeurig, maar deed ook meteen minder intelligente dingen. Daarom wilde ik hem graag aanpassen, maar de broncode was niet beschikbaar. Toen ben ik begonnen zelf kleine aanpassingen te maken aan het spel.’

‘Een van de eerste was een anti-camp modificatie. Sommige spelers blijven eindeloos op een gunstige plek hangen om anderen in de hinderlaag te lokken. Dat soort campers worden niet sportief gevonden. Mijn programmaatje gaf je een waarschuwing als je te lang op dezelfde plek bleef hangen. Ging je dan niet weg, dan teleporteerde hij je naar een andere plek. Of je kreeg een regenwolkje met bliksem boven je hoofd, dat je overal achtervolgde. Dat was niet goed voor de gezondheid.’

Omicron

In 1997 had Van Waveren een bot af die een menselijke speler op een betrouwbare manier simuleerde. Omicron, zoals de bot heette, was in een mum van tijd populair. Binnen een paar uur na de release hadden 10.000 mensen hem van het internet geplukt. Na twee weken had hij bijna de top van populairste Quake-bots veroverd. Van Waverens programmeertalent viel op en hij kreeg een baan aangeboden. Die liet hij lopen – hij wilde eerst zijn studie afmaken.

‘Toen ik eraan begon wist ik niet zoveel van kunstmatige intelligentie’, zegt hij. ‘Ik browste gewoon wat door de broncode van Quake, las een beetje en gebruikte mijn gezond verstand.’ Dat gezonde verstand maakte dat hij gebruik ging maken van ‘waypoints’, de digitale versie van Klein Duimjes kiezels. Een waypoint is een plek in het doolhof waarop de artificiële speler zich oriënteert. Zo verdwaalt hij niet tijdens zijn tocht door het doolhof. Het is slechts één van de dingen die hij moet kunnen. Hij moet bijvoorbeeld ook een tegenstander signaleren en gericht schieten. Natuurlijk is al de informatie, zoals posities van tegenstanders, bekend bij het Quake-programma zelf, maar daar mag de bot geen gebruik van maken, want anders heeft hij een veel te grote voorsprong op zijn menselijke tegenstander en speelt hij in zekere zin vals. De bot moet dus uitrekenen of hij een tegenstander vanuit de plek waar hij staat menselijkerwijs kan zien voor hij mag schieten.

‘De methode met waypoints is nog vrij primitief’, zegt Van Waveren. ‘Of je moet als mens alle waypoints voor hem inprogrammeren, wat arbeidsintensief is, of je moet hem zelf het doolhof laten verkennen. In dat laatste geval gedraagt hij zich iedere keer weer als een beginnende speler en dat schiet niet op. Een probleem met Quake 1 was bovendien dat de waypoints zich lastig lieten inprogrammeren in de datastructuren van de speciale programmeertaal die werd gebruikt om Quake 1 aan te passen.’

De komst van Quake 2 was een uitkomst. De spelregels en artificiele intelligentie werden hier geprogrammeerd in de programmeertaal C, wat in feite betekende dat alle beperkingen vervielen. Bovendien maakte id Software net als bij Quake 1 een deel van de programmacode bekend, zodat fanatici delen van het programma naar eigen smaak konden aanpassen.

Voor Quake 2 schreef Van Waveren de Gladiator bot. Daar viel veel meer aan in te stellen dan aan de voorganger. Zo kunnen de tegenstanders op een subtiele manier geprogrammeerd worden. De menselijke speler kan bijvoorbeeld aangeven of zijn kunstmatige tegenspeler een voorkeur aan de dag moet leggen voor bepaalde wapens, of hij defensief is ingesteld of juist offensief. Dat instellen gebeurt onder andere met fuzzy logic. Het is dus niet zo dat de kunstmatige speler een eigenschap wel of niet heeft – dat zou hem te voorspelbaar maken. Hij kan net als een mens zijn voorkeuren hebben, maar daar regelmatig van afwijken. De tegenstanders kregen ook een vocabulaire mee, zodat ze kunnen communiceren, zowel met de menselijke speler als onderling. Ook waren ze in staat simpele zinnen te ‘begrijpen’.

Capture the flag

De Gladiatorbot verscheen vanaf december 1998 op het internet. Er was ook een CTF (capture the flag) variant van het spel Quake2 beschikbaar. Normaal gesproken is het doel van het spel het bereiken van een bepaald eindpunt, meestal een deur naar het volgende level. Bij CTF zijn er twee teams en is het de kunst de vlag van het andere team te veroveren. Van Waveren programeerde de bots zodanig dat ze ook dit spel variant begrepen.

Opnieuw gingen van Waverens activiteiten niet ongemerkt voorbij: ‘In juni 1999 kreeg ik een mailtje van Graeme Devine, project leider bij id Software. Ze waren bezig met Quake 3. Ze wilden een bot inbouwen, maar daar hadden ze weinig ervaring mee, terwijl ik er al twee tot drie jaar mee bezig was. De vraag was of ik eens in Dallas, Texas langs wilde komen om wat te praten en ideeen uit te wisselen. Ik ging er totaal niet heen met de gedachte een baan mee terug te nemen. Het leek me gewoon een leuk uitje.’

Beeld uit Tomb Raider

‘Eenmaal daar lieten zij eerst zien hoe hun bots in elkaar zaten en daarna kwam ik met de mijne’, gaat hij verder. ‘Ik had mijn bots zo gebouwd dat ze makkelijk te integreren waren in een ander spel. We hadden toen het idee om dat dan ook maar eens te proberen. In een paar dagen hebben we hem toen aangepast voor Quake 3. Dat werkte zo goed dat ze dachten: misschien moeten we die bot of delen ervan gewoon overnemen. Ik heb de broncode aan hen verkocht en werd ingehuurd voor verdere integratie en uitbreiding van de botcode. In eerste instantie ben ik vooral met de kunstmatige intelligentie bezig geweest, maar nu doe ik ook allerlei andere dingen. Zo werk ik nu bijvoorbeeld aan bepaalde onderdelen van een nieuwe versie van Doom.’

Ondertussen wil hij ook nog afstuderen, en wel op zijn werk voor Quake 3. Dat betekent vooral schrijven, want het werk is al gedaan. De door van Waveren bedachte bot voor Quake 3 kan niet alleen in zijn eentje door het doolhof manoeuvreren, hij kan ook samenwerken met andere bots, als ware het een legereenheid.

Basisvaardigheden

De bot voor Quake 3 is opgebouwd uit vier lagen’, legt Van Waveren uit. ‘In de onderste laag zit de basis: de input en output van de bot waaronder de representatie van de omgeving en de mogelijke bewegingen. Die bewegingen zijn bijvoorbeeld lopen en springen. Voor de representatie van de omgeving maak ik gebruik van area’s. Een area is een samenhangend deel van de omgeving. De kunstmatige speler weet in welke area en waar hij zich in de huidige area bevindt en kan vanuit een area snel achterhalen waar hij heen kan. Bij lopen is dat eenvoudig: dat zijn de aangrenzende area’s. Maar bij springen kan hij ook naar area’s die niet direct aan de huidige grenzen. Dat moet allemaal uitgerekend en vastgelegd worden.’

De onderste laag legt dus vast wat de kunstmatige speler allemaal aan basisvaardigheden in huis heeft en zorgt voor de algemene informatievoorziening. Maar daarmee doet hij nog niets. De laag daarboven houdt zich onder andere met korte-termijndoelen bezig. Als hij bijvoorbeeld maximaal twee dingen kan dragen en hij heeft al een verbanddoos, is het niet verstandig een tweede doos op te pikken, tenzij hij zwaar gewond is. ‘Hij moet dus bepalen hoe graag hij het voorwerp wil hebben’, zegt Van Waveren. ‘Daarvoor gebruik ik fuzzy logic. Daarmee weeg je de verschillende argumenten tegen elkaar af.’

De derde laag verzorgt de echte intelligentie: het bepalen van de lange-termijndoelen en de overlevingsstrategie. Daartoe werkt de bot verschillende ‘states’ af. Hij begint bij zijn lange-termijndoel. Daarvan leidt hij de korte-termijndoelen af, gezien de huidige omstandigheden. Dat kan er bijvoorbeeld toe leiden dat hij naar de puzzel-state moet om een probleem op te lossen. Als hij een begerenswaardig voorwerp ziet liggen, maar hij kan er niet bij (bijvoorbeeld omdat er een gesloten traliedeur voor zit), dan moet hij een nieuw doel bepalen dat hij eerst moet halen voor hij het voorwerp kan bereiken.

Komt hij een tegenstander tegen, dan gaat hij naar de ‘battle-state’. De eigenschappen van de kunstmatige speler, vastgelegd in de tweede laag, bepalen dan bijvoorbeeld of hij liever springt of bukt om kogels te ontwijken. Gaat de tegenstander ervandoor, dan moet hij bepalen wat gegeven de omstandigheden het best is: de achtervolging inzetten of terug gaan naar de lange-termijndoelen. Besluit hij de achtervolging in te zetten, dan moet hij na een paar seconden opnieuw beslissen: heeft het nog zin? Tijdens een gevecht kan de bot ook beslissen zelf de benen te nemen als hij er slecht aan toe is.

Beeld uit Quake

Luitenant

De technologie hierachter is die van het expert systeem: een heleboel als-dan-regels, die voortdurend afgewerkt worden. De intelligentie volgt uit de interactie van de vele regels. Ten opzichte van veel traditionele expert systemen is er echter een beperkende factor: tijd. Een vloeiend verloop van het spel gaat voor alles. Het heeft ook weinig zin alle regels iedere tiende van een seconde te doorlopen (dat is de tijdseenheid waarmee de bots in Quake 3 denken). Als de kunstmatige speler net rondgekeken heeft of er begerenswaardige voorwerpen in zicht zijn, hoeft hij dat een halve stap later niet nog eens te doen. Speuren naar tegenstanders blijft echter wel cruciaal.

Als je wilt kun je het ook allemaal voor je laten doen. Een menselijke speler kan een aantal bots om zich heen verzamelen, die hij als een generaal aanvoert. Van Waveren: ‘Dat kan ook als je met mensen speelt, maar bots zijn over het algemeen gehoorzamer.’ Sterker nog, het is mogelijk een luitenant aan te wijzen die met een paar recruten bijvoorbeeld een belangrijke plek verdedigt. De intelligentie daarvoor zit in de vierde laag. Een leider moet immers niet alleen zijn eigen doelen bepalen, maar ook die van zijn ondergeschikten. Via tekst worden de bevelen uitgewisseld en het maakt de bots niet uit of die van een mens komen of van een andere bot. Als je dat zou willen, zou je zelfs legers van bots tegen elkaar kunnen laten vechten en dan voor het scherm kijken wie het er het beste vanaf brengt.

Maar daar gaat het natuurlijk niet om bij schietspelletjes. Het gaat om overlevingsdrang, agressie afkoelen, puzzelen en vooral superioriteitsgevoelens tot uiting brengen. En om steeds slimmere technologie, de grondslag van een miljardenindustrie, die bezig is Hollywood qua omvang te overvleugelen.

Eerder verschenen in Delft Integraal, nr 2, 2001.