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(options)
  28         return least_diff_pairing(options)
  29       end
  30
  31       def sort_by_rate_with_randomness(options)
  32         return [LogPlayers.new,
  33                 ExcludeSacrifice.new(options[:sacrifice]),
  34                 MakeEven.new,
  35                 SortByRateWithRandomness.new(1200, 2400),
  36                 StartGameWithoutHumans.new]
  37       end
  38
  39       def random_pairing(options)
  40         return [LogPlayers.new,
  41                 ExcludeSacrifice.new(options[:sacrifice]),
  42                 MakeEven.new,
  43                 Randomize.new,
  44                 StartGameWithoutHumans.new]
  45       end
  46
  47       def swiss_pairing(options)
  48         return [LogPlayers.new,
  49                 ExcludeSacrifice.new(options[:sacrifice]),
  50                 MakeEven.new,
  51                 Swiss.new,
  52                 StartGameWithoutHumans.new]
  53       end
  54
  55       def least_diff_pairing(options)
  56         return [LogPlayers.new,
  57                 ExcludeSacrifice.new(options[:sacrifice]),
  58                 MakeEven.new,
  59                 LeastDiff.new,
  60                 StartGameWithoutHumans.new]
  61       end
  62
  63       def floodgate_zyunisen(options)
  64         return [LogPlayers.new,
  65                 ExcludeUnratedPlayers.new,
  66                 ExcludeSacrifice.new(options[:sacrifice]),
  67                 MakeEven.new,
  68                 LeastDiff.new,
  69                 StartGameWithoutHumans.new]
  70       end
  71
  72       def match(players, logics)
  73         logics.inject(players) do |result, item|
  74           item.match(result)
  75           result
  76         end
  77       end
  78     end # class << self
  79
  80
  81     # Make matches among players.
  82     # @param players an array of players, which should be updated destructively
  83     #        to pass the new list to subsequent logics.
  84     #
  85     def match(players)
  86       # to be implemented
  87       log_message("Floodgate: %s" % [self.class.to_s])
  88     end
  89
  90     def include_newbie?(players)
  91       return players.find{|a| a.rate == 0} == nil ? false : true
  92     end
  93
  94     def less_than_one?(players)
  95       if players.size < 1
  96         log_warning("Floodgate: There should be at least one player.")
  97         return true
  98       else
  99         return false
 100       end
 101     end
 102
 103     def log_players(players)
 104       str_array = players.map do |one|
 105         if block_given?
 106           yield one
 107         else
 108           one.name
 109         end
 110       end
 111       if str_array.empty?
 112         log_message("Floodgate: [Players] Nobody found.")
 113       else
 114         log_message("Floodgate: [Players] %s." % [str_array.join(", ")])
 115       end
 116     end
 117   end # Pairing
 118
 119
 120   class LogPlayers < Pairing
 121     def match(players)
 122       super
 123       log_players(players)
 124     end
 125   end
 126
 127   class AbstractStartGame < Pairing
 128     def start_game(p1, p2)
 129       log_message("Floodgate: Starting a game: BLACK %s vs WHITE %s" % [p1.name, p2.name])
 130       p1.sente = true
 131       p2.sente = false
 132       board = Board.new
 133       board.initial
 134       Game.new(p1.game_name, p1, p2, board)
 135     end
 136
 137     def start_game_shuffle(pair)
 138       pair.shuffle!
 139       start_game(pair.first, pair.last)
 140     end
 141   end
 142
 143   class StartGame < AbstractStartGame
 144     def match(players)
 145       super
 146       if players.size < 2
 147         log_message("Floodgate: There are less than two players: %d" % [players.size])
 148         return
 149       end
 150       if players.size.odd?
 151         log_warning("Floodgate: There are odd players (%d). %s will not be matched." %
 152                     [players.size, players.last.name])
 153       end
 154
 155       log_players(players)
 156       while (players.size >= 2) do
 157         pair = players.shift(2)
 158         start_game_shuffle(pair)
 159       end
 160     end
 161   end
 162
 163   # This tries to avoid a human-human match
 164   #
 165   class StartGameWithoutHumans < AbstractStartGame
 166     def match(players)
 167       super
 168       log_players(players)
 169       if players.size < 2
 170         log_message("Floodgate: There are less than two players: %d" % [players.size])
 171         return
 172       elsif players.size == 2
 173         start_game_shuffle(players)
 174         return
 175       end
 176
 177       loop do
 178         humans = get_human_indexes(players)
 179         log_message("Floodgate: There are (still) %d humans." % [humans.size])
 180         break if humans.size < 2
 181
 182         pairing_possible = false
 183         for i in 0..(humans.size-2)  # -2
 184           next if humans[i].odd?
 185           if humans[i]+1 == humans[i+1]
 186             pairing_possible = humans[i]
 187             break
 188           end
 189         end
 190         unless pairing_possible
 191           log_message("Floodgate: No possible human-human match found")
 192           break
 193         end
 194
 195         current_index = pairing_possible
 196         j = [0, current_index - 2].max
 197         while j < players.size
 198           break if players[j].is_computer?
 199           j += 1
 200         end
 201
 202         pairing_indexes = []
 203         if j == players.size
 204           # no computer player found
 205           pairing_indexes << current_index << current_index+1
 206         else
 207           # a comupter player found
 208           pairing_indexes << current_index << j
 209         end
 210
 211         pair = []
 212         pair << players.delete_at(pairing_indexes.max)
 213         pair << players.delete_at(pairing_indexes.min)
 214         start_game_shuffle(pair)
 215       end # loop
 216
 217       while (players.size >= 2) do
 218         pair = players.shift(2)
 219         start_game_shuffle(pair)
 220       end
 221     end
 222
 223     private
 224
 225     def get_human_indexes(players)
 226       ret = []
 227       for i in 0..(players.size-1)
 228         ret << i if players[i].is_human?
 229       end
 230       return ret
 231     end
 232   end
 233
 234   class Randomize < Pairing
 235     def match(players)
 236       super
 237       log_message("Floodgate: Randomize... before")
 238       log_players(players)
 239       players.shuffle!
 240       log_message("Floodgate: Randomized after")
 241       log_players(players)
 242     end
 243   end # RadomPairing
 244
 245   class SortByRate < Pairing
 246     def match(players)
 247       super
 248       log_message("Floodgate: Ordered by rate")
 249       players.sort! {|a,b| a.rate <=> b.rate} # decendent order
 250       log_players(players)
 251     end
 252   end
 253
 254   class SortByRateWithRandomness < Pairing
 255     def initialize(rand1, rand2, desc=false)
 256       super()
 257       @rand1, @rand2 = rand1, rand2
 258       @desc = desc
 259     end
 260
 261     def match(players)
 262       super(players)
 263       cur_rate = Hash.new
 264       players.each{|a| cur_rate[a] = a.rate ? a.rate + rand(@rand1) : rand(@rand2)}
 265       players.sort!{|a,b| cur_rate[a] <=> cur_rate[b]}
 266       players.reverse! if @desc
 267       log_players(players) do |one|
 268         "%s %d (+ randomness %d)" % [one.name, one.rate, cur_rate[one] - one.rate]
 269       end
 270     end
 271   end
 272
 273   class Swiss < Pairing
 274     def match(players)
 275       super
 276       if players.size < 3
 277         log_message("Floodgate: players are small enough to skip Swiss pairing: %d" % [players.size])
 278         return
 279       end
 280
 281       path = ShogiServer::League::Floodgate.history_file_path(players.first.game_name)
 282       history = ShogiServer::League::Floodgate::History.factory(path)
 283
 284       winners = []
 285       if history
 286         winners = players.find_all {|pl| history.last_win?(pl.player_id)}
 287       end
 288       rest = players - winners
 289
 290       log_message("Floodgate: Ordering %d winners..." % [winners.size])
 291       sbrwr_winners = SortByRateWithRandomness.new(800, 2500, true)
 292       sbrwr_winners.match(winners)
 293
 294       log_message("Floodgate: Ordering the rest (%d)..." % [rest.size])
 295       sbrwr_losers = SortByRateWithRandomness.new(200, 400, true)
 296       sbrwr_losers.match(rest)
 297
 298       players.clear
 299       [winners, rest].each do |group|
 300         group.each {|pl| players << pl}
 301       end
 302     end
 303   end
 304
 305   class DeletePlayerAtRandom < Pairing
 306     def match(players)
 307       super
 308       return if less_than_one?(players)
 309       one = players.sample
 310       log_message("Floodgate: Deleted %s at random" % [one.name])
 311       players.delete(one)
 312       log_players(players)
 313     end
 314   end
 315
 316   class DeletePlayerAtRandomExcept < Pairing
 317     def initialize(except)
 318       super()
 319       @except = except
 320     end
 321
 322     def match(players)
 323       super
 324       log_message("Floodgate: Deleting a player at rondom except %s" % [@except.name])
 325       players.delete(@except)
 326       DeletePlayerAtRandom.new.match(players)
 327       players.push(@except)
 328     end
 329   end
 330
 331   class DeleteMostPlayingPlayer < Pairing
 332     def match(players)
 333       super
 334       one = players.max_by {|a| a.win + a.loss}
 335       log_message("Floodgate: Deleted the most playing player: %s (%d)" % [one.name, one.win + one.loss])
 336       players.delete(one)
 337       log_players(players)
 338     end
 339   end
 340
 341   class DeleteLeastRatePlayer < Pairing
 342     def match(players)
 343       super
 344       one = players.min_by {|a| a.rate}
 345       log_message("Floodgate: Deleted the least rate player %s (%d)" % [one.name, one.rate])
 346       players.delete(one)
 347       log_players(players)
 348     end
 349   end
 350
 351   class ExcludeSacrifice < Pairing
 352     attr_reader :sacrifice
 353
 354     # @sacrifice a player id to be eliminated
 355     def initialize(sacrifice)
 356       super()
 357       @sacrifice = sacrifice || "gps500+e293220e3f8a3e59f79f6b0efffaa931"
 358     end
 359
 360     def match(players)
 361       super
 362       if @sacrifice &&
 363          players.size.odd? &&
 364          players.find{|a| a.player_id == @sacrifice}
 365          log_message("Floodgate: Deleting the sacrifice %s" % [@sacrifice])
 366          players.delete_if{|a| a.player_id == @sacrifice}
 367          log_players(players)
 368       end
 369     end
 370   end # class ExcludeSacrifice
 371
 372   class ExcludeSacrificeGps500 < ExcludeSacrifice
 373     def initialize
 374       super("gps500+e293220e3f8a3e59f79f6b0efffaa931")
 375     end
 376   end
 377
 378   class MakeEven < Pairing
 379     def match(players)
 380       super
 381       return if players.size.even?
 382       log_message("Floodgate: There are odd players (%d). Deleting one of them..." %
 383                   [players.size])
 384       DeletePlayerAtRandom.new.match(players)
 385     end
 386   end
 387
 388   # This pairing algorithm aims to minimize the total differences of
 389   # matching players' rates. It also includes penalyties when a match is
 390   # same as the previous one or a match is between human players.
 391   # It is based on a discussion with Yamashita-san on
 392   # http://www.sgtpepper.net/kaneko/diary/20120511.html.
 393   #
 394   class LeastDiff < Pairing
 395     def random_match(players)
 396       players.shuffle
 397     end
 398
 399     # Update estimated rate of a player.
 400     # 1. If it has a valid rate, return the rate.
 401     # 2. If it has no valid rate, return:
 402     #   a. If it won the last game, the opponent's rate + 200
 403     #   b. If it lost the last game, the opponent's rate - 200
 404     #   c. otherwise, return 2150 (default value)
 405     #
 406     def estimate_rate(player, history)
 407       player.estimated_rate = 2150 # default value
 408
 409       unless history
 410         log_message("Floodgate: Without game history, estimated %s's rate: %d" % [player.name, player.estimated_rate])
 411         return
 412       end
 413
 414       g = history.last_valid_game(player.player_id)
 415       unless g
 416         log_message("Floodgate: Without any valid games in history, estimated %s's rate: %d" % [player.name, player.estimated_rate])
 417         return
 418       end
 419
 420       opponent_id = nil
 421       win         = true
 422       case player.player_id
 423       when g[:winner]
 424         opponent_id = g[:loser]
 425         win = true
 426       when g[:loser]
 427         opponent_id = g[:winner]
 428         win = false
 429       else
 430         log_warning("Floodgate: The last valid game is invalid for %s!" % [player.name])
 431         log_message("Floodgate: Estimated %s's rate: %d" % [player.name, player.estimated_rate])
 432         return
 433       end
 434
 435       opponent_name = opponent_id.split("+")[0]
 436       p = $league.find(opponent_name)
 437       unless p
 438         log_message("Floodgate: No active opponent found. Estimated %s's rate: %d" % [player.name, player.estimated_rate])
 439         return
 440       end
 441
 442       opponent_rate = 0
 443       if p.rate != 0
 444         opponent_rate = p.rate
 445       elsif p.estimated_rate != 0
 446         opponent_rate = p.estimated_rate
 447       end
 448
 449       if opponent_rate != 0
 450         player.estimated_rate = opponent_rate + (win ? 200 : -200)
 451       end
 452
 453       log_message("Floodgate: Estimated %s's rate: %d" % [player.name, player.estimated_rate])
 454     end
 455
 456     # Return a player's rate based on its actual rate or estimated rate.
 457     #
 458     def get_player_rate(player, history)
 459       if player.rate != 0
 460         return player.rate
 461       elsif player.estimated_rate != 0
 462         return player.estimated_rate
 463       else
 464         estimate_rate(player, history)
 465         return player.estimated_rate
 466       end
 467     end
 468
 469     def calculate_diff_with_penalty(players, history)
 470       pairs = []
 471       players.each_slice(2) do |pair|
 472         if pair.size == 2
 473           pairs << pair
 474         end
 475       end
 476
 477       ret = 0
 478
 479       # 1. Diff of players rate
 480       pairs.each do |p1,p2|
 481         ret += (get_player_rate(p1,history) - get_player_rate(p2,history)).abs
 482       end
 483
 484       # 2. Penalties
 485       pairs.each do |p1,p2|
 486         # 2.1. same match
 487         if (history &&
 488             (history.last_opponent(p1.player_id) == p2.player_id ||
 489              history.last_opponent(p2.player_id) == p1.player_id))
 490           ret += 400
 491         end
 492
 493         # 2.2 Human vs Human
 494         if p1.is_human? && p2.is_human?
 495           ret += 800
 496         end
 497
 498         # 2.3 a match with likely kin players
 499         if (p1.player_id[0..6] == p2.player_id[0..6])
 500           ret += 800
 501         elsif (p1.player_id[0..3] == p2.player_id[0..3])
 502           ret += 400
 503         end
 504       end
 505
 506       ret
 507     end
 508
 509     def match(players)
 510       super
 511       if players.size < 3
 512         log_message("Floodgate: players are small enough to skip LeastDiff pairing: %d" % [players.size])
 513         return players
 514       end
 515
 516       # Reset estimated rate
 517       players.each {|p| p.estimated_rate = 0}
 518
 519       # 10 trials
 520       matches = []
 521       scores  = []
 522       path = ShogiServer::League::Floodgate.history_file_path(players.first.game_name)
 523       history = ShogiServer::League::Floodgate::History.factory(path)
 524       10.times do
 525         m = random_match(players)
 526         matches << m
 527         scores << calculate_diff_with_penalty(m, history)
 528       end
 529
 530       # Debug
 531       #scores.each_with_index do |s,i|
 532       #  puts
 533       #  print s, ": ", matches[i].map{|p| p.name}.join(", "), "\n"
 534       #end
 535
 536       # Select a match of the least score
 537       min_index = 0
 538       min_score = scores.first
 539       scores.each_with_index do |s,i|
 540         if s < min_score
 541           min_index = i
 542           min_score = s
 543         end
 544       end
 545       log_message("Floodgate: the least score %d (%d per game) [%s]" % [min_score, min_score/players.size*2, scores.join(" ")])
 546
 547       players.replace(matches[min_index])
 548     end
 549   end
 550
 551   # This pairing method excludes unrated players
 552   #
 553   class ExcludeUnratedPlayers < Pairing
 554
 555     def match(players)
 556       super
 557
 558       log_message("Floodgate: Deleting unrated players...")
 559       players.delete_if{|a| a.rate == 0}
 560       log_players(players)
 561     end
 562   end # class ExcludeUnratedPlayers
 563
 564 end # ShogiServer