AI hatar osäkerhet. Men för att navigera i vår oförutsägbara värld måste den lära sig att göra val med ofullkomlig information – som vi gör varje dag.
DeepMind bara tog ett stick på att lösa denna gåta. Tricket var att väva in spelteori till en algoritmisk strategi löst baserad på den mänskliga hjärnan som kallas djup förstärkningsinlärning. Resultatet, DeepNash, störtade mänskliga experter i ett mycket strategiskt brädspel som heter Stratego. Ett notoriskt svårt spel för AI, Stratego kräver flera styrkor av mänsklig intelligens: långsiktigt tänkande, bluffande och strategiserande, allt utan att känna till din motståndares pjäser på brädet.
"Till skillnad från schack och Go är Stratego ett spel med ofullkomlig information: spelare kan inte direkt observera identiteten på motståndarens pjäser," DeepMind skrev i ett blogginlägg. Med DeepNash har "spelande artificiell intelligens (AI)-system avancerat till en ny gräns."
Det är inte bara skoj och spel. AI-system som enkelt kan manövrera slumpmässigheten i vår värld och anpassa sitt "beteende" därefter skulle en dag kunna hantera verkliga problem med begränsad information, som att optimera trafikflödet för att minska restiden och (förhoppningsvis) släcka vägraseri som självkörande bilar blir allt mer närvarande.
"Om du gör en självkörande bil vill du inte anta att alla andra förare på vägen är helt rationella och kommer att bete sig optimalt," sade Dr. Noam Brown på Meta AI, som inte var involverad i forskningen.
DeepNashs triumf kommer varmt i hälarna på ytterligare ett AI-framsteg denna månad, där en algoritm lärde sig att spela diplomati— ett spel som kräver förhandling och samarbete för att vinna. I takt med att AI får mer flexibelt resonemang, blir mer generaliserat och lär sig att navigera i sociala situationer, kan det också ge insikter i vår egen hjärnas neurala processer och kognition.
Möt Stratego
När det gäller komplexitet är Stratego en helt annan best jämfört med schack, Go eller poker – alla spel som AI tidigare har bemästrat.
Spelet är i huvudsak fånga flaggan. Varje sida har 40 bitar som de kan placera var som helst på brädet. Varje pjäs har olika namn och numerisk rang, till exempel "marskalk", "general", "scout" eller "spion". Högre rankade pjäser kan fånga lägre. Målet är att eliminera oppositionen och fånga deras flagga.
Stratego är särskilt utmanande för AI eftersom spelare inte kan se platsen för sina motståndares pjäser, både under den första installationen och under hela spelet. Till skillnad från schack eller Go, där varje pjäs och rörelse syns, är Stratego ett spel med begränsad information. Spelare måste "balansera alla möjliga resultat" varje gång de fattar ett beslut, förklarade författarna.
Denna nivå av osäkerhet är delvis anledningen till att Stratego har stött på AI i evigheter. Även de mest framgångsrika spelalgoritmerna, som AlphaGo och Alpha Zero, lita på fullständig information. Stratego har däremot en touch av Texas holdem, ett pokerspel DeepMind som tidigare erövrats med en algoritm. Men den strategin vacklade för Stratego, till stor del på grund av spelets längd, som till skillnad från poker normalt omfattar hundratals drag.
Antalet potentiella spel är häpnadsväckande. Schack har en utgångsposition. Stratego har över 1066 möjliga startpositioner – långt fler än alla stjärnor i universum. Strategos spelträd, summan av alla potentiella drag i spelet, uppgår till svindlande 10535.
"Den stora komplexiteten i antalet möjliga utfall i Stratego innebär att algoritmer som fungerar bra på spel med perfekt information, och även de som fungerar för poker, fungerar inte." sade studieförfattaren Dr Julien Perolat vid DeepMind. Utmaningen är "det som gjorde oss upphetsade", sa han.
A Beautiful Mind
Strategos komplexitet gör att den vanliga strategin för att söka spelrörelser inte är aktuell. Tekniken, kallad Monte Carlo-trädsökningen, en "trogen metod för AI-baserat spel", ritar ut potentiella rutter - som grenar på ett träd - som kan resultera i seger.
Istället kom den magiska touchen för DeepNash från matematikern John Nash, porträtterad i filmen A Beautiful Mind. En pionjär inom spelteori, Nash vann Nobelpriset för sitt arbete för Nash jämvikt. Enkelt uttryckt, i varje spel kan spelare utnyttja en uppsättning strategier som följs av alla, så att ingen enskild spelare vinner något genom att ändra sin egen strategi. I Statego leder detta till ett nollsummespel: varje vinst en spelare gör resulterar i en förlust för motståndaren.
På grund av Strategos komplexitet tog DeepNash en modellfri strategi för sin algoritm. Här försöker AI inte att exakt modellera motståndarens beteende. Som en bebis har den en sorts blank tabell att lära sig. Denna uppställning är särskilt användbar i tidiga skeden av spelet, "när DeepNash vet lite om sina motståndares pjäser", vilket gör förutsägelser "svåra, för att inte säga omöjliga", sa författarna.
Teamet använde sedan djup förstärkningsinlärning för att driva DeepNash, med målet att hitta spelets Nash-jämvikt. Det är en match made in heaven: förstärkningsinlärning hjälper till att bestämma det bästa nästa draget i varje steg i spelet, medan DeepNash tillhandahåller en övergripande inlärningsstrategi. För att utvärdera systemet konstruerade teamet också en "handledare" som använde kunskap från spelet för att filtrera bort uppenbara misstag som sannolikt inte skulle vara vettiga i verkligheten.
Övning ger färdighet
Som ett första inlärningssteg spelade DeepNash mot sig själv i 5.5 miljarder spel, ett populärt tillvägagångssätt inom AI-träning som kallas självspel.
När den ena sidan vinner belönas AI:n och dess nuvarande artificiella neurala nätverksparametrar stärks. Den andra sidan – samma AI – får en straffavgift för att dämpa dess neurala nätverksstyrka. Det är som att repetera ett tal för sig själv framför en spegel. Med tiden räknar du ut misstag och presterar bättre. I DeepNashs fall går det mot en Nash-jämvikt för bästa spel.
Hur är det med den faktiska prestandan?
Teamet testade algoritmen mot andra elit Stratego-bots, av vilka några vann Computer Stratego World Championship. DeepNash slog sina motståndare med en vinstgrad på ungefär 97 procent. När DeepNash släpptes lös mot Gravon – en onlineplattform för mänskliga spelare – slog DeepNash sina mänskliga motståndare. Efter över två veckors matcher mot Gravons spelare i april i år steg DeepNash till tredje plats i alla rankade matcher sedan 2002.
Det visar att bootstrapping av mänsklig speldata till AI inte behövs för att DeepNash ska nå prestanda på mänsklig nivå – och slå den.
AI:n uppvisade också ett spännande beteende med den initiala installationen och under spelandet. Till exempel, snarare än att sätta sig på en viss "optimerad" startposition, flyttade DeepNash hela tiden runt pjäserna för att förhindra att motståndaren upptäcker mönster över tiden. Under spelet studsade AI mellan till synes meningslösa drag – som att offra högt rankade pjäser – för att lokalisera motståndarens ännu högre rankade pjäser vid motattack.
DeepNash kan också bluffa. I ett spel flyttade AI:n en lågt rankad pjäs som om den vore en högt rankad, och lockade den mänskliga motståndaren att jaga efter pjäsen med sin högt rankade överste. AI:n offrade bonden, men lockade i sin tur motståndarens värdefulla spionpjäs i ett bakhåll.
Även om DeepNash utvecklades för Stratego, är det generaliserbart till den verkliga världen. Kärnmetoden kan potentiellt instruera AI att bättre tackla vår oförutsägbara framtid med hjälp av begränsad information – från publik- och trafikkontroll till att analysera marknadsturbulens.
"Genom att skapa ett generaliserbart AI-system som är robust inför osäkerhet, hoppas vi kunna föra AIs problemlösningsförmåga längre in i vår i sig oförutsägbara värld", sa teamet.
Image Credit: Derek Bruff / Flickr
