LINUXSOFT.cz Přeskoč levou lištu
Uživatel: Heslo:  
   CZUKPL

> Šachové myšlení (12) - Knihovna zahájení

Dnes si ukážeme, jak napsat pro náš program knihovnu zahájení a především jak získat potřebná data.

25.2.2010 12:00 | Jan Němec | Články autora | přečteno 10027×

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 se dokáže při troše snahy i průměrný klubový šachista nebo třeba náš program.

Datová struktura a čtení dat

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

Součet samozřejmě bude vždy 100%. 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 (ať už je to setříděné pole v paměti nebo souboru, B-, AVL- nebo dokonale vyvážený strom, C++ mapa nebo dokonce tabulka třeba v MySQL) 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 (a jako na potvoru došlo ke kolizi, haš = 368) s jediným tahem 2. Jf3 (100%)

Vyhledávací struktura
haš 129, index 0haš 368, index 3haš 368, index 5
pozice po 1. e4pozice po 1. e4 e5zá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ů.

Pole tahů
012345678
c5 (50 %)e5 (50 %)0Jf3 (100%)0e4 (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é.

Získávání dat

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:

  • Cesta od kořene k pozici má délku nejvýše 60 půltahů
  • Pozice se vyskytla alespoň 3 krát
  • Tah se hrál buď alespoň 100 krát nebo alespoň v 10% případů
  • Tah alespoň v jednom případě nevedl k prohře
  • Úspěšnost po zahraném tahu není výrazně horší než úspěšnost z výchozí pozice

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ě.

Pokračování příště

V příštím dílu si představíme databáze koncovek.

Verze pro tisk

pridej.cz

 

DISKUZE

Pravidlá pre vytvorenie zahájení 21.3.2010 13:33 msx.
  L Re: Pravidlá pre vytvorenie zahájení 23.3.2010 08:42 Jan Němec




Příspívat do diskuze mohou pouze registrovaní uživatelé.
> Vyhledávání software
> Vyhledávání článků

15.5.2017 23:50 /František Kučera

Máš rád svobodný software a hardware nebo se o nich chceš něco dozvědět? Zajímá tě DIY, CNC, SDR nebo morseovka? Přijď na sraz spolku OpenAlt, který se bude konat ve čtvrtek 18. května od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5).


Přidat komentář

12.5.2017 16:42 /Honza Javorek
PyCon CZ, česká konference o programovacím jazyce Python, se po dvou úspěšných ročnících v Brně bude letos konat v Praze, a to 8. až 10. června. Na konferenci letos zavítá např. i Armin Ronacher, známý především jako autor frameworku Flask, šablon Jinja2/Twig, a dalších projektů. Těšit se můžete na přednášky o datové analytice, tvorbě webu, testování, tvorbě API, učení a mentorování programování, přednášky o rozvoji komunity, o použití Pythonu ve vědě nebo k ovládání nejrůznějších zařízení (MicroPython). Na vlastní prsty si můžete na workshopech vyzkoušet postavit Pythonem ovládaného robota, naučit se učit šestileté děti programovat, efektivně testovat nebo si v Pythonu pohrát s kartografickým materiálem. Kupujte lístky, dokud jsou.
Přidat komentář

2.5.2017 9:20 /Eva Rázgová
Putovní konference československé Drupal komunity "DrupalCamp Československo" se tentokrát koná 27. 5.2017 na VUT FIT v Brně. Můžete načerpat a vyměnit si zkušenosti z oblasti Drupalu 7 a 8, UX, SEO, managementu týmového vývoje, využití Dockeru pro Drupal a dalších. Vítáni jsou nováčci i experti. Akci pořádají Slovenská Drupal Asociácia a česká Asociace pro Drupal. Registrace na webu .
Přidat komentář

1.5.2017 20:31 /Pavel `Goldenfish' Kysilka
PR: 25.5.2017 proběhne v Praze konference na téma Firemní informační systémy. Hlavními tématy jsou: Informační systémy s vlastní inteligencí, efektivní práce s dokumenty, mobilní přístup k datům nebo využívání cloudu.
Přidat komentář

15.4.2017 15:20 /František Kučera
Máš rád svobodný software a hardware nebo se o nich chceš něco dozvědět? Zajímá tě IoT a radiokomunikace? Přijď na sraz spolku OpenAlt, který se bude konat ve středu 19. dubna od 18:30 v Šenkovně (Sokolská 60, Praha 2).
Přidat komentář

5.3.2017 19:12 /Redakce Linuxsoft.cz
PR: 23. března proběhne v Praze konferenci na téma Cloud computing v praxi. Hlavními tématy jsou: Nejžhavější trendy v oblasti cloudu a cloudových řešení, Moderní cloudové služby, Infrastruktura současných cloudů, Efektivní využití cloudu, Nástrahy cloudových řešení a jak se jim vyhnout.
Přidat komentář

27.2.2017 22:12 /František Kučera
Pozvánka na 137. sraz OpenAlt – Praha: Tentokrát jsme si pro vás připravili neobvyklou akci. Ve středu 1.3. v 17:30 nás přivítá sdružení CZ.NIC ve svých prostorách v Milešovské ulici číslo 5 na Praze 3, kde si pro nás připravili krátkou prezentaci jejich činnosti. Následně navštívíme jejich datacentrum pod Žižkovskou věží. Provedou nás prostory, které jsou běžnému smrtelníkovi nedostupné!
Po ukončení prohlídky se všchni odebereme do hostince U vodoucha, Jagelonská 21, Praha 3 pochutnat si na některém z vybraných piv či dát si něco na zub. Rezervaci máme od 19:30, heslo je OpenAlt.
Ale pozor! Do prostor datového centra máme omezený přístup, dostane se tam pouze 10 lidí! Takže kdo přijde dříve, ten má přednost, a občanky s sebou! Kdo nebude chtít na prohlídku datového centra, může se pomalu přesunout do hostince U vodoucha a u nepřeberné nabídky piv počkat na ostatní.
Přidat komentář

18.1.2017 0:49 /František Kučera
Členové a příznivci spolku OpenAlt se pravidelně schází v Praze a Brně. Fotky z pražských srazů za uplynulý rok si můžete prohlédnout na stránkách spolku. Příští sraz se koná už 19. ledna – tentokrát je tématem ergonomie ovládání počítače – tzn. klávesnice, myši a další zařízení. Také budete mít příležitost si prohlédnout pražský hackerspace Brmlab.
Přidat komentář

   Více ...   Přidat zprávičku

> Poslední diskuze

11.5.2017 23:32 / lelo
Re: Problém se správcem balíčků

11.5.2017 5:45 / davd mašek
Re: Problém se správcem balíčků

10.5.2017 22:54 / lelo
Re: Problém se správcem balíčků

10.5.2017 22:19 / davd mašek
Problém se správcem balíčků

17.4.2017 19:15 / Jakub shoop
chyba

Více ...

ISSN 1801-3805 | Provozovatel: Pavel Kysilka, IČ: 72868490 (2003-2017) | mail at linuxsoft dot cz | Design: www.megadesign.cz | Textová verze