Forum: Ruby Magic Fingers (#120)

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
James G. (Guest)
on 2007-04-19 16:08
(Received via mailing list)
Eric I. said it best when he said the real trick of this quiz is
figuring out a
way to convince someone of the outcome beyond the shadow of a doubt.
Eric's own
code convinced me, after we clarified my mistakes in the rules.

Eric's code outputs a table of your moves compared with the opponent's
moves.
At each step, it tells you the move to make based on the following
priorities:

  1. It suggests a forced win if it can find one
  2. It aims for draw if there is no forced win
  3. As a last resort, it will stall a loss as long as possible to
increase
     the chances of your opponent making an error

The first one is really the point of interest for this quiz.  There's
just not
that many different hand positions in this game and a sufficiently deep
search
can find the wins.  Here's the chart Eric's code shows for the game:

         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

Columns and rows are labeled in normalized hand positions, meaning that
a left
hand of one finger and a right hand of two fingers is the same as a left
of two
with a right of one.

You find the row for your hands and cross reference it with the column
of the
opponent's hands.  The cell where the two meet lists your best move, be
it a
touch or a clap.  Don't worry too much about the format of those moves,
but know
this:  a plus indicates that you have a forced win and a minus indicates
that
you face a forced loss.

Using that knowledge you can look up the starting position at row 11,
column 11.
You will find a minus there telling you that your best move still leads
to a
forced loss.  That's correct.  The second player can always win a game
of Magic
Fingers.

Now let's examine how the code reaches this conclusion.  First, let's
look at
the class used to represent the current 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

  # ...

Most of this class is very straightforward.  A GameState is created by
providing
the current values of the two hands.  You can then query the resulting
object
for a win, loss, or yet unknown score(), whether or not it is
game_over?(), or a
String representation of the hands.  The class also defines eql?() and
hash() in
terms of the hand counts so these objects can be used as keys in a Hash.

The only semi-involved method is do_turn(), which takes a Proc that will
perform
a move and uses that to create the resulting GameState object.  You will
see how
this method is used when we get a little farther.

Next we will look into generating possible moves:

  # ...

  HandNames        = ["left hand", "right hand"]
  AllowClapsToZero = false

  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

  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

  Moves = generate_claps + generate_touches

  # ...

The main work here is in the two almost identical methods.  They work by
filling
an Array with Proc objects that generate touch and clap moves when
passed a pair
of hands.  These Procs return the new hands and descriptions of the move
that
are used in the chart we saw earlier.  They also include a good deal of
error
handling to prevent illegal moves, as you can see.  Finally the Moves
constant
is populated with the results of a call to each.

This next method is the work horse of this solution.  This is a
recursive depth
first search of the available moves.  It limits the recursion, to keep
things
like draws from creating infinite loops, and memoizes GameState objects
to keep
from redoing work.  Let's take it in slices:

  # ...

  Levels = 25
  Memo   = Hash.new

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

Right off the bat, we see the code that controls when recursion stops.
As soon
as the recursion limit is reached or a game is over, the code tosses a
final
score back up the stack.

When that's not the case, the method moves into search mode.  The first
step is
to check for a memoized answer that would short circuit the need to
search at
all.  When we don't have that for the current position though, it's time
to
recurse:

      # ...

      # 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

      # ...

Here we see the Array of Proc move generators and the do_turn() method
of
GameState come together.  Each Proc is passed in one-at-a-time to
generate the
resulting GameState.  Remember that those Procs toss Exceptions whenever
an
illegal move is found and this code uses a rescue clause to skip over
such
moves.  The new state is then recursed into by pick_move() to fetch a
resulting
score.  That score will be from the opponent's point of view, so it has
to be
negated to count for our point of view.

When we have the moves, it's time to hunt for winners:

      # ...

      # 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

  # ...

The first line is just a long-hand way to write move_choices.compact!
and the
second line filters the legal moves down to winning moves.  If we have
winning
moves, the quickest kill is selected.  Otherwise, the code checks draws
and
losses as I described earlier.  At this point we finally know a best
move and
score.  Those are memoized for future calls and passed back up the stack
to the
calling code.

The next step is to put this method to work by handing it all possible
hand
combinations:

  # ...

  # 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

  # ...

This is just a brute force generation of positions, their scores, and
the best
moves to make in them.  Everything shown in Eric's output is built here
using
the tools we have been examining.

Speaking of that chart, drawing that is our last bit of code:

  # ...

  # 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

This code is just boring print calls to display the chart.  There
shouldn't be
anything surprising here.

My thanks to the few brave souls that toughed out my surprisingly
challenging
problem.  I didn't realize it would be so much work, but you guys made
it look
easy enough, as usual.

Tomorrow we have a super easy code breaking problem so I want to see all
you
beginners playing!
This topic is locked and can not be replied to.