Od mehaničnega Turka do digitalnega velemojstra

Razvoj računalniškega šaha ima zanimivo in pestro zgodovino, tesno prepleteno z razvojem računalništva. Bil je vzpodbuda za raziskovalce in inženirje, pa tudi nekakšno merilo za zmogljivost računalnika za vse tiste, ki jim megaherci in gigaflopi niso veliko pomenili. Čim bolje je znal računalnik igrati šah, tem zmogljivejši je bil.

Zamisel o stroju, ki bi znal igrati šah, je precej starejša od računalnikov in je domišljijo izumiteljev burila že v osemnajstem stoletju. Tehnologija takrat seveda še zdaleč ni bila tako razvita, da bi lahko o pravem računalniškem avtomatu sploh resno razmišljali, zato si je madžarski baron Wolfgang von Kempelen pomagal z zvijačo.

Mehanični Turek

V Bratislavi je von Kempelen leta 1770 sestavil mehaničnega šahista in ga predstavil na dvoru cesarice Marije Terezije. V mizi, za katero je sedela v oblačila turškega plemenitaša oblečena mehanska lutka, je bil zapleten mehanizem s številnimi vzvodi, zobatimi kolesci in vzmetmi - "pamet" avtomata.

Mehanični Turek seveda ni znal igrati šaha, in von Kempelen tega pravzaprav ni nikoli trdil. Večina izobraženih sodobnikov je vedela, da gre le za imenitno cirkuško ukano, pa čeprav niso vedeli, kako v resnici deluje, ne tako malo pa je bilo vedno tudi lahkovernežev, ki so bili prepričani, da mehanični Turek res zna šahirati.

Von Kempelen je uporabil podobno ukano kot čarodeji, ki v skrinji prežagajo lepo pomočnico. Kljub temu da so pred vsako predstavo mizo odprli in pokazali, da je v njej le zapleten mehanizem, je bil notri skrit spreten šahist, ki je z vzvodi premikal Turkovo roko in premagoval znane osebnosti tistega časa.

Mehanični Turek je gostoval po dvorih in meščanskih salonih od Petrograda do Pariza in vsepovsod zbujal veliko pozornost. Na gostovanju v Parizu je na primer premagal ameriškega izumitelja in politika Benjamina Franklina, leta 1809 na Dunaju pa tudi Napoleona Bonaparteja. Mehanični Turek je na koncu pristal v philadelphijskem muzeju v Združenih državah in tam leta 1854 v velikem požaru zgorel.

V drugi polovici devetnajstega stoletja so naredili še nekaj podobnih mehanskih šahistov, najbolj znana pa sta bila Ajeeb ali Arabec (naredili so ga leta 1868) in Mefisto (1878). Ob 200-letnici von Kempelenove smrti so leta 2004 v nemškem muzeju Heinz Nixdorf v Paderbornu naredili delujočo repliko mehaničnega Turka (www.hnf.de/Schachtuerke/).

Leta 1820 se je z mehaničnim Turkom pomeril tudi Charles Babbage in prav njegov na videz delujoči mehanizem naj bi ga pripeljal do zamisli, da bi bilo mogoče narediti računalnik. In to ne samo za računanje, kajti njegov analitični stroj, mehanski računalnik na parni pogon, naj bi znal igrati tudi šah.

Mehanični Turek šaha ni znal igrati, analitični stroj pa tudi ni bil nikoli narejen in na prvi pravi šahovski avtomat, ki je deloval brez človeške pomoči, je bilo treba počakati do začetka 20. stoletja.

Mehanični Turek

Takole je videti mehanični Turek v šahovskem programu Fritz Chess 9.

Elektromehanski šahist

Prvi delujoči šahovski avtomat je leta 1912 izdelal španski matematik, inženir in izumitelj Leonard Torres Quevedo. El Ajedrecista (šahist), kakor ga je poimenoval, je prvič javno predstavil leta 1914 na svetovni razstavi v Parizu. S takratno tehnologijo seveda še ni bilo mogoče narediti pravega šahovskega "računalnika", temveč le zelo poenostavljeno različico. El Ajedrecista je namreč znal igrati le šahovske končnice s kraljem in trdnjavo proti človeku, ki mu je na šahovnici ostal samo še kralj.

Včasih je Šahist sicer porabil več potez, kot bi bilo nujno potrebno, a človeškega nasprotnika je vendar vedno matiral. Opazil je tudi, če je nasprotnik poskušal goljufati in je svojega kralja premaknil na napačno polje. Vgrajeno je imel celo gramofonsko ploščo in je na koncu napovedal mat.

Elektromehanski šahist je bil, podobno kakor stoletje prej Turek, vsepovsod, kjer je nastopal, deležen velikega občudovanja, kajti ne pozabimo, da se je to dogajalo v časih, ko po domovih še niti radijskih sprejemnikov niso imeli. Leta 1920 so naredili tudi izboljšano različico, ki je namesto z elektromehansko roko figure premikala z elektromagneti pod šahovnico. Oba Šahista delujeta še danes in ju je mogoče videti v madridskem muzeju združenja gradbenikov Colegio de Ingenieros de Caminos, Canales y Puertos.

Mehanizem El Ajedrecista (Foto Mark Sussman)

Teoretična otvoritev

Kmalu po drugi svetovni vojni se je genialni angleški matematik Alan Turing začel ukvarjati z umetno inteligenco in mimogrede leta 1947 napisal teoretične osnove za računalniški šah ter prvi šahovski program, za katerega pa sploh ni imel računalnika, saj tisti prvi primerki računalnikov še niso bili dovolj zmogljivi. Program je deloval le teoretično, v edini ohranjeni "papirnati" partiji pa je Turingov sodelavec potreboval kar 29 potez za zmago.

Še preden je prvi računalnik naredil prvo potezo, je oče informacijske teorije, ameriški matematik Claude E. Shannon, v članku Programiranje računalnikov za igranje šaha med drugim ugotovil, da poznamo dve osnovni strategiji računalniškega šaha. Pri strategiji A računalnik oziroma program pregleda vse mogoče poteze do določene globine in nato izbere najboljšo, pri strategiji B pa program sproti ocenjuje posamezne poteze in obetavnejše pregleda globlje.

Turing za prikaz umetne pameti šaha ni izbral naključno. Ljudje ga namreč dojemamo kot igro, za katero je potreben razum. Sicer tudi za matematiko potrebujemo razum, vendar je bilo za računanje že veliko prej vsakomur jasno, da je le izvajanje vnaprej določenih postopkov. Nič takega torej, česar ne bi zmogli tudi stroji.

Alan Turing je seveda dobro vedel, da tudi šah pravzaprav ni nič drugega kot nekakšna zelo zapletena matematična formula in da torej ni nobenega teoretičnega zadržka, da mu računalniki ne bi bili kos. Še več, leta 1950 je v članku Računski stroji in pamet (Computing Machines and Intelligence) postavil hipotezo, da je mogoče človeški razum oziroma delovanje možganov matematično opisati. Da skratka ni samo šah zapletena matematična formula, temveč je to pravzaprav vsako razmišljanje in da zaradi tega ni nobene teoretične ovire, da ga ne bi zmogel dovolj napreden računalnik. V istem članku je opisal tudi postopek za prepoznavanje pametnega stroja, ki se ga je pozneje oprijela oznaka Turingov preizkus - računalniku in človeku postavljamo poljubna vprašanja in če na podlagi odgovorov ne moremo prepoznati računalnika, je ta očitno razumen.

S hipotezo o matematični naravi razuma se sicer marsikdo ne strinja in zaenkrat še ni povsem zanesljivo, ali bo mogoče kdaj resnično narediti računalnik ali, pravilneje rečeno, računalniški program, ki bo prestal Turingov preizkus, povsem jasno pa je, da njegovo šahovsko različico že dolgo opravi vsak spodobnejši šahovski program. Toda zdaj se malce prehitevamo.

Angleški matematik Alan Turing je postavil teoretične osnove računalniškega šaha in napisal prvi program.

Prve poteze

Teorija, vsaj osnovna, je bila v začetku petdesetih let prejšnjega stoletja torej znana, veliki računalniki pa so tudi že postajali dovolj zmogljivi za prve pionirske poteze. Leta 1951 je Dietrich Prinz, raziskovalec na univerzi Manchester v Veliki Britaniji, za računalnik Ferranti Mark 1 napisal program, ki sicer še ni znal igrati šaha, je pa znal reševati šahovske probleme, ki jim pravimo mat v dveh potezah. Za rešitev, ki jo sodobni programi na osebnih računalnikih najdejo v delčku sekunde, je potreboval približno četrt ure. Mimogrede, na istem računalniku so naslednje leto napisali prvi program za igranje dame.

Leta 1956 so z računalnikom MANIAC I v ameriškem Los Alamosu na šahovnici s 6 x 6 polji že igrali nekakšen poenostavljen šah brez lovcev, naslednje leto pa je IBMov računalnik 704 že igral čisto pravi šah. Počasi in začetniško, a vendarle.

Pomemben napredek so dosegli leta 1958, ko sta raziskovalca na univerzi Carnegie Mellon, Allan Newell in Herbert Simon, s Cliffom Shawom iz Rand Corporation odkrila tako imenovano klestenje alfa-beta, s katerim lahko, če vse skupaj zelo poenostavimo, hitro izločimo neobetavne poteze in omogočimo programu, da v enakem času pregleda precej več potez.

Skupaj so za IBMov računalnik 704 naredili program NSS, ki ga je doletela čast, da je bil prvi, ki mu je uspelo premagati človeka, pa čeprav le tajnico, ki so jo naučili igrati šah uro pred partijo z računalnikom. Navdušenje nad zmagoslavjem tehnologije je bilo v tistem času veliko in marsikdo je bil prepričan, da bo v desetih ali petnajstih letih računalnik postal svetovni šahovski prvak.

Maniac je znal igrati samo poenostavljen šah na manjši šahovnici in brez lovcev.

Pionirja računalniškega šaha, Allan Newell (desno) in Herbert Simon (Foto Carnegie Mellon University)

Prve računalniške zmage

V šestdesetih letih prejšnjega stoletja je bil razvoj računalništva hiter, vzporedno pa so razvijali tudi čedalje zmogljivejše šahovske programe. Leta 1962 je Alan Kotok s pomočjo mentorja Johna McCarthyja za diplomsko nalogo na univerzi MIT napisal prvi šahovski program, za katerega ni bilo več mogoče reči, da igra začetniški šah. Deloval je na IBMu 7090 in na sekundo pregledal 1100 položajev.

Z razvojem šahovskih programov so se v tistem času ukvarjali tudi v Sovjetski zvezi, predvsem na moskovskem Inštitutu za teoretično in eksperimentalno fiziko. Novembra 1966 se je začel dopisni šahovski dvoboj med ruskim programom in tistim, ki sta ga na MITu razvijala Kotok in McCarthy. Dvoboj je trajal devet mesecev, s tremi zmagami in enim porazom pa ga je dobil sovjetski program.

John McCarthy, eden od pionirjev računalniškega šaha, med partijo z računalnikom IBM 7090 leta 1967 (Foto Standford University)

Iz tistega časa je tudi prvi računalniški nastop na "človeškem" šahovskem turnirju. Na amaterskem prvenstvu ameriške zvezne države Massachussets je leta 1966 sodeloval DECov računalnik PDP-6 s programom MacHACK VI in doživel štiri poraze, enkrat pa mu je uspelo remizirati. A že naslednje leto je istemu programu na državnem prvenstvu Massachussetsa uspelo prvič na resnem turnirju premagati šahista. Sicer le malo boljšega ljubitelja, a to je bilo za marsikoga potrdilo, da se bodo napovedi o prevladi računalnikov kmalu uresničile.

Leta 1967 je MacHACK VI igral še na štirih turnirjih in dosegel tri zmage, tri remije in 12 porazov, ameriška šahovska zveza pa ga je razglasila za častnega člana. MacHACK je bil prvi program v splošni rabi, saj je deloval na računalnikih PDP, ki so takrat prevladovali na ameriških univerzah, bil pa je tudi prvi, ki je imel vgrajeno knjižnico z otvoritvami.

Leta 1970 so v New Yorku organizirali prvi računalniški šahovski turnir. Sodelovalo je šest programov, zmagal pa je Chess 3.0. Prvo svetovno prvenstvo šahovskih programov je bilo leta 1974 v Stockholmu, prepričljivo, s štirimi zmagami in brez poraza, ga je osvojil sovjetski program KAISSA in potrdil, da so imeli v tistem času na drugi strani železne zavese boljše šahovske programe, žal pa o njih še danes vemo le malo.

Dobljena stava

V drugi polovici šestdesetih let je marsikdo napovedoval skorajšnjo prevlado šahovskih programov, mednarodni šahovski mojster David Levy pa je leta 1968 na delavnici o strojni inteligenci na univerzi v Edinburghu za 3000 dolarjev stavil, da ga še deset let ne bo premagal noben računalnik. Stavo je dobil leta 1978, ko je v Torontu s tremi zmagami in enim remijem premagal takrat najmočnejši šahovski program Chess 4.7.

Šahovski računalniki

Šahovski programi so sprva delovali samo na velikih in dragih računalnikih, ker manjših pač ni bilo. Zaradi tega so bili dosegljivi samo programerjem in raziskovalcem na inštitutih in univerzah ter študentom, ki jim je uspelo izboriti si čas za delo s tem ali onim računalnikom. Prvi poskus približanja računalniškega šaha povprečnemu ljubitelju je bil mali šahovski računalnik, Chess Challenger, ki so ga v Fidelity Electronics, podjetju, ki se je sicer ukvarjalo s slušnimi aparati, začeli izdelovati leta 1977.

Mali šahovski računalniki so kmalu postali zelo priljubljeni in prvemu so sledili še številni drugi modeli. Najcenejši in najmanjši sploh niso imeli šahovnice, temveč samo majhen prikazovalnik, na katerem je igralec odčital potezo računalnika, in majhno tipkovnico, na katero je odtipkal svojo.

Chess Challenger je računalniški šah približal ljubiteljskim šahistom.

Chess Challenger 7 iz leta 1979 (Foto Computer History Museum)

Majhen prenosni šahovski računalnik Mephisto II iz leta 1981

Hkrati s prvim malim šahovskim računalnikom so naredili tudi prvi šahovski superračunalnik. Leta 1977 je namreč Kenneth Thompson, v računalniških krogih bolj znan kot eden od očetov Unixa in avtor Bja, predhodnika programskega jezika C, iz 1700 procesorjev sestavil 20.000 dolarjev vredni računalnik Belle. Šahovska lepotica je ime dobila po Bellovih laboratorijih, v katerih je nastala. Šahovski superračunalnik je lahko v eni sekundi pregledal kar 160.000 položajev (to je bilo od dvajsetkrat do tridesetkrat hitreje od tedanjih superračunalnikov) oziroma do 7 polpotez v globino in bil v drugi polovici sedemdesetih let najmočnejši šahovski računalnik.

Ken Thompson je bil tudi prvi, ki je šahovski program opremil s knjižnicami končnic. Tako opremljen program, če se mu uspe prebiti do končnice, ne more več izgubiti, seveda če je zmaga vsaj teoretično mogoča. Pa tudi če ni, se opremljen s takšno knjižnico v dolgih končnicah lahko zanaša na nasprotnikovo napako.

Leta 1982 so Belle na poti na šahovski turnir v Sovjetski zvezi začasno zasegli, ker naj bi šlo za nezakonit izvod strateško pomembne tehnologije, še istega leta pa je na ameriškem odprtem prvenstvu v hitropoteznem šahu dosegel drugo mesto (v človeški konkurenci, da ne bo pomote). Leta 1983 je Belle kot prvi specializiran šahovski računalnik uradno dosegel rating šahovskega mojstra. A takrat že ni bil več najzmogljivejši.

Ken Thompson (desno) in Joe Condon, konstruktorja šahovskega računalnika Belle (Foto Bell Laboratories)

V začetku osemdesetih let je namreč v računalniškem šahu vladal Cray Blitz. Bil je naslednik programa Blitz, ki ga je Robert Hyatt napisal že leta 1968. Hyatt je program ves čas po malem razvijal, pravi pospešek pa je doživel, ko je leta 1980 postal njegov pokrovitelj izdelovalec superračunalnikov Cray. Hyatt je Blitz predelal za takrat najmočnejši superračunalnik Cray-1 in Cray Blitz je leta 1981 zmagal na državnem prvenstvu Mississipija, kot prvi šahovski program na turnirju premagal šahista z naslovom mojstra in dosegel mojstrski rating.

Harry Nelson (na sliki) je skupaj z Robertom Hyattom naredil Cray Blitz (Foto Lawrance Livermore National Laboratory)

Antični šahovski programi

Marsikaterega izmed starih šahovskih programov brezplačno dobimo v internetu. Ena najboljših zbirk je na spletni strani Antique Computer Chess (classicchess.tripod.com)

Šahiranje z osebnimi računalniki

Šahovske programe so v drugi polovici sedemdesetih let začeli pisati tudi za prve osebne računalnike in zgodba z velikih računalnikov se je ponovila. Prvi šahovski programi za Apple, Atarije, Mavrice in kar je še bilo podobnih računalnikov, so bili namreč še zelo nebogljeni, a predvsem zaradi omejene procesorske in pomnilniške zmogljivosti malih računalnikov.

Eden prvih takih programov je bil Sargon iz leta 1978. Avtorja Dan in Kathle Spracklen sta njegove programske vrstice kar javno objavila v knjigi SARGON: A computer chess program, od koder ga je lahko vsakdo prepisal.

Ne pozabimo, da so v časih pred internetom in ko nekateri računalniki še disket niso imeli, ljubitelji računalnikov pogosto prepisovali programe iz računalniških revij in knjig. Na njihovo srečo so bili programi za osebne oziroma mikroračunalnike, kakor so jim takrat rekli, majhni. Leta 1980 izdelani šahovski program HIARCS (Higher Intelligence Auto Response Chess System) je imel, recimo, v prvi različici samo 550 v basicu napisanih vrstic. Mimogrede, njegovi potomci so še danes med bolj priljubljenimi in zmogljivimi šahovskimi programi za osebne in žepne računalnike.

Za Sinclair ZX-81 so tri leta zatem napisali verjetno najmanjši šahovski program. 1K Chess je imel, verjeli ali ne, samo 672 bajtov in manjši čudež je, da je sploh znal pravilno premikati figure. A osebni računalniki so hitro postajali zmogljivejši in že za Sinclairjeve Spectrume z 48 kilobajti pomnilnika so napisali šahovske programe, ki jih ni bilo več tako lahko premagati.

Leta 1986 je v trgovine prišel Chessmaster 2000, prva različica danes verjetno najbolj priljubljenega šahovskega programa. Chessmaster je bil za razliko od večine takratnih šahovskih programov grafično bogato opremljen, uporabili smo ga lahko za učenje šaha, za povrh pa je bil tudi zmogljiv. Njegova trenutna različica Chessmaster 10 je osmi najboljši šahovski program na svetu in dandanes morajo tudi najboljši šahovski mojstri napeti vse sile, če hočejo premagati svoj domači "pecejček".

Takole je bil videti prvi šahovski program za PC iz leta 1981.

Crafty

Cray Blitz je bil pred dvajsetimi leti najmočnejši šahovski program, dandanes pa njegovega neposrednega naslednika, Crafty, dobimo kar brezplačno. A nikar ne mislite, da je zaradi ugodne cene drugorazredni program. Igra namreč na ravni velemojstra in ima šahovski rating približno 2600. V Sloveniji ima samo en šahist, Beliavsky, višjega.

Crafty je lani na svetovnem prvenstvu šahovskih programov med 12 udeleženci zasedel solidno peto mesto. V osnovni obliki deluje v Dosu (pa tudi v Linuxu in MacOS) in sploh nima grafičnega vmesnika, a k sreči lahko uporabimo dodatnega, na primer WinBoard. Crafty najdete na spletni strani njegovega avtorja, Roberta Hyatta (www.cis.uab.edu/info/faculty/hyatt/), skupaj z WinBoardom pa tudi na cito.atspace.com/crafty.html.

Šahovnica WinBoard in odličen šahovski program Crafty sta brezplačna.

Velemojstri v težavah

Šahovski programi so bili pred dvajsetimi leti že zelo dobri, saj so se najboljši ponašali z mojstrskimi ratingi, a velemojstrom, razen pri hitropoteznem šahu, še vedno niso bili kos. Eden najboljših šahistov vseh časov, Gari Kasparov, je na primer leta 1985 v Hamburgu igral s 15 najmočnejšimi šahovskimi računalniki in vse po vrsti premagal, in to dvakrat zapored. A do prvega poraza velemojstra takrat ni bilo več daleč.

Sredi osemdesetih let so se v tekmo za najmočnejši šahovski računalnik podali na univerzi Carnegie Mellon. Leta 1985 je skupina Hansa Berlinerja, ki je bil tudi svetovni prvak v dopisnem šahu, razvila poseben procesor za analizo šahovskih položajev in iz njih sestavila računalnik HiTech. Ta je leta 1988 premagal velemojstra Arnolda Denkerja in postal prvi šahovski računalnik, ki je dosegel velemojstrsko raven.

Hans Berliner (levo) in Carl Ebeling sta na univerzi Carnegie Mellon izdelala šahovski superračunalnik HiTech. (Foto Bill Redick)

HiTech ni bil edini šahovski superračunalnik, ki so ga razvijali na univerzi Carnegie Mellon. Že leta 1985 sta študenta Feng-Hsiung Hsu in Murray Campbell razvila podoben šahovski igri prirejen procesor in na njegovi osnovi naredila šahovski računalnik ChipTest. V prvi različici je bil še razmeroma skromen, saj je lahko pregledal "le" 50.000 položajev na sekundo, ko so ga čez dve leti nadgradili, pa je bil že desetkrat hitrejši. A to je bil pravzaprav šele začetek.

Leta 1988 sta Hsu in Campbell na podlagi ChipTesta naredila šahovski računalnik Deep Thought, poimenovan po računalniku iz legendarne radijske igre Štoparski vodič po Galaksiji. Deep Thought se je leta 1989 pomeril s Kasparovom in v obeh partijah gladko izgubil. A snovalcema to ni vzelo veselja. Še istega leta sta v IBM naredila Deep Blue, šahovski superračunalnik, ki se je zapisal v zgodovino kot prvi, ki mu je uspelo premagati aktualnega svetovnega šahovskega prvaka.

Digitalna pamet šahovskega superračunalnika ChipTest. (Foto Internet Chess Club)

Globoka modrina

Deep Blue je bil približno milijonkrat zmogljivejši od IBM 704, ki se je štirideset let prej prvi naučil šahirati. Narejen je bil na podlagi superračunalnika RS/6000 s 480 posebnimi šahovskimi procesorji. Leta 1996 sta se Deep Blue in Gari Kasparov prvič spopadla in računalnik je že v prvi partiji dosegel senzacionalno zmago. Kasparov se je nato zbral in v naslednjih petih partijah dvakrat remiziral in trikrat zmagal ter dobil dvoboj.

V IBM so Deep Blue izboljšali in naslednje leto je Deeper Blue, kakor so ljubkovalno imenovali izboljšano različico, s 3,5 proti 2,5 dosegel zgodovinsko zmago v dvoboju s Kasparovom. Zmagovalni računalnik je lahko v eni sekundi pregledal kar 200 milijonov položajev in igro analiziral do 12 polpotez (šest svojih in šest nasprotnikovih) v globino.

Poraz Kasparova z Globoko modrino je bil morda res bolj posledica slabše forme človeškega prvaka in tudi danes Kasparov in drugi velemojstri še vedno premagujejo najzmogljivejše šahovske računalnike in programe, a vedno teže in sploh ne vedno.

Velemojster Kramnik je na primer leta 2002 v razvpitem dvoboju v Bahrainu s programom Fritz dosegel le neodločen rezultat (dve zmagi, štirje remiji in dva poraza), naslednje leto pa se je z neodločenim rezultatom proti izraelskemu programu Deep Junior moral zadovoljiti tudi Kasparov.

Trenutno verjetno najzmogljivejši šahovski superračunalnik, Hydra, v neposrednem dvoboju s človekom sploh še ni doživel poraza. Premagal je že nekaj velemojstrov, je pa res, da se z najboljšimi še ni pomeril. Gari Kasparov je pred nekaj leti napovedal, da leta 2010 nihče več ne bo mogel premagati računalnika in prav mogoče je, da se bo njegova napoved uresničila.

Deep Blue, prvi računalnik, ki mu je uspelo premagati svetovnega šahovskega prvaka. (Foto IBM)