Šahovski računalniški programi

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

Kratka zgodovina

Prvi šahovski stroj

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 10¹²⁸ razporeditev, kar je več kot je atomov v nam znanem Vesolju (skromnih 10⁸⁰). 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

Zopet je bil tukaj vseprisoten Kenneth Thompson kot pionir tega razvoja. V osemdesetih je pričel generirati in shranjevati vse možne dovoljene razporeditve v šahovskih končnicah s štirimi in petimi figurami na šahovski tabli. Tipična šahovska končnica s petimi figurami, kot kralj in dva lovca proti kralju in skakaču, vsebuje 121 milijonov razporeditev. S kmetom, ki je asimetričen v svojih premikih, številka naraste na 335 milijonov. Thompson je napisal programe, ki generirajo vse možne dovoljene razporeditve in izdelajo vse prisiljene različice, ki so možne v vsaki končnici. Rezultate je stisnil na način, da je lahko shranil približno 20 končnic na standardni CD-ROM.

Z uporabo teh končnic lahko računalnik igra vsako končnico idealno (»kot bog«). V vsaki razporeditvi z določenim materialom na šahovnici program v trenutku »ve« ali je razporeditev zmagovalna, remi ali izgubljena. Napove tudi v koliko potezah sledi rezultat, pogosto napove zmago ali mat v preko petdesetih potezah. Na izgubljeni strani pa se brani optimalno. »Deep Blue« uporablja Thompsonove knjižnice končnic in celo PC šahovski program »Fritz« ima vgrajene pri drevesnem iskanju razporeditev. Kako bo to vplivalo na igralno moč bomo šele videli.

Nekatere končnice s petimi figurami so za človeka izredno težke ali celo neobvladljive. Najboljši primer je kraljica in kralj proti kralju, kraljici in kmetu, kjer ni človeka, ki bi imel najmanjšo možnost proti računalniku. Vendar pa so končnice s petimi figurami igrica križcev in krožcev v primerjavi s končnicami s šestimi figurami na katerih Thompson trenutno dela. V nekaterih razporeditvah s šestimi figurami je potrebno preko 200 pravilnih potez za zmago. Pogosto je nemogoče tudi namočnejšemu igralcu napovedati kakšen napredek je bil dosežen po stotih potezah za katere računalnik meni, da so ključnega pomena. Seveda se računalniška strojna oprema razvija v skladu z večanjem računalniških kapacitet. Thompsonove knjižnice šahovskih končnic, ki vsebujejo 8 do 20 milijard razporeditev vsaka, se zlahka shrani stisnjena na DVD.

Na srečo za končnice s sedmimi figurami, ki vsebujejo pol trilijona razporeditev vsaka, še ni prostora za njihovo shranitev. Še večja sreča pa je, da se otvoritve in končnice nikoli ne bodo srečale. Prav gotovo ne bo nihče videl računalnika, ki bi po prvi potezi napovedal mat v štiridesetih potezah. Vendar pa je najbrž samo vprašanje časa, nekaj let ali desetletje, ko bo računalnik za človeka nepremagljiv.

Kdaj se bo zgodilo?

Kdaj natančno se bo to zgodilo? Kdaj bo računalnik premagal svetovnega šahovskega prvaka v regularnem dvoboju? Tukaj je nekaj napovedi vodilnih strokovnjakov, vprašanih med letoma 1991 in 1994:

• 1992, Prof. Monty Newborn
• 1993, John McCarthy
• 1994, Hans Jack Berliner, Feng-hsiung Hsu
• 1995, Murray Campbell, Donald Michie, Mike Valov
• 1999, Claude Shannon, Frederic Friedel
• 2001, John Nunn
• 2010 (ali nikoli), Gari Kasparov
• 2018, Kenneth Thompson

Za napoved Wikipedije poglejte in glasujte na pogovorni strani.

Časovni pregled računalniškega šaha

• 1769, Wolfgang von Kempelen izdela »računalniški stroj«.
• 1868, Charles Hooper predstavi »računalniški stroj« Ajeeb.
• 1912, Leonardo Torres y Quevedo zgradi mehanski stroj El Ajedrecista, ki s pomočjo elektromagnetov lahko igra končnico s tremi figurami - kralj in trdnjava proti človeškemu nasprotniku s kraljem.
• 1948, Norbert Wiener v knjigi Kibernetika (Cybernetics) opiše kako se lahko razvije računalniški program s pomočjo globinsko omejenega minimalno-maksimalnega iskanja z vrednotenjsko funkcijo.
• 1950, Claude Elwood Shannon objavi Programiranje računalnika za igranje šaha (Programming a Computer for Playing Chess), enega prvih člankov o problemu računalniškega šaha.
• 1951, Alan Turing na papirju razvije prvi program, ki je bil sposoben igrati šah v celoti.
• 1952, Dietrich Prinz razvije program, ki rešuje šahovske probleme.
• 1956, Paul Stein in Mark Wells za računalnik MANIAC I razvijeta Los Alamos chess, prvi program, ki igra šahu podobno igro na šahovnici 6 × 6 brez lovcev.
• 1956, John McCarthy izumi iskalni algoritem alfa-beta.
• 1958, program NSS prvi uporablja algoritem alfa-beta.
• 1958, razvijejo prva programa, ki sta sposobna igrati šahovsko igro v celoti, enega Alex Bernstein, drugega pa ruski programerji s pomočjo računalnika BESM.
• 1962, MIT izda program Kotok-McCarthy, prvi program, ki igra verodostojno.
• 1966-1967, poteka prva partija med računalniškimi programi. Moskovski ITEP po dobrih devetih mesecih prek telegrafa premaga program Kotok-McCarthy z Univerze Stanford.
• 1967, program Mac Hack VI, ki so ga razvili Richard D. Greenblatt in sodelavci, uporablja premestitvene tabele, prvi dobi rating in prvi premaga človega v turnirski igri.
• 1970, v New Yorku poteka prvo Severnoameriško prvenstvo v računalniškem šahu kjer zmaga program Chess 3.0 s Severnozahodne univerze.
• 1974, program Kaissa zmaga na prvem Svetovnem prvenstvu v računalniškem šahu v Stockholmu.
• 1977, izdelajo prvi mikroprocesorski šahovski stroj CHESS CHALLENGER.
• 1977, ustanovljena je Mednarodna zveza računalniškega šaha (ICCA).
• 1977, program Chess 4.6 zmaga na drugem Svetovnem prvenstvu v računalniškem šahu v Torontu.
• 1980, v Londonu poteka prvo Svetovno prvenstvo v računalniškem šahu z mikroprocesorji.
• 1980, ustanovijo Fredkinovo nagrado.
• 1980, šahovski računalnik Belle, ki sta ga izdelala Joe H. Condon in Kenneth Thompson, zmaga na tretjem Svetovnem prvenstvu v računalniškem šahu v Linzu.
• 1981 program Cray Blitz, ki so ga napisali Robert Hyatt, Harry Nelson in Albert Gower, zmaga na Državnem prvenstvu Mississippija z rezultatom 5-0 in ratingom 2258. V četrti partiji premaga Joeja Sentefa (2262) ter tako postane prvi program, ki je premagal mojstra v turnirski igri in prejel mojstrski rating.
• 1982, Belle dobi ameriški naziv mojstra.
• 1983, Cray Blitz zmaga na četrtem Svetovnem prvenstvu v računalniškem šahu v New Yorku.
• 1984, Cray Blitz zmaga na petem Svetovnem prvenstvu v računalniškem šahu v Kölnu.
• 1988, šahovski računalnik HiTech, zgrajen na Univerzi Carnegie Mellon pod vodstvom svetovnega prvaka v dopisnem šahu Hansa Jacka Berlinerja ter skupine v kateri so bili Berliner, Carl Ebeling, Murray Campbell in Gordon Goetch, zmaga proti mednarodnemu velemojstru Arnoldu Sheldonu Denkerju s 3,5-0,5.
• 1988, šahovski računalnik Deep Thought si deli prvo mesto z velemojstrom Tonyjem Milesom na Prvenstvu programskih orodij pred nekdanjim svetovnim prvakom Mihailom Taljem in nekaterimi drugimi velemojstri Samuelom Reshevskym, Walterjem Browneom in Mihailom Naumovičem Gurevičem. Premaga tudi velemojstra Benta Larsena, kar je prvič v turnirski igri. Njegov rating ELO za nastop na tem turnirju 2745 (lestvica USCF) je bil najvišji za računalnik.
• 1989, Deep Thought izgubi dve ekshibicijski igri proti Gariju Kasparovu, tedanjemu svetovnemu prvaku. Zmaga na šestem Svetovnem prvenstvu v računalniškem šahu v Edmontonu.
• 1992, program Gideon 3.1, ki je tekel na šahovskem računalniku ChessMachine in ga je razvil Ed Schröder, kot prvi mikroračunalnik zmaga na sedmem Svetovnem prvenstvu v računalniškem šahu v Madridu pred velikimi računalniki, superračunalniki in posebno strojno opremo.
• 1995, program Fritz zmaga na osmem Svetovnem prvenstvu v računalniškem šahu v Hong Kongu.
• 1997, IBM-ov šahovski računalnik Deep Blue zmaga v šestih partijah proti Gariju Kasparovu.
• 1999, program Shredder zmaga na devetem Svetovnem prvenstvu v računalniškem šahu v Paderbornu.
• 2002, Vladimir Kramnik remizira v osmih partijah proti programu Deep Fritz.
• 2002 program Deep Junior zmaga na desetem Svetovnem prvenstvu v računalniškem šahu v Maastrichtu.
• 2003, Kasparov remizira v šestih partijah proti programu Deep Junior.
• 2003, Kasparov remizira v štirih partijah proti programu X3D Fritz.
• 2003, Shredder zmaga na enajstem Svetovnem prvenstvu v računalniškem šahu v Gradcu.
• 2004, Deep Junior zmaga na dvanajstem Svetovnem prvenstvu v računalniškem šahu v Ramat Ganu.
• 2005, program Hydra premaga velemojstra Michaela Adamsa s 5,5-0,5.
• 2005, skupina računalnikov (Hydra, Deep Junior in Fritz), z rezultatom 8,5-3,5 premaga močno skupino šahistov (Veselin Topalov, Ruslan Ponomarjov in Sergej Karjakin, s povprečnim ratingom ELO 2681).
• 2005, program Zappa zmaga na trinajstem Svetovnem prvenstvu v računalniškem šahu v Reykjavíku.
• 2006, svetovnega prvaka Vladimirja Kramnika s 4-2 premaga Deep Fritz.
• 2006, program Junior zmaga na štirinajstem Svetovnem prvenstvu v računalniškem šahu v Torinu.
• 2007-2009, program Rybka, ki ga je razvil mednarodni mojster Vasik Rajlich, zmaga na 15., 16. in 17. Svetovnem prvenstvu v računalniškem šahu v Amsterdamu, Pekingu in Pamploni.
• 2007 Zappa premaga Rybko s 5,5-4,5.

Glej tudi

• šah

Prevod z dovoljenjem avtorja, izvorni avtor: Frederic Friedel, www.chessbase.com