Havannah - Havannah
Havannah je hráč pro dva hráče abstraktní strategie desková hra vynalezl Christian Freeling. Patří do rodiny her, které se běžně nazývají připojení hry; mezi jeho příbuzné patří Hex a TwixT. Havannah má „propracovanou a rozmanitou strategii“ a nejlépe se hraje na šestihranné desce základny-10, 10 hex buněk na stranu.[1]
Tato hra byla vydávána po dobu v Německu autorem Ravensburger, s menší deskou base-8 vhodnou pro začátečníky. V současné době je vyráběn pouze Hexboards.[2]
Pravidla hry
Jeden hráč hraje jako černý; druhý hraje jako bílý. Bílá začíná, poté se pohyby střídají. Pravidla jsou následující:
- Každý hráč položí na hrací plochu za každý tah jeden kámen své barvy.
- Kameny se nikdy nepohybují, nezachycují ani jinak nemění.
- Hráč vyhraje, když dokončí jednu ze tří různých struktur z nepřerušených linií nebo cest spojených kamenů, všechny jejich barvy:
- A prsten je smyčka kolem jedné nebo více buněk (bez ohledu na to, zda jsou obklíčené buňky obsazeny jakýmkoli hráčem nebo prázdné[3]);
- A most, který spojuje libovolné dvě ze šesti rohových buněk desky;
- A Vidlička, který spojuje libovolné tři hrany desky; rohové body se nepovažují za části hrany.
Příklad všech tří výherních kombinací je uveden výše. Struktura ve středu desky je prsten; konstrukce na levé straně je vidlice; konstrukce na pravé straně je most.
Vzhledem k tomu, že první hráč, který se pohybuje v Havananě, má zřetelnou výhodu, pravidlo koláče je obecně implementován pro spravedlnost. Toto pravidlo umožňuje druhému hráči zvolit si, zda má změnit pozici s prvním hráčem poté, co první hráč provede první tah.[4]
Hráči s různou silou mohou i nadále hrát zajímavou hru, když slabšímu hráči (jako bílému) je povoleno umístit na první kolo dva nebo více kamenů.
Rozdíl ve srovnání s Hex
V Hexu, když je hrací deska zcela zaplněna, bude mít právě jeden hráč výherní spojení; v Havannah bude mít úplně vyplněná hrací plocha obvykle více než jednu výherní strukturu (ale hra končí první výherní strukturou).
Na rozdíl od Hexu jsou v Havannah remízy technicky možné, v praxi jsou extrémně vzácné. Mezi lidskými hráči byla známá jedna remíza.[5]Taktiky se zvládají mnohem snáze než strategie a rozdíly v úrovni hraní jsou značné.
Počítač Havannah
V roce 2002 Freeling nabídl cenu 1 000 eur, která byla k dispozici do roku 2012, za jakýkoli počítačový program, který by ho dokázal porazit i v jedné hře z deseti her. Po mnoho let počítačové programy daleko zaostávaly za lidskými hráči. Od roku 2010 však platí několik programů pro hraní Havannah Hledání stromu v Monte Carlu techniky vedoucí k výraznému zlepšení síly hry. „Havannah Challenge 2012“ se konala ve dnech 15. – 19. Října 2012, během nichž Freeling odehrál deset her proti třem nejsilnějším dostupným programům na hraní v Havannah, přičemž proti každému soupeři hrál (alespoň) jednu hru jako černou a jednu jako bílou.[6] Freeling tuto výzvu ztratil, když musel odstoupit proti bílé hře proti programu Lajkonik.
Do roku 2019 byli nejlepší lidé stále mnohem silnější než počítače. Nicméně, MetaTotoro, založený na Polygames[7] (open-source projekt, původně vyvinutý Výzkum umělé inteligence na Facebooku a několik univerzit[8]), vyhrál proti lidskému hráči s nejlepší ELO hodností LittleGolem, který byl také vítězem různých turnajů.
Tohoto výsledku bylo dosaženo stejným programem, jaký byl použit k bití nejlepších lidí Hex. Jedná se o algoritmus založený na nulovém učení, stejně jako v AlphaZero, ale s novinkami: invariance BoardSize díky plně konvolučním neuronovým sítím (jako v U-Net) a globálnímu sdružování. To umožňuje růst architektury, což znamená, že se program může učit na malé desce a poté extrapolovat na velké desce.[9]
Výpočetní složitost
Řešení Havannah je PSPACE - kompletní vzhledem k velikosti vstupního grafu.[10] Důkaz je snížením z zobecněná geografie a je založen na použití ring-threats k reprezentaci geografického grafu. Podrobně, protože Lichtenstein a Sipser prokázali, že generalizovaná geografie zůstala tvrdá na PSPACE, i když je graf pouze bipartitní a stupně nanejvýš 3, z takového grafu zbývá pouze zkonstruovat ekvivalentní pozici Havannah, čehož je dosaženo konstrukcí různých gadgetů v Havannah.
Reference
- ^ Handscomb, Kerry, ed. (Zima 2002). "Přední kryt". Abstraktní hry. Nakladatelství Carpe Diem (12). ISSN 1492-0492.
- ^ Hexboardy
- ^ Jak objasnil Freeling v http://www.mindsports.nl/index.php/arena/havannah/49-havannah-rules; Schmittbergerova kniha mylně uvádí, že prsten by měl obklopovat alespoň jednu prázdnou buňku.
- ^ Schmittberger, R. Wayne (1992), "Havannah", Nová pravidla pro klasické hry, John Wiley & Sons, Inc., str.116–17, ISBN 978-0471536215
- ^ "Malý Golem".
- ^ „Člověk proti počítači: 7-3 - tisková zpráva“.
- ^ facebookincubator / Polygames, Facebook inkubátor, 2020-05-28, vyvoláno 2020-05-29
- ^ „Open-sourcing Polygames, nový rámec pro trénování robotů AI prostřednictvím hraní hry“. ai.facebook.com. Citováno 2020-05-29.
- ^ Cazenave, Tristan; Chen, Yen-Chi; Chen, Guan-Wei; Chen, Shi-Yu; Chiu, Xian-Dong; Dehos, Julien; Elsa, Maria; Gong, Qucheng; Hu, Hengyuan; Khalidov, Vasil; Li, Cheng-Ling (2020-01-27). "Polygames: Vylepšené nulové učení". arXiv:2001.09832 [cs.LG ].
- ^ Bonnet, Édouard; Jamain, Florian; Saffidin, Abdallah (14. srpna 2013). Havannah a TwixT jsou kompletní pro systém PSPACE. 8. mezinárodní letiště Konf. na počítačích a hrách. Keio University, Jokohama, Japonsko. arXiv:1403.6518. doi:10.1007/978-3-319-09165-5_15.
externí odkazy
- Oficiální stránka MindSports.nl
- Havannah článek na Senseiova knihovna
- Havannah na BoardGameGeek