AI heeft een hekel aan onzekerheid. Maar om door onze onvoorspelbare wereld te navigeren, moet het leren keuzes te maken met imperfecte informatie - zoals we elke dag doen.
DeepMind gewoon een steek gestoken bij het oplossen van dit raadsel. De truc was om de speltheorie te verweven in een algoritmische strategie die losjes gebaseerd was op het menselijk brein, genaamd Deep Reinforcement Learning. Het resultaat, DeepNash, wierp menselijke experts omver in een zeer strategisch bordspel genaamd Stratego. Stratego, een notoir moeilijk spel voor AI, vereist meerdere sterke punten van menselijk verstand: langetermijndenken, bluffen en strategieën, allemaal zonder de stukken van je tegenstander op het bord te kennen.
"In tegenstelling tot schaken en Go, is Stratego een spel met onvolmaakte informatie: spelers kunnen de identiteit van de stukken van hun tegenstander niet direct waarnemen," DeepMind schreef in een blogbericht. Met DeepNash zijn "game-playing kunstmatige intelligentie (AI) -systemen naar een nieuwe grens geavanceerd."
Het is niet allemaal leuk en spelen. AI-systemen die gemakkelijk de willekeur van onze wereld kunnen manoeuvreren en hun "gedrag" dienovereenkomstig kunnen aanpassen, zouden op een dag echte problemen kunnen oplossen met beperkte informatie, zoals het optimaliseren van de verkeersstroom om reistijd te verkorten en (hopelijk) woede op de weg te blussen als zelfrijdend auto's worden steeds meer aanwezig.
"Als je een zelfrijdende auto maakt, wil je er niet van uitgaan dat alle andere bestuurders op de weg volkomen rationeel zijn en zich optimaal gaan gedragen", zei Dr. Noam Brown van Meta AI, die niet betrokken was bij het onderzoek.
De triomf van DeepNash komt deze maand op de hielen van een nieuwe AI-opmars een algoritme leerde diplomatie spelen- een spel dat onderhandeling en samenwerking vereist om te winnen. Naarmate AI flexibeler gaat redeneren, algemener wordt en leert navigeren in sociale situaties, kan het ook inzicht geven in de neurale processen en cognitie van onze eigen hersenen.
Maak kennis met Stratego
In termen van complexiteit is Stratego een heel ander beest vergeleken met schaken, Go of poker - alle spellen die AI eerder onder de knie heeft.
Het spel is in wezen capture the flag. Elke kant heeft 40 stukken die ze op elke positie op het bord kunnen plaatsen. Elk stuk heeft een andere naam en numerieke rang, zoals 'maarschalk', 'generaal', 'verkenner' of 'spion'. Hogere stukken kunnen lager geplaatste stukken slaan. Het doel is om de oppositie uit te schakelen en hun vlag te veroveren.
Stratego is vooral een uitdaging voor AI omdat spelers de locatie van de stukken van hun tegenstanders niet kunnen zien, zowel tijdens de eerste installatie als tijdens het spelen. In tegenstelling tot schaken of Go, waarbij elk stuk en elke beweging in beeld is, is Stratego een spel met beperkte informatie. Spelers moeten "alle mogelijke uitkomsten in evenwicht brengen" elke keer dat ze een beslissing nemen, legden de auteurs uit.
Dit niveau van onzekerheid is deels de reden waarom Stratego AI eeuwenlang met stomheid heeft geslagen. Zelfs de meest succesvolle algoritmen voor het spelen van games, zoals AlphaGo en alfanul, vertrouwen op volledige informatie. Stratego heeft daarentegen een vleugje Texas Hold 'em, een pokerspel dat DeepMind eerder veroverde met een algoritme. Maar die strategie haperde voor Stratego, grotendeels vanwege de lengte van het spel, dat in tegenstelling tot poker normaal gesproken honderden zetten omvat.
Het aantal potentiële games is verbluffend. Schaken heeft één startpositie. Stratego heeft er meer dan 1066 mogelijke startposities - veel meer dan alle sterren in het universum. De spelboom van Stratego, de som van alle mogelijke zetten in het spel, bedraagt maar liefst 10535.
"De enorme complexiteit van het aantal mogelijke uitkomsten in Stratego betekent dat algoritmen die goed presteren op spellen met perfecte informatie, en zelfs degenen die werken voor poker, niet werken," zei studie auteur Dr. Julien Perolat bij DeepMind. De uitdaging is "wat ons opwond", zei hij.
A Beautiful Mind
Door de complexiteit van Stratego is de gebruikelijke strategie voor het zoeken naar gameplay-bewegingen uitgesloten. Nagesynchroniseerd met het zoeken naar bomen in Monte Carlo, een "sterke benadering van op AI gebaseerd gamen", stippelt de techniek mogelijke routes uit - zoals takken aan een boom - die kunnen resulteren in de overwinning.
In plaats daarvan kwam de magische aanraking voor DeepNash van de wiskundige John Nash, geportretteerd in de film A Beautiful Mind. Nash, een pionier in de speltheorie, won de Nobelprijs voor zijn werk voor de Nash evenwicht. Simpel gezegd, in elk spel kunnen spelers gebruikmaken van een reeks strategieën die door iedereen worden gevolgd, zodat geen enkele speler iets wint door zijn eigen strategie te veranderen. In Statego leidt dit tot een nulsomspel: elke winst die een speler maakt, resulteert in een verlies voor zijn tegenstander.
Vanwege de complexiteit van Stratego koos DeepNash voor een modelvrije benadering van hun algoritme. Hier probeert de AI niet het gedrag van zijn tegenstander nauwkeurig te modelleren. Net als een baby heeft het een soort onbeschreven blad om te leren. Deze opstelling is vooral handig in de vroege stadia van het spel, "wanneer DeepNash weinig weet over de stukken van zijn tegenstander", waardoor voorspellingen "moeilijk, zo niet onmogelijk" zijn, aldus de auteurs.
Het team gebruikte vervolgens diepgaand leren om DeepNash aan te drijven, met als doel het Nash-evenwicht van het spel te vinden. Het is een match made in heaven: versterkend leren helpt bij het bepalen van de beste volgende zet bij elke stap van het spel, terwijl DeepNash een algemene leerstrategie biedt. Om het systeem te evalueren, ontwierp het team ook een 'tutor' die kennis uit het spel gebruikte om overduidelijke fouten uit te filteren die in de echte wereld waarschijnlijk niet logisch zouden zijn.
Al doende leert men
Als eerste leerstap speelde DeepNash tegen zichzelf in 5.5 miljard games, een populaire benadering in AI-training genaamd self-play.
Wanneer een kant wint, wordt de AI beloond en worden de huidige kunstmatige neurale netwerkparameters versterkt. De andere kant - dezelfde AI - krijgt een boete om de sterkte van het neurale netwerk te dempen. Het is alsof je een toespraak voor jezelf repeteert voor een spiegel. Na verloop van tijd ontdek je fouten en presteer je beter. In het geval van DeepNash drijft het naar een Nash-evenwicht voor de beste gameplay.
Hoe zit het met de werkelijke prestaties?
Het team testte het algoritme tegen andere elite Stratego-bots, waarvan sommige het Computer Stratego World Championship wonnen. DeepNash verpletterde zijn tegenstanders met een winstpercentage van ongeveer 97 procent. Toen DeepNash werd losgelaten tegen Gravon - een online platform voor menselijke spelers - versloeg DeepNash zijn menselijke tegenstanders. Na meer dan twee weken van wedstrijden tegen de spelers van Gravon in april van dit jaar, steeg DeepNash naar de derde plaats in alle gerangschikte wedstrijden sinds 2002.
Het laat zien dat het bootstrapping van menselijke speelgegevens naar AI niet nodig is voor DeepNash om prestaties op menselijk niveau te bereiken - en te verslaan.
De AI vertoonde ook wat intrigerend gedrag bij de eerste installatie en tijdens het spelen. In plaats van zich bijvoorbeeld te vestigen op een bepaalde "geoptimaliseerde" startpositie, verschoven DeepNash de stukken constant om te voorkomen dat zijn tegenstander na verloop van tijd patronen zou ontdekken. Tijdens het spelen stuiterde de AI tussen ogenschijnlijk zinloze bewegingen, zoals het opofferen van hooggeplaatste stukken, om de nog hogere stukken van de tegenstander te lokaliseren bij een tegenaanval.
DeepNash kan ook bluffen. In één spel verplaatste de AI een laaggeplaatst stuk alsof het een hooggeplaatst stuk was, waardoor de menselijke tegenstander werd gelokt om het stuk met zijn hooggeplaatste kolonel te achtervolgen. De AI offerde de pion op, maar lokte op zijn beurt het waardevolle spionagestuk van de tegenstander in een hinderlaag.
Hoewel DeepNash is ontwikkeld voor Stratego, is het generaliseerbaar naar de echte wereld. De kernmethode kan AI mogelijk instrueren om onze onvoorspelbare toekomst beter aan te pakken met behulp van beperkte informatie - van het beheersen van mensenmassa's en verkeer tot het analyseren van marktonrust.
"Door een generaliseerbaar AI-systeem te creëren dat robuust is in het licht van onzekerheid, hopen we de probleemoplossende mogelijkheden van AI verder in onze inherent onvoorspelbare wereld te brengen", aldus het team.
Krediet van het beeld: Derek Bruff / Flickr
