Japansk forskare erövrar brädspelet Othello

(Vänster) Den ursprungliga positionen på brädet för 8 × 8 Othello. (Höger) Ett diagram över en optimal spelföring enligt vår studie. Spelprotokollet är "F5D6C3D3 C4F4F6F3 E6E7D7C5 B6D8C6C7 D2B5A5A6 A7G5E3B4 C8G6G4C2 E8D1F7E2 G3H4F1E1 F2G1B1F8 G8B3H3B2 H5B7A3A4 A1A2C1H2 H1G2B8A8 G7H8H7H6". Siffrorna i stenarna anger dragordningen och färgerna på stenarna anger slutresultatet. Vår studie bekräftar att om en avvikelse från detta rekord inträffar vid något tillfälle, är vår programvara, som spelar som motståndaren, garanterad oavgjort eller vinst. Kredit:
(Vänster) Den ursprungliga positionen på brädet för 8 × 8 Othello. (Höger) Ett diagram över en optimal spelföring enligt vår studie. Spelprotokollet är "F5D6C3D3 C4F4F6F3 E6E7D7C5 B6D8C6C7 D2B5A5A6 A7G5E3B4 C8G6G4C2 E8D1F7E2 G3H4F1E1 F2G1B1F8 G8B3H3B2 H5B7A3A4 A1A2C1H2 H1G2B8A8 G7H8H7H6". Siffrorna i stenarna anger dragordningen och färgerna på stenarna anger slutresultatet. Vår studie bekräftar att om en avvikelse från detta rekord inträffar vid något tillfälle, är vår programvara, som spelar som motståndaren, garanterad oavgjort eller vinst. Kredit: arXiv

”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

Bli först med att kommentera

Lämna ett svar

Din e-postadress kommer inte att publiceras.