|
Nie obrażaj więc mojej inteligencji poprzez czynione na pokaz zaniżanie własnej.
Využití teorie grafů v šachových úlohách
Application of Graph Theory in Chess Problems (Dual-free Leaper and Hopper tours) (Václav Kotěšovec, 2009) Úvod – Introduction Tato publikace se zabývá především jednoznačnými cestami skokanů na různých šachovnicích a algoritmy hledání hamiltonovských cest v grafech. Výsledkem je pak srie korektních šachových úloh, většinou absolutních rekordů. Druhá část je věnována cestám přeskakujících kamenů . This booklet examines Leaper and Hopper tours with unique move order and algorithms for finding Hamiltonian paths in graphs. A consequence is a series of correct chess problems, the majority being absolute length records. The first part of this booklet identifies an equivalence between Hamiltonian tours and chess problems of a certain kind (series-movers in which the aim is to stalemate Black by capturing all his men), discusses the finding of such tours by computer, and presents various numerical results. The second part examines some tours of the same kind using hoppers. Most of the results are „ absolute “ (proven optima), but some are identified as only „ probable “ (best found to date and an improvement seems unlikely, but an exhaustive search has not been performed). The text is almost wholly in Czech, but the diagrams are self- explanatory. Nejprve je třeba vysvětlit, jaká byla motivace hledání jednoznačných cest? Tzv. „jezdcova procházka“ ( Knight's tour ), tedy hledání cesty jezdce na šachovnici 8×8 (takov, aby prošel všechna pole šachovnice a přitom na ţádn nevstoupil dvakrát), je jedním z klasických problmů, který jde ale zařadit spíše do kategorie hádanek (nebo matematických úloh) neţ do šachových úloh. Z hlediska šachových problmů jde totiţ o to, ţe kaţdá úloha musí mít jen jedno řešení, resp. tolik řešení, kolik stanovil autor skladby. Klasická cesta jezdce (ať uţ otevřená nebo uzavřená) však tuto podmínku nesplňuje. Řešitele můţe potěšit, ţe nějakou takovou cestu odpovídající zadání našel, ale v naprost většině případů tyto cesty nejsou jednoznačn a moţných řešení (tedy cest z počátečního na koncov pole) jsou obvykle tisíce. Jako šachová úloha je proto taková skladba nekorektní. Celá problematika mě však velmi zaujala a přemýšlel jsem o tom, zda by přesto nebylo moţn tyto různ cesty (jezdce nebo obecně skokanů) na šachovnicích transformovat na takov typy úloh, kter by obstály i jako korektní „šachov úlohy“. Jednou z moţných transformací jsou úlohy typu sd=n , tj. sriový pat n-tým tahem, kdy má bílý za úkol srií tahů postupně sebrat všechny čern kameny. Vtip je v tom, ţe postup, v jakm musí být kameny sebrány, je jediný moţný. Celkový přehled maximálních délek jednoznačných cest skokanů na různých šachovnicích přináší na straně Podobnho charakteru (s braním všech kamenů) jsou i cesty kamenů typu Locust na str. Druhou moţností jsou úlohy typu ( series-case ), ve kterých je cílem se srií tahů co nejrychleji dostat na určen pole. Těmi se zabývám v části „Cesty přeskakujících kamenů“, Na str. najdeme nejdelších cest podle počtu překáţek. Jiná moţnost úloh typu „SerienZug-Ziel“ byla popsána v článku Václav Kotěšovec: (Games and Puzzles Journal 20/2001). Kdyţ uţ jsem měl připravený program na hledání jednoznačných cest, prozkoumal jsem pak i cesty nejednoznačn, resp. uzavřen (ty jsou v případě skokanů z principu nejednoznačn, ale pro kameny typu Locust jednoznačn být mohou, protoţe cesta opačným směrem není moţná). Zkoumáním i nejednoznačných cest jsem zejmna v případě skokanů ověřil řadu jiţ existujících výsledků (ze kterých však někter nebyly doposud potvrzeny počítačem) a současně jsem i v tto oblasti doplnil výsledky Totţ platí i pro cesty přeskakujících kamenů, kde v případě úloh zkoumaných v podkapitolách a nemá jednoznačnost zásadní význam, naopak v podkapitolách a je jednoznačnost naprosto zásadní. Celkově bylo na získání všech výsledků, obsaţených v tto knize, potřeba asi 4000 hodin počítačovho času (k výpočtům jsem pouţil svůj počítač AMD 64 s dvojjádrovým procesorem), z toho bylo přes 3300 hodin na cesty skokanů, zbytek na cesty přeskakujících kamenů. Pro zobrazení řešení úloh se osvědčily diagramy obsahující čísla určující pořadí tahů. Řešení ve formátu textu je pak jiţ obvykle nadbytečn. Pokud je přesto někde vloţeno, názvy kamenů jsou (kvůli lepší srozumitelnosti pro zahraniční čtenáře) v anglick notaci. Figurkovou notaci jsem pouţil pouze pro ortodoxní kameny, protoţe pro exokameny je mně přehledná. Kniha obsahuje celkem 280 diagramů (z toho 211 s čísly), 33 grafů a 20 tabulek. Moje poděkování za pomoc při sestavování tto knihy si zaslouţí John Beasley (který provedl korekturu většiny mých anglických textů a ochotně pro mě vyhledal dva chybějící prameny ze starých anglických časopisů), Pavel Kameník, Ivan Skoba a Ivan Jarolín (kteří si přečetli celý text ještě před publikováním a přispěli několika cennými připomínkami). Praha, zima 2008 – jaro 2009 Václav Kotěšovec 2 Obsah – Content ............................................................................ ......................................................... 1 ................................... ............................... ● ................................... ● ............................... 4 ● .................................. ● ....................... 5 ● ................................. ● ... 7 ● ............................................................. ● ............................... 8 ● Optimalizace odstraňováním hran, kudy uţ ..................................................... ● .......................................... ● ................ ● ........................................... ● ......... ● ..... ● ....... ● ........................... ● ........... ● ........................................................... ● ............................. ● ..... ● ....... ● ........ ● ......................................... ● ............................................. ● ........................................................................... ● .................................. 15 ● ............ ● .... ● ......................... ● ........... ● Časy nezbytn k nalezení maximálních ................ ● ..................... 22 ● ....................................... ● ........................................................ 23 ● ....................................... ● ......................... 24 ● ............................. ● ........................................................ ....... ............................. ● ... ● ............................................ ● ................................................................... ● ..................................... ● ............. ● ............ ● ......... ● .. ● (a jiných kamenů)..... ● ......................... ......... ........... ............................. ............................................................ 76 3 I. Cesty skokanů I . Leaper tours Vysvětlení základních pojmů – Description of basic terms Skokan (Leaper) [x,y] – bodový kámen, který se na šachovnici pohybuje na všechny strany tak, ţe se jeho souřadnice mění o [x,y] (bývá zvykem x a y volit tak, aby x ≤ y). Jeho moţn tahy z pole o souřadnicích [x 0 ,y 0 ] jsou v maximálním případě na těchto 8 polí: [x 0 +x,y 0 +y], [x 0 +x,y 0 -y], [x 0 -x,y 0 +y], [x 0 -x,y 0 -y], [x 0 +y,y 0 +x], [x 0 +y,y 0 -x], [x 0 -y,y 0 +x], [x 0 -y,y 0 -x] Skutečný počet tahů můţe být menší. V případě, ţe x=0 nebo y=0, některá pole jsou identická. Ve všech případech koncov pole tahu nesmí překročit okraje šachovnice. Počet moţných tahů z danho pole odpovídá stupni příslušnho uzlu v grafu. Nejznámějším případem skokana je jezdec, coţ je skokan [1,2]. (Knight is Leaper [1,2]) Free Leaper – označení takovho skokana, ktermu jsou na šachovnici dostupná všechna pole (český termín neexistuje) . Pro názornost jsem pro zjištění tto vlastnosti doplnil do na str. sloupec „ access from a1 “. V tomto sloupci je pro kaţdho skokana počet polí, která jsou mu na šachovnici 8×8 dostupná z pole a1. Tato hodnota je horním omezením pro dlky všech typů cest. Vidíme, ţe hodnota 63 (tedy všechna moţná pole šachovnice 8×8 kromě výchozího) se v na str. vyskytuje pouze pro 5 typů skokanů: [0,1] = vezír [1,2] = jezdec [1,4] = ţirafa [2,3] = zebra [3,4] = antilopa Toto není ţádný objev, ale stará známá věc, kterou znal jiţ T. R. Dawson a o kter přehledně píše G. P. Jelliss v několika článcích „The Five Free Leapers“ v časopise Chessics, např. v č. nebo nebo v Výrazně to však redukuje „zajímav“ skokany. Opravdu – těchto 5 skokanů je nejatraktivnějších i při hledání hamiltonovských cest, ostatními skokany jsem se zabýval v podstatě jen pro úplnost. Z hlediska teorie grafů určení dostupnosti polí z výchozího pole odpovídá hledání nejkratší cesty v grafu ze zvolenho uzlu do ostatních (coţ je jednoduchá úloha). Hamiltonovská cesta (open tour) – je sekvence tahů skokana po různých polích šachovnice taková, ţe skokan nevstoupí na ţádn pole dvakrát. V teorii grafů se pouţívá spíše termín Hamiltonian path . Pro vybranou mnoţinu polí nemusí taková cesta vůbec existovat. Pro určení, zda daný graf je nebo není hamiltonovský, neexistují ţádn rozumně pouţiteln postačující podmínky a v teorii algoritmů je dokázáno, ţe jde o tzv. NP problm, tedy úlohu, která není řešitelná v polynomiálním čase. Jednoduše řečeno – jde o úlohu velmi těţkou, na vyřešení kter nemusí stačit ani desítky hodin počítačovho času. 4 Uzavřená cesta (closed tour) – je speciální případ hamiltonovsk cesty, na jejímţ konci můţe skokan skočit zpět na počáteční pole (tento poslední skok se obvykle ale do dlky cesty jiţ nezapočítává). V teorii grafů se takov cestě říká hamiltonovská kruţnice (Hamiltonian circuit) . Tento případ je nejvíce známý a to hlavně díky problmu ktermu byly v posledních 200 letech věnovány desítky knih a stovky článků. V tto publikaci se jím zabývám jen okrajově. Více viz Z na str. vidíme, ţe uzavřená cesta vedoucí přes všechna pole šachovnice 8×8 je moţná právě jen pro jezdce a vezíra. V tto oblasti existuje několik vět a i pro šachovnice různých rozměrů. Jednoznačná cesta (dual-free tour, sequence with unique move order) – je speciální (ale nejzajímavější!) případ obecn hamiltonovsk cesty s jednoznačným pořadím tahů. Právě jednoznačn cesty mě motivovaly k napsání tto publikace a byly prostředkem k vytvoření korektních šachových úloh (tj. úloh s právě jedním řešením). Program se ale pak ukázal jako pouţitelný i pro hledání nejednoznačných cest (otevřených i uzavřených) a nedalo mi to, abych neověřil do t doby publikovan výsledky v tto oblasti. Řadu z nich jsem potvrdil, v případě jsem dokonce našel nov. Nejednoznačn cesty (uzavřen i otevřen) se podařilo prozkoumat pro všech 35 moţných typů skokanů (nejsloţitější byla v tomto Zebra). V případě jednoznačných cest se to podařilo tměř tak (s vyjímkou několika případů, speciálně jezdce na 8×8, kde je však velmi pravděpodobn, ţe jde tţ o hodnoty maximální). sériovotahový pat (sriový pat, series direct stalemate ) - bílý vykoná bezprostředně za sebou určený počet tahů tak, aby posledním tahem dal pat druh straně. Označuje se sd=n , kde n je počet tahů. In a series direct stalemate (sd=n) White plays n moves to reach a position where Black is in stalemate. Základní pojmy z teorie grafů – Basic terms from Graph theory graf (graph) – je struktura, skládající se z uzlů, z nichţ někter dvojice uzlů jsou spojeny hranami. uzel (vertex) – je bod, ze kterho mohou vst hrany, kter jej spojují s jinými uzly. Z hlediska šachov pozice odpovídá kaţdý uzel jednomu poli na šachovnici. Celkový počet uzlů grafu odpovídá počtu polí na šachovnici, v případě šachovnice 8×8 dostáváme graf se 64 uzly. V textu občas používám termíny uzel nebo pole (podle kontextu) pro jedno a to samé. hrana (edge) – je spojnice mezi dvěma uzly. Z hlediska šachovho určují hrany moţn tahy kamenů z danho pole. 5 |
Menu
|