Report

. AE1APS Algorithmic Problem Solving John Drake Previously we introduced matchstick games, using one pile of matches It is possible to have more than one pile of matches First a pile must be chosen, then matches may be removed from the chosen pile according to some rule (which may differ from pile to pile) The game is thus a combination of two games Combinations of games is such a way are known as sum games We have two games, each with its own rules Let us call the two games, the left and right games A position in the sum game is the combination of the position in the left game and the position in the right game A move in the sum game is a move in one of the left or right games A graph represents a game. The positions are represented by nodes. The moves are represented by edges. Imagine a coin placed on a node. A graph represents a game. The positions are represented by nodes. The moves are represented by edges. Imagine a coin placed on a node. A graph represents a game. The positions are represented by nodes. The moves are represented by edges. Imagine a coin placed on a node. A graph represents a game. The positions are represented by nodes. The moves are represented by edges. Imagine a coin placed on a node. In the sum game, two coins are used One coin being placed over a node in each of the two graphs A move is then to choose one of the coins, and move it along an edge to another node A move changes the position of one of the coins The two games are unstructured, thus we have to use brute force to determine if they are winning or losing positions The left game has 15 positions, the right game has 11 positions How many positions are there in the sum game? There are 15*11 positions (165) Brute force is not a desirable approach We now look at how to compute a strategy for the sum of two games We find that the computation effort needed to find winning and losing states is not the product, but the sum of the computational effort for the individual games. Suppose there are two piles of matches A move is to choose a pile of matches, and remove at least one match from that pile The game is lost when a player cannot remove any matches. Given a pile of matches, remove at least one The winning positions are the positions where there is at least one match The winning strategy is to remove all the matches The losing position contains no matches Draw the state transition diagram The single game strategy cannot be applied directly to the sum game Why not? Symmetry between left and right allows us to identify a winning strategy. Let m, n represent the number of matches in the two piles. In the end m=n=0. This suggests m=n identifies losing positions. Choose the larger pile and restore the property that m=n. i.e. maintain the invariant The property n!=m is the precondition for the winning strategy to be applied Equivalently m<n or n<m. If m<n , we infer 1 <= n-m <=n So n-m matches can be removed from the pile with n matches. After the assignment n:=n-(n-m), the property m=n will hold. Suppose K matches can be removed (K is fixed) This restriction disallows some winning moves We are not allowed to remove m-n matches when K<m-n The property m=n no longer characterises losing positions. Example K=1 Lets set K=1 (2, 0). A player is forced to move to (1, 0) and the opponent can then win the game. It seems that the strategy of restoring symmetry no longer applies Worse, if the number of matches we are allowed to remove from the two piles differs Even worse, the left and right games may be completely different!!! With one pile of matches, where M matches at most can be removed, The winning strategy is to continually restore the property that the remainder after dividing the number of matches by M+1 is 0 (i.e. m mod (M+1) == 0) The number, m mod (M+1) == 0, determines if the position is winning or not. The one player game suggests the symmetry as: m mod (M+1) = n mod (N+1) We will prove this in later lectures. In the final position (0,0), this property is satisfied.