shogi_server/pairing.rb

   1 ## $Id$
   2
   3 ## Copyright (C) 2004 NABEYA Kenichi (aka nanami@2ch)
   4 ## Copyright (C) 2007-2008 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 swiss_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 match(players)
  56         logics = default_factory
  57         logics.inject(players) do |result, item|
  58           item.match(result)
  59           result
  60         end
  61       end
  62     end # class << self
  63
  64
  65     def match(players)
  66       # to be implemented
  67       log_message("Floodgate: %s" % [self.class.to_s])
  68     end
  69
  70     def include_newbie?(players)
  71       return players.find{|a| a.rate == 0} == nil ? false : true
  72     end
  73
  74     def less_than_one?(players)
  75       if players.size < 1
  76         log_warning("Floodgate: There should be at least one player.")
  77         return true
  78       else
  79         return false
  80       end
  81     end
  82
  83     def log_players(players)
  84       str_array = players.map do |one|
  85         if block_given?
  86           yield one
  87         else
  88           one.name
  89         end
  90       end
  91       if str_array.empty?
  92         log_message("Floodgate: [Players] Nobody found.")
  93       else
  94         log_message("Floodgate: [Players] %s." % [str_array.join(", ")])
  95       end
  96     end
  97   end # Pairing
  98
  99
 100   class LogPlayers < Pairing
 101     def match(players)
 102       super
 103       log_players(players)
 104     end
 105   end
 106
 107   class AbstractStartGame < Pairing
 108     def start_game(p1, p2)
 109       log_message("Floodgate: Starting a game: BLACK %s vs WHITE %s" % [p1.name, p2.name])
 110       p1.sente = true
 111       p2.sente = false
 112       board = Board.new
 113       board.initial
 114       Game.new(p1.game_name, p1, p2, board)
 115     end
 116
 117     def start_game_shuffle(pair)
 118       pair.shuffle!
 119       start_game(pair.first, pair.last)
 120     end
 121   end
 122
 123   class StartGame < AbstractStartGame
 124     def match(players)
 125       super
 126       if players.size < 2
 127         log_warning("Floodgate: There should be more than one player (%d)." % [players.size])
 128         return
 129       end
 130       if players.size.odd?
 131         log_warning("Floodgate: There are odd players (%d). %s will not be matched." %
 132                     [players.size, players.last.name])
 133       end
 134
 135       log_players(players)
 136       while (players.size >= 2) do
 137         pair = players.shift(2)
 138         start_game_shuffle(pair)
 139       end
 140     end
 141   end
 142
 143   # This tries to avoid a human-human match
 144   #
 145   class StartGameWithoutHumans < AbstractStartGame
 146     def match(players)
 147       super
 148       log_players(players)
 149       if players.size < 2
 150         log_warning("Floodgate: There should be more than one player (%d)." % [players.size])
 151         return
 152       elsif players.size == 2
 153         start_game_shuffle(players)
 154         return
 155       end
 156
 157       loop do
 158         humans = get_human_indexes(players)
 159         log_message("Floodgate: There are (still) %d humans." % [humans.size])
 160         break if humans.size < 2
 161
 162         pairing_possible = false
 163         for i in 0..(humans.size-2)  # -2
 164           next if humans[i].odd?
 165           if humans[i]+1 == humans[i+1]
 166             pairing_possible = i
 167             break
 168           end
 169         end
 170         unless pairing_possible
 171           log_message("Floodgate: No possible human-human match found")
 172           break
 173         end
 174
 175         current_index = pairing_possible
 176         j = (current_index == 0 ? current_index : current_index-1)
 177         while j < players.size
 178           break if players[j].is_computer?
 179           j += 1
 180         end
 181
 182         pairing_indexes = []
 183         if j == players.size
 184           # no computer player found
 185           pairing_indexes << current_index << current_index+1
 186         else
 187           # a comupter player found
 188           pairing_indexes << current_index << j
 189         end
 190
 191         pair = []
 192         pair << players.delete_at(pairing_indexes.max)
 193         pair << players.delete_at(pairing_indexes.min)
 194         start_game_shuffle(pair)
 195       end # loop
 196
 197       while (players.size >= 2) do
 198         pair = players.shift(2)
 199         start_game_shuffle(pair)
 200       end
 201     end
 202
 203     private
 204
 205     def get_human_indexes(players)
 206       ret = []
 207       for i in 0..(players.size-1)
 208         ret << i if players[i].is_human?
 209       end
 210       return ret
 211     end
 212   end
 213
 214   class Randomize < Pairing
 215     def match(players)
 216       super
 217       log_message("Floodgate: Randomize... before")
 218       log_players(players)
 219       players.shuffle!
 220       log_message("Floodgate: Randomized after")
 221       log_players(players)
 222     end
 223   end # RadomPairing
 224
 225   class SortByRate < Pairing
 226     def match(players)
 227       super
 228       log_message("Floodgate: Ordered by rate")
 229       players.sort! {|a,b| a.rate <=> b.rate} # decendent order
 230       log_players(players)
 231     end
 232   end
 233
 234   class SortByRateWithRandomness < Pairing
 235     def initialize(rand1, rand2)
 236       super()
 237       @rand1, @rand2 = rand1, rand2
 238     end
 239
 240     def match(players, desc=false)
 241       super(players)
 242       cur_rate = Hash.new
 243       players.each{|a| cur_rate[a] = a.rate ? a.rate + rand(@rand1) : rand(@rand2)}
 244       players.sort!{|a,b| cur_rate[a] <=> cur_rate[b]}
 245       players.reverse! if desc
 246       log_players(players) do |one|
 247         "%s %d (+ randomness %d)" % [one.name, one.rate, cur_rate[one] - one.rate]
 248       end
 249     end
 250   end
 251
 252   class Swiss < Pairing
 253     def match(players)
 254       super
 255       if players.size < 3
 256         log_message("Floodgate: players are small enough to skip Swiss pairing: %d" % [players.size])
 257         return
 258       end
 259
 260       path = ShogiServer::League::Floodgate.history_file_path(players.first.game_name)
 261       history = ShogiServer::League::Floodgate::History.factory(path)
 262
 263       winners = []
 264       if history
 265         winners = players.find_all {|pl| history.last_win?(pl.player_id)}
 266       end
 267       rest = players - winners
 268
 269       log_message("Floodgate: Ordering %d winners..." % [winners.size])
 270       sbrwr_winners = SortByRateWithRandomness.new(800, 2500)
 271       sbrwr_winners.match(winners, true)
 272
 273       log_message("Floodgate: Ordering the rest (%d)..." % [rest.size])
 274       sbrwr_losers = SortByRateWithRandomness.new(200, 400)
 275       sbrwr_losers.match(rest, true)
 276
 277       players.clear
 278       [winners, rest].each do |group|
 279         group.each {|pl| players << pl}
 280       end
 281     end
 282   end
 283
 284   class DeletePlayerAtRandom < Pairing
 285     def match(players)
 286       super
 287       return if less_than_one?(players)
 288       one = players.choice
 289       log_message("Floodgate: Deleted %s at random" % [one.name])
 290       players.delete(one)
 291       log_players(players)
 292     end
 293   end
 294
 295   class DeletePlayerAtRandomExcept < Pairing
 296     def initialize(except)
 297       super()
 298       @except = except
 299     end
 300
 301     def match(players)
 302       super
 303       log_message("Floodgate: Deleting a player at rondom except %s" % [@except.name])
 304       players.delete(@except)
 305       DeletePlayerAtRandom.new.match(players)
 306       players.push(@except)
 307     end
 308   end
 309
 310   class DeleteMostPlayingPlayer < Pairing
 311     def match(players)
 312       super
 313       one = players.max_by {|a| a.win + a.loss}
 314       log_message("Floodgate: Deleted the most playing player: %s (%d)" % [one.name, one.win + one.loss])
 315       players.delete(one)
 316       log_players(players)
 317     end
 318   end
 319
 320   class DeleteLeastRatePlayer < Pairing
 321     def match(players)
 322       super
 323       one = players.min_by {|a| a.rate}
 324       log_message("Floodgate: Deleted the least rate player %s (%d)" % [one.name, one.rate])
 325       players.delete(one)
 326       log_players(players)
 327     end
 328   end
 329
 330   class ExcludeSacrifice < Pairing
 331     attr_reader :sacrifice
 332
 333     # @sacrifice a player id to be eliminated
 334     def initialize(sacrifice)
 335       super()
 336       @sacrifice = sacrifice
 337     end
 338
 339     def match(players)
 340       super
 341       if @sacrifice &&
 342          players.size.odd? &&
 343          players.find{|a| a.player_id == @sacrifice}
 344          log_message("Floodgate: Deleting the sacrifice %s" % [@sacrifice])
 345          players.delete_if{|a| a.player_id == @sacrifice}
 346          log_players(players)
 347       end
 348     end
 349   end # class ExcludeSacrifice
 350
 351   class ExcludeSacrificeGps500 < ExcludeSacrifice
 352     def initialize
 353       super("gps500+e293220e3f8a3e59f79f6b0efffaa931")
 354     end
 355   end
 356
 357   class MakeEven < Pairing
 358     def match(players)
 359       super
 360       return if players.size.even?
 361       log_message("Floodgate: There are odd players (%d). Deleting one of them..." %
 362                   [players.size])
 363       DeletePlayerAtRandom.new.match(players)
 364     end
 365   end
 366
 367 end # ShogiServer