Fun with Sandpiles

The following applets are two separate, interactive sandpile simulations. In both cases, we start with square, stable 500x500 piles of sand. The edges of the table are identified with a sink. Clicking anywhere on either applet (with exception of anywhere too close to the edge of the board) will sprinkle sand onto the table causing avalanches. No matter how much sand you sprinkle (assuming you stop at some point), both of these piles will stabilize. Check it out.


Random, stable sandpile

This sandpile is randomly generated.

Hyper-critical sandpile (this one is fun)

This sandpile starts as a hyper-critical pile of sand. That is, individual sand site (of which there are 500x500--each corresponding to a pixel) is at its maximum capacity.

Conway's Game of Life

Beloved ARPers,

I'm learning a new programming language called Processing, and I thought I'd go ahead and share my first applet, which I created by tweaking a few pieces of code found in the tutorials section of the Processing Website. If you hold place your cursor over the applet below, click and hold, you should get Conway's game of life!



Up next: coding sandpiles. It shouldn't be hard to get to sandpile simulations from the code structure I used for this applet, I'll just need to change my updating procedure. Anywhoo, just thought I'd procrastinate finishing up my Unit Plan and share this with y'all.

-James

Background Math - Combinatorial Games

In this post I will state as well as prove some important basic results relating to the theory of impartial games. You will recall from my introduction that impartial refers to games where all players have the same set of available moves. In addition, we include the assumption that these games are finite, that they will necessarily end after no more than some specific number of terms. Formally, we can define games as sets of all options available to the current player. These options are themselves games, albeit simpler ones. The simplest of all possible games is a zero game. A zero game, represented by the empty set { }, is a game without any moves. For purposes of this paper we are considering games in normal play, that is games where the player who makes the final move wins. In the case of the zero game, there are no moves to be made. Thus any player presented with a zero game is an automatic loser.

An example - The Nimbers

I am assuming that you, the reader, have some familiarity with the rules and gameplay of nim. The rules of nim are widely available online , and a brief description can be found in my introduction.

A nimber, written *n for some natural number n, is simply a game of nim consisting of a single heap containing n objects. The simplest case is *0, a game of nim without any objects. Formally, we say *0 = { }. This represents the fact that a player presented with *0 does not have any possible moves to make. Next one could consider the game of nim with a single heap and a single object, *1. We define *1 = {*0}, that is the only option in such a game is to remove the single object, presenting your opponent with a zero game. Likewise, the game with a single heap and two objects, *2, is defined as {*0, *1}. When presented this game, the player can remove one object, handing her opponent a single heap with a single object (*1). The other option is to remove both, leaving the other player with the zero game (*0). Thus we can define a nimber for any natural number n as

*n = {*0, *1, *2, *3, ..., *(n-1)}.

At this point one might wonder as to the motivation for looking at games of nim with a single heap, as the solution to such games is trivial: remove all of the objects in the heap and declare victory. The real usefulness of nimbers is apparent when one adds them to other games. Furthermore, it can be shown that any finite, impartial game is equivalent to a nimber, in a result known as the Sprague-Grundy Theorem. Of course neither addition nor equivalence of games has any inherent meaning. Going forward we will give precise definitions to both of these concepts, as well as prove some results that lead up to Sprague-Grundy.

Addition of Games

Suppose we get bored of playing nim with a single heap, and decide to venture out into more complex variations of the game. We might, for example, decide to pursue a game consisting of two heaps, one with five objects and the other with seven. It is apparent that this is precisely the same as playing *5 and *7 at the same time, that is having the options of making a move in *5 or making a move in *7. Thus we could write *5 + *7 to describe such a game. More generally, for two games A and B, we define their sum A + B to be the game where the player may make a move in either game. These games need not be of the same type. It is possible, for example, to play a game of nim alongside some other game. Each turn, the players choose a game in which to make a move, and may only move in that game. The winner is the last person able to make a move in either game. Notice that addition of games is commutative, as A + B provides a player with exactly the same set of options as B + A.

Characteristic of a Game

In the context of game theory, “solving” a game constitutes the process of finding out the optimal strategy for each player to take. Again, for simplicity, let us consider a single heap game of nim with two players, Left and Right. Suppose Left is able to make a move in *5. The obvious choice is to remove all five objects from the heap, serving Right a game of *0 and removing their ability to make the final move. The game *0 is obviously a losing position for Right. We can also say that *5 is a winning position for Left, as it allows Left to force Right into a losing position. In fact for any n > 0, *n is a winning position.

Games with multiple heaps are a bit more complicated. From the introduction, you will recall that in a two heap game of nim, the optimal strategy is to reduce the larger heap so that both heaps have an equal number of objects. If left is presented with a game of *2 + *4, she can remove two objects from *4, giving right a game of *2 + *2. If Right removes either one of the heaps, left can remove the other and win. If Right removes one object from either of the heaps, Left can do the same in the remaining heap. Either way, Right will be forced to eventually remove a whole heap, allowing Left a win. Thus *2 + *4 is a winning position for Left, as it allows her to force Right into losing position.

In any game, a winning position is a position that allows the player to force the other player into a losing position. A winning position is also known as an N-position or N-Game, referring to the fact that the next player to make a move will win the game, provided she plays optimally. In other words, in an N-Game, there exists a move that will put the other player in a losing position. Likewise, a losing position is also known as a P-position or P-Game. In a P-Game, the previous player to make a move will win the game, provided she plays optimally. This means that any move in a P-Game results in an N-Game for the other player.

This begs the question: “Is every game either a P-Game or an N-Game?” For finite, impartial games, the answer is yes. For nim, this is shown by an explicit derivation of the optimal strategy, that is any game where the “nimsum” of all of the heaps is 0 is a P-Game. (Bouton) As we will later see, all other finite, impartial games are equivalent to a game of nim, and thus it makes sense to extend the concept to all games of that sort.

In summary:

An N-Game is a game where any move made results in a P-Game.

A P-Game is a game where there exists a move into an N-Game.

These are the definitions that we will apply going forward. When we refer to the characteristic of a game, we are referring to it’s position, N or P.

Equivalence of Games

The time has come to formally define what it means for two games to be equivalent. It may be tempting at first to say that two games with the same characteristic are equivalent. This definition, however, is less than satisfactory. Consider the games *1 and *2. These are both N-Games. Yet if we were to add them individually to some third game, another instance of *2, we find that they behave very differently. The game *1 + *2 is a P-Game, while *2 + *2 is an N-game. This tells us that we need a stricter definition.

In fact, the definition of equivalent games says that two games are equivalent if they behave the same with regard to game addition. Thus two games, A and B, are equivalent, written A ≡ B, if for any third game C, A+C and B+C have the same characteristic.

Lemma 1: ≡ is an equivalence relation. That is for any games A, B, and C:

i)A ≡ A (≡ is reflexive)

ii) If A ≡ B then B ≡ A (≡ is symmetric)

iii)If A ≡ B and B ≡ C, then A ≡C (≡ is transitive)

The proof of this lemma is trivial, and left up to the reader.

Lemma 2: For any game A, A + *0 ≡ A

Again, I shall omit a formal proof. It is clear that adding a game without any moves to A is the same as playing A by itself.

Lemma 3: For any games A and B, if A ≡ B, then A and B have the same characteristic.

Proof: Suppose A ≡ B. Then for any game C, A + C and B + C have the same characteristic. Let C be *0. Then A + *0 and B + *0 have the same characteristic. By Lemma 2, A and B both have the same characteristic.

This shows us that while two games having the same characteristic is not sufficient to establish equivalency, it is a necessary condition.

Characteristic of Added Games

Is it possible to determine the characteristic of the sum of two games from the characteristic of the games individually? In general, it is not. However there are certain situations where it is possible, and these are handled by the following two lemmas. A third lemma describes the result of a game added to itself.

Lemma 4: Let A and B both be P-Games. Then A + B is a P-Game.

Proof: As we are working with finite games, let us assume that A + B requires no more than n moves to be finished. We shall induct on n to show that the lemma holds for all finite games. In the case of n=0, A and B must both be zero games. The sum of two zero games is a zero game, and a zero game is a P-Game.

Now as our inductive hypothesis, let us assume that the lemma holds for all A + B that can be finished in n moves or less. Let C and D both be P-Games, such that C + D can be completed in at most n + 1 moves. A player presented with C+D is allowed to either make a move in C or a move in D. Thus we can write C + D = {C’ + D | C’ is an option in C} U {C + D’| D’ is an option in D}. Notice that as C is a P-Game, any move in C is necessarily an N-Game. Likewise any move in D is an N-Game as well. Thus for any C’ there exists a move into a P-Game, call this C’’. By the same logic for any D’, there exists a move into a P-Game, D’’. Thus C’’ + D is the sum of two P-Games, as is C + D’’. Both of these sums are games requiring at most n-1 moves to complete. By our induction hypothesis, C’’ + D is a P-Game, as is C + D’’. As there exists a move into a P-Game from C’ + D, by definition C` + D is an N-Game. (The same holds true for C + D’). As every option in C + D is an N-Game, we must conclude that C + D is a P-Game.

Lemma 5: Let A be a P-Game and B be an N-Game. Then A + B is an N-game.

Proof: As B is an N-Game, there exists some move in B, call this B’, such that B’ is a P-Game. Notice that from A + B it is possible to move into A + B’. As A and B’ are both P-Games, by Lemma 4 we can conclude that A + B’ is a P-Game as well. Since there exists a move from A + B into a P-Game, A + B must, by definition, be an N-Game.

Lemma 6: For any game A, A + A is a P-Game.

Proof: Suppose A is a P-Game. Then A + A is P-Game by Lemma 4.

Next suppose A is an N-Game. Then there exists some move in A, say A’, such that A’ is an P-Game. Notice that it is possible to move from A + A to A’ + A. As A’ is a P-Game and A is an N-Game, by Lemma 5 A’ + A must be an N-Game. As there exists a move from A + A into an N-Game, A + A must be a P-Game.

A few more thoughts about P-Games

In the previous section, we showed that the sum of any two P-Games must also be a P-Game as well as that the sum of a P-Game with an N-Game results in an N-Game. What about the case of the sum of two N-games? Lemma 6 showed one specific case where the some of two N-Games, in this case a single game added to itself, results in a P-Game. This can be seen, for example, with *1 + *1. However consider the game *1 + *2. In this case, we have two N-Games summing to another N-Game. In general, the characteristic of the sum of two N-Games is inconclusive.

As to why this might be the case, it is best to consider the true essence behind the meaning of a P-Game. Notice that a P-Game added to another P-Game results in a P-Game, while a P-Game added to an N-Game results in an N-Game. We could rephrase this to say that a P-Game added to another game does not affect the second game’s characteristic. Lemma 2 proved this for one specific P-Game, *0, while Lemmas 4 and 6 showed this for P-Games in general. This motivates the following lemma.

Lemma 7: For any P-Game A, A ≡ *0.

Proof: Let B be an arbitrary game. We need to show that A + B and *0 + B have the same characteristic. Suppose B is a P-Game. Then A + B is a P-Game by Lemma 4. By Lemma 2, we know that *0 + B ≡ B. *0 + B must be a P-Game as well.

Next suppose B is an N-Game. By Lemma 5, A + B must be an N-Game. Again, Lemma 2 tells us that *0 + B ≡ B. Thus *0 + B must be an N-Game as well.

This result is simple but powerful, and really emphasizes that every P-Game truly is a losing position. Giving your opponent a game of *99 + *99 is no different than handing them a zero game, with the exception of how many turns it takes for them to reach their inevitable defeat.

There is one more important fact about P-Games that we must understand, before proceeding on to a proof of the Sprague-Grundy theorem. Lemma 6 told us that a game added to itself must be a P-Game. Presumably this should be true of adding any two equivalent games, and we will soon see that this is indeed the case. The obvious question, however, is as to whether or not this holds in the opposite direction. That is, if two games sum to a P-Game, are they equivalent? The answer is in fact yes, and the following Lemma makes this clear.

Lemma 8: For any two games A and B, A ≡ B if and only if A + B is a P-Game.

Proof: Suppose A ≡ B. Then A + A has the same characteristic as A + B, by Lemma 3. As A + A is a P-Game by Lemma 6, A + B must be a P-Game as well.

Next suppose A + B is a P-Game. We need to show that for any game C, A + C has the same characteristic as B + C. Let us a assume that A + C is a P-Game. Then for any move A’ in A and any move C’ in C, A’ + C and A + C’ are both N-Games. Also by our assumption that A + B is a P-Game, for any moves A` in A and B` in B, A` + B and A + B` are both N-Games. We wish to show that B + C’ and B’ + C are N-Games as well. Since A + C is a P-Game, then by Lemma 7 A + C ≡ *0. Thus B’ + C ≡ A + C + B’ + C. Lemma 6 allows us to simplify this to B’ + C ≡ A + B’. Thus B’ + C is an N-game.

By a similar argument, B+ C’ ≡ A + B + B + C’ ≡ A + C’. Thus A + C’ is an N-Game. Therefore If A + C is an P-Game, then B + C is a P-Game. By symmetry, we can also conclude that if B + C is a P-Game then A + C is a P-Game. Therefore A + C and B + C have the same characteristic, meaning A ≡ B.

The Mex Rule and The Sprague-Grundy Theorem

At this point in my research, I am still working on formulating a solid proof of the Sprague-Grundy Theorem. I look forward to updating this post in the near future with that result.

Yeah Pebbling

Basic Pebbling Intro/Technical Background

Background Math

Background: Fibonacci Polynomials

Technical Background

It has been proven that one of the players of Nim, let us say Player A, can leave a certain number of objects in play in a way such that Player B cannot win. This is called a safe-combination (Bouton). This safe-combination is also what theorists call p-games (the “p” standing for previous player). In other words, a safe-combination is a set of objects left in play that could result in the player who just played (or previous player) winning. N-games (where the “n” stands for next player) represent a set of objects left in play that could result in the player who is about to make a move will win the game. N-games are also called unsafe-combinations (Bouton). It has also been proven that within in any p-game, there exists some move such that an n-game will result.

NEED TO INSERT THE PROOF OF P + P = P, N + P = N, N + P = N, N + N = ?

Two finite impartial games, A and B, are said to be equivalent if and only if for all games C, A + C and B + C have the same characteristics (i.e. A + C and B + C are either both p-games or both n-games).

Let us take an example of this—let us compare the 1-pile Nim game with 3 objects in one pile (III) and the 2-pile Nim game with 1 object in one pile and 2 objects in another pile (I+II). It is my goal to prove (using the definition of equivalence) that III is equivalent to I + II. First let us explain that in order for III to be equivalent to I + II, this means that for all n element of the Natural Numbers, for all finite games, A with at most n moves such that A + I + II has the same characteristic as A + III.

Let us show that III is equivalent to I+II. By definition, this means that some game, A can be added to both games and A + III and A + I + II will have the same characteristic. The base case of this proof is the zero case. When the zero game is added to III and I + II, they both have the same characteristic. Now, assume that when a game with n moves, A, is added to both III and I + II, A + III and A + I + II have the same characteristic. We need to show that when a game with n + 1 moves, A, is added to both the III game and I + II game, A + III and A + I + II have the same characteristic.

First, let us assume that A + III is a p-game. This means that in order for A + III and A + I + II to be equivalent, we must show A + I + II is also a p-game. Since A + III is a p-game and by one of our definitions of a p-game (that there exists some move in a p-game that will make it n-game), we can look at possible outcomes of sets of objects after a move is made in A + III, all of which will be n-games: A + II, A + I, A, A^l + III (where A^l is the game A after a move has been made). If we assume A + I + II is also a p-game, find the same possible outcomes of sets of objects after a move is made and do not get a contradiction, we have shown this side of assumption to be true. If A + I + II is a p-game, then A + II, A + I, A + I + I, and A^l + I + II (again, where A^l is the game A after a move has been made).

By our assumption, we know A + II and A + I are n-games and that A is an n-game. Based on our earlier proof, we know that a n-game + p-game results in an n-game. We also know that 1 + 1 is a p-game. Therefore, A + I + I is an n-game. This leaves A^l + I + II as the only possible contradiction. However, based on our inductive hypothesis, we know that A^l + I + II has the same characteristics as A^l + III. Since A^l + III is an n-game, A^l + I + II is also an n-game. Because we arrived at no contradictions and all games resulting after a move from a p-game are in fact n-games, A + I + II is a p-game and therefore has the same characteristic as A + III.

Now, we must start with the assumption that A + I + II is a p-game and continue with the same process. After a move is made in A + I + II, we are left with the n-games A + II, A + I, A + I + I, and A^l + I + II (where A^l is the game A after a move has been made). Now let us show that A + III is also a p-game. In other words, let us show that each of the resulting games after a move has been made are n-games. We are left with the set of objects A + II, A + I, A, A^l + III (where A^l is the game A after a move has been made). If A + III is a p-game, then A + II, A + I, A, A^l + III should all be n-games and we should not arrive at any contradictions. By our assumption, we know that A + II and A + I are both n-games. By our inductive hypothesis, we know that A^l + III has the same characteristics as A^l + I + II. Since A^l + I + II is an n-game, A^l + III is also an n-game. This leaves A as a possible contradiction. Let us assume that A is a p-game and by our assumption, we know that A + I + I is an n-game. We also know that I + I is a p-game. This makes A + I + I the sum of two p-games. However, we know by our earlier proof that the sum of two p-games is a p-game. Therefore, A is an n-game. Because every game that resulted from a move in a p-game was an n-game, A + III was in fact a p-game and therefore, A + III and A + I + II have the same characteristics. Thus, III is equivalent to I + II.

Because we are using addition, and addition holds the Reflexive, Transitive, and Symmetric Properties, we can prove this to be true by showing this to be true for each property.

INSERT THE THREE PROOFS (I CAN’T READ MY HANDWRITING).

I am not sure where I am going with this yet (meaning, I do not know what my problem is yet), but I hope that this information and these proofs will help inform my readers of the characteristics of Nim games. I think I want to modify another game and show that it is equivalent to a Nim game. So, I think that these proofs will help establish how I will do this in other cases.

The Sandpile Model

I've been busy studying sandpiles; unfortunately, LaTex and blogger are not friends. I've condensed most of what I've been up to into a pdf available for download from my dropbox.

The Sandpile Model

xoxo,

The Sandman