Introductions

Corey Levin

ARP introduction on Nim

The mathematical field of game theory displays the calculated circumstances where success is based on the choices of others (Myers). People (referred to as players), theoretically make rational decisions towards achieving a goal, and if that goal is achieved, we say that the player has won the game. Usually, this accomplishment is attained by applying an optimal strategy, which is the best strategic approach to a given game. The beautiful thing about Game Theory is that there are deep mathematics and a multitude of extensions to the games which are relatively simple to understand. There are various categories of within the field of game theory, but I will be focusing primarily on combinatorial games.

Combinatorial game theory typically involves two players, often referred to as Left and Right. These games are characterized by their multiplicity of moves. One aspect of these games that makes them so mathematically interesting is that no randomness or hidden information is permitted. We say that all players know all information in combinatorial gameplay (perfect information). Therefore, determining the best way to play is purely strategic (Demaine). Further assumptions are that the game terminates after a finite number of moves and the winner is unique (there are, of course, some exceptions to these assumptions, but this is the basic setup). In normal play, the winner is the last player to make a legal move. This condition is reversed in misere play, however, when the winner is defined as the player who first cannot make a legal move. Some games are designed in such a way that it is possible to return to a previous position. We call these games loopy. Finally, we say the game is impartial if the same moves are available to both players from the same positions (that is, gameplay is identical regardless of player perspective) (Demaine). If this is not the case, we define the game as partisan. The most common method for analyzing a combinatorial 2-player game is with a rooted tree. Branches of the nodes correspond to potential moves by either the Left or Right player. Most of the interest in this field has focused on the various ways of manipulating, analyzing, and interpreting these trees for various games (Demaine).

A result that hones in closely to my particular topic is the Sprague-Grundy Theorem, which states that every finite impartial game is equivalent to an instance of the game Nim. Beyond that, it has been shown that every impartial, two-player, perfect information game has the same value as a single pile of Nim (Demaine). However, this result does not make much sense without an explanation of the game itself.

Nim is classified as a “take-away” game, defined as a 2-player game where each player alternately diminishes a stock of markers until the last marker is removed (in normal play this denotes the winner) (Schwenk). These games are arranged in a way that immediate victory is impossible (it would be uninteresting if a player could simply take all of the markers instantly), and that will always terminate. The optimal strategy generally is to reduce the pile to a certain “safe combination,” leaving the opponent with only options of making the pile unsafe. This process iterates until the least marker is drawn from after an unsafe combination is left. This can best be thought of with modular arithmetic (with a turn allowing one to remove up to m markers and optimally seeking to reduce the pile to 0mod(m+1)). This will be defined more rigidly and illustrated later in the paper. It should be evident, however, that once an equivalence of 0mod(m+1) is achieved, the opponent cannot reach that same equivalence, and therefore must leave the pile(s) unsafe (Schwenk). There are certainly other ways to perceive of an optimal strategy, and particularly methods are best determined with respect to specific games.

Nim is a 2-player game with objects placed in three piles. A player takes at least one object from a single pile (and at most the entire pile). The last player to take a token wins the game. Charles L. Bouton has proved that if Player A leaves a safe combination on the table, Player B cannot. This can be repeated until A wins. Safe combinations here refer to a particular type of binary addition, which we refer to as taking the Nim-Sum. Column addition is performed, and when all columns sum to a congruence of 0(mod2), we have a safe combinations (or we say that the Nim-Sum = 0). Charles Bouton proved that a player can derive a safe combination from any unsafe combination (and similarly, a player cannot play a safe combination if it is already safe). Thus, if Player 1 approaches a game that begins in an unsafe combination (which Bouton also proved is most probable) he can ensure victory.

A plethora of variations and extensions followed since Bouton’s original proof in 1902. E. H. Moore presented a generalization of the game in 1910. He refers to this as Nim_k, where the original was Nim₁. Here, a player takes as many counters as he so chooses and disperses them into any number of piles can choose up to k piles from which to draw from (for obvious reasons, the game is always played with a greater number of piles than k). John C Holladay extends upon this with his variation of the game in 1958. He calls it Matrix Nim, and it involes arranging piles into finite rows and columns. A player has the option of reducing the size of any number of counters in a given row or column (provided they leave one column untouched). For both of these variations, authors have successfully shown the same conditions of the optimal strategy of Nim. That is, given a safe position, any move leads to an unsafe position, and given an unsafe position, any move leads to a safe position.

These authors have built upon a simple, but mathematically rich game, and extended it to prove some other condition that might be valuable within the field. There are a variety of interesting ways to analyze a game, but game theorists rarely limit themselves to the exploration of one game. Sometimes it is of more interest to analyze many games and try to extract some common principle. That is, with respect to games G and H, we might choose to look at the compound of G+H. In this respect we have to see how to win G, H, and the both of them at once. G+H can refer to the disjunctive sum, where each player must play a legal move in either G or H. It can also refer to the conjunctive compound, where a legal move must be played in G and H (Conway).

Similarly, we might try to break up a game into various sub-games to get a better analysis. Games on a checkerboard might be broken up into smaller 2x2 versions, and when principles are understood in these games, they can be combined and extended to the greater versions. Other things game theorists may look into are the remoteness of pieces. What this means is that a piece that might be pivotal for a winning move is much less remote than one that is almost unnecessary. Often, one can work backwards from this to derive an optimal strategy. Another notion is that of a suspense function. This is where one can determine how long a win can be drawn out, or on the contrary, how quickly a loss can be succumbed to (this is based on certain assumptions of the human condition) (Conway). These aspects, and others I will learn along the way, are some of the qualities I hope to pay particular attention to as I begin my analysis of Nim and its variations.