Artikel top billede

(Foto: Computerworld)

Nu lærer computeren selv at spille skak

Skakverden var i chok, da det sidste år tog en Google-finansieret skakcomputer fire timer at blive verdens bedste i det ædle tankespil. Her fortæller vi, hvordan det kunne lade sig gøre, og tager dig med ud i skakcomputernes verdenshistorie     .

Af Caspar Haarløv, Alt om Data

Denne artikel er oprindeligt bragt på Alt om Data. Computerworld overtog i november 2022 Alt om Data. Du kan læse mere om overtagelsen her.

Et chok bredte sig i den internationale skakverden, da det britiske Google-firma Deepmind i december 2017 præsenterede AlphaZero. Den danske stormester i skak Peter Heine Nielsen, der træner den norske verdensmester Magnus Carlsen, udtalte, at ”det er det mest fascinerende og skræmmende, jeg har set.”

Det er dog ikke nyt, at et computerprogram spiller fremragende skak. Det er over tyve år siden, at IBM Deep Blue slog Garry Kasparov. Den store forskel fra dengang til nu er udviklingen af kunstig intelligens.

Deep Blue var først og fremmest en programmeringsmæssig præstation. Taktikken var baseret på træk, der oprindeligt var udtænkt af mennesker – helt præcist 700.000 kampe mellem stormestre. AlphaZero, derimod, er ikke blevet fodret med andet end reglerne for skak og har selv eksperimenteret sig frem ved at spille mod sig selv.

Og så er der det med hastigheden. Det tog fire timer for AlphaZero at træne sig selv til at blive bedre end det hidtil stærkeste skakprogram, Stockfish. Det tog 10 år at programmere Deep Blues efterfølger Deep Junior. Inden for det samme døgn lærte AlphaZero sig selv at blive verdens bedste både til skak, Go og det japanske skak-lignende brætspil shogi.

Kunstig intelligens i stor skala

Lars Kai Hansen, der er professor ved DTU Compute og ekspert i kognitive systemer, fortæller, at AlphaZero egentlig ikke er anderledes end anden kunstig intelligens, vi ser i dag.

”Men det foregår på en meget stor skala, både økonomisk og computermæssigt, derved adskiller den sig fra tidligere resultater.”

Men hvorfor bruge så mange kræfter på at udvikle en skakcomputer? Lars Kai Hansen ser først og fremmest sociale perspektiver i udviklingen.

”Der er række områder i samfundet, hvor det enten er for dyrt eller besværligt at lave høj grad af konventionel personlig service. For eksempel inden for sundhed, økonomi eller uddannelse, hvor velhavende mennesker kan få meget bedre rådgivning og service. Der ville AI kunne give bredere adgang til detaljerede og personlige råd.”

”Selvom det er for eksempel sundhed, der er målet for AI-forskning, bliver forskningen ofte anvendt inden for meget simplere domæner som spil. Simpelthen fordi man her kan se generelle intelligensproblemer udlevet i enkle omgivelser. Det kan være problemstillinger som f.eks. afvejning af nysgerrighed og grådighed, eller om det kan betale sig at tage et kortsigtet tab for at opnå en langsigtet gevinst. Man forestiller sig at, når det principielle er forstået ved hjælp af spillene, kan vi gå videre til at se på de mere alvorlige samfundsproblemer,” siger Lars Kai Hansen.

En slags intuition

Det mest bemærkelsesværdige ved DeepAlpha er den måde, som den spiller skak på. Den laver ikke flere beregninger end andre programmer. Tværtimod. Til gengæld har maskinen tilsyneladende udviklet en form for intuition, som er helt anderledes end menneskers.

Programmet laver engang imellem nogle tilsyneladende vanvittige ofre som at tilbyde et tårn og en dronning for at udnytte en positionel fordel – og vinder. I et andet tilfælde flyttede programmet sin dronning til hjørnet af brættet med en overraskende positionsværdi.

Men hvordan virker den? Først og fremmest er AlphaZero baseret på ekstrem stærk
computerkraft. Den bruger 5000 første-generations-TPU'er til at generere spil og 64 andengenerations-TPU'er til at træne de neurale netværk.

Men den beregner ikke flere stillinger end sine modstandere. Stockfish undersøger cirka 70 millioner stillinger pr. sekund, mens AlphaZero undersøger ca. 80.000 pr. sekund, altså næsten 1000 gange færre stillinger.

Det er nøjagtig som med de bedste menne-skelige spillere, der som regel beregner færre variationer end svagere spillere. I stedet bruger de deres stærke intuition til at fokusere på de mest relevante linjer i spillet. Det virker, som om computeren udviklede en tilsvarende intuition. Men hvordan det?

Google købte DeepMind i 2014. London-selskabet bag AlphaZero udvikler spilalgoritmer.

Et nyt princip

Alle hidtidige, populære skakmotorer er baseret på minimax-algoritmen, hvor det træk udvælges, der giver den største fordel uanset, hvad modstanderen spiller. Minimax forbedres med alfa-beta-beskæring, som reducerer antallet af variationer, der skal undersøges.

Når computeren overvejer et træk, analyserer den alle modstanderens mulige svar. Lad os sige, at der er 20 mulige svar. Et af disse svar fører til mat – eller tab af en vigtig brik. Derefter vil programmet opgive det skridt uanset, hvor dårligt den ville stå efter nogle af de 19 andre svar.

Dette princip kombineres med andre principper som for eksempel kendskab til tidligere spil og forventningen om gentagelse af bestemte mønstre.

AlphaZero bruger derimod Monte Carlo Tree Search eller MCTS. MCTS evaluerer en position ved at generere et antal bevægelsessekvenser (kaldet "playouts") tilfældigt og beregne de gennemsnitlige slutresultater. Dette tilfældighedsprincip gør, at maskinen i sin læringsproces tager skridt, som et menneske aldrig ville tage. Derfor oplever vi dens spil som fremmed eller ligefrem vanvittigt.

Men fordi den har kraft nok til at gennemgå ufattelige mængder af spil giver denne fremgangsmåde også maskinen en erfaring, hvor disse tilsyneladende vanvittige træk virker. Disse træk tager den uden tilsyneladende at tænke meget over det. Og det skaber illusionen af at møde en maskine med en ”over-menneskelig” intuition.

En svaghed i MCTS er, at dens playouts er tilfældige. Derfor kan det gå helt galt i bestemte stillinger, hvor der kun er én bestemt linje til optimalt spil. Hvis programmet ikke tilfældigvis vælger denne linje, vil det sandsynligvis tabe.

Det begyndte med en skaktyrken i 1770

Skaktyrken var verdens første skakcomputer – uden at være det.

Den første skakspillende maskine blev præsenteret i 1770. ”Skaktyrken” havde form som en træfigur i tyrkisk klædedragt bygget sammen med et stort skrivebord, hvorpå der stod et skakspil. Bag låger i skrivebordet kunne man skimte en urværk-lignende mekanik, som sammen med lyden af drejende tandhjul og løbende stålkæder gav indtryk af, at der virkelig var tale om en mekanisk robot, der var i stand til at spille skak uden menneskelig indblanding.

Skaktyrken blev dog styret af en lille person, der gemte sig i skrivebordet, og som fulgte med i spillet ved hjælp af magnetiske skakbrikker og et omvendt skakbræt under bordet. Men det blev først afsløret mange år senere og inden det, nåede Skaktyrken at slå både Napoleon og den senere amerikanske præsident Benjamin Franklin. Turing kom på banen Den første rigtige skakcomputer blev dog først fremstillet senere.

En af frontfigurerne var Alan Turing (ham der knækkede nazisternes enigma-kode), der udviklede ideen bag skakcomputer-programmer. For Turing, der begyndte at arbejde på programmet i 1948, havde ikke en computer at køre sit program på og gennemførte derfor selv de lange rækker af beregninger i hånden ved hjælp af en blyant og strimler af papir.

Det tog ham efter sigende i omegnen af 30 minutter at gennemføre et træk. I 1956 lykkedes det at programmere en Univac Maniac I computer til at spille skak på et 6 x 6-bræt uden tårne. Men allerede året efter programmerede man på MIT i USA en IMB 704 til at spille skak på et fuldt bræt. I 1958 tabte et menneske for første gang til et computerprogram.

Den menneskelige spiller havde dog aldrig spillet skak før. Den første skakstormester, der tabte til en computer, var Michael Stean i 1977. I 1985 udfordrede den daværende verdensmester Kasparov de 15 bedste skakcomputere i verden og vandt hvert eneste spil.

I 1997 lykkedes det så folkene bag IMB Deep Blue at slå Kasparov. Men Kasparov har aldrig accepteret resultatet, og i 2003 spillede han uafgjort mod Deep Blues efterfølger, Deep Junior.

Er den intelligent?

Hvordan skal vi som almindelige ikke-computer-specialister forstå en skakcomputer, der lærer sig selv at spille ved hjælp af metoder, specialisterne kalder kognition, intuition og intelligens?

”Kognition, intuition og intelligens er menneskelige kompetencer, som vi gerne vil overføre til computere. Der er ikke nogen fysisk grund til, at det ikke skulle kunne ske. Hjernen er stadig, både i bredde, dybde og energieffektivitet, mange gange bedre end vore computersystemer. Men computerne kommer tættere og tættere på,” siger Lars Kai Hansen.