Cram (hra) - Cram (game)
Nacpat je matematická hra hrál na listu milimetrový papír. Jedná se o nestrannou verzi Dominující a jediný rozdíl v pravidlech je, že každý hráč může umístit své domino v libovolné orientaci, ale výsledkem je velmi odlišná hra. Říkalo se mu mnoho jmen, včetně „plugg“ od Geoffrey Mott-Smith a „dots-and-pair“. Cram byl popularizován Martin Gardner v Scientific American.[1]
Pravidla
Hra se hraje na listu milimetrový papír, s vysledovatelnou sadou vzorů. Nejčastěji se hraje na obdélníkové desce, jako je čtverec 6 × 6 nebo a šachovnice, ale lze jej hrát i na zcela nepravidelném polygon nebo válcová deska.
Dva hráči mají sbírku domino které postupně umístí na mřížku. Hráč může umístit domino horizontálně nebo vertikálně. Na rozdíl od související hry o Dominující, možné tahy jsou pro oba hráče stejné, a Cram je pak nestranná hra.
Co se týče všech nestranných her, existují dvě možné konvence pro vítězství: v normální hře první hráč, který se nemůže hýbat, prohrává, a naopak v misère verze, vyhrává první hráč, který se nemůže hýbat.
Symetrická hra
 | Tato sekce ne uvést žádný Zdroje. (Července 2019) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) |
Vítězství strategie pro normální Cram je jednoduchý pro desky sudých sudých a sudých sudých desek. V případě sudého po druhém vyhrává druhý hráč symetrie hrát si. To znamená, že jakýkoli pohyb, který hráč 1 provede, má hráč 2 odpovídající symetrický pohyb napříč vodorovnou a svislou osou. V jistém smyslu hráč 2 „napodobuje“ tahy provedené hráčem 1. Pokud se hráč 2 řídí touto strategií, hráč 2 provede vždy poslední tah, a tím vyhraje hru.
V případě sudého po lichém vyhrává první hráč podobnou hrou symetrie. Hráč 1 umístí své první domino do středu dvou čtverců na roštu. Hráč 2 poté provede tah, ale hráč 1 může poté hrát symetricky, čímž zajistí výhru hráče 1.
Hra symetrie je v USA zbytečná strategie misère verze, protože v takovém případě by to pouze zajistilo hráče, že on ztrácí.
Normální verze
Zelená hodnota
Protože Cram je nestranná hra, Sprague – Grundyho věta označuje, že v normální verzi je jakákoli poloha Cram ekvivalentní a nim-heap dané velikosti, nazývané také Zelená hodnota. Některé hodnoty najdete v Vítězné způsoby pro vaše matematické hry, zejména 2 ×n deska, jejíž hodnota je 0, pokud n je sudé a 1 pokud n je zvláštní.
Strategie symetrie znamená, že desky sudých sudých sudů mají Grundy hodnotu 0, ale v případě sudých tabulek sudých sudých sudů to znamená pouze Grundovu hodnotu větší nebo rovnou 1.
| n × m | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|
| 4 | 0 | 2 | 0 | 3 | 0 | 1 |
| 5 | - | 0 | 2 | 1 | 1 | 1 |
| 6 | - | - | 0 | 5 | 0 | ≥1 |
| 7 | - | - | - | 1 | ≥1 | ? |
Známé hodnoty
V roce 2009 vypočítal Martin Schneider zelené hodnoty až na desky 3 × 9, 4 × 5 a 5 × 7.[2] V roce 2010 aplikovali Julien Lemoine a Simon Viennot na hru Cram algoritmy, které byly původně vyvinuty pro hru Klíčky.[3] Umožnilo jim to vypočítat zelené hodnoty až na desky 3 × 20, 4 × 9, 5 × 9, 6 × 7 a 7 × 7.[4]
Posloupnost aktuálně známých Grundyových hodnot pro 3 ×n desky, od n = 1 do n = 20 je: 1, 1, 0, 1, 1, 4, 1, 3, 1, 2, 0, 1, 2, 3, 1, 4, 0, 1, 0, 2. Neukazuje žádný zjevný vzorec.
V tabulce níže jsou uvedeny známé výsledky pro desky s oběma rozměry většími než 3. Protože hodnota an n × m deska je stejná jako hodnota a m × n desce, dáváme pouze horní část stolu.
Misère verze
Hodnota Misère Grundy
Misère Grundyova hodnota hry G je definována Conway v O číslech a hrách jako jedinečné číslo n takové, že G + n je druhým hráčem, který vyhrál v misère hře.[5] I když to vypadá velmi podobně jako obvyklá Grundyova hodnota v normální hře, není to tak silné. Zejména není možné odvodit misère Grundy-hodnotu souhrnu her pouze z jejich příslušných misère grundy-hodnot.
| n × m | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|
| 4 | 0 | 0 | 0 | 1 | 1 | 1 |
| 5 | - | 2 | 1 | 1 | ? | ? |
| 6 | - | - | 1 | ? | ? | ? |
Známé hodnoty
V roce 2009 Martin Schneider vypočítal misère grundy hodnoty až do 3 × 9, 4 × 6 a 5 × 5.[2] V roce 2010 Julien Lemoine a Simon Viennot rozšířili tyto výsledky až na desky 3 × 15, 4 × 9 a 5 × 7, spolu s hodnotou desky 6 × 6.[4]
Sled aktuálně známých hodnot Misère Grundy pro 3 ×n desek, od n = 1 do n = 15 je: 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1. Tato posloupnost je považována za periodickou období 3.[4]
V sousední tabulce jsou uvedeny známé výsledky misère u desek s oběma rozměry většími než 3.
Reference
- Berlekamp, Elwyn R.; Conway, John H.; Guy, Richard K. (2003). Vítězné způsoby pro vaše matematické hry. A K Peters, Ltd.
- ^ Gardner, Martin (1974). „Matematické hry: Cram, crosscram a quadraphage: nové hry s nepolapitelnými výherními strategiemi“. Scientific American. 230 (2): 106–108.
- ^ A b Das Spiel Juvavum, Martin Schneider, diplomová práce, 2009
- ^ Julien, Lemoine; Simon, Viennot (2010). "Nimbers jsou nevyhnutelní". arXiv:1011.5841 [math.CO ].
- ^ A b C Výpočtové záznamy normální a Misère Cram, Julien Lemoine a Simon Viennot
- ^ John H., Conway (2000). O číslech a hrách. A K Peters, Ltd.