Combinatorial Games

The focus of my academic research paper is going to be game theory, and in particular the theory of combinatorial games. Game theory is a branch of applied mathematics used extensively in the social sciences, most notably in economics. Formally, “Game theory studies the behavior of rational players in interaction with other rational players. Players act in an environment where other player’s decisions influence their payoffs.”(Eichberger) In this case, “rational” refers to the standard economic assumption that individuals act to maximize their utility, usually in the form of maximizing their payoff. Games are often used to model markets with a few participants, as the decision of one participant often depends on the decisions made by others. In a game, each player has an available set of strategies. In Game Theory for Economists, Eichburger writes, “A strategy is a complete plan for how to play the game. ‘Complete’ means in this context that for any contingency the plan must specify what the player would do.” Thus a strategy specifies a reaction for any possible situation that could arise in a game. Games are solved by finding an equilibrium strategy for each player, that is a strategy that maximizes the payoff of each player, taking into account the decisions made by others.

It is common to make a distinction between pure and applied mathematics, and the traditional game theory that I have described falls squarely into the applied category. However the combinatorial games that this paper will focus on have very little in common with traditional economic games. Rather than modeling real life situations, combinatorial game theory uses mathematics to search for solutions of games in the common sense of the word, such as Chess or Go. Players in combinatorial games are, in a sense, trying to maximize their payoffs. In this case, however, the payoff consists of either winning or losing. Combinatorial games are sequential games with perfect information. This means that players take turns making moves, and at any given time all players are aware of the moves available to the other players. Outcomes depend strictly on the rules of the game and the decisions made by players. There is no randomness or element of chance. The nature of these conditions allows for elegant solutions, often with results of great interest to pure mathematicians. One such result is construction of the surreal numbers, the largest possible ordered field. (Conway) This was motivated by studies of Go.

For the sake of simplicity, it is assumed that the games consist of a finite number of turns. Combinatorial games can be further classified into partisan and impartial games. In an impartial game, all players have the same set of moves available to them for a given position. This restriction is lifted for partisan games. (Demaine) Chess, for example, is a partisan game as each player has his own pieces that he can control. The emphasis of this paper is going to be on impartial games. In a impartial game, the winner is determined by the last player to make a move. In normal play, the last player to move is the winner. If the last player to move loses, it is known as miserè play. While games are often played miserè, normal play is more commonly used in theory, as it allows for much more conclusive results. One such result is deeply related to the game of strategy known as Nim.

Nim is a simple two player impartial game. At the beginning of the game, the players are presented with any number of objects. These objects are divided between one or more piles, known as heaps. The players take turns removing objects from the heaps. They may remove any number of their choice, with the requirement that they remove at least one object per turn and all objects removed must come from the same heap. (It is understood that in the case of a single heap game, the first player may not remove all of the objects in the first turn.) Under normal play, the last player to remove an object wins. This begs the question, do either of the players have a strategy that will guarantee victory every time? The answer is “yes!”, as was discovered by Charles Bouton back in 1901. In his paper, “Nim, the Game with a Complete Mathematical Theory”, Bouton demonstrates that one player has the ability to turn the game completely in his favor, provided he makes the right move each turn. (Bouton) Essential to this solution is the concept of a safe combination. For each of the heaps on the board, the number of objects in each heap can be represented as a binary number. Bouton defines a sort of addition on these numbers, often referred to as the nimsum. To calculate the nimsum, each bit of the number is added to the corresponding bit of the other number(s) being added, mod2. For example if we use “+” to mean the bitsum, 1001 + 1111 = 0110. If we imagine these binary numbers in a column, each column with an even number of ones is assigned the value “0” and each column with an odd number of ones is assigned the value “1”. If the nimsum of all of the heaps is equal to 0, it is known as a safe combination.

Bouton proves that if a Player A is able to leave player B with a safe combination, then Player A will win the game, provided he does not make any mistakes. A safe combination can be formed by removing the correct number of objects from the largest heap, until the nimsum of all of the heaps is equal to 0. In the case of two heaps, this is equivalent to making the heaps equal in size. Bouton shows that a game with a safe combination present cannot be made into a safe combination, however any other combination can be made safe. Thus if Player A is able to establish a safe combination, he will be able to do so after each of Player B’s turns, until Player A removes the last object and wins. Thus if the initial setup of the game is not a safe combination, Player A can make it safe in the first move and guarantee himself a victory. If the initial setup is safe, this option is then reserved for Player B. To visualize this, imagine a game of Nim with two heaps. One heap contains three objects, the other two. The first player can create a safe combination by removing one of the objects from the heap containing three, leaving two objects in each heap. The second player can either remove one or both objects from one of the heaps. If both objects are removed, the first player can remove the whole other heap and win. If one is removed, the first player can remove an object from the other heap, creating another safe combination. As two, single-object heaps are remaining, the second player may only remove one of these. It is clear at this point that the first player wins.

The importance of Nim comes into play with a result known as the Sprague-Grundy theorem. The Sprague-Grundy theorem states that any impartial game under normal play is equivalent to some single heap game of Nim. (Demaine) What do I mean by equivalent? For any two games, G and H, we can define their sum, G+H, as a new game where the players may choose to move in either G or H each turn. Thus two games, G and G` are said to be equivalent if and only if for any game H, G+H = G`+H. The particular game of Nim that some game may be equivalent to is known as a nimber. For example, the nimber *7 refers to a game of Nim with a single heap containing 7 objects. An interesting consequence of this theorem is that the concept of safe combinations can be generalized to other impartial games. If the player whose turn it is can leave a safe combination, that player is said to be in a winning position. This is also known as an N-game, with the ‘N’ referring to the next player being in the winning position. (Notice that in this case, “game” refers to the current position rather than the game as a whole. This is OK, as each position within a larger game is equivalent to some smaller game with the second player now going first.) The opposite situation is referred to as a P-Game, with the previous player being in the winning position.

The Sprague-Grundy theorem allows us to consider any impartial game as equivalent to some variation of Nim. There are several such games that can be considered. One example can be found in the article “Take Away Games” by Allen J. Schwenk, who explores games where the number of objects one is allowed to remove is dependent on the amount removed in the previous turn. Even in this specific subclass of games, there are plenty of variations. Over the coming weeks, I hope to explore as many variations as I possibly can, looking for unanswered questions and possible avenues for original research. I very much look forward to sharing my results as this project progresses.

Sandpiles!

“If you keep your head in the sand, you don’t know where the kick’s coming from.”

-Herbie Mann, jazz flautist

There’s nothing like a social scientist to take a wind out of your math-researching sails. Yesterday, I was sitting in a coffee shop doing some work when a man sitting nearby took off his headphones to make a comment on my t-shirt—my favorite t-shirt—which proudly displays a colorful fractal image and the words “Fractal Geometry” on its front.

“Is this the kind of thing you’re into?” he asked, pointing at my shirt and then to the few math textbooks I’d been reading. “You do math in your spare time?” Excited by the opportunity to talk math on a weekend, I immediately volunteered that yes, I did do math for fun, and that I was starting to do some research.

“Math research?” he said, looking puzzled, “Can you even do that?”

“Sure. Why not?”

“Oh, I dunno. I do research on the housing market, which is changing all the time. Math just seems pretty absolute.”

“That’s fair; unfortunately, math is taught that way quite a bit, but you can definitely still do research. Mathematicians ask questions and try to answer them—just like any other research. Check this out.” I showed him some of the pretty sandpile pictures I’d been looking at on my laptop.

“Oh cool, what are you studying?” he asked, as I scrolled through a few pages.

“Sandpiles. I’m studying…sandpiles.” He nodded his head and smirked a little before turning back to his coffee.

“Wow. Looks crazy. I’ll let you get back to that.”

As soon as I’d said the word “sandpiles,” I realized how silly it must have sounded. I thought about trying to get the guy’s attention again to further explain myself, but the moment was lost. His headphones were back on, and he was already busy typing on his laptop. If only I had chosen to research something that sounded less childish. Maybe then I’d have had a chance at keeping his attention.

Luckily, within the blogosphere, I have a captive audience to with which I can share my sandpiling discoveries. In the remainder of this post, I’ll introduce what I’ve learned thus far about sandpiles in the form of a general overview. At this point, my knowledge is limited to the work of authors that have come before me. My hope is that, in the coming weeks, I’ll have something that is my own.

What is a sandpile?

A sandpile is exactly what it sounds like—it’s a pile of sand. Examined at any given moment, such a pile is fairly uninteresting, consisting of individual grains distributed in smaller piles across a surface; however, observed over a period of time, the behavior of a sandpile closely resembles other dynamical systems that arise within a variety of natural phenomena, including electrical networks, gravitational fields, earthquakes, quasars and the distribution of matter in the Universe (Dhar, Bak et. al).

What these systems have in common is a tendency towards what is called self-organized criticality, or SOC. The term, coined by (Bak et. al) in their 1988 article titled “Self-Organized Criticality,” describes two basic characteristics present within dynamical processes mentioned above; first, criticality refers to the unpredictable evolution of a dynamical system to a predictable and stable, critical state which is invariant under the specifics of that evolution; second, self-organization describes how, even in the presence of high degrees of spatial and temporal freedom, the critical state can be determined by a small set of parameters.

In the same article, (Bak et. al) introduced sandpiles to model SOC through a series of numerical simulations, where avalanches, called “topplings,” were created by randomly adding individual grains of sand to a pile over time. Their sandpile model was basic in its structure and design, and paved the way for all subsequent sandpile research. Beginning with a finite N x N lattice of points to act as the resting surface of a sandpile, they assigned each column of points in the lattice a critical sand height z­­­_c based on an ideal sandpile slope (z_c > z_c+1 ).

Following an original distribution of sand on the lattice, grains were randomly added to the pile. Toppling occurred any time a lattice point reached its critical height, at which point two grains of sand would be sent to neighboring lattice points, one to the “right” and one “up,” often resulting in lengthy chain reactions. Simulations would end when piles had reached a critical state such that the height of each lattice point (x , y), denoted z(x , y), was less than its critical height, and that the introduction of a grain of sand, regardless of it’s location, would result in the same state. As the authors noted in their paper, critical states were only guaranteed in the presence of a sink, which was identified with all lattice points (N , y) and (x , N). Below, I’ve included an example of a critical sandpile from their original simulation:

As the research of (Bak et. al) relied heavily upon empirical data collected from simulations, their results were mostly qualitative. This is not to say that their work wasn’t valuable to mathematicians. Most notably, (Bak et. al) hypothesized that critical states were invariant under the order of avalanches, an idea which would go on to inspire years of mathematical research.

Following the advent of the (Bak et. al) sandpile, other mathematicians began constructing their own sandpile models, which soon led sandpile research into familiar mathematical territory. In 1989, Dhar constructed a sandpile model, again using a lattice structure, but with an adjusted toppling condition and critical height structure which deviated from the gradient structure of (Bak et. al). Under his toppling condition, toppling lattice points sent grains to neighbors in all four directions, and all four edges of the lattice were identified with a sink. As it turned out, Dhar’s sandpile model was highly algebraic in structure and, using foundations of Markov processes, he was able to divide the set of stable sandpiles into two classes: recurrent and transient. Recurrent sandpiles, as he first described them, were stable piles which would recur under repeated application of sand to any single location. That is, for any recurrent pile C, there existed an integer m_i such that a_i^m C=C for all i (where the operation a_i C indicates that a grain is added to pile C at lattice point i) Further, he was able to prove that the set of all stable sandpiles, when restricted to recurrent piles, formed an abelian group with nontrivial identity under the operation aC.

Following Dhar, research on sandpiles has only grown in its sophistication and subtlety. In the following weeks, I hope to fully unpack the work of Dhar and move into more modern sandpile research, which studies piles on a wide variety of connected graphs, and comes under an equally large variety of names (chip-firing, burning, the dollar game, and more).

My goals for future posts:

-Prove that Dhar’s classification of stable piles into recurrent and transient sets is legitimate

-Prove Dhar’s lemma that the operation aC is abelian

-Verify an algorithm for the construction of an identity element I under the operation aC.

-Show that the set of stable sandpiles of a lattice forms a commutative monoid.

-Impose a structure of ideals onto the set of stable sandpiles of a lattice and show that the minimal ideal of that monoid forms a group of recurrent sandpiles.

-Find out what a Tutte polynomial is.

-Find a way to make pretty pictures like this one, the identity element of a recurrent sandpile group of a 523 x 523 lattice, taken from (Levine, Propp).

A Basic Introduction & Research interests

Leonardo of Pisa was the Italian mathematician of the late twelfth century and early thirteenth century known famously as Fibonacci. In 1202, he published the book Liber Abaci in which he subtly presented the Fibonacci sequence through a problem regarding the reproduction of a one pair of rabbits. The problem stated: “A pair of adult rabbits produces a pair of baby rabbits once each month. Each pair of baby rabbits requires one month to grow to be adults and subsequently produces one pair of baby rabbits each month thereafter. Determine the number of pairs of adult and baby rabbits after some number of months. It is also assumed that the rabbits are immortal.” Edouard Lucas brought attention to the sequence again and called it the Fibonacci sequence in the nineteenth century. Lucas studied the sequence extensively and generalized to a case where $L_1 = 1, L_2 = 3, L_n = L_{n-1} + L_{n-2}$. The sequence is now called the Lucas sequence.

Although the sequence is named after him, Fibonacci was not the first one to have described it. Notions of the sequence appeared in India as early as 200 BC, in particular, with Sanskrit prosody.

By the twentieth century, interest in Fibonacci numbers rose in the mathematics community. The Fibonacci Association was founded in 1963 by mathematician Verner E. Hoggatt; the association began to publish the journal The Fibonacci Quarterly. International conferences to discuss Fibonacci numbers began in the 1980s.

We define the Fibonacci sequence $\{f_n\}$ as follows:

$$f_1 = f_2 = 1$$

$$f_{n+1} = f_n + f_{n-1}$$ where $n = 2, 3, ...$.

Fibonacci numbers have appeared throughout mathematics. They are used in looking at how long the Euclidian algorithm takes to run. Approximate conversations between miles and kilometers can be made if the miles given happens to be a Fibonacci number. In such a case, it’s conversion to kilometers is approximately the next Fibonacci number in the sequence. The sequence can be found by adding the entries along each shallow diagonal of Pascal’s triangle. Variations of the Fibonacci sequence include the Negafibonacci numbers (indexing includes negative integers), the Lucas numbers mentioned earlier, and the Pell numbers ($p_n = 2p_{n-1} + p_{n-2}$).

Apart from their many applications within mathematics, Fibonacci numbers appear vastly throughout nature. If we were to look at the arrangement of petals in flowers, they come in groups of 3, 5, 8, 13, $\dots$. These are remarkable the Fibonacci numbers. Having flower follow this patter allows for optimization of space given the time seeds will appear in the flower head’s center. Leaves on the stems of plants are also arranged in a similar way.

The sequence is also connected to the golden ratio $\phi = \frac{1+ \sqrt{4}}{2}$. In particular, if we form a sequence using ratios from terms of the Fibonacci sequence, this sequence $\{\frac{f_{n+1}}{f_n}\}$ approaches the golden ratio as $n$ approached infinity.

----

Right now I've in looking at generalized Fibonacci numbers, which are defined in a couple of the papers in the Dropbox. I would really like to incorporate field/Galois theory into my research while looking at this, so when I search for articles right now this is what I'm looking for. I don't have a specific research question yet.

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.