Re: [QUIZ] Magic Fingers (#120)

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
[e-mail]
http://www.jessemerriman.com/