+ # This pairing algorithm aims to minimize the total differences of
+ # matching players' rates. It also includes penalyties when a match is
+ # same as the previous one or a match is between human players.
+ # It is based on a discussion with Yamashita-san on
+ # http://www.sgtpepper.net/kaneko/diary/20120511.html.
+ #
+ class LeastDiff < Pairing
+ def random_match(players)
+ players.shuffle
+ end
+
+ # Update estimated rate of a player.
+ # 1. If it has a valid rate, return the rate.
+ # 2. If it has no valid rate, return:
+ # a. If it won the last game, the opponent's rate + 200
+ # b. If it lost the last game, the opponent's rate - 200
+ # c. otherwise, return 2150 (default value)
+ #
+ def estimate_rate(player, history)
+ player.estimated_rate = 2150 # default value
+
+ unless history
+ log_message("Floodgate: Without game history, estimated %s's rate: %d" % [player.name, player.estimated_rate])
+ return
+ end
+
+ g = history.last_valid_game(player.player_id)
+ unless g
+ log_message("Floodgate: Without any valid games in history, estimated %s's rate: %d" % [player.name, player.estimated_rate])
+ return
+ end
+
+ opponent_id = nil
+ win = true
+ case player.player_id
+ when g[:winner]
+ opponent_id = g[:loser]
+ win = true
+ when g[:loser]
+ opponent_id = g[:winner]
+ win = false
+ else
+ log_warning("Floodgate: The last valid game is invalid for %s!" % [player.name])
+ log_message("Floodgate: Estimated %s's rate: %d" % [player.name, player.estimated_rate])
+ return
+ end
+
+ opponent_name = opponent_id.split("+")[0]
+ p = $league.find(opponent_name)
+ unless p
+ log_message("Floodgate: No active opponent found. Estimated %s's rate: %d" % [player.name, player.estimated_rate])
+ return
+ end
+
+ opponent_rate = 0
+ if p.rate != 0
+ opponent_rate = p.rate
+ elsif p.estimated_rate != 0
+ opponent_rate = p.estimated_rate
+ end
+
+ if opponent_rate != 0
+ player.estimated_rate = opponent_rate + (win ? 200 : -200)
+ end
+
+ log_message("Floodgate: Estimated %s's rate: %d" % [player.name, player.estimated_rate])
+ end
+
+ # Return a player's rate based on its actual rate or estimated rate.
+ #
+ def get_player_rate(player, history)
+ if player.rate != 0
+ return player.rate
+ elsif player.estimated_rate != 0
+ return player.estimated_rate
+ else
+ estimate_rate(player, history)
+ return player.estimated_rate
+ end
+ end
+
+ def calculate_diff_with_penalty(players, history)
+ pairs = []
+ players.each_slice(2) do |pair|
+ if pair.size == 2
+ pairs << pair
+ end
+ end
+
+ ret = 0
+
+ # 1. Diff of players rate
+ pairs.each do |p1,p2|
+ ret += (get_player_rate(p1,history) - get_player_rate(p2,history)).abs
+ end
+
+ # 2. Penalties
+ pairs.each do |p1,p2|
+ # 2.1. same match
+ if (history &&
+ (history.last_opponent(p1.player_id) == p2.player_id ||
+ history.last_opponent(p2.player_id) == p1.player_id))
+ ret += 400
+ end
+
+ # 2.2 Human vs Human
+ if p1.is_human? && p2.is_human?
+ ret += 800
+ end
+ end
+
+ ret
+ end
+
+ def match(players)
+ super
+ if players.size < 3
+ log_message("Floodgate: players are small enough to skip LeastDiff pairing: %d" % [players.size])
+ return players
+ end
+
+ # Reset estimated rate
+ players.each {|p| p.estimated_rate = 0}
+
+ # 10 trials
+ matches = []
+ scores = []
+ path = ShogiServer::League::Floodgate.history_file_path(players.first.game_name)
+ history = ShogiServer::League::Floodgate::History.factory(path)
+ 10.times do
+ m = random_match(players)
+ matches << m
+ scores << calculate_diff_with_penalty(m, history)
+ end
+
+ # Debug
+ #scores.each_with_index do |s,i|
+ # puts
+ # print s, ": ", matches[i].map{|p| p.name}.join(", "), "\n"
+ #end
+
+ # Select a match of the least score
+ min_index = 0
+ min_score = scores.first
+ scores.each_with_index do |s,i|
+ if s < min_score
+ min_index = i
+ min_score = s
+ end
+ end
+ log_message("Floodgate: the least score %d (%d per player) [%s]" % [min_score, min_score/players.size, scores.join(" ")])
+
+ players.replace(matches[min_index])
+ end
+ end
+
+ # This pairing method excludes unrated players
+ #
+ class ExcludeUnratedPlayers < Pairing
+
+ def match(players)
+ super
+
+ log_message("Floodgate: Deleting unrated players...")
+ players.delete_if{|a| a.rate == 0}
+ log_players(players)
+ end
+ end # class ExcludeUnratedPlayers
+