Programtorsk dokumentace (v0.2.00)
====================================

Zdrojov kd program se skld z nsledujcch modul:

data.h	-	soubor definuje hlavn datov typy a obsahuje prototypy pouvanch funkc setdn podle pslunosti k modulm se strunmi popisky innosti.

book.c  -	modul, kter obsahuje zkladn funkci natn knihovny zahjen ze souboru.

inic.c	-	obsahuje funkci, kter nastavuje datov struktury do vchozho stavu, nastavuje hru do potenho stavu vetn postaven figurek do vchoz pozice. (nastaven struktury THra)

interf.c -	obsahuje zkladn vstupn vstupn operace, pedevm vstup achovnice na STDOUT a funkce realizujc pevod rznch formt zznamu tahu.

main.c	-	zde je hlavn pkazov smyka, kter nat zadan pkazy a provd zkladn obslun rutiny typu pota je na tahu, tedy bude thnout, kdy se m vypsat obsah achovnice, zda je mat nebo pat apod.

makemove.c -	obsahuje rutinu, kter provede zadan tah nad intern datovou strukturou, a kontroln rutinu vpotu nejlepho tahu z dan pozice (odkud se vol alfa-beta vpoet kaskdn variantou).

movegen.c -	funkce pmo souvisejc s generovnm ppustnch tah v dan pozici.

rules.c -	zde jsou naimplementovna pravidla, tedy funkce, kter dovedou rozhodnout, zda je tah ppustn nebo ne, zda je hr v achu apod.

search.c -	zde je jdro Alfa-Bety a jej varianty s tichm dohledvnm.

sort.c -	zde je naimplementovn tdc algoritmus pro tdn pedchozch vsledk kaskdn varianty. Protoe se jedn obvykle o 20-40 poloek, zvolil jsem jednoduch algoritmus pmho vbru. (sloitost O(n^2))
	
test.c - 	jednoduch funkce typu benchmark slouc pedevm pro intern testovn innosti zmn pi vvoji programu.

value.c -	ohodnocovac rutina, obsahuje ohodnocen materilu a pozice, matu a patu.

Kaskdn varianta alfa-bety s stenm dohledvnm do tichch pozic

Jak funguje alfa-beta procedura zde rozepisovat nebudu, zjemce odkazuji na mj refert, kter je k dispozici na m domovsk strnce nebo na jin WWW zdroje.
Vpoet nejlepho tahu v dan pozici obsluhuje funkce NejlepsiTah(), kter je v modulu makemove.c a funguje nsledujcm zpsobem.
Pipomnm, e pi vpotu do njak hloubky sluji jednotliv rovn stromu vpotu jaksi `odzadu`, tedy napklad pi vpotu do hloubky IQ=4 a SIQ=-2 je vrchol stromu oznaen rovn 4, jeho synov 3,2,1 a vtve v rovni 0. Tyto vtve se dle ohodnocuj `tichou alfa-betou` (pi dohledvn do tichch pozic) a jejich rovn pokrauj dle do zpornch sel -1,-2 - pozice v tto rovni jsou ohodnoceny Ohodnot(). Za zmnky stoj fakt, e pi nastaven globln promnn SIQ=0 se dn dohledvn do tichch pozic nekon, vpoet kon ohodnocovnm na rovni 0. Tedy zpt k funkci NejlepsiTah().
Nejprve je sputn vpoet alfa-beta s hloubkou 1, tedy jsou vygenerovny vechny tahy, provedeny nad kopi aktuln pozice a ohodnoceny. Ohodnocen spov v stenm dohledvn do tichch pozic do hloubky SIQ (cel nekladn slo). To znamen, e pokrauje alfa-beta do dal hloubky, ale generuje ji jen brac tahy, obranu proti achy a tzv. NULL tah (prost dn tah, hr se jakoby vzd tahu - supluje to vechny ostatn `nedleit` tahy). Tm zskme jaksi ohodnocen pozic, kter zohleduje do jist mry napaden a brnn figury (napadnutou dmu jakobychom nemli). Vsledek tto analzy do hloubky jedna promtneme do ohodnocen tah z vchoz zkouman pozice a setdme je od nejlepho k nejhormu.
Pot provedeme dal analzu tchto tah (v novm poad), tentokrte do hloubky 2 a se stejnou hloubkou dohledvn do tichch pozic. Zopakujeme setdn vsledku. Tento postup opakujeme pro hloubky 3,4,...,IQ. Nakonec pomoc pointeru na etzec vsledn nejlep tah vrt zpt (jeden z parametr).
Zdnliv tedy potme zbyten mnoho vc opakovan, ale v naprost vtin ppad dospjeme k celkov rychlejmu vpotu, ne kdybychom potali rovnou do konen hloubky, a to dky vlastnostem alfa-beta procedury, kter kdy dostv dve ty lep tahy a a pozdji ty hor pot mnohem rychleji, ne normln.

Strun popis testovn korektnosti pozice

Pokud uivatel zad tah (co program pozn podle toho, e zad pkaz, kter vyhovuje regulrnmu vrazu [a-h][1-8][a-h][1-8] funkc a1b1();), zavol se funkce PreJTT() - ta zjiuje (v tomto poad), jestli na prvnm poli vbec stoj figura, jestli figuru vlastn hr na tahu, a zda se pslun figura tmto zpsobem vbec po achovnici pohybuje, zda m volnou cestu.
Pokud spln vechna tato kritria, je zavolna dal funkce JeToTah(), kter dle zjiuje, zda eventuln bran figura je soupeova, test korektnosti ppadn rochady, bran pc mimochodem a v posledn ad, zda se tm krl nevystav achu. Pokud je ve v podku, funkce vrt 1.

Genertor tah

Genertor tah (funkce MoveGen()) m jeden integer parametr navc, kter slou k indikaci poadavku, kdy ns pouze zajm, zda njak ppustn tah existuje a nechceme generovat vechny. V tom ppad je funkce spn ukonena v okamiku nalezen prvnho (vyuvme toho pi detekci matu a patu). V ostatnm ppad posupuje tmto zpsobem:
Nejprve vygeneruje kolm a ikm tahy s volnou cestou dmami, vmi, a stelci. Potom vygeneruje while smykou vechny ostatn korektn tahy. Ped kadm pidnm vygenerovanho tahu do vsledn struktury se otestuje korektnost tahu pouze funkc JeToTah(), aby se dn test nedlal zbyten mnohokrt. Proto je tak testovn korektnosti tahu obecn rozloeno do funkc a1b1(), PreJTT(), JeToTah() a ostatnch pomocnch funkc.

Poznmky k XBOARD

Kvli komunikaci s programem XBOARD jsou poteba dv zmny. Za prv je poteba oetit signl SIGINT, konkrtn v naem ppad ignorovat. Jinak napklad u GNUchess slou pro pemlen v dob tahu protihre a podobn. Za druh je poteba oetit vstup a vstup, aby nebyl bufferovan. Pi pouit std. in/out na konzoli a klvesnici je toto provdno automaticky (pochopiteln), ale pi pouit rour, kter vytv XBOARD je poteba zruit bufferovn, aby byla komunikace s XBOARD bez problm. (viz dokumentace PROTOCOL).
Protoe oeten signlu nen obecn penositeln operace, jej kompilace je podmnna nadefinovnm makra UNIX. Pro kompilaci napklad pro DOS je poteba tuto definici zakomentovat nebo smazat.

Trocha kritiky

Pi testovn korektnosti tahu, generovn tah a jinch operacch nebyla pli vhodn zvolena datov reprezentace. Je poteba zbyten asto konvertovat mezi numerickou a stringovou notac tah. Nkter penen struktury nesou v nkterch mlo ppadech zbyten mnoho informace (napklad testovn JeVSachu(), kde by postaila achovnice, na druhou stranu i tak je to peneno pointerem ...).
Myslm, e pepsnm tchto prav by dolo k cca dvounsobnmu urychlen, co je na druhou stranu tak mlo, e by se to nevyplatilo.
Dnes se podstatnjch urychlen dosahuje ukldnm spotench pozic do pamti, haovac funkc nad touto reprezentac (nroky na operan pamt jsou pak nkolik MB, zhruba 5-10MB), co mimochodem tak zpsobuje problm s remzou pi trojnsobnm zopakovn pozice. Dle pro pohyby figur po achovnici jsou implementovna bitov pole a pro rzn operace se pouv velik mnostv bitovch operac (XOR, shift ...) - minimalizuj se tm pamov nroky a hlavn urychluje detekce rznch souvislost figur na achovnici, generovn tah apod. Dle se vyuvaj rzn obmny heuristickch metod, pedevm takzvan "metoda oknka" a jej odvozeniny s metodou nulovho oknka (NegaScout a MTD(f)).
Implementac tchto struktur a algoritm bychom doshli vkonu srovnatelnho s nejlepmi souasnmi achovmi programy (Rebel, ChessMaster, Crafty, DarkThought, Cilkchess a dalch) na jednoprocesorovch architekturch. Na druhou stranu jejich komplikovanost a rozshlost pevyuje rozsah tohoto ronkovho projektu.
