LINUXSOFT.cz Přeskoč levou lištu

ARCHIV



   

> Š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 13895×

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ů

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ář

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

> Poslední diskuze

31.7.2023 14:13 / Linda Graham
iPhone Services

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?

Více ...

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