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.
No comments:
Post a Comment