Pod pojmom kompjuterskog šaha podrazumevamo oblast koja je deo naučne discipline kojoj je ime veštacka inteligencija. Kompjuterski šah se bavi izgradnjom programa i sistema koji automatski igraju šah, poštujući šahovska pravila. Današnji moderni šahovski programi se izvršavaju na razlicitim računarskim sistemima, pa i na standardnim personalnim računarima. Oni su proizvod visoke tehnologije s obzirom da u sebi objedinjavaju brojne teorijske i implementacione tehnike. Pri tome se koriste i matematička teorija, baze podataka, programiranje, različiti hardveri (jednoprocesorski ili višeprocesorski sistemi), softveri (počev od operativnih sistema, do namenskih algoritama) … Pristup kompjuterskom šahu imaju široki slojevi potencijalnih vrhunskih eksperata u ovoj oblasti, od talentovanih pojedinaca koji mogu da razvijaju programe na svojim kucnim racunarima, pa do ozbiljnih naučnih timova na fakultetima i institutima. Ulaskom najveće svetske kompjuterske kompanije IBM u oblast kompjuterskog šaha i izgradnjom, u to vreme, najjačeg kompjutera na svetu IBM Deep Blue koji je u meču u maju 1997 god. pobedio svetskog šampiona Garija Kasparova, otvorena je nova era u razvoju kompjuterskog šaha.
Istorijski razvoj računskih šahovskih mašina
Razvoj kompjuterskog šaha, kao oblasti veštacke inteligencije, datira od pojave elektronskih računskih mašina.
Ipak, jedan interesantan pokušaj konstruisanja automata zabeležen i pre toga, 1769. godine. Naime, nemacki inženjer Baron Wolfgang von Kempelen se te godine pojavljuje sa svojom znamenitom mašinom Turčin. U mašini je zapravo bio sakriven neki šahovski majstor koji je razmišljao o potezima. Prevara je otkrivena kada je jednom prilikom došlo do požara u prostoriji u kojoj se nalazio Turčin. Šahista je u strahu iskocio iz svog zaklona.
Za datumski početak ozbiljnog razvoja kompjuterskog šaha se može uzeti 1946. godina, kada engleski matematičar Alan Tjuring prvi put povezuje mašinsku inteligenciju sa problemom mašinskog igranja šaha.
Od tog samog početka do današnjih dana u žiži interesovanja, kako opšte tako i stručne javnosti, je bilo pitanje: Može li mašina svojim “intelektom“ nadmašiti coveka? ili pojednostavljeno: Može li kompjuter pobediti svetskog prvaka u šahu?
Zaplovimo malo kroz istorijat kompjutrskog šaha, pominjući samo neke, najznačajnije, momente iz njegove burne istorije.
1948 – Napravljen je kompjuter UNIVAC, najjači kompjuter toga doba i prvi kompjuter u komercijalnoj upotrebi. Neki tadašnji teoretičari su smatrali da ako se programira da igra šah, može pobediti svakog igrača na svetu. To, naravno, nije bilo tačno. Prvobitne mašine, kasnije se pokazalo, su imale snagu šahovskih početnika.
1950 – Alan Tjuring je napisao prvi šahovski program. Iste godine on je postulirao Tjuringov test i predložio da šah bude jedan od osnovnih medija za testiranje veštacke inteligencije. Konkretno, ako u toku šahovske partije covek-šahista ne može da odredi da li igra sa drugim covekom-šahistom ili pak sa kompjuterom, u slucaju da partiju igra kompjuter, on prolazi test veštacke inteligencije.
1950 – Claude Shannon je opisao principe izgradnje šahovskog programa u radu pod nazivom „Programming a computer for playing chess“, štampanom u casopisu Philosophical Magazine, Series 7, Vol. 41 (No. 314, March 1950). Ovo je bio prvi rad o kompjuterskom šahu.
1951 – Alan Turing je napisao, tada verovatno, prvi šahovski program TURBOCHAMP. Nažalost, tada nije postojao kompjuter koji je sposoban da pokrene TURBOCHAMP. Prvi meč između šahovskog programa i čoveka nadgledan je od strane Turinga koji je vršio proračune programa bez pomoći kalkulatora. Protivnik mu je bio Allick Glenms koji je matirao TURBOCHAMP posle 29 poteza u igri koja je trajala 3 sata. TURBOCHAMP program nije mogao da gleda više od jednog koraka unapred, nije znao razliku između otvaranja, sredine i kraja igre. Program je znao pravila igre i koristio je osnovne algoritme.
1959 – Neki programeri kompjuterskih šahovskih programa su predvideli da će kompjuter biti svetski šampion pre 1970.
1968 – Internacionalni šahovski majstor David Levy je objavio čuvenu opkladu u 3.000 dolara, da ga ni jedan šahovski program ne može pobediti za 10 godina. Prvobitna opklada je zapravo bila sa John McCarthz-jem u toku trajanja konferencije o mašinskoj inteligenciji na Stenford-u, ali je kasnije proširena. (Videće se kasnije šta je bilo sa opkladom.)
1970 – Održano je prvo kompjutersko prvenstvo u Nju Jorku. Prvo mesto zauzeo je program Chess 3.0 koji je radio na CDC 6400 kompjuteru. Program je napisan od strane Slate, Atkin i Gorlen sa Northwestern Univerziteta. Šest programa je učestvovalo u prvenstvu koji je ogranizovala asocijacija ACM Association for Computing Machinery i Montz Newborn. Ostali programi koji su učestvovali su DALY CP, J Brit, COKO III, SCHACH i Marsland CP.
1977 – Michael Stean postaje prvi velemajstor koji je izgubio od kompjutera, doduše u brzopoteznoj partiji.
1977 – Konstruisan je prvi paralelni šahovski sistem BELLE koji je koristio specijalno dizajniran hardver. Brzina mašine iznosila je 160000 pozicija u sekundi. Korišćeno je preko 1700 integralnih kola. Ovaj kompjuter izradio je Ken Thompson. Kasnije je mašina korišcena za izgradnju baze završnica. Cena mašine je bila 20000 dolara.
1977 – Zvanično je osnovana Međunarodna organizacija kompjuterskog šaha (International Computer Chess Association).
1980 – Edward Fredkin osniva nagradni fond (Fredkin Prize) za kompjuterski šah. Nagrada od 100.000 dolara ide prvom programu koji pobedi svetskog šampiona u šahu.
1981 – Program CRAY BLITZ pobeduje na državnom šampionatu Misisipija sa savršenim 5-0 rezultatom, sa rejtingom 2258. U cetvrtoj rundi pobeduje Joe Sentef-a (2262) i postaje prvi kompjuter koji je u regularnim uslovima pobedio šahovskog majstora i dostigao majstorski rejting.
1988 – Mašina i program pod nazivom DEEP THOUGHT i velemajstor Tony Miles dele prvo mesto na U.S. Open šampionatu. DEEP THOUGHT dostiže rejting 2745.
1989 – DEEP THOUGHT pobeđuje na 6. Svetskom kompjuterskom šampionatu u Edmontonu sa 5-0 rezultatom. Zatim, iste godine, DEEP THOUGHT dobija velemajstora Roberta Birna u partiji u mecu sa njim. Mašina dostiže 2 miliona pozicija u sekundi. U martu 1989. Gari Kasparov dobija DEEP THOUGHT u mecu, pobedom u 2 partije. DEEP THOUGHT dobija internacionalnog majstora Dejvida Levija (onog, koji je svojevremeno dobio opkladu) sa 4-0. Programski tim DEEP THOUGHT-a izjavljuje da ce kompjuter postati svetski šampion u naredne 3 godine.
1989 – IBM počinje da radi na mašini Big Blue. Kasnije projekat prerasta u DEEP BLUE.
Mart 1993 – Velemajstor Judit Polgar gubi od kompjutera DEEP THOUGHT u 30 minutnoj partiji.
Februar 1996 – Gari Kasparov pobeđuje IBM-ov kompjuter DEEP BLUE sa rezultatom 4-2 u Filadelfiji. DEEP BLUE je dobio prvu partiju, čime je postao prvi kompjuter koji je pobedio svetskog šampiona u normalnim turnirskim okolnostima. Mašina je obradivala 50 milijardi pozicija na svakih 3 min, prema Kasparovu koji je mogao da obraduje svega desetak pozicija za isto vreme. DEEP BLUE se sastojao od 200 procesora.
April 10 – 17 1996 – Održan je 11. AEGON turnir (Mankind vs Machine) u Hagu u Holandiji. Učestvovalo je 50 šahovskih majstora, internacionalnih majstora i velemajstora kao i 50 šahovskih kompjutera. Najbolji rezultat postigao je velemajstor Yasser Seirawan sa 6 pobeda iz 6 partija. Najbolji kompjuter je bio QUEST (verzija Fritz-a) sa 4.5 poena iz 6 partija i rejtingom 2652. Kompjuteri su pobedili u ovom velikom meču osvojivši 162.5 poena prema 137.5 poena koliko su osvojili šahovski majstori.
Maj 1997 – Održan je istorijski meč u kome je IBM Deep Blue (usavršena verzija programa i kompjutera iz 1996. godine – njegov neslužbeni nadimak je bio Deeper Blue) pobedio Gari Kasparov-a u meču od 6 partija (rezultat: 3.5 – 2.5) u New York-u.
1997 – Nagradu od 100.000 dolara iz fonda Fredkin Prize iz 1980. godine, osvajaju konstruktori DEEP BLUE mašine (koja je pobedila Svetskog šampiona u šahu Garija Kasparova u standardnim turnirskim uslovima) Feng Hsu, Murraz Campbell, and Joseph Hoane.
Jula 2002 – 10. Svetski šampionat u kompjuterskom šahu održava se u Maastricht-u. Šampion je DEEP JUNIOR posle pobede u play-off mecu protiv SHREDDER-a.
2003 – Kasparov igra mec protiv Deep Junior-a 7 u New York-u. Mec je završen remijem, sa po jednom pobedom za svakog protivnika. Ovo je prvi put da je šahovski meč održan pod patronatstvom FIDE. Na programu Deep Junior njegovi autori Amir Ban i Shay Bushinsky su radili 10 godina.
2003 – Kasparov igra protiv X3d Fritz-a u New Yorku. Meč je završen nerešeno 2-2. Fritz je dobio 2. partiju a Kasparov treću. Prvi put je igrano na virtuelnoj, 3D šahovskoj tabli.
21-27 juni 2005 – Održan je mec između najboljeg engleskog velemajstora Adamsa (2723) i paralelnog šahovskog kompjutera Hydra u 6 partija (slika 5). Meč je završen pobedom kompjutera 5.5 prema 0.5, što je najveća pobeda neke mašine nad vodećim svetskim velemajstorom.
Deep Blue vs Kasparov
Deep Blue i Kasparov su igrali međusobno u dva navrata. Prvi meč je počeo 10. februara 1996. godine, u kojem je Deep Blue postao prva mašina koja je pobedila aktuelnog šahovskog prvaka u redovnim vremenskim kontrolama. Međutim, Kasparov je dobio tri meča i odigrao 2 remija u preostalih 5 mečeva, pobedivši Deep Blue rezultatom 4-2. Meč je završen 17. februara 1996. godine. Deep Blue je posle toga unapređen (nezvaničan naziv je bio Deeper Blue) i ponovo je igrao sa Kasparovom u maju 1997. godine, pobedivši sa 3.5 – 2.5. Deep Blue je pobedio u odlučujućem meču posle Kasparove greške u otvaranju i tako postavši prvi kompjuterski sistem koji je pobedio aktuelnog svetskog šampiona u standardnom šahovskom turniru. DEEP BLUE je koristio masivnu paralelizaciju na bazi 30- pinskih IBM RS-6000 SP procesora povezanih sa 480 šahovskih cipova, specijalne namene u VLSI tehnologiji. Mogao je da evaluira 200 miliona pozicija u sekundi.
Dve glavne strategije koje su dostupne programima za šah
1. Brute force search ili Tip A. Sve moguće pozicije su pregledane.
2. Strategic AI ili Tip B. Samo ’dobre’ pozicije su pregledane.
Kako se ispostavilo, računari imaju problema sa konceptom ’dobro’. To je razlog zašto istorijom kompjuterskog šaha dominira Tip A. Najpoznatiji Tip A računar je IBM-ov Deep Blue.
Godina Pozicija/sekundi
1985 50k
1987 500k
1988 720k
1989 2 miliona
1991 7 miliona
1996 100 miliona
1997 200 miliona
Najbolji šahovski programi
- Komodo 9 (rating: 3340) – vodeći komercijalni program.
- Stockfish 6 (rating: 3318) – kompletno besplatan, open-source
- Houdini 4 (rating: 3277) – nekada najbolji šahovski program
- Fire 4 (rating: 3229) – besplatan program, nekada je bio open-source
- Gull 2.8b (rating: 3214) – novi program, bespatan i open-source
Autor teksta: Aleksandar Stojmenović