AI hader usikkerhed. Men for at navigere i vores uforudsigelige verden, skal den lære at træffe valg med ufuldkommen information – som vi gør hver eneste dag.
DeepMind bare tog et stik ved at løse denne gåde. Tricket var at flette spilteori ind i en algoritmisk strategi løst baseret på den menneskelige hjerne kaldet deep reinforcement learning. Resultatet, DeepNash, væltede menneskelige eksperter i et yderst strategisk brætspil kaldet Stratego. Et notorisk vanskeligt spil for AI, Stratego kræver flere styrker af menneskelig vid: langsigtet tænkning, bluffing og strategisering, alt sammen uden at kende din modstanders brikker på brættet.
"I modsætning til skak og Go er Stratego et spil med uperfekt information: Spillere kan ikke direkte observere identiteten af deres modstanders brikker," DeepMind skrev i et blogindlæg. Med DeepNash er "spillende kunstig intelligens (AI)-systemer avanceret til en ny grænse."
Det er ikke alt sammen sjov og leg. AI-systemer, der nemt kan manøvrere tilfældigheden i vores verden og justere deres "adfærd" i overensstemmelse hermed, kunne en dag håndtere problemer i den virkelige verden med begrænset information, såsom optimering af trafikflowet for at reducere rejsetiden og (forhåbentlig) slukke road rage som selvkørende biler bliver stadig mere til stede.
"Hvis du laver en selvkørende bil, vil du ikke gå ud fra, at alle de andre bilister på vejen er helt rationelle og kommer til at opføre sig optimalt," sagde Dr. Noam Brown hos Meta AI, som ikke var involveret i forskningen.
DeepNashs triumf kommer varmt i hælene på endnu en AI-fremgang denne måned, hvor en algoritme lærte at spille Diplomacy-et spil, der kræver forhandling og samarbejde for at vinde. Efterhånden som AI får mere fleksibel ræsonnement, bliver mere generaliseret og lærer at navigere i sociale situationer, kan det også give indsigt i vores egen hjernes neurale processer og kognition.
Mød Stratego
Med hensyn til kompleksitet er Stratego et helt andet udyr sammenlignet med skak, Go eller poker – alle spil, som AI tidligere har mestret.
Spillet er i det væsentlige capture the flag. Hver side har 40 brikker, de kan placere på enhver position på brættet. Hver brik har et andet navn og numerisk rang, såsom "marskal", "general", "spejder" eller "spion". Højere rangerede brikker kan fange lavere. Målet er at eliminere oppositionen og fange deres flag.
Stratego er især udfordrende for AI, fordi spillere ikke kan se placeringen af deres modstanderes brikker, både under den indledende opsætning og under hele spillet. I modsætning til skak eller Go, hvor hver brik og bevægelse er i udsigt, er Stratego et spil med begrænset information. Spillere skal "afbalancere alle mulige resultater", hver gang de træffer en beslutning, forklarede forfatterne.
Dette niveau af usikkerhed er til dels grunden til, at Stratego har slået kunstig intelligens i stykker i evigheder. Selv de mest succesrige spilalgoritmer, såsom AlphaGo og Alpha Zero, stole på fuldstændige oplysninger. Stratego har derimod et strejf af Texas Hold 'em, et pokerspil DeepMind tidligere erobret med en algoritme. Men den strategi vaklede for Stratego, hovedsageligt på grund af spillets længde, som i modsætning til poker normalt omfatter hundredvis af træk.
Antallet af potentielle spil er overvældende. Skak har én startposition. Stratego har over 1066 mulige startpositioner - langt flere end alle stjerner i universet. Strategos spiltræ, summen af alle potentielle træk i spillet, er i alt svimlende 10535.
"Den store kompleksitet af antallet af mulige udfald i Stratego betyder algoritmer, der fungerer godt på spil med perfekt information, og selv dem, der fungerer til poker, virker ikke." sagde studieforfatter Dr. Julien Perolat ved DeepMind. Udfordringen er "hvad begejstrede os," sagde han.
A Beautiful Mind
Strategos kompleksitet betyder, at den sædvanlige strategi for at søge efter gameplay-bevægelser er udelukket. Kaldet Monte Carlo-træsøgningen, en "trofast tilgang til AI-baseret spil", tegner teknikken potentielle ruter - som grene på et træ - der kan resultere i sejr.
I stedet kom det magiske touch til DeepNash fra matematikeren John Nash, portrætteret i filmen A Beautiful Mind. En pioner inden for spilteori vandt Nash Nobelprisen for sit arbejde for Nash-ligevægt. Kort sagt, i hvert spil kan spillere udnytte et sæt strategier fulgt af alle, så ingen enkelt spiller vinder noget ved at ændre deres egen strategi. I Statego medfører dette et nulsumsspil: enhver gevinst, som en spiller opnår, resulterer i et tab for deres modstander.
På grund af Strategos kompleksitet tog DeepNash en modelfri tilgang til deres algoritme. Her forsøger AI ikke præcist at modellere sin modstanders adfærd. Som en baby har den en slags blank tavle at lære. Denne opsætning er især nyttig i tidlige stadier af gameplay, "når DeepNash ved lidt om modstanderens brikker," hvilket gør forudsigelser "svære, hvis ikke umulige," sagde forfatterne.
Holdet brugte derefter dyb forstærkningslæring til at drive DeepNash med det mål at finde spillets Nash-ligevægt. Det er en match made in heaven: forstærkende læring hjælper med at beslutte det bedste næste træk ved hvert trin af spillet, mens DeepNash giver en overordnet læringsstrategi. For at evaluere systemet konstruerede teamet også en "vejleder", der brugte viden fra spillet til at bortfiltrere åbenlyse fejl, som sandsynligvis ikke ville give mening i den virkelige verden.
Øvelse gør mester
Som et første læringstrin spillede DeepNash mod sig selv i 5.5 milliarder spil, en populær tilgang til AI-træning kaldet selvspil.
Når den ene side vinder, bliver AI belønnet, og dets nuværende kunstige neurale netværksparametre styrkes. Den anden side - den samme AI - modtager en straf for at dæmpe dens neurale netværksstyrke. Det er som at øve en tale for dig selv foran et spejl. Over tid finder du ud af fejl og præsterer bedre. I DeepNashs tilfælde driver det mod en Nash-ligevægt for det bedste gameplay.
Hvad med den faktiske ydeevne?
Holdet testede algoritmen mod andre elite Stratego-bots, hvoraf nogle vandt Computer Stratego World Championship. DeepNash knuste sine modstandere med en sejrsrate på omkring 97 procent. Da DeepNash blev sluppet løs mod Gravon – en online platform for menneskelige spillere – afslørede DeepNash sine menneskelige modstandere. Efter over to ugers kampe mod Gravons spillere i april i år, steg DeepNash til tredjepladsen i alle rangerede kampe siden 2002.
Det viser, at bootstrapping af menneskelige legedata til AI ikke er nødvendig for, at DeepNash kan nå præstationer på menneskeligt niveau – og slå den.
AI'en udviste også noget spændende adfærd med den indledende opsætning og under gameplay. For eksempel, i stedet for at indstille sig på en bestemt "optimeret" startposition, flyttede DeepNash konstant brikkerne rundt for at forhindre modstanderen i at opdage mønstre over tid. Under gameplay hoppede AI'en mellem tilsyneladende meningsløse bevægelser - såsom at ofre højtstående brikker - for at lokalisere modstanderens endnu højere rangerende brikker ved modangreb.
DeepNash kan også bluffe. I et spil flyttede AI'en en lavtstående brik, som om den var en højtrangerende brik, og lokkede den menneskelige modstander til at jagte brikken med sin højtstående oberst. AI ofrede bonden, men lokkede til gengæld modstanderens værdifulde spionbrik i et baghold.
Selvom DeepNash blev udviklet til Stratego, kan det generaliseres til den virkelige verden. Kernemetoden kan potentielt instruere AI til bedre at tackle vores uforudsigelige fremtid ved hjælp af begrænset information – fra crowd- og trafikkontrol til analyse af markedsuro.
"Ved at skabe et generaliserbart AI-system, der er robust over for usikkerhed, håber vi at bringe AIs problemløsningsevner længere ind i vores iboende uforudsigelige verden," sagde teamet.
Billede Credit: Derek Bruff / Flickr
