i i “1631-Kaucic-Kako” — 2010/8/26 — 11:56 — 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 5 Strani 23–26 Branko Kaučič: KAKO DELUJEJO ŠAHOVSKI PROGRAMI (DRUGI DEL) Ključne besede: računalništvo, miselne igre, programske rešitve, šah, postopek minimax. Elektronska verzija: http://www.presek.si/33/1631-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.  Kako delujejo šahovski programi (drugi del) Branko Kaučič V prvem delu (Presek 2) smo si zadali nalogo napisati raču- nalniški šahovski program in si že ogledali glavne gradnike vsakega šahovskega programa. Povedali smo tudi, da se isti gradniki uporabijo za katerokoli računalniško igro s popolno informacijo. Stopimo v tem prispevku korak dlje in si nekoliko podrobneje poglejmo še osnove predstavitve šahovnice, pre- mikanja figur ter iskanja naslednje poteze. \ Na katerem polju stoji črna kraljica Na začetku naj poudarimo, da že več kot trideset let pametne glave niso odkrile nič revolucionarnega na tem področju (morda uspe vam!). Predstavljenih je bilo kar nekaj različnih zamisli kako bi bilo mogoče pred- staviti položaj figur v računalniku. Zadnjo tako zamisel že uporabljajo vsi boljši šaho- vski programi, ker omogoča izredno hitro ge- neriranje potez obeh igralcev. V 60-tih letih je bil pomnilnik računalnikov precej bolj cenjen kot dandanes; kompak- tnejša, kot je bila predstavitev šahovnice, boljša je bila. Najočitnejša rešitev je bilo polje velikosti 8�8, kjer je vsak element polja predstavljal svojo celico šahovnice. V celici je zapisana celoštevilčna kon- stanta (velikosti enega zloga), ki na tem mestu predstavlja kodo figure. Hitro se je pojavilo kar nekaj izboljšav te predsta- vitve, od katerih sta bili najpopularnejši naslednji dve: Šahovski program sargon je polje ve- likosti 8�8 razširil na 12�12 z dvema vr- stama celic na vsaki stranici šahovnice (slika 1). Dodatne celice so predstavljale nedovoljene položaje in so omogočile hitrejše preverjanje nedovoljenih potez (npr. skok skakača izven šahovnice). Šahovski program mychess je za ša- hovnico namesto 64 uporabil 32 zlo- gov, od katerih je vsak predstavljal po- Slika 1. Šahovnica, ki jo je uporabljal sargon. Presek 33 (2005/2006) 5, strani 23–26 8 7 6 5 4 3 2 1 A B C D E F G H RAÈUNALNIŠTVO Presek 5-koncna.indd 23 28.3.2006 12:06:51  RAÈUNALNIŠTVO ložaj figure na šahovnici. Zajeto figuro je označevala vnaprej definirana kon- stantna vrednost, preglavice programu pa je povzročalo promoviranje kmeta. Danes bi bila takšna predstavitev pri- merna le za začetno razmišljanje o šahov- skem programu oz. če bi program pisali za napravo, ki je s pomnilnikom precej omejena (mobilni telefon, dlančnik). Do revolucionarne zamisli predstavitve šahovnice se je v poznih 60-tih letih do- kopal tim Kaissa iz takratne Sovjetske zveze (kaissa je sicer tudi šahu podobna igra). Zamisel, imenovana bitna plošča, je 64 bitni podatek, ki si ga lahko pred- stavljamo kot polje bitov velikosti 8�8. Z več bitnimi ploščami lahko predstavimo stanje igre v celoti. Na primer, ena plošča predstavlja položaj belih kmetov, druga plošča predstavlja položaj belih trdnjav, tretja položaj belih skakačev, položaj na- padenih celic ipd. Operacija logičnega se- števanja dveh bitnih plošč omogoča na- daljne izračune v izjemno kratkem času. Za dvomljivce pokažimo to na naslednjem primeru: v danem položaju figur nas zani- ma, ali je črni kralj v šahu zaradi bele kralji- ce. V primeru šahovnice brez bitne plošče bi zagotovo uporabili naslednji postopek: Na šahovnici poiščemo položaj bele kraljice, kar v najslabšem primeru po- meni, da preverimo vseh 64 celic ša- hovnice. Za vsako celico, kamor lahko poma- knemo kraljico (v vseh osmih smereh), preverimo, ali se tam nahaja črni kralj. Bližje kot je kraljica robu šahovnice, več celic preverimo. V najslabšem prime- ru preverimo kar lepo število celic in v nobeni od teh celic ne najdemo črnega kralja. V primeru šahovnice z bitnimi ploščami je postopek enostavnejši: Vzamemo bitno ploščo, ki predstavlja položaj bele kraljice. Na podlagi te plošče vzamemo bitno ploščo, ki predstavlja celice, ki jih napa- da bela kraljica. Izračunamo logični in te plošče in bitne plošče, ki predstavlja položaj črnega kralja. Če je rezultat različen od 0 (vsaj ena enica se pojavi v polju), potem bela kraljica s šahom napada črnega kralja (slika 2). Ker je večina uporabljenih bitnih plošč v pomnilniku računalnika in ker operacijo logičnega in izvedemo praktično v tre- nutku, je računanje s takšno zamislijo mnogo hitrejše od prejšnje. \ Kam lahko premaknem črno kraljico Generiranje potez (odločanje, katere po- teze so dovoljene v danem položaju fi- gur) in ovrednotenje njihovega položaja je kompleksnejši del vsakega šahovske- ga programa. Igralec ima namreč večino časa na voljo vsaj 30 ali več potez, od ka- terih nekatere vodijo k ugodnemu razple- tu igre, druge pa v izgubo igre. Izkušeni igralec bo med njimi zlahka prepoznal ugodnejše poteze, obenem pa se zave- dal, da je večina potez (od vseh možnih) premalo ugodnih za nadaljevanje igre. A kako takšno razmišljanje vcepiti našemu računalniku? V nadaljevanju podajamo opis dveh strategij generiranja potez in navodilo kdaj ju uporabiti, pred tem pa se posvetimo še pomožni tehniki v ša- hovskih programih, ki jo prav tako upora- bljajo vsi boljši programi. Premikalne tabele – zakladnica znanja V šahu pogosto na več različnih načinov dosežemo isti položaj figur. Na primer, vseeno je, ali igramo najprej P-K4 in nato P-Q4, ali pa najprej P-Q4 in nato P-K4. V obeh primerih je položaj figure na ša- hovnici enak. Kot že rečeno, vsak položaj figur oz. stanje šahovnice ovrednotimo. Razmišljajmo dalje – če smo s takšnim ali drugačnim naporom izvedli ovrednotenje, zakaj bi ta izračun ponavljali, ko naletimo na že znano stanje figur. Podobno so raz- mišljali tudi drugi. Odkar je v uporabi Gre- enblattov program mac hack vi, vsi boljši šahovski programi uporabljajo premikal- ne tabele (ang. transposition tables). Te tabele, ki so pravzaprav zbirka ovredno- tenih stanj figur, v največji možni meri preprečujejo ovrednotenje že znanega stanja figur. Ko ovrednotimo novo stanje figur, ga shranimo v takšni tabeli. Vsakič ko naletimo na novo stanje figur, najprej v tej tabeli preverimo, ali se je takšno sta- nje že pojavilo. Uporabimo že izračunano informacijo in se izognemu nepotrebne- mu računanju. V šahovskih programih je namreč vsak privarčevani trenutek zlata vreden. Večja tabela oz. večje število raz- ličnih položajev figur je seveda zaželeno; uporabnost tabele se pokaže, kadar le-ta vsebuje več tisoč položajev. Pri milijon položajih bi imeli že pravo zakladnico znanja, a žal takšna velikost za računal- niške programe ni sprejemljiva. Vsi boljši programi premikalno tabelo pri otvori- tvah (začetne poteze) napolnijo z najbolj pogostimi položaji figur takoj, ko prične- mo z novo igro šaha. Pri igranju končnic 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 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 Presek 5-koncna.indd 24 28.3.2006 12:06:51  RAÈUNALNIŠTVO Slika 2. Uporaba bitnih plošč (zadnje poteze šaha) v tej tabeli najdemo ovrednotena stanja figur za skoraj 90 od- stotkov vseh primerov. Nazaj k črni kraljici Vrnimo se h generiranju potez. Leta 1949 (presenetljiva letnica, če upoštevamo dejstvo, kdaj je bil predstavljen prvi ra- čunalnik) je Claude Shannon opisal dva postopka igranja šaha: preverimo vse možne poteze in od vseh možnih potez spet vse možne poteze, preverimo le »najboljše« poteze in od- govore na najboljšo potezo nasprotni- ka na te poteze. Idealno bi bilo, da bi preverili vse možne poteze in med njimi izbrali najboljšo. Žal že nekaj osnovne matematike pokaže, da bi najboljšo potezo iskali morda tudi nekaj dni (ali več). Zatorej moramo po- skrbeti, da poteze generiramo hitro in kolikor se le da učinkovito. Ločimo dve strategiji: selektivno generiranje, kjer raziščemo položaj figur na šahovnici, predlagamo manjše število najbolj verjetnih potez, medtem ko vse ostale poteze ignorira- mo; inkrementalno generiranje, kjer generi- ramo nekaj potez in upamo, da se za poteze izkaže, da so, ali tako dobre ali pa tako slabe, da se razmišljanje o njih, in o nadaljnjih potezah izkaže za pri- merno oz. neprimerno. Ljudje igramo s pomočjo selektivnega generiranja – razmišljamo le o potezah, ki se nam zdijo najboljše. Na žalost rezulta- ti dokazujejo, da se programi na podlagi selektivne strategije ne obnesejo najbo- lje. Dosežejo sicer stopnjo zahtevnosti srednje dobrih šahistov, a večkrat sredi najmanj primernega položaja generirajo katastrofalne poteze. Dobro znan primer tovrstne strategije je delo svetovnega šahovskega prvaka Mikhaila Botvinnika, ki je skupaj z ekipo programerjev razvijal šahovski program, ki bi čim bolje opona- šal razmišljanje odličnega šahista. Pro- gram je generiral le nekaj potez, za katere je bil prepričan, da so najboljše in segajo v veliko globino (število naslednjih potez). Program žal ni dosegel vidnih uspehov. Sredi 70-ih sta Slate in Atkin dokazala, da tovrstni način ni primeren, in selektiv- no generiranje je v šahovskih programih skoraj izginilo. Poiskati je torej potrebno generiranje potez, ki bo učinkovitejše od selektivne- ga generiranja in hitrejše od generiranja vseh možnih potez. Običajno uporabimo naslednji postopek: v danem položaju figur poiščemo vse dovoljene poteze, poteze po nekem kriteriju uredimo, s čimer upamo, da bomo pospešili na- slednji korak, preverjamo generirane poteze. Poteze preverjamo po eno naenkrat, do- kler ne preverimo vseh potez. Pri vsaki potezi preverjamo tudi nekaj naslednjih potez in pri tem lahko ugotovimo, da po- teza vodi v slabo igro. Kakor hitro to ugo- tovimo, prekinemo preverjanje »slabe« poteze. Kot že rečeno, poteze uredimo. Z dobro urejenimi potezami hitreje najdemo do- bro potezo in hitreje prepoznamo slabo potezo. Vsi boljši šahovski programi po- teze najprej razdelijo v tri skupine: figu- re, ki napadajo, napadene figure in figure v mirnem položaju. Programi običajno najprej preverjajo poteze, ki zajamejo na- sprotnikove figure, začenši z zajemanjem nasprotnikovih najmočnejših figur. Temu sledi promoviranje kmetov, kar lahko precej spremeni razmerje figur na šahov- nici. Po drugi strani pa napadene figure običajno vodijo do prekinitve preverjanja poteze, čeprav vsak izkušen šahist pozna tudi trik žrtvovanja figure, omenjen v prejšnjem prispevku. Izkaže se, da lahko zmanjšamo število vseh možnih prever- janj iz n na √– n. Zavedati pa se moramo, da to ne pomeni, da določenih potez med igro ne bomo preverili, temveč da bomo njihovo preverjanje najverjetneje le pre- stavili na kasneje. \ Kdor išče, ta najde Kaj smo se do sedaj naučili? Vemo, da imamo različne predstavitve šahovnic v računalniku, ki se izkažejo predvsem pri generiranju potez figur. Predpostavimo tudi, da znamo ovrednotiti stanje fi- gur na šahovnici, ki kaže v prid nam ali nasprotniku. Še vedno pa nam manjka znanje, kako se med generiranjem potez odločimo o naslednji potezi, kar imenu- jemo iskanje poteze. Tehniki, ki ju bomo omenili, nista omejeni zgolj na šahovski program, ampak na igre dveh igralcev s popolno informacijo. V nadaljevanju se bomo torej posvetili razmišljanju, kateri od igralcev je boljši in kateri slabši oz. ali poteze vodijo v zma- go ali poraz. Roko na srce, v šahu je tako velika množica vzorcev, pravil in izjem, da tudi najboljši šahovski programi v neka- terih trenutkih zatajijo. Dobri so »le« v hi- trem izračunavanju, kar moramo čim bo- lje izkoristiti. Programi torej namesto, da z logičnim razmišljanjem generirajo dobre poteze, generirajo vse možne poteze, od teh potez vse možne poteze nasprotnika, od nasprotnikovih potez spet vse svo- je poteze itn. Zamislimo si npr. potezo skakača na polje, od koder lahko napade trdnjavo in kraljico. Dober šahovski pro- gram bo za nekaj potez vnaprej preveril, kaj se bo zgodilo, če bo nasprotnik zašči- til trdnjavo, in kaj, če bo zaščitil kraljico. Ker v tem postopku iskanja preverimo vse možne poteze (naše poteze in od- govore nasprotnika), se bomo zagotovo lahko odločili za najboljšo potezo. Globlje, kot bomo iskali, bolje se lahko odločimo. Opozorimo pa vendarle, da smo omejeni z globino iskanja, torej s številom naših in nasprotnikovih potez, zato se za najbolj- šo potezo odločimo na podlagi zmožno- sti. Lahko smo namreč omejeni s časom iskanja poteze in/ali z veli- kostjo razpoložljivega pomnilnika. Presek 5-koncna.indd 25 28.3.2006 12:06:51  RAÈUNALNIŠTVO Postopek minmax Zamislimo si, da v igri sodelujeta dva igralca – prvega imenujmo Max, njego- vega nasprotnika pa Min. Predpostavi- mo, da je ovrednotenje figur funkcija, ki vrne pozitivno vrednost, kadar je v pred- nosti Max, negativno vrednost, kadar je v prednosti Min, in vrednost 0, kadar je enakovredno stanje sil na šahovnici. Naloga Maxa je, da izbere potezo, ki bo povečala vrednost stanja igre, medtem ko je naloga Mina, da izbere potezo, ki bo zmanjšala vrednost stanja igre. Predpo- stavimo tudi, da igralca poteze izbirata brez napak, torej da se vedno odločita za potezo, ki je v prid igralcu samemu in ne nasprotniku. Oglejmo si to na primeru. Recimo, da je na potezi Max in ima na voljo potezi a in b. Ne glede na izbiro poteze je za njim na vrsti Min, ki lahko izbere potezo c ali d. Zamislimo si vse možne kombinacije potez (imenujemo jih iskalne poti) in jih ovrednotimo (slika 3) – če Max izbere potezo b in Min potezo c, je stanje igre ovrednoteno z 9. Kako Max izbere potezo, ki jo bo igral? Max predvideva, da bo Min vedno odigral najboljšo možno potezo. Zatorej, če bo igral potezo a, bo Min odgovoril s potezo d, kar bi privedlo do vrednosti –10 (zmaga Min). Ve pa tudi, če bo igral potezo b, bo ne glede na potezo Mina (c ali d) stanje igre njemu v prid. Brez nadaljnjega se bo Max odločil za potezo b, čeprav bi lahko imel boljše stanje igre, če bi izbral potezo a in upal, da bo Min izbral potezo c. Ampak, kot že rečeno, Min bo vedno izbral zase najboljšo potezo, kar zagotovo ne bo c. Težava postopka minmax, ki morda ni ta- koj razvidna v tem preprostem primeru, nastopi, kadar obstaja eksponentno šte- vilo poti, ki jih moramo preveriti. Ločimo dva faktorja, ki opisujeta naraščanje šte- vila možnih poti: globina iskanja, ki predstavlja število zaporednih preverjenih potez. Globina 6 pomeni tri poteze igralca Max in tri poteze igralca Min. Vejitveni faktor, ki predstavlja število možnih potez vsakega igralca na dani globini. Zgornji primer je imel vejitveni faktor in globino iskanja enako 2, pri igranju šaha pa imamo v sredini igre vejitveni fak- tor okoli 35 potez in iskanje v globino 8 potez. 358 predstavlja že neverjetnih 2.251.875.390.625 različnih poti! Si dr- znete računati poteze v globino 9 ali celo 10? K sreči obstajajo načini, da ne prever- jamo vseh možnih poti. Postopek alfabeta V postopku alfabeta postopek minmax privedemo do obvladljive situacije. Reci- mo, da smo najprej preiskali stanje igre, ko Max izbere potezo b. Vemo, da bo v najslabšem primeru stanje igre vsaj 8. Nadaljujemo s preverjanjem poteze a tako, da najprej preverimo potezo d. Pot nas vodi do rezultata –25, kar je za Maxa nezaželeno stanje igre. Vemo tudi, da bo ne glede na vrednost pri potezi c stanje igre vsaj –25. Če bo vrednost stanja pri potezi c namreč večje od –25, bo Min iz- bral potezo d, sicer bo izbral potezo c. Za- kaj bi torej nadaljevali s pregledovanjem preostalih potez na poti, če že imamo informacijo, da je igralec Min v boljšem položaju? Osnovna ideja postopka alfabeta je, da ko enkrat generiramo dobro potezo, v iskanju poti takoj odstranimo vsa na- daljnja računanja takoj, ko naletimo na slabše stanje igre. Izkaže se, da je v šahu ogromno takšnih potez. S pomočjo pre- mikalnih tabel, vejitvenega faktorja 23 in globine 8 s postopkom alfabeta v sredi- ni igre običajno preverimo le še približno 2000 različnih poti. \ Naslednjič Pustimo za naslednjič nadaljnjo opti- mizacijo postopka alfabeta in nekatere pomembne malenkosti. Do takrat pa se lahko poigrate s postopkoma minmax in alfabeta ter razmislite o postopku za igro z več kot dvema igralcema. \ Viri http://www.geocities.com/ SiliconValley/Lab/7378/comphis.htm http://en.wikipedia.org/wiki/ šahovski_računalniški_programi http://www.cs.biu.ac.il/~davoudo/ tutorials.html Slika 3. Postopek minmax trenutno stanje a b 25 -10 9 8 dc dc Presek 5-koncna.indd 26 28.3.2006 12:06:52