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 Quiz 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.
Quiz Summary
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:
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!
