Een kunstmatig intelligent systeem van het Britse bedrijf DeepMind heeft geleerd menselijke tegenstanders te misleiden en te verslaan in het bordspel Stratego, een spel met een onvoorstelbaar hoog aantal mogelijke scenario’s.
Een kunstmatig intelligent systeem (AI) heeft deskundige menselijke spelers verslagen in het bordspel Stratego. Dat op oorlog gebaseerde bordspel heeft meer mogelijke spelscenario’s dan schaken, go of poker.
Het systeem is ontwikkeld door het Britse bedrijf DeepMind, en werd een van de hoogst gerangschikte online spelers van de Napoleon-versie van Stratego. Dat deed het onder andere door te bluffen met zwakkere stukken, en door waar nodig belangrijke stukken op te offeren.
Heersen zwermen killerdrones straks over het slagveld?
Een luchtruim gevuld door kunstmatig intelligente killerdrones, die autonoom bepalen wie blijft leven en wie zal sterven. Hoe waarschijnlijk is dat?
‘Voor ons was het verrassendste gedrag van de AI zijn vermogen om waardevolle stukken op te offeren en zo informatie te krijgen over de opstelling en strategie van de tegenstander’, zegt DeepMind-onderzoeker Julien Perolat.
10535 spelsituaties
Bij Stratego proberen twee spelers de vlag van de tegenstander te pakken te krijgen, die ergens tussen de veertig speelstukken verborgen zit. De meeste stukken zijn militairen, genummerd van één tot tien. Wanneer twee militairen elkaar op het bord ontmoeten, verslaat de militair met de hogere rang de lager geplaatste (behalve de spion, die de maarschalk kan verslaan).
Zolang stukken elkaar nog niet zijn tegengekomen, kunnen de spelers de identiteit van de stukken van de tegenstander niet zien. Daarmee verschilt Stratego van spellen als schaken en go, waar beide spelers alle beschikbare informatie vanaf het begin kunnen zien.
Wat Stratego nog ingewikkelder maakt, is dat er maar liefst 10535 mogelijke spelsituaties zijn. Ter vergelijking: go heeft 10360 mogelijke speltoestanden, schaken en poker hebben er nog minder.
Optimale strategie
Perolat en zijn collega’s van DeepMind noemden hun AI DeepNash. Ze leerden het systeem Stratego door het 5,5 miljard keer tegen zichzelf te laten spelen. De gesimuleerde trainingstijd kwam grofweg overeen met een paar eeuwen stratego spelen. De AI had geen enkele kennis van bestaande menselijke strategieën. Ook was het systeem niet getraind om tegen specifieke tegenstanders te spelen.
Het zou veel te veel rekentijd vergen om in de training alle mogelijke spelscenario’s door te nemen. In plaats daarvan heeft DeepNash een algoritme dat zijn gedrag voortdurend stuurt in de richting van een optimale strategie die gebaseerd is op speltheorie, aldus DeepMind-onderzoeker Karl Tuyls. Die optimale strategie garandeert ten minste 50 procent winst tegen een foutloos spelende tegenstander, zelfs als die tegenstander precies weet wat de AI van plan is.
Het resultaat is een AI winnende beslissingen kan nemen, ondanks de verborgen informatie over de stelling van de tegenstanders, een enorm aantal mogelijke speltoestanden en tal van mogelijke opties voor elke beurt. ‘Dit is iets dat we niet eerder konden doen’, zegt AI-onderzoeker Julian Togelius van de New York University.
WK Stratego voor computers
DeepNash heeft zowel menselijke als computergestuurde tegenstanders verslagen. In vijftig potjes op een online spelletjesplatform tegen deskundige menselijke spelers behaalde het systeem een winstpercentage van 84 procent. Daarmee behoorde het tot de beste drie spelers. De menselijke tegenstanders wisten niet dat ze tegen een AI speelden.
Daarnaast behaalde de AI een winstpercentage van 97 procent tegen een aantal computerspelers. Daaronder bevonden zich verschillende die eerder het wereldkampioenschap Stratego voor computers hadden gewonnen.
‘Goede spelers kunnen de stukken van hun tegenstander onthouden en voorspellen in welke patronen ze worden verplaatst’, zegt Georgios Yannakakis, computerspelonderzoeker aan de Universiteit van Malta. ‘DeepNash doet dat allebei goed, deels dankzij een competitief voordeel in geheugen. Hij speelt op interessante en onvoorspelbare manieren, met elementen van bluf.’
