liiloriii.it i(:i st. 3 letnik 1978 43 računalniško gene= niranje popolnih strategij za šahovske končnice mogams i.bratko UDK 681.,l:7y'1.1 Institut J.Štefan in Fakulteta za elektrotehniko, Univerza v Ljubljani, Ljubljana V članku je opisan algoritem, ki v smeri od zadaj naprej zgradi prostor vseh možnih pozicij dane igre in za vsako pozicijo določi njeno vrednost. S tem algoritmom smo izračunali popolno strategijo za šahovsko končnico kralj in trdnjava proti kralju in skakaču, kar je zaradi kompleksnosti izračuna zahtevna programska naloga. Rezultati so zanimivi tudi s stališča some šahovske igre, ker je optimalna igra v tej končnici v splošnem že preveč težavna za šahovske mojstre. Ta eksperiment vodi k zaključku, da je na tak način možno v celoti reševati končnice z največ s pet do šest figurami, medtem ko postane od tu dalje kompleks­ nost izračuna že praktično nesprejemljiva in je potrebna uporaba metod umetne inteligence. COMPUTER GENERATION OF COMPLETE STRATEGIES FOR CHESS END-GAMES. The articie presents a backv/ard-chaining algorithm for the generation of the spoce of ali possible positions for a given game and for each position its value is computod. Using this algorithm, a complete strateg/ for the king ond rook vs. king and knight chess ending was generated, which proved to be o progromming task of considerable difficult/. The results ore of interest olso from tl)e chess game point of view since optimal play in this ending is beyond chess-master's skill. A conclusion of the experiment is that endings with at most 5 or 6 pieces con stili be completel/ solved in this way, vvhile for more complex endings the computation becomes infeosable ond from here on artificial intelligence methods are to be employed. UVOD Znani so razmeroma enostavni algoritmi, ki bi načeloma po­ polnoma pravilno igrali šah. Mednje sodi npr. algoritem, ki preišče vsa možno nadaljevanja iz dane pozicije, dokler ne naleti na končne pozicije, tj. take, ki so dobljene, iz­ gubljene ali remi po pravilih igre (npr. eden izmed kraljev v matu). Imenujmo tak algoritem "algoritem A". Hitro po­ stane očitno, da algoritem A praktično ni izvedljiv zaradi svoje časovne kompleksnosti. V povprečju je v vsaki šahovski poziciji možnih okrog 35 potez. Tako moro algoritem A v dani začetni poziciji, kjer je npr. no potezi beli, pregledati 35 potez belega; za vsako od nastalih pozicij moro upoštevati po 35 možnih od­ govorov črnega itd. Tako mora za preiskovanje samo do glo­ bine ene cele poteze (tj. dveh polpotez, belega in črnega) pregledati okrog 1000 pozicij, za vsako naslednjo potezo v . globino pa število pozicij naraste še za faktor 1000. Če optimistično ocenimo, do lahko računalnik generira po eno legalno potezo v eni mikrosekundi, potem bi potrebovali za izračun najboljše poteze v začetni šahovski poziciji po algo­ ritmu A čas v velikostnem razredu, ki presega 10''^'-' let (starost našega vesolja je približno 10'0 let). Algoritem A preiskuje možna nadaljevanja v smeri naprej od dane začetne pozicije proti končnim pozicijam. Drugi algo­ ritem, ki tudi v načelu rešuje šahovsko igro, preiskuje pro­ stor možnih pozicij v smeri nazaj. Imenujmo ga algoritem B. Algoritem B generira popolno strategijo npr. za belega tako, da generira najprej vse pozicije, ki so po definiciji dobljene za belega, npr. črni kralj v matu. Te pozicije so dobljene v O polpotezah (slika 1). Iz vseh teh pozicij poišče vzvratne poteze belega in tako dobi množico vseh pozicij, ki so dobljene zo belega v eni polpotezi. Zatem poišče vse pozi­ cije s črnim na potezi, v katerih vse možne poteze črnega vodijo v pozicije, dobljene zo belega v eni polpotezi. Tako imamo množico vseh pozicij, dobljenih za belega v dveh polpotezah. Izhajajoč iz te množice lahko prejšnji postopek ponovimo in dobimo pozicije, dobljene v 3 polpotezah, 4 polpotezah itn. Kot končni rezultat algoritma B dobimo množico vseh dobljenih pozicij, pri čemer za vsako pozicijo vemo tudi število polpotez, potrebnih do zmage ob najboljši obrambi nasprotnika. Tako klasificirana množica možnih po­ zicij nam omogoča ne samo pravilno igro temveč tudi opti­ malno Igro, optimalno v tem smislu, da dobljeno pozicijo privedemo do zmage v minimalnem številu potez. Ker je vseh možnih šahovskih pozicij okrog lO'*'' ( npr. Berliner 1978) in ker moramo pri izvajanju algoritma B hra­ niti vsaj vse dobljene pozicije, je jasno, da tudi algoritem B. za celotno šahovsko igro ni izvedljiv. Možno pa je z algo­ ritmom B rešiti končnice z manjšim številom figur. Tako je npr. v končnici s tremi figurami, npr. kralj in kmet proti kralju (kratko: končnica KPK), možnih manj kot 2x64^ po­ zicij (ki se med seboj razlikujejo po položaju treh figur na šahovnici in po tem, kdo je no potezi). Zaradi simetrije lahko to število v končnici KPK reduciramo še za faktor 2 in tako dobimo problemski prostor z okrog 200.000 legalnimi pozicijami, ki ga je mogoče praktično obvladati z algorit­ mom B. Znana tovrstna rešitev te končnice je opisana v CIarke (1977). Če dodamo eno figuro, se velikost problem­ skega prostora poveča približno za faktor 64, kompleksnost algoritma B pa raste z večanjem števila figur še hitreje. Kompleksnost algoritma A raste eksponencialno z globino iskanja v smeri naprej. Kompleksnost algoritma B pa raste eksponencialno s številom figur, prisotnih v končnici, ki jo rešujemo. Jasno je, da postane zaradi eksponencialne rasti tako kompleksnost algoritma A kot algoritma B praktično nesprejemljiva že za razmeroma majhno globino iskanja ozi­ roma za razmeroma majhno število figur v končnici. Od teh dveh mejnih vrednosti naprej šahovske igre ne moremo več programirati s premočrtnimi eksaktnimi olgoritmi, kot sto algoritmo A in B, temveč z uporabo hevrističnih metod ozi­ roma metod umetne inteligence. 44 Nivo v žtovUu poliJOt07, do 7;mBp;e 5 ki kažejo no to, da je popolnoma pravilna igro v tej na videz enostavni končnici že izven domefa šahovskih moj- sfrov. Celo obsežrKi obravnava te končnice v klasični Fineovi knjigi o šahovskih končnicah je polno netočnosti. Primer je na sliki 2. O pozicijo z belim na potezi 0 pozicije 3 črnim na potezi poteze optimalne igre poteze nazaj, ki vodijo v za belega nedobljene pozicije ob optimalni igri črnega SI. 1; Grafični prikaz delovanja algoritma B. Algoritem B generira pozicije od spodnjih nivojev navzgor Postavljata se vpraianji: (o) Do kakšne globine iskanja je algoritem A še praktično izvedljiv? (b) Za kolikšno število figur v končnici je algoritem B še praktično izvedljiv? Na vprašanje (a) dajejo odgovor izkušnje s turnirskimi šahov­ skimi programi. Trenutno najmočnejši In najhitrejši šahovski program, CHESS 4.7, preišče (če igro pod turnirskimi igralni­ mi pogoji, tj. po nekaj minut rozmišljonjo na potezo)vse variante do globine 8 al! 9 polpotez, odvisno od tipa pozici­ je, pri čemer teče no hitrem računalniku CYBER 176. Pri tem je algoritem A implementiran z znanim olfa-beta postopkom (npr. Knuth, Moore, 1975'), ki je hitrejši od algoritma A, daje po enak rezultat kot A. Izkušnje kažejo, do bi bilo tudi s precej hitrejšim računalnikom težko doseči bistveno večjo globino iskanja, npr. globino preko 10 pol­ potez, tj. 5 polnih potez. Eksperiment, opisan v preostalem delu tega članka, pa daje odgovor na vprašanje b. V tem poskusu smo izračunali z algoritmom B popolno strategijo za končnico štirih figur: kralj in trdnjava proti kralju in skokoču (končnica KTKS). Rezultati tega izračuna, ki so zanimivi tudi s stališča same šahovske igre, predstavljajo pomembno orodje pri eksperimen­ tiranju z metodami umetne inteligence, opliciranlmi no to eksperimentalno okolje. Da moro biti pravilno strategija za to končnico generirano s pomočjo računalnike, potrjujejo re- zultotl psiholoških eksperimentov v Kopec, Niblett (1978), ^ % (te B SI. 2: R. Fine (Basic Chess Endings, 1964), v skladu z analizami Bergerja, ocenjuje to pozicijo kot remi. Računalniško generirano strategija za končnico KTKS vsebuje za to pozicijo 15 potezno zmagovito varianto, ki se začenja z I.Kc6. Noš poskus kaže, skupaj z nekaterimi podobnimi znanimi re­ zultati, do je zo končnice 4 figur še mogoče graditi popolne strategije z algoritmom 6, da po je sama programska izvedba tega algoritma zaradi časovnih omejitev zelo zahtevna. Če namreč želimo, da je čas izvajanja progromo zo rešitev ce­ lotne končnice v razumnih mejah, npr. nekoj ur, potem je treba najti učinkovito metodo za predstavitev pozicij v raču­ nalniku ter za organizacijo podatkovnih struktur na zurranjem pomnilniku. Npr. premočrtna, neustrezno strukturirana imple­ mentacija podatkovnih množic z datotekami z naključnim do­ stopom lahko poveča časovno kompleksnost programa za ne­ kaj velikostnih razredov. Če število figur v končnici povečamo samo za 1, postane izračun popolne strotegije še neprimerno težji. Rešitev končnice kralj, trdnjavo in kmet proti kralju in trdnjavi (Arlazorov, Futer, 1977) se lahko po programski zahtevnosti primerja z Izdelavo prevajalnikov zo programirne jezike. Končnice s 6 figurami po so (razen v trivialnih primerih) verjetno že na meji dosegljivega pri današnjem stanju tehno­ logije. ALGORITEM B Spodnji algoritem zgradi množico pozicij, ki so dobljene za "nai" proti "njim" (ne za belega proti črnemu). V algo­ ritmu so uporobljene naslednje kratice: ttm - them to move, oni na potezi (nosprotnik na potezi, npr. črni na potezi) utm - us to move, mi no potezi (npr. beli na potezi) t - števec polpotez do zmage ob optimalni igri obeh Igralcev n(L)- število pozicij z L polpotezomi do zmage ob optimolnl igri poz(p)- število polpotez do zmage za pozicijo p goal(p)- "končni predikat" za razpoznavanje pozicij, ki so po definiciji dobljene, npr. mat. 1. Iniclolizocija. 2. Za vse ttm pozicije označi vse nelegalne poteze. 3. Generiranje pozicij nivoja 0: vse ttm pozicije p, ki izpolnjujejo končni predikat goal(p), označi s "satisfied" in poz(p) = O, n(0) = število pozicij s poz(p) = 0,L = 0. 4. Če je n(L) T' O in so še možne Inverzne poteze nazaj Iz pozicij nivoja L, nadaljuj, drugače končaj. 5. L = L+1, n(L) = 0. 6. Če je L sod, pojdi no 9, drugače nadaljuj s 7. 7. Generiroj utm nivo L iz ttm nivoja L-1: Zo vsako ttm pozicijo p, označeno s "satisfied", naredi: 45 poišči vse predhodnike p (generlraj inverzne "us-move" poteze iz p) in za vsakega predhodnika q (no utm ni­ voju), če q ni ozrMČen s "sotisfied", naredi: 1 . označi q s "sotisfied" 2. poz(q) = L 3. n(L) = n(L) + 1 8. Pojdi na 4. 9. Generiraj ttm nivo L iz utm nivoja L-l . Za vsako utm pozicijo p, označeno s "satisfied" in poz(p) = L-l naredi: poišči vse predhodnike p (generiraj inverzne "them - move" poteze iz p) in zo vsakega naslednika q (no ttm nivoju), če q ni označeno s "satisfied", naredi: 1 . označi ustrezr« potezo iz q z "bodmove" 2. če so vse poteze "bodmove", potem 1 . označi q s "satisfied" 2. poz(q) = L 3. n(L) = n(L + l) 10. Pojdi na 4. Za izvedbo algoritma B potrebujemo naslednje osnovne po­ datkovne strukture: UTMP: vektor utm pozicij dolžine N (= število vseh možnih pozicij). Za vsako pozicijo p: poz(p) (če je poz(p) večje kot Lniax ~ max(L) , potem p ni označeno s "sotisfied"). Indeks pozicije v vektorju je koda po­ zicije p. TTMP: vektor ttm pozicij dolžine N. Za vsako pozicijo p: 1 bit zo oznako "satisfied" M bitov za M možnih "them move" potez (če je pozicija p označena s "satisfied", potem je v teh M bitih shranjeno poz(p)). Za hitrejšo izvedbo algoritma običajno potrebujemo še: UTMNEW; vektor bitov dolžine N. UTMNEW(koda(p)) = 1, če je bilo utm pozicija p označeno na predhodnem nivoju, to je poz(p) = L-l TTMNEVV: isto kot UTMNEVV zo ttm pozicije. OCENITEV ŠTEVILA POZICIJ ZA KONČNICO KRALJ + TRDNJAVA : KRALJ + SKAKAČ Ker imamo no šahovski deski (64 polj) 4 figure, je vseh možnosti 64 . 63.62.61, to je 15249024 pozicij. V tej oceni so zajete tudi pozicije, ki niso možne. Z upošte­ vanjem simetrije lahko v prvem zamahu zmanjšamo število pozicij na 10.63.62.61 = 2382660. Šahovsko desko raz­ režemo na 8 trikotnikov in izbrano figuro s transformacijami prevrtimo v izbrani trikotnik velikosti 10 polj, kot je to razvidno s slike 3. Pri tem je BT bela trdnjava, BK beli kralj, CK črni kralj in CS črni skokač. b C d e f g h SI. 3: Zmanjševonje števila pozicij z upoštevanjem simetrije. Preslikovanja BK (belega kralja) v trikotnik 1. BT (bela trdnjavo) je zraven, da lažje vidimo, kako potekajo preslikave preko osi simetrije Figure so urejene po prioriteti, recimo BK, BT, CK, CS. Ce je beli kralj no diagonali (al - d4), lahko po prioriteti drugo figuro preslikamo v trikotnik 1+2. Če so vse priori- tetnejše figure no diagonali, lahko zavrtimo pozicijo preko diagonale (al-h8) tako, do po prioriteti nojpomembnejSa figuro, ki ni no diagonali, pristane v trikotniku 1+2. S tem lahko še bolj zmonjšamo število pozicij na eno osmino od 15249024 = 1906128. Seveda je treba razlikovati še v tem, kdo je na potezi, tako da je dejansko število pozicij dvakrat večje. IMPLEMENTACIJA ALGORITMA B Pri izvajanju algoritma B je treba za vsako možno pozicijo hraniti določeno množino informacij (po 6 bitov za utm pozicije oziroma po 17 bitov za ttm pozicije, kot je raz­ vidno iz nodaljevonja). Tako je celotni potrebni pomnilni prostor pri obdelavi končnice KTKS velikosti okrog 60 mili­ jonov bitov. V grobem lahko časovno kompleksnost algoritma B ocenimo takole; zo vsako dobljeno pozicijo moramo generirati vse možne inverzne poteze, tj. zo končnico KTKS v velikostnem razredu 30 milijonov. Tolikokrat je potem potrebno tudi ažu- riroti podatke v datotekah skupne velikosti 60 milijonov •bitov. Zato premočrtna organizacija teh podatkov, tako da bi bilo pri izvedbi algoritma B potrebnih 30 milijonov naključnih dostopov, praktično ni sprejemljivo. V naslednjih odstavkih so opisane podotkovne strukture, ki omogočajo, da ažuriromo te oodotke povečini sekvenčno. UTMP TTMP UTMNEVV, TTMNEW , 0.. 4095 BKBT O . . . A095 CKCS 0...4095 1 1 540 i=BKx54*BT 0.. i .. 4095 Ji j=BKx6 C. i=CKx64*(3 O ...i . . UBT*1 63 poteze poteze kmlJG konja 0..63 n 1 če je izgubljena, je tu kar število polpotez do poraza. SI. 4: Podatkovne strukture Na sliki 4 so osnovne podatkovne strukture. To $o datoteke dolžine 640 okenc, okence po je polje 4096 elementov. Indeks okenca dobimo iz položaja dveh najbolj prioritetnih figur. Položaj figure je dan z zaporedno številko polja no katerem stoji figura, pri čemer so polja oštevilčena od O do 63. Kratice BK, BT, CK in CS v nodaljevonju pomenijo po vrsti položoj belego kralja, bele trdnjave, črnega kralja in črnega skakočo. Npr. UTMP je datoteka, katere okence i = CKx64 + CS + l (027 10-^ 10'8, =: 1000 i18 Pri »em je 10'° s starost Zemlje. LITERATURA: 1. Arlozarov, V.L., Futer, A.V., Computer anal/sis of a rook end-game, v Machine Intelligence 9 (Ed. D.Michie), v tisku. 2. Berliner, H.J., Computer Chess, Nature, Vol. 274, 24. Aug. 1978, 745-748. 3. CIarke, M.R.B., A quantitative stud/ of king and ogainst king, v Advonces in Computer Chess 1, 108-118 (Ed. M.R.B. CIarke), Edinburgh: Universit/ Press, 1977. 4. Knulh, D.E., AAoore, R.W., An anal/sis of alpha-beta prunir^, Artificial Intelligence, 6, 293-326, 1975. 5. Kopec, D., Niblett, T., How difficult Is the king and rook vs. king and knighf ending?, v Advonces in Computer Chess 2, (ed. M.R.B. CIarke), v tisku. V ^ a % Obe beli figuri se odpravljata no lov na črnega konja. 24. Ke5 Sg7, 25. Th2 Se8 (25. Tf7, f8 ..) (25. .. Ka4,b3, b4) 26. Th7 Ka2 (26. .. Kb2, b3, b4, a4) O 1 w a črni konj je očitno izgubljen. 27, Te7 Sg7 (27. .. Kal, a3, bi, b2, b3, Sc7, d6, f6) 28. Tg7: IN WIRE- WRAPPING ^fe H AS THE LINE. ELECTRIC 8. PNEUMATIC INDUSTRIAL WRAPPING TOOLS OK MACHINE i TOOL CORPORATION