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 | přečteno 13500×
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.
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:
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%)
| 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.