OSDN Git Service

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