Boem! Computer wint met Stratego

AI Een nieuwe computer slaagt erin 84 procent van de menselijke spelers bij Stratego te verslaan. Dat is een grote prestatie, omdat de stukken van de tegenstander onzichtbaar zijn en er een enorme hoeveelheid zetten mogelijk is.

Slechts 16 procent van de beste menselijke spelers kan nog op tegen de Stratego-bot van DeepMind.
Slechts 16 procent van de beste menselijke spelers kan nog op tegen de Stratego-bot van DeepMind.

Bom onschadelijk gemaakt, vlag gepakt. Kunstmatige intelligentie heeft eindelijk ook het bordspel Stratego onder de knie. Stratego, een op oorlog gebaseerd spel waarbij twee spelers elkaar bestrijden met veertig stukken die verschillende ‘rangen’ van een leger vertegenwoordigen en ondertussen elkaars vlag proberen te lokaliseren, is ingewikkeld voor computers. Niet alle informatie ligt open op tafel en er zijn veel meer spelmogelijkheden dan in andere spellen.

Een nieuwe bot, DeepNash genoemd, verslaat nu met gemak bestaande Stratego-bots, en wint 84 procent van de spellen die hij speelt tegen menselijke experts, schrijven onderzoekers van DeepMind, een zusterbedrijf van Google dat kunstmatige intelligentie ontwikkelt, vrijdag in Science.

Vooruitgang van artificiële intelligentie (AI) wordt vaak afgemeten aan het succesvol spelen van spellen door computers. Een spel vormt een gecontroleerde omgeving waar menselijke denkstrategie wordt uitgedaagd. In 1997 was het groot nieuws dat schaakkampioen Gary Kasparov werd verslagen door DeepBlue, een computer van IBM. Het duurde vervolgens twintig jaar voordat een bot beter was in het spel Go dan ervaren spelers. Die bot, die de naam AlphaGo kreeg, werd net als deze Stratego-bot gemaakt door onderzoekers van DeepMind.

Een 1 met 535 nullen

Bij schaken, dammen en Go zijn heel veel spelvariaties mogelijk en is vooruitdenken noodzakelijk, maar de stukken liggen wel allemaal open op het bord. Bij andere spellen is sprake van verborgen informatie. Bij pokerspel Texas Hold’em of bridge bijvoorbeeld houdt een speler zijn kaarten tegen de borst. Stratego is ook een spel met verborgen informatie: een speler ziet niet hoe de stukken van de tegenstander staan.

AI-onderzoekers bijten zich al jaren stuk op Stratego – de meeste computers spelen niet beter dan menselijke amateurs. Het is zo moeilijk omdat het spel ontzettend veel spelmogelijkheden heeft: 10535 (een 1 met 535 nullen) om precies te zijn. Veel meer dan Go (10360 spelmogelijkheden) en Texas Hold’em (10164). Ook de beginstaat is uiterst complex, met 1066 mogelijkheden om de stukken te plaatsen. Bij Texas Hold’em zijn er bij twee spelers ‘maar’ 106 mogelijkheden voor de beginkaarten.

All-time klassement

Het zelflerende algoritme achter de Stratego-bot neemt beslissingen op basis van een bekende speltheorie: het Nash-evenwicht. Deze theorie zegt dat spelers weliswaar zelfstandig besluiten kunnen nemen, maar de consequentie daarvan hangt ook af van het besluit van de andere spelers. Een spel met een eindig aantal deelnemers en opties kent altijd minstens één evenwicht waarbij het voor de spelers geen zin meer heeft om de strategie te wijzigen als anderen daarin niet meegaan. Het Regularized Nash Dynamics-algoritme achter de Stratego-bot zoekt naar zo’n evenwicht.

Begin april van dit jaar heeft DeepNash het twee weken lang opgenomen tegen andere Stratego-bots en ervaren menselijke Stratego-spelers die actief zijn op Gravon, een spellensite waar Stratego fanatiek wordt gespeeld. DeepNash won 97 procent van de spellen die hij speelde tegen andere bots. Menselijke spelers moeten van goeden huize komen als ze het opnemen tegen DeepNash: de bot won 42 van de 50 spellen die meetelden voor een ranking. Dat komt neer op 84 procent. Daarmee wist de bot de derde plaats in het all-time klassement te bereiken.

Diplomacy-bot

Eind november stond in Science ook al een paper over een algoritme dat menselijke spelers had verslagen, ditmaal bij het bordspel Diplomacy. Het valt op dat het vaak grote techbedrijven zijn die hun spierballen laten zien door spellen te winnen: de Diplomacy-bot werd gemaakt door onderzoekers van Meta, het moederbedrijf van Facebook.

Bij Diplomacy strijden de spelers om de heerschappij over Europa. Spelers verplaatsen legers en marine-eenheden, en kunnen hiermee andere spelers aanvallen of juist ondersteunen. Diplomacy vraagt om meer dan pure strategie, onderhandelingen tussen de spelers zijn een belangrijk onderdeel van het spel, de bot moet dus ook taal kunnen begrijpen en genereren.

Het algoritme van de Diplomacy-bot (die de naam Cicero kreeg), heeft dan ook twee modules, één voor strategie en één voor dialoog. Gevoed met trainingsdata van eerder door mensen gespeelde (online) spellen wist de bot niet alleen geloofwaardig taalgebruik te produceren, maar ook af te wisselen tussen eerlijkheid en leugens.

Onzin

Ook Cicero presteerde goed, na veertig spellen hoorde de bot bij de 10 procent beste spelers. Maar het is lastig af te wegen hoeveel de beide modules hier precies aan hebben bijgedragen. De bot bleek ook veel onzin uit te kramen. In tekst had hij het dan bijvoorbeeld over heel wat anders dan de zet die hij daarna deed. Wellicht is het dus vooral de heel sterke strategische component die maakt dat de computer het beter doet dan veel (talig ingestelde) mensen.