JavaScript is disabled in your web browser or browser is too old to support JavaScript. Today almost all web pages contain JavaScript, a scripting programming language that runs on visitor's web browser. It makes web pages functional for specific purposes and if disabled for some reason, the content or the functionality of the web page can be limited or unavailable.

Takk for at du vil dele artikkelen

Den du deler artikkelen med, kan lese og eventuelt lytte til heile artikkelen.
Det gjer vi for at fleire skal oppdage DAG OG TID.

Namnet ditt vert synleg for alle du deler artikkelen med.

TeknologiFeature

Sjakkprogrammet Stockfish

Kvar veke les vi inn utvalde artiklar, som abonnentane våre kan lytte til.
Lytt til artikkelen
5711
20221104
5711
20221104

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.

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

Digital tilgang til DAG OG TID – heilt utan binding

Prøv ein månad for kr 49.
Deretter kr 199 per månad. Stopp når du vil.


Eller kjøp eit anna abonnement

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.

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

Grunnen til at det finst sjakkprogram som slår Magnus Carlsen med god margin, er i hovudsak den store reknekapasiteten.

Emneknaggar

Fleire artiklar

President Donald Trump held valkampmøte i Traverse i Michigan 25. oktober.

President Donald Trump held valkampmøte i Traverse i Michigan 25. oktober.

Foto: Carlos Barria / Reuters / NTB

KommentarSamfunn

Få dagar før det amerikanske presidentvalet er det klart at Donald Trump kan bli vald.

Kva kan ein Trump-siger få å seia for verda, for Europa og for Noreg?

Halvor Tjønn
President Donald Trump held valkampmøte i Traverse i Michigan 25. oktober.

President Donald Trump held valkampmøte i Traverse i Michigan 25. oktober.

Foto: Carlos Barria / Reuters / NTB

KommentarSamfunn

Få dagar før det amerikanske presidentvalet er det klart at Donald Trump kan bli vald.

Kva kan ein Trump-siger få å seia for verda, for Europa og for Noreg?

Halvor Tjønn
Stian Jenssen (t.v.) var alt på plass i Nato då Jens Stoltenberg tok til i jobben som generalsekretær i 2014. Dei neste ti åra skulle dei arbeide tett i lag. Her er dei fotograferte i Kongressen i Washington i januar i år.

Stian Jenssen (t.v.) var alt på plass i Nato då Jens Stoltenberg tok til i jobben som generalsekretær i 2014. Dei neste ti åra skulle dei arbeide tett i lag. Her er dei fotograferte i Kongressen i Washington i januar i år.

Foto: Mandel Ngan / AFP / NTB

IntervjuSamfunn
Christiane Jordheim Larsen

Nato-toppen som sa det han tenkte

Stian Jenssen fekk kritikk då han som stabssjef i Nato skisserte ei fredsløysing der Ukraina gjev opp territorium i byte mot Nato-medlemskap. – På eit tidspunkt må ein ta innover seg situasjonen på bakken, seier han.

President Joe Biden og visepresident Kamala Harris i august 2023. Den økonomiske politikken deira bidrog til å få ned arbeidsløysa, men inflasjonen som tok av i 2022, gjorde større inntrykk.

President Joe Biden og visepresident Kamala Harris i august 2023. Den økonomiske politikken deira bidrog til å få ned arbeidsløysa, men inflasjonen som tok av i 2022, gjorde større inntrykk.

Foto: Evan Vucci / AP / NTB

Samfunn
Per Anders Todal

Harris blir heimsøkt av inflasjonen

Kanskje vart presidentvalet i USA 2024 avgjort ved bensinpumpene og i matbutikkane.

Noreg er på tredjeplass i kokainbruk i Europa.

Noreg er på tredjeplass i kokainbruk i Europa.

Foto: Beate Oma Dahle / NTB

Samfunn
Sofie May Rånes

– Meiningslaust å straffe sjuke

Ronny Rene Raveen, tidlegare politimann og rusmisbrukar, vil ha avkriminalisering av rusmisbrukarar og unge opp til 25 år.

Høyanger i Vestland er ein relativt urban industristad, men talet på innbyggarar går éin veg. I fjor mista dei Tronvik, ei ruseining med 50 tilsette under Helse Førde. Å miste den vidaregåande skulen vil vere endå ein spikar i kista.

Høyanger i Vestland er ein relativt urban industristad, men talet på innbyggarar går éin veg. I fjor mista dei Tronvik, ei ruseining med 50 tilsette under Helse Førde. Å miste den vidaregåande skulen vil vere endå ein spikar i kista.

Foto: Marit Hommedal / NTB

ØkonomiSamfunn

Med skulane som hjørnesteinar

Det er dyrt å drive ein halvfull skule. Men kostnaden ved å flytte elevane om skulen blir nedlagd, er vanskelegare å rekne ut.

Marita Liabø
Høyanger i Vestland er ein relativt urban industristad, men talet på innbyggarar går éin veg. I fjor mista dei Tronvik, ei ruseining med 50 tilsette under Helse Førde. Å miste den vidaregåande skulen vil vere endå ein spikar i kista.

Høyanger i Vestland er ein relativt urban industristad, men talet på innbyggarar går éin veg. I fjor mista dei Tronvik, ei ruseining med 50 tilsette under Helse Førde. Å miste den vidaregåande skulen vil vere endå ein spikar i kista.

Foto: Marit Hommedal / NTB

ØkonomiSamfunn

Med skulane som hjørnesteinar

Det er dyrt å drive ein halvfull skule. Men kostnaden ved å flytte elevane om skulen blir nedlagd, er vanskelegare å rekne ut.

Marita Liabø

les DAG OG TID.
Vil du òg prøve?

Her kan du prøve vekeavisa DAG OG TID gratis i tre veker.
Prøveperioden stoppar av seg sjølv.

Komplett

Papiravisa
Digital utgåve av papiravisa
Digitale artiklar
Digitalt arkiv
Lydavis

Digital

Digital utgåve av papiravisa
Digitale artiklar
Digitalt arkiv
Lydavis

Komplett

Papiravisa
Digital utgåve av papiravisa
Digitale artiklar
Digitalt arkiv
Lydavis

Digital

Digital utgåve av papiravisa
Digitale artiklar
Digitalt arkiv
Lydavis