Sve šahovske revolucije – od početaka do računalnih programa, te do umjetne inteligencije

Tijekom povijesti, šah je doživio nekoliko revolucija. Potkraj 19-tog stoljeća, prvi svjetski prvak Wilhelm Steinitz izazivao je protivnike da ga napadaju i postavio temelje strategije i pozicionog šaha. Od tada do danas šah je doživio brojne promjene, ali ništa nije revolucioniralo šah kao pojava šahovskih računalnih programa.

Sredinom 20-tog stoljeća, šesti svjetski prvak Mikhail Botvinnik je počeo posvećivati enormne količine vremena fizičkoj spremi i šahovskoj pripremi prije turnira i mečeva, čime je započela era šahovskog profesionalizma.

1970-tih, pod utjecajem jedanaestog šahovskog prvaka Roberta Jamesa Fischera, teorija otvaranja je doživjela velike promjene. Pojavili su se novi sustavi poput „ježa“ i nove ideje su udahnute čak i u stara otvaranja, dokazujući još jednom neiscrpno bogatstvo šaha.

Ništa, međutim, nije revolucionariziralo šah do te mjere kao pojava šahovskih računalnih programa. Danas su čak i najveći početnici upoznati s terminima „Stockfish“ i „Rybka“. Čak je i običan šahovski program na mobitelu jači od većine velemajstora. Nije nimalo iznenađujuće da su ih igrači počeli koristiti kao alat i učiti od njih.

Iako smo danas prihvatili šahovske programe kao nešto sasvim normalno i koristimo ih na dnevnoj bazi, vrlo malo nas je upoznato s izazovima i problemima koje su prethodne generacije nadvladale prilikom njihovog stvaranja.

Znate li tko je izmislio prvi šahovski program? Koliko je trebalo računalima da postanu jači od ljudi? Koja je razlika između klasičnog šahovskog programa i Google-ovog AlphaZero-a?

U okviru ovog članka, probat ćemo odgovoriti na ta pitanja i bolje se upoznati s poviješću šahovskih računalnih programa.

18. stoljeće – Turk

1769-te, Francuski iluzionist Francois Pelletier je nastupio u Schönbrunnu u Beču pred Marijom Terezijom. Između ostalih, u publici se našao i mađarski izumitelj Wolfgang von Kempelen. Inspiriran Pelletierovom izvedbom, Kempelen je ubrzo krenuo s izgradnjom izuma koji će kasnije postati zapamćen kao jedna od najvećih obmana u cjelokupnoj povijesti.

Već iduće godine, na istom mjestu, Kempelen je predstavio tzv. „Turka“ (eng. Turčin) – prvi automat za igranje šaha u povijesti. Njegova komplicirana konstrukcija sastojala se od nekoliko pretinaca s različitim operacijskim mehanizmima. Nad mašinom se nadvijala lutka ljudskog oblika i veličine, obučena u tradicionalne istočnjačke odore (što objašnjava podrijetlo imena).

„Turk“ je bio sposoban igrati šah i pobjeđivati ljudske protivnike. Čak je bio sposoban i prepoznati nelegalne poteze i prisiliti protivnike da ih vrate. U jednom od nastupa je čak uspio riješiti i vrlo težak šahovski problem, u kojem je cilj proći skakačem svako polje na šahovskoj ploči.

Postojao je samo jedan problem – sve je bila jedna velika prevara. „Turk“ nije bio taj koji je radio poteze, nego čovjek sakriven unutar mašinerije.

Naime, prilikom izgradnje, Kempelen je predvidio nekoliko tajnih komora, dovoljno velikih da u njih stane odrastao čovjek. Čak je napravio i prohodne hodnike, kroz koje je osoba mogla prolaziti od jednog pretinca do drugog. To je bilo važno radi čuvanja iluzije – prije svake izložbe, Kempelen je pozvao publiku da provjeri „Turka“. Čovjek unutar mašine bi ostao sakriven.

Prevara je funkcionirala! Kempelen je proputovao Europu predstavljajući svoj izum sve do 1804. Nakon smrti, mašina je promijenila nekoliko vlasnika i nastavila igrati šah do 1854, sve dok nije izgorjela u požaru u Philadelphiji.

Tijekom „života“ nitko nije otkrio prevaru.

Može se zaključiti da je prvo šahovsko računalo (program) postiglo veliki komercijalan uspjeh. Usprkos tome, ako zanemarimo nekoliko sličnih izuma, razvoj šahovskih programa je stagnirao tijekom idućih 100 godina. Značajan iskorak se dogodio tek u kasnim 1940-tima i ranim 1950-tima. Kao i u mnogim drugim područjima, povijesni svjetski događaj je bio katalizator promjena.

1950-te:  Početak jedne ere

Tijekom Drugog svjetskog rata, i saveznici i nacisti su provodili puno vremena „vrbujući“ vrhunske znanstvenike i formirajući timove. Cilj je bio jasan – pobijediti u ratu. Najveći umovi 20-tog stoljeća su posvetili svoje ratne godine razvijanju tehnologije i oružja u svrhu nadvladavanja neprijatelja. Znanost je bila sluga ratne industrije.

Usprkos tome, tijekom rata je došlo do ogromnog napretka u mnogim sferama te su postavljeni temelji mnogih novih grana znanosti. U kontekstu ovog članka, od najvećeg je interesa računalna znanost. Dva čovjeka su ponajviše zaslužna za njezin razvoj – Claude Shannon i Alan Turing.

Shannon se smatra ocem moderne teorije informacije, dok je Turing otac modernih računala (tzv. Turingov stroj). Njihov doprinos računalnoj znanosti je vrlo dobro dokumentiran. Međutim, manje je poznato da su Shannon i Turing također i očevi šahovskih računalnih programa.

Nakon što su doktorirali neposredno prije rata, Shannon i Turing su počeli raditi kao kriptoanalitičari, prvi u SAD-u, a drugi u UK-u. Obojica su bili upoznati s radom onoga drugoga te su se i upoznali 1943. godine, tijekom Turingovog dvomjesečnog posjeta Bellovom laboratoriju u New Yorku (gdje je Shannon bio zaposlenik). Nakon rata, obojica su se posvetila programiranju šahovskog računala.

1949. godine, Shannon je napisao poznati članak pod nazivom „Programiranje računala za igranje šaha“ , u kojem je opisao prvi algoritam za šahovsko računala. Gotovo istovremeno, Turing je razvio vlastito funkcionalno računalo – tzv. „Turbochamp“ – kojeg je razvijao u periodu od 1948. do 1950. godine. Koliki je on zapravo bio genijalac najbolje potvrđuje činjenica da je „Turbochamp“ programiran u potpunosti olovkom i papirom. Čak niti testiranje nije prošlo glatko – Turing ga je inicijalno neuspješno isprobao na prvom komercijalno dostupnom računalo Ferranti Mark I. Na koncu je algoritam verificiran 1951. godine u prijateljskoj šahovskoj partiji.

Zanimljivo je napomenuti da je 51 godinu Turbochamp testirao veliki Garry Kasparov. Program nije imao šanse, ali je najveći šahist ikada odao priznanje Turingovom geniju.(2)

Još uvijek nije poznato do koje su mjere Shannon i Turing surađivali, a do koje bile nezavisni – tema njihovog razgovora 1943. godine do danas nije poznata. Jedno je sigurno – njihov doprinos je bio enorman, a sve buduće generacije programera šahovskih računala su „stajali na ramenima“ ove dvojice „divova“.

Tako je 1951. godine Turingov kolega Dietrich Prinz uspio implementirati algoritam na Ferranti Mark-u I i kreirati program koji je mogao rješavati matove u 2 poteza.

1956, tim znanstvenika predvođen Stan-om Ulam-om (jednom od izumitelja hidrogenske bombe) je napravio program koji je mogao igrati šah na ploči smanjenih dimenzija (6×6).

Konačno, 1957. godine je IBM inženjer Alex Bernstein napravio prvi automatizirani program koji je u potpunosti bio sposoban odigrati cijelu partiju šaha.

Era šahovskih računalnih programa je time i službeno započela.

1960-te i 1970-te: Mali korak ili velik skok?

Prvi šahovski računalni programi su bili slabi i primitivni. Tijekom 1960-tih i 1970-tih se njihova snaga značajno povećala. Dva su glavna razloga:

• Poboljšani i sofisticirani algoritmi
  1960-tih i 1970-tih su algoritmi korišteni u šahovskim računalnim programima značajno poboljšani, ponajviše zahvaljujući geniju Johnu Von Neumannu, koji je razvio tzv. MiniMax algoritam, savršeno prilagođen za ocjenu šahovskih pozicija. U narednim desetljećima, MiniMax je dodatno poboljšan naprednim heurističkim tehnikama i tzv. „iterativnim produbljivanjem“, koje je postepeno povećavalo dubinu „izračuna“ baziranu na tom algoritmu.
• Poboljšani i brži hardver
  Jedno od najvećih ograničenja na koje su naišli Turing i ostali pioniri je bila računalna moć tog vremena. 1960-te i 1970-te su to promijenile – prema tzv. Mooreovom zakonu, računalna moć se udvostručavala svake dvije godine. Poboljšani i brži hardver je omogućio i implementaciju poboljšanih i bržih softverskih rješenja – npr. vrijeme pretrage MiniMax algoritma je višestruko smanjeno.

Doduše, nije se samo radilo o sirovoj računalnoj snazi. 1960-tih i 1970-tih, kompjutorski šah se profilirao kao zasebna disciplina. Prvo prvenstvo šahovskih računalnih programa je organizirano 1970. godine u New Yorku.

Nedugo nakon toga – 1974. – je organizirano prvo Svjetsko Prvenstvo Šahovskih Računalnih Programa u Stockholmu. Razvoj „scene“ je neizbježno doveo do osnivanja specijaliziranih kompanija koje su počele razvijati vlastite šahovske računalne programe, koji su postepeno postajali sve bolji i bolji.

Koliko dobro je „bolji i bolji“ bilo? Koliko su jaki bili tadašnji šahovski računalni programi u odnosu na ljude? Dovoljno dobri da bi pobijedili amatere, nedovoljno dobri da se natječu na majstorskoj razini.

Primjerice, 1967. godine, MacHack VI je postao prvi šahovski računalni program koji je pobijedio ljudskog protivnika. Njegova snaga se kretala oko 1300 rejtinga po USCF (američka federacija). Ali već u 1976, šahovski računalni program Chess 4.5 je pobijedio na B turniru u Sjevernoj Kaliforniji. Zatim je 1977. godine također pobijedio i na Minnesota Open-us performance ratingom od 2271 i pobjedom nad igračem klase A (prema USCF) Stenbergom.

Ipak, računala se nisu mogla nositi s jakim igračima. 1968. godine, međunarodni majstor David Levy se kladio u 3000 $ da će pobijediti bilo koji šahovski računalni program koji se pojavi u sljedećih 10 godina. 1977. godine je dobio tu okladu pobjedom protiv šahovskog računalnog programa KAISSA. 1978. je pobijedio i noviju verziju MacHack-a.

Može se zaključiti da su se 1970-tih šahovski računali programi mogli natjecati s ljudima, ali ne i igrati na majstorskoj razini.

Ali onda su došle 1980-te.

1980-te: Izazov čovječanstvu

Do početka 1980-tih, programiranje šahovskih računalnih programa je postalo unosan biznis. Sve je više kućanstava posjedovalo vlastito osobno računalo. To je dovelo do „boom-a“ u razvoju specijaliziranih softvera bilo koje vrste – pa tako i šahovskih računalnih programa. Tijekom 1982. godine, kompanije koje su se bavile njihovim razvojem su ostvarile preko 100 milijuna dolara prihoda.

Stoga nas ne treba iznenaditi činjenica da su se šahovski računalni programi nastavili razvijati. 1980-tih je njihov razvoj postao i ozbiljno natjecanje. Edward Fredkin, profesor računalne znanosti u sveučilištu Carnegie Mellon je osnovao tzv. Fredkinovu nagradu i ponudio značajne novčane nagrade za sve koji uspiju ostvariti vrhunska postignuća u svijetu programiranja šahovskih računalnih programa (5000 $ za prvo računalo koje dosegne majstorski nivo, 10000 $ za prvo računalo koje dosegne nivo velemajstora, 100 000 $ za prvo računalo koje pobijedi svjetskog prvaka).

Utrka je započela. Broj i snaga šahovskih računalnih programa su nastavili rasti.

Fredkinove kolege sa sveučilišta su bili na čelu kolone. Najpoznatiji projekt i perjanica cijele generacije je bio Deep Thought – prvo šahovski računalni program koji je dosegao nivo velemajstora. 1988. godine, Deep Thought je podijelio prvo mjesto na US Open-u s velemajstorom Tony-jem Miles-om. Sljedeće godine je s lakoćom pobijedio ranije spomenutog međunarodnog majstora David-a Levy-a rezultatom 4:0.

Pad čovječanstva se činio neizbježnim. U potrazi za herojem, šahovski svijet se okrenuo svjetskom prvaku i možda i najvećem igraču svih vremena – Garryu Kasparovu, koji je to povjerenje opravdao.

Naime, Garry je prvo 1985. godine u legendarnoj simultanki igrao protiv 32 (!) najjača šahovska računalna programa toga doba – i sve ih pobijedio! Zatim je 1989. godine dobio meč protiv Deep Thought-a rezultatom 2:0.

Moglo bi se reći da je tijekom svojih dvoboja protiv „mašina“ u 80-tima, Garry izborio status „Izabranog“.
Nažalost, 1990-te su dovele i do njegovog pada.

1990-1997: Računala počinju preuzimati

1989. godine, čovječanstvo je dobilo bitku, ali ne i rat. 1990-tih je odigrano nekoliko mečeva naslovljenih „čovjek protiv mašine“. Najboljim šahovskim računalnim programima je čak dopušteno natjecanje u elitnim turnirima. Vrhunac je bio poznati meč 1997. godine u kojem je šahovski računalni program po prvi puta porazio svjetskog prvaka.

1989. godine, IBM je preuzeo tim koji je razvijao Deep Thought, te se odmah pristupilo razvoju boljeg, još moćnijeg šahovskog računalnog programa, koji je nazvan Deep Blue.

1996., samo 7 godina nakon poraza Deep Thought-a od Kasparova, dogovoren je novi meč: Kasparova protiv Deep Blue-a. Prva partija je šokirala cijeli svijet – Deep Blue je postao prvi šahovski računalni program koji je porazio svjetskog prvaka. Kasparov se, doduše, uspio pribrati i okrenuti meč u svoju korist, te konačnim rezultatom 4:2 produljiti nade čovječanstva.

Poraz nije obeshrabrio programere Deep Blue-a, koji su nastavili svoj rad i zaposlili velemajstora Joela Benjamina kao konzultanta, čiji je zadatak bio izgraditi pouzdanu knjigu varijanti otvaranja. Nedugo nakon prvog meča, tim je izazvao Kasparova na uzvrat – i kako kažu – ostalo je povijest.

U slavnom meču, Kasparov je dobio prvu partiju. Usprkos tome, neobičan 44-ti potez računala mu je uzdrmao samopouzdanje. U drugoj partiji je Deep Blue izjednačio nakon što je Kasparov nepreciznom igrom propustio izjednačiti i remizirati. Nakon tri remija, u šestoj partiji je svjetski prvak igrao riskantnu varijantu Caro-Kanna. U kritičnom momentu u otvaranju – na osmom potezu – Deep Blue je žrtvovao konja za pješaka i ostvario enormnu kompenzaciju. Nakon samo 19 poteza, Kasparov je morao položiti oružje i omogućiti programerima Deep Bluea da osvoje Fredkinovu nagradu.

Nakon meča, Kasparov je optužio IBM za varanje. Tvrdio je da je poteze Deep Blue-a zapravo vukao čovjek (Joel Benjamin). Neki su tvrdili da je Deep Blue dobio meč zahvaljujući pogrešci u kodu zbog koje se odlučio na spomenutu žrtvu figure (Kasparov je smatrao da Deep Blue nije sposoban odigrati takve „intuitivne“ poteze).

U svakom slučaju, 1997. se simbolično smatra krajem ljudske dominacije nad šahovskim računalnim programima.
Međutim, čovječanstvo se nije još u potpunosti predalo.

1997-2006: Čovječanstvo uzvraća udarac

Nakon pobjede Deep Blue-a, svi su očekivali da će se razlika u snazi između ljudi i šahovskih računalnih programa nastaviti povećavati. Ipak, tijekom idućih 6 godina, ljudi su uspješno pružali otpor.

Primjerice, 2000. je šahovski računalni program Deep Junior sudjelovao u tradicionalnom elitnom turniru u Dortmundu – i ostvario rezultat od samo 50%. 2002., novi svjetski prvak Vladimir Kramnik je remizirao meč protiv šahovskog računalnog programa Deep Fritz-a (usprkos tome što je previdio mat u potezu). 2003. je Garry Kasparov remizirao mečeve protiv Deep Junior-a7 i X3d Firtz-a.

Nažalost, ovaj mali tračak nade je brzo ugušio šahovski računalni program Hydra, koji je 2004. pobijedio velemajstore Evgeny-a Vladimirov-a (3:1) i Ruslan-a Ponomariov-a (2:0). Zatim je u 2005-toj uništio Michael-a Adams-a – igrača iz prvih 10 na svijet – katastrofalnim rezultatom od 5.5:5.

Konačno, u 2006-toj je Deep Fritz zabio posljednji čavao u lijes čovječanstva pobjedom nad Vladimirom Kramnikom 4:2.

2006-2017: Zlatno doba šahovskih računalnih programa

Desetljeće između 2006. i 2017. se s pravom može smatrati zlatnim dobom šahovskih računalnih programa.
Ljudi su ih počeli koristiti na svakodnevnoj bazi. Bilo da je riječ o analiziranju ili igranju, postali su svakidašnji alat bilo kojeg ozbiljnijeg šahista. Njihova dostupnost je dovela do pojave nove generacije mladih talenata – tzv. kompjuterske generacije. Nakon pojave pametnih telefona, pojavile su se i Androdi i iOS inačice šahovskih računalnih programa, na sveopći užas svih protivnika varanja na šahovskim turnirima.

Svjetsko prvenstvo šahovskih računalnih programa je nastavilo rasti. Velika količina novca je i tu uzrokovala neetične radnje. Najpoznatiji primjer je diskvalifikacija šahovskog računalnog programa – četverostrukog uzastopnog prvaka u periodu između 2007. i 2010. godine – jer je programer optužen za plagiranje velikog dijela koda.

Osim standardnog svjetskog prvenstva, 2010. je osnovano i novo natjecanje – Natjecanje vrhunskih šahovskih računalnih programa (eng. TCEC – Top Chess Engines Competition).

Razlika između šahovskih računalnih programa i ljudi su pokazali da je razlika prevelika. Tijekom desetljeća organizirani su mečevi u kojem su programi davali različite „fore“ jakim velemajstorima. Rezultati su bili porazni za čovječanstvo.

Primjerice, 2014. šahovski računalni program Stockfish je pobijedio velemajstora Daniel-a Naroditsky-ja, koji se tijekom igre služio ranom verzijom Rybke. 2015-te je šahovski računalni program Komodo igrao 6 partija s forom protiv Sergeija Movsesiana (bivšeg člana svjetskog top 10) i uvjerljivo ga nadigrao. 2016-te je i Hikaru Nakamura – jedan od najbolji šahista svijeta – poražen u meču sličnog formata.

U svakom slučaju, klasični šahovski računalni programi su dominirali u periodu između 2006-te i 2017-te. Njihova snaga se nastavila povećavati kontinuirano, ali sporo. Mislilo se da su svi algoritmi već otkriveni i gotovo nitko nije očekivao neke brze i radikalne promjene.

A onda se dogodio AlphaZero.

2017-nadalje: Nova revolucija?

5. prosinca 2017., grupa stručnjaka za umjetnu inteligenciju iz kompanije Deep Mind u vlasništvu Google su uzdrmali šahovski svijet do temelja.

Oni su u svojem znanstvenom članku, naslovljenom „Savladavanje šaha i shogi-ja igranjem protiv samoga sebe pomoću općeg algoritma za strojno učenje“ , opisali razvoj šahovskog računalnog programa AlphaZero-a, baziranog na potpuno novom pristupu. Umjesto alpha-beta pretraga i linearne aproksimacijske funkcije korištene u standardnim šahovskim računalnim programima, AlphaZero je zasnovan na korištenju nelinearne aproksimacijske funkcije bazirane na dubokim neuralnim mrežama i Monte Carlo simulacijama.

Jednostavno rečeno, umjesto „duboke“ analize pozicije, AlphaZero je sposoban „samostalno“ naučiti šah iterativnim igranjem protiv samoga sebe.

Snaga AlphaZeroa je testirana pomoću meča od 100 partija protiv najjačeg dostupnog šahovskog računalnog programa – Stockfisha 8. Rezultat je bio zapanjujuć – 28 pobjeda, 0 poraza i 72 remija u korist AlphaZero-a.

Osim samog rezultata, još je impresivnija bila njegova igra jer je bila puno intuitivnija i sličnija ljudskoj od igre tradicionalnih šahovskih računalnih programa.

Članak je izazvao različite reakcije. Mnogi šahisti su bili osupnuti – kako je moguće da moćni Stockfish doživi takav poraz? S druge strane, mnogi su bili izrazito skeptični. Dosta je kritika upućeno na uvjete u kojima je meč održavan – Stockfish je pogonjen na slabijem hardveru i igrao je bez knjige otvaranja.

Međutim, 7. prosinca 2018., tim iz Deep Mind-a je objavio novi članak, pod naslovom: „ Opći algoritam za strojno učenje za savladavanje šaha, shogi-ja i go-a pomoću igranja protiv samoga sebe“ , u kojem su predstavili rezultate novog meča između AlphaZer-a i Stockfisha. Od 1000 partija, AlphaZero je dobio 155 i izgubio samo 6. Iako je korištena starija verzija Stockfish-a, to je nevjerojatan rezultat.

Neovisno o tome je li skepticizam opravdan ili ne, ne može se poreći da je AlphaZero izvršio ogroman utjecaj na šahovski svijet. Nedugo nakon objave članaka, grupa entuzijasta iz cijeloga svijeta je počela razvijati sličan šahovski računalni program LeelaZero, baziran na istom algoritmu.

U svakom slučaju jedno je sigurno: dolaskom umjetne inteligencije, svijet šahovskih računalnih programa više nikada neće biti isti.

Poveznice iz članka:

1. Claude Shannon
2. Glavni izvor koji opisuje odnos Shannona i Turinga
3. Did Deep Blue Beat Kasparov Because of a System Glitch?
4. Rybka, the world’s best chess engine, outlawed and disqualified
5. Man vs Machine Historical Archive‎
6. Komodo Beats Nakamura In Final Battle
7. Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm
8. Is AlphaZero really a scientific breakthrough in AI?

Reference i izvori: 

• Kasparov and thirty years of computer chess
• Deep Blue Inventors Win Fredkin Prize for Computer Chess
• A Brief History of Computer Chess
• Early Computer Chess Programs by Bill Wall