Úvod do deskových her v Linuxu

Tímto úvodním článkem začíná seriál o možnostech hraní abstraktních strategických deskových her v Linuxu. Obecně lze říci, že možnosti hraní těchto her v Linuxu jsou velmi dobré. Příčiny mohou být následující:

Tvůrci svobodného softwaru se pravděpodobně nadprůměrně zajímají o deskové hry. Třeba šachový program GNU Chess patří mezi jeden z vůbec prvních projektů sdružením GNU. V současnosti jenom samotné GNU oficiálně vyvíjí čtyři tituly (GNU Chess, XBoard, GNU Shogi a GNU Go).
Problematika vytváření programů hrajících deskové hry na velmi vysoké úrovni zasahuje do mnoha oblastí umělé inteligence, a proto je předmětem intenzivního vědeckého výzkumu na různých specializovaných pracovištích. Zde bych doporučil zajímavý web příslušných výzkumných skupin univerzity v Albertě. V akademickém prostředí se Linux těší mimořádné popularitě. Výsledné programy jsou naštěstí obvykle zveřejněny pod některou ze svobodných licencí.
Má-li programátor ambice maximálně demonstrovat herní sílu současné techniky, musí využít masivní paralelizace. Drtivá většina gridů, clusterů a superpočítačů běží v současnosti na Linuxu nebo jiném POSIXové systému (např. FreeBSD).

Uživatelské rozhraní a herní engine

Softwaru pro hraní deskových her se skládá z logicky oddělených celků. Uživatel se střetává s grafickým uživatelským rozhraní, které mimo jiné zobrazuje hrací desku, figury nebo časomíru a umožňuje nastavit parametry partie... Grafická uživatelská prostředí umožňují hru dvou (lidských) hráčů, ale již neobsahuje žádnou umělou herní inteligenci. Grafické uživatelské rozhraní se proto připojuje na herní engine, který integruje veškerou potřebnou umělou inteligenci. Protože se jedná o klasickou architekturu klienta a serveru, budu dále grafické uživatelské rozhraní označovat jen jako klient.

U většiny řešení zůstává engine samostatným programem, přičemž většina enginů navíc disponuje vlastním velmi primitivním textovým rozhraním pro hraní z terminálu. Vývoj herního enginu pochopitelně vyžaduje mnohem hlubší teoretické znalosti než vývoj klienta.

Další vývojáři mohou přepisovat knihovny zahájení, partie velmistrů, sbírat problémové úlohy... Takto pořízené záznamy přiložené k softwaru lze využít k samostatnému studiu. Navíc některé herní enginy se při počátečních tazích dokáží řídit nahranou knihovnou zahájení.

Standardy a formáty

Naštěstí jsou standardizovány všechny významné komunikační protokoly mezi klientem a herním enginem a i formáty ukládaní partií. K jednomu klientovi lze snadno připojovat různé herní enginy. Navíc jeden klient, protokol nebo souborový formát může nabízet podporu pro různé deskové hry. Ve svém oblíbeném klientu proto můžete hrát různé hry a zkoušet různé enginy.

XBboard

Například populární protokol pro různé deskové hry Chess Engine Communication Protocol (CECP) navrhl Tim Mann v rámci GNU šachového klienta XBoard. Tento rozšířený klient zvládá všechny podstatné druhy šachů a šachovnic. Vedle „západního“ šachu podporuje Xiangqi (Čínské šachy), Shogi (Japonské šachy), Makruk (Thajské šachy), původní formu Shatranj (šatranž) a další hry „šachového“ typu a jejich různé jejich varianty jako například verzi vytvořenou José Raúlem Capablancou.

Na dalším ilustračním obrázku jsou vidět dvě instance klienta Quarry. Klient vlevo zobrazuje hru Reversi na desce zvané othelier mezi dvěma enginy Rhino. Klient vpravo zobrazuje hru Go hranou enginem Fuego proti enginu GNU Go. Oba klienti při hraní odlišných her komunikují s enginy stejným standardizovaným protokolem Go text protocol (GTP).

Dvě instance klienta Quarry

I případné problémy s nepodporou formátů se dají často obejít. Na ilustračním obrázku se v klientovi gShogi pro Shogi (Japonské šachy) snažím neúspěšně zprovoznit engine GNU Shogi. Aplikace gShogi vyžaduje speciální Universal Shogi Interface (USI) protokol a GNU Shogi nabízí jen CECP protokol. Nekompatibilitu snadno vyřešení použitím speciálního konektoru mezi CECP a USI. (Ostatně defaultní engine v gShogi je téměř originální GNU Shogi s přikompilovaným konektorem.)

Neúspěšný pokus

Internetové herní servery

Weby herních serverů často obsahují klienta řešeného například java appletem. V těchto případech lze přistupovat na server z jakéhokoli počítače připojeného k Internetu. Není tedy vyžadována instalace herního softwaru. Běžnými funkcemi herních serverů jsou následující:

Umožňuje se zřízení účtu, uložení informací o hráči... Navíc se automaticky stanovuje výkonnostní rating hráčů z odehraných hodnocených partií.
Hráč si může odehrané partie stáhnout na svůj počítač.
Můžete zadat „automatickou výzvu“, kde stanovíte sílu požadovaného soupeře, čas hry... Nebo naopak v „seznamu výzev“ vybírat a zajímavé výzvy přijímat. U partií lze zpravidla dále nastavit, zda je veřejná a zda je partie hodnocená, nebo volná (např. možné vracení tahů), možnost komentování partie přihlížejícími...
Herní servery často nabízí nebo zprostředkovávají kvalitní nabídku doplňkových komerčních služeb. Konkrétně může jít o prodej specializované literatury nebo poskytování privátních placených lekcí velmi silnými hráči prostřednictvím herního serveru.

KGS Go Server

Ilustrace pochází z online herního serveru KGS Go Server. Okno zobrazuje nabídky k partii seřazené sestupně podle síly vyzyvatele.

Herní síla algoritmů

Pouze u několika velmi jednoduchých deskových her známe obecné výpočetně jednoduché řešení. (Příklad takové hry se silným řešením: Na desce je v mnoha přihrádkách různý počet kuliček. Hrají dva hráči. Při tahu vyberou přihrádku a odeberou nenulový počet kuliček. Kdo odebere všechny zbývající kuličky na desce, vyhrál. Řešení je poměrně překvapivé. Provede se operace binární XOR s počty kuliček v jednotlivých přihrádkách. Nenulový výsledek znamená vyhranou pozici, nulový výsledek znamená naopak prohranou pozici.) Se zvětšující se herní plochou a počtem kamenů obvykle prudce roste náročnost nalezení nejlepšího tahu. Při tomto zobecnění nalezení nejlepšího tahu ze zadané pozice je často například úloha třídy EXPTIME-complete (Go, Shogi, šachy, dáma...) nebo PSPACE-complete (Amazonia, Sudoku, Reversi...). U mnoha her byl dokázán jen horní odhad třídy složitosti.

Samozřejmě současné herní enginy neimplementují nejlepší možné algoritmy. V praxi vychází design enginů především z následujících myšlenek:

Prohledávání herního stromu: Základem je návrh kvalitní ohodnocovací funkce, která vrací ohodnocení pozice odhadující očekávaný výsledek hry z této pozice. Například výsledek -100 může reprezentovat téměř jistou výhru černého, výsledek 0 vyrovnané šance a výsledek 100 téměř jistou výhru bílého. S pomocí tohoto ohodnocení algoritmus identifikuje kandidáty na nejlepší posloupnosti tahů, které pak „prodlužuje“. Známými implementacemi této idee jsou algoritmy Minimax, Negascout, MTD-f...
Monte Carlo: Obecně se jako metoda Monte Carlo označují numerické postupy, které odhadují hodnotu nějaké veličiny s pomocí statistického zpracování velmi rozsáhlého souboru náhodně vygenerovaných vzorků. Herní engine na principu Monte Carlo má zabudovaný alespoň jeden extrémně rychlý „subengine“ (např. generátor náhodných tahů). S jejich pomocí generuje množství her a sleduje, které tahy zvyšují nebo snižují pravděpodobnost výhry. Algoritmus vybere tah, v němž se maximalizuje pravděpodobnost výhry. V praxi používané algoritmy jako například Upper Confidence bounds applied to Trees (UCT) při generování her upřednostňují tahy, které se v již vygenerovaných hrách osvědčily.

Dále se často aplikují postupy z různých oborů umělé inteligence. Mimo jiné jde o oblasti:

Hledání a rozpoznávání vzorů (pattern matching, pattern recognition): Engine nalézá v pozicích určité typické vzory. Identifikace vzorů může být využita při konstrukci ohodnocovací funkce, engine v databázi minulých partií může hledat podobnou pozici... Tento přístup hojně využívají i lidští hráči, alespoň tomu nasvědčuje význam přisuzovaný studiu partií velmistrů a výsledky experimentální psychologie (např. studie Adriaana de Groota).
Tvorba expertních systémů: Engine může využívat rozsáhlou množinu expertních znalostí. Například může jít o poznatek, že je velmi neobvyklé táhnout třikrát po sobě stejnou figurou.
Strojové učení a data-mining: Databáze partií velmistrů může být zvolena za tréninková data, jejichž zpracováním budou optimalizovány koeficienty v návrhu ohodnocovací funkce.

Síla programů v praxi

Hry bych rozdělil podle výkonnosti nejlepších enginů do následujících kategorií:

Program dosáhl úrovně, kdy již ani dokonalá hra nevynutí jeho porážku. Příkladem je Anglická dáma a aplikace Chinook.
Program je i na běžném hardwaru mnohem silnější než nejsilnější člověk. Příkladem je hra Reversi.
Běžnému osobnímu počítači dokáží konkurovat pouze nejsilnější hráči. Příkladem jsou šachy.
Úrovně nejsilnějšího programu se dá srovnat s úrovní běžného silnějšího amatérského hráče. Příkladem je hra Go.

Většina úspěchů současných nejlepších enginů vyplývá z hrubé výpočetní síly a schopnosti rychle vyhodnocovat velké množství pozic. Programy proto dominují v situacích vyžadující přesný taktický propočet, v koncovkách a při velmi rychlých hrách, kdy se člověk ocitá v časové tísni. Naopak člověk se spoléhá na hlubší pochopení fundamentálních principů příslušné hry.

Remíza

Například i naprostému začátečníkovi dojde, že na výše uvedeném diagramu černého od bílého oddělí neproniknutelná pěšcová zeď a černý proto nemůže nijak i přes značnou materiální převahu vynutit mat. Partie tedy skončí remízou, protože následujících padesát tahů nebude možné zajmout žádný kámen a ani učinit tah pěšcem. Prostým prohledáváním herního stromu by vzhledem k omezené výpočetní síle nebylo možné toto zjistit.

Dvojité fianchetto

Se znalostí slabin algoritmu lze snadno zvolit preferovat „proti-počítačové“ tahy. Konkrétně počáteční vývin dvojitým fianchettem se často považuje za strategii zvýhodňující lidského hráče.

Autorem obrázku šachové figurky v úvodu článku je dracos. Dílo je zveřejněno pod licencí Creative Commons BY-NC-SA.