Nim hry

Desková hra Nim
games Tato hra je volným dílem

Formát	rozličný
Hráči	2
Stáří	od 5 let
Oznámené trvání	asi 5 minut

Klíčové údaje

fyzická schopnost

rozhodnutí o reflexi

Ano

generátor
šancí

informace. kompl.
a perfektní

Ano

K Nim hry jsou hry čistého strategie , se dvěma hráči. Existuje několik variant. Hrají se se semeny, kuličkami, žetony, zápalkami nebo jiným snadno manipulovatelným předmětem.

Příklady

Mnoho her Nim se hraje s jednou nebo více hromadami předmětů (například zápasy), přičemž každý hráč upravuje jednu nebo více hromádek podle přijatých pravidel. Pojďme si podrobně vysvětlit verzi použitou v emisi Fort Boyard , taková hra představuje souboj hole proti mistrovi temnoty (hromada obsahuje 20 zápasů). Tato hra spočívá v odebrání 1, 2 nebo 3 hokejek v každém kole. Vítězem je ten, kdo může hrát jako poslední. Zde je příklad hry: 20 -> 19 -> 16 -> 13 -> 12 -> 10 -> 8 -> 5 -> 4 -> 3 -> 0

U této hry je strategií opustit pokaždé - pokud je to možné - počet předmětů, který je násobkem 4: jedná se o výherní pozice. Pak vidíme, že soupeř nebude schopen udělat totéž.

Existují i jiné varianty:

Můžeme si představit variantu verze Fort Boyard, kde ten, kdo vezme poslední objekt, ztratí, strategií je ponechat několik objektů shodných s 1 modulo 4 (to znamená: 1, 5, 9, 13 .. .). Ve skutečnosti se vracíme k předchozímu případu tím, že vezmeme v úvahu, že cílem hry je získat předposlední objekt.
Klasickou hru Nim nebo hru Marienbad proslavil film Alaina Resnaise z roku 1961 , loni v Mariánských Lázních . Skládá se z několika hromádek. Každý hráč si zvolí hromádku, kterou si zvolí, a z této hromádky vezme počet zápasů podle svého výběru.
Hra Grundy je hrán tím, že oddělí jednu ze svazku ve dvou hromadách různých velikostí, dokud existuje jen vrší jeden nebo dva předměty.
Hra Wythoff se hraje na dvě hromádky. Každý hráč sníží o stejný počet předmětů obě hromádky najednou, jinak sníží jednu hromádku o počet předmětů, které chce.

Také triviální hra Nim (nebo hra Nim s jednou hromadou) sestává z jedné hromady zápasů. Když je řada na nich, každý hráč si vezme požadovaný počet zápasů. Vítězná strategie pro prvního hráče je vyhrát všechny zápasy. Tato hra je triviální a má teoretický zájem.

Dějiny

Počátky jsou pravděpodobně velmi staré. První stopy jsou hlášeny v Číně pod názvem fan-tan , v Africe je známá pod názvem tiouk-tiouk . Současný název pochází z německého slova Nimm, což znamená „vezměte si!“ „Mohlo by to ale také pocházet z anglického slova WIN („ wins! “), Protože grafickým převrácením se slovo WIN stává NIM . Současný název dal hře anglický matematik Charles Leonard Bouton v roce 1901, když našel algoritmus umožňující výplatu.

Na světové výstavě v New Yorku v roce 1940 vystavila společnost Westinghouse Electric Corporation stroj s názvem Nimatron , který hrál Nimovu hru. Od 11. května 1940 do 27. října 1940 byl stroj schopen porazit jen malý počet účastníků; ti, kteří vyhráli, dostali minci označenou „Nim Champ“. V roce 1951 je Nimrod , který přebírá koncept Nimatronu, počítač , který vám umožňuje hrát Nimovu hru. Jeho původním účelem je však vychloubat Ferrantiho dovednosti v oblasti počítačového designu a programování , spíše než bavit .

Cíl hry

Každou hru hrají postupně dva lidé. Šance nezasahuje. To obvykle zahrnuje přesun nebo vyzvednutí předmětů podle pravidel, která naznačují, jak se pohybovat z jedné pozice hry do druhé, čímž se zabrání cyklickému opakování stejných pozic. Počet pozic je u konce a hra nutně končí, přičemž hráč již nemůže hrát jako poražený (nebo podle určitých variant vítězem).

Vítězná strategie

Nimovy hry jsou soubojové hry s nulovým součtem (dva hráči, jeden vítěz a jeden poražený, žádná remíza není možná), což odpovídá přesunu z jednoho vrcholu do druhého orientovaného grafu bez obvodu , jehož vrcholy představují různé možné polohy a hrany přechody z jedné pozice do druhé. Ukazuje se, že existuje optimální strategie, přičemž různé pozice hry jsou rozděleny do dvou podmnožin, vítězných pozic a pozic prohrávajících.

Ty jsou definovány rekurzivně následovně, v případě, že hráč, který již nemůže hrát, prohrál:

Konečné pozice (ze kterých již nelze hrát) vyhrávají, protože hráč, který dosáhne jednoho, brání svému soupeři ve hře a vyhrává hru.
Pozice ztrácí, pokud dojde k tahu, který vede k vítězné pozici. Pokud hráč dosáhne pozice, která prohrává, může jeho soupeř dosáhnout pozice vítězná.
Nefinální pozice je vítězná, pokud bez ohledu na tah, který hráč hraje, dorazí na prohrávající pozici. Pokud hráč dosáhne vítězné pozice, jeho soupeř bude muset jít do pozice prohrávající.

Posunutím konečných pozic tedy můžeme postupně určovat stav každé pozice. Optimální strategií je pak přesun z jedné výherní pozice do druhé.

Stanovení vítězných pozic v případě složitého grafu využívá pojem Grundyho čísla nebo nimberu . To je definováno takto:

Zelené číslo konečné pozice se rovná 0.
Zelené číslo dané pozice je nejmenší kladné nebo nulové celé číslo, které se neobjevuje v seznamu zelených čísel pozic bezprostředně následujících za danou pozicí.

Vítězné pozice jsou ty s nulovým zeleným číslem. Ve skutečnosti, počínaje takovou pozicí, bez ohledu na pohyb, který člověk hraje, se člověk dostane na pozici, jejíž Grundovo číslo není nula (ztrácí pozici). Naopak, počínaje pozicí prohrávající, je možné zahrát alespoň jeden tah, který vede k pozici, kde je počet Grundy nulový (vítězná pozice).

Součet Nimových her

Součet Nim her nazýváme hraním několika Nim her současně. Každý hráč si zase vybere, kterou hru Nim chce hrát, a odehraje tah z této hry. Součet hra končí, když hráč není schopen hrát žádnou z jednotlivých her Nim. To znamená, že klasická hra Nim nebo herní Mariánských v n haldy je součtem n hry Nim triviální.

The Sprague-Grundy theorem explains how to determine the winner positions of a sum of Nim sets, know the winner positions of each individual Nim game. Zelené číslo libovolné pozice součtu hry se ve skutečnosti získá rozložením zelených čísel pozic každé jednotlivé hry na binární a následným použitím exkluzivní funkce OR na číslice stejné pozice všech těchto čísel. Dostaneme binární číslo, jehož hodnota je Zelené číslo součtu herní pozice.

Tento jev je ilustrován v následujícím odstavci.

Klasická hra Nim

Klasická verze hry Nim se hraje s několika hromadami, z nichž každá se skládá z několika žetonů, pěšců nebo zápasů. Každý hráč na svém tahu může odstranit tolik pěšců, kolik si přeje, ale po jedné hromadě najednou. Vítězem je ten, kdo odstraní posledního pěšce (tzv. „Mizérská“ verze je místo, kde hráč, který vezme posledního pěšce, je poražený. Dá se z toho snadno odvodit).

Jelikož tato sada je součtem triviálních jednořadých Nim sad a Grundovo číslo každého jednotlivého stacku je počet pěšců v tomto stacku, získáme Grundovo číslo pozice vyjádřením počtu pěšců v každém stacku v binárním formátu a vytvořením součtu výlučných OR nebo XOR, (také uvedeno ⊕) z těchto čísel. Pozice s hodnotou 0 vždy vyhraje pro toho, kdo uspěje, pozice s hodnotou jinou než 0 vždy prohraje.

Vezměme si příklad hry začínající třemi hromádkami A, B a C, hromádkou A obsahující 3 pěšce, hromádkou B 4 pěšci a hromádkou C 5 pěšců. Pak máme:

0112 310 Pile A 1002 410 Pile B 1012 510 Pile C --- 0102 210 Nim-somme X des piles A, B et C: 3 ⊕ 4 ⊕ 5 = 2

Vítězná strategie spočívá v opuštění soupeře pozice, jejíž Nim-součet X se rovná 0. To je vždy možné v případě, že jeden začíná z pozice, kde je Nim-součet odlišný od 0, nemožné, když začneme od pozice, jejíž Nim-součet je 0. Zde stačí z hromady A (která nyní obsahuje pouze jednoho pěšce) odstranit například dva pěšce, aby se dospělo k:

0012 110 Pile A 1002 410 Pile B 1012 510 Pile C --- 0002 010 Nim-somme X des piles A, B et C: 1 ⊕ 4 ⊕ 5 = 0

K systematickému nalezení tahu ke hře postačí sestrojit součet XOR každé z hromádek s číslem X. Začněme znovu například z našich hromádek A = 3 = 011 2 , B = 4 = 100 2 a C = 5 = 101 2 originál a přidejte X, které jsme našli (X = 2 = 010 2 ):

A ⊕ X = 3 ⊕ 2 = 1 [Znak (011) ⊕ (010) = 001] B ⊕ X = 4 ⊕ 2 = 6 C ⊕ X = 5 ⊕ 2 = 7

Jediný stack, jehož množství klesá, je stack A. Musíme tedy snížit A na toto číslo, to znamená na 1 jediného pěšce, a proto stáhnout dva pěšce z A, což je přesně to, co jsme udělali.

Jedna z nejklasičtějších variant spočívá v omezení počtu pěšců, které lze vzít z každého stohu, na maximálně k pěšců. Předchozí metoda platí za předpokladu, že Grundovo číslo každé haldy je bráno jako počet objektů modulo (k + 1).

Program

V roce 1977 , manuál k programovatelné kalkulačce HP-25 zahrnoval hru s názvem Nimb . Hra začala 15 zápasy a každý hráč si mohl postupně odnést 1, 2 nebo 3. Kdokoli vzal poslední, ztratil. Program, 49 kroků , hrál druhý a použil vítěznou strategii, která nepřipustila žádné chyby u jeho soupeře.

Poznámky a odkazy

Lisa Rougetet, Mnoho předků hry Nim , Pour la Science, říjen 2012, č. 420, str. 80-85
J.-P. Delahaye, Magické strategie v zemi Nim , Pour la Science, březen 2009, č. 307, s. 88-93
Rudolf Flesch , Umění jasného myšlení , New York, Harper and Brothers Publishers,1951, str. 3
„ ExpoMuseum / Světová výstava v New Yorku, 1939–40 “ , na www.expomuseum.com (přístup 20. dubna 2018 )
„ 1940: Nimatron “ , na platinumpiotr.blogspot.com (přístup 20. dubna 2018 )
(in) „ Nimb pro HP-25 “