i i “1615-Kaucic-Kako” — 2010/8/26 — 11:54 — 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 2 Strani 25-27 Branko Kaučič: KAKO DELUJEJO ŠAHOVSKI PROGRAMI (PRVI DEL) Ključne besede: računalništvo, miselne igre, programske rešitve, šah. Elektronska verzija: http://www.presek.si/33/1615-Kaucic.pdf c© 2005 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. 25 Kako delujejo šahovski programi (prvi del) RAÈUNALNIŠTVO Šah je igra s »popolno informacijo«, ker sta oba igralca seznanjena s celotnim stanjem igre ves čas igranja. Že s pogledom na igralno ploščo je namreč razvidno, katere figure so še prisotne in kakšen je njihov položaj. Takšnih iger je še več (križci-krožci, go, backgammon), a igre, kot so po- tapljanje ladjic in poker, ne sodijo v to kategorijo. Pred vami je prvi prispevek iz serije prispevkov o računalniških programih za igranje šaha in strategij za podobne igre s popolno informa- cijo. Opisane bodo najpomembnejše tehnike, ki jih uporabljajo nekateri od najboljših šahov- skih programov, vključno z legendarnim Deep Blue (več o tem v nadaljevanju). Večina teh- nik, ki bodo omenjene, so namenjene skoraj vsem igram s popolno informacijo, čeprav se podrobnosti seveda razlikujejo od igre do igre. Poteze igralcev in ovrednotenje položaja so »Greva še eno partijo šaha?« Nekako tako je zvenelo iz ust mo- jega očeta, ko me je v osnovni šoli učil te kraljevske igre. Nekaj let intenzivnega igranja, polna glava miselnih vzorcev, uporaba računalnika in predvsem dejstvo, da očeta nikakor nisem uspel premagati, me je sčasoma privedlo do razmišljanja, kako napi- sati svoj šahovski program. Morda so podobno razmišljali tudi ljudje, ki so se podobnega podviga lotili že leta pred mano, za- gotovo pa so se soočili s spoznanji, ki sledijo. 64 64 R A È U N A L N IŠ T V O 8×8 8×8 8×8 8×88×8 8×8 8×8 8×8 8×8 8×8 8×8 8×88×8 8×8 8×8 8×8 8×8 8×8 8×8 8×88×8 8×8 8×8 8×8 alfa–beta minmax 6×6 200.000.000 /s 6×6 Branko Kaučič Presek 2-4-z-pop.indd 25 9.11.2005 15:15:08 Process Cyan Process Magenta Process Yellow Process Black PANTONE 3395 CVC 26 mu številu nepotrebnih izračunov. Podrobneje si ga bomo ogledali drugič. Istega leta je s pomočjo tega algoritma računalnik, s programom nss, prvič pre- magal človeka. Sledila je vrsta dosežkov, seznam nekaterih naj- de bralec v [1]. Med najodmevnejše med njimi sodi partija takratnega svetovnega šahovskega prvaka Garija Kasparova z računalnikom Deep Blue. Leta 1997 je računalnik zmagal z rezultatom 3,5:2,5, medtem ko je leto prej slavil Kasparov. Deep Blue je predstavljal paralelni računalnik s 30 vozlišči s skupaj 480 posebej namenskimi šahovskimi čipi. V tistem času je bil 259-ti najboljši računalnik na svetu. Šahovski program je bil napisan v program- skem jeziku C in je zmogel izračunati približno 200.000.000 položajev v sekundi, pri izboljševanju delovanja programa pa je sodelovalo kar nekaj vele- mojstrov. \ Zgradba šahovskih programov Uspešen šahovski program sestavljajo naslednje, med seboj tesno prepletene komponente: način, kako v pomnilniku računalnika predsta- vimo igralno ploščo (šahovnico), ki predstavlja stanje igre; pravila, ki določajo dovoljene poteze, da igramo brez goljufanja (in da preverjamo, da nasprotnik ne goljufa); tehniko, ki med vsemi dovoljenimi potezami iz- bere neko potezo (potezo raje izberemo po ne- kem ključu, kakor naključno); način primerjave različnih potez in položajev fi- gur med seboj in uporabniški vmesnik. V prispevkih bomo obravnavali vse zgoraj našteto, razen uporabniškega vmesnika. \ Predstavitev igralne plošče V zgodnjem obdobju računalniških šahovskih pro- gramov je bila količina pomnilnika izredno omejena (programi so smeli uporabiti največ 8K pomnilnika) in najpreprostejše predstavitve šahovnice so bile najučinkovitejše. Le-ta je bila običajno kar polje velikosti 8×8 zlogov: prazno celico (brez figure) je RAÈUNALNIŠTVO namreč odvisni od pravil igre, ki jo igramo (oziroma poskušamo napisati računalniški program zanjo). \ Pomembnejši mejniki zgodovine šahovskih programov Ideja stroja, ki obvlada šah, presenetljivo ne sovpada z začetki računalništva, temveč sega precej nazaj, v osemnajsto stoletje, po- vezana je z eno večjih prevar človeštva. Okoli leta 1776 je za zabavo cesarice Marije Tere- zije madžarski baron Wolfgang von Kempe- len skonstruiral mehanski stroj. V njem se je skrival človek, vešč mojstrovin šaha, ki je preko vzvodov premikal lutko Turka in s tem figure. Stroj je menjal lastnike, njegova skrivnost pa je dolgo ostala neodkrita. Med prve stroje, ki so dejansko znali odi grati vsaj del partije šaha, štejemo mehanski stroj Ajedrecista Španca Torresa y Queve- da. Stroj je znal odigrati končnico (zaključek igre) s kraljem in trdnjavo proti kralju. Leta 1912 je Torres y Quevedo predstavil prvo in leta 1920 izboljšano verzijo stroja. Stroja še danes delujeta v madridskem muzeju. Prvi šahovski program je leta 1947 napisal matematik Alan Mathison Turing, čeprav zgolj na papirju. Moč računalnika je nado- mestil kar sam in za izračun ene poteze porabil več kot pol ure. Leta 1949 je prav tako znamenit matematik Claude Shannon opisal, kako razviti šahovski program. Ugo- tovil je, da težavo predstavlja izredno veli- ko število izračunov položajev figur. Ločil je strategijo A, kjer pregledamo »vse« možne poteze (osnova algoritmu minmax), in stra- tegijo B, kjer pregledamo le določene pote- ze. Na ta način tudi danes ločimo šahovske programe. S šahovnico velikosti 6×6 polj in brez lovcev so se na računalniku maniac ukvarjali tudi ameriški znanstveniki. Leta 1958 beležimo prvi pomembnejši dosežek treh znanstvenikov iz univerze Carnegie- Mellon (Newell, Shaw in Simon). Predla- gali so postopek, imenovan algoritem alfa- beta, s katerim se je možno izogniti velike- Presek 2-4-z-pop.indd 26 9.11.2005 15:15:11 Process Cyan Process Magenta Process Yellow Process Black PANTONE 3395 CVC 27 predstavljala vrednost 0, črnega kralja vrednost 1, črno kraljico vrednost 2. Z uvedbo 64 bitnih raču- nalnikov so v takratni Sovjetski zvezi iznašli učin- kovitejše predstavitve, t. i. »bitne plošče«. Gre za 64 bitno besedo (1 bit za eno celico), ki vsebuje informacijo enega vidika stanja igre. Na primer, ena bitna plošča vsebuje »množico celic, ki jih za- sedajo črni kmetje«, druga vsebuje »množico celic, kamor se lahko prestavi črna kraljica«, tretja vse- buje »množico celic, ki jih trenutno napadajo črni konji«. Bitne plošče so vsestranske in omogočajo hitrejše računanje položajev. Mnoge operacije, ki se med igro zelo pogosto ponavljajo, se namreč lahko implementirajo kot preproste logične operacije nad bitnimi ploščami. \ Premikanje figur Pravila igre določajo, katere poteze sme opraviti beli in katere črni igralec. V nekaterih igrah je že s pogledom na igralno ploščo možno določiti dovo- ljene poteze. Pri igri križci-krožci, na primer, vsa- ka prazna celica predstavlja dovoljeno potezo. Pri šahu, žal, ni tako preprosto. Vsaka figura ima svoja pravila premikanja in zajemanja drugih figur, pre- povedano je pustiti kralja v šahu, poznamo tudi »en passant« poteze, promoviranje kmetov v višje figure, rokade, ki morajo ustrezati še dodatnim po- gojem. Izkaže se, da je generiranje potez figur prav- zaprav eden najtežjih vidikov (računsko zahtevnih in kompleksnih zaradi samih pravil) šahovskega programiranja. Pravila igre k sreči omogočajo, da nekatere operacije pripravimo vnaprej. \ Iskalne tehnike V šahovski program je treba zapisati tudi najbolj očitno. Računalnik namreč sam od sebe ne zna do- ločiti, katera od dovoljenih potez je »dobra« in ka- tera »slaba«. Velja preprosto razmišljanje: najlažje jih med seboj razlikujemo, če poznamo njihove po- sledice. Tvorimo zaporedje potez, na primer štiri za vsako igralno stran (skupaj torej osem) in pogleda- mo stanje igralne plošče. To je tudi osnovni princip algoritma minmax, ki predstavlja korenine vsakega šahovskega programa. Njegova učinkovitost je na žalost odvisna od povprečnega števila dovoljenih potez in števila potez, ki jih generiramo (imeno- van tudi globina). Število možnih položajev tako raste izredno hitro in vloženega je bilo precej truda v algoritme, ki zmanjšajo število računanih položajev. Tak je na primer prej omenjeni al- goritem alfa-beta. Vzrok mnogih glavobolov šahovskih pro- gramerjev je tudi t. i. »problem horizonta«. Zamislite si, da vaš program išče osem po- tez vnaprej in ugotovi, da vam bo naspro- tnik v osmi potezi vzel kraljico. Slabo stanje igre torej. Žal pa ne vidi, da bi to pravzaprav bila zvita poteza, s katero bi nasprotnik umaknil eno od svojih figur in vam v deveti potezi omogočil matiranje. Najboljše mož- no stanje igre torej. Namesto da bi izkoristil to priložnost, se bo program odločil raje za drugo potezo in tako »obvaroval« kraljico. Izkaže se, da je primerno število preverjenih potez težko določiti in uporaba vedno iste- ga števila potez zelo verjetno vodi do slabe igre. \ Ovrednotenje položaja figur Program potrebuje tudi možnost ocenjeva- nja, ali določeni položaj figur vodi v zmago ali ne. Ovrednotenje je v veliki meri odvis- no od pravil igre, najpomembnejše v šahu pa predstavlja število in tip figur na plošči. Že en kmet več lahko za dobrega igralca pomeni zagotovljeno zmago. Razviti upo- rabno funkcijo ovrednotenja položaja figur je težka naloga in predvsem to loči dobre šahovske programe od slabih. Sedaj, ko v grobem poznamo vse kompo- nente šahovske sestavljanke, se bomo v naslednjih prispevkih vsake od njih lotili ne- koliko podrobneje. \ Viri http://www.geocities.com/SiliconValley/ Lab/7378/comphis.htm http://en.wikipedia.org/wiki/ sahovski_racunalniski_programi http://www.cs.biu.ac.il/~davoudo/ tutorials.html RAÈUNALNIŠTVO Presek 2-4-z-pop.indd 27 9.11.2005 15:15:12 Process Cyan Process Magenta Process Yellow Process Black PANTONE 3395 CVC