class Mastermind::Knuth

Attributes

game[R]

Public Class Methods

new(game) click to toggle source
# File lib/mastermind/knuth.rb, line 5
def initialize(game)
  @game = game
  # 1. Create the set S of 1296 possible codes
  @possible_guesses = Game::Piece::COLORS.repeated_permutation(game.secret_length).to_a.map do |permutation|
    Game::Code.from(permutation)
  end
  @set = @possible_guesses.dup
  @game.turns.each { |turn| prune(turn) }
end

Public Instance Methods

exploratory_guess() click to toggle source
  1. Choose from the set of guesses with the maximum score, preferring members of S

# File lib/mastermind/knuth.rb, line 33
def exploratory_guess
  max_scoring = maximum_scoring_guesses
  (max_scoring & @set).sample || max_scoring.sample
end
first_guess() click to toggle source
  1. Make initial guess of 1122

# File lib/mastermind/knuth.rb, line 23
def first_guess
  first_color = Game::Piece::COLORS.sample
  second_color = Game::Piece::COLORS.reject { |color| color == first_color }.sample
  sequence = Array.new(@game.secret_length) do |position|
    position < @game.secret_length / 2 ? first_color : second_color
  end
  Game::Code.from(sequence)
end
prepare_guess() click to toggle source
# File lib/mastermind/knuth.rb, line 15
def prepare_guess
  return first_guess if @game.attempts == 0
  prune(@game.turns.last)
  return @set.first if @set.length == 1
  exploratory_guess
end

Private Instance Methods

highest_match_count(guess) click to toggle source
# File lib/mastermind/knuth.rb, line 61
def highest_match_count(guess)
  highest = 0
  # for a given number of matches
  (0..@game.secret_length).each do |matches|
    # count how many possibilities in S would be retained
    count = @set.count do |combination|
      combination.color_matches_with(guess) == matches
    end
    # track the highest of these
    highest = count if count > highest
  end
  highest
end
maximum_scoring_guesses() click to toggle source

Find the possible guesses for which the highest match count is the minimum match count.

# File lib/mastermind/knuth.rb, line 76
def maximum_scoring_guesses
  min_matches = minimum_match_count
  @possible_guesses.select do |possible|
    highest_match_count(possible) == min_matches
  end
end
minimum_match_count() click to toggle source
  1. For each possible guess, find the minimum highest match count

# File lib/mastermind/knuth.rb, line 52
def minimum_match_count
  lowest = @set.length
  @possible_guesses.each do |possible|
    count = highest_match_count(possible)
    lowest = count if count < lowest
  end
  lowest
end
prune(turn) click to toggle source
  1. Remove from S any code that would not give the same response if the guess were the code.

# File lib/mastermind/knuth.rb, line 41
def prune(turn)
  @set.select! do |code|
    !(turn.guess == code) &&
    turn.exact   == code.exact_matches_with(turn.guess) &&
    turn.partial == code.partial_matches_with(turn.guess)
  end

  @possible_guesses.reject! { |guess| turn.guess == guess }
end