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'
27 def default_factory(options)
28 return least_diff_pairing(options)
31 def sort_by_rate_with_randomness(options)
32 return [LogPlayers.new,
33 ExcludeSacrifice.new(options[:sacrifice]),
35 SortByRateWithRandomness.new(1200, 2400),
36 StartGameWithoutHumans.new]
39 def random_pairing(options)
40 return [LogPlayers.new,
41 ExcludeSacrifice.new(options[:sacrifice]),
44 StartGameWithoutHumans.new]
47 def swiss_pairing(options)
48 return [LogPlayers.new,
49 ExcludeSacrifice.new(options[:sacrifice]),
52 StartGameWithoutHumans.new]
55 def least_diff_pairing(options)
56 return [LogPlayers.new,
57 ExcludeSacrifice.new(options[:sacrifice]),
60 StartGameWithoutHumans.new]
63 def floodgate_zyunisen(options)
64 return [LogPlayers.new,
65 ExcludeUnratedPlayers.new,
66 ExcludeSacrifice.new(options[:sacrifice]),
69 StartGameWithoutHumans.new]
72 def match(players, logics, options)
73 logics.inject(players) do |result, item|
74 item.set_options(options)
85 def set_options(options)
86 @options.merge!(options)
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.
95 log_message("Floodgate: %s" % [self.class.to_s])
98 def include_newbie?(players)
99 return players.find{|a| a.rate == 0} == nil ? false : true
102 def less_than_one?(players)
104 log_warning("Floodgate: There should be at least one player.")
111 def log_players(players)
112 str_array = players.map do |one|
120 log_message("Floodgate: [Players] Nobody found.")
122 log_message("Floodgate: [Players] %s." % [str_array.join(", ")])
128 class LogPlayers < Pairing
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])
140 board = Board.new(@options)
142 Game.new(p1.game_name, p1, p2, board)
145 def start_game_shuffle(pair)
147 start_game(pair.first, pair.last)
151 class StartGame < AbstractStartGame
155 log_message("Floodgate: There are less than two players: %d" % [players.size])
159 log_warning("Floodgate: There are odd players (%d). %s will not be matched." %
160 [players.size, players.last.name])
164 while (players.size >= 2) do
165 pair = players.shift(2)
166 start_game_shuffle(pair)
171 # This tries to avoid a human-human match
173 class StartGameWithoutHumans < AbstractStartGame
178 log_message("Floodgate: There are less than two players: %d" % [players.size])
180 elsif players.size == 2
181 start_game_shuffle(players)
186 humans = get_human_indexes(players)
187 log_message("Floodgate: There are (still) %d humans." % [humans.size])
188 break if humans.size < 2
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]
198 unless pairing_possible
199 log_message("Floodgate: No possible human-human match found")
203 current_index = pairing_possible
204 j = [0, current_index - 2].max
205 while j < players.size
206 break if players[j].is_computer?
212 # no computer player found
213 pairing_indexes << current_index << current_index+1
215 # a comupter player found
216 pairing_indexes << current_index << j
220 pair << players.delete_at(pairing_indexes.max)
221 pair << players.delete_at(pairing_indexes.min)
222 start_game_shuffle(pair)
225 while (players.size >= 2) do
226 pair = players.shift(2)
227 start_game_shuffle(pair)
233 def get_human_indexes(players)
235 for i in 0..(players.size-1)
236 ret << i if players[i].is_human?
242 class Randomize < Pairing
245 log_message("Floodgate: Randomize... before")
248 log_message("Floodgate: Randomized after")
253 class SortByRate < Pairing
256 log_message("Floodgate: Ordered by rate")
257 players.sort! {|a,b| a.rate <=> b.rate} # decendent order
262 class SortByRateWithRandomness < Pairing
263 def initialize(rand1, rand2, desc=false)
265 @rand1, @rand2 = rand1, rand2
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]
281 class Swiss < Pairing
285 log_message("Floodgate: players are small enough to skip Swiss pairing: %d" % [players.size])
289 path = ShogiServer::League::Floodgate.history_file_path(players.first.game_name)
290 history = ShogiServer::League::Floodgate::History.factory(path)
294 winners = players.find_all {|pl| history.last_win?(pl.player_id)}
296 rest = players - winners
298 log_message("Floodgate: Ordering %d winners..." % [winners.size])
299 sbrwr_winners = SortByRateWithRandomness.new(800, 2500, true)
300 sbrwr_winners.match(winners)
302 log_message("Floodgate: Ordering the rest (%d)..." % [rest.size])
303 sbrwr_losers = SortByRateWithRandomness.new(200, 400, true)
304 sbrwr_losers.match(rest)
307 [winners, rest].each do |group|
308 group.each {|pl| players << pl}
313 class DeletePlayerAtRandom < Pairing
316 return if less_than_one?(players)
318 log_message("Floodgate: Deleted %s at random" % [one.name])
324 class DeletePlayerAtRandomExcept < Pairing
325 def initialize(except)
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)
339 class DeleteMostPlayingPlayer < Pairing
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])
349 class DeleteLeastRatePlayer < Pairing
352 one = players.min_by {|a| a.rate}
353 log_message("Floodgate: Deleted the least rate player %s (%d)" % [one.name, one.rate])
359 class ExcludeSacrifice < Pairing
360 attr_reader :sacrifice
362 # @sacrifice a player id to be eliminated
363 def initialize(sacrifice)
365 @sacrifice = sacrifice || "gps500+e293220e3f8a3e59f79f6b0efffaa931"
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}
378 end # class ExcludeSacrifice
380 class ExcludeSacrificeGps500 < ExcludeSacrifice
382 super("gps500+e293220e3f8a3e59f79f6b0efffaa931")
386 class MakeEven < Pairing
389 return if players.size.even?
390 log_message("Floodgate: There are odd players (%d). Deleting one of them..." %
392 DeletePlayerAtRandom.new.match(players)
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.
402 class LeastDiff < Pairing
403 def random_match(players)
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)
414 def estimate_rate(player, history)
415 player.estimated_rate = 2150 # default value
418 log_message("Floodgate: Without game history, estimated %s's rate: %d" % [player.name, player.estimated_rate])
422 g = history.last_valid_game(player.player_id)
424 log_message("Floodgate: Without any valid games in history, estimated %s's rate: %d" % [player.name, player.estimated_rate])
430 case player.player_id
432 opponent_id = g[:loser]
435 opponent_id = g[:winner]
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])
443 opponent_name = opponent_id.split("+")[0]
444 p = $league.find(opponent_name)
446 log_message("Floodgate: No active opponent found. Estimated %s's rate: %d" % [player.name, player.estimated_rate])
452 opponent_rate = p.rate
453 elsif p.estimated_rate != 0
454 opponent_rate = p.estimated_rate
457 if opponent_rate != 0
458 player.estimated_rate = opponent_rate + (win ? 200 : -200)
461 log_message("Floodgate: Estimated %s's rate: %d" % [player.name, player.estimated_rate])
464 # Return a player's rate based on its actual rate or estimated rate.
466 def get_player_rate(player, history)
469 elsif player.estimated_rate != 0
470 return player.estimated_rate
472 estimate_rate(player, history)
473 return player.estimated_rate
477 def calculate_diff_with_penalty(players, history)
479 players.each_slice(2) do |pair|
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
493 pairs.each do |p1,p2|
496 (history.last_opponent(p1.player_id) == p2.player_id ||
497 history.last_opponent(p2.player_id) == p1.player_id))
502 if p1.is_human? && p2.is_human?
506 # 2.3 a match with likely kin players
507 if (p1.player_id[0..6] == p2.player_id[0..6])
509 elsif (p1.player_id[0..3] == p2.player_id[0..3])
517 # Total combinations of possible games among n players
518 # nC2 * (n-2)C2 * ... * 2C2 / (n/2)!
519 def total_posibilities(n)
526 ret *= ::ShogiServer::nCk(i,2)
529 ret /= ::ShogiServer::factorial(n/2)
536 log_message("Floodgate: players are small enough to skip LeastDiff pairing: %d" % [players.size])
540 # Reset estimated rate
541 players.each {|p| p.estimated_rate = 0}
545 path = ShogiServer::League::Floodgate.history_file_path(players.first.game_name)
546 history = ShogiServer::League::Floodgate::History.factory(path)
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])
553 m = random_match(players)
555 scores << calculate_diff_with_penalty(m, history)
559 #scores.each_with_index do |s,i|
561 # print s, ": ", matches[i].map{|p| p.name}.join(", "), "\n"
564 # Select a match of the least score
566 min_score = scores.first
567 scores.each_with_index do |s,i|
573 log_message("Floodgate: the least score %d (%d per game) [%s]" % [min_score, min_score/players.size*2, scores.join(" ")])
575 players.replace(matches[min_index])
579 # This pairing method excludes unrated players
581 class ExcludeUnratedPlayers < Pairing
586 log_message("Floodgate: Deleting unrated players...")
587 players.delete_if{|a| a.rate == 0}
590 end # class ExcludeUnratedPlayers