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