Verdens beste sjakkspiller er et dataprogram

Denne saken har blitt oppdatert i forkant av verdensmesterskapet i år.

Hva? Er ikke verdens beste sjakkspiller Magnus Carlsen? Faktisk ikke om vi tillater oss å utvide begrepet «sjakkspiller»  til også å inkludere dataprogrammer. Det er like før verdensmesteren skal forsvare sin tittel i New York mot det jevnaldrede talentet Sergey Karjakin, men ingen av disse hadde hatt sjanse alene mot verdens beste sjakkprogrammer.

En god del sjakkprogrammer ligger idag godt foran de beste menneskelige spillerne i verden. Ett av de ledende heter Stockfish og er opprinnelig skrevet av nordmannen Tord Romstad. Stockfish er åpen kildekode og en god sjakkspiller. Meget god. Faktisk så god at mot Magnus Carlsen ville programmet statistisk sett vunnet 96 av 100 partier om en kun hadde tatt hensyn til ratingen (spillestyrken). Det sier ikke så lite når vi snakker om mannen fra Lommedalen som mange regner for å være tidenes aller beste sjakkspiller, og som guttunge måtte leve med å bli kalt «Mozart of Chess».

Hva er det som gjør det mulig at en liten sjakkmotor, kjørende på en bærbar PC til noen tusenlapper, kan slå de beste spillerene verden har klart å produsere? Det er noe av det denne artikkelen vil sette litt lys på.

En sjakkmotor er ikke som andre motorer

Som du sikkert allerede har skjønt, en sjakkmotor går ikke på diesel og styrken kan ikke måles i hestekrefter. Betegnelsen brukes for å beskrive et dataprogram som kun er laget for å gjøre sjakktrekk. Omtrent like lenge som det har eksistert datamaskiner, har det eksistert sjakkmotorer. Allerede på 50-tallet ble det laget programmer som klarte å spille hele partier med sjakk, og det gikk ikke lang tid før disse utviklet seg til å slå mennesker. Derimot skulle det gå adskillig lengre før de kunne måle seg mot verdenseliten.

Les også om fremskritt innenfor kunstig intelligens: Kvanteteknologi kan gi oss virkelig smarte roboter »

Teknologien gjør som teknologien bør, den sprenger grenser og driver verden videre. Etter hvert som megahertz ble til gigahertz, kom det i 1988 endelig et gjennombrudd. IBMs sjakkmotor «Deep Thought» slo for første gang en stormester i sjakk i en tøff turnering og offeret var ingen ringere enn det danske sjakkgeniet Bent Larsen. Ikke nok med det, den fikk også delt førsteplass foran blant andre tidligere verdensmester Mikhail Tal, en begavet russisk spiller som har satt sine spor i sjakkens historiebøker.

Inspirert av denne bragden fortsetter IBM utviklingen av dette monsteret i nesten ti år, døper det om til «Deep Blue» og sender sjokkbølger gjennom verden i 1997 når selveste verdensmester Garry Kasparov går ned for telling. Datidens enerådende sjakkonge var helt målløs, foruten om de vanlige unnskyldningene, men tapet var et faktum og fremstår den dag i dag som en milepæl i sjakkmotorens historie. I årene som fulgte ble maskinvaren stadig bedre, utviklerne smartere og folk sluttet endelig å le av de som programmerte sine binære venner til å spille sjakk.

Av med topplokket

Nok historie. Det er på tide å jekke opp kjerra, åpne panseret og plukke fra hverandre motoren. Hvordan fungerer disse programmene? For å finne svaret på det, må vi brette opp ermene og gå litt i dybden.

Sjakk er det man kaller et «endelig spill». Det vil si at det finnes en øvre grense for hvor mange mulige trekk en totalt kan gjøre, eller sagt på en annen måte, hvor mange veier man kan gå for å komme til mål. Problemet er at den grensen er et tall som er så høyt at ingen enda har klart å komme med noe annet enn estimater.

Wikipedia kan fortelle oss at antall mulige forskjellige posisjoner estimeres til å være 10⁴⁷ og antall mulige trekk på hele 10¹²³. Vi snakker Store tall her. Sammenligner man dem med antall atomer i det kjente univers, altså et sted rundt 10⁸⁰, så er det lett å skjønne at det å «løse sjakk» matematisk byr på en aldri så liten utfordring. Heldigvis finnes det mange lure triks og smarte algoritmer en programmerer kan bruke for å temme disse guddommelige tallene.

Selv med verktøykassen full av magi er det ikke til å stikke under en stol at det å bygge en bra sjakkmotor er en kompleks affære. Full forståelse for hvordan alt henger sammen krever mye lesing, pågangsmot og ikke minst tid. Alikevel er det ikke så altfor vanskelig å skjønne grunnprinsippene bak det hele. En sjakkmotor må kunne løse mange små og store oppgaver, men grovt sett er det tre som skiller seg ut:

• Generere lovlige trekk
• Søke gjennom trekk
• Evaluere forskjellige stillinger

Vi mennesker tenker ikke særlig over disse oppgavene når vi spiller. De glir litt inn i hverandre og det går ofte på automatikk grunnet lærdom vi plukket opp som barn da far tok frem brettet for første gang. En datamaskin derimot må ha klare definerte skiller mellom de ulike stegene i prosessen, slik at implementasjonen av koden blir rask, ryddig og effektiv. Gjennom historien har flere metoder og strategier blitt tatt i bruk, men vi skal fokusere på de beste og mest brukte.

Kom igjen, gjør et trekk da

Det å kunne generere gyldige trekk er grunnmuren i programmet og ofte der man starter. Et gyldig trekk er rett og slett et trekk som ikke strider imot reglene, for eksempel at tårn ikke kan gå på skrå og bønder bakover. Lett for oss mennesker å forstå, men en datamaskin må ha dette inn med skje. Denne oppgaven er også en av de som «koster mest» prosessorkraft, derfor er det viktig å være både smart og nøye slik at koden blir mest mulig effektiv.

Det første en sjakkmotor trenger er en måte å representere spillets regler, brettets tilstander og brikkenes posisjoner på. Til det brukes noe som på fagspråket kalles «bitboard». I en rekke med 64 binære tall (64-bit unsigned integer) representerer hver binære bit en enkelt rute på brettet.

Med en slik tilnærming kan den sorte dronningens posisjon representeres med å sette verdien til 1 på den biten som samsvarer med feltet hun står på. Denne metoden er meget effektiv og brukes også til å lagre en del andre ting, som spillets regler, alle okkuperte felter, alle hvite brikkers posisjon, felter en brikke kan flytte til og så videre.

Trekkgeneratoren bruker «bitboard»-ene sammen med litt smart teknikk til å foreslå gyldige trekk. Binære tall har nemlig den fordelen at man kan utføre bitvis operasjoner på dem (AND, OR, NOT og flere). Operasjonene er en del av prosessorens instruksjonssett og kan derfor stort sett gjennomføres i løpet av èn klokkesyklus.

Dagens 64-bit prosessorer er gaven fra teknologien som virkelig får denne metoden til å skinne. Det er nesten så man skulle tro at forskerne hadde sjakkbrettets 64 ruter i bakhodet da de utviklet dem. Selvsagt hadde de ikke det, men denne lille «tilfeldigheten» gjør at disse bitvis operasjonene koster ekstremt lite å gjennomføre. I praksis bruker en prosessor bare 3-4 sykluser på å finne ut om sort dronning har satt hvit konge i sjakk, og det går lynkjapt når vi snakker om klokkefrekvenser på flere gigahertz.

Nå som sjakkmotoren kan utføre lovlige trekk er det faktisk mulig å spille et helt parti sjakk! Med litt ekstra flaks klarer den kanskje til og med å slå en 3-åring..

Fram med tryllestaven

Ingen havner på forsiden av nyhetene ved å lage et program som er verdensmester i å tape. Hvis det skal ha noen sjans for å komme seg til mål med flagget reist må det litt intelligens til. Her er det de to siste hovedpunktene kommer inn. For å spille bra sjakk trengs et søketre og en evalueringsfunksjon.

Tre ganger verdensmester Mikhail Botvinnik var overbevist om at den eneste måten en datamaskin kunne bli god til å spille sjakk på, var å tenke som en stormester. Han mente det lureste var å plukke ut noen få gode trekk og kun regne videre på dem. Det er forståelig med tanke på maskinvaren som da var tilgjengelig, men viste seg i etterkant å være feil vei å gå. Tankegangen har en soleklar ulempe, nemlig at en noen ganger går glipp av trekkrekkefølger som kanskje 20 trekk senere fører til tap.

Alle moderne sjakkmotorer bruker derfor en «brute force» strategi, som går ut på å undersøke absolutt alle lovlige trekk. Det koster litt, men kan forsvares med de utrolige hastighetene vi har på prosessorer i dag. For å håndtere søket brukes forskjellige søketrær som baserer seg på «minmax»-algoritmen. Den går ut på at man rekursivt finner alle mulige trekk i en posisjon helt til en definert dybde er nådd. Nede på bunnen av dypet brukes så en evalueringsfunksjon som analyserer stillingen og gir poeng etter hvor god den er. Disse poengene blir sendt oppover i treet igjen etter regler som er bestemt av algoritmen.

Prosessen er lettere å forstå med et eksempel, hvor vi for enkelhets skyld jukser litt og reduserer antall mulige trekk til to. For å finne beste trekk i en utgangsstilling gjør man så følgende:

• Hvit prøver med bonde til h3 og løper til e4
• Sort svarer med to trekk til hvert av dem
• Hvit svarer hvert av dem igjen med to ny trekk og bunnen er nådd
• Evalueringsfunksjonen regner ut poengsummen for hver av de åtte sluttstillingene

Poengene sendes nå oppover treet igjen ved bruk av «minmax»-metoden som går ut på at hvit alltid antar at sort vil gjøre det beste trekket og motsatt. I vårt eksempel er lave tall bra for sort («min») og høye tall bra for hvit («max»)

• Hvit sammenligner de fire trekk-parene sine poeng og sender det høyeste tallet ett steg opp
• Sort gjør det samme, men sender det laveste tallet et steg opp
• Hvit velger igjen det høyeste tallet og finner ut at bonde til h3 er best

I partier fra den virkelige verden vil selvfølgelig datamaskinen søke mye dypere over langt flere muligheter. For hvert eneste trekk vokser antall varianter eksponensielt og det gir ekstremt mye å regne seg igjennom. For å få bukt med problemet brukes mer avanserte løsninger som «negamax», «alpha-beta pruning» og «transposition table» for å nevne noen få. Slike algorithmer har forskjellige måter å trimme treet på eller finne snarveier ned til bunn om du vil.

Prikken over i-en

Evalueringsfunksjonen som bedømmer en stilling i enden av søketreet er den siste viktige oppgaven for å få en fullverdig sjakkmotor. Den skiller menn fra mus i en verden hvor digitale sjakkspillere ofte kniver med hverandre daglig.

Alt av metoder og algorithmer nevnt fram til nå kan betegnes som «iskald beregning», mens det å vurdere en posisjon krever litt dypere kunnskaper om sjakk. Selvsagt er det også her en god del kjedelige utregninger og kjente teknikker, men de som stikker av med pokalen har som regel litt ekstra utenom det vanlige. Programmerere har derfor ofte en stormester eller to med på laget for å finne fram til de smarteste løsningene.

Ikke alle er så priviligerte, men heldigvis kommer man langt på vei med det kjente og tilgjengelige. For å evaluere en sjakkstilling er det mest naturlig å begynne med brikkenes verdi. Differansen mellom den totale verdien av hver spillers brikker gir en god indikasjon på hvem som står best. Det er også verdt å nevne at brikker kan ha ulike verdier på forskjellige stadier i spillet eller hvor på brettet de står. Andre metoder som brukes til å gi poeng i en posisjon kan være:

• Hvordan brikkene er plassert i forhold til sentrum av brettet
• Antall bønder og deres formasjon
• Hvor trygt kongen står
• Hvor mye plass brikkene har å spille på
• Kontroll over strategiske felter
• Utviklingen av brikkene

Dermed har faktisk sjakkmotoren løst alle de tre viktigste oppgavene og er klar til å sette enhver sjakkspiller på prøve. Det er alltid rom for forbedringer, men i bunn og grunn er det ikke så mye som skal til. Meksikaneren Oscar Toledo Gutiérrez har spesialisert seg på å lage et nano-sjakkprogram med en størrelse på bare 1 kB! Det finnes også i en Javascript-versjon slik at hvem som helst kan prøve seg.

Magnus Carlsen er best i verden

Datamaskiner har kommet for å bli og med det også umenneskelige sjakkspillere som spiller god kompromissløs sjakk. Styrken deres er blant annet at de aldri blir trøtte og sjelden går glipp av noe, så lenge søketreet går dypt nok. Mennesker har derimot en bedre forståelse for visse typer stillinger på brettet og kan se dypere enn maskinene. Med riktig strategi og god utholdenhet er det fremdeles mulig å slå Stockfish og vennene hans, men sannsynligvis bare for elitespillere.

Det er likevel ikke helt feil å kalle Carlsen for verdens beste sjakkspiller. Han er i følge nye beregninger tidenes mest nøyaktige spiller og gjør utrolig sjeldent feil ved brettet. I en kamp hvor Magnus hadde fått lov å bruke hjelp fra et dataprogram er det liten tvil om hvem som hadde vunnet flest partier.

Det er passende å runde av med et sitat fra programmereren Rune Zakariassen. I et inspirerende foredrag han holdt sammen med stormester Rune Djurhuus sa han følgende med et lite håp i stemmen:

– Jeg kommer aldri til å slå Magnus Carlsen i sjakk, men teoretisk sett burde jeg kunne lage en sjakkmotor som er like god.

Det er vel det nærmeste oss dødelige kan komme å slå verdensmesteren i sjakk.

Lykke til i VM Magnus!

Du kan også spille sjakk på mobilen eller nettbrettet:
Her er de beste og de mest populære sjakk-appene »

(Kilder: wikipedia, gamedev.net, chessprogramming.wikispaces.com, foredrag med Rune Zakariassen og GM Rune Djurhuus: Chess Engines Theory and Practice)