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

Becca's Introduction (Finally)

Almost each and every one of us has played some sort of game in our lives before. In addition, we have experienced a loss or a win during a game. Have you ever played someone in a game and it seems they just cannot lose? Well if may be this person has studied Combinatorial Game Theory at some point in his or her life.

This branch of applied mathematics is the study of a particular type of games. This typically involves two players and it is assumed that both players know all there is to know about how to play the game. In order to find a winning strategy, Game Theory becomes a means of determining such strategy. In other words, Game Theory takes on the task of finding how to beat even the best player (Demaine & Hearn).

In games studied in game theory, there are several distinctions commonly made. First, it is understood that in normal play, the winner of each game is determined by the last player to make a legal move. However, in what game theorists call miseré play, the goal of the game is reversed. Thus, the loser of the game is the last player to make a legal move (Demaine & Hearn). In addition, there is a clear distinction between impartial and partial games. Impartial games are when the same opportunities of moves are given to each player while partial games are when game play is not equal based on perspective of the players (i.e. chess is a partial game because each of the players are faced with different play opportunities at each turn) (Demaine & Hearn).

One particularly famous and well studied and relied upon Theorem in the field of Combinatorial Game Theory is the Sprague-Grundy Theorem. This states that every finite impartial game under normal play “is equivalent to an instance of the game Nim” (Demaine & Hearn). To better understand this, let us look at the game of Nim itself.

Nim, in normal play, is an impartial game, which is played with two players, A and B. Say there are three piles of objects with an arbitrary number of objects in each pile. The only condition of number of objects in the initial piles is that no pile may contain the same number of objects as another. Play begins and Player A may choose one pile in which he or she wishes to remove objects from. Player A can remove at least one and up to the entire pile. It is only necessary that from only one pile are objects removed in a single turn and at least one object is taken during a turn. After Player A removes a number of objects, it is Player B’s turn with the same conditions of play. The player with the last legal move wins. In other words, the player who removes the last object is declared the winner (Bouton). As mentioned earlier, in miseré play, the player who takes the last object is declared the loser of the game.

Technical Analysis of Combinatorial Take Away Games

There are numerous methods in which game theorists approach the analysis of combinatorial games. Primarily, we will be dealing with two-player, impartial take-away games. The terms and techniques vital to the exploration of these games will be discussed, leading up to an explanation of the Sprague-Grundy Theorem.

We first define some necessary terms and definitions for entering into the field of combinatorial game theory. An impartial game is aptly named in that it refers to the type of game where players have the same moves available to them (in other words, the only difference is that one player makes the first move). Furthermore, we will be studying combinatorial games (between two players) with perfect information, meaning that all information related to game-play is readily available to both players. The success of one player in a mathematical game is thereby dependent on the choices of another. Typically, these games will terminate after a finite number of moves (however, we will perhaps be looking at variations of games in which the act of tweaking them has made them Loopy, or put in a state in which positions can be returned to throughout the game) (Demaine). Essentially, what makes combinatorial games with these particular characteristics so fascinating is that the element of chance we associate with our typical connotation of a game is minimized to the extent of choosing the player to take the first move. Hence, they are purely strategic in nature.

With these characteristics in mind (finite, impartial, alternating, perfect information), as well as the essential notion that game theory analysis is based on how players respond to each other, we can use a rooted tree to map out the moves of a game (Demaine). There is a plethora of ways in which these positions, or nodes, can be studied. A particularly useful technique for discovering the optimal strategy is to work backwards through the game-tree. That is, if a tree be used can be used to map out all of the outcomes of a given game, rational players can determine the best moves with respect to whatever position they find themselves in. In this sense, we can use this method to trace a path through a game to determine the winner of the game (assuming optimal play) from the onset. Hence, we find it useful to characterize games in terms of who should win with optimal play. There are a variety of terms game theorists have coined, but we will refer to a game in which the next player to move has the possibility to win as an “N-game,” and those games where a player must make a move that allows a winning possibility to his opponent as “P-games” (Conway). Furthermore, each node of the tree, or position in the game, can be characterized as “N” or “P,” in that these are really sub-games themselves. We refer to “N” and “P” as the “characteristic” of a game (and henceforth we will not use the description in an ambiguous manner).

There are certain characteristics that are immediately evident about N-games and P-games.” If an N-game means that there is a possibility to win, it follows that from every N-position, there exists a move to put the opponent into a P-position. Similarly, since every P-game means that through optimal play, the next player to make a move will lose, every move made from a P-position will put the next player in an N-position (Conway). These simple notions become crucial elements in setting up proofs for comparisons between games.

We have briefly touched on the concept of combining games for the purposes of comparison. Specifically, we mentioned that adding two games together can be done “disjunctively,” where a player has the option to play a move in either game, or “conjunctively,” where a player must play a move in both games on each turn. We will set aside conjunctive summation for possible use in analyzing variations of games and focus on the disjunctive sum, as it is this notion that is used in determining equality of games. We say that two games A and B are equivalent if and only if A+C has the same characteristic as B+C for any third game C. Logically we can also claim that two games A and B are not equivalent if there exists a third game C such that A+C does not have the same characteristic as B+C. We can verify the equivalence relation by showing the reflexive, symmetric, and transitive axioms of equivalent games A and B.

The reflexive axiom is fairly straightforward, as a game will naturally have the same characteristic as itself. For the symmetric axiom, we need to show that if a game A is equivalent to a game B, then B is equivalent to A. By our definition, A is equivalent to B if and only if A+C and B+C have the same characteristic for any game C. Since A+C and B+C have the same characteristic for any game C, by a simple change in ordering, we see that B+C and A+C have the same characteristic for any game C, and hence, B is equivalent to A. For the transitive axiom, we need to show that if a game A is equivalent to a game B, and a game B is equivalent to a game C, then game A is equivalent to game C. By definition, if A is equivalent to B, then A+D has the same characteristic as B+D for any game D. Similarly, since B is equivalent to C, then B+E has the same characteristic as C+E. Since games D and E are arbitrary representatives of any game, B+D and B+E have the same characteristic, and therefore A+D has the same characteristic as B+E and by extension the same characteristic as C+E. Since we have shown that A+D has the same characteristic as C+E, and D and E were arbitrarily chosen to represent any game, we can make a substitution to say that A+F has the same characteristic as C+F for any game F, which shows that A is equivalent to C. This is precisely the transitive axiom, and since we have shown all three, we can conclude that this relation between games does in fact represent an equivalence relation.

We now proceed to investigate the various disjunctive sums of P and N games to provide a powerful tool which we might use in proving equivalencies of games. We want to see if there is a conclusive characteristic attached to the sum of two P-games. Examples seem to indicate that the result will always be a P-game itself, and we will verify this with an induction proof, with induction placed on the number of moves in the sum of the two games. Our general statement we wish to show is that given any two P-games, their sum will result in a P-game. Our base case is simply the sum of the zero game and itself. Naturally, this sum is a P-game since there are no moves. Our induction hypothesis states that for all P-games A and B such that A+B has at most n moves, A+B is a P-game. We need to show that for any two P-games C and D where C+D has at most n+1 moves, C+D is a P-game.

Note that one step before we reach the n+1 move implies that we have made a move in either C or D. Hence, whichever game we have taken this move in is now an N-game, since any move in a P-game results in an N-game. By definition of N-games, another move can be played in this same game to return it to a P-game. We now have two possibilities at n-1 moves which both represent the summation of two P-games. By our induction hypothesis, each sum is a P-game. Therefore, the possible sums at n-moves are N-games, since there exists a move that will result in the P-games we mentioned. Finally, since these sums are N-games and represent all possibilities of moves from C+D, we conclude that C+D is indeed a P-game. We have not only shown that the sum of two P-games will result in a P-game, but within our proof (the logical process which took as from the nth move, the sum of an N-game and a P-game, to the n-1 move, the sum of two P-games) there is a corollary that the sum of an N-game and P-game is necessarily an N-game. The last combination, the sum of two N-games, is inconclusive, which can be verified by simple examples.

These ideas are incredibly useful in proving equivalencies between games. The technique is a combination of our previous demonstrations: inducting on the moves in the game and verifying their characteristic properties when adding an arbitrary game. This concept gets extended into what we refer to as the Sprague-Grundy Theorem. We go one step further in the notion of equivalent games by creating a standard by which to compare all games. That is, all finite, impartial games has a particular “nimber,” value which denotes its equivalence to a specific heap in the game Nim. One method by which to evaluate games is to calculate its nimber value. It can be shown that every P-game will have a nimber that associates it with the 0-pile of Nim, whereas N-games will have positive nimber values corresponding to a given head in Nim (Conway). Other methods of analysis, such as a game’s suspense and remoteness function (which analyze how long a game can be drawn out or how quickly it can be finished), will also come into play in my research as I analyze a variation of the take-away game Euclid.