Odčítání hry - Subtraction game

v kombinatorická teorie her, a odečítací hra je abstraktní strategická hra jehož stav může být reprezentován a přirozené číslo nebo vektor čísel (například počet herních žetonů v hromadách žetonů nebo pozice dílků na palubě) a ve kterých povolené tahy tyto počty snižují.[1][2] Tahy hry často umožňují snížit libovolné číslo odečtením hodnoty od zadaného odečítací sadaa různé odečítací hry se liší v sadách odečítání.[1] Tyto hry se také liší v tom, zda vyhrává poslední hráč, který se přestěhoval ( konvence normální hry ) nebo ztrácí (misère ).[2] Další vítězná konvence, která byla také použita, je, že hráč, který se pohybuje na pozici se všemi čísly nuly, vyhrává, ale že jakákoli jiná pozice bez možných tahů je remíza.[1]

Příklady

Mezi příklady pozoruhodných her pro odečítání patří:

  • Nim je hra, jejíž stav se skládá z více hromád žetonů, jako jsou mince nebo zápalky, a platný tah odstraní libovolný počet žetonů z jedné hromádky. Nim má dobře známou optimální strategii, ve které je cílem při každém tahu dosáhnout hromádky, jejichž nim-součet je nula a tato strategie je pro Sprague – Grundyho věta optimální hry v nestranné hry. Když však hrajete pouze s jednou hromadou žetonů, optimální hra je triviální (jednoduše odeberte všechny žetony jediným tahem).[3]
  • Odečtěte čtverec je variace nim, ve které lze jediným tahem odebrat pouze čtvercový počet žetonů. Výsledná hra má netriviální strategii i pro jednu hromádku žetonů; the Furstenberg – Sárközyho věta znamená, že jeho výherní pozice mají mezi celými čísly nulovou hustotu.[4]
  • Fibonacci nim je další variace nim, ve které povolené tahy závisí na předchozích tazích na stejnou hromadu žetonů. Při prvním tahu na hromádku je zakázáno brát celou hromádku a při dalších tazích musí být odečtená částka maximálně dvojnásobná oproti předchozímu množství odstraněnému ze stejné hromádky.[5]
  • Wythoffova hra se hraje umístěním šachové královny na velkou šachovnici a jejím pohybem (při běžném způsobu šachové královny) směrem ke spodní straně, levé straně nebo levému dolnímu rohu desky. Tuto hru lze ekvivalentně popsat dvěma hromádkami žetonů, ze kterých může každý tah odebrat libovolný počet žetonů z jedné nebo obou hromádek a odebrat stejné množství z každé hromádky, když jsou obě hromádky sníženy. Má optimální strategii zahrnující Beatty sekvence a Zlatý řez.[6]

Teorie

Odečítání hry jsou obecně nestranné hry, což znamená, že sada tahů dostupných na dané pozici nezávisí na hráči, na jehož tahu se má pohybovat. U takové hry lze stavy rozdělit na -pozice (pozice, ve kterých vyhrává předchozí hráč, který se právě přestěhoval) a -pozice (pozice, ve kterých vyhrává další hráč v pohybu) a optimální strategie hraní hry spočívá v přechodu na a -pozice, kdykoli je to možné. Například s konvencí normální hry a jednou hromadou žetonů je každé číslo v odečítací sadě -pozice, protože hráč může vyhrát z takového čísla přesunem na nulu.[2]

U odečitatelných her s normálním hraním, ve kterých je více čísel, ve kterých každý tah snižuje pouze jedno z těchto čísel, a ve kterých redukce, které jsou možné z daného čísla, závisí pouze na tomto čísle a ne na zbytku stavu hry , Sprague – Grundyho věta lze použít k výpočtu „hodnoty nim“ každého čísla, čísla představujícího ekvivalentní pozici ve hře nim, takže hodnota celkového stavu hry je nim-součet jejích hodnot nim. Tímto způsobem lze optimální strategii pro celkovou hru snížit na výpočet hodnot nim pro zjednodušenou sadu pozic hry, tedy těch, ve kterých je pouze jedno číslo.[7] Hodnoty nim jsou pro nulu -pozice a nenulové pro -pozice; podle věty o Tom Ferguson, pozice s jedním číslem s hodnotou nim jedna jsou přesně čísla získaná přidáním nejmenší hodnoty v odečítací sadě k -pozice. Výsledek Fergusona vede k optimální strategii v odebíracích hrách s více hromádkami, s malou změnou oproti běžné herní strategii.[8]

Pro odečítací hru s jedinou hromadou žetonů a pevnou (ale možná nekonečnou) sadou odčítání, pokud má sada odčítání mezi svými členy libovolně velké mezery, pak sada -pozice hry jsou nutně nekonečné.[9] Pro každou odečítací hru s konečnou odečítací sadou jsou hodnoty nim ohraničeny a obě oblasti do -pozice a -pozice a posloupnost hodnot nim jsou nakonec periodické. Období může být výrazně větší než maximální hodnota v odečítací sadě, ale je maximálně .[10] Existují však nekonečné sady odčítání, které produkují ohraničené nim-hodnoty, ale neperiodickou posloupnost těchto hodnot.[11]

Složitost

U odečítacích her s pevnou (ale možná nekonečnou) odečítací sadou, jako je odečtení čtverce, se rozdělení do P-pozic a N-pozic čísel až do dané hodnoty lze vypočítat včas . Hodnoty nim všech čísel až lze vypočítat včas kde označuje velikost odečtené sady (až do ) a označuje největší hodnotu nim vyskytující se v tomto výpočtu.[12]

Pro zobecnění odečtených her hraných na vektorech přirozených čísel se sadou odčítání, jejichž vektory mohou mít kladné i záporné koeficienty, je to nerozhodnutelný problém zjistit, zda dvě takové hry mají stejné P-pozice a N-pozice.[13]

Viz také

Poznámky

  1. ^ A b C Golomb (1966).
  2. ^ A b C Berlekamp, ​​Conway & Guy (2001) „Odčítání her“, s. 83–86.
  3. ^ Bouton (1901–1902); Golomb (1966); Berlekamp, ​​Conway & Guy (2001) „Green hackenbush, hra nim a nimbers“, str. 40–42.
  4. ^ Golomb (1966); Eppstein (2018)
  5. ^ Whinihan (1963); Larsson & Rubinstein-Salzedo (2016)
  6. ^ Wythoff (1907); Coxeter (1953)
  7. ^ Golomb (1966); Berlekamp, ​​Conway & Guy (2001), „Hry s hromadou“, s. 82.
  8. ^ Ferguson (1974), str. 164; Berlekamp, ​​Conway & Guy (2001) „Fergusonův párovací majetek“, s. 86.
  9. ^ Golomb (1966), Věta 4.1, str. 451.
  10. ^ Golomb (1966), Příklad (a), s. 454; Althöfer & Bültermann (1995)
  11. ^ Larsson & Fox (2015).
  12. ^ Eppstein (2018).
  13. ^ Larsson & Wästlund (2013).

Reference