![]() ![]() |
ARCHIV |
||||||||||||||||||||||||||||
![]() ![]() ![]() ![]() ![]() ![]() |
|
haš 129, index 0 | haš 368, index 3 | haš 368, index 5 |
pozice po 1. e4 | pozice po 1. e4 e5 | základní postavení |
Takhle 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ám 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í. Koukneme se while cyklem doleva, tam už je jiná hodnota haš funkce. Tak tedy doprava na poslední políčko, zde odpovídá haš funkce a i pozice je správně, budeme tedy hledat tahy na indexu 5 v poli tahů.
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.
Zhruba takhle může fungovat knihovna zahájení v nějakém programu. Řada věcí by mohla fungovat i jinak. Známe předem množinu dat, můžeme se proto pokusit sestavit funkci, která je zde prostá. Umím si i představit nějakou funkci napsanou na míru zadaným datům, jejíž hodnotou bychom mohli pole přímo indexovat a podobně. Nicméně je dobré si uvědomit, že pro účely běžného šachového programu bude stačit prakticky jakákoli aspoň trochu rozumná datové struktura s nejhůře logaritmickým vyhledáváním. Uživateli bude nejspíš jedno, jestli program zatáhne za dvě desetiny vteřiny nebo jednu mikrosekundu. Zatímco desetinásobné zrychlení myšlení - rekurzivního propočtu může znamenat prohloubení minimálně o jeden půltah a 60 elo bodů (samozřejmě přesná čísla závisí na konkrétním programu), nekonečné zrychlení knihovny zahájení až na nulový čas znamená v průběhu celé partie tak vteřinu nebo dvě ušetřeného času a zlepšení programu díky ušetřenému času pro propočet dalších tahů v elo bodech nebude ani měřitelné.
Navrhnout algoritmy a datové struktury knihovny zahájení bylo celkem jednoduché. O to víc práce je se získáním vlastních dat. Nápad koupit si za pár korun v knihkupectví učebnici zahájení pro začátečníky a přeťukat do našeho formátu varianty není úplně nejlepší. Jednak řada knih (a to i celkem kvalitních) je až příliš ovlivněná subjektivním názorem autora na jednotlivá zahájení nebo je prostě poplatná současné šachové módě. Rovněž styl jednotlivých variant (ač třeba objektivně správných) nemusí programu sednout. Nicméně hlavním problémem bude rozsah knihovny. Moderní programy mají knihovnu zahájení s milióny pozic a data opsaná z nějaké učebnice zde nemohou konkurovat.
Naštěstí si můžeme knihovnu vytvořit z databáze skutečně sehraných partií. Seznam míst ke stažení databází je například zde. Nejčastěji se používá neúsporný, ale jednoduchý textový formát PGN. Jedná se o potenciálně velmi dlouhý textový soubor, ve kterém jsou v anglické notaci a s jednoduchou hlavičkou uloženy partie. Jedna partie může vypadat zhruba takhle:
[Event "F/S Odvetný zápas"] [Site "Bělehrad, Jugoslávie"] [Date "1992.11.04"] [Round "29"] [White "Fischer, Robert J."] [Black "Spasskij, Boris V."] [Result "1/2-1/2"] 1. e4 e5 2. Nf3 Nc6 3. Bb5 {Španělská hra} 3... a6 4. Ba4 Nf6 5. O-O Be7 6. Re1 b5 7. Bb3 d6 8. c3 O-O 9. h3 Nb8 10. d4 Nbd7 11. c4 c6 12. cxb5 axb5 13. Nc3 Bb7 14. Bg5 b4 15. Nb1 h6 16. Bh4 c5 17. dxe5 Nxe4 18. Bxe7 Qxe7 19. exd6 Qf6 20. Nbd2 Nxd6 21. Nc4 Nxc4 22. Bxc4 Nb6 23. Ne5 Rae8 24. Bxf7+ Rxf7 25. Nxf7 Rxe1+ 26. Qxe1 Kxf7 27. Qe3 Qg5 28. Qxg5 hxg5 29. b3 Ke6 30. a3 Kd6 31. axb4 cxb4 32. Ra5 Nd5 33. f3 Bc8 34. Kf2 Bf5 35. Ra7 g6 36. Ra6+ Kc5 37. Ke1 Nf4 38. g3 Nxh3 39. Kd2 Kb5 40. Rd6 Kc5 41. Ra6 Nf2 42. g4 Bd3 43. Re6 1/2-1/2
V jednom souboru může být podobných partií libovolně mnoho. Hlavička může mít řadu dalších nepovinných údajů, pro nás bude mít největší význam WhiteElo a BlackElo, tedy šachovou výkonnost obou soupeřů. Umožní nám snadno odlišit partie velmistrů od partií z oddílového přeboru ŠK Horní Kotěhůlky, jejichž kvalita jistě nebude valná. Nekvalitní partie nebudeme dále uvažovat.
Nyní již bude vytvoření knihovny zahájení poměrně jednoduchou záležitostí. Jedním průchodem projdeme celou databázi her a z partií kvalitních (dle ela) soupeřů sestavíme orientovaný graf hry, vrcholy budou pozice, které se vyskytly alespoň v jedné partii a hrany alespoň jednou zahrané tahy. Pro každou pozici i tah z příslušné pozice si nasčítáme, kolikrát se v naší databázi vyskytl, jak dopadaly partie pro jednotlivé tahy (0 za prohru, 1 za výhru a 1/2 za remízu) a případně i počet tahů od základního postavení nebo průměrné elo obou hráčů a podobně. Teď již vlastně máme knihovnu zahájení v paměti, stačí jen nadefinovat jednoduchá pravidla pro výběr pozic a knihovnu uložit v požadovaném formátu.
Konkrétní pravidla pro výběr pozic a tahů do knihovny se pochopitelně mohou lišit podle typu knihovny. Jiná knihovna se bude hodit pro mistrovství světa v počítačovém šachu, jiná pro volné partie s lidským soupeřem, hrané pro jeho zábavu a šachové vzdělávání. Pravidla pro výběr pozic a tahů by mohla vypadat zhruba takhle:
Máme tady vybrané pozice i tahy, které z nich budeme hrát. Zbývá ještě přiřadit tahům pravděpodobnost zahrání. Nejjednodušší je hrát tahy přesně v tom poměru, v jaké je hráli hráči z naší databáze. Můžeme přidělit vyšší váhu partiím velmistrů s vyšším elem. Časově náročná, ale velmi vhodná je i analýza myslícím algoritmem našeho programu. Knihovna by měla preferovat tahy, které se našemu algoritmu líbí a které považuje za správné. Jednak i velmistři chybují, ale především objektivně dobrý tah, kterému náš program nerozumí, nejspíš nebude dobrý z čistě praktického pohledu. V extrémním případě jej náš program v jednom z příštích tahů po opuštění známých pozic z knihovny prostě zahraje zpět. S šachovým programem je to prostě jako s lidskými hráči. Nemá cenu jej nutit hrát pozice, které mu nesednou. Analýzou našeho programu navíc můžeme získat seznam podezřelých pozic, kde velmistři hrají divné tahy a na které bychom se měli (minimálně z ladících důvodů) podívat ručně.
V příštím dílu si představíme databáze koncovek.
Příspívat do diskuze mohou pouze registrovaní uživatelé. |
28.11.2018 23:56 /František Kučera
Prosincový sraz spolku OpenAlt se koná ve středu 5.12.2018 od 16:00 na adrese Zikova 1903/4, Praha 6. Tentokrát navštívíme organizaci CESNET. Na programu jsou dvě přednášky: Distribuované úložiště Ceph (Michal Strnad) a Plně šifrovaný disk na moderním systému (Ondřej Caletka). Následně se přesuneme do některé z nedalekých restaurací, kde budeme pokračovat v diskusi.
Komentářů: 1
12.11.2018 21:28 /Redakce Linuxsoft.cz
22. listopadu 2018 se koná v Praze na Karlově náměstí již pátý ročník konference s tématem Datová centra pro business, která nabídne odpovědi na aktuální a často řešené otázky: Jaké jsou aktuální trendy v oblasti datových center a jak je optimálně využít pro vlastní prospěch? Jak si zajistit odpovídající služby datových center? Podle jakých kritérií vybírat dodavatele služeb? Jak volit vhodné součásti infrastruktury při budování či rozšiřování vlastního datového centra? Jak efektivně datové centrum spravovat? Jak co nejlépe eliminovat možná rizika? apod. Příznivci LinuxSoftu mohou při registraci uplatnit kód LIN350, který jim přinese zvýhodněné vstupné s 50% slevou.
Přidat komentář
6.11.2018 2:04 /František Kučera
Říjnový pražský sraz spolku OpenAlt se koná v listopadu – již tento čtvrtek – 8. 11. 2018 od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5). Tentokrát bez oficiální přednášky, ale zato s dobrým jídlem a pivem – volná diskuse na téma umění a technologie, IoT, CNC, svobodný software, hardware a další hračky.
Přidat komentář
4.10.2018 21:30 /Ondřej Čečák
LinuxDays 2018 již tento víkend, registrace je otevřená.
Přidat komentář
18.9.2018 23:30 /František Kučera
Zářijový pražský sraz spolku OpenAlt se koná již tento čtvrtek – 20. 9. 2018 od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5). Tentokrát bez oficiální přednášky, ale zato s dobrým jídlem a pivem – volná diskuse na téma IoT, CNC, svobodný software, hardware a další hračky.
Přidat komentář
9.9.2018 14:15 /Redakce Linuxsoft.cz
20.9.2018 proběhne v pražském Kongresovém centru Vavruška konference Mobilní řešení pro business.
Návštěvníci si vyslechnou mimo jiné přednášky na témata: Nejdůležitější aktuální trendy v oblasti mobilních technologií, správa a zabezpečení mobilních zařízení ve firmách, jak mobilně přistupovat k informačnímu systému firmy, kdy se vyplatí používat odolná mobilní zařízení nebo jak zabezpečit mobilní komunikaci.
Přidat komentář
12.8.2018 16:58 /František Kučera
Srpnový pražský sraz spolku OpenAlt se koná ve čtvrtek – 16. 8. 2018 od 19:00 v Kavárně Ideál (Sázavská 30, Praha), kde máme rezervovaný salonek. Tentokrát jsou tématem srazu databáze prezentaci svého projektu si pro nás připravil Standa Dzik. Dále bude prostor, abychom probrali nápady na využití IoT a sítě The Things Network, případně další témata.
Přidat komentář
16.7.2018 1:05 /František Kučera
Červencový pražský sraz spolku OpenAlt se koná již tento čtvrtek – 19. 7. 2018 od 18:00 v Kavárně Ideál (Sázavská 30, Praha), kde máme rezervovaný salonek. Tentokrát bude přednáška na téma: automatizační nástroj Ansible, kterou si připravil Martin Vicián.
Přidat komentář
30.11.2022 9:32 /
Kyle McDermott
Hosting download unavailable
13.12.2018 10:57 /
Jan Mareš
Re: zavináč
2.12.2018 23:56 /
František Kučera
Sraz
5.10.2018 17:12 /
Jakub Kuljovsky
Re: Jaký kurz a software by jste doporučili pro začínajcího kodéra?
20.9.2018 10:04 /
Jan Ober
Jaký kurz a software by jste doporučili pro začínajcího kodéra?