i i “1637-Kaucic-kako” — 2010/8/26 — 11:57 — page 1 — #1 i i i i i i List za mlade matematike, fizike, astronome in računalnikarje ISSN 0351-6652 Letnik 33 (2005/2006) Številka 6 Strani 22–25 Branko Kaučič: KAKO DELUJEJO ŠAHOVSKI PROGRAMI (TRETJI DEL) Ključne besede: računalništvo, miselne igre, programske rešitve, šah, postopek minimax, posto- pek alfabeta, optimizacija, mobilnost figur, razvoj igre. Elektronska verzija: http://www.presek.si/33/1637-Kaucic.pdf c© 2006 Društvo matematikov, fizikov in astronomov Slovenije c© 2010 DMFA – založništvo Vse pravice pridržane. Razmnoževanje ali reproduciranje celote ali posameznih delov brez po- prejšnjega dovoljenja založnika ni dovoljeno.  Pred nedavnim smo si zadali nekoliko obsežnejšo nalogo: spoznati, kako so zgrajeni računalniški programi za igra- Kako delujejo šahovski programi (tretji del) Branko Kaučič RAÈUNALNIŠTVO tivne poteze; kakor hitro naletimo na slabo potezo, pa gledanje takšne poteze prekinemo. Optimizacija postopka alfabeta Morda na prvi pogled ni popolnoma oči- tno, da je uspešnost iskanja s postopkom alfabeta odvisna od vrstnega reda potez, ki jih pregledujemo. Z dobrim vrstnim redom ugotovimo največje število sla- bih potez oziroma v največji možni meri povečamo število nepreverjenih potez. V najboljšem primeru dosežemo le √—n računanj, kjer n predstavlja število vseh možnih potez. Kateri primer je sploh naj- boljši? Odgovor je preprost: to je primer, v katerem bi najprej poskusili najboljšo po- tezo. Vendar si, na žalost, s takšnim od- govorom ne moremo kaj prida pomagati. Če bi vedeli, katera poteza je najboljša, bi \ bilo pisanje šahovskih programov mala malica. In obratno, kateri primer je naj- slabši? V najslabšem primeru preisku- jemo poteze v obratnem vrstnem redu, tako je vsaka poteza, ki jo preiskujemo, boljša od vseh do takrat pregledanih po- tez. Posledično nikoli ne naletimo na t.i. slabo potezo in število pregledanih potez (iskalno drevo iz slike v prejšnjem pri- spevku) postane enako kot pri postopku minmax. Urejene poteze Kako lahko torej dosežemo najboljši mo- žni scenarij pri pregledovanju potez? Ali najboljši scenarij sploh potrebujemo? Za postopek alfabeta velja, da je zelo učin- kovit pri odkrivanju slabih potez, če le do- volj hitro najdemo dobro potezo, s katero primerjamo ostale. Brez ugibanja seveda ne gre in razvitih je bilo kar nekaj metod, ki težijo k čim boljšemu zaporedju prever- janja potez: Vse položaje figur ocenimo (kako ocenimo, bomo videli v nadaljevanju) in jih uredimo od najboljše proti najslabši. Bolj realna kot je ocena, bolj učinkovita je ta metoda. Zavedati pa se moramo, da nekaterih položajev ne moremo natanč- no oceniti in tako je dober položaj lahko ocenjen slabo.   Na tem mestu obravnavamo, kako lahko ta postopek še izboljšamo, temu pa sledi še zadnji manjkajoči člen: kako dejansko ocenimo položaj figur posameznika. Spomnimo se Postopek alfabeta deluje na principu po- stopka minmax, v katerem imamo dva igralca (Min in Max); gledamo vse možne kombinacije potez igralcev. V alfabeta nasprotno od vseh možnih potez gleda- mo (pravimo, da iščemo) samo perspek- \ nje šaha. V prvem prispevku smo si ogledali osnov- ne gradnike takšnih programov, v drugem neka- tere od teh, med drugim tudi postopek izbiranja naslednje igralčeve poteze (svoje in nasprotniko- ve). Končali smo z omembo postopka alfabeta. Presek 33 (2005/2006) 6, strani 22–25 Računalništvo ? iščemo sa mo perspe ktivne pot eze... n = Presek 6-3.indd 22 19.5.2006 10:54:42  Najprej poskusimo določene tipe po- tez. Na primer, preverjanje poteze, v ka- teri nam bo nasprotnik vzel kraljico, bo redkokdaj dobra izbira. Zato pričnemo s potezami, kjer nasprotniku vzamemo ka- kšno figuro, promoviramo kmeta v drugo figuro (kar lahko dramatično spremeni ravnovesje igre), nasprotniku napovemo šah (kar pogosto omogoča le peščico ve- ljavnih potez) in šele nato preostale po- teze. Kot bomo videli kasneje, je ta me- toda osnova postopku, ki ga imenujemo »postopno podaljševanje iskanja«. Poiskati poskusimo potezo, ki pred- stavlja položaj figur, ki so že v premikalni tabeli (glej prejšnji prispevek za podrob- nosti te tabele). Če je ocena takšnega položaja dovolj dobra, bo povzročila pre- poznavanje večjega števila slabih potez. Idejo preverjanja določenega tipa po- tez razširimo na idejo preverjanja poteze, ki je pred kratkim (morda v prejšnjem ra- čunanju ali pa na kateri od manjših globin iskanja) povzročila prepoznavanje večjega števila slabih potez. Omenjena metoda se imenuje »ubijalska poteza« in teme- lji na opazovanju, da je mnogo potez (od vseh možnih) slabih. Na primer, če nam je nasprotnik napadel kraljico, so skoraj vse poteze, ki ne zaščitijo ali premaknejo kraljice, najverjetneje slabe poteze. Na- sprotnik bo ne glede na to, katero potezo bi izbrali, verjetno vzel kraljico. Idejo ubijalske poteze lahko nadalje razširimo v idejo »zgodovine potez«. Na primer, če se med igro premik figure iz G2 na E4 izkaže kot učinkovit, bo morda tudi sedaj pri tem iskanju potez učinko- vit (tudi če je prejšnja figura, recimo, bila     skakač in je sedaj zamenjana s kraljico), ker se morda stanje šahovnice od zadnje- ga računanja ni veliko spremenilo. Izkaže se, da zgodovina potez daje zelo zanimi- ve rezultate. Vse omenjene metode niso zanemarljive, vendarle pa se za najbolj učinkovito me- todo izkaže metoda »postopno podaljše- vanje iskanja«, ki je sicer na prvi pogled nelogična. Postopno podaljševanje iskanja Ideja je preprosta: pričnimo z iskanjem vseh potez, ki izvirajo iz danega položaja, do globine 2. Poteze zatem uredimo in na podlagi njihove ureditve iščemo poteze do globine 3. Nove poteze ponovno ure- dimo in iščemo poteze na globini 4. Po- stopek ponavljamo, dokler ne pridemo do želene globine. Vidimo lahko, da smo si z urejanjem potez na vsaki globini dodatno otežili iskanje najboljše poteze. Zakaj bi ravnali tako, ko pa vemo, da s preverja- njem čim večjega števila potez lahko bo- lje napovemo najboljšo potezo? Izkaže se, da s postopnim podaljševanjem iska- nja s katerokoli od prej omenjenih metod v povprečju preverimo manjše število potez kot pa z običajnim postopkom al- fabeta. Ko uporabimo premikalne tabele, je izboljšava celo še večja: dodatno delo, ki ga opravimo, je v primerjavi z drugimi izračuni nično. Ocenjevanje položaja figur Še ničesar nismo zapisali o dejanski oceni položaja figur na šahovnici. Predpostavili smo namreč, da nekako znamo oceniti položaj. Oglejmo si torej še zadnji košček  \ RAÈUNALNIŠTVO naše odisejade računalniških šahovskih programov. Naj poudarimo, da se ocenjevanje polo- žaja figur še vedno razvija. Že desetletja iščejo čim boljše funkcije ocene in mnogi dobri šahovski programi tovrstno infor- macijo skrivajo kot največji zaklad. Polo- žaj je nemogoče zares optimalno oceniti, če ne poznamo vseh lastnosti, ki lahko vodijo k zmagi enega ali drugega igralca. Nekatere od lastnosti, ki jih lahko opazu- jemo, podajamo v nadaljevanju. Razmerje figur na šahovnici Razmerje figur nam za vsakega igralca daje oceno pomembnosti figur na šahov- nici. Po vzoru šahovske literature lahko kraljici pripišemo vrednost 900 točk, tr- dnjavi 500, tekaču 325, skakaču 300 in kmetu 100. Teoretično gledano ima kralj neskončno veliko vrednost, zaradi česar ga v računanju razmerja ne upoštevamo. Za preostale figure posameznega igralca izračunamo vrednost ocena = ∑ N f · V f , kjer N f predstavlja število določenih figur na šahovnici in V f vrednost posamezne figure po prej omenjeni lestvici. Ugodnej- še stanje figur ima nasprotnik z boljšo oceno. Obstajajo tudi položaji figur, kjer bomo žrtvovali figuro (včasih celo kraljico) v zameno za kasnejšo boljše stanje figur oziroma za prednost v igri. Kar nekaj šahovskih programov uporablja tovrstno ocenjevanje kot osnovo. Ker je takšno računanje preprosto, nas navede  Računalništvo Presek 6-3.indd 23 19.5.2006 10:54:43  na misel, da bi v program morda vpletli ocenjevanje še kakšne lastnosti igre, kar večina šahovskih programov tudi počne. Eno izmed dobro znanih šahovskih navo- dil (ne trdimo sicer, da je to pravilo vedno dobro) je, da v kolikor smo v prednosti s figurami, izmenjava figur enake vredno- sti predstavlja napredek naše igre. Zame- njava enega kmeta za nasprotnikovega je pogosto dobra ideja, ker »odpremo« ša- hovnico za druge figure, na primer trdnja- vi. Ne smemo pa pretiravati – kljub vsemu je priporočljivo ohraniti določeno število kmetov na šahovnici zaradi obrambe in/ ali promoviranja v boljšo figuro. Mobilnost figur in nadzor igre Ena od lastnosti matiranja je, da naspro- tnik nima več izbire dovoljenih potez. Intuitivno lahko razmišljamo, da ima- mo z večjim številom možnih potez več možnosti, da najdemo boljšo potezo. Na primer, med tridesetimi možnimi pote- zami bo verjetno lažje najti kakšno boljšo potezo, kot če smo omejeni le na tri mo- žne poteze. Govorimo torej o mobilnosti figur, ki jo lahko zelo preprosto ocenimo: preštejemo število dovoljenih potez za vsakega igralca v danem položaju. Vendarle moramo biti previdni. Izkaže se, da ima takšna statistika majhno vre- dnost. Zakaj? Prvi razlog tiči v dejstvu, da je večina potez brez pravega pomena. Na primer, premik konja nazaj na zadnjo lini- jo je sicer dovoljena poteza, vendar mor-  da popolnoma neproduktivna. Drugi ra- zlog je izbira potez, s katerimi bi na vsak način želeli omejiti mobilnost nasprotni- ka. Šah je timska igra figur in lahko bi se zgodilo, da bi s takšno igro nasprotniku zadali šah in pokvarili svojo obrambno linijo. Nekateri programi uporabljajo celo kompleksnejše funkcije in pripišejo slabo oceno »slabim tekačem in skakačem«: t.j. tistim tekačem, katerih poteze ovirajo veliko število kmetov na poljih iste barve, in tistim skakačem, ki so preblizu robo- vom šahovnice. Prav tako nekateri pro- grami pripisujejo večjo oceno mobilnosti trdnjavam na »odprtih« ali »pol odprtih« površinah, kjer ni kmetov (ali pa vsaj na- sprotnikovih kmetov). Neposredno z mobilnostjo je povezan tudi nadzor nad šahovnico. Pravimo, da ima nadzor nad poljem tisti igralec, ki lahko polje napade z večimi figurami. V iskanju potez se je običajno varneje pomikati po RAÈUNALNIŠTVO nadziranih poljih in nevarneje po poljih, ki jih nadzira nasprotnik. Obstajajo seveda tudi izjeme: premik kraljice na polje, ki ga napada nasprotnikov kmet, je redko do- bra poteza, ne glede na to, na koliko na- činov lahko potem zajamemo kmeta. Ne smemo pa pozabiti tudi na tehniko zape- ljevanja, kjer figuro namerno postavimo na škodljivo mesto, da nasprotnika spe- ljemo stran od pomembnejšega mesta. Razvoj igre Eno starejših pravil igranja šaha je, da manj vredne figure (tekača in skakača) v bitko uvedemo čim hitreje in tako kralju omogočimo rokado, trdnjavi in kraljica pa lahko čim dlje mirujejo, vse dokler jih ne potrebujemo za odločilni napad. Obstaja več razlogov za to: skakači in tekači (ter kmetje) lahko zagotovijo nadzor nad sre- dino šahovnice, podpirajo kraljičine na- pade in se lahko umaknejo ter naredijo prostor za močnejše trdnjave. Funkcija ocene lahko dodeli slabo oceno tudi kateremukoli položaju, kjer kmetje pred kraljem in kraljico še niso bili presta- vljeni. Slabo oceno lahko dobijo tudi ska- kači in tekači, ki preprečujejo pot kraljici; dobro oceno lahko dobijo položaji, kjer je kralj varno ograjen, in slabo oceno, ko še ni ograjen. Ocena razvoja igre je pomemb- na predvsem v otvoritvi igre, kasneje pa postane manj pomembna, ker se po pri- bližno desetih potezah večina potez, ki preprečijo slabe ocene, že zgodi.  napadena polja bele kraljice položaj črnega kralja je kralj napaden? 8 7 6 5 4 3 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 A B C D E F G H logični in 8 7 6 5 4 3 2 1 1 A B C D E F G H 8 7 6 5 4 3 2 1 1 A B C D E F G H Popravek slike 2 iz članka Kako delujejo šahovski programi (drugi del) iz prejšnje številke Preseka.  1 1 Presek 6-3.indd 24 19.5.2006 10:54:43 Astronomija ASTRONOMIJA Položaj kmetov Šahovski velemojstri velikokrat poudar- jajo, da so kmetje duša igre. V zgodovini šahovskih iger lahko celo zasledimo pre- dajo iger po izgubi katerega od kmetov na dobrem položaju. V splošnem pa lah- ko sledimo šahovski literaturi, ki omenja kar nekaj lastnosti (pozitivne in negativ- ne) kmetov: Podvojeni ali potrojeni kmeti v isti li- niji so slabo izhodišče za nadaljnjo igro, ker ovirajo drug drugega. Kmetu tako namesto 100 točk pripišemo na primer le 75 točk. Dva nasprotujoča kmeta, preprečujeta premik drug drugemu, kar je lahko nadle- žna ovira. Kmetje, ki so prešli že tako daleč, da jih nasprotnikovi kmetje ne morejo več napasti, so zelo močni, ker imajo laž- jo pot do konca šahovnice in morebitno promocijo v boljšo figuro. Osamljeni kmetje so lahka tarča, zato prav tako ne dobijo vseh 100 točk. Preveč kmetov na šahovnici omejuje mobilnost figur, zaradi česar posamezen kmet prav tako ni deležen vseh 100 točk. Varnost kralja in tropizem Varnost kralja smo že nekajkrat ome- nili: v otvoritvi in sredi igre je varovanje kralja najpomembnejše in rokada je naj- boljša rešitev za to. Ker pa je ob razvoju igre večina figur na obeh straneh lahko že odstranjena, lahko kralj postane celo najboljša napadalna figura. Puščanje kra- lja v varnem pristanu je lahko v takšnih primerih izguba dragocene napadalne moči. Neposredno z varnostjo kralja je povezan t.i. tropizem, ki predstavlja oceno, kako preprosto lahko katera od figur napade kralja. Običajno jo merimo v smislu raz- dalje, natančna pravila pa so odvisna od        tipa figure. Ne glede na tip figure pa velja načelo: bližje kralju je figura, večji pritisk lahko izvaja na kralja. Omenjene metode ocenjevanja relativno preprosto izračunamo. Izkaže se, da je med vsemi omenjenimi ocena razmerja figur daleč najpomembnejša. Avtorji pro- grama chess 4.5 na primer ocenjujejo, da je velika prednost v položaju, mobilnosti in varnosti kralja vredna manj kot število točk za enega in pol kmeta. Pravzaprav lahko celo vidimo, da lahko šah srednje dobro igramo že zgolj samo na tak način. Za zaključek Mnogi poudarjajo, da bodo računalniki v povprečju igrali bolje od ljudi do leta 2010, potem pa bo njihova sposobnost tako prehitela človeško, da bo primerjava igre med računalnikom in človekom podobna primerjavi vožnje s kočijo in športnim av- tomobilom. Nekateri temu nasprotujejo in poudarjajo, da se bo človeška strategija še veliko časa lahko zoperstavljala raču- nalniškemu iskanju vseh možnih potez. Zavedati se namreč moramo, da je šah težavna igra, še posebej za računalnik. Namen serije treh prispevkov o računal- niškem šahu je bil prav v tem, da spo- znamo zapletenost tovrstnih programov, hkrati pa pridobimo dovolj znanja, da se morda tudi sami lotimo razvoja takšnega programa. Viri http://www.geocities.com/ SiliconValley/Lab/7378/comphis.htm http://sl.wikipedia.org/wiki/ Sahovski_računalniški_programi http://www.cs.biu.ac.il/�$davoudo/ tutorials.html \ \    Presek 6-3.indd 25 19.5.2006 10:54:43