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 Q. 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 Q. 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 Q. 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 Q. 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 Q. 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 Q. 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 Q. 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
-------------------------------------------------------------------