Winnen met het bordspel Stratego betekent dat je af moet gaan op onvolledige informatie. Voor het eerst is dit een AI, DeepNash, nu gelukt.
Harde dobber voor Deepmind
Wat Stratego voor een AI een lastige noot maakt om te kraken, zijn twee dingen. Ten eerste is dat de onvolledige informatie. Immers, aan het begin van het spel weet je alleen waar je eigen stukken staan. Ten tweede duurt een game Stratego erg lang, vaak honderden zetten. Dat tezamen betekent dat de strategieën die tot nu toe zijn gebruikt om bijvoorbeeld te winnen met poker en met schaken en go, niet werken bij Stratego.
Brute kracht werkt ook al niet. Het speelveld is weliswaar een stuk kleiner dan bij go (10 X 10 in plaats van 19 X 19). Omdat er zoveel verschillende types stukken zijn die op een willekeurige manier kunnen worden neergezet, zijn er meer mogelijkheden (een getal met 535 cijfers) dan alle deeltjes in het universum (een getal met 80 cijfers).
Hoe is het Deepmind toch gelukt om Stratego te kraken?
Hiervoor ontwikkelde het team van DeepMind de AI DeepNash. Deze streeft naar een Nash evenwicht, waardoor deze strategie niet te kraken is. DeepNash leerde zichzelf Stratego door ontelbaar veel potjes tegen zichzelf te spelen. Hierdoor werd DeepNash erg goed in Stratego: op het online bordspellenforum Gravon behaalde de kunstmatige intelligentie de derde plaats op de ranglijst van de beste spelers ooit. Gemiddeld won DeepNash 84% van de potjes tegen de beste menselijke Strategospelers ter wereld.
Meer dan alleen een spelletje
Door deze prestatie leerde het team van DeepMind twee belangrijke skills. Ze slaagden erin om een AI op basis van onvolledige informatie toch de beste besluiten te laten nemen, een typisch menselijke vaardigheid. Ten tweede, hoe ze een AI verschillende uitkomsten kunnen laten afwegen om zo de beste te vinden.
Natuurlijk is Stratego een eenvoudige omgeving, vergeleken met de werkelijke wereld. Maar in toekomstige AI projecten, brengen deze successen dit binnen bereik. Voor wie niet bang is voor een beetje vakjargon, kan hier het artikel in Nature lezen.
Meer over Stratego
Stratego is een bekend bordspel dat in de vorm van nu, al sinds het einde van de Tweede Wereldoorlog bestaat. Voor wie het spel nog niet kent: op een bord met 10 x 10 velden kan iedere speler zijn 40 speelstukken in elke volgorde die hij maar wil neerzetten. Zolang hij dat maar op de vier achterste rijen doet. Het doel is de verovering van het vijandelijke vaandel, één van de 40 stukken.
Je kan niet zien op welke manier de tegenstander zijn stukken heeft neergezet. De stukken hebben rangen, waarbij het sterkste stuk, de maarschalk, elk ander stuk kan verslaan.
De generaal, het op een na sterkste stuk, verslaat alle stukken behalve de maarschalk, enzovoort. Als twee stukken van gelijke sterkte elkaar treffen, wordt het wederzijdse zelfmoord. Het zwakste stuk, de spion, is als enige stuk in staat om de maarschalk te verslaan. Dan zijn er nog bommen, die niet kunnen bewegen maar die ieder ander stuk verslaan behalve de mineur. Dus zelfs als de vijandelijke spion dood is, kan je met de maarschalk nog steeds geen ongehinderde slachting aanrichten.
Van geen enkel stuk kan je daarom zeker zijn dat het helemaal veilig is. Goed kunnen bluffen is een essentiële skill om een potje te winnen. Dat maakt Stratego een populair en spannend spel.
