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