(TF)² #13 – Schackdatorer, AI och the end of genesis T.N.K.evolution turbo type D

För 50 år sedan var AI och schack starkt associerat. Man såg det fortfarande som ett intelligensproblem att göra en bra schackspelande dator. Sedan dess har AI och schack hunnit göra slut och bli ihop igen flera gånger. Denna romans är perfekt för att förstå AI:s framgångar och nederlag och vad vi kan förvänta oss av framtiden.

När jag var blott en liten parvel i början på 80-talet så hade vi en schackdator. Chess Champion Mark V var ett stiligt grått rätblock med specialdesignad hårdvara, som jag spelade så mycket på att texten på knapparna blektes bort och de lossnade. Inställd på 3 sekunders betänketid kunde även ett barn spela mot den med viss framgång. I dag räcker 3 sekunder per drag för att de bästa schackdatorerna ska krossa världsmästaren.

Chess Champion Mark V 🥲

Min pappa programmerade flera schackdatorer under min uppväxt, där den kanske mest framgångsrika var den senaste, Alaric, som kom fyra i schackdator-VM 2008. Med ett eget intresse av programmering, schack och AI sedan barnsben så föll det sig naturligt att jag själv har följt schackdatorns utveckling noga under åren. Sverige skulle för övrigt spela en roll i schackdatorutvecklingen eftersom SSDF, Svenska Schackdatorföreningen, arrangerade matcher mellan de bästa schackdatorerna och publicerade den rankinglista som åtminstone fram till 2000-talet hade hela världens ögon på sig, eftersom den sågs som den officiella schackdatorrankingen över världstoppen. På 80-talet skickades dessa ut som som en del av SSDFs svartvita tidskrifter, som vi naturligtvis hade fullt av hemma. Ryktet gör gällande att dessa fortfarande ligger arkiverade i en låda, om någon behöver rykande färska schackdatornyheter.

Chess Champion Mark V designades av David Levy, som var en duktig schackspelare och AI-pionjär. Levys AI-kunskaper (han var bl.a inblandad i att vinna Loebner-priset både 1997 och 2009) skulle senare bli ovanliga i schackdatorvärlden. 1968 slog Levy vad med ett av historiens största datorgenier, John McCarthy (myntade begreppet AI, uppfann LISP och garbage collection..), om att ingen schackdator skulle kunna slå honom inom tio år. 1978 spelade Levy en match mot den då bästa datorn och vann. Detta är ett generellt återkommande tema i AI - förbättringen är inte linjär. Även stora genier som McCarthy överskattar hur snabbt datorer kommer bli bra på olika uppgifter, men när utvecklingen i ett AI-område senare tar fart så underskattar vi i stället hur snabbt det går.

Människan faller

1997 hände det oundvikliga. Garry Kasparov, 20 år som världsetta och av många ansedd som den bästa spelare som någonsin rört en schackpjäs, blev slagen av IBMs snabbräknande maskin med futuristisk specialhårdvara, Deep Blue. Ingen trodde att människan skulle falla så snabbt. Sju år senare var vanliga persondatorer tillräckligt bra för att lätt slå de bästa stormästarna i Man vs Machine World Team Championship.

Garry Kasparov med en blick som skrämde många vid brädet.

Ingen trodde att människan skulle falla så snabbt, men problemet var att datorerna blev ca 50 Elo-poäng bättre varje år (100 Elo-poäng betyder ungefär dubbelt så bra) och när datorerna närmade sig 2800 (världsmästarnivå) i Eloranking så saktade de inte ned. . Mänskliga begränsningar hade inget med dem att göra, så de fortsatte att bli bättre i samma takt och trenden fortsätter än i dag. Samma sak har hänt och kommer att hända i många andra AI-områden.

...igen..

Kasparov introducerade Advanced Chess som ett sätt för människan att fortsätta vara relevant. I denna tävlingsform så får en människa använda en schackdator för att de tillsammans ska nå de bästa besluten - en så kallad kentaur. På detta sätt kan man få människans strategiska känsla tillsammans med datorns övermänskliga taktik. Kasparov är en känd talare runt om i världen och skrev och pratade ofta om hur detta sätt är hur människor och AI kan samexistera och förstärka varandra.

På Tenfifty tycker vi att detta är en bra metod och förespråkar det ofta i kundprojekt, men det är också värt att känna till att Advanced Chess sedan många år är dött, eftersom människan inte längre tillför något. Det finns inte längre någon anledning att blanda in oss i schackgudarnas partier.

En anledning till att människan blev överflödig så snabbt är att schack är ett slutet system. Reglerna och målen är kända. I mer komplicerade situationer i verkliga världen så har människor ofta kunskap om strategiska omständigheter, rykten och händelser som datorn inte känner till. Därför kommer kentaurerna dominera beslutsfattandet i många år till.

AI stormar tillbaka

Dominansen gjorde att schackdatorer blev tråkiga för allmänheten och i AI-världen tyckte man ända sedan slutet på 80-talet att schack inte hade så mycket med AI att göra. Allt detta ändrades dock när AlphaZero tog schackvärlden med storm i december 2017! DeepMind publicerade resultat där deras nya schackdator slog det högst rankade programmet Stockfish (som från början skrevs av norrmannen Tord Romstad - Norge har chockerande nog alltså de senaste 10 åren både den mänskliga och den maskinliga världsmästaren i schack) stort i en match. I 100 partier vann AlphaZero 25 partier som vit, 3 som svart och resten blev remi.

AlphaZero är ett program vars ställningsbedömning och dragsortering helt baseras på ett neuronnät. En intressant detalj är att DeepMind använde exakt samma arkitektur som man använder för bilder, där varje ruta på brädet ses som en pixel och varje pjästyp en sorts färg. AlphaZero lärde sig helt och hållet på egen hand, genom att spela miljoner partier mot sig själv.

Precis som att en mänsklig stormästare räknar långsammare men kan kompensera genom att värdera ställningar och välja drag bättre, så var AlphaZero mer lik en människa. Den räknade "bara" ca 80 000 positioner i sekunden, jämfört med Stockfish som på hårdvaran de använde i matchen nådde ca 70 000 000 positioner i sekunden. En stormästare räknar ca 1 position i sekunden. AlphaZero var en stor framgång för det tilltalande angreppssättet att ge så lite förkunskap som möjligt till en modell och i stället bara ösa på med datorkraft och data (antal träningspartier i detta fall).

En omdiskuterad fråga var hur rättvisa hårdvaruförhållanden det varit i matchen mellan AlphaZero och Stockfish. AlphaZero kör mestadels på en grafikprocessor, medan Stockfish kör på en traditionell CPU. Hur gör man det rättvist? Detta löste sig med open source-projektet Leela som replikerade AlphaZeros resultat och sedan byggde vidare på det. Nuförtiden spelas de största datortävlingarna av Top Chess Engine Championship (TCEC i folkmun) och de bestämde sig för att hårdvaran för de olika datortyperna helt enkelt skulle kosta lika mycket. I början av 2020 slog Leela Stockfish med 52.5 - 47.5 på sådan hårdvara och ingen kunde längre tvivla på att AI var tillbaka!

För 25 år sedan föll mänsklig intelligens mot maskinen, när det visade sig att inte ens de bästa längre kunde mäta sig. För 5 år sedan föll människan igen på metanivån, när det visade sig att inte ens mänsklig förkunskap kring ställningsbedömning är värdefull för att utveckla en schackdator.

the end of genesis T.N.K.evolution turbo type D

Men.. Historien har fått ytterligare en intressant vändning, vilket egentligen är anledningen till att jag skriver denna bloggpost.

Det första offret för DeepMind var faktiskt spelet Go genom programmet AlphaGo 2016. Go är ett mer komplicerat spel än schack och innan AlphaGo så var fortfarande människan bättre än de bästa programmen. Detta ändrade sig med matchen mellan det unga självsäkra koreanska geniet Lee Sedol, där AlphaGo vann med 4-1. Lee Sedol trodde att han skulle krossa datorn och sade efteråt att han var chockad. Kommer ni ihåg vad vi lärde oss tidigare? När maskinen kommer så kommer den snabbt. Jag kan starkt rekommendera den kritikerrosade dokumentärfilmen Alpha Go - The Movie (Finns på Netflix, men DeepMind har tillgängliggjort den gratis på Youtube i länken) som handlar om både maskiner och människor.

Lee Sedol sliter mot AlphaGo

Shogi, japanskt schack, föll också mot AlphaZero som lärde sig alla tre disciplinerna (schack, go och shogi). Precis som med go, så är shogi mer komplicerat och hade tidigare varit svårt för datorer. Men i shogivärlden hände något intressant och mycket mindre publicerat! Den japanske datavetaren Yu Nasi uppfann 2018 en egen neuronnätstyp som han kallade NNUE (ƎUИИ Efficiently Updatable Neural Networks). NNUE är ett mer traditionellt neuronnät som tar handkodade egenskaper om ställningen som indata, i stället för ett helt bräde som AlphaZero gör. NNUE klarar att indata ändras inkrementellt, som den ofta gör i dessa sammanhang eftersom ett drag inte gör så stor skillnad, och kan då räkna om bara en liten del av sin utvärderingsfunktion och därför köra på en vanlig CPU i stället för en GPU. Det första programmet som hade denna funktion hade det väldigt japanska namnet the end of genesis T.N.K.evolution turbo type D. En nästan okänd revolution, men Yu och hans vänner i dator-shogi-gruppen The Minstrel's Ballad: Tanuki's Reign hade inte riktigt samma PR-muskler som Google-ägda DeepMind. NNUE visade sig vara en stor framgång och detta var första gången en övermänsklig shogi-dator kunde spela på en vanlig processor.

På mindre tekniskt språk så har pendeln alltså svängt tillbaka. I stället för att ge en rå ställning som indata till modellen, så bestämmer människor vilka delar av ställningen som är viktiga och hur dessa ska uttryckas för en modell. Neuronnätet får sedan bestämma hur viktiga dessa ställningselement är i kombination med varandra. I stället för att spela Advanced Chess så spelar vi nu Advanced Programming där en ståtlig kentaur har tagit tillbaka kronan från den delvis självprogrammerande AlphaZero.

Stockfish-teamet blev inspirerat och bytte till en identisk hybridlösning i slutet på 2020, där schackställningens egenskaper fortfarande plockas ut manuellt, men ett NNUE-nät används för att bedöma värdet av egenskaperna, speciellt i kombination med varandra (är ett löparpar värt en bonde i ett mittspel där motståndaren har många bondeöar?). Denna hybrid mellan å ena sidan mänsklig kunskap kring vad som är viktigt i en ställning och hur man effektivt kan implementera det i maskinkod och å andra sidan datorlärande av exakt hur viktiga de olika egenskaperna är, har hittills visat sig starkare än Leelas helt självlärande metod. Stockfish NNUE (det nya namnet) är nu tillbaka på tronen och har flera gånger i rad slagit Leela och de andra utmanarna i TCEC.

Vad kan vi lära oss?

Det finns en generell läxa att lära sig här. När man har begränsat med data är mänskliga priors fortfarande ovärderliga för att göra bra och robusta modeller. Men till och med när man har ett slutet system, obegränsat med data, nästan obegränsat med beräkningskapacitet och världens bästa AI-forskare så är det fortfarande svårt att konkurrera med kombinationen av människa och maskin.

Det finns även en annan läxa. Schack ansågs som ett löst problem och ointressant tills någon igen insåg att det finns en massa intressant mänsklig intelligens att ersätta här. Jag får känslan av att många i AI-världen gör samma misstag igen. Schackdatorer känns återigen lösta och ointressanta. Men även de helt självlärande algoritmerna har idag en manuellt hårdkodad sökalgoritm, ett hårdkodat sätt att lära sig på genom självspelande, en hårdkodad NN-arkitektur och en massa mänsklig kunskap kring hur man effektivt implementerar schackreglerna på en processor och vilka datastrukturer som används för att stödja algoritmerna.

Det finns fortfarande flera ännu större AI-genombrott än AlphaZero att göra innan schack är "löst"!