”Othello är nu löst.” Med den sammanfattningen bekräftade en forskare vid ett japanskt datorföretag ännu en milstolpe i superdatorernas utveckling.
Othello, ett 140 år gammalt spel med rötter i Shakespeares drama med samma namn som skildrar konflikten mellan Moor av Venedig och Desdemona, verkar inte komplicerat vid första anblicken. Det spelas på ett bräde med svarta och vita diskar som är strategiskt placerade i rutor längs åtta rader och åtta kolumner.
Utmaningen, enligt bioinformatikern Hiroki Takizawa, är att utforma en spelplan ”där inget misstag görs av någon av spelarna”.
”[Det] har länge varit en stor utmaning inom datavetenskap”, säger han. ”I den här artikeln meddelar vi att vi har löst Othello på ett svagt sätt.”
Tillämpat på spelteori avser en ”svag” lösning en algoritm som säkerställer antingen en vinst mot alla möjliga drag av en motståndare från början av ett spel, eller oavgjort. En ”stark” lösning är en algoritm som ger perfekta drag från alla positioner på brädet, även efter misstag av någon av de två spelarna.
Uppgiften att ”lösa” Othello är en enorm uppgift. Det finns 10 octillioner möjliga spelpositioner, vilket innebär att om du råkade ha en laptop vid universums födelse och började testa ett drag per sekund, skulle du fortfarande vara långt ifrån färdig idag.
En sådan uppgift är nästan en barnlek för dagens massivt parallella datorsystem.
Takizawa använde sitt företags MN-J superdatorkluster för att ta sig an uppgiften. Även om kraftfullare datorer har byggts under de senaste åren innehåller MN-J-systemet en energieffektiv komponent som, med 21,1 gigaflops per watt effekt, ansågs vara världens mest kraftfulla år 2020. Den är nu nr 11.
Takizawa vidareutvecklade Edax, ett datorprogram som först användes för att analysera Othello-strategin för flera år sedan.
”Vårt genombrott kom genom att förbättra sökeffektiviteten och modifiera den senaste Othello-programvaran”, säger Takizawa.
Othello-resultatet är en monumental prestation för mänskligheten”, sade Takizawa, ”som visar de anmärkningsvärda framstegen inom datavetenskap och AI-teknik. Att lösa Othello har varit en av de stora utmaningarna för AI.”
Datorer har räknat siffror och besegrat världsmästare i många spel i flera år.
IBM:s DeepBlue vann över schackvärldsmästaren Gary Kasparov 1997, vilket var första gången en dator slog en mänsklig schackspelare i ett formellt parti.
På samma sätt besegrade Googles AlphaGo 2016 Go-världsmästaren Lee Sedol, som anses vara en av spelets starkaste spelare genom historien. Go anses vara mer utmanande än schack. Brute force-beräkningar används framgångsrikt i maskinschack, men den metoden är inte lika produktiv i Go, där datorstrategin är mer beroende av förstärkningsinlärning.
Och datorer har programmerats att spela Connect-4 – ett spel med 4,5 biljoner rutnätsscenarier – perfekt; de förlorar aldrig.
Takizawa medger att vissa kan ifrågasätta legitimiteten hos beräkningsbevis. Minnesfel och CPU-strul kan inte uteslutas, säger han. Han noterade dock att minnet för felkontroll och felkorrigering användes under hela processen. Han betonade att även i händelse av ett datorfel är risken för att hans slutsats omkullkastas ”extremt låg”.
Hans rapport, ”Othello is solved”, laddades upp till preprint-servern arXiv.
Ytterligare information: Hiroki Takizawa, Othello is Solved, arXiv (2023). DOI: 10.48550/arxiv.2310.19387
