Pojam i definicija
Pod pojmom kompjuterskog šaha podrazumevamo oblast koja je deo naučne discipline kojoj je ime veštačka 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 različitim 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 kućnim računarima, pa do ozbiljnih naučnih timova na fakultetima i institutima.
Šahovski programi majstorske snage rade na procesorima mobilnih telefona, PalmTop i LapTop računarima, specijalizovanim šahovskim mašinama, kućnim računarima, standardnim PC računarima, višeprocesorskim serverima, sve do nivoa superkompjutera. 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štačke inteligencije, datira od pojave elektronskih računskih mašina.
Ipak, jedan interesantan pokušaj konstruisanja automata zabeležen i pre toga, 1769. godine. Naime, nemački inženjer Baron Wolfgang von Kempelen se te godine pojavljuje sa svojom znamenitom mašinom «turčin» (slika 1). 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 iskočio iz svog zaklona u uređaju.
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 čoveka? 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štačke inteligencije. Konkretno, ako u toku šahovske partije čovek-šahista ne može da odredi da li igra sa drugim čovekom-šahistom ili pak sa kompjuterom, u slučaju da partiju igra kompjuter, on prolazi test veštačke inteligencije.
1950 – Claude Shannon je opisao principe izgradnje šahovskog programa u radu pod nazivom “Programming a computer for playing chess”, štampanom u časopisu Philosophical Magazine, Series 7, Vol. 41 (No. 314, March 1950). Ovo je bio prvi rad o kompjuterskom šahu.
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.
1974 – Svetski šampion u dopisnom šahu, Hans Berliner piše svoju doktorsku tezu “Chess Computers as Problem Solving.”. Ovo je prva doktorska disertacija napisana na temu kompjuterskog šaha.
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 (slika 2). 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šćena 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).
1977 – Im David Levy je igrao protiv prvog kompjutera (Kaissa) u okviru opklade. Pobedio je i dobio opkladu iz 1968. godine.
1978 – BELLE pobeđuje na devetom ACM kompjuterskom šampionatu u Vašingtonu, DC.
1978 – Devid Levy pobeđuje program MacHack u dve partije i potvrđuje svoj stav u vezi opklade iz 1968. godine.
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.
1980 – program BELLE pobeđuje na jedanaestom ACM kompjuterskom šampionatu u Nešvilu.
1981 – Program CRAY BLITZ pobeđuje na državnom šampionatu Misisipija sa savršenim 5-0 rezultatom, sa rejtingom 2258. U četvrtoj rundi pobeđuje Joe Sentef-a (2262) i postaje prvi kompjuter koji je u regularnim uslovima pobedio šahovskog majstora i dostigao majstorski rejting.
1982 – Kompanije koje proizvode šahovske mašine beleže prodaju od preko 100 miliona dolara.
1985 – Gari Kasparov igra protiv 15 najjačih šahovskih kompjutera u Hamburgu u Nemačkoj, i dobija svaku partiju, sa rezultatom 32-0.
1988 – Mašina i program pod nazivom DEEP THOUGHT (slika 3) 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 meču sa njim. Mašina dostiže 2 miliona pozicija u sekundi. U martu 1989 Gari Kasparov dobija DEEP THOUGHT u meču, 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 će 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.
1992 – Kasparov igra sa programom Fritz 2 na 5 minuta u Cologne u Nemačkoj. Kasparov dobija meč sa 6 pobeda, 1 remijem i 4 poraza. Ovo je prvi put da je kompjuterski program pobedio, u nekoj partiji, svetskog šampiona, doduše u brzopoteznoj partiji.
Mart 1993 – Velemajstor Judit Polgar gubi od kompjutera DEEP THOUGHT u 30 minutnoj partiji.
1994 – Kasparov gubi od programa Fritz 3 u Minhenu na blic turniru. Program je takode pobedio velemajstore Ananda, Šorta, Geljfanda i Kramnika. Velemajstor Robert Hibner je odbio da igra. Meč je izgubio sudijskom odlukom, što se po prvi put desilo. Kasnije, Kasparov je odigrao i drugi meč protiv Fritz-a koji je dobio sa 4 pobede i 2 remija, bez poraza.
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 obrađivala 50 milijardi pozicija na svakih 3 min, prema Kasparovu koji je mogao da obrađuje 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 (Slika 4). Ovo je prvi put u istoriji da je kompjuter pobedio šahovskog šampiona u klasicnom šahu u regularnim turnirskim uslovima. DEEP BLUE je koristio masivnu paralelizciju na bazi 30- pinskih IBM RS-6000 SP procesora povezanih sa 480 šahovskih čipova, specijalne namene u VLSI tehnologiji. Mogao je da evaluira 200 milijardi pozicija u sekundi.
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.
1999 – Najjači šahovski kompjuteri, prema SSDF rang listi, su: Hiarcs 7.0, koga slede Fritz 5.32, Fritz 5.0, Junior 5.0, Nimzo 98, Hiarcs 6.0, Rebel 9.0, MChess Pro 7.1, Rebel 8.0, i MChess Pro 6.0
Maj 2002 – Meč između velemajstora Mihajla Gurevića i programa Junior 7 održan je u Grčkoj. Junior je pobedio sa 3 pobede i jednim remijem.
Jula 2002 – 10. Svetski šampionat u kompjuterskom šahu održava se u Maastricht-u. Šampion je DEEP JUNIOR posle pobede u play-off meču protiv SHREDDER-a.
Oktobra 2002 – Kramnik igra 4-4 u meču protiv DEEP FRITZ-a u Bahreinu, sa po dve pobede za oba protivnika.
2003 – Kasparov igra meč protiv Deep Junior-a 7 u New York-u. Meč 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. Program računa 3 miliona pozicija u sekundi do dubina 15 poteza.
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.
2003 – Prema SSDF rang listi, nabolji šahovski programi su: Shredder 7.04 (2810), Shredder 7.0 (2770), Fritz 8.0 (2762), Deep Fritz 7.0 (2761), Fritz 7.0 (2742), Shredder 6.0 (2724), i Chess Tiger 15.0 (2720).
21-27 juni 2005 – Održan je meč 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.
Novembar 25 – 2 decembar 2006 – Održan ponovo meč između Vladimira Kramnika i DEEP FRITZ-a u Bonu (Nemacka), ali za razliku od onog meča iz 2002. godine, sada (ojačani) DEEP FRITZ dobija dve partije uz 4 remija i dobija meč sa 4 – 2.
Analiza postojećeg stanja u kompjuteskom šahu
Sa porastom snage hardvera i novih tehnologija u računarskoj tehnici, nastao je proces širenja teoretskih i pratičnih znanja koja su potrebna za izgradnju jakih šahovskih mašina. Pravci razvoja su direktno sledili razvoj hardvera.
Najvažniji impulsi za oblast kompjuterskog šaha su prodori u mikroelektronskoj tehnologiji. Pojava sve bržih procesora je direktno uticala na porast šahovske snage programa.
Sa druge strane, na teoretskom nivou su se usavršavali sve bolji algoritmi za pretragu stabla, pored osnovne ALFA-BETA tehnike pronađena je klasa PVS i null-move algoritama.
Sa treće strane, usavršavanje memorija i periferijskih uređaja je omogućilo razvoj baza podataka tipa Ken Thomson i Nalimov kojima se može pristupati u realnom vremenu, čime se ekstremno pojačala igra kompjutera u mnogim tipovima završnica.
Na današnjem nivou, možemo biti veoma zadovoljni globalnim stanjem u kompjuterskom šahu. Od više stotina šahovskih programa koji su razvijeni, par desetina ima velemajstorski rejting. Odigrani su mnogi mečevi sa vrhunskim svetskim šahistima.
Svetska šahovska federacija FIDE je u novom Pravilniku predvidela mogucnost nadmetanja sa šahovskim mašinama, tako da se veliki mečevi, sa igračima koji pripadaju vrhunskoj klasi od prvih 20-tak na svetu, organizuju pod pokroviteljstvom FIDE.
Postoje nekoliko kompanija koje se bave kompjuterskim šahom na tržišnoj osnovi. Najznačajnije kompanije koje se bave razvojem šahovskog softvera su: ChessBase, LokaSoft i Arena.
Nekoliko vrhunskih profesionalnih programa, koji su usavršeni do nivoa jakog velemajstora, mogu se instalirati na bilo kom standardnom PC računaru.
Operativan je šahovski superkompjuter Hydra, naslednik IBM Deep Blue mašine.
Svake godine se održava svetsko šahovsko prvenstvo u kompjuterskom šahu, sa mogućnošcu pristupa amaterima i profesionalcima iz čitavog sveta.
Brojne su konferencije i radovi na temu kompjuterskog šaha.
