ZCUChess - 源码 - 源码 - 免费下载

开通博客赚积分

发布资源赚积分

ZCUChess

文件大小： unknow

源码售价： 5 个金币积分规则积分充值

充值1元得10金币

资源说明：Šachy vytvořené pro ZČU FAV

Semestrální práce z PC a PT
Martin Zadražil
5. ledna 2013

Obsah

1 Zadání
2 Analýza úlohy
2.1 Umělá inteligence a teorie šachové hry
  2.1.1 Od nejjednoduššího algoritmu ke kaskádové metodě
  2.1.2 Zpomalení je malé
  2.1.3 Lepší časová kontrola
  2.1.4 Třídění tahů
  2.1.5 Metoda okénka
  2.1.6 Prohlubování
  2.1.7 Dopočet do tiché pozice
  2.1.8 Prohlubování taktických variant
  2.1.9 Haš tabulky
  2.1.10 Databáze zahájení a koncovek
2.2 Reprezentace pozice
2.3 Reprezentace pole tahů
2.4 Ohodnocovací funkce
3 Popis implementace
3.1 Globální datové struktury
3.2 Reprezentace šachovnice, pozice a hodnot figur
3.3 Reprezentace tahu a množiny tahů
3.4 Statická ohodnocovací funkce
3.5 Myslící algoritmus
4 Uživatelská příručka
4.1 Instalace
4.2 Ovládání
5 Závěr
5.1 Problémy v průběhu psaní programu
5.2 Možná vylepšení

1 Zadání

Implementace jednoduchého šachového algoritmu, který umožňuje hru hráče proti počítači. Vstup a výstup bude probíhat na příkazové řádce.

2 Analýza úlohy

Nejprve je potřeba navrhnout základní datové struktury a rutiny, které musí obsahovat každý šachový program i takový, který neobsahuje žádný myslící algoritmus a umožňuje například jen hru dvou lidských hráčů po síti. Patří sem funkce pro

nalezení všech legálních tahů z dané pozice,
kontrola šachu a matu,
funkce kontrolující dodržení pravidel při rošádě a braní mimochodem,
funkce, která zahraje samotný tah.

Bude následovat umělá inteligence a chybět nesmí ani několik málo funkcí pro komunikaci s okolím, jako je zparsování tahu zadaného z klávesnice, vypsání tahu, upozornění na přemýšlení programu a podobně.

2.1 Umělá inteligence a teorie šachové hry

2.1.1 Od nejjednoduššího algoritmu ke kaskádové metodě

Šachy jsou čistě matematickou úlohou, k jejímuž vyřešení se dá v každém případě dopočítat. Za vyřešení úlohy můžeme považovat mat v případě vyhrané pozice, pat v případě remízové pozice nebo alespoň co největší oddalování porážky v případě prohrané pozice. Klíčovou funkcí je statická ohodnocovací funkce, která vrátí číselnou hodnotu dané pozice. Nejjednodušší algoritmus, který nehraje úplně náhodně, vygeneruje všechny tahy ze zadané pozice, každý z nich zahraje a vzniklou pozici ohodnotí statickou ohodnocovací funkcí. Pokud je hodnota pozice vyšší než dosud nejvyšší, uloží ji i tah, kterým jsme se na ni dostali. Poté zahraje tah zpět a tak dále, dokud nevyzkoušíme všechny tahy. Tento algoritmus je sice lepší než náhodné generování tahů, ale přesto je velmi primitivní. Sebere klidně dámou krytého pěšce, nepokryje jednotahový mat a podobně.

Vylepšením je přidat rekurzi. Zahrajeme všechny tahy z dané pozice, na tyto tahy zahrajeme odpověď soupeře, pak zase naši odpověď a tak dále až do nějaké hloubky n, kde zavoláme statickou ohodnocovací funkci. Tento algoritmus se jmenuje minimax. Na šachovnici je v základním postavení 16 pěšců, každý z nich může táhnout nejvýše šestkrát, poté se promění v nějakou figuru. Když nepočítáme krále, které není možné sebrat, je na šachovnici 30 figur a každá z nich může být sebrána maximálně jednou. Pokud se během 50ti tahů (50 tahů bílého a 50 tahů černého, celkem 100 půltahů) netáhne pěšcem ani nesebere žádná figura, je partie považovaná za remízu. Díky tomu můžeme shora odhadnout hloubku šachové partie na (16 * 6 + 30 + 1) * 100 = 12700 půltahů. Algoritmus minimax s hloubkou propočtu 12700 bude teoreticky hrát šachy úplně dokonale, alespoň v tom smyslu, že žádnou remízovou pozici neprohraje, každou vyhranou pozici nejen vyhraje, ale dokonce tím nejrychlejším způsobem, a při prohrané pozici bude porážku alespoň maximálně oddalovat.

Paměťová složitost minimaxu není příliš velká, neboť v zásobníku rekurzivního propočtu je v danou chvíli pouze jedna varianta. Kdyby se tedy minimaxu opravdu podařilo nalézt variantu dlouhou 12 700 půltahů a jedna instance minimaxu zabrala 1 kB, vešli bychom se i s volajícím kódem pohodlně do 13 MB. Na propočet stromu tak bohaté hry, jakou šachy bezesporu jsou, nám tedy stačí pouze pár megabajtů operační paměti. Bohužel časová složitost minimaxu je exponenciální v^h , kde v je větvící faktor a h hloubka propočtu. Předpokládejme, že z pozice můžeme vygenerovat 20 tahů (například z výchozího postavení 16 tahů pěšci, 4 tahy jezdci) a že dokážeme spočítat milion ohodnocovacích funkcí za sekundu. Propočet do hloubky 2 pak potrvá 0,008 sekundy, propočet do hloubky 5 3,2 sekundy, propočet do hloubky 10 zhruba 118 a půl dne. Při hloubce 12 700 by to pak bylo 3,81 * 10¹⁶⁵⁰⁹ let, konce výpočtu by se tedy nejspíš nedočkala ani naše galaxie.

Časovou složitost můžeme zlepšit. Potřebujeme-li zmenšit výsledek vzorce v^h , můžeme zmenšovat h, což je hloubka propočtu a na kvalitu hry má zásadní vliv. Druhou možností je zmenšit v, což je větvící faktor a některé varianty vůbec nepočítat. I přesto se můžeme dostat ke správnému výsledku.

V pozici na diagramu je na tahu bílý, jedná se o známou pozici ze zahájení jménem španělská hra (1. e4 e5 2. Jf3 Jc6 3. Sb5), kde se černý brání obvyklým tahem 3. ...a6. Napadl tedy bílému střelce a ten musí hrozbu nějak pokrýt. Běžné tahy jsou nyní 4. Sa4 a Sxc6, hrát by se dalo i Sc4 a snad ještě velmi defenzivní Se2, všechny ostatní tahy jsou již vyloženě špatné. Z této pozice dáme programu za úkol provést propočet do hloubky dvou půltahů. Vygeneruje tahy a zkouší jeden po druhém zahrát. Generátor tahů je lehce modifikovaný tak, aby vracel braní před ostatními tahy. Program tedy nejprve propočítá 4. Sxc6, projde všechny odpovědi černého a zjistí, že po nejlepším 4. ...dxc6 je pozice přibližně vyrovnaná. Bílý sice ztratil výhodu dvojice střelců, ale zase černému znehodnotil pěšcovou strukturu. Ohodnocení prvního tahu zatím proběhlo tak, jako v algoritmu minimax. Rozdíl nastane až u druhého tahu bílého 4. Sxa6. Jedná se o zjevnou chybu, kterou bílý odevzdává střelce za pouhého pěšce, ale minimax by musel projít všechny odpovědi, aby si to uvědomil. Tedy poctivě počítat a ohodnocovat nejen 4. ...bxa6 a Vxa6, ale i zcela nesmyslné tahy jako 4. ...Jh6 nebo g5. Modifikovanému algoritmu stačí jediná: 4. ...Vxa6 nebo bxa6. Navíc generátor tahů, který preferuje braní, vrátí jeden z uvedených tahů hned jako první. Jak program pozná, že může propočet odpovědí na 4. Sxa6 přerušit a prohlásit tah za neperspektivní? Z propočtu 4. Sxc6 si zapamatoval hodnotu nejlepší odpovědi 4. ...dxc6, tedy zhruba 0 tj. vyrovnanou pozici. Při propočtu dalších tahů (4. Sxa6) uvedenou hodnotu použijeme jako práh. Pokud jej jakákoli odpověď (4. ...bxa6 nebo Vxa6) přesáhne, propočet tahu (4. Sxa6) ukončíme, neboť již víme, že je špatný. Jinými slovy: pokud víme, že tah je špatný (= horší než nějaký jiný - zde 4. Sxc6), nemá smysl dále zkoumat, jestli není náhodou ještě o něco horší, než jsme zatím zjistili. Pokud počítáme do hloubky 3 a více, dojde při prořezávání na oba hráče a jsou zde proto meze pro obě strany. Dolní se říká alfa, horní beta, odtud také název algoritmu alfabeta metoda (nebo alfabeta ořezávání). Pokud během propočtu narazíme na variantu, která je horší než alfa, můžeme ji zahodit. Vyjde-li nám varianta lepší než beta, může se jí zase vyhnout soupeř a zahrát tah, který je lepší pro něj. Časová složitost alfabety silně závisí na pořadí tahů, což ovlivňuje, jak rychle se nám podaří sevřít meze alfa a beta. Časová složitost optimální alfabety je v^h∕2 , můžeme se s ní tedy za stejný čas dostat dvakrát hlouběji než s minimaxem. Je tudíž žádoucí, aby nejnadějnější varianty počítal algoritmus jako první. Existuje několik heuristik, jak odhadnout už v generátoru tahů, které varianty by mohly být nejlepší:

Sežer, co můžeš: Způsobí-li tah změnu materiálu, posuneme ho na více dopředu. Preferovat můžeme rovněž braní nižší figurou.
Historická heuristika: Je založena na myšlence, že pokud byl tah dobrý v jedné variantě, nejspíš bude dobrý i v jiné. Tři typy této metody mohou být:
Globální tabulka tahů: Program si musí nějak pamatovat tahy. Informace, odkud a kam se táhne, případně typ nové figury po proměně pěšce, se při troše snahy vejde do 16 bitů. Vytvoříme si tedy pole velikosti 216, pro každý možný tah jeden byte. Na počátku propočtu obsahuje pole samé nuly. Když se nějaký tah ukáže jako dobrý (větší než aktuální hodnota alfa), zvětším hodnotu jeho políčka v poli. Když potom po vygenerování třídíme tahy, uvažujeme ještě také hodnotu této heuristiky. Jak přesně se mají zvětšovat hodnoty v tabulce, je složitá otázka. Je zřejmé, že dobré tahy z pozic vzdálenějších od kořene mají menší význam než dobré tahy z pozic blízkých kořeni. Je to tím, že průměrná pozice z propočtu je bližší kořeni než nějakému listu ze vzdálené větve.
Nejlepší tahy pro danou hloubku: Pro každou hloubku zanoření v propočtu si zapamatujeme poslední dva zlepšující tahy. Tyto tahy dostanou při propočtu v tomto zanoření speciální bonus. Oproti globální tabulce má metoda tu výhodu, že se více týká aktuální pozice a příslušné hloubky, chová se tedy lokálně. Tím pádem většinou preferuje zlepšující tahy z blízkých uzlů a u nich je opravdu dost velká pravděpodobnost, že budou dobré i v počítané pozici. Nevýhodou je, že ohodnocuje jen relativně málo tahů (přesně 2).
Hlavní varianta: Program si uchovává v tabulce dosavadní hlavní variantu, tedy větev výpočtu při optimální hře (optimální ve smyslu ohodnocení listů) obou hráčů. Tah, který přísluší k hlavní variantě, bude zřejmě dobrý i v celé řadě jiných variant, a proto získává bonus. Varianty se ukládají do matice, využívá se ale jen horní trojúhelník. V jednom políčku matice je jeden tah. Jsme-li při propočtu v nějakém uzlu, počítáme v tomto okamžiku vlastně hodnotu všech pozic na cestě z kořene do našeho uzlu. V i-tém řádku (od diagonály dál) si uchováváme nejlepší dosavadní variantu z i-té pozice na cestě od kořene. Dejme tomu, že v hloubce i došlo k nalezení zlepšujícího tahu. V řádku i máme původní nejlepší variantu (od naší pozice dál) a v řádku i+1 je zlepšující varianta. Za této situace musíme zkopírovat i+1-ní řádek na pozici i-tého (z něj zůstane jen první tah na diagonále).

Nevýhodou alfabety je její pevná hloubka. Jsme-li v zahájení nebo střední hře, bude tahů k ohodnocení velmi mnoho. Hloubka výpočtu v této části hry by tedy neměla být příliš vysoká, jinak se k výsledku nedopočítáme v rozumném čase. Naopak v koncovce, kdy je pouze pár přípustných tahů, lze hloubku propočtu zvýšit. Tento problém řeší kaskádová metoda. Jedná se vlastně o alfabeta metodu, která postupně počítá do hloubky 1,2,3,...,n. Na první pohled se může zdát zbytečné počítat pokaždé znovu, nicméně kaskádová metoda má několik výhod:

2.1.2 Zpomalení je malé

Protože je složitost alfabety exponenciální, zpomalí kaskádová metoda program cca jeden a půl krát. Dejme tomu, že průměrný větvící faktor šachu je 38, při dobrém alfabeta ořezávání se dostaneme na větvící faktor zhruba odmocnina z 38, přiližně 7. !7^n-1 je zhruba o řád menší než 7ⁿ .

2.1.3 Lepší časová kontrola

V praxi obvykle nezní zadání _”=ldej mi nejlepší tah do hloubky 5“, ale _”=ldej mi nejlepší tah, máš na to 5 sekund“. Potom je velmi obtížné stanovit hloubku propočtu, kterou dosáhneme v daném čase. U kaskádové metody prostě provádíme iterace tak dlouho, dokud máme čas. To nám právě umožní v koncovce (případně kdykoliv, když je množina možných tahů dostatečně malá) počítat do větší hloubky.

2.1.4 Třídění tahů

Kaskádová metoda poskytuje lepší možnosti třídění tahů. Propočet do hloubky 1 začneme s tahy setříděnými podle jednoduchých heuristik v generátoru tahů. Nejlepší tah poté přemístíme na začátek, pokračujeme propočtem do hloubky 2, nejlepší taj z hloubky 2 opět přemístíme na začátek a tak dále. Tím se nám podaří velmi rychle sevřít interval alfa a beta okolo nejnadějnějších tahů, což kaskádovou metodu ještě dále zrychlí. Případů, kdy zahájíme propočet několika špatnými tahy, bude velmi málo - obvykle se jedná o pozice s možností složité oběti nebo komplikovaného tahu.

2.1.5 Metoda okénka

Alfabeta metoda svírá interval alfa a beta velmi defenzivně tak, aby se vždy dopočítala ke správnému výsledku. Celý výpočet můžeme zrychlit tím, že meze alfa a beta ještě více sevřeme - vytvoříme interval alfa2 a beta2, který bude podmnožinou původního alfa a beta. Pokud jsme měli pravdu, ušetřili jsme na výpočtu nějaký čas, pokud ne, interval prostě přeteče a v následující iteraci kaskádové metody se počítá interval s již opravenými mezemi.

2.1.6 Prohlubování

Herní algoritmus počítá do nějaké hloubky, na jejímž konci ohodnotí pozici statickou ohodnocovací funkcí. Tento postup dobře funguje v běžných pozicích, ale v taktických (jako je výměna těžkých figur, pozice tah před matem, kdy vítězná strana obětovala materiál, atp.) selhává. Přitom by zde stačila o něco málo větší hloubka propočtu a program by hrozby včas viděl. Celkovou hloubku propočtu nemůžeme příliš zvyšovat - program by se nedopočítal. Řešením je tedy prohloubení těch variant, které jsou obzvláště zajímavé.

2.1.7 Dopočet do tiché pozice

Dopočet do tiché pozice patří v šachu k nejjednodušším a zároveň nejdůležitějším vylepšením alfabeta metody. Na úroveň hry programu má zcela zásadní vliv. Spočívá v tom, že pokud se v propočtu dostaneme do listu, neodhadujeme hodnotu pozice statickou ohodnocovací funkcí, ale jakousi modifikací alfabety, která se liší tím, že bere v úvahu pouze braní a proměny pěšce. Vzhledem k tomu, že hráči odepíráme všechny ostatní tahy (tzv. tiché tahy), musíme mu umožnit nehrát, jinak bychom jej nutili i do nevýhodných braní. Funkce tedy vrací maximum z hodnoty pozice odhadnuté statickou ohodnocovací funkcí a rekurzivního dopočtu braní. Právě dopočet do tiché pozice řeší případy nedopočítaných výměn. Dopočet samozřejmě hodně zdržuje a sníží základní hloubku propočtu, ale pozitivní efekt je i tak obrovský. Dopočet do tiché pozice má navíc kladný vliv i na stabilitu výpočtu - již se nám nestane příliš často, že by zvýšení základní hloubky propočtu mělo nějaký zásadní vliv na hodnotu varianty.

2.1.8 Prohlubování taktických variant

Dopočet do tiché pozice je účinný, ale neřeší vše. Ve zvlášť nadějných variantách bývá dobré hloubku propočtu o jedničku zvýšit a nemusí se při tom nutně jednat o braní nebo proměny pěšce. K prohloubení také nemusí dojít jen v listu. Kdy přesně má smysl prohlubovat, je složitá otázka. Za typické kandidáty na prohloubení můžeme označit tahy:

Kdy je sebraná figura, která v minulém tahu sama brala (může se jednat o dokončení výměny)
Pokrytí šachu představením (může být jen oddálením matu skrývajícího se za horizontem propočtu)
Jakékoliv varianty s vynucenými tahy
Vidle pěšcem i jezdcem a podobné taktické údery
Varianty s tzv. Fisherovým střelcem
Taktické hrozby králi

Při prohlubování je potřeba postupovat velmi obezřetně, neboť prohloubení jedné varianty zkrátí výpočetní čas ostatních variant.

2.1.9 Haš tabulky

Až do tohoto okamžiku jsme se snažili zrychlit výpočet pomocí ořezávání a svírali jsme interval alfa a beta, jak to jen bylo možné, abychom odřízli co nejvyšší počet variant, které nemá smysl počítat. Existuje však ještě jeden druh variant, které rovněž nemusíme počítat. Jde o dvojice variant, které se od sebe liší pouhým prohozením tahů. Pokud program počítá do hloubky 5 půltahů ze základního postavení, nevynechá ani variantu bílý pěšec na e4, černý pěšec na c5 v prvním tahu, bílý jezdec na f3 v druhém tahu a z této pozice počítá ještě do zbývající hloubky 2 půltahy. Ke stejnému výsledku se však dostane i z pozice, kdy v prvním tahu přijde bílý jezdec na f3 a černý pěšec na c5 a ve druhém tahu bílý pěšec na e4. Následující dva půltahy se budou počítat znovu. Je přitom zřejmé, že vzniklou pozici stačí zkoumat jen jednou. V zahájení a střední hře s velkým počtem figur a malou hloubkou propočtu dochází k těmto duplicitám ještě poměrně zřídka. Mnohem horší je situace v koncovce s malým počtem figur. Typickým příkladem je koncovka dvou králů, v níž mají obě strany už jen několik zablokovaných pěšců. Král se obvykle snaží vytlačit soupeřova monarchu (obvykle i s využitím nevýhody tahu), pobrat soupeřovy pěšce a prosadit ty své do dámy. Obě strany přitom mají na výběr jen několik málo přípustných tahů, a tak hloubka propočtu roste oproti střední hře i dvojnásobně. Při podobných hlubokých propočtech dochází k opakovanému vyhodnocování jedné varianty, vzniklé jen přehozením tahů, zcela běžně. Právě v podobných typech pozic přitom může mít počítač s lidským soupeřem problémy. Jednoduchý charakter pozice totiž umožní lépe oprostit plán výhry nebo obrany od detailního propočtu (případně lidský propočet degeneruje na jedinou, ale zato dlouhou variantu bez větvení) a umožní vidět mnohem dál i člověku.

Řešením je mít haš tabulku s výsledky jednotlivých výpočtů, do které se podíváme, a pokud zde výsledek propočtu z naší pozice najdeme, okamžitě ho vrátíme. Je nutné dát pozor na několik věcí:

Ukládat je třeba i hloubku propočtu, neboť nelze nahradit propočet výsledkem předchozího propočtu do menší hloubky.
Alfabeta nedává jen mezivýsledky typu _”=l∙pozice má cenu = 3“, ale i _”=lpozice má cenu ≤ 3“ nebo _”=lpozice má cenu ≥ 3“. Tyto mezivýsledky je rovněž nutné ukládat.
Musíme pracovat velmi rychle s velkým množstvím dat.
Program by neměl číst z disku - struktura se musí za každou cenu vejít do paměti.
Je lepší, když struktura zapomíná než aby swapovala
Pozice obsahuje 64 polí a stavovou informaci o tahu, právu na rošády a braní mimochodem, ale jeden záznam ve struktuře by měl mít Jen několik bytů, proto volíme haš tabulku.

V této haš tabulce nemusíme řešit kolize - nová nebo cennější hodnota prostě přepíše starou. Je to rychlejší a jednodušší než na jednotlivých prvcích vytvářet spojové seznamy a zabývat se alokováním a uvolňováním paměti.

2.1.10 Databáze zahájení a koncovek

Každá šachová partie začíná vždy stejnou pozicí. Je celkem pochopitelné, že šachisté velmi pečlivě studují jednotlivé varianty vzniklé ze základního postavení již v klidu doma s počítačem nebo v klubu během tréninku a ne až v omezeném čase během partie. O konkrétních zahájeních byly napsány stovky knih, věnovali se jim ti nejlepší šachisté teoretici. Během zahájení běžně vznikají velmi komplikované pozice, ve kterých se nevyznají ani velmistři, a malá nenápadná a těžko odhalitelná chyba může vést k rychlé prohře nebo alespoň k výhodě soupeře. Rozmotat přímo za šachovnicí několik delších a trochu rozvětvených vynucených variant (které během desítek let vymysleli šachoví teoretici) bývá bez předchozí přípravy nad síly i těch nejlepších hráčů a dnešních programů, ale naučit se řešení nazpaměť a pochopit ho dokáže při troše snahy i průměrný klubový šachista nebo třeba náš program. Program naučíme zahájení tak, že někam uložíme pozice běžné v zahájení a/nebo jejich haš funkce a k nim sadu tahů, které od programu v uvedené pozici očekáváme. Každému tahu zároveň přiřadíme pravděpodobnost jeho zahrání. Například pro základní postavení může seznam vypadat takto:

30% 1. e4
30% 1. d4
15% 1. c4
13% 1. Jf3
5% 1. f4
2% 1. b3
1% 1. b4
1% 1. g3
1% 1. e3
1% 1. d3
1% 1. Jc3

Největší pravděpodobnost budou mít dobré a obvykle hrané tahy, méně běžným a nepříliš ambiciózním tahům, které však pozici bílého nijak neohrožují, dáme jen malou pravděpodobnost (hodí se občas k vyprovokování lidského soupeře) a tahy vyloženě špatné jako například 1.f3? nebo 1.h3?, nebudeme uvádět vůbec, program je tedy nebude hrát. Podobný seznam pravděpodobností ohodnocených tahů budeme mít pro každou naučenou pozici uložený v nějaké datové struktuře postavené nad hašovací funkcí pozice. Tahů z pozic je proměnlivé množství. Typická vyhledávací datová struktura proto nebude obsahovat přímo tahy. Místo nich v ní budou indexy do pole tahů zakončené nulou. Ukážeme si to na příkladu se setříděným polem a hašovací funkcí, která není na naší množině uložených pozic prostá. Obsahovat bude jen 3 pozice: základní postavení (haš = 368) se třemi tahy 1. e4 (40%), 1. d4 (40%) a 1. c4 (20%), pozici po 1. e4 (haš = 129) se dvěma tahy 1. ...c5 (50%) a 1. ... e5 (50%) a nakonec pozici po 1. e4 e5


haš 129, index 0	haš 368, index 3	haš 368, index 5

pozice po 1. e4	pozice po 1. e4 e5	základní postavení

Takto by vypadala vyhledávací struktura. Pozice bychom si pamatovali nejspíš fyzicky odděleně, například na stejném indexu v jiném poli, zde je proto máme v druhém řádku. Dejme tomu, že hledáme tah ze základního postavení. Spočítáme si hašovací funkci 368. Nějakým algoritmem pro vyhledávání v setříděném poli s rovnoměrným rozdělením dat (logaritmicky půlením nebo ještě lépe dělením podle hodnoty haš funkcí) najdeme políčko se správnou hodnotou haš funkce, dejme tomu, že máme smůlu, a bude to prostřední políčko. Zjistíme, že pozice není naše, neboť došlo ke kolizi haš funkcí. Podíváme se while cyklem doleva, a vidíme tam už jinou hodnotu haš funkce. Podíváme se tedy doprava na poslední políčko. Zde odpovídá haš funkce a také pozice je správně, budeme tedy hledat tahy na indexu 5 v poli tahů. Tabulka tahů pak může vypadat zhruba takto:


0	1	2	3	4	5	6	7	8

c5 (50%)	e5 (50%)	0	Jf3 (100%)	0	e4 (40%)	d4 (40%)	c4 (20%)	0

V poli od pozice 5 až k následující nule jsou tahy e4, d4 a c4, vygenerujeme tedy náhodné číslo z rozsahu 0 až 100, padne třeba 50 a program zahraje 1. d4.

S ubývajícím počtem figur a blížícím se koncem partie se pozice postupně zjednodušuje. Při propočtu ubývá možných variant, spousta z nich vede do stejné pozice, jiné zase brzy končí matem nebo remízou. Program by měl tudíž v jisté chvíli začít počítat dokonale. Pokud však zkusíme standardnímu prohledávacímu algoritmu předložit třeba nějakou pozici z koncovky střelce a jezdce proti samotnému králi, kvalitní program koncovku sice zvládne - zatlačí soupeřova krále do rohu barvy střelce a tam mu nasadí mat, ale rozhodně nenajde ten nejrychlejší postup a maty třeba 20. tahem zdálky prostě neuvidí. V opravdu těžkých koncovkách typu dáma proti dvěma lehkým figurám pak běžný kvalitní myslící algoritmus již bude chybovat a některé vyhrané pozice vyhrát nedokáže. V omezeném čase není možné ani v poměrně jednoduché koncovce projít celý graf hry z kořene k listům, díky kolizím v hašovací funkci navíc budeme řadu variant počítat opakovaně, takže s dokonalou hrou nemůžeme počítat ani v elementární koncovce dámy proti samotnému králi. Naštěstí je to s pozicemi z koncovek podobné, jako s těmi ze zahájení. Dají se naučit. Všech možných pozic několikafigurové koncovky je sice z lidského pohledu mnoho, ale počítač má posunutá měřítka. Jednoduchý horní odhad pro počet pozic n-figurové koncovky je 2 * 64ⁿ , neboť každá figurka může být na jednom ze 64 polí a možnosti se násobí. Úvodní dvojka je tam kvůli právu tahu, buď hraje bílý nebo černý. Náš odhad bychom mohli i zpřesnit na 2 * 64 * 63 * 62 * ... * (64 - n + 1), protože dvě figurky nemohou být na stejném políčku, takže první figurka má 64 možností, druhá jen 63 atd. Mohli bychom také vyškrtat nepřípustné pozice, ztotožnit stejné figury atd., ale úvodní vzorec nám zároveň dává návod, jak velmi jednoduše a efektivně každé pozici zkoumané koncovky přidělit číslo od 0 do 2 * 64^n-1 (její místo v tabulce příslušné koncovky) a naopak ke každému číslu z uvedeného intervalu přiřadit pozici. Stanovíme si pořadí figur naší koncovky podle jejich barvy a materiální hodnoty. Například pro koncovku jezdce a střelce to může být pořadí bílý král, bílý střelec, bílý jezdec, černý král. Očíslujeme políčka šachovnice od 0 do 63, přičemž a1 bude 0, a2 bude 1 atd., h8 bude 63. Máme-li n jednoznačně seřazených figur, označíme čísla políček, na nichž se nacházejí, p₀ až p_n-1 . U koncovek s opakováním jednoho druhu kamene (například koncovka krále proti dvěma střelcům) budeme jako první uvažovat figuru s vyšším indexem políčka. Číslo pozice pak bude p₀ + 64 * p₁ + 64² * p₂ + ... + 64^n-1 * p_n-1 + ( hraje bílý ? 64ⁿ : 0) .

Na obrázku je příklad pozice z koncovky dvou střelců. Pořadí figur bude KSSk, tedy bílý král a oba střelci a nakonec černý král. Na tahu je bílý a na naší šachovnici hraje nahoru, střelci jsou tedy na d3 a e3, bílý král na f3 a černý na e5. V následující tabulce je výpočet čísla pozice v rámci dané koncovky. Výsledek je 26 293 525.

Suma


Figurka	Pole	Index	Hodnota	Výsledek

Bílý král	f3	21	21	21

První bílý střelec	e3	20	20 * 64	1 280

Druhý bílý střelec	d3	19	219 * 64²	77 824

Černý král	e5	36	36 * 264³	9 437 184

Bílý na tahu			264⁴	16 777 216

			26 293 525

Opačný převod z čísla na pozici bude analogický, číslo rozložíme na cifry v 64-kové soustavě a to budou indexy políček jednotlivých kamenů.

Vlastní algoritmus vygenerování databáze n-figurové koncovky bude vypadat přibližně takto:

Rekurzivně stejným algoritmem vygeneruj databáze koncovek, které z naší koncovky mohou vzniknout. (Například pro koncovku dámy proti věži vygeneruj nejprve koncovku se samotnou dámou a se samotnou věží.)
Naalokuj místo pro 2 * 64ⁿ čísel a vyplň je nulami
Projdi přirozená čísla od 0 do 2 * 64ⁿ - 1 , ke každému vygeneruj pozici. Je-li nepřípustná (2 figury na sobě, šach nehrajícímu), vlož do pole čísel na daný index konstantu CHYBA, je-li černý v matu, vlož 1, je-li bílý v matu, vlož -1.
Projdi přirozená čísla od 0 do 2 * 64ⁿ - 1 , přeskoč ta, kde je na daném indexu v poli jiné číslo než nula. Ke každému číslu vygeneruj pozici. Na náš index do pole vlož, stručně řečeno, hodnotu propočtu minimaxem do hloubky 1 s ohodnocením pomocí již spočítaných hodnot a nul v poli. Podrobně řečeno: Dejme tomu, že hraje bílý (pro černého budeme postupovat analogicky). Vygeneruj z pozice tahy, zahraj je. Pokud zahraným tahem přešla pozice do jiného druhu koncovky (proměna pěšce, braní), podívej se do tabulky pro tuto koncovku, kolikátým půltahem bílý dává nebo dostává mat, případně zda je pozice remízová. Pokud zůstal zachován typ koncovky, spočítej si index pozice a podívej se do pole, zda a jak již máme pozici ohodnocenou. 0 znamená, že zatím nevíme, kladné číslo, že je pozice vyhraná za bílého, záporné, že za černého. Je-li mezi čísly alespoň jedno kladné, vlož do pole na náš index to nejmenší z těch kladných čísel zvětšené o 1. (Například z 0, 0, 0, 5, 3, -2, 0, 0, -2, -4 vyber 3 a do pole na náš index dej 3 + 1 = 4. Znamená to, že dáváme mat 2. tahem, neboť jsme o 3 půltahy od 1, což je mat.) Jsou-li všechna čísla záporná, je pozice za bílého prohraná, vyber z nich tedy to nejmenší (s největší absolutní hodnotou) a do pole na náš index ho dej zmenšené o 1. (Například z -2, -4, -6, -6, -4 vyber -6 a do pole dej -7. To znamená, že jsme na tahu a dostáváme mat 3. tahem.) Poslední možností je, že mezi čísly je alespoň jedna 0 a zbytek jsou buď nuly nebo záporná čísla. V tom případě ještě nemůžeme rozhodnout a v poli necháme nulu.
Pokud jsme zapsali do pole alespoň jednu nenulu, pokračuj bodem 4.
Ulož pole do souboru tak, jak je.

Máme-li vygenerovanou tabulku, je již velmi jednoduché napsat optimální algoritmus hry. Jedná se o prostý minimax do hloubky 1. Místo běžné ohodnocovací funkce se budeme dívat do tabulky. 0 znamená, že žádná ze stran nemůže vyhrát, tedy remíza. Kladná čísla jsou pozice vyhrané za bílého, čím dál od jedničky, tím dál od matu. Totéž platí s černým pro záporná čísla. V remízových pozicích pak můžeme spustit i klasický myslící algoritmus omezený na tahy, které nevedou k naší prohře. Jde jen o to, aby v remízových pozicích, kde ovšem o remízu bojuje soupeř, program nerezignoval na teoreticky marnou, ale prakticky proti reálnému soupeři často nadějnou snahu o výhru a nezahrál prostě jakýkoli neprohrávající tah. Například v těžké (pro 2 jezdce), ale remízové koncovce dámy proti dvěma jezdcům by program asi neměl nastavit dámu. To sice objektivně není chyba, neboť i koncovka krále a dvou jezdců proti samotnému králi je remízová, ale subjektivně to jistě chyba je a uživatel by to nejspíš programu neodpustil.

Bohužel tento algoritmus není na současných počítačích dostatečně rychlý - na počkání získáme jen třífigurové koncovky, přes noc pak čtyřfigurové. Jednou z nejjednodušších a zároveň velmi účinných metod, jak výpočet zrychlit a zmenšit i objem vygenerovanýc

部分文件列表（点击文件名可查看文件内容）

					
									本源码包内暂不包含可直接显示的源代码文件，请下载源码包。