Razvoj šahovskih računalniških programov od mehanskih do aktualnih.

Kratka zgodovina Prvi šahovski stroj thumb|right|240px|Prvi »šahovski stroj« Leta 1769 je madžarski inženir baron Wolfgang von Kempelen skonstruiral šahovski stroj za zabavo avstrijske kraljice Marije Terezije. Stroj je bil mehanski, v njem se je skrival človek vešč šaha, ki je preko vzvodov premikal lutko Turka in tako premikal figure. »Stroj« je bil velika atrakcija, s katerim so igrale mnoge znane osebnosti tistega časa, med drugim tudi Napoleon Bonaparte, ki je bojda enkrat vlekel nemogoče poteze in tako razjezil »stroj«, da je zamahnil in podrl figure. Prisotni so ostrmeli, lasnik stroja pa se je v zadregi začel zgovarjati na zlomljen vzvod. Napoleon pa se je na olajšanje prisotnih nasmejal. Šahovski stroj je menjal lastnike, vendar pa je njegova skrivnost s skritim šahistom dolgo ostala neodkrita.

Ob 200 letnici smrti Wolfganga von Kempelena, (2004), so v nemškem muzeju Heinz Nixdorf, Paderborn izdelali natančno in delujočo repliko prvega šahovskega stroja.

Torres y Quevedov »Šahist«

Prvi šahovski stroj z vgrajenim algoritmom za »računanje« potez ni bil neki digitalni računalnik, pač pa mehanski stroj z imenom »El Ajedrecista«, ki ga je leta 1912 izumil španski izumitelj Torres y Quevedo. Naprava je bila omejena na igranje končnice s kraljem in trdnjavo proti kralju. Za današnjo digitalno dobo to ni neki dosežek, vendar je bilo to takrat nekaj izjemnega. »Šahist« je s pomočjo elektromagnetov popolnoma avtomatsko premikal tri šahovske figure ne glede na začetno postavitev in tako matiral kralja. Res, da ne na najbolj optimalen način, pa vendar veljajo danes prispevki Torresa y Queveda za pomemben zgodovinski mejnik umetne inteligence.

Quevedo je leta 1920 izdelal izboljšano različico »Šahista« z elektromagneti pod šahovnico. Oba stroja sta še danes delujoča in se nahajata v madridskem muzeju.

Turingov »papirni stroj«

Fascinantno je, da je bil prvi šahovski program napisan preden je bil izumljen računalnik. Napisal ga je vizionar in matematik, Alan Turing, ki se je zavedal, da so na pohodu stroji, ki se jih bo dalo programirati in bodo sposobni igranja šaha. Turing se je zelo zanimal za šah, vendar je bil kljub izjemnemu intelektu in analiziranju šaha povprečen šahist. Kmalu po drugi svetovni vojni je napisal navodila za še neizumljen stroj po katerih naj bi igral šah. Stroja za katerega je napisal program še ni bilo, zato je njegovo procesorsko moč nadomeščal kar sam. Za izračun ene poteze je potreboval več kot pol ure.

Shannonove strategije

Nekako vzporedno s Turingom je prav tako velik matematik Claude Elwood Shannon razmišljal o učenju računalnika igranja šaha. Ugotovil je, da bo problem izredno veliko število izračunov. Zato je ločil strategijo A v kateri je pregledoval vsa nadaljevanja in strategijo B v kateri je selektivno izločil določena nadaljevanja. Na ta način tudi danes ločimo šahovske programe, čeprav najmočnejši programi bolj ali manj spadajo v prvo skupino.

Šah namesto atomske bombe

Med drugo svetovno vojno so v ZDA zgradili ogromen laboratorij, katerega namen je bil izgradnja atomskega orožja. Za doseganje pravilne oblike implozijskih nabojev, kateri sprožijo verižno reakcijo je potrebno veliko število izračunov. Leta 1946 je bila dodeljena naloga madžarsko-ameriškemu matematiku Johnu von Neumannu, da skonstruira računski stroj, ki bo pospešil zadano nalogo. Leta 1950 je bil nared gromozanski računalnik imenovan MANIAC. Vseboval je tisoče vakuumskih elektronk in stikal. Zmožen je bil izračunati 10.000 operacij na sekundo in dalo se ga je programirati.

Vendar pa znanstveniki niso takoj začeli z atomskimi izračuni, pač pa je bila ena prvih stvari katero so sprogramirali - igranje šaha. Šahovnica je bila velikosti 6 × 6 polj in na njej ni bilo lovcev. Stroj je potreboval dvanajst minut za potezo pri globini štirih polpotez (z lovci bi potreboval tri ure).

Sredi pedesetih let je program odigral tri partije. Prvo sam s seboj (beli je zmagal), drugo je odigral z močnim šahistom in zgubil. Partija je trajala deset ur. Tretjo pa je odigral z mlado damo, ki se je pravil naučila teden dni prej. Program je zmagal v 23 potezah. To je bilo tudi prvič, da je človeka premagal računalnik v intelektualni sposobnosti.

Šah in matematika

Glavni problem pri šahovskem programiranju je veliko število izračunov. V povprečni razporeditvi je približno 40 dovoljenih potez. Pri odgovoru na vsako od teh potez dobimo 40 × 40 = 1600 razporeditev. To pomeni, da po vsaki drugi polpotezi, ki velja za eno potezo v šahu, število razporeditev naraste za 1600. Po dveh potezah je število že 2,5 milijona in po treh 4,1 milijarde. Povprečna šahovska igra traja 40 potez. To pomeni 10128 razporeditev, kar je več kot je atomov v nam znanem Vesolju (skromnih 1080). Jasno je, da noben računalnik ali kakšna druga naprava ne more rešiti problema šahovske igre z izračunavanjem vseh možnih razporeditev. Vendar je tudi človeški um nepopoln in je samo vprašanje iskanja globine, ki je potrebno za izenačitev s človeško taktično sposobnostjo. Zgodnji računalniki so bili sposobni izračunati približno 500 razporeditev na sekundo ali 90.000 v treh minutah, ki so na voljo v turnirski igri. To pomeni, da so lako izračunali samo tri polpoteze (eno in pol potezo) globoko. To je vodilo k zelo skromnim rezultatom - nivoju začetnika. Za izračun ene polpoteze globlje je potrebno 15.000 razporeditev na sekundo. Vendar je tudi štiri polpotezna globina zelo plitka. Takrat se je zdelo, da računalniki nikoli ne bodo igrali šaha na mojsterskem nivoju.

Alfa-beta

Prvi preboj se je zgodil leta 1958, ko so trije znanstveniki z Univerze Carnegie-Mellon (Newell, Shaw in Simon) prišli do pomembnega odkritja. Ugotovili so, da se da izogniti velikemu številu izračunov, ne da bi to vplivalo na končni rezultat. To so imenovali algoritem alfa-beta. Potrebno je poudariti, da gre pri tem algoritmu za čisto matematično tehniko, ki deluje brez uporabe kakršnegakoli dodatnega šahovskega znanja.

To je zelo grob opis kako algoritem alfa-beta deluje: recimo, da je program končal z vrednotenjem poteze in začel z drugo. Kakor hitro nasledji izračun pokaže nižjo vrednost od prejšnje poteze program prekine računanje le-te. Ni pomembno koliko je poteza slabša, program se bo vedno odločil za potezo z največjo vrednostjo.

Algoritem alfa-beta doseže enak rezultat, kot iskanje vseh možnih potez s tem, da je potrebno preiskati le približno kvadratni koren potez, ki so drugače potrebne za uspešen rezultat. Tako so lahko tedanji računalniki kar naenkrat izračunavali pet in šest polpotez naprej. V sedemdesetih letih so najhitrejši računalniki (npr. CDC Cyber series) izračunavali sedem polpotez naprej in so dosegali dobre šahovske rezultate. Vendar je potrebno tudi z algoritmom alfa-beta petkratno povečanje hitrosti za dodatno polpotezo globine. Eksponentna eksplozija je spet ujela programerje.

Računalnik Belle

Kenneth Thompson, računalniški znanstvenik in programer ni mogel čakati na superračunalnik vreden milijon dolarjev, da bi dosegel pet oziroma dvajsetkrat hitrejše rezultate in tako izboljšal računalniško šahovsko igro. S svojimi kolegi iz Bellovih laboratorijev se je odločil razviti namenski računalnik sestavljen iz več tisoč čipov vrednih 20.000 dolarjev. Računalnik so imenovali »Belle«, in bil je sposoben igranja šaha. Računal je lahko približno 180.000 razporeditev na sekundo (superračunalniki v tistem času so dosegali 5000 razporeditev na sekundo). Belle je lahko računal osem do devet polpotez naprej v turnirskih igrah, kar je omogočalo igranje na mojsterskem nivoju. Zmagal je na svetovnem računalniškem šahovskem tekmovanju in vseh drugih računalniških turnirjih od leta 1980 do 1983, ko ga je izrinil velikanski superračunalnik Cray X-MPs vreden dvajsetkrat več.

Šahovski čipi

Sredi osemdesetih let je profesor Hans Jack Berliner zapolnil vrzel, ki jo je Kenneth Thompson pustil odprto. Berliner, ki je bil med drugim tudi svetovni prvak v dopisnem šahu, je sestavil hardverski šahovski računalnik imenovan »HiTech«. S svojim študentom Carl Ebelingom sta izdelala hardverski čip – generator premikov. S 64 vzporednimi čipi je »HiTech« za malenkost zgrešil zmago na svetovnem računalniškem šahovskem prvenstvu leta 1986 in tako prepustil zmago superračunalniku Crayu.

Kmalu zatem so Berlinerjevi študentje Feng-hsiung Hsu, Murray Campbell in ostali sami razvili nov računalnik imenovan »ChipTest« in kasneje »Deep Thought«. Stal je približno 5000 dolarjev in je lahko izračunaval 500.000 razporeditev na sekundo. Hsu in Campbell sta se posledično razšla s svojim učiteljem in se pridružila podjetju IBM. Skupaj z Joejem Hoaneom so razvili sedanji računalnik »Deep Blue«.

Deep Blue

Računalnik s katerim je leta 1997 svetovni šahovski prvak Gari Kasparov izgubil z rezultatom 2,4 : 3,5. Leto prej 1996 je Kasparov zmagal z rezultatom 4 : 2. »Deep Blue« je imel vgrajen server IBM SP/2 z ogromnim številom namenskih čipov, ki so omogočali hitre izračune. Vsak čip je bil sposoben računanja dva do tri milijone razporeditev na sekundo. Z uporabo več kot 200 takih čipov je bil program sposoben izračunati 200 milijonov razporeditev na sekundo.

Globina iskanja in igralna moč

Kaj pove hitrost 200 milijonov razporeditev na sekundo šahovskega računalnika? Kenneth Thompson je v osemdesetih letih izvedel nekaj zanimivih poizkusov med povezavo igralne moči in iskanjem potez v globino.

Thompson je igral z računalnikom »Belle« tako, da je postopoma povečeval globino iskanja potez. Ugotovil je, da se igralna moč poveča za 200 točk ELO ob povečanju iskanja globine za pol poteze. Pri globini štirih polpotez je »Belle« igral z močjo približno 1230 točk ELO, pri globini devetih polpotez pa je dosegal že približno 2328 točk ELO.

Zaključek strokovnjakov: Za izenačenje šahovske moči s človeškim svetovnim šahovskim prvakom je potreben računalnik, ki bo sposoben izračunati milijardo potez na sekundo (in iskanja 14 polpotez v globino). »Deep Blue« je blizu, vendar še vedno ne dovolj.

Osebni računalniki

Seveda je pomembna tudi kakovost programiranja pri igralni moči. Današnji najboljši programi za osebne računalnike kot sta »Fritz« in »Junior« npr., sta sposobna izračuna 500.000 in več razporeditev na sekundo. Stvarno taki programi igrajo z močjo 2600 točk ELO. Kljubuje jim lahko le 100 najboljših šahovskih igralcev na svetu. V pospešenem šahu so jim kos le nekateri, v pet minutni igri pa »preživita« verjetno le dva ali trije na svetu.

Spopad na obeh frontah

Pomembno vlogo v moči računalnikov igra dodatna knjižnica otvoritev. Zbrano znanje in izkušnje več generacij človeških šahovskih velemojstrov je enostavno shraniti na trdi disk in tako dostopati do nje v otvoritveni fazi šahovske igre. Programi za osebne računalnike poznajo desetine milijonov otvoritvenih razporeditev in imajo dostop do statistik za vsako od njih (katere poteze so bile premaknjene. s kakšnim uspehom, kakšen igralec je potezo izvedel itd). Pogosto bo program odigral petnajst ali dvajset potez preden začne izračunavati razporeditev. Brez te knjižnice s človeškim znanjem bi bili programi občutno slabši.

Medtem, ko računalniki izkoriščajo prednost v nakopičenem znanju otvoritev na eni strani, prav tako izkoriščajo prednost z druge strani šahovske igre.

Knjižnica šahovskih končnic