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