Algorithms and methods of chess programming, part of "Between chessboard and computer", Vaclav Kotesovec, 1996
(Mezi šachovnicí a počítačem, str.255-272, Václav Kotěšovec, 1996)Redukční algoritmus řeší úlohy metodou vyhledávání matových obrazců. Jádro redukčního algoritmu dodá nalezené obrazce (nejsou to obrazce v klasickém slova smyslu, ale jakési kostry obrazců). Ve fázi optimalizace se zjišťuje, zda tyto obrazce mohou nastat a dochází k vytřídění jen některých obrazců z původních. Ve další fázi se běhově zkoumá, zda jsou možné konkrétní cesty z počáteční pozice do těchto obrazců. V případě úspěšnosti je nalezeno řešení.
Také by byl možný opačný postup, kdy by se nejprve běhově prováděly tahy a po každém tahu by byl volán redukční algoritmus s modifikovaným počtem možných tahů. Experimenty však ukázaly, že tímto vnořením obou cyklů by bylo dosaženo podstatně horších časů řešení. Vyjímku by mohly tvořit pouze velmi zablokované pozice (nebo pozice hrozící patem) se skrytými možnostmi proměn bílých pěšců, kdy by bylo výhodnější nejprve pozici rozplést a až následně použít redukční algoritmus s menším počtem tahů.
Redukční algoritmus hledá obrazce na základě masek (tabulek možností pokrytí matové sítě) příslušejících jednotlivým typům kamenů. Obrazec odpovídá skupině kamenů, kdy jde o šach a všechna pole kolem černého krále jsou kryta bílými kameny nebo blokována černými kameny (nutná podmínka pro mat). Z celkového počtu bílých a černých kamenů v pozici úlohy jsou v konkrétním obrazci obsaženy jen některé, které se obrazce aktivně účastní. Tyto kameny nazýváme zúčastněné kameny. Zbývající kameny, které se na obrazci nepodílejí, nazýváme nezúčastněné kameny.
Na základě tabulek dostupnosti polí se provede statický (jednoúrovňový) odhad počtu tahů bílého a černého nezbytných pro dosažení obrazce. Tímto sítem neprojdou obrazce, kterých není možno dosáhnout v počtu tahů, které jsou k dispozici. Celkový počet tahů, které jsou k dispozici, je dán výzvou úlohy. Odečteme-li od celkového počtu tahů počet nutných tahů k dosažení obrazce, dostáváme počet stupňů volnosti (bílého a černého) pro daný obrazec.
Stupně volnosti představují rezervní tahy, které zbývají oběma stranám k např. tempovým tahům, vzájemným vyhnutím se kamenů, různým manévrům, odvázáním apod. Pokud je úloha korektní, je tento počet v průběhu řešení jednoznačně vyčerpán.
Z jádra redukčního algoritmu dostanu “něco, co by mohl být matový obrazec”.
Pro každý obrazec nejprve zjistím násobnost šachu. Bodový šach může být maximálně jeden. Pokud je počet šachů větší nebo roven než 2, nelze většinu dalších optimalizací použít. Nemusí jít jen o dvojité šachy. Jelikož jádro redukčního algoritmu “nevidí přes linie”, může být tento počet šachů i větší než 2, ale v tomto případě může jít o vazby černých kamenů. V případě jednoduchých šachů vytvořím seznam kritických polí. Kritická pole jsou pole matujícího kamene a pole na matující linii.
Ve fázi optimalizace prozkoumám soubor podmínek, které tomu mohou bránit. Tím mohou být bílé zúčastněné kameny, stojící na matové linii, černé zúčastněné kameny, které mohou bodově vstoupit do matové linie nebo na matové pole, atd. Optimalizace jsou podrobně probrány na dalších stranách včetně příkladů. Pokud obrazec projde sítem optimalizací, hledá se běhově (dynamicky) cesta z počáteční pozice do nalezeného obrazce. V této fázi sice už dochází k provádění konkrétních tahů (podobně jako při použití metody hrubé síly), jednotlivé tahy však mohou snižovat aktuální počet stupňů volnosti a pokud jsou takto dynamicky tahy některé strany již vyčerpány, všechny dále následující varianty od této úrovně už nejsou uvažovány. Ke zvýšení těchto eliminací přispívá i běhové volání některých algoritmů (algoritmus pěšců, rozpojovací algoritmus apod.)
Dva dále uvedené příklady demonstrují průběh redukčního algoritmu a parametry nalezených obrazců.
|
Kd2 |
Ja6 |
Kg2 |
Dg3 |
Sd1 |
nutných tahů bílého |
nutných tahů černého |
stupňů volnosti bílého |
stupňů volnosti černého |
|
c1 |
c2 |
a1 |
nezúčast. |
a2 |
3 |
8 |
5 |
0 |
|
1 |
2 |
6 |
- |
2 |
||||
|
a3 |
b3 |
a1 |
nezúčast. |
b1 |
5 |
8 |
3 |
0 |
|
3 |
2 |
6 |
- |
2 |
||||
|
h6 |
g6 |
h8 |
nezúčast. |
g8 |
8 |
8 |
0 |
0 |
|
4 |
4 |
6 |
- |
2 |
|
Kg3 |
Jh5 |
Kb1 |
Va4 |
Pa5 |
Pa6 |
Pd7 |
Pg5 |
nutných tahů bílého |
nutných tahů černého |
stupňů volnosti bílého |
stupňů volnosti černého |
|
g3 |
g7 |
f5 |
e4 |
e5=V |
f6=V |
g6=S |
g5 |
1 |
25 |
0 |
0 |
|
0 |
1 |
4 |
1 |
6 |
7 |
7 |
0 |
||||
|
g3 |
g7 |
f5 |
e4 |
f6=V |
e5=V |
g6=S |
g5 |
1 |
25 |
0 |
0 |
|
0 |
1 |
4 |
1 |
6 |
7 |
7 |
0 |
Další 3 příklady obrazců, vyloučených optimalizacemi se vracejí ke dvěma již analyzovaným úlohám. První z obrazců je vyloučen, protože na pole matujícího kamene (c2) působí bodově zúčastněný černý kámen. Ve druhém obrazci působí čDh2 na pole f2 nikoliv bodově, ale přes krátkou linii, tj. vzniká multiobrazec (viz dále) s nutností toho, aby na g2 stál předtím nezúčastněný kámen. Konečně třetí obrazec ze sériovotahové úlohy. Předpokládejme, že pozice čKf5, čSg6 a čPg5 jsou stejné jako v uvažované úloze, tj. že tyto kameny potřebují 4+7+0 tahů. Černému zbývá tedy ještě 14 tahů. Nyní předpokládejme, že čVa4 je v obrazci na e5 a čVf6 vznikla proměnou pěšce a6. Potřeba bylo 2+7 tahů a černému zbývá 5 tahů. Pokud by se černá dáma proměnila z pěšce a5 na poli a1, potřebovala by 6 tahů a tedy tato možnost neprošla již primární fází redukčního algoritmu. Prošla však možnost s proměnou tohoto pěšce na b1, kdy k přemístění na pole e4 je nutných právě zbývajících 5 tahů. Tento obrazec je následně vyloučen až optimalizací č.9, kdy se zjistí, že již neexistuje bílý nezúčastněný kámen (zúčastněný kámen nemůže být brán, protože ten musí být v koncové pozici!), který by mohl být sebrán na b-sloupci. Je třeba si uvědomit, že pokud by byl v počáteční pozici alespoň jeden bílý nezúčastněný kámen, mohl by tento obrazec teoreticky nastat a nelze jej vyloučit. Mohl by však být vyloučen až běhově algoritmem pěšců.
Z jádra redukčního algoritmu dostanu sadu obrazců, ze kterých však některé z principu obrazci být nemohou (šlo pouze o nutnou podmínku pro mat, nikoliv o podmínku postačující). Vhodná optimalizace může podstatně zkrátit čas řešení, když se podaří staticky některé z těchto obrazců vyloučit bez nutnosti dynamického hledání možné cesty. Provádějí se tyto optimalizace:
optimalizace odstraní obrazce, kde
V sériovotahových pomocných matech lze navíc uplatnit ještě některé specifické optimalizace.
Proberme nyní na příkladech jednotlivé optimalizace:
Pokud je bílý pěšec již na poli, z kterého má matovat (a není-li proměněn), pak tento obrazec vyloučím a to včetně případných dvojitých šachů. Např. ve schématu 1 nemůže nastat obrazec s bPc6, pokud je tento pěšec na tomto poli již v počáteční pozici.
Je-li kámen, který dává šach bodově u černého krále, pak pokud na tomto poli již stojí, musí vykonat minimálně 2 tahy. Např. bVe6 dává šach bodově čKe7 a pokud je počet stupňů volnosti bílého menší nebo roven než 1, obrazec vyloučím. Naopak bVg5 nedává šach čKg7 bodově, obrazec musím uvažovat (může jít např. o odtažný šach, kdy bílá věž zůstane na svém původním poli).
Dvojité šachy realizované bodově, je třeba eliminovat. Ve schématu 1 můžeme vyloučit obrazec s bSc3, který dává bodově šach čKb4 (společně s bJc2). Naopak, šach bVh4 není realizován bodově, obrazec je nutno uvažovat. Ve schématu 2 dávají dva jezdci b5 a c8, resp. střelec f7 a pěšec f5 bodové šachy, oba obrazce jsou vyloučeny optimalizací č.4.
Vazby je z principu algoritmu obecně třeba považovat za dvojité šachy (nelze pak použít např. optimalizaci č.2). Ve schématu 2 je čSc2 vázán a obrazec je nutno uvažovat. Též se bude uvažovat obrazec s bVh1 (čVf2 je v tomto obrazci redundantní), ale už ne jako dvojitý šach (jak byl primárně dodán red.algoritmem), ale zjistí se, že v linii matujícího kamene stojí bílý kámen (opt.č.3) a tedy nemůže jít o šach.
Nejčastější případy eliminace obrazců přináší optimalizace č.2. Např. na schématu 3 může zúčastněný černý kámen - čJa7 vstoupit na jedno ze tří kritických polí b8, c8, d8, v dalších obrazcích jsou kritická pole c2, f1 a i h6, kde je bílý král bodově napadán zúčastněným černým kamenem. Bílý král je zde evidentně též zúčastněný kámen, jinak pokud je počet stupňů volnosti bílého roven 0, je jasné, že i nezúčastněný bílý král musí zůstat na svém původním poli a je ho možno proto považovat též za zúčastněný kámen, což přináší možnost použití dalších optimalizací.
Schéma 4 představuje další možnosti kritických polí, pole matujícího kamene c1 nebo h8 nebo pole matující linie b8 a c8 nebo f2. Podstatné je, že na kritická pole mají černé zúčastněné kameny možnost bodového vstupu.
Schéma 5 znázorňuje kostry multiobrazců (vytváření multiobrazců se provádí algoritmem polí). Multiobrazec je obrazec, ve kterém na některých polích není přesně určeno, jaký zde má být kámen, jen je nutné, aby na tomto poli (polích) nějaký kámen stál. Kameny, které obstarají tuto funkci, se vyberou z možných nezúčastněných kamenů s akceptováním aktuálního počtu stupňů volnosti příslušné strany, tj. počtu tahů, který má bílý nebo černý ještě k dispozici. Např. pole b7 musí být obsazeno nějakým kamenem, aby mohl bJc7 matovat (podstatné je, že čVa7 nepůsobí na c7 bodově). Analogicky musí stát na b2 nějaký kámen, aby bílý král nebyl v šachu od čVb3.
Tyto linie se uvažují jen krátké (např. v případě pozice čVa1 ve schématu 6 se už optimalizace neprovádí). V případě dlouhých linií by totiž docházelo k neúměrné expanzi mutliobrazců, což by vedlo k velkým časovým ztrátám, takže optimalizace by spíš zdržovala, než přinášela časovou úsporu.
V případě bCe1 je nutný k šachu kámen na g1. Obrazec v pravém horním rohu vyžaduje umístění dokonce 3 nezúčastněných kamenů: na pole f8 (zamezení šachu bílému králi), g7 (aby bCh7 kryl pole f7) a g6 (aby bCh7 kryl pole f5). Samozřejmě, že pokud jsou k dispozici už jen např. 2 nezúčastněné kameny, obrazec neuvažujeme, stejně tak, pokud k dosažení těchto polí nezbývá již nezúčastněným kamenům dostatek tahů. Též pole b6 ve schématu 6 je třeba obsadit kamenem.
Obrazec s bVe6 ve schématu 6 je vyloučen, protože na f6 (na kritickém poli v matující linii) stojí bílý zúčastněný kámen. Zajímavý by byl případ, kdy by na f6 stála druhá bílá věž (nebo dáma). Ten by byl nejprve uvažován jako dvojitý šach, ale optimalizace č.3 by šach bílou věží e6 vyloučila a dále by se obrazec považoval jako jednoduchý šach kamenem z f6.
Pokud má být v obrazci černý král vedle pole bílého (nezúčastněného) krále, stojí to min. 1 tah navíc, pokud dokonce přímo na tomto poli, min. 2 tahy navíc. Ve schématu 6 by musel bKh1 vykonat dokonce 3 tahy navíc (při požadované pozici čKh1).
Pokud je bílý král již zúčastněný kámen, bude v obrazci na svém koncovém poli, k čemuž bude muset vykonat požadovaný počet tahů, ale optimalizaci č.6 již přímo nepůjde použít (potřebné tahy jsou již zahrnuty).
Testy ukázaly, že u celkem 19 úloh z 80 testovaných projde optimalizací méně než 1% obrazců (lze si všimnout, že ve většině těchto pozic jsou možné proměny černých pěšců).
V průměru sítem optimalizací projde v průměru jen 15% obrazců (tj. cca 85% obrazců je v této fázi vyloučeno, což představuje v průměru více jak šestinásobné zrychlení). Dále je vidět, že optimalizace jsou mírně účinnější v sériovotahových pomocných matech.
Výstupem z algoritmu polí je k-tice vybraná z n prvků (k<=n). Postupně jsou takto probrány všechny možné k-tice.
Příklady výstupů z algoritmu polí:
n=4, k=2
kombinace 12, 13, 14, 23, 24, 34
variace 12, 13, 14, 21, 23, 24, 31, 32, 34, 41, 42, 43
variace s opakováním 11, 12, 13, 14, 21, 22, 23, 24, 31, 32, 33, 34, 41, 42, 43, 44
n=5, k=3
kombinace 123, 124, 125, 134, 135, 145, 234, 235, 245, 345
variace 123, 124, 125, 132, 134, 135, 142, 143, 145, 152, 153, 154, 213, 214, 215, 231, 234, 235, 241, 243, 245, 251, 253, 254, 312, 314, 315, 321, 324, 325, 341, 342, 345, 351, 352, 354, 412, 413, 415, 421, 423, 425, 431, 432, 435, 451, 452, 453, 512, 513, 514, 521, 523, 524, 531, 532, 534, 541, 542, 543
variace s opakováním 111, 112, 113, 114, 115, 121, 122, 123, 124, 125, 131, 132, 133, 134, 135, 141, 142, 143, 144, 145, 151, 152, 153, 154, 155, 211, 212, 213, 214, 215, 221, 222, 223, 224, 225, 231, 232, 233, 234, 235, 241, 242, 243, 244, 245, 251, 252, 253, 254, 255, 311, 312, 313, 314, 315, 321, 322, 323, 324, 325, 331, 332, 333, 334, 335, 341, 342, 343, 344, 345, 351, 352, 353, 354, 355, 411, 412, 413, 414, 415, 421, 422, 423, 424, 425, 431, 432, 433, 434, 435, 441, 442, 443, 444, 445, 451, 452, 453, 454, 455, 511, 512, 513, 514, 515, 521, 522, 523, 524, 525, 531, 532, 533, 534, 535, 541, 542, 543, 544, 545, 551, 552, 553, 554, 555
Algoritmus polí je ve VKSACHu volán v optimalizacích v redukčním algoritmu při generování multiobrazců, k=nutně obsazená pole, n=počet nezúčastněných kamenů, používají se variace. Výsledkem každého volání algoritmu polí jsou pořadová čísla nezúčastněných kamenů, kterými se obsadí pole, na nichž nutně musí stát nějaký kámen.
Dále je algoritmus polí volán v algoritmu výseče a je používán dokonce ve dvou cyklech: Nejprve k=d(x), n=d(y), používají se kombinace (v uvedeném příkladu při přechodu pěšce z d3 na f7 je d(x)=počet braní=2 a d(y)=délka cesty=4). Výsledkem jsou pořadová čísla polí, kde bude provedeno braní (vygenerovaným kombinacím čísel se přiřadí konkrétní pole). Pro každou kombinaci těchto uzlových bodů se pak znovu volá algoritmus polí s k=d(x), n=počet nezúčastněných kamenů, používají se variace. Výsledkem je nabídka pořadových čísel braných nezúčastněných kamenů opačné barvy.
Algoritmus pěšců běhově probírá postupně všechny zúčastněné pěšce bílého a černého v aktuální úrovni řešení a zjišťuje minimální počet tahů nutný k dosažení obrazce s přihlédnutím k proměnám a počtu nutných braní.
2 1 0 1 2
Uvažujme následující schéma, kde má být bílý pěšec stojící v aktuální úrovní řešení na f2 v matovém obrazci na poli g4 a bílý pěšec stojící na e6 má být v matovém obrazci proměněný na jezdce na poli g6. Vidíme, že pěšec f2 bude potřebovat 2 tahy a nutně 1 braní. Pěšec f6 zvládne svou cestu nejlépe ve 3 tazích, když se promění na f8, k čemuž ovšem nutně potřebuje 1 braní. Pokud ale nebudou v aktuální úrovni řešení k dispozici již žádné nezúčastněné černé kameny k sebrání, musel by se proměnit na e8, což by šlo sice bez braní, ale potřeboval by celkem 6 tahů. Pokud jich nebude mít tolik k dispozici, není uvažovaný obrazec v této větvi řešení možný.
Zúčastněné kameny jsou ty, které se účastní aktuálního obrazce (tvoří jeho kostru). Nezúčastněné kameny jsou ty, které se právě probíraného obrazce neúčastní.
Nyní si ukážeme jak celý problém zalgoritmizovat. Zavedeme si vektory obsahující minimální počty tahů nutné k dosažení obrazce podle počtu braní. Hloubka této tabulky je maximálně rovna počtu nezúčastněných kamenů opačné barvy (s vyjímkou krále).
|
počet braní |
Pf2 |
normováno |
Pe6 |
minimum1 |
normováno2 |
|
0 |
*3 |
* |
2+44 |
6 |
6 |
|
1 |
2 |
2 |
2+3,2+15 |
3 |
3 |
|
2 |
* |
2 |
2+2,2+26 |
4 |
3 |
|
3 |
* |
2 |
|
|
3 |
1 Při stejném počtu braní, je třeba vybrat pro daný kámen cestu v nejkratším počtu tahů
2 Aby se dále korektně prováděly výpočty s těmito vektory, musí být posloupnost nerostoucí - když na něco stačí jedno braní, musí na to (z hlediska logiky programu) stačit i více - převezmeme aktuální minimum posloupnosti.
3 * znamená, že cesta není možná při libovolném počtu tahů
4 2 tahy do proměny a další 4 tahy z pole proměny (e8) na g6. Zde je třeba poznamenat, že pokud by šlo o proměnu na obecný exokámen (ovšem z pohledu VKSACHu, kde např. cvrček do této skupiny nepatří ...), uvažují se z důvodů obecnosti pouze tahy do proměny.
5 V tomto řádku jsou 2 možnosti při 1 povoleném braní - 3 tahy z d8 nebo 1 tah z g8
6 I při 2 braních jsou 2 možnosti - z polí c8 i g8 se jezdec dostane na g6 vždy ve 2 tazích
Algoritmus začne pro každou barvu vždy s nulovým vektorem a provádí cyklus přes všechny zúčastněné pěšce stejné barvy a s průběžně získaným mezivýsledkem provede následující operaci (předpokládejme, že začal s pěšcem e6 a nyní probírá pěšce f2):
|
počet braní |
mezivýsledek
|
operand
|
|
|
|
|
QB tahů |
|||||||||
|
0 |
m0 |
6 |
t0 |
* |
m0+t0 |
* |
|
* |
||||||||
|
1 |
m1 |
3 |
t1 |
2 |
m1+t0 |
* |
m0+t1 |
8 |
|
8 |
||||||
|
2 |
m2 |
3 |
t2 |
2 |
m2+t0 |
* |
m1+t1 |
5 |
m0+t2 |
8 |
|
5 |
||||
|
3 |
m3 |
3 |
t3 |
2 |
m3+t0 |
* |
m2+t1 |
5 |
m1+t2 |
5 |
m0+t3 |
8 |
5 |
|||
|
(4) |
|
(3) |
|
(2) |
|
m3+t1 |
5 |
m2+t2 |
5 |
m1+t3 |
5 |
(5) |
||||
|
(5) |
|
(3) |
|
(2) |
|
m3+t2 |
5 |
m2+t3 |
5 |
(5) |
||||||
|
(6) |
|
(3) |
|
(2) |
|
m3+t3 |
5 |
(5) |
||||||||
Složením vektorů jednotlivých pěšců podle předchozích pravidel dostaneme vektor obsahující minimální počty tahů bílého nebo černého podle nutného počtu braní. Samotné minimum představuje nejefektivnější kombinaci tahů vedoucí k požadovanému obrazci. Označíme nyní
QB vektor min.počtu tahů podle počtu nutných braní bílých pěšcůJe dokonce možné, že takové i nebo j neexistuje (tj. že aktuální počet tahů nestačí ani při největším počtu braní), pak samozřejmě probíranou cestu ihned eliminujeme.
Podobně hledáme takové nejmenší j, aby QC(j) <= THC
Hodnoty i, resp. j představují minimální nutný počet braní bílého, resp.černého nevyhnutelný k dosažení obrazce při počtu tahů, který je aktuálně k dispozici.
V předchozím příkladu, pokud např. bude THB=6, dostaneme i=2, protože QB(2)=5 <= THB, ale pro QB(1)=8 nerovnost neplatí, tj. i=2 je nejmenší možné i, které ji splňuje.
K tomu, aby byla aktuálně možná cesta do probíraného obrazce, nesmí být nutný počet braní větší než počet aktuálně možných braní, tj. musí platit i <= NZC a j <= NZB.
V našem příkladu, pokud nám vyšlo, že potřebujeme minimálně 2 braní bílými pěšci a zjistíme-li, že černý má např. už jen jeden kámen, který je možno sebrat (ostatní - zúčastněné kameny - musí zůstat v matovém obrazci), probíranou cestu eliminujeme.
V základní části algoritmu pěšců jsme zjišťovali, zda je dostatek nezúčastněných kamenů opačné barvy, které je nutno vzít při cestě pěšců na svoje koncová pole, aby bylo obrazce dosaženo v požadovaném počtu tahů.
Algoritmus výseče jde ještě o něco dál. Pro pěšce uvažuje cestu na koncové pole (nebo na pole proměny) a zjišťuje, zda kameny opačné barvy, které musí pěšec na své cestě vzít, mají dostatek tahů na to, aby to bylo v požadovaném počtu tahů možné. Tento problém je netriviální a vyžaduje tzv. backtracking, který je ve VKSACHu řešen algoritmem polí.
Backtracking je algoritmus, který postupně probírá všechny možnosti ve všech úrovních (tj. po každé možnosti na úrovni 1 probere všechny možnosti na úrovni 2, po každé z možností na úrovni 2 všechny možnosti na úrovni 3, atd.). Pokud dojde do poslední úrovně (nebo pokud jsou možnosti na některé z úrovní vyčerpány), následuje tzv. zpětný běh, kdy se vrací o 1 úroveň zpět atd., až opět do úrovně 1, kde pokračuje další možností atd. Algoritmus končí, až jsou všechny možnosti vyčerpány.
Několik příkladů: Řešení úloh metodou hrubé síly je backtracking, počet možností je roven počtu tahů bílého, resp. černého po každém tahu. Redukční algoritmus při probírání existence obrazců je též backtracking, ale ne přes tahy, ale přes masky a kameny. S-algoritmus není backtracking, rozpojovací algoritmus není backtracking.
Backtracking má exponenciální složitost a provádět jej do více úrovní je časově velmi náročné. U algoritmu výseče naštěstí potřebná hloubka není velká (max.6 tahů).
Cílem je probrat všechny možné cesty pěšce na koncové pole s uzlovými body, které tvoří pole, kde budou provedena potřebná braní.
V předcházejícím schématu u algoritmu pěšců jsme si mohli všimnout, že cesty kamenů na koncová pole i nutná braní s nimi spojená, bylo možno uskutečnit několika způsoby. Např. pěšec f2 může jít na g4 přes f3 a brát až na g4 nebo brát nejprve na g3 a pak postoupit na g4.
Pro každou z těchto cest se musí probrat všechny kombinace možných braných nezúčastněných kamenů opačné barvy a určit součet počtu nutných tahů těchto kamenů, aby se dostaly ze svých počátečních polí na pole, kde budou brány. Minimum těchto součtů pro všechny možné cesty a všechna možná rozmístění braných kamenů na těchto cestách určuje nezbytný počet tahů opačné strany nutných k dosažení obrazce. Pokud jich není tolik aktuálně k dispozici, není možno dosáhnout obrazce a probíraná cesta je eliminována.
Ve schématu má být bílý pěšec d3 v matovém obrazci na poli f7. Tabulka rozebírá všechny možné cesty, šrafovaně jsou vyznačeny uzlové body, kde jsou provedena nutná 2 braní. Vidíme, že existuje více rovnocenných optimálních cest, při kterých jsou potřebné vždy 3 tahy černých kamenů. Pokud má tedy černý v aktuální úrovni řešení 2 nebo méně tahů, nelze obrazce dosáhnout. Zjišťování počtu tahů potřebných k převodu kamenů na pole braní se provádí efektivně pomocí tabulek dostupnosti polí (staticky) a tento počet může být teoreticky i nulový, pokud je již kámen na tomto poli.
|
možné cesty pěšce d3 na f7 |
braní |
tahů |
braní |
tahů |
min. |
||||||
|
d3 |
d4 |
d5 |
e6 |
f7 |
Je6 |
Vf7 |
3+2 |
Ve6 |
Jf7 |
2+3 |
5 |
|
d3 |
d4 |
e5 |
e6 |
f7 |
Je5 |
Vf7 |
2+2 |
Ve5 |
Jf7 |
2+3 |
4 |
|
d3 |
d4 |
e5 |
f6 |
f7 |
Je5 |
Vf6 |
2+2 |
Ve5 |
Jf6 |
2+2 |
4 |
|
d3 |
e4 1 |
e5 |
e6 |
f7 |
Je4 |
Vf7 |
1+2 |
Ve4 |
Jf7 |
1+3 |
3 |
|
d3 |
e4 |
e5 |
f6 |
f7 |
Je4 |
Vf6 |
1+2 |
Ve4 |
Jf6 |
1+2 |
3 |
|
d3 |
e4 |
f5 |
f6 |
f7 |
Je4 |
Vf5 |
1+2 |
Vf5 |
Jf5 |
2+3 |
3 |
1 Tah e4-d5 už neuvažujeme, protože vyžaduje více než nutný počet braní
Tabulky dostupnosti polí umožňují statické zjištění, v kolika tazích je dostupné určité pole. Potřebujeme-li např. v průběhu řešení zjistit, v kolika tazích se dostane jezdec z e4 na g6, nebudeme to zjišťovat zkoumáním všech možných cest (což by byl dokonce backtracking), ale zjistíme to přímo z tabulky dostupnosti polí pro příslušný typ kamene (což spočívá jen v určení indexu v této tabulce podle diference obou polí a ve vyzvednutí této hodnoty z paměti).
Tabulky dostupnosti polí mohou být několika typů podle toho, kolik mohou zabírat paměti. Pokud budeme vázat pohyblivost např. na pole A1, zabere taková tabulka jen 64 bytů (a musí odpovídat vlastně nekonečné šachovnici). Tuto tabulku potom přiložíme polem A1 na výchozí pole kamene a hodnotu zjistíme podle stejnolehlého pole (ve zmíněném příkladu by bylo e4-g6 převedeno na a1-c3). Tento rozsah představuje dobrý kompromis mezi kapacitou paměti a přesností výsledku. Pokud nemusíme šetřit pamětí, můžeme vytvořit tabulky dostupností každého pole s každým, což ale vyžaduje (pro šachovnici 8x8) 4096 bytů pro každý typ kamene. Např. cestu jezdce z g7 na h8 lze (díky okrajům šachovnice) provést až ve 4 tazích, ale z 64 bytové tabulky bychom dostali hodnotu 2. Poslední možností je zjišťování dostupnosti jednoúrovňově jen programově (např. u krále, věže nebo střelce lze snadno), ale zde je třeba si uvědomit, že i příslušná procedura zabírá v paměti nějaké místo ... Tabulky 4096 bytů jsou výhodné na normální šachovnici hlavně pro skokany (x,y), kde x,y jsou větší čísla. VKSACH je používá též pro tátošového cvrčka (snížení o 1-2 stupně volnosti na kámen je znát v časech řešení).
Tabulky dostupnosti polí jsou velmi účinné u bodových kamenů. U liniových kamenů se už staticky nezjistí, zda na cestě překáží nějaký kámen (a obecně nelze takovou možnost optimalizovat, protože překážející kameny mohou během řešení táhnout a liniový kámen může provést svou cestu přesně ve zjištěném počtu tahů). U přeskakujících kamenů statický odhad ztrácí nejvíce. Pokud má např. cvrček c2 táhnout na e6, musíme (bez rizika ztráty řešení) uvažovat, že to zvládne ve 2 tazích. Ve skutečnosti jsou skoky podmíněné tím, že na některé z možných cest budou v okamžiku tahu nějaké kameny, přes které cvrček přeskočí.
Vylepšení odhadu potřebného počtu tahů (bez nutnosti fyzického provedení všech možností) provádí rozpojovací algoritmus.
Rozpojovací algoritmus je volán běhově pro přeskakující kameny - cvrček (Grasshopper), tátošový cvrček (Nightriderhopper) atd. (pro všechny kameny s charakteristikou 3 ve VKSACHu).
Podobně jako algoritmus výseče uvažuje i nezúčastněné kameny a to (na rozdíl od algoritmu výseče) obou stran. Provádí se (podobně jako třeba S-algoritmus) pouze do hloubky 2, tj. nejde o backtracking.
Samozřejmě, že by i zde bylo možné použít backtracking (tj. provádět rozpojování do hloubky), ale poměrně těžko by se ošetřoval případ vzájemné kolize několika přeskakujících kamenů, kdy je možné i přeskakování jednoho přeskakujícího kamene přes jiný přeskakující kámen, který bude též v obrazci. Též by se muselo počítat s tím, že skoky může běhově umožnit i jeden kámen postupně na více polích. Navíc u podobných algoritmů je třeba uvážit, zda nejsou příliš časově náročné a to dokonce až tak, že vyžadují více času než pouhé procyklení všech možností bez optimalizací. Hranice kdy hrubá síla je rychlejší než inteligentní metody vždy existuje, někdy je ji nutno zjistit až experimentálně (např. h#2/R je pomalejší než h#2, h#3/ZR a h#3/Z jsou někde na hranici a h#3/R už je obvykle rychlejší než h#3), příp. optimalizaci vůbec nepoužívat.
Rozpojovací algoritmus provádí cyklus přes všechny přeskakující kameny a pro každý z nich hledá možné cesty z počátečního (resp.aktuálního pole) na koncové pole (v obrazci). Vychází z toho, že má pro bílého i černého pouze určitý zbylý počet tahů (stupňů volnosti), který nesmí přečerpat.
Základní počet stupňů volnosti je dán počtem tahů úlohy zmenšeným o nutný počet tahů (zjištěný z tabulek dostupnosti polí) zúčastněných kamenů do pozice obrazce. Ve skutečnosti (běhově) bude převod do obrazce stát minimálně tento počet a obvykle k tomu budou třeba ještě nějaké tahy navíc. Když se zjistí, že již tolik tahů není aktuálně k dispozici, lze možnost eliminovat bez nutnosti zabývat se tím, co by nastalo po ní. To přináší obvykle velkou časovou úsporu.
Následující obrázky znázorňují princip rozpojení.
| zúčastněný kámen | nezúčastněný kámen | |
|
v pozici na poli P1 v obrazci na poli P3 |
v pozici na poli P1 |
|
|
|
Bez použití rozpojovacího algoritmu | |
S rozpojovacím algoritmem |
||
Pokud není použit rozpojovací algoritmus, potom je pro zúčastněný kámen stojící na poli P1, který má být v obrazci na poli P3 potřeba t0 tahů, pro nezúčastněný kámen stojící na poli P1 není potřeba žádný tah.
Uvažujeme-li nyní cestu cvrčka z výchozího pole Q1 přes pole Q2 (1 tah) na koncové pole Q3 (zbylý počet tahů), musí na poli P2, přes které je realizován skok na pole Q2, stát nějaký kámen.
(Pokud by se měl skok uskutečnit přes jiný přeskakující kámen, tak se dostupnosti počítají už jen z tabulek dostupnosti polí, tj. rekurzivní volání rozpojovacího algoritmu se nekoná.)
Rozpojovací algoritmus nyní v případě, že jde o zúčastněný kámen stojící na poli P1, který má být v obrazci na poli P3, přináší podmínku, že tato cesta musí být realizována přes pole P2. Rozpojí proto původní cestu a uvažuje 2 cesty: nejprve z pole P1 na pole P2 (v t1 tazích) a následně z pole P2 na koncové pole P3 (v t2 tazích). Evidentně t1+t2 >= t0
V případě, že jde o nezúčastněný kámen stojící na poli P1, uvažuje jeho cestu na pole P2, kde umožní skok cvrčka na pole Q2. K tomu bude potřebovat t1 tahů.
Při použití rozpojovacího algoritmu je úspora v případě zúčastněného kamene t1+t2-t0 tahů a v případě nezúčastněného kamene t1 tahů.
Optimalizace v rozpojovacím algoritmu
Pokud má bílý již nejvýše jeden tah (což je speciálně v sh#n splněno vždy), lze použít následující optimalizace
Činnost rozpojovacího algoritmu si ukážeme na příkladu. Ve schématu mají být v obrazci Jd2 na f6, Kf5 na h7 a TCf2 na g6. Ka1 a Se6 jsou pro tento obrazec nezúčastněné kameny. Snadno spočítáme (při nepoužití rozpojovacího algoritmu), že k dosažení obrazce potřebuje bílý 2 tahy a černý 4 tahy. Ve skutečnosti je třeba zajistit provedení skoků tátošového cvrčka, což bude stát další tahy. V tabulce jsou uvedeny všechny možnosti, které probírá rozpojovací algoritmus. Postupně uvažuje jednotlivé linie TC a na nich možná pole, kde je možno realizovat skok. Na těchto 4 polích (označených ve schématu kroužkem) postupně zkouší všechny ostatní kameny bílého i černého a zjišťuje potřebné počty tahů.
|
černý tátošový cvrček zúčastněný |
bKrál nezúčastněný |
bJezdec zúčastněný |
čKrál zúčastněný |
čStřelec nezúčastněný |
bílých tahů
|
černých tahů
|
|||
|
čTC |
přes |
na pole |
tahů |
skok přes bK |
bJd2-f6 |
čKf5-h7 |
čSe6 |
||
|
f2 |
d3 |
b4 |
1+3 |
3 |
2
|
2 |
0 |
5 |
6 |
|
e4 |
d6 |
1+3 |
4 |
6 |
6 |
||||
|
d6 |
c8 |
1+1 |
5 |
7 |
4 |
||||
|
g4 |
h6 |
1+3 |
6 |
8 |
6 |
||||
|
|
bKa1 |
skok přes bJ |
čKf5-h7 |
čSe6 |
|
||||
|
d3 |
b4 |
1+3 |
0 |
3+3 |
2 |
0 |
6 |
6 |
|
|
e4 |
d6 |
1+3 |
1+1 |
2 |
6 |
||||
|
d6 |
c8 |
1+1 |
2+2 |
4 |
4 |
||||
|
g4 |
h6 |
1+3 |
3+1 |
4 |
6 |
||||
|
|
bKa1 |
bJd2-f6 |
skok přes čK |
čSe6 |
|
||||
|
d3 |
b4 |
1+3 |
0 |
2 |
2+4 |
0 |
2 |
10 |
|
|
e4 |
d6 |
1+3 |
1+3 |
2 |
8 |
||||
|
d6 |
c8 |
1+1 |
2+4 |
2 |
8 |
||||
|
g4 |
h6 |
1+3 |
1+3 |
2 |
8 |
||||
|
|
bKa1 |
bJd2-f6 |
čKf5-h7 |
skok přes čS |
|
||||
|
d3 |
b4 |
1+3 |
0 |
2 |
2 |
2 |
2 |
8 |
|
|
e4 |
d6 |
1+3 |
2 |
2 |
8 |
||||
|
d6 |
c8 |
1+1 |
* |
2 |
* |
||||
|
g4 |
h6 |
1+3 |
1 |
2 |
7 |
||||
Nyní je třeba uvažovat počet tahů bílého a černého, které jsou aktuálně k dispozici. Např. pokud půjde o h#8 a budeme-li v úrovni po 3.tahu černého, bude mít bílý k dispozici ještě 6 tahů a černý 5 tahů. Pak by přicházela v úvahu pouze (šrafovaně označená) možnost, kdy bílý Jd2 při své cestě na f6 nejprve umožní na d6 přeskok TCf2 na c8. K tomu bude celkem potřebovat bílý 4 tahy a černý rovněž 4 tahy. Zda povede tato cesta skutečně k cíli, se ukáže až běhově (dynamicky) v dalším průběhu řešení (po dalších tazích bude opět volán rozpojovací algoritmus a ukáže se, zda se stačí v uvažované variantě obsadit pole e7 k dalšímu skoku čTC nebo zda bude varianta eliminována).
Porovnáme-li zjištěný počet tahů (4+4) s primárním odhadem (2+4), vidíme, že rozpojovací algoritmus v příkladu ušetřil 2 tahy bílého (což může představovat i řádovou časovou úsporu).
Řešení pomocných matů se vyznačuje tím, že pořadí tahů obou stran (resp. černého u sériovotahových úloh) je jednoznačné. Zkoumejme tedy jen takové tahy, jejichž pořadí je jednoznačné - tím by došlo k velké eliminaci možností. Má to však jeden háček - program by našel jen jednoznačná řešení a vedlejší, u kterých tomu tak obvykle nebývá, nikoliv. V případě nejednoznačnosti proto uvažujme jednu reprezentující možnost. Tak vznikly dva algoritmy:
Princip S1 - algoritmu: pokud uvažujeme sekvenci tahů A B C, kde tahy A a C jsou různými kameny (téže barvy), je tato sekvence jednoznačná pouze, když není možné pořadí tahů C B A (tj. když tahy nelze prohodit). Když tahy A a C jsou stejným kamenem, pak je tato sekvence jednoznačná pouze, když cesta tohoto kamene na koncové pole je možná jen jedním způsobem (např. pokud je bílý král na a2, tak na c4 existuje pouze jedna cesta a2-b3-c4, zatímco na b1 jsou možné 2 a na c2 dokonce 3 různé cesty). Samozřejmě, že je též třeba rozlišovat případy, kdy jsou tahy spojené s braním.
S - algoritmus uvažuje kromě jednoznačných tahů ještě reprezentující možnosti, což jsou sekvence, které nahrazují nejednoznačné sekvence tahů. V případě 2 různých kamenů se z možností pořadí tahů A B C, C B A vybere jen jedna (druhá přináší jen další vedlejší řešení stejného typu). V případě tahů stejným kamenem se rovněž z možných cest uvažuje jen jedna reprezentující možnost (a může zde nahrazovat 2 i více nejednoznačných sekvencí A1 B C1, A2 B C2, ...). Při výpisu tohoto (evidentně vedlejšího) řešení je k němu připojen text „Duál“.
Experimenty ukázaly, že jednoznačných tahů v každé úrovni řešení je asi 45%, nejednoznačných asi 55%. Přibližně 70% tahů je třeba uvažovat pro úplnou kontrolu korektnosti, reprezentujících možností je přibližně 25%. Nejednoznačných tahů eliminovaných S-algoritmem je přibližně 30%.
Pojem jednoznačnosti pořadí tahů je intuitivně jasný. S-algoritmus zkoumá vždy trojice tahů (označme je A - B - C) a zjišťuje jejich jednoznačnost, v další úrovni se posune o jeden tah a zkoumá další trojici tahů, atd. Složitější je 2-jednoznačnost přesně definovat, tak, aby šla naprogramovat.
Pozn.: Šlo by zkoumat i jednoznačnost delších sekvencí, ale to by bylo časově už velmi náročné a časová ztráta tím způsobená by byla často větší než uvažování všech možností bez optimalizace. Zkoumání trojic tahů, které můžeme též nazvat 2-jednoznačností je relativně časově únosné (a má smyl používat od h#2.5 tahem). Tento algoritmus je jakýmsi "hashováním bez potřeby paměti RAM".
Pokud jsou tahy A a C jsou různými kameny, zkoumá se, zda je možno tyto tahy prohodit, tj. zda je přípustná sekvence C - B - A. Pokud ano, možnost se eliminuje (S1) nebo se uvažuje jen jedna z nich (S). Když jsou tahy A a C stejným kamenem, zjišťuje se, zda existuje sekvence tahů A’,B,C’, kde tahy A’,C’ jsou týmž kamenem a C’ je na stejné pole jako C. Pokud ano, postupuje se stejně jako výše.
Např. ve schématu jsou sekvence tahů 1.Kf2 A Kd6 B 2.Se2 C (tah Se2 neexistuje v úrovni A), 1.Vg2 A Kd6 B 2.Sg4 C (tah Vg2 neexistuje v úrovni C) jednoznačné. Stejně tak je jednoznačná sekvence 1.Vg5 A1 Kd6 B 2.Vd5+ C1, protože v případě 1.Vd7 A2 Kd6??? B 2.Vd5 C2 není tah Kd6 možný.
Ze tří sekvencí 1.Ke2 A1 Kd6 B 2.Kd1 C1, 1.Ke2 A1 Kd6 B 2.Kd2 C1, 1.Ke2 A1 Kd6 B 2.Kd3 C1 je jednoznačná pouze první, protože ve druhém případě je možné i 1.Ke3 A2 Kd6 B 2.Kd2 C2 a ve třetím případě existují dokonce 2 jiné sekvence, 1.Ke3 A2 Kd6 B 2.Kd3 C2 a 1.Ke4 A3 Kd6 B 2.Kd2 C3.
Též je třeba rozlišit případ braní, sekvence 1. - J:g7 A1 2.Kg2 B Je8 C1 a 1. - Jf6 A2 2.Kg2 B Je8 C2 jsou dvě různé sekvence tahů, naopak sekvence 1. - J:g7 A 2.Kg2 B Kf5 C je nejednoznačná, protože je možné i pořadí 1. - Kf5 C 2.Kg2 B J:g7 A.
V sériovotahových pomocných matech nebo patech (sh#n, sh=n) se v případě tahu stejným kamenem eliminuje příp.tah na původní pole, v případě nesériovotahových výzev je tento návrat kamene možný a musí se uvažovat. Např. možnost 1.Ke2 A (teoretický prázdný tah bílého B) 2.Kf3 C (oscilace) se vyloučí v sh#n, ale musí být uvažována v h#n (kde B bude nějaký skutečný tah bílého). Podobně tomu bude se sekvencí 1.Ke2 A (B) 2.Ke3 C (tempový manévr), pokud existuje na úrovni A přímý tah na koncové pole (1.Ke3, samozřejmě by ale nešlo ani v sh#n použít, pokud by byl tento tah spojen s braním).
S-algoritmus lze též použít v sériovotahovém samomatu (ss#n/S1 bude velmi efektivní k nalezení autorského řešení), nelze jej ale použít v sériovotahovém reflexním matu (sr#n).
S-algoritmus lze kombinovat prakticky se všemi exopodmínkami, z hlediska programování to však může přinášet různá úskalí.
Uvažujme v CIRCE šachu např. pozici na schématu. Sekvence tahů 1.K:h1 A (nějaký tah bílého B, nebo jen teoretický, pokud jde o sh#n) 2.Jh2 C a 1.Jh2 C (B) 2.K:h1(Sf1) A nelze přehodit. V ortodoxním šachu je tato sekvence nejednoznačná (A-B-C i C-B-A stačí nahradit jen jednou z nich a o žádné vedlejší řešení nepřijdeme), zatímco v CIRCE je sekvence jednoznačná (a může být součástí autorského řešení) !
