shogi_server/pairing.rb

   1 ## $Id$
   2
   3 ## Copyright (C) 2004 NABEYA Kenichi (aka nanami@2ch)
   4 ## Copyright (C) 2007-2012 Daigo Moriwaki (daigo at debian dot org)
   5 ##
   6 ## This program is free software; you can redistribute it and/or modify
   7 ## it under the terms of the GNU General Public License as published by
   8 ## the Free Software Foundation; either version 2 of the License, or
   9 ## (at your option) any later version.
  10 ##
  11 ## This program is distributed in the hope that it will be useful,
  12 ## but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 ## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 ## GNU General Public License for more details.
  15 ##
  16 ## You should have received a copy of the GNU General Public License
  17 ## along with this program; if not, write to the Free Software
  18 ## Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  19
  20 require 'shogi_server/util'
  21
  22 module ShogiServer
  23
  24   class Pairing
  25
  26     class << self
  27       def default_factory
  28         return least_diff_pairing
  29       end
  30
  31       def sort_by_rate_with_randomness
  32         return [LogPlayers.new,
  33                 ExcludeSacrificeGps500.new,
  34                 MakeEven.new,
  35                 SortByRateWithRandomness.new(1200, 2400),
  36                 StartGameWithoutHumans.new]
  37       end
  38
  39       def random_pairing
  40         return [LogPlayers.new,
  41                 ExcludeSacrificeGps500.new,
  42                 MakeEven.new,
  43                 Randomize.new,
  44                 StartGameWithoutHumans.new]
  45       end
  46
  47       def swiss_pairing
  48         return [LogPlayers.new,
  49                 ExcludeSacrificeGps500.new,
  50                 MakeEven.new,
  51                 Swiss.new,
  52                 StartGameWithoutHumans.new]
  53       end
  54
  55       def least_diff_pairing
  56         return [LogPlayers.new,
  57                 ExcludeSacrificeGps500.new,
  58                 MakeEven.new,
  59                 LeastDiff.new,
  60                 StartGameWithoutHumans.new]
  61       end
  62
  63       def match(players)
  64         logics = default_factory
  65         logics.inject(players) do |result, item|
  66           item.match(result)
  67           result
  68         end
  69       end
  70     end # class << self
  71
  72
  73     # Make matches among players.
  74     # @param players an array of players, which should be updated destructively
  75     #        to pass the new list to subsequent logics.
  76     #
  77     def match(players)
  78       # to be implemented
  79       log_message("Floodgate: %s" % [self.class.to_s])
  80     end
  81
  82     def include_newbie?(players)
  83       return players.find{|a| a.rate == 0} == nil ? false : true
  84     end
  85
  86     def less_than_one?(players)
  87       if players.size < 1
  88         log_warning("Floodgate: There should be at least one player.")
  89         return true
  90       else
  91         return false
  92       end
  93     end
  94
  95     def log_players(players)
  96       str_array = players.map do |one|
  97         if block_given?
  98           yield one
  99         else
 100           one.name
 101         end
 102       end
 103       if str_array.empty?
 104         log_message("Floodgate: [Players] Nobody found.")
 105       else
 106         log_message("Floodgate: [Players] %s." % [str_array.join(", ")])
 107       end
 108     end
 109   end # Pairing
 110
 111
 112   class LogPlayers < Pairing
 113     def match(players)
 114       super
 115       log_players(players)
 116     end
 117   end
 118
 119   class AbstractStartGame < Pairing
 120     def start_game(p1, p2)
 121       log_message("Floodgate: Starting a game: BLACK %s vs WHITE %s" % [p1.name, p2.name])
 122       p1.sente = true
 123       p2.sente = false
 124       board = Board.new
 125       board.initial
 126       Game.new(p1.game_name, p1, p2, board)
 127     end
 128
 129     def start_game_shuffle(pair)
 130       pair.shuffle!
 131       start_game(pair.first, pair.last)
 132     end
 133   end
 134
 135   class StartGame < AbstractStartGame
 136     def match(players)
 137       super
 138       if players.size < 2
 139         log_warning("Floodgate: There should be more than one player (%d)." % [players.size])
 140         return
 141       end
 142       if players.size.odd?
 143         log_warning("Floodgate: There are odd players (%d). %s will not be matched." %
 144                     [players.size, players.last.name])
 145       end
 146
 147       log_players(players)
 148       while (players.size >= 2) do
 149         pair = players.shift(2)
 150         start_game_shuffle(pair)
 151       end
 152     end
 153   end
 154
 155   # This tries to avoid a human-human match
 156   #
 157   class StartGameWithoutHumans < AbstractStartGame
 158     def match(players)
 159       super
 160       log_players(players)
 161       if players.size < 2
 162         log_warning("Floodgate: There should be more than one player (%d)." % [players.size])
 163         return
 164       elsif players.size == 2
 165         start_game_shuffle(players)
 166         return
 167       end
 168
 169       loop do
 170         humans = get_human_indexes(players)
 171         log_message("Floodgate: There are (still) %d humans." % [humans.size])
 172         break if humans.size < 2
 173
 174         pairing_possible = false
 175         for i in 0..(humans.size-2)  # -2
 176           next if humans[i].odd?
 177           if humans[i]+1 == humans[i+1]
 178             pairing_possible = humans[i]
 179             break
 180           end
 181         end
 182         unless pairing_possible
 183           log_message("Floodgate: No possible human-human match found")
 184           break
 185         end
 186
 187         current_index = pairing_possible
 188         j = [0, current_index - 2].max
 189         while j < players.size
 190           break if players[j].is_computer?
 191           j += 1
 192         end
 193
 194         pairing_indexes = []
 195         if j == players.size
 196           # no computer player found
 197           pairing_indexes << current_index << current_index+1
 198         else
 199           # a comupter player found
 200           pairing_indexes << current_index << j
 201         end
 202
 203         pair = []
 204         pair << players.delete_at(pairing_indexes.max)
 205         pair << players.delete_at(pairing_indexes.min)
 206         start_game_shuffle(pair)
 207       end # loop
 208
 209       while (players.size >= 2) do
 210         pair = players.shift(2)
 211         start_game_shuffle(pair)
 212       end
 213     end
 214
 215     private
 216
 217     def get_human_indexes(players)
 218       ret = []
 219       for i in 0..(players.size-1)
 220         ret << i if players[i].is_human?
 221       end
 222       return ret
 223     end
 224   end
 225
 226   class Randomize < Pairing
 227     def match(players)
 228       super
 229       log_message("Floodgate: Randomize... before")
 230       log_players(players)
 231       players.shuffle!
 232       log_message("Floodgate: Randomized after")
 233       log_players(players)
 234     end
 235   end # RadomPairing
 236
 237   class SortByRate < Pairing
 238     def match(players)
 239       super
 240       log_message("Floodgate: Ordered by rate")
 241       players.sort! {|a,b| a.rate <=> b.rate} # decendent order
 242       log_players(players)
 243     end
 244   end
 245
 246   class SortByRateWithRandomness < Pairing
 247     def initialize(rand1, rand2, desc=false)
 248       super()
 249       @rand1, @rand2 = rand1, rand2
 250       @desc = desc
 251     end
 252
 253     def match(players)
 254       super(players)
 255       cur_rate = Hash.new
 256       players.each{|a| cur_rate[a] = a.rate ? a.rate + rand(@rand1) : rand(@rand2)}
 257       players.sort!{|a,b| cur_rate[a] <=> cur_rate[b]}
 258       players.reverse! if @desc
 259       log_players(players) do |one|
 260         "%s %d (+ randomness %d)" % [one.name, one.rate, cur_rate[one] - one.rate]
 261       end
 262     end
 263   end
 264
 265   class Swiss < Pairing
 266     def match(players)
 267       super
 268       if players.size < 3
 269         log_message("Floodgate: players are small enough to skip Swiss pairing: %d" % [players.size])
 270         return
 271       end
 272
 273       path = ShogiServer::League::Floodgate.history_file_path(players.first.game_name)
 274       history = ShogiServer::League::Floodgate::History.factory(path)
 275
 276       winners = []
 277       if history
 278         winners = players.find_all {|pl| history.last_win?(pl.player_id)}
 279       end
 280       rest = players - winners
 281
 282       log_message("Floodgate: Ordering %d winners..." % [winners.size])
 283       sbrwr_winners = SortByRateWithRandomness.new(800, 2500, true)
 284       sbrwr_winners.match(winners)
 285
 286       log_message("Floodgate: Ordering the rest (%d)..." % [rest.size])
 287       sbrwr_losers = SortByRateWithRandomness.new(200, 400, true)
 288       sbrwr_losers.match(rest)
 289
 290       players.clear
 291       [winners, rest].each do |group|
 292         group.each {|pl| players << pl}
 293       end
 294     end
 295   end
 296
 297   class DeletePlayerAtRandom < Pairing
 298     def match(players)
 299       super
 300       return if less_than_one?(players)
 301       one = players.sample
 302       log_message("Floodgate: Deleted %s at random" % [one.name])
 303       players.delete(one)
 304       log_players(players)
 305     end
 306   end
 307
 308   class DeletePlayerAtRandomExcept < Pairing
 309     def initialize(except)
 310       super()
 311       @except = except
 312     end
 313
 314     def match(players)
 315       super
 316       log_message("Floodgate: Deleting a player at rondom except %s" % [@except.name])
 317       players.delete(@except)
 318       DeletePlayerAtRandom.new.match(players)
 319       players.push(@except)
 320     end
 321   end
 322
 323   class DeleteMostPlayingPlayer < Pairing
 324     def match(players)
 325       super
 326       one = players.max_by {|a| a.win + a.loss}
 327       log_message("Floodgate: Deleted the most playing player: %s (%d)" % [one.name, one.win + one.loss])
 328       players.delete(one)
 329       log_players(players)
 330     end
 331   end
 332
 333   class DeleteLeastRatePlayer < Pairing
 334     def match(players)
 335       super
 336       one = players.min_by {|a| a.rate}
 337       log_message("Floodgate: Deleted the least rate player %s (%d)" % [one.name, one.rate])
 338       players.delete(one)
 339       log_players(players)
 340     end
 341   end
 342
 343   class ExcludeSacrifice < Pairing
 344     attr_reader :sacrifice
 345
 346     # @sacrifice a player id to be eliminated
 347     def initialize(sacrifice)
 348       super()
 349       @sacrifice = sacrifice
 350     end
 351
 352     def match(players)
 353       super
 354       if @sacrifice &&
 355          players.size.odd? &&
 356          players.find{|a| a.player_id == @sacrifice}
 357          log_message("Floodgate: Deleting the sacrifice %s" % [@sacrifice])
 358          players.delete_if{|a| a.player_id == @sacrifice}
 359          log_players(players)
 360       end
 361     end
 362   end # class ExcludeSacrifice
 363
 364   class ExcludeSacrificeGps500 < ExcludeSacrifice
 365     def initialize
 366       super("gps500+e293220e3f8a3e59f79f6b0efffaa931")
 367     end
 368   end
 369
 370   class MakeEven < Pairing
 371     def match(players)
 372       super
 373       return if players.size.even?
 374       log_message("Floodgate: There are odd players (%d). Deleting one of them..." %
 375                   [players.size])
 376       DeletePlayerAtRandom.new.match(players)
 377     end
 378   end
 379
 380   # This pairing algorithm aims to minimize the total differences of
 381   # matching players' rates. It also includes penalyties when a match is
 382   # same as the previous one or a match is between human players.
 383   # It is based on a discussion with Yamashita-san on
 384   # http://www.sgtpepper.net/kaneko/diary/20120511.html.
 385   #
 386   class LeastDiff < Pairing
 387     def random_match(players)
 388       players.shuffle
 389     end
 390
 391     # Returns a player's rate value.
 392     # 1. If it has a valid rate, return the rate.
 393     # 2. If it has no valid rate, return average of the following values:
 394     #   a. For games it won, the opponent's rate + 100
 395     #   b. For games it lost, the opponent's rate - 100
 396     #   (if the opponent has no valid rate, count out the game)
 397     #   (if there are not such games, return 2150 (default value)
 398     #
 399     def get_player_rate(player, history)
 400       return player.rate if player.rate != 0
 401       return 2150 unless history
 402
 403       count = 0
 404       sum = 0
 405
 406       history.win_games(player.player_id).each do |g|
 407         next unless g[:loser]
 408         name = g[:loser].split("+")[0]
 409         p = $league.find(name)
 410         if p && p.rate != 0
 411           count += 1
 412           sum += p.rate + 100
 413         end
 414       end
 415       history.loss_games(player.player_id).each do |g|
 416         next unless g[:winner]
 417         name = g[:winner].split("+")[0]
 418         p = $league.find(name)
 419         if p && p.rate != 0
 420           count += 1
 421           sum += p.rate - 100
 422         end
 423       end
 424
 425       estimate = (count == 0 ? 2150 : sum/count)
 426       log_message("Floodgate: Estimated rate of %s is %d" % [player.name, estimate])
 427       return estimate
 428     end
 429
 430     def calculate_diff_with_penalty(players, history)
 431       pairs = []
 432       players.each_slice(2) do |pair|
 433         if pair.size == 2
 434           pairs << pair
 435         end
 436       end
 437
 438       ret = 0
 439
 440       # 1. Diff of players rate
 441       pairs.each do |p1,p2|
 442         ret += (get_player_rate(p1,history) - get_player_rate(p2,history)).abs
 443       end
 444
 445       # 2. Penalties
 446       pairs.each do |p1,p2|
 447         # 2.1. same match
 448         if (history &&
 449             (history.last_opponent(p1.player_id) == p2.player_id ||
 450              history.last_opponent(p2.player_id) == p1.player_id))
 451           ret += 400
 452         end
 453
 454         # 2.2 Human vs Human
 455         if p1.is_human? && p2.is_human?
 456           ret += 800
 457         end
 458       end
 459
 460       ret
 461     end
 462
 463     def match(players)
 464       super
 465       if players.size < 3
 466         log_message("Floodgate: players are small enough to skip LeastDiff pairing: %d" % [players.size])
 467         return players
 468       end
 469
 470       # 10 trials
 471       matches = []
 472       scores  = []
 473       path = ShogiServer::League::Floodgate.history_file_path(players.first.game_name)
 474       history = ShogiServer::League::Floodgate::History.factory(path)
 475       10.times do
 476         m = random_match(players)
 477         matches << m
 478         scores << calculate_diff_with_penalty(m, history)
 479       end
 480
 481       # Debug
 482       #scores.each_with_index do |s,i|
 483       #  puts
 484       #  print s, ": ", matches[i].map{|p| p.name}.join(", "), "\n"
 485       #end
 486
 487       # Select a match of the least score
 488       min_index = 0
 489       min_score = scores.first
 490       scores.each_with_index do |s,i|
 491         if s < min_score
 492           min_index = i
 493           min_score = s
 494         end
 495       end
 496       log_message("Floodgate: the least score %d (%d per player) [%s]" % [min_score, min_score/players.size, scores.join(" ")])
 497
 498       players.replace(matches[min_index])
 499     end
 500   end
 501
 502 end # ShogiServer