Elektrotehniški vestnik 78(3): 153-158, 2011 Existing separate English edition
Šahovski program Umko
Borko Boškovic, Janez Brest
Univerza v Mariboru, Fakulteta za elektrotehniko računalništvo in informatiko, Smetanova ulica 17, 2000 Maribor, Slovenija E-pošta: borko.boskovič@uni-mb.si
Povzetek. Umko je mocan odprtokodni šahovski program. Pri njegovem razvoju smo uporabili dobre koncepte iz literature in drugih odprtokodnih projektov. S pomočjo teh konceptov smo želeli implementirati kar se da močnega šahovskega igralca. Da bi to naredili, smo implementirali naslednje koncepte: bitno predstavitev deske, generator potez, paralelni iskalni algoritem, preiskovanje vec glavnih variant, transpozicijsko tabelo, standardni šahovski vmesnik za komunikacijo z graficnim vmesnikom, ocenitveno funkcijo, uporabo baz koncnic in uporabo otvoritvene knjižnice. Vse omenjene koncepte bomo podrobneje predstavili v clanku.
Umko je program, ki se izvaja na razlicnih platformah in znotraj razlicnih graficnih uporabniških vmesnikov. Zna uporabljati najsodobnejše tehnologije procesorjev. Program vsebuje paralelni iskalni algoritem, ki mu omogoca uporabo vec procesorjev oz. jeder hkrati. Na drugi strani program uporablja nov SSE4.2 nabor inštrukcij. Tako paralelni iskalni algoritem kot novi nabor inštrukcij omogocata, da je program hitrejši in mocnejši igralec. Program je bil preizkušen in uvršcen na razlicne neodvisne lestvice. Na teh lestvicah se je uvrstil med 10 najboljših odprtokodnih programov.
Ključne besede: šahovski program, bitna predstavitev deske, ocenitvena funkcija, iskalni algoritem, generator potez, transpozicijska tabela, baze koncnic, otvoritvena knjižnica
Chess Program Umko
Umko is a strong open-source chess program developed to collect good concepts from literature and other open-source projects. Using these concepts, we want to implement as strong as possible chess program. To do this, Umko has implemented a bitboard representation, move generator, parallel search algorithm, multiple principal variation search, transposition table, universal chess interface, evaluation function, usage of endgame tablebases and usage of the opening book. The paper provides details of these concepts.
Umko is a program running on several platforms inside different graphical user interfaces and using the modern processor technology. It has a parallel search algorithm allowing its program to simultaneously use more processors or cores and the new SSE4.2 CPU instruction set. Both the parallel search algorithm and the new instruction set enable the program to be a faster and stronger player. Having been tested on different independent rating lists, the program is rated among the top ten open-source chess programs.
1 Uvod
Računalniški šah ima dolgo zgodovino raziskav na področju umetne inteligence. S cedalje vecjo racunalniško mocjo, kije zrasla do izjemne stopnje, smo prica vse vec igram med racunalniki in ljudmi, kjer po navadi zmagajo racunalniki. Razloga za to sta v glavnem izboljšava strojne opreme in optimizacija šahovskih algoritmov. Prvi racunalnik, ki je premagal svetovnega šahovskega prvaka, je bil Deep Blue. Premagal je Garija Kasparova,
to je bilo leta 1997 [12]. Leta 2006 je racunalniški program Deep Fritz 10 na osebnem racunalniku premagal svetovnega prvaka Vladimirja Kramnika [18]. Leta 2005 je s svojo mocjo presenetil šahovski program Rybka. Zasedel je prvo mesto na vseh pomembnih lestvicah šahovskih programov in je prvi program, ki je dosegel moc igranja vec kot 3000 tock [9]. Še vec, odprtokodni in brezplacni programi so postajali mocnejši, nekateri od njih so postali tudi mocnejši od komercialnih programov. Trenutno je najboljši odprtokodni program Stockfish. Njegova igralna moc je bila na vecini lestvic ocenjena na vec kot 3200 tock. V letu 2010 je mesto najboljšega programa prevzel brezplacni program Houdini. Njegova igralna moc je za približno 50 tock presegla programa Rybka in za približno 70 tock program Stockfish.
Zakaj razvijalci poskušajo izboljšati že tako zelo mocne šahovske programe? Veliko poklicnih šahistov za izboljšanje igralne moci, uporablja šahovske programe. Šahovski programi so zelo uporabni v dopisnem šahu in prostem slogu (ang. Freestyle Chess). Cedalje bolj priljubljena postajajo tudi tekmovanja med samimi programi. Navsezadnje se je racunalniški šah izkazal tudi kot zelo koristno okolje za preizkušanje razlicnih metod umetne inteligence.
Tudi mi smo želeli razviti mocan šahovski program. Da bi to naredili, smo zbrali dobre koncepte iz literature in odprtokodnih projektov. Glede na te vire ima naš program implementirane naslednje koncepte: bitno predstavitev deske, generator potez, paralelni iskalni algoritem, preiskovanje vec glavnih variant, transpozicijsko
tabelo, standardni šahovski vmesnik za komunikacijo z grafičnim vmesnikom, ocenitveno funkcijo, uporabo baz končnic znotraj iskalnega algoritma in uporabo otvoritvene knjižnice. Program ima implementiran paralelni iskalni algoritem, ki omogoca programu, da uporablja vec procesorjev ali jeder hkrati. Na drugi strani pa program lahko uporablja nov nabor procesorskih in-štrukcij SSE4.2. Paralelni iskalni algoritem in nov nabor inštrukcij omogocata programu, da uporablja sodobno tehnologijo procesorjev in postane hitrejši, s tem pa tudi mocnejši igralec.
Ker naš program temelji na odprtokodnih projektih, je objavljen pod licenco GNU GPL v3 na spletni strani sistema SourceForge: http://umko.sourceforge.net/. So-urceForge je eden največjih spletnih sistemov za razvoj odprtokodne programske opreme. Zagotavlja brezplacne storitve, ki pomagajo ljudem, da razvijajo programsko opremo in jo delijo z drugimi ljudmi. Umko je implementiran s pomočjo programskega jezika C++, tako da ga je mogoce prevesti s prevajalnikom GNU C++ za operacijske sisteme Linux, Android, Mac OS X in Windows ter za arhitekture i586, x64 in ARM.
Clanek je organiziran takole: 2. poglavje podrobneje predstavi program oz. njegove sestavne dele. Eksperimentalni rezultati in doseženi ratingi so predstavljeni v 3. poglavju. (Članek koncujemo s sklepi in smernicami za nadalnje delo, ki so podani v 4. poglavju.
2 Predstavitev programa
Umko nima lastnega graficnega uporabniškega vmesnika, je konzolna aplikacija, ki komunicira z graficnim vmesnikom preko protokola UCI (ang. Universal Chess Interface). Naš program tece kot zunanji proces znotraj graficnega vmesnika. Le-ta krmili naš program s po-mocjo standardnih tokov V/I in protokola UCI. Glede na to, da naš program hkrati komunicira z graficnim vmesnikom in analizira doloceno pozicijo, ima vsaj dve niti. Ena se uporablja za komunikacijo, medtem ko se druga ali preostale uporabljajo za analizo dolocene pozicije in iskanje najboljše poteze. Ker želimo razviti program za operacijske sisteme Windows in Unix, uporablja program niti Windows ali POSIX. Med prevajanjem se ugotovi ciljni operacijski sistem in glede nanj se uporabijo dolocene niti oz. knjižnice za gradnjo programa.
Osnovni sestavni deli sodobnih šahovskih programov so: predstavitev igre, iskalni algoritem, generator potez, transpozicijska tabela, ocenitvena funkcija, otvoritvena knjižnica in baze koncnic. Predstavitev igre omogoca programu, da upravlja pozicije in poteze. Vpliva pa tudi na hitrost šahovskega programa. Generator potez je mehanizem, ki generira legalne poteze, kakor hitro je to mogoce. Iskalni algoritem je odgovoren za iskanje najboljše poteze glede na vrednosti, ki jih vraca ocenitvena funkcija. Ta vsebuje šahovsko znanje, ki ji omogoca, da ocenjuje pozicije. Transpozicijska tabela (TT) omogoca
iskalnemu algoritmu, da se izogne večkratnemu iskanju ene in iste pozicije. Otvoritvena knjižnica omogoča šahovskemu programu, da uporabi znanja in izkušnje ljudi oz. računalniških igralcev v otvoritveni fazi igre. Podobno baze končnic omogočajo izbiro močnih potez v končni fazi igre.
Šah je igra, ki je časovno omejena. To pomeni, da je šahovski program časovno omejen pri odločanju, katera poteza je najboljša v določeni poziciji. Zato mora biti šahovski program hiter. To mu omogoča, da preišče več pozicij v določenem času, da je izbrana poteza verjetno boljša in da je program boljši igralec. Na drugi strani šahovski program vsebuje šahovsko znanje, ki prav tako vpliva na hitrost programa. Ce program vsebuje več znanja, postaja počasnejši in nasprotno, manj znanja ko vsebuje, hitrejši postaja. Zato razvijalci šahovskih programov morajo najti ravnovesje med količino znanja in hitrostjo, da bi dobili močan šahovski program.
2.1	Predstavitev igre
Predstavitev igre omogoča šahovskemu programu upravljanje potez in pozicij. Vpliva tudi na hitrost generatorja potez, ocenitveno funkcijo in na splošno na hitrost vseh sestavnih delov programa. Obstaja veliko različnih načinov za predstavitev pozicij in potez. Šahovska pozicija vsebuje naslednje informacije: položaj figur, kateri igralec je na potezi, možnosti rokade, polje en passant, število polpotez od zadnje poteze kmeta ali jemanja figure in število vseh potez, ki so bile odigrane, da je nastala ta pozičija. Pri predstavitvi igre je najpomembnejše, kako je predstavljen položaj figur oz. predstavitev deske. Za predstavitev deske smo uporabili bitno predstavitev deske (ang. Bitboard). Bitboard je 64-bitno čelo število brez predznaka, kjer vsak bit pomeni kvadrat na šahovnici. Ker šahovska igra vsebuje več različnih figur, potrebujemo več bitnih števil oz. eno bitno število za vsak tip figure in barvo. Glavna prednost te predstavitve je, da omogoča hiter izračun potez in izrazov v ocenitveni funkciji [11], [19], [3], [4].
Predstavitev potez je tudi zelo pomembna. Poteze spreminjajo pozicije in kot take se uporabljajo znotraj iskalnega algoritma, kjer se shranjujejo v transpozičijsko tabelo. Zato mora biti predstavitev potez kompaktna. Mi smo uporabili 16-bitna cela števila brez predznaka. Znotraj teh števil so zakodirane naslednje informačije: tip poteze, začetno polje in končno polje poteze. Glede na te informacije se v iskalnem algoritmu spreminjajo pozicije z igranjem in vračanjem poteze. V šahovskem programu je treba tudi primerjati pozicije med seboj. V ta namen smo uporabili ključe Zobrist [24], ki so skoraj unikatna števila za pozicije. Ti ključi se uporabljajo tudi znotraj transpozičijske tabele in otvoritvene knjižniče.
2.2	Iskalni algoritem
Ker je narava šahovske igre zapletena, ni načina, kako izdelati program, ki bi igral popoln šah. Vendar je mogoče razviti iskalni algoritem in ocenitveno funkcijo, ki
skupaj omogočata programu, da postane mocan igralec [23]. Ocenitvena funkcija je odgovorna za statično oceno pozicij, iskalni algoritem pa za dinamicno oceno pozicij in izbiro potez, ki bodo odigrane.
Na splošno, iskalni algoritmi šahovskih programov temeljijo na algoritmu alfa-beta oz. minimax . V našem programu smo uporabili Principal Variation Search (PVS) [17], [2], [3], kije izboljšan alfa-beta algoritem. Glavna ideja tega algoritma je, da razlikuje vozlišca (pozicije) glavne variante (PV-vozlišca) in vozlišca, ki ne pripadajo glavni varianti (ne PV-vozlišca). PV-vozlišca se preiskujejo z dolocenim oknom, na drugi strani ne PV-vozlišca z minimalnim oknom. Okno dolocata argumenta alfa in beta. Za minimalno okno je razlika med tema argumentoma enaka ena. Algoritem PVS smo uporabili, ker omogoca razlicne nacine klestenja med PV-vozlišci in ne PV-vozlišci. Glavna varianta bo verjetno odigrana in je bolje, da se pri teh vozlišcih uporabi manj agresivno klestenje in nasprotno, bolj agresivno klestenje pri ne PV-vozlišcih.
Za ovrednotenje listov iskalnega drevesa smo uporabili iskanje mirovanja (ang. Quiescence Search). Namen tega iskanja je, da se algoritem izogne ucinku obzorja [22]. To pomeni, ce bi se iskanje ustavilo v listih drevesa in bi se ocenile pozicije, bi lahko dobljene ocene vsebovale veliko napako. To bi se lahko zgodilo, ce bi zadnja odigrana poteza v veji iskalnega drevesa bila jemanje in bi bila naslednja mogoca poteza povratno jemanje. Zato iskanje mirovanja v listih drevesa nadaljuje preiskovanje in se poskuša izogniti ucinku obzorja ter pravilno oceniti pozicije.
V iskalnem algoritmu smo implementirali naslednje razširitve iskanja in tehnike klestenja: klestenje vozlišc blizu listov (ang. Futility Pruning) [10], klestenje z nicelno potezo (ang. Null Move Pruning) [6], redukcije pri poznejših potezah (ang. Late Move Reductions) [16], transpozicijska tabela (ang. Transposition Table) [5], razširitve izstopajocih potez (ang. Singular Extensions) [1], notranje iterativno poglabljanje (ang. Internal Iterative Deepening), razširitve edine mogoce poteze (ang. Single Move Extensions), razširitve šaha (ang. Check Extensions), razširitve potez prostih kmetov (ang. Passed Pawns Extensions) in razširitve povratnih jemanj (ang. Recapture Extensions). Klestenje vozlišc blizu listov je tehnika, ki klesti vozlišca blizu listov glede na dobljene ocene iz ocenitvene funkcije. Klestenje z nicelno potezo je tehnika, ki s pomocjo ni-celne poteze (zamenja igralca na potezi) in redukcije globine iskanja razpozna vozlišca, ki jih je mogoce klestiti. Redukcije pri poznejših potezah je tehnika, ki zmanjša globino preiskovanja pri tihih potezah (poteze, ki ne jemljejo figur ali dajo šah nasprotniku), ki so bliže repu generiranih potez. Transpozicijska tabela shranjuje informacije, ki omogocajo iskalnemu algoritmu, da se izogne veckratnemu iskanju ene in iste pozicije. Razširitev izstopajocih potez je tehnika, kjer se razširi iskanje poteze, za katero se zdi, da je bistveno boljša
od preostalih potez. Notranje iterativno poglabljanje je tehnika, podobna iterativnemu poglabljanju s to razliko, da se tukaj poglabljanje izvaja znotraj vozlišc iskalnega drevesa. Iz imen preostalih razširitev: razširitev edine mogoce poteze, razširitev šaha, razširitev potez prostih kmetov in razširitev povratnih jemanj, je mogoce razbrati, za kaj gre, zato teh razširitev ne bomo posebej opisovali.
Celoten algoritem je bil implementiran skupaj z iterativnim poglabljanjem (ang. Iterative Deepening), aspi-racijskim iskanjem (ang. Aspiration Search) in iskanjem v korenskem vozlišcu (ang. Root Search). Iterativno poglabljanje je tehnika, ki programu omogoca, da iterativno povecuje globino iskanja [15]. Ta tehnika skupaj s preostalimi tehnikami, kot sta npr. transpozicijska tabela in zgodovinska hevristika (ang. History Heuristic), omogoca iterativno izboljšanje zaporedja potez. Ceprav se na tak nacin dolocena vozlišca preiskujejo veckrat, se ucinkovitost celotnega algoritma poveca. Tako je zato, ker je algoritem alfa-beta obcutljiv na zaporedje potez. Aspiracijsko iskanje je tehnika, ki zmanjša iskalni prostor [14]. Namesto da bi preiskali celoten iskalni prostor, algoritem ugiba oceno pozicije in preiskuje okoli te vrednosti z dolocenim oknom. Ce je dobljena ocena zunaj okna, je treba iskanje ponavljati, dokler se ocena ne znajde znotraj iskalnega okna. Iskanje v korenskem vozlišcu vrne oceno iskalnega algoritma in hkrati potezo, ki bo odigrana. V našem programu smo v to iskanje vkljucili še iskanje vec glavnih variant. To pomeni, da program lahko preiskuje vec glavnih variant hkrati. Poteze glavnih variant se preiskujejo kot PV-vozlišca z manj agresivnim klestenjem. S pomocjo protokola UCI se preiskovane variante posredujejo graficnemu vmesniku. Tako lahko uporabnik socasno analizira vec variant hkrati in dobi njihove ocene.
Da bi povecali hitrost preiskovanja oz. globino preiskovanja z uporabo vec procesorjev ali jeder, ima naš program implementiran algoritem "Young Brothers Wait" [7], [8]. To je paralelni algoritem, kjer se v dolo-cenem vozlišcu prva poteza preiskuje brez paralelizacije, preostale poteze pa se nato preiskujejo vzporedno. Ker pri vzporednem iskanju vsaka iskalna nit piše in bere iz transpozicijske tabele, se lahko zgodi, da so uporabljeni podatki nepravilni. Zato je treba transpozicijsko tabelo prilagoditi paralelnemu algoritmu [13].
Vse predstavljene tehnike iskalnega algoritma smo v našem programu izboljšali glede na dobljene ideje iz odprtokodnih šahovskih programov Toga II in Stockfish.
2.3 Generator potez
Kot smo že omenili, je iskalni algoritem zelo obcutljiv na zaporedja potez. Dobro zaporedje potez izboljša ucinkovitost iskalnega algoritma in moc šahovskega programa. V našem programu smo implementirali "Magic Bitboard Move Generator", ki temelji na prej opisani bitni predstavitvi pozicij. Dodatno pa omogoca hitro ge-neriranje potez drsecih figur (ang. Sliding Pieces) [19].
S samo nekaj inštrukcijami se izracuna indeks baze bitnih števil, ki vsebujejo bitno predstavitev napadov obeh linij za figuri lovca in trdnjavo. Za izboljšanje zaporedja generiranih potez smo uporabili: transpozicijsko tabelo, oceno staticne izmenjave (ang. Static Exchange Evaluation), ubijalske poteze (ang. Killer Moves) in zgodovinsko hevristiko (ang. History Heuristic).
implementirani generator potez ima štiri sheme. Povzete so po šahovskem programu Toga ii. Dve shemi se uporabljata za PVS-vozlišca in dve za QS-vozlišca. Pri PVS-vozlišcih se tedaj, ko igralec ni v šahu, uporablja naslednja shema:
•	poteza transpozicijske tabele,
•	dobra jemanja (ocena staticne izmenjave),
•	ubijalske poteze,
•	tihe poteze (zgodovinska hevristika) in
•	slaba jemanja (ocena staticne izmenjave).
Ce je igralec v šahu, se uporablja naslednja shema:
•	poteza transpozicijske tabele,
•	dobra izogibanja šahu (ocena staticne izmenjave) in
•	slaba izogibanja šahu (ocena staticne izmenjave). Podobne sheme se uporabijo pri QS-vozlišcih. Ce igralec ni v šahu, se uporabi naslednja shema:
•	poteza transpozicijske tabele,
•	dobra jemanja (ocena staticne izmenjave) in
•	poteze, ki šahirajo nasprotnika (le tedaj, ko je globina preiskovanja enaka 0).
Ce je igralec v šahu, se uporabi naslednja shema:
•	poteza transpozicijske tabele in
•	vse poteze izogibanja šahu.
Prva uporabljena tehnika, ki izboljšuje zaporedje potez, je transpozicijska tabela. To je razpršena tabela (ang. Hash Table), ki vsebuje dolocene informacije o pozicijah. Kot smo že omenili, se te informacije uporabljajo v iskalnem algoritmu, da ne preiskujemo ene in iste pozicije veckrat. Dodatno se v transpozicijsko tabelo shranjujejo tudi poteze. Ce poteza za doloceno pozicijo obstaja v transpozicijski tabeli, se preiskuje kot prva in tako se izboljša zaporedje potez. Druga uporabljena tehnika za izboljšavo zaporedja potez je ocena staticne izmenjave. Ta tehnika omogoca locevanje med dobrimi in slabimi potezami jemanj. Za doloceno potezo se oceni izmenjava potez na enem polju [20]. Ce je ocena vecja ali enaka 0, potem gre za dobro jemanje, v nasprotnem primeru za slabo jemanje. Tretja uporabljena tehnika za izboljšavo zaporedja potez vkljucuje ubijalske poteze. To so dobre tihe poteze, ki so povzrocile rez (ang. Cutoff) v vozlišcih prejšnjih vej iskalnega drevesa in so enako oddaljene od korenskega vozlišca. Zadnja tehnika, ki smo jo uporabili, je zgodovinska hevristika [21]. Uporablja se za dinamicno urejanje tihih potez. Skozi preiskovanje se te poteze ovrednotijo glede na število rezov in pripadajocih globin iskanja. Na podlagi teh hevristik se nato tihe poteze urejajo. Omenjeni izraz rez je dogodek, ko se doloceno vozlišce preiskuje in je po preiskovanju dolocene poteze ocena pozicije nad zgornjo
mejo iskalnega okna (beta). To pomeni, da preostalih potez ni treba preiskovati.
2.4	Ocenitvena funkcija
Ocenitvena funkcija je zelo pomemben del šahovskih programov. Vsebuje šahovsko znanje in staticno ocenjuje pozicije. Te ocene so cela števila, ki se uporabljajo v iskalnem algoritmu in na podlagi njih se oceni korensko vozlišce oz. pozicija. Naša ocenitvena funkcija ima implementirane ideje, ki so povzete iz šahovskega programa Toga II in nadgrajene z dolocenimi idejami iz šahovskega programa Stockfish. Tako naša ocenitvena funkcija vsebuje naslednja šahovska znanja:
•	preproste pozicije koncnic (KK, KNK, KBK, KRK, KQK, KNKN, KBKB, KRKR, KQKQ, KNNK, KBBK, KBNK, KBKN, KRRK, KQQK, KQRK),
•	vzorci (ujete in blokirane figure),
•	figure (material, mobilnost, pozicijske vrednosti),
•	kralj (nevihta kmetov, zašcitna polja, napad figur),
•	struktura kmetov (veriga kmetov, podvojeni kmeti, izolirani kmeti, zaostali kmeti, kandidati za promocijo, prosti kmeti, nezaustavljivi prosti kmeti) in
•	grožnje (napad figur).
Našteta znanja se pri ocenjevanju racunajo za otvoritveno fazo in koncno fazo igre. Na koncu se s pomočjo interpolacije glede na fazo pozicije v igri izracuna koncna ocena.
2.5	Otvoritvena knjižnica in baze koncnic
Program, ki uporablja otvoritveno knjižnico in baze koncnic, je mocnejši igralec. Otvoritvena knjižnica vsebuje izkušnje in znanje ljudi in programov o otvoritveni fazi igre. To omogoca programu, da v otvoritveni fazi igre igra mocne poteze zelo hitro. Tako tudi naš program lahko uporablja otvoritvene knjižnice programa Polyglot. Te knjižnice za doloceno pozicijo ponujajo poteze in njihove pripadajoce verjetnosti. To pomeni, da program izbira med ponujenimi potezami z doloceno verjetnostjo. Tako program igra razlicne otvoritvene variante. V nasprotnem primeru, brez uporabe otvoritvene knjižnice, bi program igral le nekaj otvoritvenih variant in bi bil predvidljiv.
Podobno kot otvoritvena knjižnica, ki izboljšuje moc programa v otvoritveni fazi igre, baze koncnic izboljšujejo njegovo moc v koncni fazi igre. Baze koncnic omogocajo programu, da oceni dolocene pozicije koncnic brez napak. Naš program uporablja baze koncnic programa Gaviota. Te baze vsebujejo pozicije koncnic s petimi ali manj figurami. To pomeni, da program igra brez napak pri pozicijah, ki vsebujejo pet ali manj figur. Baze koncnic se uporabljajo tudi tedaj, ko korensko vozlišce iskalnega drevesa vsebuje vec kot pet figur in pozicije znotraj iskalnega drevesa vsebujejo pet ali manj figur. Tako baze koncnic pomagajo iskalnemu algoritmu, da izbira mocnejše poteze v koncni fazi igre, celo tedaj, ko pozicije vsebujejo vec kot pet figur.
Tabela 1: Testne knjižnice (Umko 1.1b)
Testna knjižnica	Cas	Trans. tab.	Hitrost	Globina	Uspešnost	Rat. caš	Rating
Win at Chess	5	64 (70,7%)	1,74e+06	26,1 (36,2)	294/300	54,8	-
1001 Winning Chess Sacrifices	5	64 (80,1%)	1,73e+06	21,7 (37,9)	872/1001	738,3	-
1001 Brilliant Ways to Checkmate	5	64 (7,8%)	1,34e+06	55,1 (16,1)	988/1001	89,4	-
Strategic Test Suite	10	128 (94,1%)	1,63e+06	18,0 (40,1)	996/1300	3752,6	-
Encyclopedia of Chess Middlegame	20	128 (94,0%)	1,68e+06	20,8 (47,0)	677/770	2429,0	-
Bratko-Kopec	60	256 (95,6%)	1,56e+06	23,8 (46,8)	18/24	404,0	-
LCT II	600	512 (98,0%)	1,75e+06	27,4 (65,6)	29/35	3777,3	2740
BT 2630	900	512 (96,7%)	1,67e+06	29,8 (69,7)	27/30	2889,4	2534
BS 2830	900	512 (96,1%)	1,54e+06	26,1 (71,6)	19/27	7847,6	2771
Nolot	3600	512 (99,8%)	1,54e+06	27,8 (83,4)	6/11	18935,7	-
Tabela 2: Analiza pozicije (Nolot št. 4)
Globina	Ocena	(Cas	Hitrost	TT	Poteza
23 (43)	0,83	315	1,48e+6	99,8	h5e2
23 (50)	1,04	370	1,51e+6	99,8	d4e6
23 (52)	1,78	488	1,50e+6	99,8	d4e6
29 (65)	2,11	3003	1,47e+6	99,8	d4e6
3 Rezultati
3.1 Eksperimentalni rezultati
Umko je bil preizkušen z reševanjem testnih knjižnic. Ta test smo opravili na računalniku s procesorjem Intel(R) Core(TM)2 CPU 6600 2.40GHz. Operacijski sitem je bil Linux in uporabljeni sta bili dve niti za iskalni algoritem. Doseženi rezultati so prikazani v tabeli 1. Prvi stolpec prikazuje ime knjižnice. Drugi stolpec prikazuje čas v sekundah, ki je bil dovoljen za reševanje pozicije. Tretji stolpec prikazuje velikost in povprecno zasedenost transpozicijske tabele. Povprecno hitrost preiskovanja oz. število vozlišc na sekundo prikazuje cetrti stolpec. Peti stolpec vsebuje prikaz povprecne globine in pov-precne selektivne globine (maksimalno število polpotez od korena drevesa do listov). Šesti stolpec prikazuje uspešnost programa oz. število rešenih pozicij in število vseh pozicij v doloceni knjižnici. Sedmi in osmi stolpec prikazujeta rating cas in opcijsko dosežen rating. Dolo-cene knjižnice na podlagi rating casa in števila rešenih problemov omogocajo izracun doseženih ratingov.
Nacin delovanja programa je ponazorjen v tabeli 2. Analizirana je 4. pozicija (slika 1) iz testne knjižnice Nolot. V tabeli prvi stolpec prikazuje globino iskanja skupaj s selektivno globino. Preostali stolpci prikazujejo oceno pozicije, cas v sekundah, hitrost preiskovanja (milijon vozlišc na sekundo), zasedenost transpozicijske tabele v odstotkih in izbrano potezo. Iz rezultatov vidimo, da je program v globini preiskovanja 23 našel pravo rešitev. Pri tem je ocena znašala 1,04 oz. prednost enega kmeta. Daje program našel to rešitev, je potreboval 370 sekund. Hitrost preiskovanja je znašala 1,5 milijona vozlišc na sekundo. Zasedenost transpozicijske tabele je bila 99,8 odstotna. Iskanje se je koncalo, ko je program preiskoval 29. globino, in ocena pozicije se je zvišala na 2,11 (prednost dveh kmetov).
8 7 6 5 4 3 2 1
a b c d e f g h
Slika 1: Bronstein - Kotov, Budimpešta 1950
Tabela 3: Doseženi ratingi na različnih neodvisnih lestvicah
Rating lestvica	Program	Rating
CCRL 40/4 CCRL 40/40 CEGT 40/20 CEGT 40/4 IPON	Umko 1.1 64-bit 2CPU Umko 1.0 64-bit Umko 1.0 x64 4CPU Umko 1.0 x64 1CPU Umko 1.1 SSE42	2912±17 2908±29 2848±62 2811±13 2635±11
3.2 Dosežen rating
Umko je bil preizkušen in je na različnih lestvicah šahovskih programov dosegel različne ratinge. Ti so skupaj s 95 odstotnimi intervali zaupanja prikazani v tabeli 3. CCRL (ang. Computer Chess Rating Lists) je klub ljudi, ki radi preizkušajo različne programe. Programe tudi primerjajo med seboj tako, da izračunajo njihove ratinge in jih rangirajo. CCRL ima dve lestviči: 40/40 in 40/4. Na prvi lestviči se igrajo igre, kjer programi odigrajo 40 potez v 40 minutah (ponavljajoče). Na drugi lestviči imajo programi na voljo 4 minute za 40 potez (ponavljajoče). (Časovni omejitvi na obeh lestvičah sta prilagojeni tako, kot če bi se igralo na računalniku s pročesorjem AMD64 X2 4600+ (2.4GHz). Na obeh lestvičah je Umko zasedel 25. mesto (junij, 2011). Med odprtokodnimi programi se je uvrstil na 6. (40/4) oz. 7. (40/40) mesto.
Podobno kot CCRL, CEGT (ang. Chess Engines Grand Tournament) je skupina ljudi, ki radi preizkušajo šahovske programe in hkrati delijo dobljene rezultate
z vsemi šahovskimi entuziasti. Prav tako imajo dve lestvici 40/4 in 40/20. IPON je še ena lestvica. V nasprotju s prejšnjima dvehma tukaj programi igrajo po nacinu "pondering" (razmišljajo tudi, ko niso na potezi). Casovno so programi omejeni s 5 minutami na igro in imajo 3 sekunde dodatka na potezo. Na tej lestvici je bil preizkušen Umko, ki vsebuje inštrukcije SSE4.2, in se je uvrstil na 20. mesto.
Umko igra tudi na strežniku freechess.org nasproti ljudem in racunalnikom iz vsega sveta. Na tem strežniku je naš program dosegel "blitz" rating 2416 iz 858 iger, "standard" rating 2500 iz 911 iger in "lightning" rating 2619 iz 155 iger. Ti ratingi so doseženi s pomočjo enakega racunalnika, kot je bil uporabljen za reševanje testnih knjižnic.
V tem poglavju so prikazani ratingi treh razlicic našega programa, ki pa se nekoliko razlikujejo. Rating namrec pomeni relativno moc programa. Vse razlicice programa so približno enake po igralni moci, razlika med njimi je le v manjših popravkih ali izboljšavah.
4 Sklep
V prispevku smo predstavili najboljši slovenski šahovski program, Umko. Program ima implementirane koncepte in ideje, povzete iz literature in iz odprtokodnih projektov. Uporablja tudi najnovejše tehnologije procesorjev, kot sta uporaba vec procesorjev oz. jeder socasno in uporaba novega nabora procesorskih inštrukcij SSE4.2. Program je razvit kot odprtokodni projekt na spletnem sistemu SourceForge. Tako je prosto dostopen in hkrati tece na razlicnih platformah. Preizkusili smo ga na operacijskih sistemih Linux, Android, Mac OS X in Windows. Glede na dosežene rezultate ugotavljamo, da je Umko mocan šahovski igralec. Na neodvisnih lestvicah se uvršca med 25 najboljših programov. Med odprtokodnimi programi se uvršca med 10 najboljših programov. Zanimivo je tudi, da se je Umko izkazal za boljšega kot nekateri komercialni programi, med njimi je tudi znani šahovski program Chessmaster 11.
Pri nadaljnjem delu bomo program poskušali izboljšati. Dodali mu bomo vec šahovskega znanja in mu izboljšali paralelni iskalni algoritem. Na drugi strani bomo programu dodati nov koncept, ki mu bo omogocal, da bo igral z razlicno mocjo. Tako bo postal zanimivejši za razlicne igralce, od zacetnikov do velemojstrov.
Zahvala
Avtorja se zahvaljujeta avtorjema odprtokodnega programa Toga II Thomasu Gakschu in Fabienu Letou-zeyu, avtorjem odprtokodnega programa Stockfish Tordu Romstadu, Marcu Costalbi in Jooni Kiiski, avtorju baz koncnic Miguelu A. Ballicori, avtorju programa Polyglot Fabienu Letouzeyu, skupinam CCRL, CEGT in IPON in spletnemu sistemu SourceForge.
Literatura
[1]	Thomas Anantharaman, Murray S. Campbell in Feng-hsiung Hsu. Singular extensions: adding selectivity to brute-force searching. Artificial Intelligence, 43:99-109, 1990.
[2]	Yngvi Bjornsson. Selective Depth-First Game-Tree Search. doktorska disertacija, University of Alberta, 2002.
[3]	B. Boškovic. Implementacija računalniškega šaha, 2004.
[4]	B. Boškovic, S. Greiner, J. Brest in V. Žumer. The Representation of Chess Game. V Proceedings of the 27th International Conference on Information Technology Interfaces, str. 381-386, 2005.
[5]	D.M. Breuker, J. W. H. M. Uiterwijk in H. J. Van Den Herik. Replacement Schemes for Transposition Tables. ICCA Journal, 17:183-193, 1994.
[6]	Omid David-Tabibi in Nathan Netanyahu. Extended Null-Move Reductions. V H. van den Herik, Xinhe Xu, Zongmin Ma in Mark Winands, uredniki, Computers and Games, volume 5131 of Lecture Notes in Computer Science, str. 205-216. Springer Berlin / Heidelberg, 2008.
[7]	R. Feldmann, P. Mysliwietz in B. Monien. A Fully Distributed Chess Program. Advances in Computer Chess 6, 1991.
[8]	Rainer Feldmann. Game Tree Search on Massively Parallel Systems. doktorska disertacija, 1993.
[9]	Harald Fietz. Beyond the 3000 Elo barrier A glance behind the scenes of the Rybka chess engine. Chess, str. 18-21, 2007.
[10]	E.A. Heinz. Extended Futility Pruning. 21(2):75-83, 1998.
[11]	Ernst A. Heinz. How DarkThought Plays Chess. ICCA Journal, (3):166-176, 1997.
[12]	Feng-hsiung Hsu. IBM's Deep Blue Chess Grandmaster Chips. IEEE Micro, 19:70-81, 1999.
[13]	Robert M. Hyatt in Timothy Mann. A lockless Transposition-Table Implementation for Parallel Search. ICGA Journal, 25(1):36-39, 2002.
[14]	Hermann Kaindl, Reza Shams in Helmut Horacek. Minimax Search Algorithms With and Without Aspiration Windows. IEEE Trans. Pattern Anal. Mach. Intell., 13:1225-1235, December 1991.
[15]	Richard E. Korf. Depth-first Iterative-Deepening: An Optimal Admissible Tree Search. Artificial Intelligence, 27:97-109, 1985.
[16]	D. Levy, D. Broughton in M Taylor. The SEX algorithm in Computer Chess. ICCA Journal, 12(1):10-21, 1989.
[17]	T. A. Marsland in M. Campbell. Parallel Search of Strongly Ordered Game Trees. ACM Computing Surveys, 14:533-551, 1982.
[18]	Dylan Loeb Mcclain. Once Again, Machine Beats Human Champion at Chess. New York Times, 2006.
[19]	Fritz Reul. New Architectures in Computer Chess. doktorska disertacija, Tilburg University, 2009.
[20]	Fritz Reul. Static Exchange Evaluation with «^-Approach. ICGA Journal, 33(1):3-17, 2010.
[21]	Jonathan Schaeffer. The History Heuristic. ICCA Journal, 6(3):16-19, 1983.
[22]	Gunther Schrufer. A Strategic Quiescence Search. ICCA Journal, 12:3-9, 1989.
[23]	C. Shannon. Programming a computer for playing chess. Philosophical Magazine, 41(4):256, 1950.
[24]	Albert Zobrist. A New Hashing Method with Application for Game Playing. ICCA Journal, 13(2):69-73, 1970.
Borko Boškovic je diplomiral leta 2004 in doktoriral leta 2010 na Fakulteti za elektrotehniko racunalništvo in informatiko Univerze v Mariboru. Trenutno na omenjeni fakulteti zaseda mesto asistenta z doktoratom. Njegova podrocja raziskovanja so šahovski algoritmi in evolucijsko racunanje. Na strokovnem podrocju se ukvarja tudi s programskimi jeziki, integracijskim programiranjem in procesiranjem naravnih jezikov.
Janez Brest je diplomiral leta 1995, magistriral leta 1998 in doktoriral leta 2000 na Fakulteti za elektrotehniko racunalništvo in informatiko Univerze v Mariboru. Trenutno je redni profesor na omenjeni fakulteti. Njegova podrocja raziskovanja vkljucujejo evolucijsko racunanje, umetno inteligenco in optimiziranje. Njegova strokovna podrocja zajemajo tudi programske jezike, spletno programiranje, paralelno in porazdeljeno procesiranje.