From: "Eric I." Date: 2007-04-15T23:00:06+09:00 Subject: Re: Magic Fingers (#120) [solution] 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 <