přejít na obsah přejít na navigaci

Linux E X P R E S, Úvod do deskových her v Linuxu

Vera

Úvod do deskových her v Linuxu

kun.png

V únoru se budeme věnovat klasickým deskovým hrám. V prvním díle se dozvíte, jak to všechno vlastně funguje, jaké jsou standardy a formáty... zkrátka na to půjdeme zevnitř ven.


reklama

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 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 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 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 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 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 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.

Nahoru

(Jako ve škole)
Průměr: 1,00 | Hodnotilo: 5
 

Top články z OpenOffice.cz

Příspěvky

Úvod do deskových her v Linuxu
lzap 7. 02. 2011, 08:40:37
Odpovědět  Odkaz 
Nejedná se tak ani o slabinu vlastního výpočetního algoritmu, ale o chybějící záznam v tzv. databázi zahájení. Počítačové šachové programy mají databázi velkého množství nejvíce používanýh tahů v zahájení (doslova jich znají miliony). U jednotlivých pozic mají již předpočítané výsledky, takže "šetří" čas. Nemusejí tedy přemýšlet a ihned vracejí tahy bez počítání. Takovým fianchettem (nebo jakýmkoliv tahem "mimochodem") tuto databázi "vyřadíte" a počítač musí hned od druhého tahu "ztrácet čas" výpočty.
František Bártík Re:Úvod do deskových her v Linuxu
František Bártík 7. 02. 2011, 13:26:45
Odpovědět  Odkaz 
Jenomže popisovaný efekt se projeví i v situaci, kdy není použita knihovna zahájení. Dvojité fianchetto vede k jinému typu pozic v zahájení a střední hře než obvyklý vývin střelců přes centrum. Obecně použití dvojitého fianchetta:

-zvyšuje počet variant, což vede například k Vámi zmíněnému snížení výhody rozsáhlé knihovny zahájení,
-zpomaluje rychlost hry, klade důraz na dlouhodobou strategii,
-vytváří komplexní pozice, na kterých ohodnocovací funkce je méně účinná
Re:Re:Úvod do deskových her v Linuxu
lzap 7. 02. 2011, 21:35:05
Odpovědět  Odkaz 
Nemyslím si, že by se to dalo takto paušalizovat až do střední hry. Mimochodem co je to komplexní pozice? Jestli tím myslíte uzavřenou pozici, tak ty počítačům naopak vyhovují (nedělají chyby v materiálu).

Nicméně Fianchetta jsou obecně proti počítačům používána, to je pravda. Podle mého názoru vedou naopak k otevřeným pozicím, kde se lépe dá využít strategie. Tam mají lidé většinou navrch.
František Bártík Re:Re:Re:Úvod do deskových her v Linuxu
František Bártík 9. 02. 2011, 07:14:09
Odpovědět  Odkaz 
Nezabývám se programováním nebo hraním šachů, takže reprodukuji jen názory uvedené v různých článcích o umělé inteligenci. Stanovení konkrétní protipočítačové strategie záleží na času na tah (resp. rozsahu výpočtů na jeden tah) a na spoustě dalších věcí.
Úvod do deskových her v Linuxu
e.xitu.s 7. 02. 2011, 16:10:51
Odpovědět  Odkaz 
Chtěl bych se zeptat, neví někdo jestli existuje multiplayerová šachová hra na Linuxu? Byl bych za ni moc vděčný :)
Re:Úvod do deskových her v Linuxu
lzap 7. 02. 2011, 21:18:34
Odpovědět  Odkaz 
Internet? brainking.com třeba

Jinak v Linuxu samozřejmě funguje největší komunitní šachová síť na světě FICS (http://www.freechess.org). Existuje spoustu klientů, třeba právě pro zmíněný XBoard (v recenzi na obrázku). Pozor - zprovoznění nevhodné pro začátečníky, ale na druhou stranu až to rozchodíte, tak si pořádně zahrajete.
Re:Re:Úvod do deskových her v Linuxu
e.xitu.s 8. 02. 2011, 17:01:17
Odpovědět  Odkaz 
Díky mnohokrát!
Úvod do deskových her v Linuxu
ddo 8. 02. 2011, 23:13:28
Odpovědět  Odkaz 
Ako nainštalovať Fuego pod ubuntu?
František Bártík Re:Úvod do deskových her v Linuxu
František Bártík 9. 02. 2011, 06:58:32
Odpovědět  Odkaz 
Hrou go se bude monotematicky zabývat jeden z budoucích dílu seriálu o deskových hrách (pravděpodobně vyjde za tři týdny v pondělí). Tuším, že Fuego není v distribučním repozitáři Ubuntu. Kompilace Fuega vyžaduje C++ boost knihovny. Návod by měl být uveden ve zdrojácích http://fuego.sourceforge.net/ . Pro rozumnou herní sílu na normálním gobanu 19x19 se musí navíc použít nějaká databáze fuseki (např. http://gnugo.baduk.org/fuegoob.htm ). Engine je spustitelný soubor, který se v grafickém klientovi vybere; např. ve zmiňovaném Quarry přes tlačítko "manage engine list".
Úvod do deskových her v Linuxu
ddo 9. 02. 2011, 09:07:19
Odpovědět  Odkaz 
Ďakujem za odpoveď. Už teraz sa teším na pokračovanie.
Martin Vancl Úvod do deskových her v Linuxu
tuxmartin 9. 02. 2011, 13:56:12
Odpovědět  Odkaz 
Nejzajimavejsi je stejne hrat sachy pres jabber :-)

http://tkabber.jabber.ru/files/screenshots/tkabber-plugins-chess.png
Re:Úvod do deskových her v Linuxu
e.xitu.s 9. 02. 2011, 18:18:06
Odpovědět  Odkaz 
Jo, ale kdybych tam měl nějaké kontakty :D...
Úvod do deskových her v Linuxu
Mira 12. 02. 2011, 17:01:50
Odpovědět  Odkaz 
> Běžnému osobnímu počítači dokáží konkurovat pouze nejsilnější hráči.
> Příkladem jsou šachy.

Tohle platilo mozna pred par lety. Kdyz si clovek dneska vezme nejaky lepsi engine jako je Houdini nebo Rybka, tak ani na osobnim pocitaci ti nejlepsi hraci nemaji sanci. Obcas se bodovat da, ale ne vyhravat. Jedna z moznosti jak porazet pocitace, je nechat hrat engine z handicapem, napr. bez pesce nebo jezdce.
Smozrejme porad existuji slabsi enginy a clovek si s nimi muze krasne zahrat.

Přidat názor

Nejsou podporovány žádné značky, komentáře jsou jen čistě textové. Více o diskuzích a pravidlech najdete v nápovědě.
Diskuzi můžete sledovat pomocí RSS kanálu rss



 
 

František Bártík

Soustředím se na problémy, které vyžadují kreativní přístup anebo využití teoretických znalostí. Orientuji se na svobodná řešení a baví mě učit se nové věci. Neváhejte a oslovte mě s Vaším zajímavým pracovním zadáním.


  • Distribuce: debian a odvozená distra
  • Grafické prostředí: GNOME
  • Hodnocení autora: *

| blog