Osmičková hra - Octal game

The osmičkové hry jsou třídou her pro dva hráče, které zahrnují odebírání žetonů (hracích kamenů nebo kamenů) z hromád žetonů. Byly studovány v kombinatorická teorie her jako zobecnění Nim, Kayles a podobné hry.^[1][2]

Osmičkové hry jsou nestranný což znamená, že každý tah, který je k dispozici jednomu hráči, je k dispozici i pro druhého hráče. Liší se od sebe počtem žetonů, které mohou být odstraněny v jednom tahu, a (v závislosti na tomto počtu), zda je povoleno odebrat celý tah hromadu, zmenšit velikost hromady nebo rozdělit hromadu na dvě hromady. Tyto varianty pravidel lze kompaktně popsat pomocí kódovacího systému osmičkový číslice.

Specifikace hry

Hraje se osmičková hra se žetony rozdělenými na hromady. Dva hráči se střídají v pohybu, dokud nejsou možné pohyby. Každý pohyb spočívá ve výběru pouze jedné z hromad a buď

• odebrání všech žetonů v hromadě, nezanechání žádné hromady,
• odebrání některých, ale ne všech tokenů, ponechání jedné menší hromady, nebo
• odebrání některých žetonů a rozdělení zbývajících žetonů na dvě neprázdné hromady.

Haldy jiné než vybraná hromada zůstávají nezměněny. Vyhrává poslední hráč, který se přestěhoval normální hra. Hru lze také hrát v misere hra, ve kterém poslední hráč, který se pohybuje, prohrává.

Hry, které se tímto způsobem hrají s hromadami, ve kterých jsou povolené pohyby pro každou hromadu určovány velikostí původní hromady, se nazývají Braní a lámání her v literatuře.^[1] Osmičkové hry jsou podmnožinou braní a rozbíjení her, ve kterých jsou povolené tahy určovány počtem žetonů odstraněn z hromady.

Osmičkový kód hry je zadán jako

0 . d₁ d₂ d₃ d₄ …,

kde osmičková číslice d_n určuje, zda má hráč po odebrání možnost ponechat nulu, jednu nebo dvě hromady n žetony z hromady. Číslice d_n je součet

• 1 pokud je povoleno ponechání nulové hromady, 0 jinak;
• 2 pokud je povoleno opustit jednu hromadu, 0 jinak; a
• 4 pokud je povolen odchod ze dvou hromad, jinak 0.

Nulové žetony se nepočítají jako hromada. Tedy číslice d_n je zvláštní, pokud je hromada n žetony mohou být zcela odstraněny, a to i jinak. Výsledkem specifikace jedné hromady je d_n platí pro odebírání n žetony z hromady větší než n. Výsledkem dvou haldy je d_n platí pro odstranění n žetony z hromady minimálně n+2 a zbytek rozdělit na dvě neprázdné hromady.

Osmičkové hry mohou umožnit rozdělení haldy na dvě části bez odstranění jakýchkoli žetonů pomocí číslice 4 nalevo od desetinné čárky. To je podobné jako při nastěhování Grundyho hra, což je rozdělení hromady na dvě nerovné části. Standardní osmičkový herní zápis však nemá moc vyjádřit omezení nerovných částí.

Jsou volány osmičkové hry pouze s konečným počtem nenulových číslic konečné osmičkové hry.

Obzvláště osmičkové hry

Nim

Nejzákladnější hra v kombinatorická teorie her je Nim, ve kterém může být z hromady odstraněn libovolný počet žetonů, přičemž za sebou zůstane nula nebo jedna hromada. Osmičkový kód pro Nim je 0.333…, který se v publikované literatuře vyskytuje jako

${displaystyle 0. {dot {3}}}$ ,

označit opakující se část jako v a opakování desetinného místa. Je důležité si uvědomit, že opakující se část nehraje stejnou roli jako v osmičkových zlomcích, protože hry

${displaystyle 0,0 {dot {7}}}$

a

${displaystyle 0,1}$

nejsou totožné, navzdory jejich rovnosti jako osmičkové zlomky.

Kayles

Hra Kayles je obvykle vizualizováno jako hraní s řadou n kolíky, ale mohou být modelovány hromadou n pulty. Jeden smí odebrat jeden nebo dva žetony z hromady a zbytek uspořádat na nulu, jednu nebo dvě hromady. Osmičkový kód pro Kayles je 0.77 .

Dawsonovy šachy

Dawsonovy šachy je hra vycházející ze šachové hádanky, kterou představuje Thomas Rayner Dawson v Caissa's Wild Roses, 1938.^[3] Hádanka byla postavena tak, že zahrnuje protilehlé řady pěšců oddělených jedinou hodností. I když hádanka není pokládána za nestranná hra, předpoklad, že zachycení je povinné, znamená, že pohyb hráče v jakémkoli souboru má za následek pouze odstranění tohoto souboru a jeho sousedů (pokud existují) z dalšího zvážení, přičemž se má pohybovat opačný hráč. Modelovat to jako hromadu n žetony, hráč může odstranit celou hromadu jednoho, dvou nebo tří žetonů, může libovolnou hromádku snížit o dva nebo tři žetony nebo může hromadu rozdělit na dvě části po odebrání tří žetonů. Dawsonův šach je tedy reprezentován osmičkovým kódem 0.137.

Dawson's Kayles

Ve hře 0.07, volala Dawson's Kayles, tah znamená odstranit přesně dva žetony z hromady a zbytek rozdělit na nulu, jednu nebo dvě hromady. Dawsonova Kayles je pojmenována pro (zjevnou) podobnost s Dawsonovými šachy v tom, že Dawsonova hromada Kayles n+1 žetony fungují přesně jako hromada Dawsonových šachů n žetony. O Dawsonově Kaylesovi se říká, že je první bratranec Dawsonových šachů.

Zobecnění na jiné základy

Osmičkové hry jako Nim, ve kterém každý pohyb transformuje hromadu na nulu nebo jednu hromadu, jsou volány kvartérní hry protože jediné číslice, které se objeví, jsou 0, 1, 2 a 3. Osmičkový zápis lze také rozšířit, aby zahrnoval hexadecimální hry, ve kterém číslice umožňují rozdělení hromady na tři části. Ve skutečnosti jsou možné libovolně velké základny. Analýza kvartérních, osmičkových a hexadecimálních her ukazuje, že tyto třídy her se od sebe výrazně liší,^[1] a chování větších základen neobdrželo tolik kontroly.

Nim-sekvence

The Sprague – Grundyho věta znamená, že hromada velikosti n je ekvivalentní a nim halda dané velikosti, obvykle se uvádí G (n). Analýza osmičkové hry pak spočívá v nalezení sekvence hodnot nim pro hromady rostoucí velikosti. Tato sekvence G (0), G (1), G (2) ... se obvykle nazývá nim-sekvence hry.

Všechno konečný dosud analyzované osmičkové hry ukázaly, že jejich posloupnost je nakonec periodická, a zda všechny konečné osmičkové hry jsou nakonec periodické, je otevřenou otázkou. Je uveden v seznamu Richard Guy jako důležitý problém v oblasti kombinatorické hry.^[4]

Výpočetní záznamy

Kompletní analýza osmičkové hry má za následek nalezení její periody a předperiody její sekvence nim. Je zobrazen v Vítězné způsoby pro vaše matematické hry že k prokázání toho, že konečná osmičková hra je periodická, je zapotřebí pouze konečný počet hodnot jejich posloupnosti, což otevřelo dveře výpočtům s počítači.

V průběhu let byly analyzovány osmičkové hry s maximálně 3 osmičkovými číslicemi. Existuje 79 netriviálních osmičkových her, z nichž bylo vyřešeno 14:

• .156 Jack Kenyon v roce 1967^[1]
• 0,356, 0,055, 0,644 a 0,165 Richarda Austina v roce 1976^[1]
• 0,16, 0,56, 0,127 a 0,376 Anil Gangolli a Thane Plambeck v roce 1989^[1]
• 0,454, .104, .106, .054 a .354 od Achima Flammenkampa v letech 2000 až 2002^[5]

I přes výpočet milionů hodnot Nim od Achima Flammenkampa zbývá 63 těchto her.^[5]

Reference