3 ## Copyright (C) 2004 NABEYA Kenichi (aka nanami@2ch)
4 ## Copyright (C) 2007-2012 Daigo Moriwaki (daigo at debian dot org)
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.
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.
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
20 require 'shogi_server/util'
28 return least_diff_pairing
31 def sort_by_rate_with_randomness
32 return [LogPlayers.new,
33 ExcludeSacrificeGps500.new,
35 SortByRateWithRandomness.new(1200, 2400),
36 StartGameWithoutHumans.new]
40 return [LogPlayers.new,
41 ExcludeSacrificeGps500.new,
44 StartGameWithoutHumans.new]
48 return [LogPlayers.new,
49 ExcludeSacrificeGps500.new,
52 StartGameWithoutHumans.new]
55 def least_diff_pairing
56 return [LogPlayers.new,
57 ExcludeSacrificeGps500.new,
60 StartGameWithoutHumans.new]
63 def floodgate_zyunisen
64 return [LogPlayers.new,
65 ExcludeUnratedPlayers.new,
66 ExcludeSacrificeGps500.new,
69 StartGameWithoutHumans.new]
72 def match(players, logics)
73 logics.inject(players) do |result, item|
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.
87 log_message("Floodgate: %s" % [self.class.to_s])
90 def include_newbie?(players)
91 return players.find{|a| a.rate == 0} == nil ? false : true
94 def less_than_one?(players)
96 log_warning("Floodgate: There should be at least one player.")
103 def log_players(players)
104 str_array = players.map do |one|
112 log_message("Floodgate: [Players] Nobody found.")
114 log_message("Floodgate: [Players] %s." % [str_array.join(", ")])
120 class LogPlayers < Pairing
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])
134 Game.new(p1.game_name, p1, p2, board)
137 def start_game_shuffle(pair)
139 start_game(pair.first, pair.last)
143 class StartGame < AbstractStartGame
147 log_warning("Floodgate: There should be more than one player (%d)." % [players.size])
151 log_warning("Floodgate: There are odd players (%d). %s will not be matched." %
152 [players.size, players.last.name])
156 while (players.size >= 2) do
157 pair = players.shift(2)
158 start_game_shuffle(pair)
163 # This tries to avoid a human-human match
165 class StartGameWithoutHumans < AbstractStartGame
170 log_warning("Floodgate: There should be more than one player (%d)." % [players.size])
172 elsif players.size == 2
173 start_game_shuffle(players)
178 humans = get_human_indexes(players)
179 log_message("Floodgate: There are (still) %d humans." % [humans.size])
180 break if humans.size < 2
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]
190 unless pairing_possible
191 log_message("Floodgate: No possible human-human match found")
195 current_index = pairing_possible
196 j = [0, current_index - 2].max
197 while j < players.size
198 break if players[j].is_computer?
204 # no computer player found
205 pairing_indexes << current_index << current_index+1
207 # a comupter player found
208 pairing_indexes << current_index << j
212 pair << players.delete_at(pairing_indexes.max)
213 pair << players.delete_at(pairing_indexes.min)
214 start_game_shuffle(pair)
217 while (players.size >= 2) do
218 pair = players.shift(2)
219 start_game_shuffle(pair)
225 def get_human_indexes(players)
227 for i in 0..(players.size-1)
228 ret << i if players[i].is_human?
234 class Randomize < Pairing
237 log_message("Floodgate: Randomize... before")
240 log_message("Floodgate: Randomized after")
245 class SortByRate < Pairing
248 log_message("Floodgate: Ordered by rate")
249 players.sort! {|a,b| a.rate <=> b.rate} # decendent order
254 class SortByRateWithRandomness < Pairing
255 def initialize(rand1, rand2, desc=false)
257 @rand1, @rand2 = rand1, rand2
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]
273 class Swiss < Pairing
277 log_message("Floodgate: players are small enough to skip Swiss pairing: %d" % [players.size])
281 path = ShogiServer::League::Floodgate.history_file_path(players.first.game_name)
282 history = ShogiServer::League::Floodgate::History.factory(path)
286 winners = players.find_all {|pl| history.last_win?(pl.player_id)}
288 rest = players - winners
290 log_message("Floodgate: Ordering %d winners..." % [winners.size])
291 sbrwr_winners = SortByRateWithRandomness.new(800, 2500, true)
292 sbrwr_winners.match(winners)
294 log_message("Floodgate: Ordering the rest (%d)..." % [rest.size])
295 sbrwr_losers = SortByRateWithRandomness.new(200, 400, true)
296 sbrwr_losers.match(rest)
299 [winners, rest].each do |group|
300 group.each {|pl| players << pl}
305 class DeletePlayerAtRandom < Pairing
308 return if less_than_one?(players)
310 log_message("Floodgate: Deleted %s at random" % [one.name])
316 class DeletePlayerAtRandomExcept < Pairing
317 def initialize(except)
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)
331 class DeleteMostPlayingPlayer < Pairing
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])
341 class DeleteLeastRatePlayer < Pairing
344 one = players.min_by {|a| a.rate}
345 log_message("Floodgate: Deleted the least rate player %s (%d)" % [one.name, one.rate])
351 class ExcludeSacrifice < Pairing
352 attr_reader :sacrifice
354 # @sacrifice a player id to be eliminated
355 def initialize(sacrifice)
357 @sacrifice = sacrifice
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}
370 end # class ExcludeSacrifice
372 class ExcludeSacrificeGps500 < ExcludeSacrifice
374 super("gps500+e293220e3f8a3e59f79f6b0efffaa931")
378 class MakeEven < Pairing
381 return if players.size.even?
382 log_message("Floodgate: There are odd players (%d). Deleting one of them..." %
384 DeletePlayerAtRandom.new.match(players)
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.
394 class LeastDiff < Pairing
395 def random_match(players)
399 # Returns a player's rate value.
400 # 1. If it has a valid rate, return the rate.
401 # 2. If it has no valid rate, return average of the following values:
402 # a. For games it won, the opponent's rate + 100
403 # b. For games it lost, the opponent's rate - 100
404 # (if the opponent has no valid rate, count out the game)
405 # (if there are not such games, return 2150 (default value)
407 def get_player_rate(player, history)
408 return player.rate if player.rate != 0
409 return 2150 unless history
414 history.win_games(player.player_id).each do |g|
415 next unless g[:loser]
416 name = g[:loser].split("+")[0]
417 p = $league.find(name)
423 history.loss_games(player.player_id).each do |g|
424 next unless g[:winner]
425 name = g[:winner].split("+")[0]
426 p = $league.find(name)
433 estimate = (count == 0 ? 2150 : sum/count)
434 log_message("Floodgate: Estimated rate of %s is %d" % [player.name, estimate])
438 def calculate_diff_with_penalty(players, history)
440 players.each_slice(2) do |pair|
448 # 1. Diff of players rate
449 pairs.each do |p1,p2|
450 ret += (get_player_rate(p1,history) - get_player_rate(p2,history)).abs
454 pairs.each do |p1,p2|
457 (history.last_opponent(p1.player_id) == p2.player_id ||
458 history.last_opponent(p2.player_id) == p1.player_id))
463 if p1.is_human? && p2.is_human?
474 log_message("Floodgate: players are small enough to skip LeastDiff pairing: %d" % [players.size])
481 path = ShogiServer::League::Floodgate.history_file_path(players.first.game_name)
482 history = ShogiServer::League::Floodgate::History.factory(path)
484 m = random_match(players)
486 scores << calculate_diff_with_penalty(m, history)
490 #scores.each_with_index do |s,i|
492 # print s, ": ", matches[i].map{|p| p.name}.join(", "), "\n"
495 # Select a match of the least score
497 min_score = scores.first
498 scores.each_with_index do |s,i|
504 log_message("Floodgate: the least score %d (%d per player) [%s]" % [min_score, min_score/players.size, scores.join(" ")])
506 players.replace(matches[min_index])
510 # This pairing method excludes unrated players
512 class ExcludeUnratedPlayers < Pairing
517 log_message("Floodgate: Deleting unrated players...")
518 players.delete_if{|a| a.rate == 0}
521 end # class ExcludeUnratedPlayers