Report

AE1APS Algorithmic Problem Solving John Drake Invariants – Chapter 2 River Crossing – Chapter 3 Logic Puzzles – Chapter 5 Matchstick Games - Chapter 4 ◦ Matchstick Games – Winning Strategies ◦ Subtraction-set Games Sum Games – Chapter 4 Induction – Chapter 6 Tower of Hanoi – Chapter 8 The goal is to have some method (i.e. algorithm) do decide what to do next so that the eventual outcome is a win The key to winning is to recognise the invariants Remember - An invariant is something that does not change We will work with matchstick games We identify winning and losing positions in a game A winning strategy is therefore maintaining an invariant Played with one or more piles of matches Two players make alternate moves A player can remove one or more matches from one of the piles, according to a given rule The game ends when there are no more matches to be removed The player who cannot take any matches is the loser, i.e. the player who took the last match(es) is the winner This is an impartial, two person game with complete information. Impartial means rules for moving apply the same to both players. Complete information means that both players have complete information about the game i.e. they know the complete state of the game. An impartial game that is guaranteed to terminate, it is always possible to characterise the positions as winning or losing positions. A winning position is one from which we can assure a win. A losing position is one from which we can never win. A winning strategy is an algorithm for choosing moves from winning positions that guarantees a win (i.e. we maintain an invariant). Suppose there is one pile of matches, and a player can remove either 1 or 2 matches How do we identify winning and losing positions? Draw a state transition diagram (p.70) Nodes are labelled with the number of matches remaining Edges define the transition of state when a number of matches removed on that turn We can now label the nodes as winning or losing A node is winning if there is an edge to a losing position A node is losing if every edge from the node leads to a winning node (i.e. we cannot escape from the losing situation) Node 0 is losing, as there are no edges from it Nodes 1 and 2 are winning, as there is an edge to node 0 Node 3 is losing, as both edges from 3 are to nodes 1 and 2 which are already labelled as winning A clear pattern emerges; losing positions are where the number of matches is a multiple of 3 Beginning from a state in which n is a multiple of 3, and making and arbitrary move, results in a state in which n is not a multiple of 3. Thus removing n mod 3 matches results in a state in which n is again a multiple of 3. NB: Only labelled to 7 The terminology we use to describe the winning strategy is to maintain invariant property that the number of matches remaining is a multiple of 3 If both players are perfect, the winner is decided by the starting position. If the starting position is a losing position, the second player is guaranteed to win. Starting from a losing position, you can only hope that your opponent makes a mistake, and puts you in a winning position. Some variations on the matchstick game: There is one pile of matches, each player is allowed to remove 1, 3, 4 matches There is one pile of matches, each player is allowed to remove 1, 3, 4 matches, except that you are not allowed to repeat the last move. So if you opponent removes 1 match you must remove 3 or 4. What are the winning positions and what are the winning strategies.? What are the winning positions and what are the winning strategies? {1, 3, 4} Subtraction subset We can remove 1 or 3 or 4 matches. Calculate the remainder r after dividing by 7 i.e. mod 7 If r is 0 or 2, the position is a losing position. Otherwise it is a winning position. The winning strategy is to remove 1 match if r=1, Remove 3 matches if r=3 or r=5, remove 4 matches if r = 4 or r =6. Suppose a daisy (a flower) has 16 petals arranged symmetrically around its centre. Two players take it in turns to remove petals. A move means taking one petal or two adjacent petals. The winner is the person who removes the last petal. Who should win and what is the winning strategy.