Nim (0)

Giới thiệu

Generally, the game of Nim is a two-player game of perfect information in which there are some number of rows or "heaps" of objects, and a legal move consists of removing any number of objects from a single heap. (For a non-trivial game, we should start with at least three heaps.) In "standard play", the player who cannot make a move on his turn (because no objects remain) is the loser. A very general and far-reaching theory of such games is developed in Berlekamp, Conway, and Guy's Winning Ways for Your Mathematical Plays.

In the commercial version pictured, the players take turns removing 1, 2, 3, or 4 pegs together in a row. It would appear from the picture that "rows" can run in any direction, which means that the "heaps" intersect. This is not what most people know as Nim. Also, according to the original description, in this version the loser is the player who has to remove the last peg. This is so-called "misere play", rather than the standard winning condition. Many combinatorial games allow misère play as a variation.

Nim is solved, which means that from any initial configuration, one can readily determine whether the next player or the previous player has a winning strategy, and identify a good next move in the former case. For Nim, this can be determined surprisingly readily no matter the size of the heaps, but you're not going to get the secret from me.

As most who would be interested in Nim know the solution, there isn't much of a game here. But Nim plays a central role in the theory of combinatorial games, as any two-player finite impartial game is in some sense Nim in disguise: any position in such a game corresponds to a unique Nim-heap, and one can play the disguised game perfectly by making the moves that correspond to winning moves in Nim. Sprouts is one example. This however does not mean that Sprouts itself is solved, as the "disguise" is only partially revealed.