I 1996 slo datamaskina Deep Blue verdsmeisteren Kasparov i eit sjakkparti. Det var første gongen at eit kunstig intelligensprogram slo verdsmeisteren i sjakk. Utviklinga heldt fram, og i dag er sjølv sjakkprogrammet på mobiltelefonen ein langt betre spelar enn Magnus Carlsen. Ikkje rart spelarar vert freista til å jukse.

Stockfish er det beste programmet på marknaden som nyttar dei prinsippa vi skildrar nedanfor. Stockfish er eit såkalla ope kjeldekodeprosjekt, og arbeidet er leia av nordmannen Tord Romstad. Det er litt kjekt at både verdas beste sjakkspelar og verdas beste sjakkprogram har så sterk norsk tilknyting.

Topersonsspel som sjakk var heilt frå starten på 1950-talet eit viktig problemområde innan kunstig intelligens. Det å spele sjakk vart sett på som ein av dei vanskelegaste intellektuelle aktivitetane ein kunne halde på med. Pionerane utvikla stadig betre metodar for å få datamaskina til å spele sjakk godt og utforska lenge den såkalla alfabetaalgoritmen.

Også Hubert Dreyfus, ein skarp kritikarar av kunstig intelligens-feltet, meinte at sjakk var viktig, og sa at det ville vere umogleg for eit dataprogram å spele sjakk like godt som eit menneske. Då han tapte mot eit sjakkprogram, unnskyldte han seg med at det ikkje var særleg imponerande, for han var jo elendig i sjakk.

For at eit program skal kunne handtere sjakk, må ein bruke ein tenkt struktur som vert kalla speltre kombinert med ein såkalla minimaxalgoritme. Speltreet har, som alle tre, ei rot, og rota representerer utgangsstillinga som algoritmen skal finne det beste trekket for. Spelaren som skal flytte, kallar vi Max, og den andre kallar vi Min.

Frå rota går det ei grein ut for kvart mogleg trekk. Greina endar opp i ei ny stilling der Min skal spele. Den nye stillinga har igjen greiner til stillingar Max skal spele frå. Slik veks speltreet nivå for nivå med Max og Min annankvar gong i trekket.

Om ein skal finne ut kva trekk som er best, kan eit program følgje greinene, ein for ein, til sluttstillingane for spelet. Vi kallar gjerne slike sluttstillingar for lauv. I sjakk er resultatet tap (0), remis (0,5) eller siger (1) for Max. Om vi startar på lauva, vil vi kunne rekne ut verdien av spelet sett frå Max’ synspunkt for alle stillingane (forgreiningspunkta) i treet.

Strategien for Max er å komme til eit lauv som har så høg score som mogleg, medan Min vil prøve å komme til eit lauv som gjev Max så liten score som mogleg. Max vil alltid velje den greina som gjev best score i sine forgreiningar, medan Min alltid vil velje den greina som gjev minst score. Programmet kan i prinsippet gå gjennom heile treet, og Max bør til slutt velje den greina ut frå rota som gjev best score.

Men i spel som sjakk vil speltreet frå startposisjonen ha om lag 10120 ulike stillingar. Dette er det umogleg for noko dataprogram å handtere i praksis. Eit første forsøk er å redusere mengda av stillingar med den smarte alfabetaalgoritmen.

Den verkar slik at programmet følgjer greinene i det tenkte treet heilt ut til lauva og flyttar seg opp og ned langs greinene på ein systematisk måte. På annakvart nivå må det sjå spelet frå synspunkta til Max og Min.

Om Min er i trekket i ei forgreining, kan kanskje Min tvinge fram ein score som er dårlegare (for Max) enn den Max kan få ved eit anna val i ei tidlegare forgreining. Då vil Max unngå denne stillinga. Utprøving av nye greiner her er altså meiningslaust, så algoritmen går heller tilbake til trekket før.

Om Max er i trekket, kan han tilsvarande stoppe søket om Max kan få ein betre score enn den Min kan tvinge fram ved å velje ein annan veg i spelet. Verdiane som gjer at søket stoppar på ei forgreining, vert kalla alfa og beta. Alfa gjev ei nedre grense for scoren til Max så langt, og viss Min kan score mindre enn dette på ei forgreining, stoppar søket. Beta gjev ei øvre grense for kva Max kan score, og viss Max kan score høgre enn dette på ei forgreining, stoppar søket.

Eit speltre (med rota øverst) for Tripp-Trapp-Tresko. Max kan ikkje håpe på å vinne, og helst bør Max satse på uavgjort. Verdien i kvar stilling er enten -1, 0, eller 1 sett frå Max’ side.

Alfabetasøk kan gjerast med eit lite, men elegant program, og det kan kanskje redusere tal på undersøkte stillingar til 1060, men heller ikkje dette er nok til å gjere sjakkspelet løyseleg. Utviklarane må redusere storleiken på søkjetreet endå meir.

Derfor nyttar utviklarane ein såkalla heuristikk, ein regel som kjapt estimerer kor god ei stilling er for Max. Denne regelen tek omsyn til brikkebalansen, kor mange moglege trekk spelarane har, kor mange brikker dei har som angrip sentrum, og så vidare. Estimatet er gjerne tenkt å indikere eit overtak som tilsvarer eit overtak i bønder på brettet.

Med heuristikken kan Stockfish kutte ned på speltreet ved å la vere å søkje lenger enn til dømes ti trekk. Trekka som vert valde, er altså baserte på estimat av stoda nokre trekk framover, kombinert med bruk av alfabeta. Men alle estimat kan vere feil, så valde trekk frå sjakkprogrammet kan godt vere dårlegare enn det beste.

Grunnen til at det finst sjakkprogram som slår Magnus Carlsen med god margin, er i hovudsak den store reknekapasiteten. Datamaskinene i dag er raskare og har mykje større minne enn det som var tilfelle på 90-talet og før. Prinsippa har ikkje endra seg, sjølv om Stockfish gjer ein del smarte ting i tillegg. No kan vi søkje i mykje større speltre enn den gongen, kanskje nokre hundre millionar stillingar per sekund på ei vanleg datamaskin.

Det må nemnast at forskarar ved Google har utvikla sjakkprogrammet Alpha Zero, som nyttar svært kraftige datamaskiner og maskinlæring og innimellom slår Stockfish i testar. Men korleis dette programmet verkar, er ei anna historie.

Bjørnar Tessem
og Lars Nyre