From: Jesse Merriman Date: 2007-04-19T11:24:25+09:00 Subject: Re: [QUIZ] Magic Fingers (#120) --Boundary-00=_ALtJGEH0xbm6z8m Content-Type: Multipart/Mixed; boundary="Boundary-00=_ALtJGEH0xbm6z8m" --Boundary-00=_ALtJGEH0xbm6z8m Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: 7bit Content-Disposition: inline My original solution to this quiz had a lot of problems, but I think I fixed them now. I re-worked my StateTree class into the new StateGraph class (which is what it originally should have been named anyway). Basically, now I build a graph of states, with a node for each state and an edge for each touch/clap state change (StateGraph#build & StateGraph#build_recurse). This graph is then repeatedly traversed, so that definite outcomes propagate through it (each state has a best_outcome attached to it) (StateGraph#propagate_outcomes). Once no more changes are made, the propagation is complete. Then each node's best_outcome contains the best outcome for the player whose turn it is at the node. So if the root is, say, Outcome::P2Win, then player 2 is guaranteed a winning strategy. (Another change from my first submission: Outcome::Loop has been replaced with Outcome::Unknown, which all states default to at first. If they are still unknown after executing StateGraph#propagate_outcomes, looping is the best they can do. The code is longer than I'd like, and there's some definite redundancy and ugliness in there, but I've spent far too long debugging this to feel like cleaning it up now. Speaking of debugging, it became quite a chore to verify that my program was working right, so I wrote a little script to turn a StateGraph into input for the graph-drawing program GraphViz. This did add to the bloat, but I think it was worth it, since being able to look at the graphs made things much easier. By setting FingersPerHand to 2, I generated the attached f2.png image. That's not very impressive, but you can see the next step up here (somewhat large): http://www.jessemerriman.com/images/ruby_quiz/120_magic_fingers/f3.png For higher values its impractical, both for the size of the generated image, and the running time of the image generator. In the images, yellow nodes are loop states, green are states that lead to player 1 winning, dark green are actual player 1 win nodes, red are states that lead to player 2 winning, and magenta are actual player 2 win nodes. The asterisks show whose turn it is. Touch edges are solid and black, while clap edges are dashed and gray. Using grep & wc -l on my dot files, I came up with the following stats: FingersPerHand #Nodes #Edges -------------- ------ ------- 2 4 3 3 46 64 4 156 316 5 382 1000 6 784 2444 (any higher than 6 and I get stack overflows). One thing I could have done differently was not count whose turn it is in the state, and just reverse the outcome or not depending on whose it is. But then I'd have to store an array of reachable outcomes in each state, instead of just the single best one for its player. The diff between my original submission and my new code would be pretty long, so I'm just going to paste it all in here: # ------------------------------------------------------------------- #!/usr/bin/env ruby # constants.rb # Ruby Quiz 120: Magic Fingers Left, Right = 0, 1 # hand array indices Player1, Player2 = 0, 1 # player array indices FingersPerHand = 5 # on my machine, > 6 causes a stack overflow # ------------------------------------------------------------------- #!/usr/bin/env ruby # outcome.rb # Ruby Quiz 120: Magic Fingers require 'constants' module Outcome # Order important: from best-for-player-1 to best-for-player-2 Outcome::P1Win = 0 Outcome::Unknown = 1 Outcome::P2Win = 2 # Given an Enumerable of outcomes, return the one that is best for the given # player. def Outcome.best(player, outcomes) best = (player == Player1) ? outcomes.min : outcomes.max best.nil? ? Outcome::Unknown : best end end # ------------------------------------------------------------------- #!/usr/bin/env ruby # state.rb # Ruby Quiz 120: Magic Fingers require 'constants' require 'outcome' require 'set' # Represents one state of the game, which includes how many fingers are on each # player's hands, and whose turn it is. States can also have parents, and a # best_outcome can be assigned to them, though this class doesn't do anything # with that itself. The player's hands are always sorted, since it doesn't # matter having 3-left and 2-right is equivalent to 2-left and 3-right. When # comparing states with ==, eql?, or their hashes, only @players and @turn are # taken into account. class State attr_reader :players, :turn, :parent, :best_outcome attr_writer :best_outcome # player_1 and player_2 are Arrays of number-of-fingers on each hand. def initialize(player_1, player_2, turn, parent = nil) @players = [player_1, player_2] @turn = turn @parent = parent @touch_reachable = @clap_reachable = nil for player in @players do State.normalize(player) end if end_state? @best_outcome = (self.winner == Player1 ? Outcome::P1Win : Outcome::P2Win) else @best_outcome = Outcome::Unknown end self end def hand_alive?(player_num, hand_num) @players[player_num][hand_num] > 0 end def player_alive?(player_num) hand_alive?(player_num, Left) or hand_alive?(player_num, Right) end # true if at least one player is dead. def end_state? not player_alive?(Player1) or not player_alive?(Player2) end # Return the winner. This should only be called on end states (otherwise, # it'll always return Player1). def winner player_alive?(Player1) ? Player1 : Player2 end # Turn the given player's hand into a fist if it has >= FingesPerHand # fingers up, and sort the hands. def State.normalize(player) for hand_num in [Left, Right] do player[hand_num] = 0 if player[hand_num] >= FingersPerHand end player.sort! end # Return a nice string representation of a player. def player_string(player_num) player = @players[player_num] '-' * (FingersPerHand-player[Left]) + '|' * player[Left] + ' ' + '|' * player[Right] + '-' * (FingersPerHand-player[Right]) end # Return a nice string representation of this state (including both player # strings). def to_s s = "1: #{player_string(Player1)}" s << ' *' if @turn == Player1 s << "\n2: #{player_string(Player2)}" s << ' *' if @turn == Player2 s end # Return a compact string representation. def to_compact_s if @turn == Player1 "[#{@players[Player1].join(',')}]* [#{@players[Player2].join(',')}]" else "[#{@players[Player1].join(',')}] [#{@players[Player2].join(',')}]*" end end # Equality only tests the players' hands and the turn. def ==(other) @players == other.players and @turn == other.turn end # Both eql? and hash are defined so that Sets/Hashes of states will only # differentiate states based on @players and @turn. def eql?(other); self == other; end def hash; [@players, @turn].hash; end # Yield once for each ancestor state, starting from the oldest and ending on # this state. def each_ancestor ancestors = [self] while not ancestors.last.parent.nil? ancestors << ancestors.last.parent end ancestors.reverse_each { |a| yield a } end # Have one player (the toucher) touch the other player (the touchee). def State.touch(toucher, toucher_hand, touchee, touchee_hand) touchee[touchee_hand] += toucher[toucher_hand] end # Yield each state reachable from this state by a touch move. def each_touch_reachable_state if @touch_reachable.nil? # Set to avoid duplicates. @touch_reachable = Set[] player = @players[@turn] opponent_num = (@turn + 1) % 2 opponent = @players[opponent_num] for player_hand in [Left, Right] do for opponent_hand in [Left, Right] do if hand_alive?(@turn, player_hand) and hand_alive?(opponent_num, opponent_hand) op = opponent.clone # because touch modifies it State.touch(player, player_hand, op, opponent_hand) if @turn == Player1 @touch_reachable << State.new(player, op, opponent_num, self) else @touch_reachable << State.new(op, player, opponent_num, self) end end end end end @touch_reachable.each { |r| yield r } end # Yield each state reachable from this state by a clap move. def each_clap_reachable_state if @clap_reachable.nil? # Set to avoid duplicates. @clap_reachable = Set[] player = @players[@turn] opponent_num = (@turn + 1) % 2 opponent = @players[opponent_num] # Clap rules. for source_hand in [Left, Right] do target_hand = (source_hand == Left ? Right : Left) # The first line is the number that can be removed from the source. # The second is the number that can be added to the target without # killing it. max_transfer = [player[source_hand], (FingersPerHand - player[target_hand] - 1)].min (1..max_transfer).each do |i| # skip transfers that just flip the hands next if (player[source_hand] - i) == player[target_hand] p = player.clone p[source_hand] -= i p[target_hand] += i if @turn == Player1 @clap_reachable << State.new(p, opponent.clone, opponent_num, self) else @clap_reachable << State.new(opponent.clone, p, opponent_num, self) end end end end @clap_reachable.each { |r| yield r } end # Yield once for each state reachable from this one. def each_reachable_state each_touch_reachable_state { |r| yield r } each_clap_reachable_state { |r| yield r } end end # ------------------------------------------------------------------- #!/usr/bin/env ruby # state_graph.rb # Ruby Quiz 120: Magic Fingers require 'constants' require 'outcome' require 'state' require 'set' class Set # Get an object in the Set which equals (by ==) obj. def get(obj) find { |x| x == obj } end end # Represents a tree of States in parent-child relationships. class StateGraph attr_reader :root, :edges def initialize(root = State.new([1,1], [1,1], Player1)) @root = root @node_clap_children = {} # Maps States to Arrays of their clapped children. @node_touch_children = {} # Maps States to Arrays of their touched children. build self end # Traverse the graph from the root, filling in @node_*_children. def build @seen_nodes = Set[] build_recurse(@root) remove_instance_variable :@seen_nodes end # Traverse the graph from the given node, filling in @node_*_children. def build_recurse(node) @seen_nodes << node @node_clap_children[node] = [] if not @node_clap_children.has_key? node @node_touch_children[node] = [] if not @node_touch_children.has_key? node # Here we have to be careful to not re-create nodes that are equal to # previously created nodes. This is why I added Set#get above. node.each_clap_reachable_state do |reached| if @seen_nodes.include? reached @node_clap_children[node] << @seen_nodes.get(reached) else @node_clap_children[node] << reached build_recurse(reached) end end node.each_touch_reachable_state do |reached| if @seen_nodes.include? reached @node_touch_children[node] << @seen_nodes.get(reached) else @node_touch_children[node] << reached build_recurse(reached) end end end # Call a Proc for every state encountered in the tree. # All procs should accept two arguments: the found state, and # the state from which it was found (nil for the root, may be different from # what the state reports as its parent, if there is more than one parent). def walk(new_clap_proc, new_touch_proc, old_clap_proc, old_touch_proc) @seen_nodes = Set[] new_touch_proc[@root, nil] walk_recurse(@root, new_clap_proc, new_touch_proc, old_clap_proc, old_touch_proc) remove_instance_variable :@seen_nodes end def walk_recurse(node, new_clap_proc, new_touch_proc, old_clap_proc, old_touch_proc) @seen_nodes << node @node_clap_children[node].each do |reached| if @seen_nodes.include?(reached) old_clap_proc[reached, node] else new_clap_proc[reached, node] walk_recurse(reached, new_clap_proc, new_touch_proc, old_clap_proc, old_touch_proc) end end @node_touch_children[node].each do |reached| if @seen_nodes.include?(reached) old_touch_proc[reached, node] else new_touch_proc[reached, node] walk_recurse(reached, new_clap_proc, new_touch_proc, old_clap_proc, old_touch_proc) end end end # Yield for each node in the graph. def each_node # Can use either @node_clap_children or @node_touch_children here. @node_clap_children.each_key { |node| yield node } end # Yield for every child of the given node. def each_child(node) @node_clap_children[node].each { |child| yield child } @node_touch_children[node].each { |child| yield child } end # Starting from the root, pull up all outcomes that are absolutely determined # given perfect play. Eg, say we have a state, S. S can move to a win state # for player 1. If its player 1's turn in S, then S's best_outcome will be # set to Outcome::P1Win. The graph will be scanned from the root repeatedly # until no more changes can be made to let these outcomes propagate. If # complete is set to true, outcome propagation will be completely determined # for all states in the graph. If its false, only those that affect the root # will be determined. This is faster if you only care about knowing root's # outcome. def pull_up_outcomes(complete = true) begin @seen_nodes = Set[] @changed = false if complete each_node { |node| pull_up_recurse(node) } else pull_up_recurse(@root) end end while @changed remove_instance_variable :@seen_nodes remove_instance_variable :@changed end def pull_up_recurse(node) @seen_nodes << node if node.best_outcome == Outcome::Unknown reachable_outcomes = Set[] each_child(node) do |reached| if @seen_nodes.include? reached reachable_outcomes << reached.best_outcome else reachable_outcomes << pull_up_recurse(reached) end end best = Outcome.best(node.turn, reachable_outcomes) if best != node.best_outcome node.best_outcome = best @changed = true end end node.best_outcome end end # ------------------------------------------------------------------- #!/usr/bin/env ruby # game.rb # Ruby Quiz 120: Magic Fingers require 'constants' require 'outcome' require 'state' require 'state_graph' class Game # Constructor. p1_start and p2_start are Arrays containing the number of # fingers on each of their hands at the start of the game. def initialize(p1_start = [1,1], p2_start = [1,1]) @graph = StateGraph.new(State.new(p1_start, p2_start, Player1)) self end # Print out an analysis of the game. def analyze @graph.pull_up_outcomes outcome = @graph.root.best_outcome if outcome == Outcome::P1Win puts 'Player 1, with perfect play, can win.' elsif outcome == Outcome::P2Win puts 'No matter how well Player 1 plays, Player 2 can win.' elsif outcome == Outcome::Unknown puts 'Perfect play by both players leads to a loop.' else puts 'I am broken.' end end end # ------------------------------------------------------------------- #!/usr/bin/env ruby # magic_fingers.rb # Ruby Quiz 120: Magic Fingers require 'game' # Note: These examples assume FingersPerHand == 5. Game.new.analyze # Normal, default game. #Game.new([1,1], [0,4]).analyze # P1 should win on move 1. #Game.new([4,4], [1,1]).analyze # P1 should win on move 2. #Game.new([0,1], [3,3]).analyze # P2 should win on move 2. # ------------------------------------------------------------------- #!/usr/bin/env ruby # state_graph_to_graphviz.rb # Ruby Quiz 120: Magic Fingers # This script outputs to stdout a dot file for use with GraphViz. # ./state_graph_to_graphviz.rb | dot -Tpng -o output.png require 'state_graph' GraphVizHeader = "digraph F#{FingersPerHand} {\nmargin=0.2" GraphVizFooter = '}' # Node with best_outcome == Outcome::Unknown. DefaultNodeOpts = '[width=1.5,shape=oval,style=filled,fillcolor=lightyellow]' # Node with best_outcome == Outcome::P1Win. P1WinParentNodeOpts = '[width=1.5,shape=oval,style=filled,fillcolor=green]' # Node with best_outcome == Outcome::P2Win. P2WinParentNodeOpts = '[width=1.5,shape=box,style=filled,fillcolor=red]' # End state node where player 1 wins. P1WinnerNodeOpts = '[width=2.2,shape=box,style=filled,fillcolor=darkgreen]' # End state node where player 2 wins. P2WinnerNodeOpts = '[width=2.2,shape=box,style=filled,fillcolor=magenta]' # Edge for state --clap--> state. ClapEdgeOpts = '[style="dashed",color=gray]' # Edge for state --touch-> state. TouchEdgeOpts = '[style="solid",color=black]' # Only for use with non-end-states. OutcomesToOpts = { Outcome::P1Win => P1WinParentNodeOpts, Outcome::P2Win => P2WinParentNodeOpts, Outcome::Unknown => DefaultNodeOpts } def node_opts(node) if node.end_state? node.winner == Player1 ? P1WinnerNodeOpts : P2WinnerNodeOpts else OutcomesToOpts[node.best_outcome] end end def name(state) state.end_state? ? 'End: ' + state.to_compact_s : state.to_compact_s end # Adds a newly clapped state to the graph. new_clap = lambda do |state, parent| name = name(state) puts "\"#{name}\" #{node_opts(state)};" if not parent.nil? puts "\"#{name(parent)}\" -> \"#{name}\" #{ClapEdgeOpts};" end end # Adds a newly touched state to the graph. new_touch = lambda do |state, parent| name = name(state) puts "\"#{name}\" #{node_opts(state)};" if not parent.nil? puts "\"#{name(parent)}\" -> \"#{name}\" #{TouchEdgeOpts};" end end # Adds a clap edge to an old state to the graph. old_clap = lambda do |state, parent| puts "\"#{name(parent)}\" -> \"#{name(state)}\" #{ClapEdgeOpts}" end # Adds a touch edge to an old state to the graph. old_touch = lambda do |state, parent| puts "\"#{name(parent)}\" -> \"#{name(state)}\" #{TouchEdgeOpts}" end puts GraphVizHeader # Create the initial state tree, with only end states' outcomes known. graph = StateGraph.new # Pull up all outcomes. graph.pull_up_outcomes # Walk the tree and generate GraphViz input. graph.walk(new_clap, new_touch, old_clap, old_touch) puts GraphVizFooter # ------------------------------------------------------------------- -- Jesse Merriman jessemerriman@warpmail.net http://www.jessemerriman.com/ --Boundary-00=_ALtJGEH0xbm6z8m Content-Type: image/png; name="f2.png" Content-Transfer-Encoding: base64 Content-Disposition: attachment; filename="f2.png" iVBORw0KGgoAAAANSUhEUgAAAQMAAAGBBAMAAACQh8krAAAAElBMVEX+//8AZAAA/wDT09MAAAD/ //87CdYqAAAAAXRSTlMAQObYZgAABMBJREFUeJzt3WGOoyAYxvG5wiQ9gXEPUsN+3zT1/ldZAXmr VkVF5G3z58NsW2flN4io6JP+tKXLv5/SAggQIECAAAECBAgQIFxGqHxp/D9/LiZUlZFSy6tjjgOE R+Wrey/286bKTqjq+epDsYv3tcU+wqO2f2as2DbKROgA8fqDYjtiB2E7wCO2bo7NhEe9B+AQGxti K2FfE+xqiI2E3U3QI7YYNhEeB5qgNzQnEQ4LOsPfUwirQ1Gs1FHDBsLBfiDtEOsPccIzTdAZkglJ m8GW2KaIEpIbIdoMUUK6oKrWmyFGeJ4gqOokQnJPcITVZogQHs0ZhGp1jIwQTtkOkS0RIdSTVdmT Nhmq7IvxWZR7J9vOVOEsr14bnnYSbH1SqXsxGjuNY4o3fJREmPRGW5+cOdTzBDm7NQPCWn880Aqj DWF/1I3UKj/G787eEG+EwabJQJjsEfMEI31ykbBWx75x4WgrpIwLk/54sC8kjY6TLSEEtzeMQaNK 3d7wIqxWse9IaUcad01X+2GnmRma3CWvG6L8L1epR8qF84XI0Wt8rpd6vqDgrEnDuaOCM2gN1xEa rqY0XFMquLJuNcwvaJhlaRXMNbUaZtxaBfOOrpSefXWl+By0L4Vn4gcOV/rOcfX9iGGJHwUgQIAA AQIECBAgQIAAAQIECBAgRMrTzjGlIb6A0FpC2hq+gfBUQUjcJb6B0ELwhMQVpBOeEGwpeZgqez+C fAT5iHj9QUE+okeQj+gR5CO8gXyEbwfyEbaQj/CFfIQjkI+w5Zp8xGp04pp8hF9k5hZdlY9wi5r+ 3TQ6kT0f8Wp6eUZ78rh8/nzEMqHfatnzESuEPjqRPx8RbYXs+Qh5I91x0hcuykfITjkTnbgoHyFD 00x04up8xPsi8hHxRviMM2gN1xEarqY0XFMquLJuNcwvaJhlaRXMNbUaZtxaBfOOrpSefXWl+By0 L+QjpqX0wwMQIECAAAECBAgQIECAAAECBAhfQFAQTlBA0BBOUEAgH6GEoCOcoICQuIKvCCcoIJCP IB9R6A5d8fuU5e/WFr9nXf7OffnnF4o/xaHgWZbyT/SUf66p/NNdCp5xK/+kH/mIlnyEK+QjbNH6 /RELIYgqfH9EE7zho9PzEUshiL4+E5oh3/dHLIYg+qZvRJXt+yMWH//PRJjJRyyGINYIa3Xsz0cc aYWT8xFLIYhQn3THjN8fsRCCkPrc2JD1+yOWQhCuvjA0eQbfHzHwkI8gH+HagHwE+QjyEeQjyEeQ jzheIECAAAECBAgQIECAAAECBAgQIGgIJyggaAgnKCCQj1BC0BFOUEBIXMFXhBMUEE4+TJnLyiLh /ntRuUGAAAECBAgQIECAkIdw60545fXgN4zp3sgS434xvugY4T7/2jjePTjDRzOL7oNFpxNMWLV5 I7wW9W9TCebmmrN7LQrjFoW3U4Is6l8Yuw5Z//6+cP819+7/d3/P/dfM1bOJcHu1xKFW8H9ESiuM unUSQUq5VhgSXn3ujTDTHRP6QiD4vjDcEH6HM9Lj33ZKY87ZKe02NH5r3obdMYw/vi4zNzSF2hOH prlGWf1gw6LPO0ZAgAABAgQIEPqi4H5EkQIBAgQIECBAgAABAoRPI/wHez7KCkpmYhQAAAAASUVO RK5CYII= --Boundary-00=_ALtJGEH0xbm6z8m-- --Boundary-00=_ALtJGEH0xbm6z8m--