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