Databáze koncovek a studie

Emil Vlasák

Článek o databázích koncovek ve studii (ČŠ 8 a 11/95) vyvolal svého času slušnou odezvu. Mezitím obor citelně pokročil, proto jsem připravil po pěti letech volné pokračování.

„Technologická“ část článku popisuje existující databáze, jejich vlastnosti, názvosloví a provozní zkušenosti. Druhá část je věnována právním otázkám spojeným s publikací a vyznamenáváním „databázových“ studií.

Základní pojmy a údaje

Databáze koncovek je rozsáhlý počítačový soubor, který pro určitou konstelaci materiálu (např. DPxD) obsahuje všechny možné pozice s jejich hodnocením a délkou nejrychlejšího řešení. S vhodným softwarem je pak možné takové koncovky bezchybně rozehrávat a analyzovat. Donedávna byly databáze omezeny na konstelace s pěti kameny (včetně králů), poslední rok je už možné bezchybně posoudit i  šestikamenáče mnoha typů.

První uživatelsky dostupnou databází byly 3 díly Thompsonova CD, později doplněné ještě méně zajímavým dílem čtvrtým. V době svého vzniku kolem roku 1991 znamenala publikace takového množství dat malý zázrak. Thompson komprimoval data účinnou Huffmannovou metodou, která je však velmi náročná na čtení a dekódování. Je proto myslitelná jediná metoda použití – pozice stojí na šachovnici a po spuštění dotazu se chvíli čeká na CD.

Herní šachové programy však potřebují databáze „konzultovat“ i dynamicky během propočtu. První program s touto vlastností byl MChess 6.0 (1996), který využíval takzvané tablebase. Tablebase byly vyvinuty nezávisle na Thompsonovi a jejich autor Edwards je nabízel volně na internetu. Velikost souborů však je neúnosná. Krátce nato se do hry vložil programátor Microsoftu Nalimov, který nalezl velmi přijatelnou metodu komprese tablebasí s možností rychlého dekódování. Jde o rozumný kompromis, který se zřejmě nadlouho stane standardem. Tabulka ukazuje typické velikosti souborů pro konstelaci bez pěšce a s jedním pěšcem.

Pěšci omezují symetrie, proto jsou nároky podstatně vyšší. To je také hlavní důvod, proč Thompson nemá konstelace s více pěšci.

Nalimov pokračuje v politice svého předchůdce a na internetu nabízí vedle tablebasí i program k jejich generování. Stahování ani generování však není pro normálního uživatele časově přijatelné. Proto lze tablebase také zakoupit. Steinwender EDV nabízí předinstalovaný pevný disk, ChessBase výběr na 4 CD („Endspielturbo“) a několik dodavatelů pak kompletní tablebase na 10 - 12 CD včetně zajímavých konstelací s více pěšci. Několik základních konstelací dostanete také na CD s herními programy ChessBase.

Určitý pokrok vnesl do oboru Dr. Donninger, který se svým programem Nimzo 7.32 (konec 1999) dodal databázi šestikamenových pěšcovek 2Px2P ovšem jen pro blokované pěšce.

Prestižní studiový časopis EG se snaží zavést pro databáze koncovek obecný termín odb (oracle - tedy znalostní - database), ale zřejmě nebude úspěšný. V PC–šachu se totiž dávno ustálilo pojmenování Thompson a rovnoměrně frekventované Nalimov či tablebase.

Co však si zapamatujte jsou zkratky DTC a DTM (distance to conversion/mate) pro takzvanou metriku databáze. Lidově řečeno jde o způsob, jak databáze pojímá délku řešení. DTC databáze (Thompson) udává počet tahů k vítězné materiální konverzi (to je do zisku figury nebo proměny pěšce), zatímco DTM databáze (Nalimov) obsahuje přímo počet tahů do matu. K praktickým důsledkům se ještě vrátím.

První pokusy s šestikamenáči prováděl Stiller už v roce 1991 (ČŠ 2/97). Jeho Connection Machine měla 64k procesorů (!!) a obrovskou paměť RAM, kam bylo možno analýzy dočasně uložit. Kapacita disků však nedovolila uložit databáze trvale. Proto mají výsledky spíš statistický charakter a nejzajímavějším výstupem je několik rekordních pozic. V poslední době byly pod vlivem Elkiese pokusy obnoveny.

První použitelné šestikamenové tablebase byly vygenerovány Nalimovovým programem a umístěny na internetu. Délky jsou však na mezi použitelnosti, například běžná databáze normální konstelace VVxVJ zabere dvě CD. Stahovat taková data je myslitelné jen výjimečně – například kvůli nějaké zvlášť zajímavé studii.

Aktivní je opět Thompson, který šestikamenáče sliboval několik let. Na jeho internetové stránce rychle přibývají nové databáze se skvělou koncepcí. Není totiž nutné je stahovat – stačí si poslat „dotaz“ na konkrétní pozici a serverový program obratem odpoví její hodnocení. To je dnes nejlepší a vlastně jediná přijatelná možnost jak se šestikamenáči pracovat.

Software

Pro efektivní práci s databázemi je důležitý nadstavbový software. Samotná dotazovací schopnost nestačí, jde také o ukládání výsledků, pohodlí práce a dokonce integraci s herními motory.

Thomsonovy databáze se nejčastěji volají z ChessBase od verze 6, která je také uvažována v následujících praktických pasážích.

Možné je ale také použití Genia 6.5 nebo programu Shredder. Posledně jmenovaný má Thomsonova CD přímo v dodávce a disponuje výjimečnou luxusní funkcí „žolíkové“ analýzy, která vyrobí očíslovaný diagram v závislosti na volné poloze jednoho z kamenů. Rodina programů Fritz 6 Thompsonovy disky nepodporuje. Z DOSových programů je použitelná TASCBase,  starší specializované programy ChessBase a holandský ChessLat, který je dokonce zadarmo.

Nalimovovy databáze nepotřebují specializovaný prohlížeč, protože jeho roli zastane přímo herní motor. Hiarcs 7.32 indikuje jen jednu variantu, lepší je proto Fritz 6, Junior 6 nebo Nimzo 7.32 (a samozřejmě novější). Tyto motory je možné spouštět z herního rozhraní rodiny Fritze nebo opět z ChessBase, která má navíc i specializovaný motor pro Tablebase. Příjemný je také Shredder od verze 4, který tedy – jako ChessBase – podporuje oba formáty.

 Globální posouzení databází

Databáze spolu s uvedeným softwarem otestují jednotlivá postavení, počítač by však měl dokázat víc. Milióny pozic na disku přímo svádějí ke statistickému zpracování a dalším zajímavým hříčkám.

Už Thompson uveřejnil před lety pro různé pětikamenáče údaj, v kolika procentech je silnější strana vyhraje. Zajímá-li vás podobná statistika šestikamenových konstelací, navštivte stránku http://cm.bell-labs.com/cm/cs/who/ken/chesseg.html. Související pojem  generální výhry probereme v dalším odstavci.

Stiller 1992, výhra v 72 tazích

Thompson a Stiller nechali také pro různé konstelace vyhledat rekordní pozice s nejdelším řešením. Diagram D1 ukazuje jeden takový příklad. 72 tahové řešení nemůžeme z prostorových důvodů přetisknout a najdete ho na servisní disketě. Věže pětkrát stísní černého krále, který vždy rutinně vyvázne. A najednou je tu změna, jezdec stojí trochu hůř, bílý král trochu blíž … a je rozhodnuto!  Pochopit nuance a princip vyhrávajícího plánu lidskou hlavou je na mezi možností. V této souvislosti se mluví o obskurním řešení. Zda může taková varianta – i kdyby byla jednoznačná – být součástí řešení studie, je spornou záležitostí.

Rekordní pozice také dokazují, že v některých případech by bylo potřeba upravit 50 tahové pravidlo až na několik set tahů.

Je možné napsat software, který v databázích vyhledá všechny vzájemné zugzwangy. To je specialita Dána Rasmussena, jehož výpisy vycházejí v poslední době jako tištěná příloha časopisu EG. Jako námět jsou využívány mnohými skladateli. Typicky „databázovou“ byla nedávno rozhodnutá argentinská soutěž k 75. narozeninám Foguelmana, Caputta a Carlssona, kde se na Rasmussena odvolávala 1. a 3. cena.

S. Tkačenko

75 Jubilee of FCC 2000, 1. cena

remíza

1.e7+ 1.c8D? Df5+! . 1...Kb2 2.e8D Jxe8 3.Sxe8 De6 4.Sa4!! Ka3 5.Sb5! Vzájemný zugzwang, proto musel střelec hrát přesně. 5…Kb3 6.Sa6 Dd6 7.Sc4+.

Stiller, vzájemný zugzwang

Pěkný příklad počítačového vzájemného zugzwangu vidíme na diagramu D3. Bílý nemůže vyhrát 1. De5 Dc7!, ale při tahu černého už vyjde 1…Vb8 2.De5!.

N. Elkies

American Chess Journal, 1993

bílý vyhraje

1.Dg7+ 1.Dd6+ Kxg2 2.f8D Dh3+ 3.Kg5 De3+. 1...Kh2 2.f8D 2.De5+ Kxg2 3.f8D Dh3+ 4.Kg5 b1D. 2...Db5+ 2...b1D 3.Df4+ Kg1 4.Se4+. 3.Kh6 3.Kg4 Sf5+! 4.Kf4 Dc4+. 3...Db6+ 4.Sc6!! 4.Kxh7? b1D+ 5.Kh8 Db8!. 4...Dxc6+ 5.Kxh7 b1D+ 6.Kh8 Černý už nemá šach. 6...Kh1 7.Dfg8!!. Tato studie je poněkud dřívějšího data a závěrečný zugzwang exotického materiálu DDxDD pochází od Stillera. 

Technicky by dokonce nebyl problém napsat software, který v databázích vyhledá pozice s dlouhou jednoznačnou cestou. Pokud je mi známo, takové strojové skládání zatím nikoho nezlákalo.

 Generální výhra?

Důležitou charakteristikou bezpěšcových koncovek je generální výsledek. Pro hráče i skladatele je užitečné vědět, že SSxS je remíza, zatímco SSxJ generální výhra. Umí-li počítač bezpečně ocenit každou pozici nějaké konstelace, zdánlivě by neměl být problém stanovit automaticky i obecné pravidlo. Kupodivu to problém je – a velký!

Hned na počátku výzkumů se ukázalo, že  Thompsonovy procentní údaje nejsou dostatečným vodítkem.  DxJJ vyhraje v 89,7 procentech případů, přesto je konstelace teoretickou remízou. Vysvětlení je snadné. Při náhodném postavení kamenů je velmi pravděpodobné, že dáma začne „řádit“. Teorii ale zajímají právě jen konsolidované pozice, kdy řádit nezačne. A je známo, že  dva jezdci vedle sebe (třeba d3e3) – byť statickou pevnost nevytvářejí – dynamickým manévrováním remízu udrží.

Největším problémem je ovšem málo jasná definice generálního výsledku. Konstelace DxSJ je označována jako generální výhra. Takové tvrzení je prakticky užitečné, ale  exaktně vzato neplatí pro pevnost Karstedta (Ka1 Sb2 Jd4).  Lidský jazyk tvoří běžně takové příjemné a metodické – byť ne zcela přesné – formulace. Proto na slovním metodickém hodnocení nových šestikamenových konstelací bude muset spolupracovat člověk.

Metoda této spolupráce se dosud hledá. V EG 124 se celou věcí obsáhle zabývali Beasley a Roycroft. Zajímavá myšlenka je tato: Vedle rekordních pozic s nejdelší výhrou (které se generují a tisknou s oblibou) vygenerovat také rekordní pozice s nejdelší remízou. Ty mohou člověku mnohé objasnit. Jednoznačnost variant totiž vypovídá o tom, zda jde o náhodnou forsírovanou remízu nebo obrannou možnost hlubší povahy. Na konci takových variant se také objeví výjimečné poziční remízy typu Karstedta.

Takové úvahy však zůstaly zřejmě jen na verbální úrovni a nové poznatky se zatím získávají jednoduššími cestami. Například konstelace JJJxS  je pravděpodobně generálně vyhraná. Jako „důkaz“ však slouží jediná pozice diagramu D5  s rozhozenými silami bílého. Vypadá to opravdu logicky – pokud vyhraje bílý tuto pozici, měl by vyhrát vše. Vzhledem k délce najdete řešení opět na servisní disketě.

Stiller

bílý vyhraje v 91 tazích

Metrika a problémy s duály

J. Pospíšil 1982

závěr studie

Hned v začátcích používání databází se objevily potíže s interpretací DTC metriky Thompsonových databází. Uživatel dostává informaci o délce k vítězné konverzi, ta ale v případě proměny pěšce nemá valnou hodnotu. Znovu se vracím ke studii J. Pospíšila (diagram D6??), kde vedle antipatového řešení 1.e8V!! indikují databáze také výhru po 1.Dc4. „Nejsilnější“ obrany 1…Dh8+ (DTC=7) 2.Kf7 a 1…Df6+ (DTC=10) 2.Ke8 vedou ke komplikované výhře bez slabé proměny, což by znamenalo duál. V korespondenčním šachu bych skutečně asi 1…Df6+!? zahrál jako nejlepší praktickou šanci (k tomu se ještě vrátím), ale logika studie vyžaduje bezesporu jiný pohled. Tah 1…Df5+! (DTC „jen“ 6) zabraňuje pokračování 2.Ke8? a dokazuje  bílému, že se po 2.Df7! De5 musí vrátit k hlavní myšlence studie. 1.Dc4 není tedy vážným duálem, ale jen neškodnou ztrátou času.

DTC údaje tedy kritickou obranu 1…Df5+ neodhalí. Dnes už je možné získat hodnoty DTM z Nalimova, které na správnou cestu navedou lépe: 1…Dh8+ (DTM=15), 1…Df6+ (DTM=19) a 1…Df5+ (DTM=19).

Obecně lze říci, že přes velkou sílu databází není známa jednoduchá možnost, jak strojově rozlišit skutečný duál od zamaskovaného cyklu. Je třeba prostě analyzovat. Praxe ukazuje, že DTM údaje bývají jako vodítko cennější.

Existuje však případ, kdy je použití DTC nezbytné. V korespondenčním šachu se může stát, že optimální hra na nejrychlejší mat podle DTM povede k remíze 50 tahovým pravidlem, zatímco DTC nalezne vyhrávající postup s dostatečně rychlou konverzí.

Získání správné hodnoty DTM není v současné době zcela bez problémů. Nalimovovy soubory jsou pravděpodobně v pořádku, ale jejich rychlá implementace do prvních verzí herních motorů se neobešla bez dětských nemocí. Tak v Pospíšilově studii ukazují motory správný tah 1.e8V, ale Hiarcs 7.32 a Nimzo 7.32 indikuje DTM=19,  Fritz a TableBase DTM=18 a  Junior 6 dokonce tablebase z nějakých důvodů nepoužije vůbec.

 Cykly v Nalimovovi

Vraťme se ještě jednou k Pospíšilově studii a zkoumejme 1.Dc4 Df6+!?. Výhra je dost komplikovaná a vyžaduje pečlivou přípravu postupu pěšce: 2.Ke8 Dd6 3.Dh4+! Kg6! 4.Kf8 Kf5 5.Dh5+ Ke4 6.Dg4+ Ke3 7.Kf7 Dc7 8.Db4 Kd3 9.Kf8 DTM=12 9…De5.

Nyní se může stát, že motory (včetně specializovaného modulu TableBase) se zacyklí a navrhují donekonečna 10.Db3+ DTM=13 10…Kd2 11.Db4+ DTM=12 11…Kd3 12.Db3+ DTM=13 atd.. Nasadíte-li motor jako herní program ve vážném turnaji, dokonce tímto způsobem partii zremizuje, což může být tragédie. Vysvětlení je přitom jednoduché. Na disku chybí databáze DDxD a motor se proto nemůže odhodlat ke správnému tahu 10.e8D!, kterým opouští „pohodlné“ území tabulkou garantované výhry a jde „jen“ do velké výhody. Řešení je dnes možné jen metodou hrubé síly – používat tablebase zkopírované na disk v kompletní podobě. Proto není zmíněný výběr EndspielTurbo jinak renomované firmy vhodným řešením.

Použití nesprávné databáze

Klasickým stále se opakujícím omylem při práci s  Thompsonovými databázemi je volba nesprávného souboru a následná chybná interpretace výsledku.

Databáze jsou konstruovány pro silnější stranu, která je ve jménu souboru uvedena jako první. „Nulový“ výsledek pouze znamená, že silnější strana nevyhraje. Člověk to automaticky interpretuje jako remízu, což může být nesprávné. Nunnova kniha „Secrets of Rook Endings“, deklarující v úvodu bezchybnost, obsahuje poučný omyl tohoto typu. Pozice Ka8 Vg2 Pa7 – Kc7 Vh4 je označena za remis při tahu obou stran, ve skutečnosti černý okamžitě matí. Kdyby Nunn psal knihu bez počítače, těžko by takovou věc přehlédl.

D. Gurgenidze 1992

bílý vyhraje

Proberme tuto důležitou záležitost podrobněji. Diagram D7 ukazuje velmi zajímavou studii s řešením 1.Vaa7 Kg8 1...Dg8 2.Vf7. 2.Vg7+ Kf8 3.Vgd7! Kg8 4.Vab7! Df8+ 4...Kf8 5.Vh7. 5.Ke1! 5.Ke2? De8+ 6.Ve7 Dh5+, 5.Kg2? Kh8 6.Vh7+ Kg8 7.Vhe7 Kh8 8.Vbc7 Dg7+!.  5...Kh8 6.Vh7+ Kg8 7.Vhe7! Kh8 8.Vbc7! Kg8 9.Ke2! Kh8 10.Vf7 De8+ 11.Kf2 Kg8 12.Vg7+ Kf8 13.Vh7 Kg8 14.Vcg7+ Kf8 15.Vh8+.

Nastavím v ChessBasi výchozí pozici a vyvolám databázový motor. Program si řekne o CD 1 nebo 2, založím tedy jedničku, která je víc po ruce. Po chvíli se objeví odpověď jako řada tahů hodnocených 0. Redakce odborných časopisů jsou poslední dobou bombardovány falešnými hláškami o „počítačově ověřené“ neřešitelnosti tohoto typu. Výpis disků však hovoří jasně. První CD obsahuje soubor Q_RR a nulové hodnocení znamená jen to, že ve výchozí pozici dáma nevyhraje. Je třeba použít soubor RR_Q (tedy druhé CD) se a vše rázem začne fungovat. Bohužel svůj podíl má i nedbale napsané rozhraní, které uživateli volbu CD nijak neulehčí.

M. Karstedt 1911

bílý vyhraje

Karstedtova studie má řešení 1.c7 Vh8 2.Jd8 Vh6+ 3.Kb5 Vh5+ 4.Kb4 Vh4+ 5.Kb3 Vh3+ 6.Kc2 Vh2+ 7.Kd3 Vh3+ 8.Kd4 Vh4+ 9.Kd5 Vh5+ 10.Kd6 Vh6+ 11.Ke7 Vh7+ 12.Jf7. ChessBase žádá natvrdo disk 3, který však obsahuje pouze databázi R_NP a dává falešný výsledek. Soubor NP_R Thompsonovy disky bohužel neobsahují a studii proto není možné vůbec přezkoušet.

ChessBase má ještě jeden příbuzný problém. Zasuneme-li úplně jiné CD, pak místo chybového hlášení dává také nulové hodnocení. Tento stav občas nastane i s pomalou CD mechanikou, kde je sice zasunut správný disk, ale příliš pomalu se rozbíhá. Pak je třeba krokovat o tah vpřed a zpět, aby se objevil správný výsledek.

Genius 6.5 a Shredder 4 mají výběr disku ošetřen pečlivěji včetně dotazu, která strana vlastně hraje na výhru.

Chyby v databázích

I když většina zatím popsaných omylů je dána neodborným použitím, můžeme překvapivě narazit i na chyby ve vlastních databázích. Jsou známy dvě.

K. Husák 1995 závěr studie

černý na tahu, bílý vyhraje

Čtvrté Thompsonovo CD bylo vydáno dodatečně a jeho užitná hodnota je nižší než u předchozích dílů. Jedna z nejzajímavějších databází DxJP je chybná, jak ukazuje diagram D9 s řešením 1...Jd2+ 2.Kd3 c1D 3.Dh4+. Až do proměny hlásí Thompson remis!

A. Selezněv 1921

bílý vyhraje

Druhý problém je spojen s rošádou, kterou Thompson ani Nalimov v koncovkách neuvažují. Občas to však může vadit, jako třeba v diagramu D10. Databáze hlásí svorně remízu, ale výhra existuje:

1.d7 Kc7 2.d8D+!! Kxd8 3.0-0-0+.

Databáze a studiová legislativa

V citovaném článku jsem také předpověděl, že rozvoj databází povede k nutnosti legislativních úprav pro publikování a posuzování studií s databázovým materiálem. I když tehdejší reakce byly výrazně odmítavé, čas pomalu uzrává k řešení tohoto problému.

Článek proto uzavírám volným překladem dokumentu „Poučení pro pořadatele, skladatele a rozhodčí“, který na WCCC Netanya v říjnu 1999 podepsalo 6 členů studiové subkomise: Y. Afek, H. Aloni, O. Comay, G. Costeff, D. Gurgenidze, N. Kralin a J. Roycroft, podepsat odmítl N. Elkies.

čl. 0. Definice. Autoři zde poněkud chaotickým způsobem definují základní pojmy z oboru databází koncovek. Vzhledem k předchozímu obsahu článku si dovoluji vynechat.

čl. 1. Rozhodčí a redaktoři jsou v současné době postaveni před obtížný úkol rozlišit tradičně komponovanou „maljutku“ (studii s pěti kameny) od studií extrahovaných z databází.

čl. 2. Schopnost extrahovat „studie“ z databází (to je nalézt zde pozice s jednoznačnou sérií tahů) se liší od schopností potřebných k tradičnímu skládání jako je talent, kreativita, technika a vytrvalost.

čl. 3. Subkomise předkládá dva principy:

3.1 Tradiční a databázové studie by se neměly účastnit týchž soutěží.

3.2 Používání počítače je však vhodné. Může asistovat při testech korektnosti a je také zdrojem idejí.

čl. 4. Subkomise proto doporučuje:

4.1 Používat databáze pro testování korektnosti.

4.2 Použití databázového výstupu jako hlavní varianty řešení je přijatelné jen tehdy, má-li výchozí pozice aspoň o jeden kámen víc než je maximální velikost databází, které jsou toho času na trhu.

4.3 Obskurní varianty v řešení musí být doprovozeny slovním vysvětlením, co se v pozici děje. Toto vysvětlení musí být pro rozhodčího srozumitelné.

4.4 Pro „databázové“ studie by měly být organizovány zvláštní soutěže.

4.5 Rozhodčí studiových soutěží by se měli seznamovat s databázovou technologií a s aktuální dostupností databází.