Hackenbush - Hackenbush

Počáteční nastavení hry Hackenbush

Hackenbush je hra pro dva hráče vynalezená matematikem John Horton Conway.^[1] Může být přehráván v jakékoli konfiguraci barevných úsečky navzájem spojeny svými koncovými body a „pozemním“ vedením.

Hratelnost

Hra začíná tím, že hráči nakreslí „pozemní“ čáru (obvykle, ale ne nutně, vodorovnou čáru ve spodní části papíru nebo jiné hrací plochy) a několik úseček tak, že každý úsečka je spojena se zemí, buď přímo v koncovém bodě nebo nepřímo prostřednictvím řetězce dalších segmentů spojených koncovými body. V bodě se může setkat libovolný počet segmentů, a proto může existovat více cest k zemi.

Na svém tahu hráč „odstřihne“ (vymaže) jakýkoli segment čáry podle svého výběru. Každý segment čáry, který již není spojen se zemí žádnou cestou, „spadne“ (tj. Bude vymazán). Podle konvence normální hry z kombinatorické teorie her první hráč, který není schopen pohybu, prohrává.

Desky Hackenbush se mohou skládat z konečně mnoho (v případě „konečné desky“) nebo nekonečně mnoho (v případě „nekonečné desky“) úseček. Existence nekonečného počtu úseček neporušuje herní teorie za předpokladu, že hru lze dokončit v konečném čase, za předpokladu, že existuje pouze konečně mnoho úseček, které se přímo „dotýkají“ země. Na nekonečné desce může hra na základě rozložení desky pokračovat navždy za předpokladu, že se země dotýká nekonečně mnoho bodů.

Varianty

Modro-červená Hackenbush dívka, představený v knize Vítězné způsoby pro vaše matematické hry

V původní folklórní verzi Hackenbush může každý hráč snížit jakoukoli výhodu: protože se jedná o nestranná hra je poměrně jednoduché poskytnout úplnou analýzu pomocí Sprague – Grundyho věta. Verze Hackenbush zájmu o kombinatorickou teorii her jsou tedy složitější partyzánské hry, což znamená, že možnosti (tahy) dostupné jednomu hráči by nemuseli nutně být možnosti dostupné druhému hráči, pokud by byl na tahu, aby se pohyboval se stejnou pozicí. Toho lze dosáhnout jedním ze dvou způsobů:

• Původní Hackenbush: Všechny úsečky mají stejnou barvu a každý hráč je může oříznout. To znamená, že výplaty jsou symetrické a každý hráč má stejné operace na základě pozice na palubě (v tomto případě struktura losování)
• Modro-červený Hackenbush: Každý úsečka je zbarvena červeně nebo modře. Jeden hráč (obvykle první nebo levý hráč) smí řezat pouze segmenty modré čáry, zatímco druhý hráč (obvykle druhý nebo pravý hráč) smí řezat pouze segmenty červené čáry.
• Modro-červeno-zelený hackenbush: Každý úsečka je zbarvena červeně, modře nebo zeleně. Pravidla jsou stejná jako u modro-červeného Hackenbush s dodatečným ustanovením, že segmenty zelené čáry může oříznout kterýkoli hráč.

Blue-Red Hackenbush je pouze zvláštním případem Blue-Red-Green Hackenbush, ale stojí za zmínku zvlášť, protože jeho analýza je často mnohem jednodušší. Je to proto, že modro-červený hackenbush je tzv studená hra, což v zásadě znamená, že nikdy nemůže být výhodou mít první tah.

Analýza

Hackenbush se často používá jako ukázková hra pro demonstraci definic a konceptů v kombinatorická teorie her, počínaje jeho použitím v knihách O číslech a hrách a Vítězné způsoby pro vaše matematické hry některými ze zakladatelů pole. Ke konstrukci lze použít zejména modro-červený hackenbush neskutečná čísla jako Nimbers: finální modro-červené desky Hackenbush mohou být konstruovány dyadická racionální čísla, zatímco hodnoty nekonečných modro-červených desek Hackenbush odpovídají reálná čísla, řadové a mnoho dalších obecných hodnot, které nejsou ani jedno, ani druhé. Modro-červeno-zelený Hackenbush umožňuje konstrukci dalších her, jejichž hodnoty nejsou reálná čísla, jako např hvězda a všechny ostatní Nimbers.

Další analýzu hry lze provést pomocí teorie grafů tím, že tabuli považujeme za sbírku vrcholy a hrany a zkoumání cesty ke každému vrcholu, který leží na zemi (který by měl být považován za odlišný vrchol - neškodí identifikovat všechny základní body společně - spíše než čáru v grafu).

V nestranné verzi Hackenbush (verze bez barev specifikovaných hráčem) jej lze považovat za použití hromádek nim rozdělením hry do několika případů: vertikální, konvergentní a divergentní. Tato hra, která se hraje výhradně se svislými hromádkami liniových segmentů, označovaných také jako bambusové stonky, se přímo stává Nim a lze je přímo analyzovat. Odlišné segmenty nebo stromy dodávají hře další vrásky a vyžadují použití dvojtečka princip říkat, že když se větve spojí na vrcholu, lze je nahradit větvemi nerozvětveným stonkem o délce rovnající se jejich nim součtu. Tento princip mění zastoupení hry na základní verzi bambusových stonků. Poslední možnou sadou grafů, které lze vytvořit, jsou konvergentní, známé také jako libovolně zakořeněné grafy. Použitím principu fúze můžeme konstatovat, že všechny vrcholy v libovolném cyklu mohou být sloučeny dohromady, aniž by se změnila hodnota grafu.^[2] Libovolný konvergentní graf lze tedy také interpretovat jako jednoduchý bambusový stopkový graf. Kombinací všech tří typů grafů můžeme hře přidat složitost, aniž bychom kdykoli změnili jejich součet, a umožnit tak hře převzít strategie Nim.

Důkaz o dvojtečce

Princip Colon uvádí, že když se větve spojí na vrcholu, lze je nahradit větvemi nerozvětveným stonkem o délce rovnající se jejich nim součtu. Zvažte pevný, ale libovolný graf, G, a vyberte libovolný vrchol, X, v G. Nechat H₁ a H₂ být libovolné stromy (nebo grafy), které mají stejnou hodnotu Sprague-Grundy. Zvažte dva grafy G₁ = G_X : H₁ a G₂ = G_X : H₂, kde G_X : H_i představuje graf vytvořený připojením stromu H_i na vrchol X grafu G. Princip dvojtečky uvádí, že dva grafy G1 a G2 mají stejnou hodnotu Sprague-Grundy. Zvažte součet těchto dvou her jako na obrázku 5.4. Tvrzení, že G₁ a G₂ mít stejnou hodnotu Sprague-Grundy odpovídá tvrzení, že součet těchto dvou her má hodnotu Sprague-Grundy 0. Jinými slovy, máme ukázat, že součet G₁ + G₂ je P-pozice. Je zaručeno, že hráč vyhraje, pokud je druhým hráčem, který se nastěhuje G₁ + G₂. Pokud se první hráč pohne tím, že nasekne jednu z hran G v jedné z her pak druhý hráč naseká stejnou hranu G v druhé hře. (Takový pár tahů může smazat H₁ a H₂ z her, ale jinak H₁ a H₂ nejsou narušeni.) Pokud se první hráč pohybuje tím, že seká hrana dovnitř H₁ nebo H₂, pak hodnoty Sprague-Grundy z H₁ a H₂ již nejsou stejné, takže existuje pohyb H₁ nebo H₂ který udržuje hodnoty Sprague-Grundy stejné. Tímto způsobem budete mít vždy odpověď na každý jeho pohyb. To znamená, že uděláte poslední tah, a tak vyhrajete.^[3]

• 

  Příklad, kdy lze hru snížit pomocí Colon Principle

Reference

• John H. Conway, O číslech a hrách, 2. vydání, A K Peters, 2000.

externí odkazy

• Hackenstrings a 0,999 ... vs. 1
• Hackenbush na tužkách a papírových hrách