Finite Two-person Deterministic Games Impartial Games Nimbers Danny Sleator Andrew's Leap, 2000 Games we discuss: 2 person perfect information alternating move finite number of moves at each state finite in length Sometimes called "tree games", cause you can draw a tree. Examples: tic-tac-toe connect-4 othello nim sprouts take-away-1-2-3 (A row of 12 matches, and you can take away 1 or 2 or 3 in your move. The goal is to take the last match.) chess (have to assume game draw declared when 50-move or repetition occurs) The two players will be White and Black (White goes first) Example ..... The "natural outcome" of a game is the best outcome that White (the first player) can achieve if he always makes the best possible move. It's easy to see how to compute the natural outcome of a game. Just propogate the values up the tree. The leaves are labeled with the outcome (say W,D,B for White wins, Draw, or Black wins). On nodes where it's white to move, the node is labeled with the best of the nodes below it from white's perspective. Similarly for black. Impartial games Some of the games discussed have the property that the set of moves available in a position are not dependent on whose move it is, and the winner is the one who makes the last move. Nim, sprouts, and take-away-1-2-3 are like this. Games like this are called impartial games. (There are "Mise're" versions of all these games that arise if the goal is to get stuck with the last move. The elegant theory developed below does not work for these games.) You can think of an impartial game as simply a set. The set is in turn a collection of sets, where each internal set is just the game resulting from one of the moves of the first player. All of these sets are finite. Let @ denote the game with no moves. Alternatively, you can think of an impartial game as a tree. We say that two games are equal (A=B) if the trees of the two games are isomorphic. That is, you can draw the two trees so that they look exactly the same by reordering the children at each node. [Some of the the following definitions and theorems come from a handout prepared by Dana Scott.] The RANK of a game A, denoted |A| is just: |A| = 1 + max |b| and |@| = 0 b in A The rank is just the maximum number of moves that can occur in the game. (Maybe the rank is used on some induction proofs....) The VALUE of a game, denoted ||A|| is defined as follows: ||A|| = max -||b|| and ||@|| = -1 b in A So the value of a position that is a loss is -1 and the value of a win is 1. The join of two games A and B is a new game. It is denoted A*B (Dana uses A circle-plus B). The intuitive definition is as follows. A move in A*B is made by picking one of A or B and making a move in that game. So, for example, if the player makes a move in A, which leaves a, then the game that results after the move in the joined game is a*B. Here's a more formal definiton: A*B = {a*B | a in A} union {A*b | b in B} A*@ = A @*B = B The following theorems are easy to prove: Theorem: A*B = B*A Theorem: A*(B*C) = (A*B)*C One of the main goals of the theory we develop is a way to characterize useful properties of the join of two games knowing someting about the two games. We start with some obvious things: Theorem: (1) If ||A|| = -1 and ||B|| = -1 then ||A*B|| = -1 (2) If ||A|| = 1 and ||B|| = -1 then ||A*B|| = 1 (3) If ||A|| = -1 and ||B|| = 1 then ||A*B|| = 1 Proof: (1). We're trying to show that there's a winning strategy for the second player in the joined game A*B. We can prove this by induction on the rank of the games (i,j). Assume we've shown part (1) for all pairs (i', j') where either i' 0. In this case we exhibit a winning strategy for the first player. This strategy is simply to make a move that results in a position with nimber 0. This is of course possible (because all nimbers less than the nimber of the position are achievable, including 0). So after the move, the resulting position has value -1 (by induction). This completes the proof of the theorem. Q.E.D. As I mentioned above, it's going to turn out that [A*B] = f([A],[B]). That is, that the nimber of the join of two games is just a function of the nimbers of the two parts. This is very important from a computational point of view, because it means that if you can split a game up and evaluate the nimbers of each part, you can compute the nimber (and thus the value) of the whole game. The purpose of the theory is to prove this fact about nimbers. Lemma: [A] = [B] if and only if ||A*B|| = -1 Proof: Assume [A]=[B]. Consider A*B. No matter what move the first player makes, the result is a position that is the join of two games with differing nimbers. The value of this position is (by induction) therefore 1. Similarly, if [A] != [B], then the first player can move in the game with the largest nimber and reduce its nimber to be equal to the nimber of the other game. This, by induction, is a lost position. An alternative formulaton of this lemma is: [A]=[B] iff [A*B]=0. We define EQUIVALENCE of games as follows. A ~ B (A is equivalent to B) if for all games X the following holds: ||A * X|| = ||B * X|| It turns out that nimbers allow us to determine equivalence. Theorem: A ~ B if and only if [A] = [B] Proof: Let's first prove that A ~ B implies [A]=[B]. Choose X=A. Then we have: ||A*A|| = ||B*A||. By the lemma, the left side of this is -1. And again by the lemma the right side being -1 implies that [A]=[B]. The other direction follows because the lemma tells us that the value of a game A*X only depends on the nimbers of A and X. Thus if [A]=[B] then the value of A*X and B*X are the same for all X. Q.E.D. The key thing we still need to be able to do is determine the nimber of the join of two games from the nimber of the two games. For one thing, it's not even clear that the nimber of the join is even a function of the nimbers of the two games being joined. We'll prove this next. Theorem: [A*B] is a function only of [A] and [B]. Proof: First we need a bit of notation. Let denote the nim game with one row of k matches. As noted above [] = k for any k >= 0. So this is a simple specific game with a specific nimber. Clearly for these games, the theorem holds. Because there is a unique such game of this class with a given nimber. So there's some function f(.,.) satisfying this: [*] = f(i, j) We want to show, for all games A and B, that: [A*B] = f([A], [B]) Consider this quantity: [(A*B) * (<[A]>*<[B]>)] If we can show that this is 0, then we know that: [A*B] = [<[A]>*<[B]>] = f([A], [B]) Let's do this. [(A*B) * (<[A]>*<[B]>)] = = [A * B * <[A]> * <[B]>] = [(A*<[A]>) * (B*<[B]>)] Now [A] = [<[A]>]. So the left part of this has nimber 0. The right part is similarly 0. Therefore the nimber of this join is also 0. This completes the proof. Q.E.D. It remains to compute f(i,j). Our final theorem tells how to do this. Theorem: [*] = f(i, j) = i^j, where "^" denotes the bitwise exclusive or operation. Proof: To prove this by induction, it sufficies to prove the following assertion: For any i,j, the minimum non-negative integer NOT in the set {0^i,1^i,2^i...(j-1)^i, j^0, j^1, ... , j^(i-1)} is i^j. (Here ^ denotes xor). First of all, clearly i^j is not in this set. Let's show that any number k less than i^j is in the set. The fact that k < i^j means that the first place where k and i^j differ is on some bit where i^j is 1 and k is 0. Because in this position i^j is a 1, either i is a 1 in that position or j is. WLOG, assume it the 1 is in i. Now we're going to decrease i to a new number i' so that this bit becomes 0. i' can be chosen so that the bits below that can be anything we want. In particular we can choose them so that i' ^ j obtains the desired value, namely k. Q.E.D. Note: The reason we had to go through all this convoluted stuff is because the above construction does not work for arbitrary games. It only works for simple nim piles, like . In general in a game A, it will be possible to make moves whose nimber is any nimber less than [A], but it will also in general be possible to make moves that have nimbers greater than [A]. This causes any inductionp proof like that used in the last proof to break down. At least that's the thinking that led to this argument.