AI hater usikkerhet. Men for å navigere i vår uforutsigbare verden, må den lære å ta valg med ufullkommen informasjon – slik vi gjør hver eneste dag.
DeepMind bare tok et stikk på å løse denne gåten. Trikset var å flette inn spillteori til en algoritmisk strategi løst basert på den menneskelige hjernen kalt dyp forsterkningslæring. Resultatet, DeepNash, veltet menneskelige eksperter i et svært strategisk brettspill kalt Stratego. Et notorisk vanskelig spill for AI, Stratego krever flere styrker av menneskelig vidd: langsiktig tenkning, bløffing og strategisering, alt uten å kjenne motstanderens brikker på brettet.
"I motsetning til sjakk og Go, er Stratego et spill med ufullkommen informasjon: spillere kan ikke direkte observere identiteten til motstanderens brikker," DeepMind skrev i et blogginnlegg. Med DeepNash har "spillende kunstig intelligens (AI)-systemer avansert til en ny grense."
Det er ikke bare moro og lek. AI-systemer som enkelt kan manøvrere tilfeldighetene i vår verden og justere "atferden" deres deretter, kan en dag håndtere problemer i den virkelige verden med begrenset informasjon, for eksempel å optimalisere trafikkflyten for å redusere reisetiden og (forhåpentligvis) slukke road rage som selvkjørende biler blir stadig mer tilstede.
"Hvis du lager en selvkjørende bil, vil du ikke anta at alle de andre sjåførene på veien er helt rasjonelle og kommer til å oppføre seg optimalt," sa Dr. Noam Brown ved Meta AI, som ikke var involvert i forskningen.
DeepNash sin triumf kommer varmt i hælene på nok et AI-fremskritt denne måneden, hvor en algoritme lærte å spille Diplomacy— et spill som krever forhandlinger og samarbeid for å vinne. Ettersom AI får mer fleksibel resonnement, blir mer generalisert og lærer å navigere i sosiale situasjoner, kan det også gi innsikt i vår egen hjernes nevrale prosesser og kognisjon.
Møt Stratego
Når det gjelder kompleksitet, er Stratego et helt annet beist sammenlignet med sjakk, Go eller poker – alle spill som AI tidligere har mestret.
Spillet er egentlig fange flagget. Hver side har 40 brikker de kan plassere hvor som helst på brettet. Hver brikke har et annet navn og numerisk rangering, for eksempel «marskalk», «general», «speider» eller «spion». Brikker med høyere rangering kan fange lavere. Målet er å eliminere opposisjonen og fange flagget deres.
Stratego er spesielt utfordrende for AI fordi spillere ikke kan se plasseringen av motstandernes brikker, både under innledende oppsett og gjennom spillet. I motsetning til sjakk eller Go, der hver brikke og bevegelse er synlig, er Stratego et spill med begrenset informasjon. Spillere må "balansere alle mulige utfall" hver gang de tar en beslutning, forklarte forfatterne.
Dette nivået av usikkerhet er delvis grunnen til at Stratego har stoppet AI i evigheter. Selv de mest vellykkede spillalgoritmene, som AlphaGo og alphazero, stole på fullstendig informasjon. Stratego har derimot et snev av Texas Hold 'em, et pokerspill DeepMind tidligere erobret med en algoritme. Men den strategien vaklet for Stratego, hovedsakelig på grunn av lengden på spillet, som i motsetning til poker vanligvis omfatter hundrevis av trekk.
Antallet potensielle spill er imponerende. Sjakk har én startposisjon. Stratego har over 1066 mulige startposisjoner - langt flere enn alle stjernene i universet. Strategos spilltre, summen av alle potensielle trekk i spillet, utgjør svimlende 10535.
"Den store kompleksiteten i antall mulige utfall i Stratego betyr at algoritmer som gir gode resultater i spill med perfekt informasjon, og til og med de som fungerer for poker, ikke fungerer," sa studieforfatter Dr. Julien Perolat ved DeepMind. Utfordringen er "hva begeistret oss," sa han.
A Beautiful Mind
Strategos kompleksitet betyr at den vanlige strategien for å søke etter spillbevegelser er uaktuelt. Kalt Monte Carlo-tresøket, en "trofast tilnærming til AI-basert spill", plotter teknikken ut potensielle ruter – som grener på et tre – som kan resultere i seier.
I stedet kom det magiske preget for DeepNash fra matematikeren John Nash, portrettert i filmen A Beautiful Mind. En pioner innen spillteori, Nash vant Nobelprisen for sitt arbeid for Nash-likevekt. Enkelt sagt, i hvert spill kan spillere benytte seg av et sett med strategier fulgt av alle, slik at ingen enkeltspiller vinner noe ved å endre sin egen strategi. I Statego fører dette til et nullsumspill: enhver gevinst en spiller oppnår resulterer i tap for motstanderen.
På grunn av Strategos kompleksitet, tok DeepNash en modellfri tilnærming til algoritmen deres. Her prøver AI ikke å modellere motstanderens oppførsel nøyaktig. Som en baby har den et blankt ark å lære. Dette oppsettet er spesielt nyttig i tidlige stadier av spillingen, «når DeepNash vet lite om motstanderens brikker», noe som gjør spådommer «vanskelige, om ikke umulige», sa forfatterne.
Teamet brukte deretter dyp forsterkende læring for å drive DeepNash, med målet om å finne spillets Nash-likevekt. Det er en match made in heaven: forsterkende læring hjelper til med å avgjøre det beste neste trekk ved hvert trinn i spillet, mens DeepNash gir en overordnet læringsstrategi. For å evaluere systemet konstruerte teamet også en "veileder" som brukte kunnskap fra spillet for å filtrere ut åpenbare feil som sannsynligvis ikke ville gi mening i den virkelige verden.
Øvelse gjør mester
Som et første læringstrinn spilte DeepNash mot seg selv i 5.5 milliarder spill, en populær tilnærming innen AI-trening kalt selvspill.
Når en side vinner, blir AI belønnet, og dets nåværende kunstige nevrale nettverksparametere styrkes. Den andre siden – den samme AI – får en straff for å dempe nevrale nettverksstyrke. Det er som å øve på en tale for deg selv foran et speil. Over tid finner du ut feil og presterer bedre. I DeepNash sitt tilfelle driver den mot en Nash-likevekt for best spilling.
Hva med faktisk ytelse?
Teamet testet algoritmen mot andre elite Stratego-roboter, hvorav noen vant Computer Stratego World Championship. DeepNash knuste motstanderne med en seierrate på omtrent 97 prosent. Da DeepNash ble sluppet løs mot Gravon – en online plattform for menneskelige spillere – slo DeepNash sine menneskelige motstandere. Etter over to uker med kamper mot Gravons spillere i april i år, steg DeepNash til tredjeplass i alle rangerte kamper siden 2002.
Det viser at oppstart av menneskelige lekedata til AI ikke er nødvendig for at DeepNash skal oppnå ytelse på menneskelig nivå – og slå den.
AI viste også noe spennende oppførsel med det første oppsettet og under spillingen. For eksempel, i stedet for å sette seg på en bestemt "optimalisert" startposisjon, flyttet DeepNash hele tiden brikkene rundt for å hindre motstanderen i å oppdage mønstre over tid. Under spilling spratt AI mellom tilsynelatende meningsløse trekk – for eksempel å ofre høyrangerte brikker – for å finne motstanderens brikker med enda høyere rangering ved motangrep.
DeepNash kan også bløffe. I ett spill flyttet AI en lavt rangert brikke som om det var en høyt rangert, og lokket den menneskelige motstanderen til å jage etter brikken med sin høyt rangerte oberst. AI ofret bonden, men lokket på sin side motstanderens verdifulle spionbrikke inn i et bakhold.
Selv om DeepNash ble utviklet for Stratego, er det generaliserbart til den virkelige verden. Kjernemetoden kan potensielt instruere AI til å takle vår uforutsigbare fremtid bedre ved å bruke begrenset informasjon – fra publikum og trafikkkontroll til å analysere markedsuro.
"Ved å lage et generaliserbart AI-system som er robust i møte med usikkerhet, håper vi å bringe problemløsningsmulighetene til AI videre inn i vår iboende uforutsigbare verden," sa teamet.
Bilde Credit: Derek Bruff / Flickr
