|
Nim is a mathematical game of strategy in which two players take turns removing objects from distinct heaps. On each turn, a player must remove at least one object, and may remove any number of objects provided they all come from the same heap. The goal of the game is to be the player to remove the last object. Variants of Nim have been played since ancient times. The game is said to have originated in China—it closely resembles the Chinese game of "Tsyan-shizi", or "picking stones"〔.〕—but the origin is uncertain; the earliest European references to Nim are from the beginning of the 16th century. Its current name was coined by Charles L. Bouton of Harvard University, who also developed the complete theory of the game in 1901,〔..〕 but the origins of the name were never fully explained. The name is probably derived from German ''nimm'' meaning "take ()", or the obsolete English verb ''nim'' of the same meaning.〔 attributes this theory to .〕 Nim can be played as a ''misère'' game, in which the player to take the last object loses. Nim can also be played as a ''normal play'' game, which means that the person who makes the last move (i.e., who takes the last object) wins. This is called normal play because most games follow this convention, even though Nim usually does not. Normal play Nim (or more precisely the system of nimbers) is fundamental to the Sprague–Grundy theorem, which essentially says that in normal play every impartial game is equivalent to a Nim heap that yields the same outcome when played in parallel with other normal play impartial games (see disjunctive sum). While all normal play impartial games can be assigned a nim value, that is not the case under the misère convention. Only tame games can be played using the same strategy as misère nim. A version of Nim is played—and has symbolic importance—in the French New Wave film ''Last Year at Marienbad'' (1961).〔. Morisette writes that Alain Robbe-Grillet, one of the screenwriters for the film, "thought he had invented" the game.〕 At the 1940 New York World's Fair Westinghouse displayed a machine, the Nimatron, that played Nim. It was also one of the first ever electronic computerized games (1952). Herbert Koppel, Eugene Grant and Howard Bailer, engineers from the W. L. Maxon Corporation, developed a machine weighing 50 pounds which played Nim against a human opponent and regularly won. A NIM Playing Machine has been described made from TinkerToy 〔(【引用サイトリンク】title=How to Construct NIM Playing Machine )〕 Nim is a special case of a poset game where the poset consists of disjoint chains (the heaps). == Game play and illustration == The normal game is between two players and played with three heaps of any number of objects. The two players alternate taking any number of objects from any single one of the heaps. The goal is to be the last to take an object. In misère play, the goal is instead to ensure that the opponent is forced to take the last remaining object. The following example game is played between fictional players Bob and Alice who start with heaps of three, four and five objects. Sizes of heaps Moves A B C 3 4 5 Bob takes 2 from A 1 4 5 Alice takes 3 from C 1 4 2 Bob takes 1 from B 1 3 2 Alice takes 1 from B 1 2 2 Bob takes entire A heap, leaving two 2s. 0 2 2 Alice takes 1 from B 0 1 2 Bob takes 1 from C leaving two 1s. (''In misère play he would take 2 from C leaving (0, 1, 0).'') 0 1 1 Alice takes 1 from B 0 0 1 Bob takes entire C heap and wins. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Nim」の詳細全文を読む スポンサード リンク
|