The Next Move Some Theory And Practice With Impartial

Transcript

The Next Move Some Theory and Practice with Impartial Games Saturday Morning Math Group March 1, 2014 Combinatorial games are two-player games with the following characteristics: • • • • Two players alternate moves. Play continues until there are no legal moves remaining. No element of chance is involved (i.e. dice, spinners, etc.). Each player has full knowledge of the game position at all times. In normal play, the last player to make a legal move wins. In misère play, the last player to make a legal move loses. A combinatorial game is called impartial if both players have the same set of allowable moves at each position of the game. A game in which the allowable moves depends on the player is called a partisan game. Example of an impartial game: SUBTRACTION {1, 2, 3} Alice and Bob play a game in which they start with a pile of 25 chips. At each turn, a player must remove 1, 2, or 3 chips from the pile. The player who makes the last legal move wins. If Alice goes first and both players play perfectly, will Alice or Bob win the game? (Playing perfectly means that if you have a winning move, you make it.) Problem: Identify starting positions for SUBTRACTION {1, 3, 6} that guarantee a win for the first player. Terminology: • • A game is in P position if the previous player can force a win. A game is in N position if the next player can force a win. Graph of a game: • • Nodes are positions. Directed edges connect each position to all possible following positions. Key to labeling nodes: • • • Terminal positions are P positions. If all the edges from a node point to N positions, label the node P. If there is at least one edge pointing to a P position, label the node N. Label the nodes of the graph below: Answer: Note that for a graph labeled in this manner: • • From a non-terminal P position, a player can only move to an N position. From an N position, a player can always move to a P position. Analysis of SUBTRACTION {1, 2, 3} Identify each position as an N position or a P position. n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 8 9 10 11 12 13 Pos Analysis of SUBTRACTION {1, 2, 3} Identify each position as an N position or a P position. n 0 1 2 3 4 5 6 7 Pos Question: If you are playing SUBTRACTION {1, 3, 6} starting with 10 chips, would you choose to go first or second? What if there were 25 chips? Answers: SUBTRACTION {1, 2, 3} n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 Pos P N N N P N N N P N N N P N SUBTRACTION {1, 3, 6} n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 Pos P N P N P N N N N P N P N P If you are playing SUBTRACTION {1, 3, 6} starting with 10 chips, you should choose to go first since the position corresponding to 10 chips is an N position. If there are 25 chips to start with you should choose to go second. The pattern PNPNPNNN repeats, so the position corresponding to 25 chips is a P position. The White Knight The game of White Knight is played on a chessboard with one knight. From any space on the board, the knight has at most four allowable moves: Either move up two spaces then one space to the left or right, or move left two spaces, then one space up or down. The four squares in the upper left hand corner of the board are the “Home” squares. The first player to get the knight onto one of the home squares wins. Identify each square on the chessboard as an N position or a P position. Answer: P P N N P P N N P P N N P P N N N N N N N N N N N N N N N N N N P P N N P P N N P P N N P P N N N N N N N N N N N N N N N N N P The first complete mathematical analysis of a combinatorial game was published in 1901 by Charles Bouton, who gave a winning strategy for the game Nim. The ideas used to solve Nim have been instrumental in understanding the theory of impartial games. Nim is usually played with three piles of sticks called Nim heaps, although any number of heaps can be used. Players take turns removing any positive number of sticks from one of the piles. Traditionally, the last person to make a legal move loses (misère play), but we will consider normal play in which the last person to make a legal move wins. Play NIM{3, 4, 5} and try to identify winning (or losing) moves. Experiment with other starting positions. JIM (Japheth’s Nim) To play the game, you need 18 disks that are red on one side and green on the other. To begin the game, place one disk in each square, some with the red side up and some with the green side up. Players take turns changing the color of the chips according to the following rules: RULES: On your turn: 1. You may turn over chips in one row only. 2. You must move left to right as you turn the chips. 3. The first chip you turn must change from green to red. 4. Subsequently, you may turn chips from red to green or green to red for the rest of that row. 5. The last player to make a legal move wins. This game was described by Japheth Wood on his Math Wizard blog as a way of understanding the winning strategy in NIM. NIMBER ARITHMETIC Nimber addition on the binary numbers is the usual addition, but without carrying. For example, in regular binary arithmetic, , but in nimber arithmetic, . Compute 101100 ⊕ 110101 (Answer: 11001) Compute 3⨁4⨁5 (Answer: In binary notation 3 is 11, 4 is 100, and 5 is 101, and so the nim sum is 11 ⊕ 100 ⨁ 101 = 10) Which of the summands above can be decreased so that the resulting nim-sum is 0? (Answer: Reduce the 3 to 1 to get 1 ⊕ 100 ⨁ 101 = 0.) Key to winning at Nim: Keep the nim-sum zero. This is possible because: • • If the nim-sum of the heap sizes is 0, a move in Nim must make it non-zero. If the nim-sum of the heap sizes in non-zero, there is always a legal move in Nim that will make it 0. Since the terminal position in normal play is {0, 0, 0}, the player who can maintain a nim-sum of zero will win. Question to think about: How should the strategy by modified to win Nim in misère play? (Hint: The same strategy will work right up to the last few moves.) Northcott’s Game: Northcott’s Game is a partisan game played on a checkerboard with one white checker and one black checker on each row. “White” moves the white pieces and “Black” moves the black pieces. A checker may move any number of squares along its row, but may not jump over or onto the other checker. Players move alternately and the last to move wins. (Hint: The strategy for winning at Nim will help you find a winning strategy for Northcott’s game,) Idea behind theory of impartial games: Each position in a game is assigned a numerical value, the Sprague-Grundy (SG) value, determined by its graph. The SG value of a node (position) is the Minimum Excluded Value (mex) of all its followers (i.e., the smallest non-negative number not found among the SG values of the nodes directly connected to that position). For example, mex{0, 1, 4, 5} = 2, and mex{ 1, 2, 5} = 0. Example: Compute the SG values on the graph below: Example: Compute the SG values on the graph of a game of Subtraction {1, 2, 3} with 10 chips. n 0 1 2 3 4 5 6 7 8 9 SG Example: Compute the SG values of a single nim heap with 5 chips. n SG 0 1 2 3 4 5 10 11 12 13 Answers: SG values on the graph: SG values on the graph of a game of Subtraction {1, 2, 3} with 10 chips. n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 SG 0 1 2 3 0 1 2 3 0 1 2 3 0 1 SG values of a single nim heap with 5 chips. n 0 1 2 3 4 5 SG 0 1 2 3 4 5 In general, the SG value of a Nim heap with n chips with be equal to n. When a position has an SG value of 0, all moves from that position will have non-zero SG values. On the other hand, if a position has a non-zero SG value, then one of its follows must have an SG value of 0. In other words, an SG value of 0 corresponds to a P position and a nonzero SG value corresponds to an N position. Compute the SG values of the positions for the White Knight game. Answer: 0 0 1 1 0 0 1 1 0 0 2 1 0 0 1 1 1 2 2 2 3 2 2 2 1 1 2 1 4 3 2 3 0 0 3 4 0 0 1 1 0 0 2 3 0 0 2 1 1 1 2 2 1 2 2 2 1 1 2 3 1 1 2 0 In the disjunctive sum of two games G and H, each play can choose one of the games and make a legal move in that game. The game is over when terminal positions are reached in both games. For example, Nim can be considered as the disjunctive sum of three single-heap Nim games. To analyze a game, break it up into the disjunctive sum of subgames. Then compute the SG values for the positions in each sub-game. The SG value for a position in the original game is the nim-sum of the component SG-values. Example: The SG value of a single Nim-heap of size n is n, and the SG value of the Nim position (𝑛1 , 𝑛2 , 𝑛3 ) is 𝑛1 ⨁𝑛2 ⨁𝑛3 . Example: The White Knight Plus Chips In this variant of The White Knight, you begin with the knight placed somewhere on the chessboard and 6 chips next to the board. On each move, you may either choose to move the knight one legal move, or remove any number of chips from the pile. If the knight begins on E5, what move should you make? Example: Will the first or second player win the following variation on Nim (Subtraction Nim)? Start with three stacks of chips {10, 6, 13}. At each turn, each player must decrease the size of exactly one stack by taking • • • At most 2 chips from the first stack, At most 3 chips from the second stack, or At most 4 chips from the third stack. Answers: White Knight plus chips: This is the disjunctive sum of the game of White Knight and oneheap NIM. The SG value of the E5 position in White Knight is 4 and the SG value of NIM heap is 6. The nim-sum is therefore 100 ⊕ 110 = 10. To reduce this to a nim-sum of 0, we must decrease the SG value of the pile of chips to 4. So the first move should be to remove two chips. Subtraction Nim: The SG value of 10 chips in SUBTRACTION {1, 2} is 1, the SG value of 6 chips in SUBTRACTION {1, 2, 3} is 2, and the SG value of 13 chips in SUBTRACTION {1, 2, 3, 4} is 3. The nim-sum of the disjunctive sum of these games is 1⨁10 ⨁ 11 = 0. Therefore the second player will win. More Variants of Nim – All can be played using normal play or misère play. GREEDY NIM: Same rules as Nim, but each player must take from a heap with the largest number of sticks. ENDNIM: Same rules as Nim, but the Nim heaps are in a row and each player must remove from one of the stacks on the ends of the row. PARTISAN ENDNIM: Same rules as Endnim, except that the Left player can only take from the leftmost heap and the Right player can take only from the rightmost heap. WYTHOFF’s GAME: Start with two heaps. Players can remove any number of sticks from either one of the heaps, or can remove the same number of sticks from both heaps. Reference: For further reading on the subject, I highly recommend the book from which I got most of the material presented here: Winning Ways for your Mathematical Plays, by Elwyn Berlekamp, John H. Conway, and Richard K. Guy, Volume 1, 2nd Edition, A. K. Peters, Ltd., 2001