![]() ![]() |
ARCHIV |
|||||||||||||||||||||||||||||||||||||||
![]() ![]() ![]() ![]() ![]() ![]() |
|
Kámen | Pole | Index | Hodnota | Výsledek |
Bílý král | f3 | 21 | 21 | 21 |
První bílý střelec | e3 | 20 | 20 * 64 | 1 280 |
Druhý bílý střelec | d3 | 19 | 19 * 642 | 77 824 |
Černý král | e5 | 36 | 36 * 643 | 9 437 184 |
Bílý na tahu | 644 | 16 777 216 | ||
Suma | 26 293 525 |
Opačný převod z čísla na pozici bude analogický, číslo rozložíme na cifry v 64-kové soustavě a to budou indexy políček jednotlivých kamenů.
Vlastní algoritmus vygenerování databáze n kamenné koncovky už bude jednoduchý:
Máme-li vygenerovanou tabulku, je již velmi jednoduché napsat optimální algoritmus hry. Jedná se o prostý minimax do hloubky 1. Místo běžné ohodnocovací funkce se budeme dívat do tabulky. 0 znamená, že žádná ze stran nemůže vyhrát, tedy remíza. Kladná čísla jsou pozice vyhrané za bílého, čím dál od jedničky, tím dál od matu. Totéž platí s černým pro záporná čísla. V remízových pozicích pak můžeme spustit i klasický myslící algoritmus omezený na tahy, které nevedou k naší prohře. Jde jen o to, aby v remízových pozicích, kde ovšem o remízu bojuje soupeř, program nerezignoval na teoreticky marnou, ale prakticky proti reálnému soupeři často nadějnou snahu o výhru a nezahrál prostě jakýkoli neprohrávající tah. Například v těžké (pro 2 jezdce), ale remízové koncovce dámy proti dvěma jezdcům by program asi neměl nastavit dámu. To sice objektivně není chyba, neboť i koncovka krále a dvou jezdců proti samotnému králi je remízová, ale subjektivně to jistě chyba je a uživatel by to asi programu neodpustil.
Pokud si dáte tu práci a výše uvedený algoritmus pro generování tabulky koncovky naprogramujete, zjistíte, že ani na dnešních počítačích není dostatečně rychlý. Při jednoduché implementaci bez velkých optimalizací získáte na počkání jen (elementární) tříkamenné koncovky a přes noc i ty zajímavější čtyřkamenné. Dnes jsou přitom běžné kvalitní programy na PC vybavené kompletně vyřešenými šestikamennými koncovkami a případně i některými sedmikamennými. Soubory s vygenerovanými koncovkami zaberou řádově několik GB. Jednou z nejjednodušších a zároveň velmi účinných metod, jak výpočet zrychlit a zmenšit i objem vygenerovaných dat je využití nejrůznějších symetrií. 50% ušetříme, pokud jednotlivé koncovky budeme generovat jen pro jednu stranu tj. nikoliv celkem dvakrát: jednou pro bílého a jednou pro černého. Dále můžeme ušetřit překlápěním šachovnice. Pokud vyloučíme rošády, můžeme pozici ztotožnit s jejím osově souměrným obrazem, kdy osa vede mezi sloupci d a e. Generovat tedy budeme jen pozice, na nichž je bílý král na sloupcích a až d a jejich dvojčata budeme pomocí osové souměrnosti transformovat. V bezpěšcových koncovkách můžeme podobně překlápět i podle vodorovné osy mezi 4. a 5. řadou a dokonce i podle na hlavní diagonály a1 - h8. Bílý král tak bude vždy v trojúhelníku a1-d1-d4. Místo 64 možných polí tak zbude bílému králi pouze 10 polí, lze tedy očekávat díky osovým souměrnostem zhruba 6,4-násobné zrychlení a úsporu paměti při generování i při uložení výsledků.
V tabulce jakékoli koncovky se poměrně často a relativně pravidelně opakují číselné hodnoty. Je zřejmé, že data půjde úspěšně komprimovat téměř jakoukoli rozumnou metodou. Vzhledem ke způsobu využití je nutné, aby pro přečtení hodnoty z komprimované tabulky stačilo dekomprimovat jen nějaké malé okolí a nikoli celou tabulku.
V některých koncovkách je problém s pravidlem padesáti tahů. K výhře bychom potřebovali více než padesát tahů bez braní a tahu pěšcem. Některé jinak vyhrané pozice se s uvedeným pravidlem vyhrát prostě nedají. Jiné vyhrát jdou, ale místo nejkratší cesty k matu musíme sledovat nejkratší cestu do jednodušší vyhrané koncovky. Například pokud v koncovce dámy proti dvěma střelcům můžeme zvolit
bude náš algoritmus toužící po co nejrychlejším matu preferovat první variantu, ačkoli striktně vzato (pokud pravidlo 50 tahů chápeme opravdu jako součást pravidel šachu a nikoli jen jako ne zcela plnohodnotnou pomůcku proti nekonečným partiím) jde o chybu a správně by měl zvolit druhou variantu. Proto se někdy jako kritérium při generování tabulky volí nejen vzdálenost od matu, ale i vzdálenost k jednodušší vyhrané koncovce. Program pak nezahlásí: "Dávám mat 65. tahem.", ale: "Za 49 tahů přejdu do jednodušší vyhrané koncovky."
Databází koncovek celý seriál končí, přeji čtenářům hodně programátorské radosti a úspěchů s vlastními šachově-programátorskými experimenty.
Nejsou žádné diskuzní příspěvky u dané položky. Příspívat do diskuze mohou pouze registrovaní uživatelé. |
28.11.2018 23:56 /František Kučera
Prosincový sraz spolku OpenAlt se koná ve středu 5.12.2018 od 16:00 na adrese Zikova 1903/4, Praha 6. Tentokrát navštívíme organizaci CESNET. Na programu jsou dvě přednášky: Distribuované úložiště Ceph (Michal Strnad) a Plně šifrovaný disk na moderním systému (Ondřej Caletka). Následně se přesuneme do některé z nedalekých restaurací, kde budeme pokračovat v diskusi.
Komentářů: 1
12.11.2018 21:28 /Redakce Linuxsoft.cz
22. listopadu 2018 se koná v Praze na Karlově náměstí již pátý ročník konference s tématem Datová centra pro business, která nabídne odpovědi na aktuální a často řešené otázky: Jaké jsou aktuální trendy v oblasti datových center a jak je optimálně využít pro vlastní prospěch? Jak si zajistit odpovídající služby datových center? Podle jakých kritérií vybírat dodavatele služeb? Jak volit vhodné součásti infrastruktury při budování či rozšiřování vlastního datového centra? Jak efektivně datové centrum spravovat? Jak co nejlépe eliminovat možná rizika? apod. Příznivci LinuxSoftu mohou při registraci uplatnit kód LIN350, který jim přinese zvýhodněné vstupné s 50% slevou.
Přidat komentář
6.11.2018 2:04 /František Kučera
Říjnový pražský sraz spolku OpenAlt se koná v listopadu – již tento čtvrtek – 8. 11. 2018 od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5). Tentokrát bez oficiální přednášky, ale zato s dobrým jídlem a pivem – volná diskuse na téma umění a technologie, IoT, CNC, svobodný software, hardware a další hračky.
Přidat komentář
4.10.2018 21:30 /Ondřej Čečák
LinuxDays 2018 již tento víkend, registrace je otevřená.
Přidat komentář
18.9.2018 23:30 /František Kučera
Zářijový pražský sraz spolku OpenAlt se koná již tento čtvrtek – 20. 9. 2018 od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5). Tentokrát bez oficiální přednášky, ale zato s dobrým jídlem a pivem – volná diskuse na téma IoT, CNC, svobodný software, hardware a další hračky.
Přidat komentář
9.9.2018 14:15 /Redakce Linuxsoft.cz
20.9.2018 proběhne v pražském Kongresovém centru Vavruška konference Mobilní řešení pro business.
Návštěvníci si vyslechnou mimo jiné přednášky na témata: Nejdůležitější aktuální trendy v oblasti mobilních technologií, správa a zabezpečení mobilních zařízení ve firmách, jak mobilně přistupovat k informačnímu systému firmy, kdy se vyplatí používat odolná mobilní zařízení nebo jak zabezpečit mobilní komunikaci.
Přidat komentář
12.8.2018 16:58 /František Kučera
Srpnový pražský sraz spolku OpenAlt se koná ve čtvrtek – 16. 8. 2018 od 19:00 v Kavárně Ideál (Sázavská 30, Praha), kde máme rezervovaný salonek. Tentokrát jsou tématem srazu databáze prezentaci svého projektu si pro nás připravil Standa Dzik. Dále bude prostor, abychom probrali nápady na využití IoT a sítě The Things Network, případně další témata.
Přidat komentář
16.7.2018 1:05 /František Kučera
Červencový pražský sraz spolku OpenAlt se koná již tento čtvrtek – 19. 7. 2018 od 18:00 v Kavárně Ideál (Sázavská 30, Praha), kde máme rezervovaný salonek. Tentokrát bude přednáška na téma: automatizační nástroj Ansible, kterou si připravil Martin Vicián.
Přidat komentář
30.11.2022 9:32 /
Kyle McDermott
Hosting download unavailable
13.12.2018 10:57 /
Jan Mareš
Re: zavináč
2.12.2018 23:56 /
František Kučera
Sraz
5.10.2018 17:12 /
Jakub Kuljovsky
Re: Jaký kurz a software by jste doporučili pro začínajcího kodéra?
20.9.2018 10:04 /
Jan Ober
Jaký kurz a software by jste doporučili pro začínajcího kodéra?