Hrací algoritmus pro deskové hry

ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE FAKULTA ELEKTROTECHNICKÁ KATEDRA POČÍTAČŮ

DIPLOMOVÁ PRÁCE Hrací algoritmus pro deskové hry

Praha, 2006

David Šafránek

Prohlášení Prohlašuji, že jsem svou diplomovou práci vypracoval samostatně a použil jsem pouze podklady (literaturu, projekty, SW atd.) uvedené v přiloženém seznamu. Nemám závažný důvod proti užití tohoto školního díla ve smyslu § 60 Zákona č.121/2000 Sb. , o právu autorském, o právech souvisejících s právem autorským a o změně některých zákonů (autorský zákon).

V Praze dne ………………………

Podpis: ………………………

2

Poděkování Chtěl bych zde poděkovat především své babičce a přítelkyni za psychickou a materiální podporu bez které bych jen stěží tuto práci uskutečnil. Dále děkuji vedoucímu této práce, že mi poskytl prostor k uplatnění.

3

Abstrakt Práce se zabývá použitými algoritmy pro prohledávání stavového prostoru a zhodnocením jejich významu v obecném algoritmu. Součástí práce je program umožňující hru několika různých her proti počítači, jejich ukládání, načítání a editaci ve formě herního stromu a s množstvím dalších užitečných funkcí.

Abstract This work deals with used algorithms for searching state space and evaluates their importance in general algorithm. Part of this work is program which can play any different games versus computer, their saving, loading and editing in game tree form and with many useful functions.

4

Obsah 1 Úvod............................................................................................................................................................7 2 Základní pojmy...........................................................................................................................................8 3 Deskové hry..............................................................................................................................................10 3.1 Šachy (Chess)....................................................................................................................................10 3.2 Dáma (Draughts, Checkers)..............................................................................................................10 3.3 Exploze (Automaton Wars)...............................................................................................................10 3.4 Jungle (Dou Shou Qi, Game of fighting animals).............................................................................10 3.5 Piškvorky (Go-moku, Connect-four)................................................................................................10 3.6 Othello (Reversi)...............................................................................................................................10 3.7 Varianty.............................................................................................................................................11 4 Rozbor možných postupů.........................................................................................................................12 4.1 Reprezentace pole.............................................................................................................................12 4.2 Hrací deska........................................................................................................................................12 4.2.1 Minimální velikost – H×W.......................................................................................................12 4.2.2 Rozšířená deska – (H+4) × (W+2)............................................................................................12 4.2.3 Reprezentace – mocnina dvou...................................................................................................13 4.2.4 Bitová reprezentace...................................................................................................................14 4.2.5 Reprezentace seznamem kamenů..............................................................................................14 4.2.6 Zhodnocení................................................................................................................................15 4.3 Tahy...................................................................................................................................................15 4.3.1 Reprezentace tahů......................................................................................................................15 4.3.2 Generátor tahů...........................................................................................................................17 4.3.3 Vrácení tahů...............................................................................................................................17 4.4 Prohledávání......................................................................................................................................17 4.4.1 Minimax, negamax....................................................................................................................18 4.4.2 Alfa-beta....................................................................................................................................18 4.4.3 Okno očekávání (Aspiration Window)......................................................................................18 4.4.4 Futility pruning..........................................................................................................................18 4.4.5 Nulový tah (Null-move)............................................................................................................19 4.4.6 Negascout a MTD.....................................................................................................................19 4.4.7 Třídění pořadí tahů....................................................................................................................19 4.4.8 Hledání klidu.............................................................................................................................20 4.4.9 Efekt horizontu..........................................................................................................................20 4.4.10 Interaktivní prohlubování........................................................................................................20 4.5 Oceňování.........................................................................................................................................21 4.5.1 Herní typy..................................................................................................................................22 4.5.2 Materiální kritérium..................................................................................................................22 4.5.3 Poziční kritérium.......................................................................................................................22 4.5.4 Spekulativní ocenění pozice......................................................................................................22 4.5.5 Příklad vytvoření oceňovacích funkcí.......................................................................................23 4.6 Rozptylovací tabulky (hash tables)...................................................................................................23 4.6.1 Otevřené rozptylování...............................................................................................................24 4.6.2 Změna velikosti rozptylovací tabulky za chodu........................................................................24 4.7 Záznam hlavní varianty.....................................................................................................................25 4.7.1 Průběžné kopírování..................................................................................................................25 4.7.2 Využití rozptylovacích tabulek..................................................................................................26 4.8 Knihovna zahájení.............................................................................................................................26 4.9 Koncovky..........................................................................................................................................26 4.10 Hospodaření s časem.......................................................................................................................27 4.11 Využití času soupeře (Ponder).........................................................................................................27 4.12 Sociální pravidla..............................................................................................................................28 4.12.1 Faktor remízy (Contempt Value).............................................................................................28 4.12.2 Faktor vzdání (Resign Value)..................................................................................................28 4.13 Zhodnocení......................................................................................................................................28

5

5 Aplikace....................................................................................................................................................29 5.1 Vývojové prostředky.........................................................................................................................29 5.2 Volba vývojového prostředí..............................................................................................................29 5.3 Postup pro sestavení aplikace............................................................................................................29 5.4 PGN rozšíření....................................................................................................................................30 5.5 Zdrojový kód.....................................................................................................................................31 5.5.1 Funkčnost..................................................................................................................................31 5.5.2 Výjimky.....................................................................................................................................31 5.5.3 Optimalizace..............................................................................................................................31 5.5.4 Přidání další hry.........................................................................................................................35 5.5.5 Obecně.......................................................................................................................................35 5.6 Konfigurační soubory........................................................................................................................36 5.7 Grafika...............................................................................................................................................37 5.7.1 Metody zobrazeni kamenů........................................................................................................37 5.8 Zvuk..................................................................................................................................................37 5.9 Síla hry..............................................................................................................................................38 5.10 Srovnání s konkurencí.....................................................................................................................38 5.11 Nároky na vybavení........................................................................................................................39 5.11.1 Software...................................................................................................................................39 5.11.2 Hardware.................................................................................................................................39 5.12 Instalace...........................................................................................................................................39 5.13 Náhled aplikace...............................................................................................................................39 5.14 Aktualizace......................................................................................................................................40 6 Závěr.........................................................................................................................................................41 7 Seznam obrázků a tabulek........................................................................................................................42 7.1 Obrázky.............................................................................................................................................42 7.2 Tabulky..............................................................................................................................................42 8 Použitá literatura a odkazy........................................................................................................................43 9 Příloha.......................................................................................................................................................44

6

1 Úvod Tato práce se zabývá zhodnocením a použitelností algoritmů pro hledání tahů v deskových hrách. Obecných her je mnoho, my se budeme zabývat převážně hrami deskovými, jakožto podkapitolou her stolních. Mezi hlavní vlastnosti deskových her patří použití hrací desky (odtud název) rozdělené na pole, po kterých se přesunují resp. umísťují kameny. Další důležitá vlastnost je znalost úplné informace. Tedy známe veškeré informace, které jsou k dispozici, zrovna tak jako náš soupeř. Hry s neúplnou informací jsou například karetní hry. Nejedná-li se o hry s úplnou informací, lze tento algoritmus také použít, ale je třeba neznámou informaci odhadnout, omezit, či zcela přesně dopočítat, jak se tomu děje u karetních her. Tohoto faktu se pak využije v oceňovací funkci a v generátoru možných tahů. Část algoritmů pro deskové hry se zabývá rozhodováním jaký tah v dané pozici je ten nejlepší. Tyto algoritmy pro deskové hry mají mnoho společného, většina z nich využívá prohledávání stavového prostoru do hloubky minimaxovou (resp. negamaxovou) metodou. Existují však i hry, kde je tato metoda velmi málo použitelná v důsledku velkého vlivu náhody a nemožnosti předvídat dopředu. Stavový prostor je konečná množina stavů, do kterých se může partie dostat z výchozí pozice. Je-li tento stavový prostor dostatečně malý, stačí jen implementovat generátor tahů a funkce pro provádění tahů pro danou hru. Je-li prostor větší a absolutní řešení je mimo naše možnosti prohledávání, je třeba zavést ještě oceňovací funkci, která by měla v ocenění odrážet stav pozice. Využili jsme znalostí zde uvedených a vytvořili aplikaci, jenž najde využití i u profesionálních hráčů. Její nejdůležitější vlastnosti jsou: • • • • • • • • • • • • • • • •

podpora deskových her jako jsou šachy, dáma, exploze a jejich varianty umožnění hry proti počítači zobrazení výsledků analýzy myslícího algoritmu a výpis hlavních variant grafické rozhraní s nastavitelným vzhledem desky a kamenů editace partií a pozic stromová struktura tahů partie načítání a ukládání ve formátech PGN, FEN a EPD knihovna zahájení včetně názvů pro šachy měření času na tah a partii pomocí hodin časové a jiné kontroly nastavení parametrů vyhledávacího algoritmu nastavení parametrů motoru a časových kontrol a pro oba hráče více-souborová podpora sociální pravidla (vzdání se, nabídnutí, přijmutí, odmítnutí remízy) UCI šachový motor použitelný s jiným GUI export diagramů do HTML formátu a další funkce

Práce je členěna do dvou hlavních kapitol. Ve čtvrté kapitole provádíme rozbor možných postupů. Kapitola pátá se zabývá konkrétní aplikací.

7

2 Základní pojmy Tato kapitola obsahuje definice základních pojmů, s kterými se v dalším textu setkáme. Kámen (piece) Souhrn všech typů kamenů, které se mohou v dané variantě hry vyskytovat. Kámen lze vkládat na pole. Pole (square) Ohraničená část hrací desky, může být prázdná, resp. na ni může být jen jeden kámen, který může patřit různému hráči. Pole bývá nejčastěji čtvercové, trojúhelníkové, hexadecimální či jiného tvaru. Případně může být reprezentováno spojnicí čar, což je v podstatě předchozí případ, jen grafická reprezentace je jiná. Deska (board) Hrací deska se skládá z polí, které na sebe nějakým způsobem navazují. Šachovnice (chessboard) Speciální hrací deska se světlými a tmavými poli o rozměrech 8×8 polí. Používá se hlavně v šachách, odkud je její název. Pozice (position) Obsahuje informace o desce, vyhozených kamenech, hráči který je na tahu a další specifické informace. Uzel (node) Uzel z herního stromu. V deskových hrách se jedná v podstatě o pozici, kterou tento uzel reprezentuje. Partie, hra (game) Tvořena stromem hraných tahů a dodatečných informací o čase a dalších informacích hráčů. Databáze (database) Databáze partií. Pro ukládání se většinou používá standard PGN, ukládající partie v textové podobě. Ocenění (score , value) Hodnota pozice jako výsledek oceňovací funkce, kde je zahrnuté materiální (počet kamenů) a poziční kritérium. Nula znamená vyrovnanou pozici, kladná hodnota výhodu strany na tahu, záporná hodnota opak. Stavový prostor Jedná se o prostor stavů pozice, které na desce mohou nastat po provedení permutace tahů z výchozí pozice.

8

Prohledávaný strom (search tree) Část stavového prostoru, jehož kořenem je aktuální pozice. Z něj vedou hrany do dalších uzlů. Tento strom je zvykem zobrazovat kořenem vzhůru. Pojem herní strom je vysvětlen zde [Tree]. Prohledávání (searching) Výpočet algoritmu, který ze zadané pozice hledá nejlepší tah. Horizont Úroveň tahů v prohledávaném stromu, kde v aktuální interakci končíme propočet. Prořezávání (pruning) Ořezávání větví prohledávaného stromu za účelem snížení počtu uzlů nutných k prozkoumání. Snižuje se tak větvení stromu, což urychluje vyhledávání. Rozšíření (extension) Opak prořezávání prodlužuje hlavní varianty. Např. dohledání do klidné pozice. Varianta (variant) Herní varianta deskové hry. Například sebevražedné (suicide) šachy a množství variant pravidel v dámě. Zahájení (opening) Název prvotní posloupnosti tahů (s možností prohození). V šachách např. sicilská obrana. Varianta (variantion) Varianta zahájení. V šachách např. dračí varianta sicilské obrany. Motor (engine) Program, jehož úkolem je po zadání vstupních hodnot hledat tahy a jako výstup vrátit výsledky. Taktika Pro úspěšnou taktiku je třeba propočet do hloubky. Např. zisk kamenů po taktickém úderu. Strategie Složitější uplatnění pozičních pravidel se spojením s plánovaným vývojem pozice.

9

3 Deskové hry Pojem hry je velmi obecný a spadá pod něj mnoho kategorií, my se zaměříme hlavně na stolní hry a podkapitolu deskových her (čímž vyloučíme karetní a jiné hry). Deskových her je po světě nespočetně mnoho a stále vznikají nové viz. [Hry] nebo [Zillion]. Samozřejmě je zde i snaha opačná jak je vidět např. v organizaci mezinárodní dámy, což uvítají zejména příznivci sportovního ducha. Následuje seznam deskových her na které se budeme v textu odkazovat.

3.1 Šachy (Chess) U nás nejrozšířenější hra v níž se udržují i národní a světové databáze výkonů hráčů (Elo). Implementaci této hry můžeme použít pro snadné porovnání síly algoritmu. Pro tyto účely je program rozdělen do dvou bloků (herní algoritmus a grafické rozhraní). Herní algoritmus je pak obalen UCI rozhraním, a vznikl tak další program – motor, který je možno použít v [Arena], společně s jiným motorem a po automatickém sehrání několika partií zjistit relativně přesně sílu hry.

3.2 Dáma (Draughts, Checkers) Jednoduchá hra, převážně taktická, bez složitých strategických pravidel. Toho lze využít a generátor tahů lze napsat kompletně v asembleru. Rychlost propočtu je pak opravdu vysoká. Varianty se liší snížením pohyblivosti dam, odebírání kamenů zpětným skokem, povinnost braní v maximálním rozsahu, a dalšími pravidly, což komplikuje obecnou implementaci generátoru tahů.

3.3 Exploze (Automaton Wars) Na rozdíl od ostatních se jedná o poziční hru, kde v koncovce rozhoduje především taktika.

3.4 Jungle (Dou Shou Qi, Game of fighting animals) Na tuto hru jsme narazili v knize [Klub] a rozhodli jsme se jí implementovat pro její jednoduchost, využitelnou zejména při ladění. Pravidla jsou k nalezení zde [Jungle].

3.5 Piškvorky (Go-moku, Connect-four) Jsou obsaženy ve dvou základních variantách – klasické a gravitační (vertikální) piškvorky. Vzhledem k jejich odlišnosti, je velmi odlišná i strategie. Proto je zapotřebí použít různé generátory tahů a zejména oceňování.

3.6 Othello (Reversi) Hra na první pohled podobná piškvorkům, tím, že se na desku vkládají kameny, ale jinak je zcela odlišná. Pravidla jsou k dispozici zde [Othello].

10

3.7 Varianty Pravidla standardních variant her jsou k nalezení na [Vari]. U většiny her se dají uvažovat změny v pravidlech jako 1) změna velikosti hrací desky 2) povinnost braní 3) sebevražedný herní styl (pak je třeba změnit pravidla na povinnost braní, aby hra měla smysl) 4) znovu nasazování zajatých kamenů a další změny. Uvažovali jsme také o hře GO, ale po nastudování základních pravidel a neznalosti hlubších strategických principů jsme ji zavrhli jako příliš komplikovanou.

11

4 Rozbor možných postupů 4.1 Reprezentace pole Pro paměťovou reprezentaci jednoho pole ve většině případů stačí jeden bajt, což dává 256 hodnot. Jedna hodnota je použita pro prázdné pole a druhá pro pole zakázané (použití těchto polí bude vysvětleno dále). Zbývá 254 hodnot, což pokryje 127 kamenů obou barev. To je více než dostačující pro všechny hry vzhledem k tomu, že v šachách si vystačíme se šesti, v japonských šachách se čtrnácti kameny. Implementaci barvy lze provést buď vyhrazením bitu, nebo určením znaménka. Nevýhoda první metody je, že pro zjišťování barvy kamene nebo jeho typu je třeba provést maskování. Za nevýhodu druhé metody se považuje to, že pro zjištění typu kamene je třeba provést absolutní hodnotu, naopak pro zjištění barvy stačí testovat zda je pole menší či větší než nula.

4.2 Hrací deska Ve většině případů je deska tvořena ze čtvercových polí případně bývá složena ze šestiúhelníků podobně jako včelí plástev. Rozdíl proti čtvercovým polím je nepatrný. Přepis na lineární pole je pak po řádcích, jen posunů do sousedních polí je šest. Podobně i jiná n-úhelníková pole lze reprezentovat předešlým způsobem. Nejobecnější, ale zároveň nejpomalejší je pro každé pole vyrobit seznam jeho sousedů. Následuje popis reprezentací desky v paměti a jejich použitelnost v obecném případě.

4.2.1 Minimální velikost – H×W Nejjednodušší je klasická reprezentace dvourozměrného pole jednorozměrným. Nevýhoda je testování, zda není index mimo platný rozsah, což se dá redukovat následující reprezentací. +--+--+--+--+--+--+--+--+ |24|25|26|27|28|29|30|31| +--+--+--+--+--+--+--+--+ |16|17|18|19|20|21|22|23| +--+--+--+--+--+--+--+--+ | 8| 9|10|11|12|13|14|15| +--+--+--+--+--+--+--+--+ | 0| 1| 2| 3| 4| 5| 6| 7| +--+--+--+--+--+--+--+--+

Obr. 1:

Indexování polí na desce velikosti 4×8

4.2.2 Rozšířená deska – (H+4) × (W+2) Jedná se o desku, která vznikne přidáním polí, které ve skutečnosti na desce vůbec nejsou.

12

+--+--+--+--+--+--+--+--+ |51|52|53|54|55|56|57|58| +--+--+--+--+--+--+--+--+ |41|42|43|44|45|46|47|48| +--+--+--+--+--+--+--+--+ |31|32|33|34|35|36|37|38| +--+--+--+--+--+--+--+--+ |21|22|23|24|25|26|27|28| +--+--+--+--+--+--+--+--+

Obr. 2:

Indexování polí na desce velikosti 4×8

Okraje se volí tak, aby pohyb všech kamenů (obyčejně stačí pouze jezdec, případně nejpohyblivější kámen) ze všech polí (většinou stačí pouze krajní pole) směřoval na index existujícího pole, které má však hodnotu zarážky, což znamená, že na toto pole se nedá táhnout. Tímto trikem se ušetří testování zda je index legální. Není tedy třeba používat podmínky, zda nepřekračujeme okraj desky, což znatelně zrychlí generování posunujících tahů. V generátoru tahů GO nebo piškvorků tohoto triku sice nevyužijeme, ale okraj o velikosti jednoho pole se nám hodí v oceňovací funkci, kdy počítáme kvalitu umístěných kamenů. Naopak nevýhoda je, že dojde ke zvětšení desky, což má za příčinu větší paměťovou reprezentaci (pro šachy je to 10×12=120 oproti 8×8=64, což je téměř dvojnásobek). Pohyb kamenů na desce s touto reprezentací je zřejmý. Např. diagonální pohyb se pak provádí podle následujících indexů (+11, –11, +9, – 9). V dámě stačí použít normální desku, ale tak bychom využili jen polovinu (světlé, případně tmavé pole desky). Využijeme toho, že nelze posouvat o jedno pole ortogonálně, takže stačí index po dvou polích zvýšit o jedna, jak je vidět na následujícím obrázku. +--+--+--+--+--+--+--+--+ | |19| |20| |21| |22| +--+--+--+--+--+--+--+--+ |14| |15| |16| |17| | +--+--+--+--+--+--+--+--+ | |10| |11| |12| |13| +--+--+--+--+--+--+--+--+ |05| |06| |07| |08| | +--+--+--+--+--+--+--+--+

Obr. 3:

Rozložení indexů v dámě

Pohyb základního kamene se provádí podle následujících indexů (+4, +5). Jak je vidět, zde nám stačí použít zarážku jen na každém druhém řádku (pole s indexy 9 a 18).

4.2.3 Reprezentace – mocnina dvou Index pole zde reprezentuje hodnota, jejíchž dolní bity určují sloupec a horní řádek. Pro zjištění, zda je pole legální, stačí testovat nulovost po použití bitové masky (např. 88h pro desku 8×8, 210h pro desku 16×16 atd.).

13

+--+--+--+--+--+--+--+--+ |71|72|73|74|75|76|77|78| +--+--+--+--+--+--+--+--+ |61|62|63|64|65|66|67|68| ......................... |10|11|12|13|14|15|16|17| +--+--+--+--+--+--+--+--+ |00|01|02|03|04|05|06|07| +--+--+--+--+--+--+--+--+

Obr. 4:

Reprezentace mocnina dvou (88h)

Předchozí obrázek ukazuje reprezentaci pro desku 8×8. Čísla jsou pro větší názornost uvedena v hexadecimální číselné soustavě. Jsme-li např. na poli s indexem 0 a posuneme se dolů získáme index 80, který po použití bitové masky 88h dává nenulovou hodnotu značící, že se nacházíme mimo platný rozsah. Na následujícím obrázku je alternativní varianta s posunutím. +--+--+--+--+--+--+--+--+ |B4|B5|B6|B7|B8|B9|BA|BB| +--+--+--+--+--+--+--+--+ |A4|A5|A6|A7|A8|A9|AA|AB| ......................... |54|55|56|57|58|59|5A|5B| +--+--+--+--+--+--+--+--+ |44|45|46|47|48|49|4A|4B| +--+--+--+--+--+--+--+--+

Obr. 5:

Reprezentace mocnina dvou

Hlavní nevýhoda této metody je, že lze použít pouze pro desky velikosti násobku dvou. V obecném případě tato reprezentace není moc vhodná.

4.2.4 Bitová reprezentace Od předchozích je odlišná v tom, že neobsahuje jediné pole, ale pro každý druh kamene jedno. Počet kamenů zde není omezen, ale paměťová reprezentace pro víc než osm kamenů je vyšší (jedno pole zabírá osminu předchozího). Je-li počet polí v řádku roven délce slova procesoru (32 případně 64) lze provádět velmi rychle bitové operace. Toho však obecně nelze dosáhnout a tato reprezentace by byla komplikovanější než předchozí.

4.2.5 Reprezentace seznamem kamenů Další metodou je mít k dispozici seznam kamenů a polí kde se nachází. Procházení je rychlé, ale problém nastane při generování tahů, když chceme vědět co je na pole, kam můžeme táhnout. Toto se v generátoru tahů provádí nejčastěji a proto je obecně tato metoda pomalejší. Využití najde při použití velké desky a malého počtu kamenů. Často se používají obě metody zároveň, což dovoluje rychle generovat tahy i počítat materiál pro ocenění pozice.

14

4.2.6 Zhodnocení Někdy si nevystačíme jen s jednou deskou, ale potřebujeme jich použít více. Např. ve hře jungle je třeba určit zda je na poli voda, nebo v šachách, zda se z pole dá jít pěšcem o dvě pole vpřed. Toto jsou informace statické, v průběhu hry nebo propočtu se nemění a proto je lépe je oddělit kvůli paměťovým přesunům a použít jako další vrstvu, a ne zahrnout do záznamu pole. Na vliv reprezentace hrací desky může mýt vliv třeba i její velikost. Např. pro šachovnici velikosti 8×8 (celkem 64 polí) je optimální bitová reprezentace zabírající 64 bitů. Těchto šachovnic je více, každá určuje zda se na polí nachází kámen určité barvy, je jich proto potřeba dvojnásobek typu kamenů. Tedy pro šachy 12, což celkem zabere o 50% více paměti než klasická reprezentace. Mezi výhody patří však rychlejší přístup k pěšcovým strukturám, čehož se dá využít v oceňování. Pro ukázku indexování polí na desce u různých her stačí zadat v programu technickou notaci a zobrazit souřadnice na polích.

4.3 Tahy 4.3.1 Reprezentace tahů Požadavky na formát tahu jsou jednak, aby bylo možné tah podle datové struktury uskutečnit, a aby pokud možno šlo tah i vrátit. Druhý požadavek není nutný. U malé desky nebo při větší složitosti prováděného tahu (např. hry exploze, dáma) je lepší vrátit tah kopírováním celého stavu pozice. U většiny deskových her si vystačíme se statickou velikostí struktury pro tah. U dámy je však potřeba uvažovat i různě dlouhé skoky, takže velikost datové struktury nelze jednoznačně určit. První možností je použití statické velikosti s dostatečnou rezervou, jehož nevýhodou je nevyužité místo. Naopak mezi výhody patří, že tah zůstává sjednocen a lze tyto tahy po vygenerování jednoduše setřídit. Kromě použití tohoto statického formátu s omezením můžeme větvení skoku realizovat jako stromovou strukturu, čili dílčí skok reprezentovat jako list stromu s hodnotou, zda větev pokračuje. Nevýhoda je, že skokové tahy nemůžeme provádět od nejdelšího skoku, ale postupně, což se neslučuje s technikami prohledávání, kde je důležité začít nejlepším tahem, tudíž nejdelším skokem. Zaměřme se nyní na statickou reprezentaci. Pro dámu hranou na 8×8 polí, nám teoreticky stačí maximálně 19 polí (TSTART ,T1..T18), jak je uvedeno v následujícím příkladu. Náš kámen (značen oo) se nachází na pozici TSTART.

15

+--+--+--+--+--+--+--+--+ | | | | | | | | | +--+--+--+--+--+--+--+--+ | | | | | | | | | +--+--+--+--+--+--+--+--+ | |**| |**| |**| | | +--+--+--+--+--+--+--+--+ | | | | | | | | | +--+--+--+--+--+--+--+--+ | |**| |**| |**| | | +--+--+--+--+--+--+--+--+ | | | | | | | | | +--+--+--+--+--+--+--+--+ | |**| |**| |**| | | +--+--+--+--+--+--+--+--+ |oo| | | | | | | | +--+--+--+--+--+--+--+--+

Obr. 6:

Příklad nejdelšího možného skoku

Na následujícím obrázku je vidět příklad ukázky reprezentace tahů. Náš kámen (oo) se opět nachází na pozici TSTART. +--+--+--+--+--+--+--+--+ |T1| | | |T3| | | | +--+--+--+--+--+--+--+--+ | |**| |**| | | | | +--+--+--+--+--+--+--+--+ | | |T2| | | |T4| | +--+--+--+--+--+--+--+--+ | | | |**| |**| | | +--+--+--+--+--+--+--+--+ | | | | |oo| | | | +--+--+--+--+--+--+--+--+

Obr. 7:

Příklad pro ukázku reprezentace tahů v dámě

V první variantě uložíme následující: 0: TSTART, T2 1: TSTART, T2, T1 2: TSTART, T2, T3 3: TSTART, T2, T4 Výraz za dvojtečkou určuje cílová pole jimiž kámen prochází. Druhá varianta: 0: 0, TSTART 1: 0, T2 2: 0, T1 3: 1, T3 4: 2, T4 Výraz za dvojtečkou určuje počet tahů zpět a následuje opět cílové pole.

16

My jsme vzhledem k obecnosti přístupu a obtížnosti implementace zvolili první variantu.

4.3.2 Generátor tahů Zde tráví program značné množství času z důvodu, že musí prozkoumat celou desku. Proto je vhodné použít předzpracování, jako třeba připravit tabulky posunu kamenů, které tento proces urychlí. Hlavním úkolem generátoru tahů je vytvořit všechny pseudolegální tahy. Pseudo proto, že pro určité tahy (např. odtah vázaným kamenem) je časově náročné určit, zda jsou legální, takže tento fakt bude zjištěn o tah dále. Mat je vlastně tah, po kterém bude neodvratitelně následovat tah sebrání krále, takže by se eventuálně mohl i uskutečnit. Takto by se mohlo postupovat i dále, např. by partie mohla skončit při hrozbě neodvratitelného matu. Generovat můžeme buď všechny tahy s tím, že se při prohledávání použijí jen některé nebo jejich část a ušetřit tím potřebný čas. Výhoda generování všech tahů je, že můžeme pozici rovnou i ocenit a využít třídící algoritmy pro všechny tahy naráz. Pro jednoduchost zde lze provést spojení generátoru s oceňovací funkcí, která využívá pohyblivosti kamenů. Další důvod hovořící pro generování všech tahů je, aby byl známý index tahu z důvodů rozptylovací tabulky. Chceme-li použít v rozptylovací tabulce jen index tahu namísto celého tahu, který může být i delší, je třeba pokaždé vygenerovat všechny tahy. Druhá možnost je použít inkrementální metodu, která vygeneruje pokud možno co nejlepší tahy, aby se nemuseli generovat ostatní. Vzhledem k vyhledávacím technikám alfa-beta stačí totiž ve většině případů nalézt dostatečně dobrý tah a zbylé se provádět vůbec nebudou. Pokud je třeba můžeme na dosavadní výsledky navázat a dodatečně vygenerovat zbylé tahy. Pro hry s jednoduchým generováním tahů (např. piškvorky) je lépe použít metodu generování všech tahů, zatímco např. v šachách je značně rychlejší metoda inkrementální.

4.3.3 Vrácení tahů Zde jsou dvě možnosti, buď si zapamatovat stav celé pozice a ten pak obnovit (kompletní) nebo při generování tahu uložit informace pro vrácení tahu (speciální). První možnost je jednodušší na implementaci a při jednoduchém tahu a malé velikosti desky také rychlejší. V programu jsou použity obě metody v závislosti na typu deskové hry.

4.4 Prohledávání Cílem prohledávání je určit nejlepší tah, případně celou hlavní variantu. Hlavní varianta je ta, kdy na náš nejlepší tah odpovídá soupeř opět nejlepším tahem a to pokračuje až do námi zvolené hloubky. Také je důležité i ocenění nejlepšího tahu využívané třeba pro nabízení remíz a v odpovědi na nabídnutou remízu. Základní kámen tvořící algoritmus prohledávání do hloubky je označován jako algoritmus hrubé síly. Název plyne z toho, že je prohledán celý herní strom do určité hloubky.

17

Další algoritmy se snaží strom vzniklý prohledáváním ztenčit, aby jeho prohledání proběhlo rychleji a zároveň v některých místech prodloužit, aby program viděl dál a ocenění bylo více odpovídající realitě (tzv. dohledání do klidné pozice). Tyto metody se dají rozdělit na dvě kategorie. Metody ořezávání (pruning) mají vliv na tloušťku stromu, zatímco metody prodlužování (extensions) na jeho délku ve vybraných větvích. Rozšíříme-li hru o další hráče, situace se značně zkomplikuje a do značné míry záleží, zda bude hrát každý stále ve svůj prospěch nebo se začne spolčovat s ostatními. Dobře řešitelná je v tomto případě hra hráčů v týmu. Obecně lze podobný algoritmus jako pro dva hráče použít i pro více hráčů, jak uvádí [ZeroSum].

4.4.1 Minimax, negamax Jde o celkem jasné metody hledání nejlepší varianty ve stromu. Kdy se prohledává celý strom a v každé úrovni vybírá nejlepší tah pro danou stranu. Implementace je většinou rekurzí, ale pro paralelní zpracování je však vhodnější použít zásobník. Rozdíl mezi minimaxem a negamaxem spočívá v tom, že při metodě minimax se v liché hloubce minimalizuje a v sudé maximalizuje, zatímco u negamaxu stačí maximalizovat. Zdrojový kód je jednodušší, jen je třeba předávané parametry ocenění negovat. Časová složitost je ze, kde exponent „e“ je hloubka vnoření v půl-tazích a „z“ je faktor větvení (průměrný počet možných tahů z pozice). Vzrůstá s velikostí desky (uplatnění klouzavých kamenů), a velice ve variantě je-li možno znovu použít soupeřovy odebrané kameny (to pak dosahuje až k tisícům tahů).

4.4.2 Alfa-beta Jedná se o modifikaci předchozího algoritmu, bez kterého by hledání do hloubky pro většinu her bylo téměř nemožné. Jeho aplikace způsobí, že není třeba prohledávat kompletní strom, aniž by se změnilo nalezené řešení. Algoritmus je založen na intuitivní myšlence, že zahraji-li protivník dostatečně dobrý tah, který způsobí, že tah nebude vybrán do hlavní varianty, může se varianta oříznout. To zda bude náš tah vybrán záleží na intervalu (alfa; beta), odkud plyne název této techniky. Jak moc nám tento algoritmus ušetří záleží na pořadí prohledávaných tahů, v nejhorším případě nám nic neušetří, ale v nejlepším případě docílíme stejné hloubky pouze s odmocninou původních prozkoumaných uzlů.

4.4.3 Okno očekávání (Aspiration Window) Tato technika lze použít tam, kde nedochází ke skokové změně ocenění pozice v průběhu prohlubování. Očekáváme-li výsledek varianty nějakou hodnotu nastavíme okno okolo této hodnoty. Hodnoty mimo toto okno ořízneme. Prohledávání je rychlejší, ale jediná nevýhoda je, že vrátí-li se hodnota mimo toto okno, je třeba hledání zopakovat se zvětšeným oknem.

4.4.4 Futility pruning Pro použití této metody se předpokládá, že jakékoliv provedení tahu nemůže zhoršit naši pozici. Tak například máme prohledán nějaký tah z výchozí pozice dva půl-tahy

18

dopředu (čili známe nejlepší odpověď soupeře na tento tah). Začneme-li se zabývat jiným tahem a ocenění je horší než nejlepší známé, tak už nemá cenu se zabývat odpovědí soupeře, protože ta by ocenění jen zhoršila a tah by se stejně nestal hlavní variantou. Z příkladu je jasné, že se technika uplatní půl-tah před horizontem.

4.4.5 Nulový tah (Null-move) Hodí se pouze pro pozice, ve kterých můžeme zajistit neexistenci zhoršujícího tahu jako pro hry exploze, jungle (je-li ve hře dostatečný počet kamenů), šachy (krom koncovek) a nehodí se moc pro dámu (zde nastávají uzavřené pozice, kde hráč na tahu odevzdá kámen). V případě použití je potřeba zajistit několik podmínek jako, je-li strana na tahu v šachu v důsledku toho, že obraný tento tah bude jen ztěží zlepšující. Důsledek této techniky je vliv na trvání hloubky u prohledávacích algoritmů, a to takový, že sudá hloubka proběhne rychleji než lichá. Pravidla rovněž ovlivňují prohledávací algoritmus, je-li jistá pravděpodobnost, že můžu udělat znevýhodňující tah, nelze použít techniku nulového tahu (např. v gravitačních piškvorkách vůbec).

4.4.6 Negascout a MTD Jedná se vlastně o vylepšený alfa-beta algoritmus, kdy se hledá v rámci ocenění okna, což proběhne rychleji. Nevýhodou je, že je-li hodnota mimo toto okno, musí se výpočet opakovat. To však s použitím rozptylovacích tabulek není taková ztráta. Srovnání metod je k nalezení na [Search].

4.4.7 Třídění pořadí tahů Předpokládejme, že vygenerujeme v dané pozici všechny legální tahy. Začneme-li tím nejlepším, technika alfa-beta je nejúspěšnější, což způsobí největší ořezání. Stačí pak průměrně prozkoumat pouze odmocninu stavů oproti nejhoršímu případu bez techniky alfa-beta. Zvýšení efektivnosti třídění tahů zajistíme několika následujícími heuristickými metodami: • • • • • •

podle druhu tahu, např. získávací tahy jako braní a proměny. Potíž nastává u her jako např. othello, piškvorky, kde takto rozhodnout o kvalitě tahu nelze. materiální – v šachách braní nekrytých kamenů, v jiných hrách jako tohoto dosáhnout nemůžeme nebo poziční změna, kterou tah způsobil – oddělení dobrých a špatných tahů tahem, který je v uložen v rozptylovací tabulce jako nejlepší v dané pozici zabijácký tah (killer move) – použít tah, který v dané hloubce způsobil ořezání v minulém případě. Využívá faktu, že ve většině případů při změně předchůdce tahu v herním stromě zůstává aktuální tah stále nejlepší. tabulka historie (history prunning) – rozšiřuje zabijácký tah na hodnocení všech tahů

19

Třídění tahů můžeme provést u všech najednou nebo postupně. Výhoda první volby je možnost využít, např. třídící algoritmus quick sort: Druhá volba může být v závislosti rychlosti oříznutí rychlejší nebo pomalejší. Nyní si ještě ukážeme, jak fungují poslední dvě heuristické metody.

4.4.7.1 Zabijácký tah (Killer move) Pamatuje si tah, který byl v dané hloubce úspěšný při minulém ořezání a tím zvyšuje jeho preference nyní. Někdy se používají i dva tyto tahy, uspěje-li jiný tah nahradí jeden ze stávajících dvou.

4.4.7.2 Tabulka historie (History prunning) Zobecnění zabijáckého tahu, ale na rozdíl od něj je paměťově náročnější. Základ pro použití této techniky je aplikování rozptylovací funkce na tah. Důsledek je převedení tahu na 16-bitový klíč. Toto lze většinou dobře uskutečnit i v šachách a dámě, kde polovinu klíče tvoří zdrojové a druhou polovinu cílové pole. Dojde-li v důsledku nějakého tahu k oříznutí, zvýší se jeho preference v této tabulce.

4.4.8 Hledání klidu Abychom mohli použít ocenění pozice musíme jí dohledat do klidné, protože oceňovat pozici např. v polovině výměny nemá smysl. Nalezení klidné pozice vyžaduje znalost hry, např. v šachách uvažujeme braní a proměny jako úderné tahy, lze-li je zahrát za horizontem, prodlužujeme je. U jiných her např. v piškvorkách je neklidná pozice hrozba vytvoření řady, kde po prodloužení zamezíme hrozbě a pozice se stává klidnou, tudíž lze její ocenění použít. Naopak ve hře othello, kde se materiální balance mění každým tahem klidné pozice vlastně neexistují.

4.4.9 Efekt horizontu Nepříjemná vlastnost spočívající v oběti menšího ocenění pozice k oddálení daleko větší ztráty v ocenění pozice. Pro jeho zamezení se používá zejména technik jako hledání klidu a prodlužování při výměnách.

4.4.10Interaktivní prohlubování V podstatě se jedná o kombinaci prohledávání stavového prostoru do hloubky a do šířky. Interaktivní prohlubování (Interactive deeping), tedy postupné zvyšování prohledávané hloubky. Vzhledem k exponenciálním vývoji počtu uzlů je navýšení rovno 2 / e. Což např. e rovno 8 je zanedbatelné. Uvážíme-li, že můžeme využít předešlých znalostí jako např. částečně naplněných rozptylovacích tabulek a zejména znalost hlavní varianty a tudíž daleko efektivnějšímu alfa-beta ořezaní. Další výhodou je, že při omezeném čase lze prohledávání ukončit, aniž bychom vynechaly kterýkoliv tah z výchozí pozice.

20

Prodloužení je tedy jen o několik procent bez použití alfa-beta techniky, zato s jejím použitím je zrychlení několikanásobné v důsledku znalosti hlavní varianty, vyplnění zabijáckých tahů a rozptylovací tabulky.

4.4.10.1Přesun tahů Změnil-li se nejlepší tah, přesune se na první pozici, aby byl při další interakci prozkoumán jako první. Tento přesun můžeme provádět buď po dokončení dané hloubky nebo při nejlepší variantě. Třetí možností je setřídění podle ohodnocení tahů. Po průchodu všech tahů výchozí pozice v dané hloubce se změní jejích ocenění, proto se nabízí tato logická metoda. Bohužel vzhledem k alfa-beta okně je neopodstatněná, protože vzhledem k zamítání variant vrátí všechny tahy téměř shodné ocenění.

4.5 Oceňování Je-li prohledávací algoritmus dostatečně rychlý a stavový prostor dostatečně malý, aby propočet dosáhl konečné pozice ve smyslu vítězství, prohry případně remízy, není třeba vytvářet oceňovací funkci. Toto je ideální případ, kdy program propočtem do dostatečné hloubky, který objeví taktické možnosti v důsledku špatně či dobře zvolené strategie zvolí ideální tah a tak hraje prakticky bezchybně. To se ale vyskytuje pouze u her s malým počtem tahů partie a s malým faktorem větvení. Ve většině případů se však bez oceňovací funkce neobejdeme. Pak se jedná o nejnáročnější a nejobsáhlejší část, která je na rozdíl od algoritmů prohledávání velice závislá na druhu hry. Oceňovací funkce může být implementovaná zvlášť nebo jako součást generátoru tahů, jelikož souvisí s materiální hodnotou kamene a jejich pohyblivosti na desce. Ocenění pozice nemusí být zcela přesné, obzvlášť v případě, že je mimo rozsah alfabeta prohledávání. Pro hrubé určení je pak dostačující použít pouze materiální hodnocení a určit, zda je ocenění pozice, lepší nebo horší než meze alfa beta. Oceňovací funkce se dá v mnoha směrech kalibrovat. Kalibrováním se rozumí nalezení lineární kombinace kritérií oceňovací funkce, kde klademe různou váhu na poziční kritéria. Toto hledání připomíná nalezení minima více-dimenzionální funkce bez znalosti jejího matematického popisu. Toto je časově velmi náročné zejména proto, abychom zjistili zda se změna projeví pozitivně, je třeba sehrát několik partií se starší verzí nebo jiným, programem nebo ji použít na připravené pozice a podle výsledků zhodnotit přínos. Zde se navíc může stát, že se program zlepší v řešení jednoho problému a v jiném zhorší, nebo že se proti nějakému programu zlepší a proti jinému zhorší. Ze zkušenosti lze říci, že se zde vyplatí postupovat následujícím způsobem: Je-li více strategických problémů, je lepší začít tím nejzávažnějším, jelikož jeho vyřešení může odstranit jiný problém, ale zároveň i přidat nějaký nový. Dalším problémem zůstává, že i menší změna pravidel může způsobit velké odlišnosti v strategii. Jako příklad uvedu pravidlo o možnosti zpětného skoku neproměněných kamenů v dámě. Uplatníme-li toto pravidlo, zvýší se tím razantně cena kamenů uprostřed desky a tím i použitá strategie pro nutnost obsazení centra. Žádná strategie totiž není univerzální.

21

Prohledávání ve spojení s pozičním oceňováním dokáže vytvořit strategická pravila, kterými se program při svém hraní řídí.

4.5.1 Herní typy Podle vlastností tahu rozdělme nyní deskové hry na několik typů. Prvním typem nazveme hry, u nichž jsou na začátku rozestavěné kameny, které se přesouvají a zajímají. Jako příklad poslouží šachy či dáma. Druhý typ je charakterizován prázdnou deskou, na kterou jsou kameny přidávány, příklad je třeba GO či piškvorky.

4.5.2 Materiální kritérium Jako základ oceňování u her prvního typu slouží materiál, který je dán počtem a typem kamenů na desce či v záloze. Ve hrách jako piškvorky nemá v podstatě žádný vliv, protože se poměr v průběhu mění pouze o jeden kámen (hráči mají na desce stejně kamenů, případně začínající hráč má o jeden více). Zde je daleko důležitější působnost kamene. Zrovna tak ve hře othello, kde mít více kamenů neznamená výhodu, ale může to být zrovna tak nevýhoda. Materiální hodnocení je základ a zabrání ztrátám kamenům a hrubým chybám, pro smysluplnější hru je však zapotřebí použít i další poziční kritéria.

4.5.3 Poziční kritérium 4.5.3.1 Pohyblivost Ocenění je závislé na pozici a okolí kamene. Je dáno hlavě podle pozic a obsazení polí, kam se může kámen přesunout. Pohyblivost je zásadní ve hře othello, kde ke konci hry strana s větším počtem tahů mající zatím menší počet kamenů vyhrává.

4.5.3.2 Vývin Vyvíjení kamenů je zásadně důležité v šachách. V dámě toto neplatí zejména o kamenech na první řadě, které brání soupeří obsadit toto pole svým kamenem a proměnit jej v dámu. Ovládání desky tvoří majoritu hodnocení ve hře GO.

4.5.3.3 Bezpečnost Jedná se vlastně pouze o hry s králem, kde lze obětí materiálu ohrozit bezpečnost soupeřova krále, což vede až k matu. Jedná se o implementačně nejnáročnější kritérium založené hodně na citu. Mají s tím problémy i špičkové programy. Po delší dobu to byl problém programu [Fruit]. Při použití sebraných kamenů se nevyplatí na rozdíl od klasického šachu dělat rošádu, protože král v rohu desky je ve větším nebezpečí. To je jen ukázka toho, jak změna pravidel může razantně změnit strategii chování kamene.

4.5.4 Spekulativní ocenění pozice Oceňovací funkce vrací jako výsledek celé číslo, které je dobře použitelné pro porovnávání různých pozic mezi sebou. Ocenění pozice může však být i jiné, např.

22

takovéto ocenění vrátí hodnotu +5,02, ale v pozici hrozí věčný šach. V tom případě je lepší pozice s hodnocením +3,77 bez této hrozby, uvažujeme-li remízu oceněnou hodnotou 0. Zde lze použít např. dvě ocenění a ke každému jejich pravděpodobnost. Další možností je použít pravděpodobnou hodnotu ocenění a její rozptyl. Nebo v obecnějším případě interval, a ještě v obecnějším případě se dá využít fuzzy logika. Příklad takového intervalového ocenění může být následující: • útok na krále s obětí figury <-3..+mat> • koncovka s nestejnými střelci <-0,10; +0,10> • opakování tahů případně věčný šach <0; 0> Tyto hodnoty odráží i risk, což v jednoduchém číselném hodnocení nelze vystihnout.

4.5.5 Příklad vytvoření oceňovacích funkcí Piškvorky Strategie v gravitačních piškvorcích je založena na faktu, zda má v daném sloupci hráč výherní pole níže než jeho soupeř. Propočtem těchto vlastností stanový oceňující funkce velmi přesně fakt kdo zvítězí, aniž by bylo nutné dopočítat mnoho tahů vpřed. Podrobně je strategie popsána např. v [SC4]. Othello Pohyblivost je zde daleko důležitější než v šachách, to znamená, že v koncovce je důležitější než aktuální stav kamenů. Jako materiální základ platí, že čím více vlastních kamenů tím lépe. Pro jemnější strategie se dá využít následující tabulka jak uvádí podrobnější strategie hry othello ve zdroji [othello] udávající výhodnost obsazení pole kamenem. +--+--+--+--+--+--+--+--+ | |50| |75|75| |50| | +--+--+--+--+--+--+--+--+ |50|25|75|75|75|75|25|50| +--+--+--+--+--+--+--+--+ | |75| | | | |75| | +--+--+--+--+--+--+--+--+ |75|75| | | | |75|75| +--+--+--+--+--+--+--+--+ ......................... +--+--+--+--+--+--+--+--+

Obr. 8:

Procentuelní výhodnost obsazení pole (bez označení značí 100%)

Podrobně je strategie popsána např. zde [SOthllo]. Vzhledem k malému stavovému prostoru v koncové části hry se zde výrazně uplatní rozptylovací tabulky.

4.6 Rozptylovací tabulky (hash tables) V řadě případů potřebujeme ukládat pozice do paměti a dotazovat se, zda je určitá pozice v paměti, případně na další informace o ní. Ukládat přímo pozice by zabralo

23

mnoho paměti, a navíc vyhledávat v takovémto seznamu by bylo příliš časově náročné. Proto sáhneme k technice rozptylovacích tabulek. Jako základ pro použití je třeba použít rozptylovací funkci pro převedení pozice na 64-bitový klíč. Toho lze při vyhledávání dosáhnout velmi rychle tím, že pomocí předem vygenerované tabulky náhodných čísel, při každém tahu provádíme nonekvivalenci klíče podle pole a kamene. Část klíče využijeme pro indexování do rozptylovací tabulky v závislosti na její velikosti (modulární rozptylovací funkce). Druhou 32-bitovou část využijeme pro porovnání, zda zde nalezená pozice je námi hledaná. V rozptylovacích tabulkách použitých pro vyhledávání nám na rozdíl od běžných aplikací nevadí kolize. Klademe důraz zejména na rychlost, tudíž nám ztráta či přepis stávající položky nevadí. Proto zde nepoužíváme zřetězené či otevřené rozptylováni. Výhody použití rozptylovacích tabulek jsou hlavně v tom, že vkládání a vyhledávání záznamů má konstantní časovou náročnost, což umožňuje je použít ve vyhledávacím algoritmu, kde ani lineární časová složitost nepřichází v úvahu. V těchto klasických šachových rozptylovacích tabulkách použitých pro dočasné uložení pozic dochází k přepisování položek se stejným indexem. Kolizím se však přesto chceme vyhnout při uplatnění pravidla ukončení partie při opakování tahů, nebo při hledání v knihovně zahájení. Proto zde použijeme tabulku s otevřeným rozptylováním a lineárním prohledáváním.

4.6.1 Otevřené rozptylování Rozptylovací tabulky s otevřeným rozptylováním, nazvané též s implicitně zřetězenými synonymy, zabrání kolizím. Při kolizi použijeme lineární prohledávání, čili se díváme na následující adresy, které jsou s velkou pravděpodobností k dispozici v cache paměti a tudíž přístup k nim je rychlejší. Tabulka nemůže být zaplněna zcela, to by způsobilo zacyklení při hledání volné pozice. Měření ukázalo, že je vhodné nepřeplňovat tabulku, a obsazovat ji zhruba do 25%, kdy se její rychlost pohybuje okolo dvojnásobku ideální hodnoty. Existuje i přesný výpočet, ten však zanedbává rychlejší přístup k následující paměťové položce, nelineární rozložení indexů.

4.6.2 Změna velikosti rozptylovací tabulky za chodu Máme-li k dispozici rozptylovací tabulky s časovým razítkem, které zajistí průběžné mazání starých pozic, nemusíme rozptylovací tabulku po každém tahu mazat. Pak přijde vhod možnost změny rozptylovací tabulky, aniž by data v ní uložené ztratili na konzistenci. Příklad: Uvažujme tabulku velikosti 16 záznamů naplněnou 16 položkami, tedy validní index v rozsahu 0..15 Jako první probereme případ zmenšení na čtyři záznamy. Podle provedeného zmenšení můžeme položky s indexem větší než tři přepočítat na nižší indexy. Takto přepočítané indexy je možno buď přidat, nebo jimi nahradit stávající položky.

24

0 4 8 1 5 9 2 6 10 3 7 11 Tab. 1:Uložení po zmenšení rozptylovací tabulky

12 13 14 15

Nyní tuto tabulku zvětšíme na 8 záznamů. 0 8 1 9 2 10 3 11 4 12 5 13 6 14 7 15 Tab. 2:Uložení po zvětšení rozptylovací tabulky Toto vede na předchozí rozložení indexů. Jak je vidět, tak např. index 4 nebo 12 v prvním řádku původní tabulky by se v tabulce umístil na jiných pozicích. Vzhledem k tomu, že nedokážeme určit o jaký se jednalo přesně index je nutné tabulku vymazat. Z tohoto plyne závěr, že zmenšíme-li za chodu rozptylovací tabulku, není třeba ji mazat. Naopak při zvětšeni to třeba je, protože zpětně nedokážeme spočítat větší indexy.

4.7 Záznam hlavní varianty 4.7.1 Průběžné kopírování Při prohledávání nestačí určit nejlepší tah, případně tahy, ale určit k nim i nejlepší pokračování, čili hlavní variantu. Pro přenos těchto tahů od listů až ke kořeni herního stromu slouží struktura reprezentovaná dvourozměrným polem, kde číslo řádku odpovídá aktuální hloubce v prohledávání. Každý řádek je vyplňován jemu shodnou aktuální hloubkou. První číslice v řádku značí aktuální tah v dané hloubce, zbytek se v případě úspěšné varianty kopíruje z vyšší hloubky (z následujícího řádku). Ve finále se v horním řádku objeví hlavní varianta. Písmeno x značí nepoužitý prostor. 1: 2: 3: 4: …

12345678 x2345678 xx345678 xxx45678

Obr. 9:

Ukázka struktury uložení hlavní varianty do pole

Paměťové nároky jsou d2 / 2, kde d znamená maximální hloubku vnoření. V praxi však kvůli optimalizaci výpočetního času d2, díky vzrůstajícímu nevyužitému místu

25

(označeno x) se stoupající hloubkou. Časová náročnost je přímo úměrná vzdálenosti od aktuální maximální hloubky a vzhledem k většímu výskytu ve vyšší hloubce (tudíž kopírování menší části řádku) je velmi nízká.

4.7.2 Využití rozptylovacích tabulek Tuto metodu lze využít pouze při zapnutých rozptylovacích tabulkách a také je třeba zaručit správné přepisování záznamů, proto je méně často používána. Funguje následujícím způsobem. V kořeni se uloží pouze první tah hlavní varianty (kvůli možnosti zobrazení více nejlepších variant), ostatní se hledají v rozptylovacích tabulkách. Oproti průběžnému kopírování je rychlejší, ale je nutné mít k dispozici dostatečně velké rozptylovací tabulky, jinak může dojít k přepsání záznamu a k zkrácení hlavní varianty. Dále je třeba zajistit nepřepisování v rozptylovacích tabulkách, což se projeví oříznutou hlavní variantou a dále zacyklení, což se projeví nekonečně dlouhou variantou (často vzniká opakováním tahů). Řešení je testovat opakování pozice při výpisu hlavní varianty.

4.8 Knihovna zahájení Většina deskových her začíná vždy ze stejné pozice, proto se vyplatí mít připraven pro tuto pozici seznam hratelných tahů. Různé posloupnosti zahájení dostaly svá jména po zemích jejich zrození nebo po hráčích, kteří zahájení hrají. Pro implementaci se používá bez-kolizní rozptylovací tabulka, protože nároky na rychlost nejsou potřeba (dotaz probíhá před započetím analýzy každého tahu) může se použít i binární vyhledávání. V zahájení se počítá také se symetrií. Symetrická pozice vznikne většinou ztrátou tempa začínajícího hráče. Např. v šachách po tazích 1. e3 e5 2. e4 Jf6 Jc3 Sb5, kde se vlastně hraje zahájení španělská hra s převrácenými barvami. Ve hře othello a piškvorkách, lze využít horizontální i vertikální symetrii. Jedna pozice tak může představovat tři další otočené. Pro zautomatizování vytvoření knihovny zahájení je nejlépe použít co nejvíce partií silných hráčů dané hry, které skončily remízou (kvůli vyloučení hrubých chyb).

4.9 Koncovky V koncovkách sice ubývají kameny, což snižuje koeficient základu exponenciální funkce, avšak pro správnou volbu tahu je zapotřebí větších hloubek prohledáváni. Dále se v koncovce snižuje mohutnost stavového prostoru, což umožňuje lépe využít rozptylovacích tabulek. Koncovky sebou přináší nutnost mnoha více či méně zobecnitelných pravidel a znalostí, jako např. v šachové koncovce nestejnopolní střelci, pravidlo čtverce [Čtv], které určí zda pěšec dosáhne včas proměny nebo bude chycen soupeřovým králem. Toto pravidlo umožňuje v určitých situacích výrazně urychlit nalezení správného tahu. Dále je třeba znát, které konstelace kamenů už jsou remízové a nemá cenu je tahat, protože by skončily remízou v důsledku pravidla o počtu tahů bez braní a proměnny.

26

Např. koncovka JJ+K proti K je materiálově lepší než druhá V+K proti K, ale vyhraná je pouze druhá koncovka, první je až na speciální případ remízová. Speciální případ nastane, je-li král uvězněn v rohu desky. Tento speciální příklad ukazuje chybu programu Fritz, který hraje chybný tah králem do rohu s remízovým oceněním, ale partie bohužel skončí matem. Pro implementaci remízové konstelace kamenů je vhodné použít opět rozptylovací tabulku, kdy po jednoduchém nahlédnutí zjistíme zda daný materiál je či není remíza. Hlavní zpomalení je způsobené počítáním klíče.

4.10Hospodaření s časem V závislosti na časové kontrole máme k dispozici určitý čas na tah, na několik tahů, případně celou partii. V prvním případě není příliš důležité jak dlouho partie bude trvat, čas můžeme využít buď všechen nebo jen část, což záleží na stavu algoritmu interaktivního prohlubování. Např. máme-li na tah 10 sekund a po 7 sekundách jsme ukončili propočet do hloubky 5, nemá již smysl pokračovat, protože hloubku 6 bychom pravděpodobně nestihli. Máme-li přidělen čas na určitý počet tahů, použijeme na tah přibližně zlomek odpovídající počtu tahů. Komplikace nastává v posledním případě, a to proto, že máme vymezený čas na celou partii, ale nevíme jak dlouhá bude (to platí především v šachách a dámě). Pak nezbývá než odhadnout počet tahů do konce partie a s tím počítat. V případě delší partie dochází ke konci k zrychlování rychlosti. Zde máme na výběr různé strategie hospodaření s časem, které mohou podstatně ovlivnit výsledek partie. Vzhledem k použití interaktivního prohlubování můžeme ukončit algoritmus po jakémkoliv čase, ale pouze při přechodu do vyšší hloubky s tím, že jsme dosavadní čas rozumně využili. Proto je vhodné stanovit předpokládaný čas následující hloubky z poměru trvání dvou předchozích. Je-li tento čas s dosud uplynutým delší než požadovaný, tak výpočet ukončit.

4.11Využití času soupeře (Ponder) Poté, co program zahraje tah je na tahu soupeř. Tuto dobu může program využít. Nejčastěji se používá metoda, kdy z předchozí analýzy uvažujeme předpokládaný tah soupeře na který připravujeme odpověď. Zahraje-li soupeř náš předpokládaný tah pokračujeme v analýze, jinak začneme znovu. Tato technika se uplatní zejména tam, kde není mnoho správných odpovědí soupeře, tudíž je velká pravděpodobnost, že předpokládaný tah soupeře je správný. Další možností je po provedení tahu myslet za soupeře s uvažováním hlavních variant všech, či jen několika jeho tahů. Výhoda při uvažování všech hlavních variant je ta, že nás soupeř nemůže překvapit, čili ať soupeř zahraje jakýkoliv tah, máme připravenu odpověď. Tato technika je výhodná, máme-li málo času, či nemáme-li dokonce žádný čas na náš tah. Dosahuje však v důsledku zkoumání všech hlavních variant soupeře nižší hloubky prohledávání, což má za příčinu nižší časovou úsporu než varianta první.

27

4.12Sociální pravidla 4.12.1Faktor remízy (Contempt Value) Uplatní se u her, které mohou dopadnout nerozhodně. Určuje jakou hodnotu má remíza, čili jak si ji ceníme. Tento údaj se hodí např. jsme-li na turnaji v posledním kole a k 1. místu nám stačí remíza. Nezáleží pak jestli vyhrajeme nebo remizujeme, hlavně, že neprohrajeme. Faktor remízy proto nastavíme na vysokou hodnotu. Důsledek je takový, že např. dáme přednost věčnému šachu před ziskem věže. Může nastat i opačná událost, kdy musíme vyhrát. Pak nastavíme faktor remízy na zápornou hodnotu. Důsledkem je, že dáme přednost raději hraní špatné pozice, než abychom opakovali tahy nebo přijali remízu.

4.12.2Faktor vzdání (Resign Value) Je-li na tom program už velmi špatně bez šancí na zvrat. Je znakem sportovního chování se vzdát. Tato hodnota vlastně určuje jak odhadujeme sílu soupeře. Při velmi nízké hodnotě se nevzdáme nikdy, naopak kladné hodnotě se vzdáme i při vyrovnané pozici. Nastavení tohoto parametru není v UCI minimálně do verze 2, implementuje jej GUI.

4.13Zhodnocení K vyhledávání je nejlépe použít negamax alfa-beta prohledávání s výpisem hlavních variant. Většinu parametrů předešlých technik lze v programu nastavit pomocí dialogu. Snaha je dosáhnout co nejrychleji největší hloubky, např. u šachů je empiricky zjištěno, že dvojnásobné zrychlení algoritmu má za následek zvýšení herní síly o 70 Elo bodů. Prohledávací algoritmus lze bez větších obtíží napsat obecně, dokonce na vyšší úrovní než pro deskové hry. Generátor tahů a oceňování pozice není univerzální a záleží na pravidlech dané hry.

28

5 Aplikace 5.1 Vývojové prostředky K tvorbě aplikace jsme využili tyto programy: • Windows 98, XP • Delphi 6, 7 – sestavení spustitelného souboru • Cool Edit Pro 2.0 – úprava formátu zvuků • Paint Shop Pro 7 – vytvoření a rozdělení obrázků • Caser – vlastní program pro normalizace zdrojových kódů • Office 97, 2000, Open Office 2.0 – pro napsání tohoto dokumentu

5.2 Volba vývojového prostředí Pro vývoj většiny programů tohoto typu se používá C++ díky rychle běžícímu strojovému kódu. U náročnějších her je prakticky vyloučeno použití interpretačního jazyka (pominout kompilaci), protože zpomalení se v tomto případě pohybuje v řádu desítek. Toto zpomalení vzhledem ke vzrůstající rychlosti procesorů posouvá vývoj o několik let zpět. Z těchto důvodů se na tento typ programu nehodí Java, a to zároveň pro některá omezení jako nemožnost vytvořit Win32 proces, který se používá v UCI. My jsme zvolili programovací jazyk Delphi vzhledem k tomu, že počátky vývoje programu sahají do roku 1997 kdy vznikl v Borland Pascalu program D-Check hrající anglickou dámu, jehož části kódu jsme využili. Mezi výhody patří rychlý kompilátor , který zvládne na 1 GHz procesoru zkompilovat přibližně 1 MB (100 000 řádek) zdrojových kódů za sekundu. Pro platformu Unix je k dispozici pod názvem Kylix (od Delphi verze 6 existuje klíčové slovo platform značící platformovou závislost kódu).

5.3 Postup pro sestavení aplikace Program je zpracován v prostředí 7 (Build 8.1). Kompilace proběhla pod kompilátorem verze 15. Release projektu probíhá automaticky v následujících čtyřech krocích: Nejdříve jsou kompilovány zdroje (resource): brcc32.exe SDG.rc

Dále je program kompilován z příkazové řádky s následujícím nastavením: dcc32.exe -B -H -W SDG.dpr /$A+ /$B- /$C- /$D- /$E- /$F- /$G+ /$H+ /$I- /$J- /$K- /$L- /$M- /$N+ /$O+ /$P+ /$Q- /$R- /$s- /$T+ /$U- /$V+ /$W- /$X+ /$Y- /$Z1 /cg /$M16384,65536 /K00400000 -ULib -UExtLib

A nakonec je spustitelný soubor komprimován programem UPX což zmenší jeho velikost přibližně na polovinu: UPX.exe -c -i -m -s SDG.exe

Celý projekt je dále zabalen programem WinZip: WZZIP.EXE -a -ex -r -p [email protected] [email protected] [email protected] SDG.zip SDG\*.*

29

5.4 PGN rozšíření Všechny hry se ukládají ve formátu PGN, FEN a EPD definovaným podle specifikace [PGN], který vznikl původně pouze pro šachy, ale je velmi dobře zobecnitelný (modifikace PDN se používá pro dámu). Mezi jeho nevýhody patří zejména pracnější implementace s použitím parseru. Následuje popis syntaxe jazyka: ::= <empty> ::= <movetext-section> ::= <empty> ::= [ ] ::= ::= <string> <movetext-section> ::= <element-sequence> <element-sequence> ::= <element> <element-sequence> <element-sequence> <empty> <element> ::= <move-number-indication> <SAN-move> ::= ( <element-sequence> ) ::= 1-0 0-1 1/2-1/2 * <empty> ::=

Do specifikace jsme přidali následující značky (tagy): GameType Pro určení typu a varianty hry (není-li uvedeno jedná se o šachy, případně o dámu v závislosti na koncovce názvu souboru). Hodnota může být buď textová nebo číselná podle specifikace PDN. Variant Pro určení varianty hry textově nebo číselně podle PDN specifikace. WhiteTimeControl, BlackTimeControl Obsahuje stejnou hodnotu jako TimeControl, je použito v případě odlišných časových kontrol obou hráčů. Rozšíření PGN specifikace hrací desky Velikost řádku či počet sloupců nemusí být 8, řádky by měli být stejně dlouhé, není-li tak, bude délka všech řádků rovna nejdelšímu z nich. Minimální velikost je 1×1 polí. Maximální velikost je omezena velikostí 256 adresovatelných polí včetně okrajů. Omezující podmínka pro různé hry v závislosti na nejpohyblivější figuře je následující (X značí počet sloupců, Y počet řádek). Šachy: (X + 2) × (Y + 4) < 256

30

Shogi:

(X + 1) × (Y + 4) + 1 < 256

Dáma: ((((X + 1) and $fffe) + 1) × (Y + 2)) div 2 + ((X + 1) and 1) < 256

Ostatní:

(X + 1) × (Y + 2) + 1 < 256

Toto rozšíření zachovává zpětnou kompatibilitu, tudíž jsou PGN soubory čitelné i v ostatních programech.

5.5 Zdrojový kód 5.5.1 Funkčnost Ladění rekurzivního prohledávacího algoritmu je poměrně obtížné. Navíc s přibývajícím počtem technik, které se navzájem ovlivňují je velice obtížné a časově náročné vyladit jejich parametry. Základní kontroly probíhají na úrovni ladění pomocí příkazů assert nebo dialogem. Vzhledem k velikosti programu zde není možné popsat všechny funkce a možnosti programu.

5.5.2 Výjimky Vzhledem k tomu, že program je kompilován na rychlost, jediná výjimka která může nastat je typu neoprávněného přístupu do paměti (Access violation) nebo Integer overflow při dělení nulou, je vždy zachycena na úrovni události. To znamená, klikne-li se na položku v menu a v těle obslužné procedury dojde k výjimce je zachycena, ohlášena a program je možno používat dále. Obsloužení všech výjimek ručně v programu by učinilo program značně nepřehledný, a proto jsou použity jen ve výhradních situacích jako alokace většího množství paměti pro rozptylovací tabulky atd.

5.5.3 Optimalizace Vzhledem k je nutnosti prohledat velký stavový prostor je rychlost propočtu kritická. Z těchto důvodů je síla hry závislá i na rychlosti, proto se nyní podíváme na některé techniky optimalizace použité v programu. Většina algoritmů je optimalizována na minimalizaci výpočetního času, protože jejich paměťová náročnost je většinou zanedbatelná. To neplatí o rozptylovacích tabulkách, které mohou vyplnit veškerou dostupnou paměť a proto se vyplatí minimalizovat velikost jejích položek. Kvalita překladače je uspokojivá, ne však dokonalá. Zapnuti optimalizace překladu pascalu zrychlí algoritmus v zahájeni jen o 17%, což není o mnoho. Je to způsobeno tím, že překladač neprovádí nad zdrojovým kódem hlubší analýzu a je tak z velké části na nás, abychom tak učinili.

31

5.5.3.1 Ztráta rychlosti na úkor obecnosti Čím obecnější program bude (přidávání voleb), tím bude jeho kód větší a pomalejší. Snažíme se proto použít techniky, které nám umožní kód zobecnit, ale zároveň nemají velký dopad na jeho rychlost. Např. pro zjišťování údajů o pozici je pro desku malých rozměrů lépe využít globálních shromažďování údajů, zatímco pro desku velkých rozměrů lokálních (rozdílových) zjišťování údajů. Další otázka nastává jak vyřešit volání stejného kódu ve kterém je pouze část závislá na hodnotě vstupního parametru. Chceme-li např. oceňovací funkci zobecnit na více variant ocenění (jiné oceňování v různých fázích hry). Je rychlejší varianta bez použití podmínek, než tato varianta s podmínkami, jak ukazuje následující příklad. inc ScoreA, BonusA inc ScoreB, BonusB

Varianta bez podmínek if (varianta A) then inc ScoreA, BonusA else inc ScoreB, BonusB

Varianta s podmínkou Optimalizace někdy zachází tak daleko, že se velmi často vyskytuje duplicitní kód pro obě strany. Nevýhoda je, že je třeba dělat dodatečné úpravy dvakrát, proto je vhodná spíše ke krátkým částem v závěru implementace.

5.5.3.2 Velikost kódu Nepřesáhne-li kód algoritmu velikost cache procesoru nedochází k žádnému výraznějšímu zpomalení v důsledku komunikace s operační pamětí. Proto je snaha o co nejmenší kód namístě. Na vliv velikosti kódu překladu pascalu do asembleru má vliv i zdánlivě stejný zdrojový kód pro adresování rozptylovací tabulky. HashPos := @HashTable[CHashI and NowHashAnd]; HashPos := Pointer(UG(HashTable) + SizeOf(THashPos) NowHashAnd));

*

Následuje porovnání velikost přeloženého a zdrojového kódu v bajtech. Velikost záznamu 10 bajtů: 5 6 3 6 3 3 26

mov eax, [ChashI] and eax, [NowHashAnd] lea eax, [eax+eax*4] mov edx, [HashTable] lea eax, [edx+eax*2] mov [ebp-$28], eax celkem

5 6 2 3

mov and add lea

eax, eax, eax, eax,

[ChashI] [NowHashAnd] eax [eax+eax*2]

32

(CHashI

and

6 3 25

add eax, [HashTable] mov [ebp-$28], eax celkem

Při použití velikosti záznamu násobku dvou čili 16 bajtů: 5 6 2 6 3 3 25

mov eax, [ChashI] and eax, [NowHashAnd] add eax, eax mov edx, [HashTable] lea eax, [edx+eax*8] mov [ebp-$28], eax celkem

5 6 2 6 3 22

mov eax, [ChashI] and eax, [NowHashAnd] shl eax, $04 add eax, [HashTable] mov [ebp-$28], eax celkem, což je nejlepší dosažený výsledek

Zde platí obecné pravidlo, pokud možno používat velikost záznamů v násobcích dvou což urychlí adresování položek záznamů.

5.5.3.3 Podmínky Velmi jednoduchá optimalizace na úrovni vyššího jazyka if … then … méně častý případ else … více častý případ;

Přeložení předchozího případu do asembleru vypadá následovně: cmp … je @else … první blok instrukcí jmp @endif // insturkce prodlužující alternativu @else … druhý blok instrukcí @endif

při splnění podmínky

Díky instrukci jmp trvá první blok déle. Při použití více podmínek je lépe začít podmínkou, která se vyhodnotí nejrychleji, protože v určitém případě se podmínky následující už provádět nemusí. V případě použití podmínek spojených pomocí disjunkce je dobré seřadit je podle pravděpodobnosti splnění následovně. if (nejmenší pravděpodobnost splnění) and (…) then … else …;

V případě konjunkce je tomu naopak:

if (největší pravděpodobnost splnění) or (…) then … else …;

33

5.5.3.4 Assembler Optimalizace na úrovni assembleru uskutečněná přepsáním časově kritického kódu do asembleru se dá výrazně zrychlit. Nevýhoda je však jeho nižší čitelnost a závislost na použitém hardware, proto je vhodné takto optimalizovat jen krátkou a dostatečně jednoduchou část kódu. Využití je vidět např. ze zdrojových kódů tvůrců oficiálních knihoven pro Delphi jako „system.pas“ či „SysUtils.pas“. Už je doprovázena nepřenositelností na jinou platformu než x86. Přesto se však vyplatí časově kritické a krátké pasáže kódu napsat v asembleru. V programu asembler použit pro procházení desky, což s sebou přináší zrychlení od 65% v zahájení až do 225% v koncovce. Rychlejší procházení v koncovce na rozdíl od zahájení je způsobené menším počtem kamenů, kde se tolik neuplatní zjišťování tahů daného kamene.

5.5.3.5 Procedury Volání procedur zvyšuje přehlednost zdrojového kódu, jejich použití však nijak nepřispívá rychlosti. Jednak proto, že instrukce call a ret stojí vykonat nějaký čas a navíc je narušeno paralelní zpracování toku instrukcí. Dále je nutné provést předávání parametrů, v případě funkce i návratové hodnoty. Parametry předávané do metod se umísťují do registrů EAX EDX ECX, v tomto pořadí. Tyto registry se také mohou libovolně modifikovat, ostatní registry je třeba před jejich použitím uložit na zásobník (push) a na konci metody obnovit (pop). Při volání metod tříd je situace ještě horší. Mají totiž skrytý parametr self, kterým odkazují na konkrétní instanci dané třídy, pak tedy zbývají už jen dva parametry k umístění do registrů. S použitím pod-procedur je to podobné, proto není jejích volání vhodné v časové kritických sekcích, např. použití v generátoru tahů.

5.5.3.6 Zjišťování času Program potřebuje zjišťovat čas pro započítávání (zobrazení) uplynulého času, rychlosti propočtu, pravidelného přerušování propočtu (bez použití vláken) a především pro dodržování časových kontrol. Nabízí se několik možností. Rychlý GetTickCount vrací čas v milisekundách, jeho nevýhoda je však přesnost pouze 10 ms. Další velmi pomalou možností je využít krystalu s frekvencí řádově MHz na základní desce (API funkce GetPerformanceCounter). Poslední možnost je pomocí CPUID zjistit hodiny procesoru. Program využívá první možnost a v případě potřeby lze pomocí direktivy při překladu využít i možnost druhou pro zvýšení přesnosti při velmi rychlých počítačových hrách.

5.5.3.7 Přerušovací systém výpočtu Protože je během analýzy potřeba průběžně zobrazovat informace uzly za sekundu, vypsané analýzy, události, je třeba program po určitém čase přerušit. Pro přerušení vyhledávacího algoritmu máme dvě možnosti. Zaprvé využít více-vláknového systému a jedno vlákno vzbouzet pravidelně, např. po 100 ms a kontrolovat spotřebovaný čas se stavem výpočtu a v případě nutnosti výpočet ukončit. Jako druhá se nabízí varianta

34

kontrolovat čas a stav výpočtu po prozkoumání určitého počtu pozic (nepreemptivní multitasking). Zde je však důležité kolikrát, v případě malého počtu by tato kontrola zdržovala (zjištění času je časově náročné), v případě velkého počtu by byla rychlost odezvy příliš dlouhá. Pro určení počtu prozkoumaných pozic nutných k přerušení využijeme faktu, že víme jaký čas proběhl od minulého přerušení. Podle toho naplánujeme počet uzlů k prozkoumání než nastane další přerušení. Výhodou tohoto adaptivního řešení je, že probíhá téměř pravidelně i při změně rychlosti propočtu. V programu je tato metoda použita s ohledem na to, že výpočet lze ukončit i při přesné hodnotě propočtených pozic.

5.5.4 Přidání další hry Deskové hry jsou velmi provázané díky shodnému formátu tahů, shodnosti kamenů či částech pohybů a dalším věcem, které se používají. Reprezentovat hru objektově by bylo vhodné pro třídění podle jedné kategorie, v opačném případě se zde objekty příliš nehodí a je lepší napsat kód tvořící jádro, z kterého si každá hra vezme to, co potřebuje, případně přidá něco dalšího. Prohledávání je pro všechny společné, liší se pouze algoritmy na prořezávaní a prohlubování herního stromu. Hlavní část generátoru tahů je také společná podle několika druhů prováděných tahů. Pro generování tahů typu přesun kamene je pro každý kámen zvláštní procedura, která je na počátku přiřazena danému indexu kamene vyskytujícímu se na desce. Provádění tahů je rozděleno na tři části podle typu tahu (šachy, dáma, GO) a je přiřazeno také na počátku. Chceme-li přidat další druh deskové hry, musí splňovat následující požadavky. Herní deska tvořena čtvercovými poli. V jiném případě lze hru také přidat, ale její grafická reprezentace bude neodpovídající a nepřehledná. Pokud nesplňuje již použitý typ tahu je třeba dodělat další. Pro přidání nové hry je třeba provést následující akce: 1) zadat její název 2) určit formát tahů, který bude používat 3) určit druh kamene, které bude používat, případně dodefinovat další včetně grafické reprezentace 4) doplnit výchozí pozici a volby pro varianty 5) doplnit hodnoty pro ohodnocení materiálu, pohyblivosti kamenů (nejnáročnější část) 6) zadat další parametry jako počet opakováni pozice, který způsobí ukončení partie, výsledek partie při patu a další

5.5.5 Obecně Pro vývoj programu je použito prostředí Delphi, což sebou neslo nevýhody při implementaci. Mezi nejdůležitější patří to, že chyběly jazykové konstrukce jako inline funkce a template. Tento problém lze nahradit pomocí direktivy include. Dále makra, které byly nahrazeny funkcemi, avšak na úkor rychlosti provádění programu. Naopak mezi výhody patřil rychlý překladač a příjemné grafické rozhraní.

35

Vzhledem k velikosti programu je pravděpodobné, že bude obsahovat několik chyb. Jelikož i špičkový software obsahuje jednu chybu na 15 000 řádků. Zdrojový kód je v příloze. 70 000 řádků kódu tvoří knihovní funkce, 20 000 GUI a okolo 10 000 samotný motor. Ve zdrojovém kódu se v poznámce objevuje slovo calibrate. Označuje část kódu nebo dat, která nejsou jednoznačně určena, jsou vhodná pro ladění. Jejich změnou lze ovlivnit styl a výkonnost herního programu. Navíc jsou ve vzájemných návaznostech, což značně zkomplikuje jejich vhodné určení. Je to jako hledat minimum u vícedimenzionální funkce, čili se jedná o kombinační úlohu, kterou lze jen těžko vyřešit. Názvy v programu a komentář jsou v angličtině vzhledem k čitelnosti po celém světě, výstižnosti a kratší formě. Formální stránka zdrojového kódu je normalizována (mezery, tabulátory, klíčová slova) pomocí programu [Caser]. Ve zdrojovém kódu jsou na začátku řádek použity znaky tabulátoru, protože díky nim lze okamžitě nastavit velikost úrovně odsazení, cílové soubory jsou menší a šipkami se lze pohybovat po úrovních. Program podporuje otevření více souborů najednou. Pro rychlejší práci s otevřeným souborem (blokem dat v paměti) se používá přepínání kontextu. Jinak řečeno, při změně aktivní partie se překopíruje na pevně stanovené paměťové místo a po skončení práce se nakopíruje zpět. Hlavní datový typ TGame je neobjektového typu a to kvůli rychlejšímu adresovaní, jelikož má přidělenou statickou adresu. Proto známe adresy jeho prvků již při kompilaci, což urychlí práci s nimi. Objektový typ by vyžadoval adresaci 1. řádu.

5.6 Konfigurační soubory Jako nejméně vhodný pro ukládání dat se jeví binární formát. Je sice nejrychlejší, ale lze jen těžko modifikovat mimo program a neumožňuje změnu formátu ukládaných parametrů. Další možností je použití formátu INI případně XML. Následuje příklad souboru v INI formátu: [Statistics] RunCount=5,591 RunTime=1,335,135,869 ReadCount=370,613 ReadBytes=1,382,866,242 WriteCount=56,995 WriteBytes=253,199,677 [Reopen] ReopenCount=26 ReopenLimit=24

A soubor obsahující stejná data v XML formátu: <Statistics> …

36

…

INI soubor vlastně poskytuje data ve stromové struktuře do hloubky 1, nepotřebujeme-li další pod-sekce je jeho použití dostačující. Výhody použití XML formátu je jeho lepší čitelnost v ostatních programech a dostupnost mnoha XML nástrojů. Na úkor toho je méně přehledný a také zpracování je o něco pomalejší. Vzhledem k použití pouze jako uložení konfigurace s případnou textovou modifikací je použití INI formátu dostačující, proto je také použit pro veškeré uložení konfigurace.

5.7 Grafika Pro vykreslení se používá grafická knihovna optimalizovaná na 32-bitový x86 procesor. Kvůli rychlosti a nemožnosti použití průhledností se Win32API funkce jako BitBlt využívají až pro zobrazení. Jednodušší kameny je možno nakreslit v grafickém editoru, čímž se docílí přesné symetrie a barevné stálosti. Pro složitější je jednodušší skenovat grafickou předlohu kamenů na klíčovém pozadí. Poté je třeba ještě provést vyhlazení transparentní barvy a úpravu na velikost vhodnou pro zpracování programem. Desku není vhodné ukládat jako obrázek, ale vzhledem ke změně její velikosti je lépe jí generovat z polí. Nevýhoda je ta, že jsou všechna pole stejná, což lze částečně nahradit aplikováním náhodného vzoru. Výhody jsou možnost změny počtu polí, libovolné modifikace barvy, orámování a kvalitnější změna velikosti.

5.7.1 Metody zobrazeni kamenů 5.7.1.1 Vektorově Používá se např. formát pro písmo TTF (True type font), ten je jen černobílý a proto je třeba použít dodatečné vystínování. Výhody jsou, že je přesný i při větším zvětšení, nevýhoda je naopak rychlost.

5.7.1.2 Rastrově Vzhledem k jednoduchosti a podpory komprimovaných rastrových grafických formátů je v programu použita tato volba. Nevýhoda je nutnost použití vyššího rozlišení grafických sad kamenů a jejich neostrost při změně měřítka zobrazení. Výhoda je naopak větší rychlost zobrazení a dostupnější zdroje sad kamenů.

5.8 Zvuk Zvuku vyskytujícího se v programu je pramálo, mezi nejdůležitější patří provedení tahu. Zvuky nahrané pomocí klasického počítačového mikrofonu se vyznačují vysokou hladinou šumu. Proto je třeba je ještě dodatečně zpracovat a provést softwarovou (např.

37

programem Cool Edit) redukci šumu. Dostačující je vzorkovací frekvence 22 050 Hz, vzhledem k frekvenční charakteristice mikrofonu končící někde okolo 10 kHz. Další problém nastane v tom, že i přes svou krátkou délku dosahuje zvuk ve formátu PCM značných datových objemů. Pro jednoduchost a zahrnutí kodeku v operačním systému jsem zvolil kódování Microsoft ADPCM s konstantním kompresním poměrem 4:1.

5.9 Síla hry Síla hry záleží převážně na rychlosti procesoru, např. v šachové hře při zdvojnásobení rychlosti procesoru dojde k zvýšení herní síly o 70 ELO bodů. Síla hry tohoto programu v klasických šachách odpovídá přibližně 2 000 ELO bodům na procesoru AMD Duron 700 MHz, což je srovnatelné s algoritmem použitým v [Zillion]. Rychlost propočtu v tomto případě dosahuje 50 000 uzlů za sekundu. Ve srovnání s profesionálními programy je tato hodnota asi 4,5× pomalejší. Odhaduji, že 1,2× činí méně kvalitní překladač oproti C++, 1,5× obecnost přístupu a 2,5× poziční hodnocení i v materiálově nevyrovnaných pozicích. Existují však i výjimky, které jsou i několikrát pomalejší (např. nyní nejsilnější motor Rybka, který síly dosahuje hlavně díky mnoha vloženým znalostem). Vzhledem k existenci grafických rozhraní pro klasický šach lze použít myslící algoritmus bez GUI. Program používá pro komunikaci s uživatelským rozhraním standardní protokol UCI (Univesrsal Chess Interface). Má velikost okolo 100 KB. Nároky na paměť jsou 2 MB. S grafickým rozhraním jsou nároky vyšší, velikost programu je 800 KB a požaduje 16 MB paměti.

5.10Srovnání s konkurencí Srovnání jsem provedl s komerčním šachovým programem Fritz, hrající šachy na profesionální úrovni s Elem (hodnocení šachové síly) 2 700. Dále s programem Zillion of Games hrajícím mnoho deskových her s univerzálním herním algoritmem. Program

Herní síla Množství variant SDG 3 3 Fritz 5 1 Zillion of Games 3 5 Tab. 3:Srovnání s konkurencí, pozn. čím více bodů tím lépe

GUI

Celkem

5 5 1

11 11 9

Směr vývoje aplikace se zde nabízí dvěma směry. Buď rozšířit stávající sadu her případně zvýšit herní sílu u stávajících. Jako stávající se nabízí hlavně šach a to buď zlepšením stávajících algoritmů (přidání znalostí) případně zavedením GUI pro UCI rozhraní podobně jako v [Arena] a použít nějaký volně šiřitelný šachový motor např. [Toga], což ale přináší nevýhodu v omezení se pouze na standardní variantu šachů, případně na několik modifikací při použití motoru pro žravý šach. Další možnosti jsou např. hra po síti, více-jazyková podpora (kromě standardní anglické verze).

38

5.11Nároky na vybavení 5.11.1 Software Program kompilovaný pod platformou Win32 čili vyžaduje Win32 prostření (Windows 95/98/NT/2000/XP), popřípadě funguje i na operačním systému Unix, s použitím Wine např. verze 20041201 [Wine].

5.11.2 Hardware 5.11.2.1Procesor Teoreticky by dostačoval procesor 80486 vzhledem k použití instrukcí zavedených od této řady procesorů. Vzhledem k práci s grafikou je prakticky třeba alespoň procesor x86 výkonově srovnatelný s Intel Pentium II.

5.11.2.2Grafická karta Pro rozumné zobrazení je třeba alespoň 2 MB grafická karta zvládající rozlišení 1024×768 při 16-bitech.

5.11.2.3Operační paměť Celkové nároky na operační paměť nelze jednoznačně spočítat (v závislosti na grafice dané hry a zavádění formulářů se nároky mění za běhu). V OS Windows XP program vyžaduje přibližně 10 až 20 MB bez rozptylovacích tabulek, takže počítač s 32 MB RAM by měl být dostačující.

5.11.2.4Pevný disk Program je velmi úsporný a po dekomprimaci si vystačí s několika málo megabajty.

5.12Instalace Program nepotřebuje instalovat, stačí dekomprimovat zip archiv za pomoci např. [Zip] na pevný disk s přístupem i pro zápis (kvůli ukládání konfiguračních souborů). V případě potřeby lze pak z programu zaregistrovat koncovky souborů, které používá. Instalace UCI motoru je závislá na zvoleném grafickém rozhraní.

5.13Náhled aplikace Zde je náhled aplikace se standardním rozložením oken, obsahující tahy partie, hodiny, tahy z aktuální pozice, šachovnici partie, šachovnici analýzy a analýzu hlavních variant. Náhledy se vztahují k verzi 2.1.34.

39

Obr. 10:

Náhled aplikace

Dále následuje náhled okna analýzy hlavních variant.

Obr. 11:

Náhled okna analýzy

5.14Aktualizace Aplikace se vylepšuje, na adrese http://safrad.webzdarma.cz/Data/SDG.zip je dostupná ke stažení aktuální verze.

40

6 Závěr Dle našeho názoru se implementace programu povedla, aplikace hraje deskové hry proti lidským protihráčům na uspokojivé úrovni. Objektový přístup se ukázal vzhledem k různým náhledům na deskové hry (typ tahu, použité kameny, použitá deska) jako nepříliš vhodný. Algoritmy prohledávání stavového prostoru jsou universálně použitelné nejen pro námi použité hry, ale i pro jiné problémy řešitelné prohledáváním stavového prostoru. Omezení kladená na vlastnosti problémů byla uvedena v úvodu (dva hráči, úplná informace). Sílu algoritmu, vzhledem k jeho složitosti lze stále vylepšovat, u většiny her a variant to však není třeba, protože program lidského protivníka s přehledem poráží.

41

7 Seznam obrázků a tabulek 7.1 Obrázky Obr. 1:Indexování polí na desce velikosti 4×8................................................................12 Obr. 2:Indexování polí na desce velikosti 4×8................................................................13 Obr. 3:Rozložení indexů v dámě.....................................................................................13 Obr. 4:Reprezentace mocnina dvou (88h).......................................................................14 Obr. 5:Reprezentace mocnina dvou.................................................................................14 Obr. 6:Příklad nejdelšího možného skoku.......................................................................16 Obr. 7:Příklad pro ukázku reprezentace tahů v dámě......................................................16 Obr. 8:Procentuelní výhodnost obsazení pole (bez označení značí 100%).....................23 Obr. 9:Ukázka struktury uložení hlavní varianty do pole................................................25 Obr. 10:Náhled aplikace..................................................................................................40 Obr. 11:Náhled okna analýzy..........................................................................................40

7.2 Tabulky Tab. 1:Uložení po zmenšení rozptylovací tabulky..........................................................25 Tab. 2:Uložení po zvětšení rozptylovací tabulky............................................................25 Tab. 3:Srovnání s konkurencí, pozn. čím více bodů tím lépe..........................................38 Tab. 4:Adresářová struktura v příloze.............................................................................44

42

8 Použitá literatura a odkazy [Arena] [Caser] [Čtv] [DŠ] [Fisher] [Fruit] [Game] [GO] [Hry] [Jungle] [Klub] [Paral] [PGN] [PNG] [PSachy] [RBit] [Rozptyl] [SC4] [Search] [SOthello] [ŠPC] [Toga] [Tree] [UCI] [UPX] [Vari] [Velka] [Wine] [Winehq] [ZeroSum] [Zillion] [Zip]

www.playwitharena.com safrad.webzdarma.cz/Data/Caser.zip www.chesslady.com/index.php?page=trenink&s=28&oid=143 Václav Marek, Jan Kalendovský: Dáma a šach, Portál, 2001 fischer-random-chess.biography.ms/ arctrix.com/nas/fruit/ www.cs.nott.ac.uk/~gxk/aim/notes/gameplaying.doc www.ainewsletter.com/newsletters/aix_0301.htm www.sweb.cz/klub-deskovych-her/pravidla/abecedne.htm www.chessvariants.org/other.dir/animal.html Miloš Zapletal: Velká encyklopedie her: Hry v klubovně www.volny.cz/evcomp/evcpu.htm www.very-best.de/pgn-spec.htm#1 www.libpng.org/pub/png www.sportovnipravidla.cz/pravidla/sachy/sachy.php supertech.lcs.mit.edu/~heinz/dt/node8.html service.felk.cvut.cz/courses/X36DSA/Lesson10pub.ppt en.wikipedia.org/wiki/Connect_Four#Strategy_and_tactics www.cs.vu.nl/~aske/Papers/aij-final.ps.gz home.swipnet.se/~w-50714/othello/tutorial/intro.htm Dieter Steinwender, Frederic A. Friedel: Šachy na PC, Unis publishing, 1997 www.uciengines.de/UCI-Engines/TogaII/hauptteil_togaii.html en.wikipedia.org/wiki/Game_tree wbec-ridderkerk.nl/html/UCIProtocol.html upx.sourceforge.net www.chessvariants.org/ Miloš Zapletal: Velká kniha deskových her, Mladá ftonta, 1991 sourceforge.net/projects/winecfg www.winehq.com/ en.wikipedia.org/wiki/Zero-sum en.wikipedia.org/wiki/Zillions_of_Games winzip.com/

43

9 Příloha Na přiloženém CD se nachází tento dokument, spustitelný program SDG (Safrad's Desk Games) a UCI šachový motor včetně zdrojových kódů. Instalace je popsaná v kapitole 5.12. Následuje tabulka adresářové struktury přiloženého CD. Složka SDG SDG\Games SDG\Graphics SDG\Sounds SDG\ECO SDG\Data SDG\SDG_UCI Docs Source\SDG Source\Lib

Popis hlavní spustitelný program uložené záznamy o sehraných partiích soubory obsahující grafiku (kameny, ikony) soubory obsahující zvuky ECO kódy zahájení ostatní soubory jako seznam variant her a uživatelská nastavení UCI šachový motor tento dokument v několika formátech zdrojové kódy týkající se pouze tohoto projektu zdrojové kódy týkající se všech projektů, obsahující pomocné funkce Offline některé stažené dokumenty Tab. 4:Adresářová struktura v příloze

44