Report

Crystal Bennett Joshua Chukwuka Advisor: Dr. K. Berg Chomp. Game Setup Rules of gameplay Positions Theorem 1 Proof of Theorem 1 Approach to 3x5 Approach to 3xn Theorem 1 Theorem 2 Theorem 3 Game Setup Standard game consists of a grid of size mxn. m = # of rows, n = # of columns. Position on grid denoted by (i, j) Game Setup (1, 1) square marked by “P” for poison is the least desired square. The You lose the game if you take the (1, 1) piece. Rules of Gameplay • Players 1 and 2 alternate removing squares from the grid. • Removing an (m, n) piece means taking (m, n) and (, ) where ≥ , ≥ . Rules of Game play. P P P Positions Let’s consider the position [u, v, w] where: u = # of blocks in row 1. v = # of blocks in row 2. w = # of blocks in row 3. If [u, v, w] is a position in Chomp. Then 0≤w≤v≤u. Plan We will analyze Chomp positions for w = 0, 1, 2. Theorem 1 Theorem: The complete list of all losing positions [u, v, w], where w ∈ 0, 1, 2 is: ○ = { [1, 0, 0], [ 2, 2, 1], [3, 1, 1], [u, u-2, 2] (u ≥ 4), [u, u-1, 0] (u ≥ 1)}. Proof Let be the list from the Theorem consist of all [u, v, w] with w ≤ 2 which are not in . Let Proof will show that every position in can be moved to a position in . We We will show that any move from any position in moves it into . Proof • . • = { [, , ] | ≤ 2, [, , ] is not in } • [0, 0, 0] ∈ . Proof • Notice: • We will only make moves from a position [u, v, w] where u ≥ v ≥ 2 to a position [, , ] where ≥ ≥ . Proof • When = 0, the following positions are in the set : • [1, 0, 0] • [u, u-1, 0] Proof • For [u, v, w], w = 0; the set of positions in can be described as: • [u, u, 0] • [u, u-k, 0], where k > 1. Proof • For the position [u, u, 0], [u, u, 0]→[u, u-1, 0] by taking piece (2, u). • For the position [u, v, 0], where v ≤ u – 2, [u, v, 0]→[v+1, v, 0] by taking the piece (1, v+2). Proof • When = 1, the following positions are in the set : • [2, 2, 1] • [3, 1, 1] Proof • For [u, v, w], w = 1; the set of positions in can be described as: • [u, u, 1] with u ≠ 2. • [2, 1, 1] • [u, u-1, 1], u ≥ 3 • [u, 1, 1], u ≥ 4 • [u, u-k, 1] where 2 ≤ k < u - 1, u > 3 Proof • For the position [u, u, 1], [u, u, 1]→[2, 2, 1] by taking the (1, 3) piece. • For the position [u, u - 1, 1], [u, u, 1]→[u, u - 1, 0] by taking the (3, 1) piece. Proof • For the position [u, u - k, 1], [u, u - k, 1]→[2, 2, 1] by taking the (1, 3) piece. Proof • For [u, v, w], w = 2; the set of positions in can be described as: • [u, v, 2], where v ≠ u -2. Proof • When w = 2, the following positions are in the set : • [u, u-2, 2] Proof • For the position [u, v, 2], where v = u or v = u-1; [u, v, 2]→[u, u-2, 2] by taking the (2, u-1) piece. • For the position [u, v, 2](where v < u-2), [u, v, 2]→[v+2, v, 2] by taking the (1, v+3) piece. Proof So for [u, v, w], w ≤ 2 • We have shown that every [u, v, w] in can be taken to a position in in one move. Proof • Then every winning position for , , , ≤ 2 can be taken to a losing position in one move. Proof • Now, we will show that for any position [u, v, w] in , we can move to a position in . Proof [1, 0, 0] → [0, 0, 0] Proof • Because the position [1, 0, 0] is in , the only move from [1, 0, 0] is the move: • [1, 0, 0]→[0, 0, 0] • And since [0, 0, 0] is in W. The game is now over. Proof [2, 2, 1] → [2, 2, 0] [2, 2, 1] →[1, 1, 2] [2, 2, 1] →[2, 0, 0] [2, 2, 1] →[1, 1, 1] Proof [u, u - 1, 0] →[u - 1, u - 1, 0] [u, u - 1, 0] →[u, u - k, 0] [u , u - 1, 0] → [u – k , u - k, 0] Proof [u, u - 2, 1] →[u, u - 2, 0] [u, u - 2, 1] →[u, u - k, 1] [u, u - 2, 1] →[u-1,u – 2, 0] [u, u - 2, 1] →[u - s, u - k, 1] Proof [3, 1, 1] → [3, 1, 0] [3, 1, 1] →[3, 0, 0] [3, 1, 1] →[2, 1, 1] Proof • The first player can force the game to go from position to position and back to position. Theorem 2 For any complete chomp grid of size m by n, there is a winning strategy. In other words, any one player before the starting of the game can always be sure of winning. PROOF: Because it is a complete m by n grid, it will have a square at its upper-right hand corner . Either taking that square is a winning move or it is not. Case 1: If it is a winning move, player 1 makes it and wins the game. Case 2: If it is a losing move then player 2 has a winning move in response to the first move which he makes and then wins the game. However, player 1 could have made player 2 move because it would require the removal of the square at the upper right hand corner and he would win the game. Theorem 2. P Theorem 3 For any chomp grid of size m by n (where m=n), that is a m by m grid, there is a winning strategy and the winning move is to take the (2,2) square. If the first player take the (2,2) square we would have 1 row and 1 column. Excluding the poisoned square,, there is (m-1) columns and rows. Then, the second player can only chomp from the bottom squares or the left squares. Since both are equal, it does not matter which squares player 2 takes from. His move always makes them unequal and the winning strategy for player 1 is to make his next move such that the 1nth row and column(without poison) have equal number of squares. This way, player 1 takes the last square from either the row or the column and then player 2 is left with the poisoned square and then loses. Theorem 3 P Theorem 4 For all stair case kind of chomp grid of step size 1, that is any row has one square more than the row above it there is a winning strategy.(except the first staircase) Case 1: For the staircase with three rows, the winning move is to chomp the (2,2) square. Case 2: For any staircase, the winning move is to chomp any square that makes the staircase a 2 by n with a winning move already made. PROOF: Case 1 is true by theorem 3. Case 2 is true by theorem 1. Therefore, there is always a winning strategy for all staircase(excluding the (1,1)) Theorem 4 contd. Approach to 3x5 Start at the 2x2 Square finding the winning positions. Add one square at a time to the grid solving for the winning moves up until the 3x5 grid. Analyze different types of staircase grids where the bottom, middle, and top row all have different lengths. P Approach to 3x5 The position (3,4) is a winning position for the 3x5 grid. How do I prove this. Analyze the winning moves for all grids up to the 3x5 . Identify any patterns, or relations that may exist. 1 P Approach to 3x5 1 P * * * * Approach to 3x5 1 P * * * Approach to 3x5 1 P * * Approach to 3x5 1 P * 3x6 Chomp Grid. Losing Position. W1 P 3x6 Chomp Grid. Possible Cases. CASE 10 CASE 11 CASE 12 CASE 7 CASE 8 CASE 9 CASE 1 CASE 2 CASE 3 CASE 4 CASE 5 CASE 6 3x6 Chomp Grid. Case 1 • Case 1 is true by the Rules of Game play 3x6 Chomp Grid. Case 2 P • Case 2 is true by Theorem 2 3x6 Chomp Grid. Case 3 P • Case 3 is true by Theorem 2. 3x6 Chomp Grid. Case 4 P Case 4 is true by Theorem 2. 3x6 Chomp Grid. Case 5 P • Case 5 is true by Theorem 1. 3x6 Chomp Grid. Case 6 P Case 6 is true by Theorem 1. 3x6 Chomp Grid. Case 7 P Case 7 is true by Theorem 1. 3x6 Chomp Grid. Case 8. P Case 8 is true by the square chomp Theorem 3. 3x6 Chomp grid. Case 9 P 3x6 Chomp Grid. Case 10 P Case 10 is true by Theorem 3.(2xn) 3x6 Chomp Grid. Case 11 P Case 11 is true by Theorem C. 3x6 Chomp Grid Case 12 P Case 12 is true by Theorem c Approach to 3xn Use 2x2 up to 3x5 findings to solve larger grids at finding the winning positions. Add one square at a time to the grid solving for the winning moves. Analyze different types of staircase grids where the bottom, middle, and top row all have different lengths. Record winning positions to see if we can find a relationship between the winning positions. 3x7 Chomp Grid. 3x7 Chomp Grid. CASE 15 CASE 16 CASE 17 CASE 18 CASE 8 CASE 9 CASE 10 CASE 11 CASE 12 CASE 13 CASE 14 CASE 1 CASE 2 CASE 3 CASE 4 CASE 5 CASE 6 CASE 7 Q U E S T I O N S COMMENTS CONCERNS