Šachová koncovka

Bílý je na tahu a máme zjistit, zda může dát protivníkovi mat během předepsaného počtu tahů. Takto formulovaná úloha je příliš náročná pro jednoduchou implementaci, proto zavedeme některá zjednodušení.

Bílý může mít na začátku kromě krále nejvýše dvě další figury, věž a/nebo pěšce. Černý může mít kromě krále nejvýše jednu další figuru a tou je věž. Celkem tedy výchozí počet figur včetně obou králů je nejméně dvě a nejvýše pět.
Pokud bílý pěšec dorazí do poslední řady, budeme jej proměňovat pouze v dámu nebo jezdce. Dáma má kapacitu věže i střelce, takže každou tuto figuru v drtivé většině situací nahradí.
Celá hra se bude odehrávat na zmenšené šachovnici o rozměru 7x7 polí. Protože budeme pracovat pouze s koncovkou a nejvýše pěti figurami, odpadá otázka, kolik jezdců nebo střelců a jaké barvy hra obsahuje apod. Pro zmenšenou šachovnici zavedme formálně pravidlo, že pěšec při svém prvním tahu ze základního postavení ve druhé řadě může táhnout jen o jedno pole kupředu. Toto pravidlo není kritické, všechny případy, které budeme zkoumat dopadnou stejně bez něj i s ním. Kromě uvedených změn bude vše probíhat zcela identicky tak, jako by šlo o běžnou šachovnici s 8x8 poli.
Žádný hráč již nebude ve zkoumané koncovce dělat rošádu, předpokládáme, že ji udělal již dříve nebo si ji znemožnil pohybem zúčastněných figur.
Nebudeme brát ohled na pravidlo remízy, které říká, že remíza nastává, pokud se potřetí na šachovnici objeví identická situace. Stejně tak nebudeme aplikovat pravidlo remízy po 50 tazích bez braní a pohybu pěšce, protože do takové hloubky nebudeme hru zkoumat.
Dostatečná materiální převaha v běžné hře je zárukou výhry. Pokud jeden hráč v určitém okamžiku převahu získá, bývá lidským účastníkům zřejmé, zda si ji při bezchybném hraní dokáže udržet a tedy i vyhrát. Při pevně omezeném počtu tahů, které budeme mít k dispozici, se však udržitelnost materiální i poziční převahy nesnadno zkoumá, proto partii nebudeme považovat za vyhranou, dokud skutečně nenastane mat.

Kromě uvedených úprav budeme dodržovat běžná šachová pravidla a zvyklosti, kompletní pravidla šachu lze nalézt v prvním odkazu na konci tohoto dokumentu. Figury v zadané výchozí a každé další pozici mohou být rozmístěny na šachovnici zcela libovolně v souladu s pravidly šachové hry, králové nesmějí stát vedle sebe (ani diagonálně) a bílý pěšec nesmí stát v první nebo poslední řadě. Budeme vždy předpokládat, že oba hráči hrají optimálně, to jest budeme fakticky zjišťovat, zda si bílý může mat vynutit, ať už hraje černý jakkoli.

Když zkoumáme zadanou pozici do pouze určité hloubky (= počtu tahů), zdálo by se, že nelze nijak zjistit, jak se bude hra vyvíjet v pozdějších tazích. Kupodivu, v některých případech je možné nahlédnout "za horizont" předepsaného počtu tahů a učinit si tak představu o dalším průběhu hry. Předpokládejme kupříkladu, že zkoumáme hru do hloubky tří tahů bílého. Po prvním tahu bílého se dostaneme do určité situace, jejíž důsledky až do dané hloubky prozkoumáme. Po jiném zahajujícím tahu bílého se hra vyvíjí jinak, ale dostane se do stejné situace po jeho třetím tahu. V tomto okamžiku však máme k dispozici výsledek předchozí analýzy a můžeme tak vlastně určit průběh hry v dané větvi herního stromu až do hloubky 5. Abychom sjednotili různé přístupy jednotlivých řešitelů, zavedeme ? poněkud proti duchu analýzy hry ? poslední omezení: Při zkoumání zadané pozice se striktně omezíme na tahy před horizontem a budeme se tvářit, že žádné tahy za horizontem vůbec neexistují, to jest, nevyužijeme možnost nahlížení za horizont popsanou výše.

Vstup

Vstupem je textový soubor se dvěma řádky. Na prvním řádku jsou zapsány s pomocí české varianty algebraické notace pozice všech figur, jednotlivé figury jsou odděleny mezerou. Pořadí figur, pokud jsou ve hře, je bílý král, bílá věž, bílý pěšec, černý král, černá věž. Předpokládáme, že je to korektní pozice podle pravidel a není nutno to ověřovat. Na druhém řádku je jediné číslo udávající, na kolik tahů bílého máme danou pozici kompletně prozkoumat. Např. číslo 3 znamená, že potáhne bílý, černý, bílý, černý, bílý, odpověď černého na poslední tah bílého již zkoumat nebudeme, pokud však dá bílý svým třetím tahem mat, budeme to registrovat.

Výstup

Výstupem je textová informace na jediném řádku.
1. Pokud bílý dokáže dát mat v předepsaném nebo menším počtu svých tahů, bude výstup obsahovat nejprve řetězec 1-0 a dále za mezerou seznam veškerých počátečních tahů bílého, které k matu vedou. Někdy může bílý dát mat více způsoby a to i na různý počet svých tahů, v takovém případě je nutno uvést všechny počáteční tahy bílého, po nichž si může mat nějakým způsobem vynutit.
2. Pokud bílý v předepsaném počtu tahů nedokáže rozhodnout hru ve svůj prospěch, vystoupí pouze řetězec "Nevyhraje". Sem spadají i případy, kdy si dokáže černý vynutit remízu nebo vlastní vítězství.
Formát seznamu počátečních tahů bílého je [tah] [mezera] [tah] [mezera] [tah] ... Za posledním tahem mezera být může i nemusí. Na pořadí tahů v seznamu nezáleží. Veškeré tahy používají českou variantu algebraické notace (viz odkazy níže) s následujícím omezením: Jeden tah dané figury je zaznamenán jako identifikace figury následovaná souřadnicemi pole, na které táhne, u pěšce se identifikace figury nepíše. Nebudeme používat ani symbol pro braní figury "x" ani symbol pro šach "+" ani v případě proměny pěšce v jinou figuru nebudeme indikovat, v jakou se promění.

Příklad

Vstup

Kc5 Vf3 a6 Kc7
2

Výstup

1-0 a7 Vf7 Vf6 Ve3

V prvním případě při proměně pěšce v dámu a ve druhém případě je mat okamžitý, ve zbylých dvou případech může černý král reagovat jedině Kd7, poté ale bílý buď postupem pěšce a proměnou v dámu nebo tahem věže na poslední řadu dává mat.

Řešené příklady podobné ostrým

Download (ulož na disk)

Příklady by měly být dostatečně návodné, od ostrých se většinou odlišují velmi málo, co se pozice týče. Počet tahů, které je nutno prozkoumat v každém ukázkovém příkladu, je srovnatelný nebo menší než počet tahů v korespondující ostré úloze.

Zdroje pro další přehled:
http://en.wikipedia.org/wiki/Rules_of_chess
http://en.wikipedia.org/wiki/Algebraic_chess_notation
http://chessprogramming.wikispaces.com/