Šahovski računalniški programi
Iz Wikipedije, proste enciklopedije
[uredi] Kratka zgodovina
[uredi] 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.
[uredi] Torres y Quevedov »Šahist«
Prvi šahovski stroj z vgrajenim algoritmom za »računanje« potez ni bil nek 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 nek 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.
[uredi] 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 Mathison 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.
[uredi] 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 selktivno 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.
[uredi] Š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.
[uredi] Šah in matematika
Glavni problem pri šahovskem programiranju je veliko število izračunov. V povprečni razporeditvi je okoli 40 dovoljenih potez. Pri odgovoru na vsako od teh potez dobimo 40 × 40 = 1.600 razporeditev. To pomeni, da po vsaki drugi polpotezi, ki se smatra kot ena poteza v šahu, število razporeditev naraste za 1.600. 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 okoli 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 globje 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.
[uredi] 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 brez, 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 pet kratno povečanje hitrosti za dodatno polpotezo globine. Eksponentna eksplozija je spet ujela programerje.
[uredi] 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 okoli 180.000 razporeditev na sekundo (superračunalniki v tistem času so dosegali 5.000 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č.
[uredi] Šahovski čipi
Sredi osemdesetih let je profesor Hans Berliner zapolnil vrzel, ki jo je Ken 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 okoli 5.000 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«.
[uredi] 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.
[uredi] Globina iskanja in igralna moč
Kaj nam 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 okoli 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.
[uredi] Osebni računalniki
Seveda je pomembna tudi kvaliteta 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. Realno taki programi igrajo z močjo 2600 točk ELO. Kjubujejo 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.
[uredi] 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.
[uredi] 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 okoli 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.
[uredi] 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 leti 1991 in 1994:
- 1992, Prof. Monty Newborn
- 1993, John McCarthy
- 1994, Hans 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.
[uredi] Glej tudi
Prevod z dovoljenjem avtorja, izvorni avtor: Frederic Friedel, www.chessbase.com
