Magic Fingers (#120)

The three rules of Ruby Q.:

  1. Please do not post any solutions or spoiler discussion for this quiz
    until
    48 hours have passed from the time on this message.

  2. Support Ruby Q. by submitting ideas as often as you can:

http://www.rubyquiz.com/

  1. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps
everyone
on Ruby T. follow the discussion. Please reply to the original quiz
message,
if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

We have a foreign exchange student from Korea staying with us. The best
part of
that is the intended exchange of cultures. For example, to kill time on
a
recent plane trip, the student taught us a common finger game children
play in
Korea.

The rules are very easy:

  1. Both players start by holding up one finger on each hand.
  2. On each turn a player must do one of the following:
    a. Touch one of their hands to an opponent’s hand, adding the
    finger
    count on their hand to the touched hand. The player keeps the
    same
    number of fingers, but the opponent must add the player’s finger
    count in addition to the fingers already on that hand.
    b. Clap their hands together to “transfer” one or more fingers from
    one hand to the other. You cannot transfer all the fingers off
    of
    a hand.
  3. A hand with five or more fingers is eliminated, which is shown by
    making a fist. An opponent can not add fingers to an eliminated
    hand and an it cannot be used in touches, but players may transfer
    fingers to it, “reviving” it. The first player with two
    eliminated
    hands loses the game.

For example, here is how a quick game might play out:

1: ----| |---- Starting fingers.
2: ----| |----

1: ----| |---- Player 1’s left hand touches player 2’s right hand.
2: ----| ||—

1: ----| |||-- 2’s right touches 1’s right hand.
2: ----| ||—

1: ----| |||-- 1’s right touches 2’s right hand.
2: ----| -----

1: ----| ||||- 2’s left touches 1’s right hand.
2: ----| -----

1: ----| |||-- 1’s right touches 2’s left hand.
2: ----- -----

Of course, as a programmer, I immediately tried to solve this game. I
suck the
fun right out of everything, but at least it gave us another quiz topic.

This week’s Ruby Q. is to programmatically solve Magic Fingers. Is it
a win
for the first or second player with perfect play, or can you always
force a draw
with repeating counts? Have your program print some output that would
convince
anyone beyond the shadow of a doubt what the game’s outcome will be.

On Apr 13, 7:48 am, Ruby Q. [email protected] wrote:

      b.  Clap their hands together to "transfer" one or more fingers from
          one hand to the other.  You cannot transfer all the fingers off of
          a hand.

Can one clap to transfer fingers from one hand to another such that
the receiving hand would get five or more fingers and therefore be
reduced to zero fingers?

Thanks,

Eric


Interested in hands-on, on-site Ruby training? See http://LearnRuby.com
for information about a well-reviewed class.

On Apr 14, 2007, at 12:50 PM, Eric I. wrote:

On Apr 13, 7:48 am, Ruby Q. [email protected] wrote:

      b.  Clap their hands together to "transfer" one or more  

fingers from
one hand to the other. You cannot transfer all the
fingers off of
a hand.

Can one clap to transfer fingers from one hand to another such that
the receiving hand would get five or more fingers and therefore be
reduced to zero fingers?

I don’t think so. Let’s say no.

James Edward G. II

On Apr 15, 2007, at 9:00 AM, Eric I. wrote:

Note that the initial state, where all hands have one finger, does not
have a guaranteed win by either player. So if both players play
perfectly, the game will never end.

Wikipedia disagrees with this, which likely just means that I botched
my explanation of the rules somehow. I’m see if I can figure out
what I changed…

James Edward G. II

Part of the problem is to generate output that prints “some output
that would convince anyone beyond the shadow of a doubt what the
game’s outcome will be.” Even though I’ve convinced myself, I’m not
sure I’ve generated output that satisfies that requirement. My
program displays a table telling a player how to move given any state
of the hands. If there’s a way to guarantee a win no matter what else
the opponent does, it tells them how to get there. If the opponent
has a guaranteed win if s/he plays perfectly, it makes a choice that
will delay the win as long as possible to hopefully allow the opponent
to make a mistake. Otherwise, it chooses a move that maintains the
draw.

Here’s the generated output:

========

INSTRUCTIONS

If it’s your turn, select the row that describes your two hands. Then
select the column that describes your opponent’s two hands. The cell
at the intersection will tell you how to move and what to expect.

A leading “+” indicates there is a guaranteed way to win. A leading
“-” tells you that if the opponent plays perfectly, you will lose. If
neither of those symbols is present, then if you and your opponent
play well, neither of you will ever win.

The rest of the cell tells you what type of move to make. A “T”
represents a touching move, telling you which finger of yours first to
user first, and which finger of the opponent to touch. A “C”
represents a clapping move, and it tells you the finger counts should
end up with after the clap.

   01   02   03   04   11   12   13   14   22   23   24   33

34 44
---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----

01: 1T1 1T2 -1T3 +1T4 1T1 1T1 1T1 1T4 1T2 1T2 1T4 -1T3 1T4
-1T4
02: C11 C11 +2T3 +2T4 C11 C11 C11 C11 C11 C11 C11 C11 C11 -
C11
03: C21 +3T2 +3T3 +3T4 C21 +3T2 +3T3 +3T4 C21 C21 C21 -C21 C21 -
C21
04: +4T1 +4T2 +4T3 +4T4 C31 C31 C31 C31 C31 C31 C31 C22 C31 -
C22
11: 1T1 1T2 1T3 +1T4 1T1 1T1 1T1 1T1 1T2 1T2 1T2 1T3 1T4
1T4
12: 1T1 C12 +2T3 +2T4 1T1 1T1 1T1 1T1 1T2 C12 1T2 1T3 C12
1T4
13: 1T1 +3T2 +3T3 +3T4 1T1 1T1 1T1 1T1 1T2 C22 1T2 1T3 C22
1T4
14: +4T1 +4T2 +4T3 +4T4 1T1 1T1 1T1 1T1 1T2 C32 1T2 1T3 C32
1T4
22: 2T1 2T2 +2T3 +2T4 2T1 2T1 2T1 2T1 2T2 2T2 C13 2T3 2T3
2T4
23: 2T1 +3T2 +3T3 +3T4 2T1 2T1 C23 2T1 2T2 2T2 C23 2T3 2T3
2T4
24: +4T1 +4T2 +2T3 +4T4 2T1 2T1 2T1 2T1 2T2 2T2 C33 2T3 2T3
2T4
33: 3T1 +3T2 +3T3 +3T4 3T1 +3T2 +3T3 +3T4 3T2 +3T2 3T2 +3T3 +3T4
3T4
34: +4T1 +4T2 +4T3 +4T4 3T1 3T1 3T1 C34 3T2 3T2 3T2 3T3 3T3
3T4
44: +4T1 +4T2 +4T3 +4T4 +4T1 +4T2 +4T3 +4T4 +4T2 +4T3 +4T4 +4T3 +4T4
+4T4

========

Note that the initial state, where all hands have one finger, does not
have a guaranteed win by either player. So if both players play
perfectly, the game will never end.

Eric

Are you interested in on-site Ruby training that uses well-designed,
real-world, hands-on exercises? http://LearnRuby.com

====

HandNames = [“left hand”, “right hand”]

AllowClapsToZero = false

Levels = 25

Memo is used to store best moves for a given state to avoid

re-calculation. The key is a GameState, and the value is an array

containing the number of levels used to calculate the best move, the

best move, and the score of the best move.

Memo = Hash.new

Instances of this class represent the game state.

class GameState
attr_reader :hands

def initialize(hands = [[1, 1], [1, 1]])
@hands = hands
end

def do_turn(move)
new_hands, description1, description2 =
*move.call(@hands[0].dup, @hands[1].dup)
[GameState.new([new_hands[1], new_hands[0]]),
description1,
description2]
end

def to_s
result = “”
@hands.each_index do |i|
result << "#{i+1}: "
result << ‘-’ * (5 - @hands[i][0])
result << ‘|’ * @hands[i][0]
result << ’ ’
result << ‘|’ * @hands[i][1]
result << ‘-’ * (5 - @hands[i][1])
result << “\n”
end
result
end

def game_over?
@hands[0][0] == 0 && @hands[0][1] == 0 ||
@hands[1][0] == 0 && @hands[1][1] == 0
end

def score
if @hands[0][0] == 0 && @hands[0][1] == 0 : -1
elsif @hands[1][0] == 0 && @hands[1][1] == 0 : 1
else 0
end
end

def eql?(other)
@hands == other.hands
end

def hash
@hands[0][0] + 5 * @hands[0][1] + 25 * @hands[1][0] +
125 * @hands[1][1]
end
end

Generates an array of Procs, each able to perform a touching move.

Each Proc, when passed in the arrays representing the mover’s hands

and the opponent’s hands returns an array containing the new states

of the hands, a long description of the move, and an abbreviated

description of the move. If the move cannot legally be applied to

the hands, an exception is raised.

def generate_touches
result = []
(0…1).each do |from_hand|
(0…1).each do |to_hand|
result << Proc.new do |player_hands, opponent_hands|
raise “cannot touch from empty hand” if
player_hands[from_hand] == 0
raise “cannot touch to empty hand” if opponent_hands[to_hand]
== 0
description1 =
“touches #{HandNames[from_hand]} to opponent’s
#{HandNames[to_hand]}”
description2 =
“#{player_hands[from_hand]}T#{opponent_hands[to_hand]}”
opponent_hands[to_hand] += player_hands[from_hand]
opponent_hands[to_hand] = 0 if opponent_hands[to_hand] >= 5
[[player_hands, opponent_hands], description1, description2]
end
end
end
result
end

Generates an array of Procs, each able to perform a clapping move.

See the comment for generate_touches for the remaining details since

this method works analogously.

def generate_claps
result = []
(0…1).each do |from_hand|
to_hand = 1 - from_hand
(1…4).each do |fingers|
result << Proc.new do |player_hands, opponent_hands|
raise “do not have enough fingers on #{HandNames[from_hand]}”
unless
player_hands[from_hand] > fingers
raise “#{HandNames[to_hand]} would end up with five or more
fingers” if
!AllowClapsToZero && player_hands[to_hand] + fingers >= 5
description1 = "claps to transfer #{fingers} fingers from " +
“#{HandNames[from_hand]} to #{HandNames[to_hand]}”
player_hands[from_hand] -= fingers
player_hands[to_hand] += fingers
player_hands[to_hand] = 0 if player_hands[to_hand] >= 5
description2 =
“C#{player_hands[from_hand]}#{player_hands[to_hand]}”
[[player_hands, opponent_hands], description1, description2]
end
end
end
result
end

All possible moves for any turn, some of which might not be legal

given the state of the hands.

Moves = generate_claps + generate_touches

Picks the best possible move that can be determined using no more

than levels levels of recursion. To speed this up, if the current

state is stored in the Memo with the same or fewer levels, then

that’s used rather than recalculation. This returns an array

containing the score of the best move, the move, a long description

of the move, and an abbreviated description of the move. If a move

guaranteeing a win can be done, then that will be chosen. If there

are multiple such moves, then the one that leads to a win most

quickly is chosen. If a win can’t be chosen but a draw can be, then

it is. If a guaranteed lost must be chosen (assuming the opponent

plays a perfect game), then the lose taking the most moves is chosen

to increase the opportunities the opponent will make a mistake, and

either a draw or win can be achieved.

def pick_move(state, levels = Levels)
return [state.score, nil, nil, nil] if levels <= 0 ||
state.game_over?

memoed_move = Memo[state]
if memoed_move && memoed_move[0] >= levels
# use memoed values if levels used meets or exceeds my levels
best_move = memoed_move[1]
best_score = memoed_move[2]
else
# otherwise, calculate values recursively
best_score = nil
best_move = nil

# try each of the possible moves on this state and generate an
# array of the results of those choices
move_choices = Moves.map do |move|
  begin
    # determine the new state if the chosen move is applied
    new_state, description1, description2 = *state.do_turn(move)

    # recursively determine the score for this move (i.e., this
    # state); negate the score returned since it's in terms of
    # opponent (i.e., a win for them is a loss for us)
    score = -pick_move(new_state, levels - 1)[0]

    # increment score (by shifting away from zero) in order to be
    # able to treat is as a count of the number of moves to a win
    # or a loss
    score += score / score.abs unless score.zero?

    [score, move, description1, description2]
  rescue Exception => e
    nil  # the move was ilegal
  end
end

# remove nils that were generated by illegal moves
move_choices = move_choices.select { |option| option }

# select and sort only those with positive (i.e., winning scores)
winning_choices = move_choices.
  select { |option| option[0] > 0 }.
  sort_by { |option| option[0] }

unless winning_choices.empty?
  # if there's a winning option, choose the one that leads to a
  # with the least number of moves
  selected = winning_choices.first
else
  # otherwise, choose a move that leads to a tie (preferable) or a
  # loss but in the greatest number of moves (to increase
  # opponent's opportunities to make a mistake)
  move_choices = move_choices.sort_by { |option| option[0] }
  if move_choices.last[0] == 0
    selected = move_choices.last
  else
    selected = move_choices.first
  end
end

best_score = selected[0]
best_move = selected[1..3]

# store the best move determined for future use
Memo[state] = [levels, best_move, best_score]

end

[best_score] + best_move
end

Returns a string indicating win or loss depending on score.

def score_symbol(score)
if score > 0 : ‘+’
elsif score < 0 : ‘-’
else ’ ’
end
end

Calculate the best move given every finger combination, and store in

the results hash.

results = Hash.new
1.upto(4) do |left1|
0.upto(left1) do |right1|
key1 = “#{right1}#{left1}”
results[key1] = Hash.new
1.upto(4) do |left2|
0.upto(left2) do |right2|
state = GameState.new([[left1, right1], [left2, right2]])
score, move, description1, description2 = *pick_move(state,
40)
key2 = “#{right2}#{left2}”
results[key1][key2] = score_symbol(score) + description2
end
end
end
end

display instructions

puts <<EOS
INSTRUCTIONS

If it’s your turn, select the row that describes your two hands. Then
select the column that describes your opponent’s two hands. The cell
at the intersection will tell you how to move and what to expect.

A leading “+” indicates there is a guaranteed way to win. A leading
“-” tells you that if the opponent plays perfectly, you will lose. If
neither of those symbols is present, then if you and your opponent
play well, neither of you will ever win.

The rest of the cell tells you what type of move to make. A “T”
represents a touching move, telling you which finger of yours first to
user first, and which finger of the opponent to touch. A “C”
represents a clapping move, and it tells you the finger counts should
end up with after the clap.

EOS

display move strategy table

line1 = " " + results.keys.sort.map { |key1| " #{key1}" }.join
puts line1
puts line1.gsub(/\ \ \d\d/, ‘----’)
results.keys.sort.each do |key1|
print "#{key1}: “,
results[key1].keys.sort.map { |key2| " #{results[key1]
[key2]}” }.join,
“\n”
end

On Apr 15, 3:49 pm, James Edward G. II [email protected]
wrote:

James Edward G. II
I just read the Wikipedia description as a result of reading your
comment. And as I read through the rules there, one difference did
jump out at me. The rules disallow a clap where you start out with 3
on left and 1 on right and end up with 1 on left and three on right.
My code does not disallow that.

So that’s one possibility. The other is that I made some other
mistake (which shouldn’t be rules out!). But I’ll try adding that
aspect to the rules and re-run.

Eric

Note:
This didn’t seem to get through the first time I sent it. And now that I
look
at the online archives, I see my solution to last weeks isn’t there
either.
Perhaps the list didn’t like the fact that I attached zip files, which I
did
merely for the convenience of the person that puts the solutions on
rubyquiz.com so they won’t have to copy-paste. I’ll resend my 119
solution
in a bit, which was long and ugly, but did handle things like
parentheses.


Here’s another long-winded solution from me. I’m not sure its correct,
but for
a few small examples (2 & 3 fingers per hand), it seems to know when a
win is
unavoidable given perfect play. There are 2 main classes that do the
important
work:

State: This holds two Arrays, one for each player (@players). Each of
those hold
two numbers - how many fingers are on each hand. These are kept
sorted,
because it doesn’t matter if you have 3-left and 2-right or
2-right and
3-left. State also has a @turn, which designates who moves next,
a
@parent, for back-tracing through a state tree, and a
@best_outcome,
which holds a value assigned by StateTree. Only @players and
@turn are
taken into account by ==, eql?, and hash. State’s
each_reachable_state
method yields for each state reachable from itself, using the
touch and
clap rules.

StateTree: This class holds a @root State, and a recursive best_outcome
method.
This method will be called for each reachable state from its
argument. Whichever leads to the best outcome for that
State’s
player (@turn) is returned.

Then there’s a few other classes and modules, like Outcome, which holds
constants P1Win, P2Win, and Loop; and Game, which creates a StateTree,
runs
best_outcome, and prints the results. The number of fingers per hand can
be
changed from 5 in constants.rb.

There are some commented-out simple examples in magic_fingers.rb, which
seem
to work:

Game.new([1,1], [0,4]).analyze
Player 1, with perfect play, can win:
1: ----| |---- *
2: ----- ||||-

1: ----| |----
2: ----- ----- *

Game.new([4,4], [1,1]).analyze
Player 1, with perfect play, can win:
1: -|||| ||||- *
2: ----| |----

1: -|||| ||||-
2: ----- |---- *

1: ----- ||||- *
2: ----- |----

1: ----- ||||-
2: ----- ----- *

Game.new([0,1], [3,3]).analyze
No matter how well Player 1 plays, Player 2 can win. For example:
1: ----- |---- *
2: --||| |||–

1: ----- |----
2: --||| ||||- *

1: ----- ----- *
2: --||| ||||-

However, for the regular game:

Game.new.analyze
Player 1 can stay in a loop.

So my program thinks player 1 can forever repeat a loop of game states,
but can’t force a win. This contradicts my initial guess, but I don’t
know if its correct, so I think I have a bug.

Here’s the code:

#!/usr/bin/env ruby

constants.rb

Left, Right = 0, 1 # hand array indices
Player1, Player2 = 0, 1 # player array indices
FingersPerHand = 5

#!/usr/bin/env ruby

outcome.rb

require ‘constants’

module Outcome

Order important: from best-for-player-1 to best-for-player-2

Outcome::P1Win = 0
Outcome::Loop = 1
Outcome::P2Win = 2

Given an array of outcomes, return the one that is best for the

given

player.

def Outcome.best(player, outcomes)
(player == Player1) ? outcomes.min : outcomes.max
end
end

#!/usr/bin/env ruby

state.rb

require ‘constants’
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
@best_outcome = nil

for player in @players do
  State.normalize(player)
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

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

Also, the touchee is then normalized.

def State.touch(toucher, toucher_hand, touchee, touchee_hand)
touchee[touchee_hand] += toucher[toucher_hand]
State.normalize(touchee)
end

Yield each state reachable from self.

def each_reachable_state
reachable = Set[] # use a Set instead of yielding as we find them to
remove
# yielding duplicates.
player = @players[@turn]
opponent_num = (@turn + 1) % 2
opponent = @players[opponent_num]

# Touch rules.
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
        reachable << State.new(player, op, opponent_num, self)
      else
        reachable << State.new(op, player, opponent_num, self)
      end
    end
  end
end

# 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] - 1,
(FingersPerHand - player[target_hand] - 1)].min
(1…max_transfer).each do |i|
p = player.clone
p[source_hand] -= i
p[target_hand] += i
State.normalize(p)
if @turn == Player1
reachable << State.new(p, opponent.clone, opponent_num, self)
else
reachable << State.new(opponent.clone, p, opponent_num, self)
end
end
end

reachable.each { |r| yield r }

end
end

#!/usr/bin/env ruby

state_tree.rb

require ‘constants’
require ‘state’
require ‘outcome’

Represents a tree of States in parent-child relationships.

class StateTree
attr_reader :root, :p1_win_node, :p2_win_node, :loop_node

def initialize(root = State.new([1,1], [1,1], Player1))
@root = root
@old_nodes = Set[@root]
@p1_win_node = @p2_win_node = nil
self
end

Determine the best outcome at the given node, for that node’s

player.

If Outcome::P1Win is returned, @p1_win_node will hold one way for

player 1

to win. Likewise for Outcome::P2Win.

Because @old_nodes is filled up as it runs, it can only be called

once.

Can’t clear out @old_nodes at the end of the method, since its

recursive,

and the next level up depends on it. Could just create a wrapper

method

to do that, though.

def best_outcome(node = @root)
reachable_outcomes = []

node.each_reachable_state do |reached|
  if @old_nodes.include?(reached)
    if reached.best_outcome.nil?
      reachable_outcomes << Outcome::Loop
    else
      reachable_outcomes << reached.best_outcome
    end
  elsif reached.end_state?
    # Note that end states are never added to @old_nodes, because 

@old_nodes
# is only used for loop-checking, and loops shouldn’t include
end
# states.
if reached.winner == Player1
@p1_win_node = reached
reachable_outcomes << Outcome::P1Win
else
@p2_win_node = reached
reachable_outcomes << Outcome::P2Win
end
else
@old_nodes << node
reachable_outcomes << best_outcome(reached)
end
end

node.best_outcome = Outcome.best(node.turn, reachable_outcomes)

end
end

#!/usr/bin/env ruby

game.rb

require ‘constants’
require ‘outcome’
require ‘state’
require ‘state_tree’

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])
@state_tree = StateTree.new(State.new(p1_start, p2_start, Player1))
self
end

Print out an analysis of the game.

def analyze
outcome = @state_tree.best_outcome

if outcome == Outcome::P1Win
  puts 'Player 1, with perfect play, can win:'
  @state_tree.p1_win_node.each_ancestor do |state|
    puts "#{state}\n\n"
  end
elsif outcome == Outcome::P2Win
  puts 'No matter how well Player 1 plays, Player 2 can win. For 

example:’
@state_tree.p2_win_node.each_ancestor do |state|
puts “#{state}\n\n”
end
elsif outcome == Outcome::Loop
puts ‘Player 1 can stay in a loop.’
else
puts ‘I am broken.’
end
end
end

#!/usr/bin/env ruby

magic_fingers.rb

Ruby Q. 120: Magic Fingers

require ‘game’

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.

OK, I made two changes to my code. First, I don’t allow a clap that
ends up with the same finger counts. Second, I made it possible to
clap all the fingers off of one hand to the other, leaving one hand
with zero. And now it is the case where the first player is
guaranteed a loss.

Here’s my new move table:

   01   02   03   04   11   12   13   14   22   23   24   33

34 44
---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ----

01: -1T1 -1T2 -1T3 +1T4 -1T1 -1T2 -1T1 +1T4 -1T2 -1T2 -1T4 -1T3 -1T4
-1T4
02: +C11 -C11 +2T3 +2T4 +C11 -C11 +2T3 +2T4 -C11 +2T3 +2T4 -C11 -C11 -
C11
03: +C21 +3T2 +3T3 +3T4 -C21 +3T2 +3T3 +3T4 -C21 -C21 -C21 -C21 -C21 -
C21
04: +4T1 +4T2 +4T3 +4T4 +C31 +C22 C22 +C22 C22 +C22 C22 -C22 -C22 -
C22
11: +C02 +1T2 -1T3 +1T4 -1T1 +C02 -1T3 +1T4 C02 -1T2 -1T4 -1T3 +1T4
-1T4
12: +C03 -2T2 +2T3 +2T4 +C03 +2T2 +2T3 +2T4 -1T2 +2T3 +2T4 -1T3 -2T3
-1T4
13: +C22 +3T2 +3T3 +3T4 +3T1 +C22 +3T3 +1T4 C22 +C22 C22 -C22 3T3
1T4
14: +4T1 +4T2 +4T3 +4T4 +C32 -C32 -C32 +C32 -C32 -4T3 -4T2 -1T3 -4T3
-1T4
22: +C13 2T2 +2T3 +2T4 +C13 +2T2 +2T3 +2T4 2T2 +2T3 +2T4 +2T3 +2T4
2T4
23: +2T1 +3T2 +3T3 +3T4 +3T1 +3T2 +3T3 +3T4 -3T2 +3T2 -3T2 +3T3 +3T4
-2T4
24: +4T1 +4T2 +2T3 +2T4 +4T1 +4T2 +2T3 +2T4 2T2 +4T2 4T2 +4T3 +4T4
2T4
33: +C24 +3T2 +3T3 +3T4 +3T1 +3T2 +3T3 +3T4 +3T2 +3T2 +3T4 +3T3 +3T4
+3T4
34: +4T1 +4T2 +4T3 +4T4 +4T1 +4T2 +4T3 +4T4 +4T2 +4T3 +4T4 +4T3 +4T4
+4T4
44: +4T1 +4T2 +4T3 +4T4 +4T1 +4T2 +4T3 +4T4 +4T2 +4T3 +4T4 +4T3 +4T4
+4T4

Interestingly if you follow through starting at 11/11, then the first
player can apparently hold off on losing for 26 turns, 13 by each
player.

And my replacement generate_claps method is appended below.

Eric

Are you interested in on-site Ruby training that’s been highly
reviewed by former students? http://LearnRuby.com

====

Generates an array of Procs, each able to perform a clapping

move.

See the comment for generate_touches for the remaining details

since

this method works

analogously.
def generate_claps
result = []
(0…1).each do |from_hand|
to_hand = 1 - from_hand
(1…4).each do |fingers|
result << Proc.new do |player_hands, opponent_hands|
raise “do not have enough fingers on #{HandNames[from_hand]}”
unless
player_hands[from_hand] >= fingers
raise “#{HandNames[to_hand]} would end up with five or more
fingers” if
!AllowClapsToZero && player_hands[to_hand] + fingers >= 5
raise “cannot end up with same number combination after clap”
if
player_hands[from_hand] - fingers == player_hands[to_hand]
description1 = "claps to transfer #{fingers} fingers from " +
“#{HandNames[from_hand]} to #{HandNames[to_hand]}”
player_hands[from_hand] -= fingers
player_hands[to_hand] += fingers
player_hands[to_hand] = 0 if player_hands[to_hand] >= 5
description2 =
“C#{player_hands[from_hand]}#{player_hands[to_hand]}”
[[player_hands, opponent_hands], description1, description2]
end
end
end
result
end

On Apr 15, 2007, at 3:40 PM, Eric I. wrote:

my explanation of the rules somehow. I’m see if I can figure out
what I changed…

James Edward G. II

I just read the Wikipedia description as a result of reading your
comment. And as I read through the rules there, one difference did
jump out at me. The rules disallow a clap where you start out with 3
on left and 1 on right and end up with 1 on left and three on right.
My code does not disallow that.

Sorry, yesterday was a busy day for me and I just got around to
looking into this. Thanks for looking into this for me.

Yes, this is the rule I didn’t express in the quiz description. I
knew about it and just failed to state it correctly. For the record,
the missing rule is:

A clap must result in a change in finger counts. Just switching the
counts of the left and right hands is not allowed.

James Edward G. II

Regarding clapping, is something like 1,3 -> 0,4 allowed?

On Friday 13 April 2007 07:48, Ruby Q. wrote:

You cannot transfer all the fingers off of a hand.

Whilst Wikipedia says (under “Alternate Explanation”):

They are free to remove all fingers from a hand

Which is it? WP’s Gameplay section doesn’t say one way or the other.

On Apr 18, 2007, at 3:38 PM, Jesse M. wrote:

Regarding clapping, is something like 1,3 -> 0,4 allowed?

On Friday 13 April 2007 07:48, Ruby Q. wrote:

You cannot transfer all the fingers off of a hand.

Whilst Wikipedia says (under “Alternate Explanation”):

They are free to remove all fingers from a hand

Which is it? WP’s Gameplay section doesn’t say one way or the other.

Interesting. It seems I may have had that rule wrong. I now
understand why Eric’s code had a constant to toggle that behavior on
and off. Eric’s code still gets the right answer with it off, so I
doubt it matters.

James Edward G. II

On Apr 18, 4:45 pm, James Edward G. II [email protected]
wrote:

On Apr 18, 2007, at 3:38 PM, Jesse M. wrote:

Regarding clapping, is something like 1,3 → 0,4 allowed?

Interesting. It seems I may have had that rule wrong. I now
understand why Eric’s code had a constant to toggle that behavior on
and off. Eric’s code still gets the right answer with it off, so I
doubt it matters.

Well, there are two related issues, and my constant does not cover the
situation described.

The first issue is whether 1,3 → 0,4 is allowed. I only got the
“right answer” (i.e., second player can force a win) after I made
that legal, so it seems to be important.

The second issue is whether 3,4 → 1,0 (via 1,6) is allowed. That’s
what my constant controls (and therefore it’s somewhat misnamed). I
don’t think the Wikipedia article is clear on this issue, as it
describes it as a “transfer” of fingers. If it had used the work
“redistribution” of fingers, then I think we could say it’s clearly
disallowed. I think it makes sense to view the clap as a
redistribution, so my personal preference is to disallow it.

So that’s my $0.02, FWIW.

Eric

On-site, hands-on Ruby training is available from http://LearnRuby.com
!

I took the OO approach and implemented a strategy pattern.
To see the game play out, pass in the -v flag, and -d will show the
actual command given for each move.

The output of the test file contains a frequency distribution to show
how each matchup plays out.

Here is some sample output for the second matchup in the test over 200
games:


Game 2: Aggressive vs Random
3: ---------------------------------33
4:
--------------------------------------------------------------------68
5: -------------------------------------------43
6: ------------------------24
7: ---------------15
8: -----5
9: -------7
10: ----4
11: -1
Player 1: 166 wins
Player 2: 34 wins


In an Aggressive vs Aggressive game, the first player wins in 3 rounds
every time. Obviously there are better
strategies that I didn’t take the time to explore.

Again, I’m happy to receive any comments. I feel like my solutions
are so clunky compared to what you guys submit.
I am here to learn!

Here’s my code:

#file: game.rb
#author: Matt Hulse - www.matt-hulse.com

require ‘player’

class Game
attr_reader :p1, :p2, :winner, :rounds

def initialize(p1_strategy = “random”, p2_strategy = “random”)
@p1 = Player.new(1,p1_strategy, self)
@p2 = Player.new(2,p2_strategy, self)
@rounds = 0
end

def get_opponent(player)
return @p1 if @p2 == player
return @p2 if @p1 == player
end

def loop
#keep going until one person has no hands left
#after 100 rounds we’re calling a draw!

puts self if $VERBOSE
until(game_over) do
  @rounds += 1
  p1.move
  puts self if $VERBOSE

  unless game_over then
    p2.move
    puts self if $VERBOSE
  end
  break if @rounds >= 100
end

if(lost?(p1)) then
  @winner = p2
elsif(lost?(p2))
  @winner = p1
else
  puts "Draw"
end

end

def game_over
lost?(p1) || lost?(p2)
end

def lost?(player)
player.left.finger_count <= 0 and player.right.finger_count <= 0
end

def to_s
“#{p1}\n#{p2}\n”
end
end

#file: hand.rb
#author: Matt Hulse - www.matt-hulse.com

class Hand
attr_reader :right_or_left, :finger_count

def initialize(right_or_left, count = 1)
@right_or_left = right_or_left
@finger_count = count
end

def touch(hand)
hand.add_fingers(self.finger_count)
end

def add_fingers(num)
@finger_count += num
if @finger_count >= 5 then
@finger_count = 0
end
end

def clap(hand,num)
hand.add_fingers(num) #num must be <= self.finger_count
@finger_count -= num
end

def to_s
result = “”
#print left to right
i = 0
(1…5).each{
i += 1
if(i <= @finger_count) then
result += “|”
else
result += “-”
end
}
return result if @right_or_left == :right
return result.reverse
end

end

#file: player.rb
#author: Matt Hulse - www.matt-hulse.com

require ‘hand’

class Player
attr_reader :player_num, :right, :left, :strategy, :game
def initialize(player_num, strategy, game)
@player_num = player_num
@strategy = strategy
@game = game
@right = Hand.new(:right,1)
@left = Hand.new(:left,1)
end

def move
begin
eval(@strategy)
rescue NameError => e
random #default to random
end
end

def get_opponent
@game.get_opponent(self)
end

def get_larger_hand
return @right if @right.finger_count > @left.finger_count
return @left
end

def min(a,b)
return a if a <= b
return b
end

def random
#all possible moves, choose randomly among them
opponent = get_opponent

valid_moves = Array.new

opp_rt_count = opponent.right.finger_count
opp_lt_count = opponent.left.finger_count

if(@right.finger_count > 0) then
  valid_moves << "@right.touch(opponent.right)" if opp_rt_count >

0
valid_moves << “@right.touch(opponent.left)” if opp_lt_count > 0
#total on hand transferred to cannot be more than 5
#random number is between 1 and the minimum of what left can
receive and right can give
rand_max = min([email protected]_count,@right.finger_count-1)
valid_moves << “@right.clap(@left, #{rand(rand_max) + 1})” if
rand_max > 0
end

if(@left.finger_count > 0) then
  valid_moves << "@left.touch(opponent.right)" if opp_rt_count > 0
  valid_moves << "@left.touch(opponent.left)" if opp_lt_count > 0
  #total on hand transferred to cannot be more than 5
  #random number is between 1 and the minimum of what right can

receive and left can give
rand_max = min([email protected]_count,@left.finger_count-1)
valid_moves << “@left.clap(@right, #{rand(rand_max) + 1})” if
rand_max > 0
end

move = valid_moves[rand(valid_moves.size)]
eval(move)
puts "Player #{player_num}: #{move}" if $DEBUG

end

def aggressive
opponent = get_opponent

#every move is to touch the opponents largest hand with the local

largest hand
move = “get_larger_hand.touch(opponent.get_larger_hand)”

eval(move)
puts "Player #{player_num}: #{move}" if $DEBUG

end

def to_s
“#{player_num}: #{@left} #{@right}”
end
end

#file: test.rb
#author: Matt Hulse - www.matt-hulse.com

require ‘game’

puts “Game 1: Random vs Random”

num_rounds = Hash.new(0)
wins = Hash.new(0)

(1…200).each{
game = Game.new(“random”,“random”)
game.loop
if(game.winner) then
puts “Player #{game.winner.player_num} won in #{game.rounds}
rounds using #{game.winner.strategy} strategy.” if $VERBOSE
num_rounds[game.rounds] += 1
wins[game.winner.player_num] +=1
end
}

num_rounds.keys.sort{|a,b| a<=>b}.each{|i|
puts “#{i}: #{‘-’*num_rounds[i]}#{num_rounds[i]}”
}

wins.each_pair{|key,value|
puts “Player #{key}: #{value} wins”
}

puts
puts “Game 2: Aggressive vs Random”

num_rounds = Hash.new(0)
wins = Hash.new(0)

(1…200).each{
game = Game.new(“aggressive”, “random”)
game.loop
if(game.winner) then
puts “Player #{game.winner.player_num} won in #{game.rounds}
rounds using #{game.winner.strategy} strategy.” if $VERBOSE
num_rounds[game.rounds] += 1
wins[game.winner.player_num] +=1
end
}

num_rounds.keys.sort{|a,b| a<=>b}.each{|i|
puts “#{i}: #{‘-’*num_rounds[i]}#{num_rounds[i]}”
}

wins.each_pair{|key,value|
puts “Player #{key}: #{value} wins”
}

puts
puts “Game 3: Aggressive vs Aggressive”

num_rounds = Hash.new(0)
wins = Hash.new(0)

(1…200).each{
game = Game.new(“aggressive”,“aggressive”)
game.loop
if(game.winner) then
puts “Player #{game.winner.player_num} won in #{game.rounds}
rounds using #{game.winner.strategy} strategy.” if $VERBOSE
num_rounds[game.rounds] += 1
wins[game.winner.player_num] +=1
end
}

num_rounds.keys.sort{|a,b| a<=>b}.each{|i|
puts “#{i}: #{‘-’*num_rounds[i]}#{num_rounds[i]}”
}

wins.each_pair{|key,value|
puts “Player #{key}: #{value} wins”
}

Thanks,


Matt Hulse
[email protected]
http://www.matt-hulse.com

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

-------------------------------------------------------------------