Stratego spelen met Deepnash: ‘Ons AI-programma heeft ook leren bluffen’

Vlaamse wetenschappers werkten mee aan DeepNash, een AI-programma dat uitmunt in het spelen van Stratego. ‘Dit kan ook problemen  in de echte wereld oplossen.’

Twee Vlaamse computerwetenschappers hielpen een baanbrekend programma ontwerpen waarmee computers bij het militaire bordspel Stratego mensen kunnen verslaan. Bart De Vylder en Karl Tuyls werken bij het Britse artificiële-intelligentiebedrijf DeepMind, dat in 2014 werd overgenomen door internetgigant Google. Het succes werd bekendgemaakt in het vakblad Science. Het grote verschil met schaken en het bordspel Go, die ook door artificiële intelligentie (AI) gespeeld kunnen worden, is dat je bij Stratego niet weet hoe de stukken van de tegenstander zijn opgesteld. DeepMind boekte eerder al succes met het programma AlphaGo voor het spel Go. En nu is er dus ook DeepNash voor Stratego.

Hoe begin je aan de ontwikkeling van AI om Stratego te spelen?

Bart De Vylder: Er komt redelijk wat trial-and-error bij kijken. We probeerden methodes die bij andere spellen vruchten hadden afgeworpen, maar zonder enig idee over wat zou werken. Op een bepaald moment zie je dan een teken van leven in een van de nieuwste methodes en zet je daarop in.

Karl Tuyls: Trial-and-error, of gissen en missen, is de basisgedachte achter reinforcement learning of ‘versterkend leren’, een van de sleuteltechnieken achter DeepNash. Het programma leert uit ervaringen en uit beloningen die het krijgt. Je kunt het vergelijken met het aanleren van gedrag aan een hond. Na verloop van tijd begrijpt een hond wat er van hem verlangd wordt, zoals gaan zitten op commando. Een AI-programma complex gedrag aanleren, is vergelijkbaar.

Hoe beloon je een AI-programma?

De Vylder: Het is een digitale beloning. Het programma krijgt +1 als het een spelletje wint, 0 als er een gelijkspel is en -1 als het verliest. Dat werkt goed. Het is wel een uitdaging dat er veel tijd kan zitten tussen het moment waarop het een beslissing neemt en het moment van de beloning.

We hadden al schaakcomputers en een AI-programma voor Go. Stratego is een stap verder?

Tuyls: In 2017 kregen we bij DeepMind een documentaire over AlphaGo te zien. Dat liet een diepe indruk op me na. Ik besefte dat ik op een plek terechtgekomen was waar de grenzen van AI niet enkel afgetast, maar ook fundamenteel verlegd worden. Bij Stratego is er een opstelfase waarin spelers hun stukken op het bord plaatsen, iets wat schaken en Go niet hebben. Gemiddeld duurt een Stratego-spel ongeveer duizend zetten, veel meer dan de gemiddeld zestig voor schaken en driehonderd voor Go. Het spel simuleert beter de onvolledige informatie uit de echte wereld.

De Vylder: Stratego combineert aspecten van schaken of Go met onvolledige informatie zoals bij pokeren. De technieken die goed werken bij schaken of Go voldoen niet voor Stratego, want je weet niet hoe de stukken van de tegenstander zijn opgesteld. In vergelijking met poker is de hoeveelheid onvolledige informatie bij Stratego astronomisch. De complexiteit maakte van onze onderneming een grote uitdaging. We moesten een compleet nieuwe methode uitdokteren.

Hoe vang je de onvolledige informatie van de onzichtbare plaatjes van de tegenstander in AI op?

De Vylder: De elegantie van het algoritme achter DeepNash is dat de onvolledigheid nergens expliciet in rekening wordt gebracht. De AI wordt getraind om goede beslissingen te nemen op basis van de beperkte informatie die voorhanden is. Eigenlijk weten we nog altijd niet hoe vaak het programma raadt wat er op een stuk van de tegenstander staat. We merken wel dat het gesofisticeerde strategieën uitdoktert om met onvolledige informatie om te gaan. In partijen die DeepNash won van sterke menselijke spelers, kwam het geregeld voor dat het programma een aantal belangrijke stukken achterstond, maar er wel in was geslaagd meer informatie over de tegenstander te weten te komen dan omgekeerd.

Wat is de sleutel om de beste menselijke spelers te verslaan?

De Vylder: Het voortdurend aanpassen aan wat een tegenstander doet, is op zich niet zo moeilijk. Veel moeilijker is het om het leerproces te stabiliseren, zodat het steeds dichter bij een optimale strategie komt. Een van de andere onderzoekers in ons team zocht naar een precieze wiskundige formulering van dat proces. Hij ontdekte dat er een manier is om een vorm van ‘wrijving’ toe te voegen aan wiskundige vergelijkingen. Die zorgt ervoor dat AI-programma’s niet in rondjes blijven draaien, maar dat de AI bij elke poging steeds dichter bij haar optimale strategie komt. Het werkt als een extra beloning om te vermijden dat een programma zijn strategie bij elk nieuw spel te ver laat afwijken van de vorige.

Wat is de vernieuwing in het leermodel dat erbij komt kijken?

Tuyls: Het nieuwe is dat het leren ‘modelvrij’ gebeurt, wat wil zeggen dat het programma geen model nodig heeft van de wereld waarin het zich bevindt, noch van zijn tegenstanders. Het gaat niet plannen over mogelijke trajecten, zoals bij AlphaGo. Voorts is de innovatie gebaseerd op wiskundige vergelijkingen die beschrijven hoe een speelstrategie evolueert op basis van een survival-of-the-fittestachtige selectie: de best aangepaste overleeft. Onze modellen hebben soms iets heel biologisch.

Is het programma vernoemd naar John Nash, de beroemde wiskundige?

De Vylder: Inderdaad. John Nash bedacht het concept van een ‘Nash-evenwicht’, een combinatie van strategieën in een spel. Een belangrijke eigenschap van het Nash-evenwicht in Stratego is dat er meestal geen ‘beste zet’ is, zoals in schaken, want je wilt niet voorspelbaar zijn. DeepNash gaat op zoek naar het Nash-evenwicht door veel spelletjes tegen zichzelf te spelen.

Tuyls: We zien dat DeepNash geleerd heeft variaties in de beginopstelling te gebruiken, waarbij de vlag meestal beschermd staat opgesteld, maar soms niet om het onvoorspelbaar te houden. DeepNash heeft ook geleerd te bluffen en informatie achter te houden, vaardigheden die essentieel zijn om Stratego op hoog niveau te kunnen spelen. Het houdt ook rekening met het feit dat zijn tegenstander zich aanpast aan zijn acties.

Een week na jullie werk verscheen in Science AlphaCode, ook van DeepMind. Dat is AI om letter per letter softwareprogramma’s te schrijven. Is het concept vergelijkbaar met dat van jullie?

De Vylder: Er zijn zeker zaken die gelijklopen, zoals het gebruik van versterkend leren. Wat aartsmoeilijk was aan het maken van AlphaCode, is dat het op basis van een opdracht die in mensentaal gegeven wordt een correct programma moet genereren dat computers kunnen begrijpen. Net als DeepNash levert AlphaCode een belangrijke bijdrage aan het bereiken van onze missie.

Wat is die missie?

Tuyls: Onze missie is het vraagstuk oplossen van wat intelligentie is, en zo de wetenschap en mensheid vooruithelpen.

AlphaCode leert door het observeren van andere codes zonder dat het kennis heeft van computertaal. Is dat banaal datacrunchen zonder inzicht?

De Vylder: Hoewel ik het interessant vind om daarover na te denken, is het moeilijk om er absolute uitspraken over te doen, vooral omdat er geen consensus is over wat termen als kennis of inzicht precies betekenen. Het feit dat AlphaCode problemen kan oplossen die het tijdens de trainingsfase nooit heeft gezien, impliceert dat het erin slaagt om uit grote hoeveelheden data patronen te halen die breder toepasbaar zijn. Met wat goede wil zou je dat inzicht kunnen noemen.

Science publiceerde ook het programma CICERO van jullie concurrent Meta voor het oorlogsspel Diplomacy. Is de AI daarvan vergelijkbaar met die van jullie?

Tuyls: CICERO is ook een indrukwekkend resultaat. Het is een belangrijke stap in de richting van interactie met andere spelers in een natuurlijke taal. Dat alleen al is een mijlpaal. Dat werk en het onze bewijzen dat bordspellen nog steeds een uitstekende testbank zijn voor de vragen die we met AI willen oplossen.

De makers van CICERO stellen dat het programma de overtuigingen en intenties van spelers uit gesprekken kan afleiden en zo een dialoog kan sturen om zijn doel te bereiken. Dat klinkt heel menselijk.

Tuyls: ‘Klinkt’ is hier waarschijnlijk de juiste omschrijving. Ook het blufgedrag van DeepNash komt ‘menselijk’ over. Maar dat wil niet zeggen dat AI menselijke eigenschappen bezit. Heel wat AI’s, zoals CICERO, worden getraind door gebruik te maken van massa’s menselijke data. Het is dan niet verrassend dat ze menselijke kenmerken kunnen vertonen. Voor DeepNash hebben we echter geen menselijke data gebruikt.

Hoe zit het met AI die een ‘ziel’ zou kunnen krijgen, zoals iemand van Google beweerde?

De Vylder: Mensen projecteren gemakkelijk menselijke eigenschappen op andere systemen. Artificiële taalmodellen zijn zeer krachtig geworden. Ze kunnen verrassend uit de hoek komen. Maar dat wil niet zeggen dat er enige reden is om aan te nemen dat ze een bewustzijn zouden hebben. Integendeel, ze zijn op veel vlakken heel beperkt. De vraag of een eigenschap als bewustzijn enkel in biologische systemen kan voorkomen, is interessant. Maar het is in ieder geval onrealistisch te denken dat de huidige AI-systemen het kunnen hebben.

Zijn jullie ook met taalchatbots zoals ChatGPT bezig?

Tuyls: We hebben recent Sparrow geïntroduceerd, een AI voor dialoog die ondersteunend werkt en het risico op onveilige en ongepaste antwoorden verkleint.

Chatbot Minerva van Google lost wiskundige problemen op. Gaan we binnenkort nog iets zelf moeten doen?

De Vylder: Je kunt daar op verschillende manieren naar kijken. Sinds er rekenmachines zijn, is het wellicht enkel nog de echte liefhebber die uit nostalgie af en toe eens een staartdeling maakt. Zo is er meer tijd om na te denken over misschien interessantere vragen. Tijdens mijn doctoraat had ik graag toegang gehad tot een wiskundig orakel dat me kon helpen een bewijs te vinden voor een hypothese. Dat zou me meer tijd gegeven hebben voor zaken die ik leuker vond, zoals het bedenken van nieuwe wiskundige concepten. Ik denk dat mensen AI steeds vaker als hulpmiddel zullen gebruiken om efficiënter bij te leren. AI werkt zeer interactief en kan zich aanpassen aan het individuele niveau van een persoon.

Minerva ‘brainstormt’ blijkbaar met echte wiskundigen.

De Vylder: Ik denk dat het de bedoeling van het project is om een chatbot te maken die je als een slimme wiskundige collega kunt beschouwen, waarbij je snel nieuwe ideeën kunt aftoetsen. Maar ik weet niet in hoeverre het al zo werkt.

Een mogelijke toepassing van jullie AI-ontwikkelingen zijn zelfrijdende auto’s. Zijn er nog andere?

Tuyls: We geloven dat ons Stratego-werk kan bijdragen tot het aanpakken van grootschalige problemen uit de echte wereld. We denken aan toepassingen als verkeersmanagement en het optimaliseren van reistijden van chauffeurs om bijvoorbeeld de uitstoot van voertuigen te beperken. We kunnen denken aan het modelleren van het gedrag van mensenmassa’s en aan smartgrids waarmee elektriciteitsaanbieders en -afnemers hun gedrag op elkaar kunnen afstemmen. We maakten het algoritme waar DeepNash op steunt trouwens beschikbaar als opensourcesoftware, zodat iedereen ermee kan werken.

DeepMind maakte ook het bejubelde AlphaFold voor het voorspellen van eiwitstructuren, waarmee geneesmiddelen kunnen worden ontwikkeld.

De Vylder: AlphaFold is voor DeepMind wellicht het resultaat met de meest directe impact in de wereld tot nu toe. We waren er geen van beiden bij betrokken, maar het komt erop neer dat men erin geslaagd is een AI-model te bouwen dat op basis van een sequentie van aminozuren nauwkeurig kan voorspellen wat de driedimensionale vorm van het corresponderende eiwit is. Die vorm bepaalt sterk de functie van het eiwit. Het model werd getraind met een databank van eiwitten, waarvan de 3D-vorm experimenteel was vastgesteld. De kracht van het model zit opnieuw in de generalisatie. Het heeft aan de hand van de voorbeelden wetmatigheden ontdekt, waarmee het nauwkeurige voorspellingen kan doen voor eiwitten die het nooit heeft gezien. Ik vond de visie van DeepMind-oprichter en ceo Demis Hassabis daarover interessant: ‘Biologie is moeilijk wiskundig te beschrijven, maar zoals wiskunde de taal is van de fysica, zal AI de taal van de biologie worden.’

Meneer Tuyls, u dook op in Nature in verband met voetbalvoorspellingen. Waar ging dat over?

Tuyls: We hebben een onderzoeksproject met het voetbalteam Liverpool FC. De langetermijnvisie is het bouwen van een geautomatiseerde videoassistentcoach die kan helpen wedstrijden te analyseren, tactische keuzes te maken tijdens een match en het spel in realtime te verbeteren. Zo’n systeem zou bijvoorbeeld op basis van de eerste helft van een wedstrijd kunnen voorspellen waar spelers in de tweede helft gaan lopen en wat het effect van een verandering van de positie van een speler zou zijn. Daarnaast kan het helpen met spelers scouten en blessures voorspellen.

In Nature werd voorspeld dat België vorig jaar wereldkampioen zou worden. Helaas!

Tuyls: (lacht) Dat soort van voorspellingen blijft uiteraard moeilijk. Maar het feit dat grote Europese teams wetenschappers van topuniversiteiten in huis halen met doctoraten in wiskunde, natuurkunde en computerwetenschappen zegt veel, denk ik. Ook in België zie je de trend bij topteams als Brugge. Voetbal is een ideaal platform voor de ontwikkeling van AI-technieken. Het is een gesloten omgeving met zowel coöperatieve als competitieve eigenschappen, en met strategische interacties die te meten zijn. Een miniversie van de echte wereld dus, net als bordspellen. Ik verwacht veel nieuwe mogelijkheden voor sportteams met AI als hulpcoach. Maar dan wel uitsluitend als hulpmiddel om betere beslissingen te kunnen nemen. Het is niet de bedoeling om menselijke coaches te vervangen.•