## $Id$
## Copyright (C) 2004 NABEYA Kenichi (aka nanami@2ch)
-## Copyright (C) 2007-2008 Daigo Moriwaki (daigo at debian dot org)
+## Copyright (C) 2007-2012 Daigo Moriwaki (daigo at debian dot org)
##
## This program is free software; you can redistribute it and/or modify
## it under the terms of the GNU General Public License as published by
class Pairing
class << self
- def default_factory
- return sort_by_rate_with_randomness
+ def default_factory(options)
+ return least_diff_pairing(options)
end
- def sort_by_rate_with_randomness
- return [ExcludeSacrificeGps500.new,
+ def sort_by_rate_with_randomness(options)
+ return [LogPlayers.new,
+ ExcludeSacrifice.new(options[:sacrifice]),
MakeEven.new,
SortByRateWithRandomness.new(1200, 2400),
- StartGame.new]
+ StartGameWithoutHumans.new]
end
- def random_pairing
- return [ExcludeSacrificeGps500.new,
+ def random_pairing(options)
+ return [LogPlayers.new,
+ ExcludeSacrifice.new(options[:sacrifice]),
MakeEven.new,
- RandomPairing.new,
- StartGame.new]
+ Randomize.new,
+ StartGameWithoutHumans.new]
end
- def match(players)
- logics = default_factory
+ def swiss_pairing(options)
+ return [LogPlayers.new,
+ ExcludeSacrifice.new(options[:sacrifice]),
+ MakeEven.new,
+ Swiss.new,
+ StartGameWithoutHumans.new]
+ end
+
+ def least_diff_pairing(options)
+ return [LogPlayers.new,
+ ExcludeSacrifice.new(options[:sacrifice]),
+ MakeEven.new,
+ LeastDiff.new,
+ StartGameWithoutHumans.new]
+ end
+
+ def floodgate_zyunisen(options)
+ return [LogPlayers.new,
+ ExcludeUnratedPlayers.new,
+ ExcludeSacrifice.new(options[:sacrifice]),
+ MakeEven.new,
+ LeastDiff.new,
+ StartGameWithoutHumans.new]
+ end
+
+ def match(players, logics, options)
logics.inject(players) do |result, item|
+ item.set_options(options)
item.match(result)
+ result
end
end
end # class << self
+ def initialize
+ @options = {}
+ end
+ def set_options(options)
+ @options.merge!(options)
+ end
+
+ # Make matches among players.
+ # @param players an array of players, which should be updated destructively
+ # to pass the new list to subsequent logics.
+ #
def match(players)
# to be implemented
+ log_message("Floodgate: %s" % [self.class.to_s])
end
def include_newbie?(players)
def less_than_one?(players)
if players.size < 1
- log_warning("Floodgate: At least one player is required")
+ log_warning("Floodgate: There should be at least one player.")
return true
else
- return true
+ return false
end
end
one.name
end
end
- log_message("Floodgate: [Players] %s" % [str_array.join(", ")])
+ if str_array.empty?
+ log_message("Floodgate: [Players] Nobody found.")
+ else
+ log_message("Floodgate: [Players] %s." % [str_array.join(", ")])
+ end
end
end # Pairing
- class StartGame < Pairing
+
+ class LogPlayers < Pairing
+ def match(players)
+ super
+ log_players(players)
+ end
+ end
+
+ class AbstractStartGame < Pairing
+ def start_game(p1, p2)
+ log_message("Floodgate: Starting a game: BLACK %s vs WHITE %s" % [p1.name, p2.name])
+ p1.sente = true
+ p2.sente = false
+ board = Board.new(@options)
+ board.initial
+ Game.new(p1.game_name, p1, p2, board)
+ end
+
+ def start_game_shuffle(pair)
+ pair.shuffle!
+ start_game(pair.first, pair.last)
+ end
+ end
+
+ class StartGame < AbstractStartGame
def match(players)
super
if players.size < 2
- log_warning("There should be more than one player: %d" % [players.size])
+ log_message("Floodgate: There are less than two players: %d" % [players.size])
return
end
if players.size.odd?
- log_warning("There are odd players: %d" % [players.size])
+ log_warning("Floodgate: There are odd players (%d). %s will not be matched." %
+ [players.size, players.last.name])
end
log_players(players)
while (players.size >= 2) do
pair = players.shift(2)
- pair.shuffle!
- start_game(pair.first, pair.last)
+ start_game_shuffle(pair)
end
end
+ end
- def start_game
- log_message("Floodgate: BLACK %s; WHITE %s" % [p1.name, p2.name])
- p1.sente = true
- p2.sente = false
- Game.new(p1.game_name, p1, p2)
+ # This tries to avoid a human-human match
+ #
+ class StartGameWithoutHumans < AbstractStartGame
+ def match(players)
+ super
+ log_players(players)
+ if players.size < 2
+ log_message("Floodgate: There are less than two players: %d" % [players.size])
+ return
+ elsif players.size == 2
+ start_game_shuffle(players)
+ return
+ end
+
+ loop do
+ humans = get_human_indexes(players)
+ log_message("Floodgate: There are (still) %d humans." % [humans.size])
+ break if humans.size < 2
+
+ pairing_possible = false
+ for i in 0..(humans.size-2) # -2
+ next if humans[i].odd?
+ if humans[i]+1 == humans[i+1]
+ pairing_possible = humans[i]
+ break
+ end
+ end
+ unless pairing_possible
+ log_message("Floodgate: No possible human-human match found")
+ break
+ end
+
+ current_index = pairing_possible
+ j = [0, current_index - 2].max
+ while j < players.size
+ break if players[j].is_computer?
+ j += 1
+ end
+
+ pairing_indexes = []
+ if j == players.size
+ # no computer player found
+ pairing_indexes << current_index << current_index+1
+ else
+ # a comupter player found
+ pairing_indexes << current_index << j
+ end
+
+ pair = []
+ pair << players.delete_at(pairing_indexes.max)
+ pair << players.delete_at(pairing_indexes.min)
+ start_game_shuffle(pair)
+ end # loop
+
+ while (players.size >= 2) do
+ pair = players.shift(2)
+ start_game_shuffle(pair)
+ end
+ end
+
+ private
+
+ def get_human_indexes(players)
+ ret = []
+ for i in 0..(players.size-1)
+ ret << i if players[i].is_human?
+ end
+ return ret
end
end
end
class SortByRateWithRandomness < Pairing
- def initialize(rand1, rand2)
+ def initialize(rand1, rand2, desc=false)
super()
@rand1, @rand2 = rand1, rand2
+ @desc = desc
end
def match(players)
- super
+ super(players)
cur_rate = Hash.new
players.each{|a| cur_rate[a] = a.rate ? a.rate + rand(@rand1) : rand(@rand2)}
players.sort!{|a,b| cur_rate[a] <=> cur_rate[b]}
+ players.reverse! if @desc
log_players(players) do |one|
- "%s %d (randomness %d)" % [one.name, one.rate, cur_rate[one] - one.rate]
+ "%s %d (+ randomness %d)" % [one.name, one.rate, cur_rate[one] - one.rate]
+ end
+ end
+ end
+
+ class Swiss < Pairing
+ def match(players)
+ super
+ if players.size < 3
+ log_message("Floodgate: players are small enough to skip Swiss pairing: %d" % [players.size])
+ return
+ end
+
+ path = ShogiServer::League::Floodgate.history_file_path(players.first.game_name)
+ history = ShogiServer::League::Floodgate::History.factory(path)
+
+ winners = []
+ if history
+ winners = players.find_all {|pl| history.last_win?(pl.player_id)}
+ end
+ rest = players - winners
+
+ log_message("Floodgate: Ordering %d winners..." % [winners.size])
+ sbrwr_winners = SortByRateWithRandomness.new(800, 2500, true)
+ sbrwr_winners.match(winners)
+
+ log_message("Floodgate: Ordering the rest (%d)..." % [rest.size])
+ sbrwr_losers = SortByRateWithRandomness.new(200, 400, true)
+ sbrwr_losers.match(rest)
+
+ players.clear
+ [winners, rest].each do |group|
+ group.each {|pl| players << pl}
end
end
end
def match(players)
super
return if less_than_one?(players)
- one = players.choice
+ one = players.sample
log_message("Floodgate: Deleted %s at random" % [one.name])
players.delete(one)
log_players(players)
# @sacrifice a player id to be eliminated
def initialize(sacrifice)
super()
- @sacrifice = sacrifice
+ @sacrifice = sacrifice || "gps500+e293220e3f8a3e59f79f6b0efffaa931"
end
def match(players)
class MakeEven < Pairing
def match(players)
super
- return if players.even?
- log_message("Floodgate: there are odd players: %d. Deleting one..." %
+ return if players.size.even?
+ log_message("Floodgate: There are odd players (%d). Deleting one of them..." %
[players.size])
DeletePlayerAtRandom.new.match(players)
end
end
+ # 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
+
+ # 2.3 a match with likely kin players
+ if (p1.player_id[0..6] == p2.player_id[0..6])
+ ret += 800
+ elsif (p1.player_id[0..3] == p2.player_id[0..3])
+ ret += 400
+ end
+ end
+
+ ret
+ end
+
+ # Total combinations of possible games among n players
+ # nC2 * (n-2)C2 * ... * 2C2 / (n/2)!
+ def total_posibilities(n)
+ n -= 1 if n.odd?
+ return 1 if n <= 2
+
+ ret = 1
+ i = n
+ while i >= 2 do
+ ret *= ::ShogiServer::nCk(i,2)
+ i -= 2
+ end
+ ret /= ::ShogiServer::factorial(n/2)
+ return 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}
+
+ matches = []
+ scores = []
+ path = ShogiServer::League::Floodgate.history_file_path(players.first.game_name)
+ history = ShogiServer::League::Floodgate::History.factory(path)
+
+ # Increase trials, depending on a number of players
+ trials = [300, total_posibilities(players.size)/3].min
+ trials = [10, trials].max
+ log_message("Floodgate: %d trials" % [trials])
+ trials.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 game) [%s]" % [min_score, min_score/players.size*2, 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
+
end # ShogiServer
OSDN Git Service
