Stratego, AI en interactieve spellen
20 augustus 2023
Eind vorig jaar versloeg het Britse bedrijf DeepMind met een kunstmatig intelligent systeem het bordspel Stratego. Stratego is het moeilijkste imperfect informatiespel. Het was het enige spel dat nog niet met kunstmatige intelligentie was verslagen. Maar nu waarschuwt onder andere DeepMind voor het gevaar van kunstmatige intelligentie.
Dat Stratego moeilijk verslaanbaar was, kwam vooral doordat het spel enorm veel spelsituaties kent, namelijk 10525 (= 10 met 525 nullen). Ter vergelijking, Go heeft 10175 spelsituaties. En om het plaatje nog vollediger te maken, Texas hold’em poker heeft 10164 spelsituaties.
Voor degenen die het bordspel Stratego niet kennen even een korte uitleg van het spel. Stratego is een spel voor twee persoon. Het bestaat uit een bord met 100 vakjes, waarvan er 8 ongebruikt in het midden een meertje vormen. Beide spelers krijgen 40 speelstukken, bestaande uit verschillende militaire rangen, een spion, enkele bommen en een vlag.
De spelers stellen de speelstukken naar eigen inzicht op. Waarbij ze vanzelfsprekend de vlag niet vooraan zetten. Want doel van het spel is de vlag van de tegenstander te veroveren. Om de beurt verplaatsen de spelers een stuk. Komt een stuk van een speler daarbij op een bezet vak van de ander, dan slaat hij het stuk en wint degene met de hoogste rang. Daarop zijn enkele uitzonderingen. Bijvoorbeeld als het andere stuk een bom is, die overigens niet mag worden verplaatst.
Spelers kunnen elkaars speelstukken niet zien. Dat maakt Stratego een imperfect informatiespel. In tegenstelling tot bijvoorbeeld go en schaken, waarbij die spelstuk-informatie van de tegenstander wel beschikbaar is. Bij het slaan van een stuk wordt die informatie bij Stratego vanzelfsprekend wel bekend (de winnaar blijft staan, de verliezer verdwijnt van het bord). Het komt daarna aan op onthouden hoe de dan bekende stukken zich verplaatsen.
Verder kent Stratego strategieën. Dat begint al bij het plaatsen van de 40 speelstukken aan het begin van spel. Het gaat er immers om de vlag te verdedigen. Sommige spelers omringen de vlag door bommen, die alleen verslagen kunnen worden door mineurs. Om de bommen plaatsen ze dan hoge militairen. Et cetera. Vanuit elke gedachte kan een speler een eigen opstellingsstrategie hebben.
In het naar eigen inzicht plaatsen van de speelstukken voor het begin van het spel onderscheidt Stratego zich ook van andere spelen. Zoals schaken, waar de slechts 16 speelstukken in een vaste beginopstelling staan. De eigen-implematiefase (zoals de onderzoekers het noemen, geeft (of gaf) een extra complicatie voor het instrueren van de kunstmatig intelligente spelomgeving.
Tijdens het spelen kunnen ook strategieën worden gebruikt. Die kunnen berusten op aanval, verdediging, misleiding of bluf. Een speler kan bijvoorbeeld met zijn generaal (de hoogste rang na maarschalk) een opofferingsaanval beginnen. De generaal stormt dan door het veld van de tegenspeler. Met het risico op de maarschalk, de generaal of een bom te stuiten; een kans van 8 op 32.
Bluffen is ook een strategie die op verschillende manieren kan worden uitgevoerd. De onderzoekers van DeepMind halen in hun rapport daarvoor John Neumann aan, samen met Oskar Morgenstern bedenker van de speltheorie: het echte leven bestaat uit bluffen, uit kleine tactieken van bedrog, uit jezelf afvragen wat de andere man denkt dat jij gaat doen.
Bluffen kan bestaan uit het naar voren laten gaan van je verkenner, zoals de generaal in het vorige voorbeeld. Afhankelijk van wat je tegenstander daarbij denkt, zal er een reactie komen. Maar bluf kan ook al in de opstelling zitten, bijvoorbeeld door de bommen in een hoekje rondom een verkenner te plaatsen. Terwijl de vlag ergens aan de andere kant staat.
Het Britse DeepMind, opgericht in 2010, is sinds 2014 een volledige dochter van Alphabet Inc., ook het moederbedrijf van Google. Het bedrijf heeft de afgelopen jaren verschillende indrukwekkende prestaties geleverd op het gebied van kunstmatige intelligentie. In 2016 bouwde DeepMind bijvoorbeeld al het KI-syteem AlphaGo, waarmee het Go-grootmeester Lee Sedol versloeg.
DeepMind heeft ook enkele programma’s ontwikkeld waarbij KI-systemen de videospellen Dota, StarCraft en Capture the flag speelden. Dit zijn evenals Stratego imperfecte informatiespellen. De meeste beslissingen moeten echter bij deze real-time strategiespellen snel en instinctief worden genomen. En achter elkaar doorgaand, spelers doen dus niet om en om een zet zoals bij Stratego.
Bij Stratego wordt langzaam, weloverwogen en met logische beslissingen gespeeld. ‘Dat maakte het spel tot een uitdaging voor het team van 35 onderzoekers’, vertelt projectleider Julien Perolat. ‘Met Stratego boekten wij en andere KI-ontwikkelaars weinig vooruitgang door de complexe aspecten van het spel. Af en toe was er een succesje, maar dat kwam tot vorig jaar nooit boven het niveau van een amateur speler’.
De onderzoekers van DeepMind noemden hun Stratego-project DeepNash, naar het Nash-evenwicht dat ze in gedachten hadden bij de uitvoering. Het Nash-evenwicht is de situatie in de speltheorie waarbij geen van de spelers voordeel heeft door van strategie te veranderen.
De ontwikkelaars maakten er een leeralgoritme van dat ze Nash Dynamics noemden. Ze combineerden dit met een neuraal netwerk. Met een algoritme gebaseerd op de speltheorie speelde het systeem miljarden keer Stratego tegen zichzelf. Hierdoor kon het systeem in korte trainingstijd veel leren. Veel sneller dan wanneer het spel in real-time zou worden gespeeld tegen een menselijke tegenstander.
Het algoritme richtte zich op een optimale strategie. Dat garandeerde een winst van minstens 50% tegen een foutloos spelende tegenstander. Tijdens het spelen paste het systeem zich continu aan. Het aantal winnende beslissingen nam daardoor toe.
Na de training speelde DeepNash tegen andere geavanceerde Stratego-systemen en top Stratego-spelers op het Duitse spelplatform Gravon. Het systeem versloeg daarbij de andere robots overtuigend met 97% gewonnen spellen. Tegen de menselijke spelers schaarde het zich tussen de top-drie spelers met een winstpercentage van 84%.
De Nederlander Vincent de Boer, meervoudig wereldkampioen Stratego, was ondanks zijn deelname aan het project verrast door het spelniveau van DeepNash. Hij verwachtte niet dat een KI-systeem ook zijn WK-niveau zou kunnen bereiken. Maar hij speelde zelf tegen DeepNash. Daardoor was hij niet verrast toen het systeem de toppositie op Gravon behaalde.
Na bovenstaande is wellicht duidelijk wat de gevolgen kunnen zijn van deze stap bij kunstmatige intelligentie. DeepNash trainde zichzelf met het ingestelde algoritme (programmeer-regels) in het spelen van een imperfect informatiespel. Dus met verborgen informatie over de stappen van de tegenstanders en, in het geval van Stratego, enorm veel spelsituaties (die 10525) en bij elke beurt nog talrijke opties. Daarbij heeft het systeem ook nog een onfeilbaar geheugen, in tegenstelling tot mensen, om zich stukken te herinneren die zijn geslagen en daardoor zichtbaar werden.
Wij denken dan dat dit een mooi uitgangspunt is voor de volgende generatie videospellen. Een slim systeem dat tegen een videospel speelt kan immers ook zelf het videospel zijn. Dat kan slimme, zichzelf aanpassende en nog betere interactieve videospellen opleveren. En ook aangepaste bestaande online gokspellen als poker en blackjack.
Maar het kan ook de reden zijn dat onderzoekers, ook die van DeepMind, nu waarschuwen voor de ontwikkelingen rond kunstmatige intelligentie. Want slimmer en sneller denkend dan wij als mens willen we (nog) niet. Helemaal niet als die robots in staat zijn zelf goede beslissingen te nemen.
