Beviset, som publicerats i fredagens Science, tar formen av en strategi som aldrig förlorar mot någon opponent, oavsett om den spelas av svart eller vitt. Det är inte det första beräkningsbeviset - flera spel har blivit "lösta" på samma sätt tidigare - men damspel är det klart mest komplexa spelet som "lösts" hittills.
Luffarschack är ett enklare spel som är känt för att vara rätt poänglöst, i och med att det alltid slutar oavgjort om det spelas utan misstag från någon av spelarna. I luffarschack är de möjliga dragen så pass få - i och med att planen är liten och antalet "pjäser" begränsade - att det är förhållandevis lätt att bevisa att det är omöjligt att vinna om inte motspelaren klantar sig. Detta faktum har bland annat smugit sig in i populärkulturen i form av en strategi för att "distrahera" en försvarsdator (i filmen WarGames från 1983) - filmens hackerhjälte får helt enkelt datorn att spela luffarschack mot sig själv.
Det betydligt större damspelet, som spelas på ett schackbräde och med fler spelpjäser (12 var för de två spelarna), har också länge misstänkts för att vara ett omöjligt spel att vinna. Matcher mellan riktigt duktiga spelare slutar också oftast oavgjort. Haken är, att om man vill bevisa omöjligheten måste man räkna sig igenom ungefär femhundra miljarders miljarder olika möjliga spelställningar (5*10^20, för er som gillar exponentnotering).
Det är naturligtvis inte en lätt match att göra så mycket beräkningar. Rå datorkraft och datorernas snabba utveckling har spelat en viktig roll i att bevisberäkningen nu är avslutad - som mest kördes 200 datorer samtidigt.
Men en minst lika viktig roll, säger en expert som Science talat med, spelades av forskargruppens uppfinningsrikedom i att hitta sätt att minska antalet beräkningar som krävdes. Själva beräkningen består av flera delar. En del utgörs av en databas med poängsatta slutställningar där det är upp till tio pjäser kvar på brädet - 39271 miljarder slutställningar totalt. Det var här huvuddelen av beräkningskraften spenderades, fram till 2005 när databasen var färdig.
Parallellt och efteråt utvecklade forskarna metoder för att leta rätt på alla de spelställningar som behövde bedömas, och metoder för att utvärdera dem. Utvärderingen - som så att säga är själva kärnan i beviset - kunde ge flera olika sorters omdömen om en spelställning; ett slutgiltigt omdöme (vinst/förlust/oavgjort), ett partiellt omdöme (åtminstone oavgjort/som mest oavgjort) eller en uppskattning av hur bra en ställning var. De svagare omdömena/uppskattningarna användes för att prioritera vilka spelställningar som skulle undersökas närmare.
Det kan tyckas irrelevant att räkna på sällskapsspel, jämfört med att till exempel "lösa cancerns gåta" eller andra föreslagna (populär)vetenskapliga varianter av den heliga Graal. Men spel av den här typen är (förhållandevis) enkla och klara testfall för metoder att lösa helt andra problem; till exempel inom bioinformatik. Lösningen som presenteras här är ett stort steg framåt för metoder som kräver mycket sökande och stora databaser och utnyttjar parallelldatorer - en beskrivning som passar in på många olika "moderna" vetenskapliga problem .
Så vad är nästa spel i kö för att lösas? Othello, gissar forskarna. Schack förblir för krångligt än så länge.
UPPDATERAT 18/9 kl 09:09: En kollega påpekade att det finns två bland dataloger omdiskuterade punkter i beviset; den första är vad som händer om en av spelarna gör ett icke-optimalt drag i början och sedan spelar optimalt - skulle det då gå att lura en datormotståndare (som bara har listor över alla optimala drag) och vinna? Den andra punkten är hur exakt man bestämt att en viss spelposition är "uppenbart" vinnande/förlorande.
Så som jag uppfattat Science-artikeln leder icke-optimala drag till att man trillar utanför kedjan av drag som leder till vinst/oavgjort på kortast tid (dvs minst antal drag), vilket skulle kunna lösa det första problemet (kanske beroende på hur förvirrad motståndaren blir). På den andra punkten tror jag (utifrån artikeln) att en vinnande position är en som senare leder till vinst för den spelaren förutsatt att han/hon/den spelar optimalt - dvs, att slutspelsdatabasen används för att bedöma tidigare ställningar. Men jag kan ha fel, och jag hinner inte läsa om artikeln och kontrollera.
Länkar
artikeln (Science, pren krävs)
"News and Views" - kommentar i Science.
Engelska Wikipedia om luffarschack och damspel
Svenska Wikipedia om damspel
Andra bloggar om: vetenskap, forskning, beräkningar, matematik, damspel
*Min översättning (beräkningsforskare, alltså) av "computer scientist", eftersom jag tyckte att varken "datorforskare" eller "datavetare" är riktigt rättvisande i det här fallet. En datalogi-kollega föreslog att "datalog(i)" är bättre och mer etablerat, så jag ändrar.
Inga kommentarer:
Skicka en kommentar