Programátorská dokumentace (v0.2.00)
====================================

Zdrojový kód program se skládá z následujících modulů:

data.h	-	soubor definuje hlavní datové typy a obsahuje prototypy používaných funkcí setříděné podle příslušnosti k modulům se stručnými popisky činnosti.

book.c  -	modul, který obsahuje základní funkci načítání knihovny zahájení ze souboru.

inic.c	-	obsahuje funkci, která nastavuje datové struktury do výchozího stavu, nastavuje hru do počátečního stavu včetně postavení figurek do výchozí pozice. (nastavení struktury THra)

interf.c -	obsahuje základní vstupně výstupní operace, především výstup šachovnice na STDOUT a funkce realizující převod různých formátů záznamu tahu.

main.c	-	zde je hlavní příkazová smyčka, která načítá zadané příkazy a provádí základní obslužné rutiny typu počítač je na tahu, tedy bude táhnout, 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 výpočtu nejlepšího tahu z dané pozice (odkud se volá alfa-beta výpočet kaskádní variantou).

movegen.c -	funkce přímo související s generováním přípustných tahů v dané pozici.

rules.c -	zde jsou naimplementována pravidla, tedy funkce, které dovedou rozhodnout, zda je tah přípustný nebo ne, zda je hráč v šachu apod.

search.c -	zde je jádro Alfa-Bety a její varianty s tichým dohledáváním.

sort.c -	zde je naimplementován třídící algoritmus pro třídění předchozích výsledků kaskádní varianty. Protože se jedná obvykle o 20-40 položek, zvolil jsem jednoduchý algoritmus přímého výběru. (složitost O(n^2))
	
test.c - 	jednoduchá funkce typu benchmark sloužící především pro interní testování účinnosti změn při vývoji programu.

value.c -	ohodnocovací rutina, obsahuje ohodnocení materiálu a pozice, matu a patu.

Kaskádní varianta alfa-bety s částečným dohledáváním do tichých pozic

Jak funguje alfa-beta procedura zde rozepisovat nebudu, zájemce odkazuji na můj referát, který je k dispozici na mé domovské stránce nebo na jiné WWW zdroje.
Výpočet nejlepšího tahu v dané pozici obsluhuje funkce NejlepsiTah(), která je v modulu makemove.c a funguje následujícím způsobem.
Připomínám, že při výpočtu do nějaké hloubky čísluji jednotlivé úrovně stromu výpočtu jaksi `odzadu`, tedy například při výpočtu do hloubky IQ=4 a SIQ=-2 je vrchol stromu označen úrovní 4, jeho synové 3,2,1 a větve v úrovni 0. Tyto větve se dále ohodnocují `tichou alfa-betou` (při dohledávání do tichých pozic) a jejich úrovně pokračují dále do záporných čísel -1,-2 - pozice v této úrovni jsou ohodnoceny Ohodnot(). Za zmínky stojí fakt, že při nastavení globální proměnné SIQ=0 se žádné dohledávání do tichých pozic nekoná, výpočet končí ohodnocováním na úrovni 0. Tedy zpět k funkci NejlepsiTah().
Nejprve je spuštěn výpočet alfa-beta s hloubkou 1, tedy jsou vygenerovány všechny tahy, provedeny nad kopií aktuální pozice a ohodnoceny. Ohodnocení spočívá v částečném dohledávání do tichých pozic do hloubky SIQ (celé nekladné číslo). To znamená, že pokračuje 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 všechny ostatní `nedůležité` tahy). Tím získáme jakési ohodnocení pozic, které zohledňuje do jisté míry napadené a bráněné figury (napadnutou dámu jakobychom neměli). Výsledek této analýzy do hloubky jedna promítneme do ohodnocení tahů z výchozí zkoumané pozice a setřídíme je od nejlepšího k nejhoršímu.
Poté provedeme další analýzu těchto tahů (v novém pořadí), tentokráte do hloubky 2 a se stejnou hloubkou dohledávání do tichých pozic. Zopakujeme setřídění výsledku. Tento postup opakujeme pro hloubky 3,4,...,IQ. Nakonec pomocí pointeru na řetězec výsledný nejlepší tah vrátí zpět (jeden z parametrů).
Zdánlivě tedy počítáme zbytečně mnoho věcí opakovaně, ale v naprosté většině případů dospějeme k celkově rychlejšímu výpočtu, než kdybychom počítali rovnou do konečné hloubky, a to díky vlastnostem alfa-beta procedury, která když dostává dříve ty lepší tahy a až později ty horší počítá mnohem rychleji, než normálně.

Stručný popis testování korektnosti pozice

Pokud uživatel zadá tah (což program pozná podle toho, že zadá příkaz, který vyhovuje regulárnímu výrazu [a-h][1-8][a-h][1-8] funkcí a1b1();), zavolá se funkce PreJTT() - ta zjišťuje (v tomto pořadí), jestli na prvním poli vůbec stojí figura, jestli figuru vlastní hráč na tahu, a zda se příslušná figura tímto způsobem vůbec po šachovnici pohybuje, zda má volnou cestu.
Pokud splní všechna tato kritéria, je zavolána další funkce JeToTah(), která dále zjišťuje, zda eventuální braná figura je soupeřova, test korektnosti případné rochady, braní pěšců mimochodem a v poslední řadě, zda se tím král nevystaví šachu. Pokud je vše v pořádku, funkce vrátí 1.

Generátor tahů

Generátor tahů (funkce MoveGen()) má jeden integer parametr navíc, který slouží k indikaci požadavku, kdy nás pouze zajímá, zda nějaký přípustný tah existuje a nechceme generovat všechny. V tom případě je funkce úspěšně ukončena v okamžiku nalezení prvního (využíváme toho při detekci matu a patu). V ostatním případě posupuje tímto způsobem:
Nejprve vygeneruje kolmé a šikmé tahy s volnou cestou dámami, věžěmi, a střelci. Potom vygeneruje while smyčkou všechny ostatní korektní tahy. Před každým přidáním vygenerovaného tahu do výsledné struktury se otestuje korektnost tahu pouze funkcí JeToTah(), aby se žádný test nedělal zbytečně mnohokrát. Proto je také testování korektnosti tahu obecně rozloženo do funkcí a1b1(), PreJTT(), JeToTah() a ostatních pomocných funkcí.

Poznámky k XBOARD

Kvůli komunikaci s programem XBOARD jsou potřeba dvě změny. Za prvé je potřeba ošetřit signál SIGINT, konkrétně v našem případě ignorovat. Jinak například u GNUchess slouží pro přemýšlení v době tahu protihráče a podobně. Za druhé je potřeba ošetřit vstup a výstup, aby nebyl bufferovaný. Při použití std. in/out na konzoli a klávesnici je toto prováděno automaticky (pochopitelně), ale při použití rour, které vytváří XBOARD je potřeba zrušit bufferování, aby byla komunikace s XBOARD bez problémů. (viz dokumentace PROTOCOL).
Protože ošetření signálu není obecně přenositelná operace, její kompilace je podmíněna nadefinováním makra UNIX. Pro kompilaci například pro DOS je potřeba tuto definici zakomentovat nebo smazat.

Trocha kritiky

Při testování korektnosti tahu, generování tahů a jiných operacích nebyla příliš vhodně zvolena datová reprezentace. Je potřeba zbytečně často konvertovat mezi numerickou a stringovou notací tahů. Některé přenášené struktury nesou v některých málo případech zbytečně mnoho informace (například testování JeVSachu(), kde by postačila šachovnice, na druhou stranu i tak je to přenášeno pointerem ...).
Myslím, že přepsáním těchto úprav by došlo k cca dvounásobnému urychlení, což je na druhou stranu tak málo, že by se to nevyplatilo.
Dnes se podstatnějších urychlení dosahuje ukládáním spočtených pozic do paměti, hašovací funkcí nad touto reprezentací (nároky na operační pamět jsou pak několik MB, zhruba 5-10MB), což mimochodem také způsobuje problém s remízou při trojnásobném zopakování pozice. Dále pro pohyby figur po šachovnici jsou implementována bitová pole a pro různé operace se používá veliké množství bitových operací (XOR, shift ...) - minimalizují se tím paměťové nároky a hlavně urychluje detekce různých souvislostí figur na šachovnici, generování tahů apod. Dále se využívají různé obměny heuristických metod, především takzvaná "metoda okénka" a její odvozeniny s metodou nulového okénka (NegaScout a MTD(f)).
Implementací těchto struktur a algoritmů bychom dosáhli výkonu srovnatelného s nejlepšími současnými šachovými programy (Rebel, ChessMaster, Crafty, DarkThought, Cilkchess a dalších) na jednoprocesorových architekturách. Na druhou stranu jejich komplikovanost a rozsáhlost převyšuje rozsah tohoto ročníkového projektu.
