OSDN Git Service

[shogi-server] Enhance capability of Floodgate configuration file
[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-2012 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(options)
28         return least_diff_pairing(options)
29       end
30
31       def sort_by_rate_with_randomness(options)
32         return [LogPlayers.new,
33                 ExcludeSacrifice.new(options[:sacrifice]),
34                 MakeEven.new,
35                 SortByRateWithRandomness.new(1200, 2400),
36                 StartGameWithoutHumans.new]
37       end
38
39       def random_pairing(options)
40         return [LogPlayers.new,
41                 ExcludeSacrifice.new(options[:sacrifice]),
42                 MakeEven.new,
43                 Randomize.new,
44                 StartGameWithoutHumans.new]
45       end
46
47       def swiss_pairing(options)
48         return [LogPlayers.new,
49                 ExcludeSacrifice.new(options[:sacrifice]),
50                 MakeEven.new,
51                 Swiss.new,
52                 StartGameWithoutHumans.new]
53       end
54
55       def least_diff_pairing(options)
56         return [LogPlayers.new,
57                 ExcludeSacrifice.new(options[:sacrifice]),
58                 MakeEven.new,
59                 LeastDiff.new,
60                 StartGameWithoutHumans.new]
61       end
62
63       def floodgate_zyunisen(options)
64         return [LogPlayers.new,
65                 ExcludeUnratedPlayers.new,
66                 ExcludeSacrifice.new(options[:sacrifice]),
67                 MakeEven.new,
68                 LeastDiff.new,
69                 StartGameWithoutHumans.new]
70       end
71
72       def match(players, logics, options)
73         logics.inject(players) do |result, item|
74           item.set_options(options)
75           item.match(result)
76           result
77         end
78       end
79     end # class << self
80
81     def initialize
82       @options = {}
83     end
84
85     def set_options(options)
86       @options.merge!(options)
87     end
88
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.
92     #
93     def match(players)
94       # to be implemented
95       log_message("Floodgate: %s" % [self.class.to_s])
96     end
97
98     def include_newbie?(players)
99       return players.find{|a| a.rate == 0} == nil ? false : true
100     end
101
102     def less_than_one?(players)
103       if players.size < 1
104         log_warning("Floodgate: There should be at least one player.")
105         return true
106       else
107         return false
108       end
109     end
110
111     def log_players(players)
112       str_array = players.map do |one|
113         if block_given?
114           yield one
115         else
116           one.name
117         end
118       end
119       if str_array.empty?
120         log_message("Floodgate: [Players] Nobody found.")
121       else
122         log_message("Floodgate: [Players] %s." % [str_array.join(", ")])
123       end
124     end
125   end # Pairing
126
127
128   class LogPlayers < Pairing
129     def match(players)
130       super
131       log_players(players)
132     end
133   end
134
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])
138       p1.sente = true
139       p2.sente = false
140       board = Board.new(@options)
141       board.initial
142       Game.new(p1.game_name, p1, p2, board)
143     end
144
145     def start_game_shuffle(pair)
146       pair.shuffle!
147       start_game(pair.first, pair.last)
148     end
149   end
150
151   class StartGame < AbstractStartGame
152     def match(players)
153       super
154       if players.size < 2
155         log_message("Floodgate: There are less than two players: %d" % [players.size])
156         return
157       end
158       if players.size.odd?
159         log_warning("Floodgate: There are odd players (%d). %s will not be matched." % 
160                     [players.size, players.last.name])
161       end
162
163       log_players(players)
164       while (players.size >= 2) do
165         pair = players.shift(2)
166         start_game_shuffle(pair)
167       end
168     end
169   end
170
171   # This tries to avoid a human-human match
172   #
173   class StartGameWithoutHumans < AbstractStartGame
174     def match(players)
175       super
176       log_players(players)
177       if players.size < 2
178         log_message("Floodgate: There are less than two players: %d" % [players.size])
179         return
180       elsif players.size == 2
181         start_game_shuffle(players)
182         return
183       end
184
185       loop do 
186         humans = get_human_indexes(players)
187         log_message("Floodgate: There are (still) %d humans." % [humans.size])
188         break if humans.size < 2
189
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]
195             break
196           end
197         end
198         unless pairing_possible
199           log_message("Floodgate: No possible human-human match found")
200           break
201         end
202
203         current_index = pairing_possible
204         j = [0, current_index - 2].max
205         while j < players.size
206           break if players[j].is_computer?
207           j += 1
208         end
209
210         pairing_indexes = []
211         if j == players.size 
212           # no computer player found
213           pairing_indexes << current_index << current_index+1
214         else
215           # a comupter player found
216           pairing_indexes << current_index << j
217         end
218
219         pair = []
220         pair << players.delete_at(pairing_indexes.max)
221         pair << players.delete_at(pairing_indexes.min)
222         start_game_shuffle(pair)
223       end # loop
224
225       while (players.size >= 2) do
226         pair = players.shift(2)
227         start_game_shuffle(pair)
228       end
229     end
230
231     private
232
233     def get_human_indexes(players)
234       ret = []
235       for i in 0..(players.size-1)
236         ret << i if players[i].is_human?
237       end
238       return ret
239     end
240   end
241
242   class Randomize < Pairing
243     def match(players)
244       super
245       log_message("Floodgate: Randomize... before")
246       log_players(players)
247       players.shuffle!
248       log_message("Floodgate: Randomized after")
249       log_players(players)
250     end
251   end # RadomPairing
252
253   class SortByRate < Pairing
254     def match(players)
255       super
256       log_message("Floodgate: Ordered by rate")
257       players.sort! {|a,b| a.rate <=> b.rate} # decendent order
258       log_players(players)
259     end
260   end
261
262   class SortByRateWithRandomness < Pairing
263     def initialize(rand1, rand2, desc=false)
264       super()
265       @rand1, @rand2 = rand1, rand2
266       @desc = desc
267     end
268
269     def match(players)
270       super(players)
271       cur_rate = Hash.new
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]
277       end
278     end
279   end
280
281   class Swiss < Pairing
282     def match(players)
283       super
284       if players.size < 3
285         log_message("Floodgate: players are small enough to skip Swiss pairing: %d" % [players.size])
286         return
287       end
288
289       path = ShogiServer::League::Floodgate.history_file_path(players.first.game_name)
290       history = ShogiServer::League::Floodgate::History.factory(path)
291
292       winners = []
293       if history
294         winners = players.find_all {|pl| history.last_win?(pl.player_id)}
295       end
296       rest = players - winners
297
298       log_message("Floodgate: Ordering %d winners..." % [winners.size])
299       sbrwr_winners = SortByRateWithRandomness.new(800, 2500, true)
300       sbrwr_winners.match(winners)
301
302       log_message("Floodgate: Ordering the rest (%d)..." % [rest.size])
303       sbrwr_losers = SortByRateWithRandomness.new(200, 400, true)
304       sbrwr_losers.match(rest)
305
306       players.clear
307       [winners, rest].each do |group|
308         group.each {|pl| players << pl}
309       end
310     end
311   end
312
313   class DeletePlayerAtRandom < Pairing
314     def match(players)
315       super
316       return if less_than_one?(players)
317       one = players.sample
318       log_message("Floodgate: Deleted %s at random" % [one.name])
319       players.delete(one)
320       log_players(players)
321     end
322   end
323
324   class DeletePlayerAtRandomExcept < Pairing
325     def initialize(except)
326       super()
327       @except = except
328     end
329
330     def match(players)
331       super
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)
336     end
337   end
338   
339   class DeleteMostPlayingPlayer < Pairing
340     def match(players)
341       super
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])
344       players.delete(one)
345       log_players(players)
346     end
347   end
348
349   class DeleteLeastRatePlayer < Pairing
350     def match(players)
351       super
352       one = players.min_by {|a| a.rate}
353       log_message("Floodgate: Deleted the least rate player %s (%d)" % [one.name, one.rate])
354       players.delete(one)
355       log_players(players)
356     end
357   end
358
359   class ExcludeSacrifice < Pairing
360     attr_reader :sacrifice
361
362     # @sacrifice a player id to be eliminated
363     def initialize(sacrifice)
364       super()
365       @sacrifice = sacrifice || "gps500+e293220e3f8a3e59f79f6b0efffaa931"
366     end
367
368     def match(players)
369       super
370       if @sacrifice && 
371          players.size.odd? && 
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}
375          log_players(players)
376       end
377     end
378   end # class ExcludeSacrifice
379
380   class ExcludeSacrificeGps500 < ExcludeSacrifice
381     def initialize
382       super("gps500+e293220e3f8a3e59f79f6b0efffaa931")
383     end
384   end
385
386   class MakeEven < Pairing
387     def match(players)
388       super
389       return if players.size.even?
390       log_message("Floodgate: There are odd players (%d). Deleting one of them..." % 
391                   [players.size])
392       DeletePlayerAtRandom.new.match(players)
393     end
394   end
395
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.
401   #
402   class LeastDiff < Pairing
403     def random_match(players)
404       players.shuffle
405     end
406
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)
413     #
414     def estimate_rate(player, history)
415       player.estimated_rate = 2150 # default value
416
417       unless history
418         log_message("Floodgate: Without game history, estimated %s's rate: %d" % [player.name, player.estimated_rate])
419         return
420       end
421
422       g = history.last_valid_game(player.player_id)
423       unless g
424         log_message("Floodgate: Without any valid games in history, estimated %s's rate: %d" % [player.name, player.estimated_rate])
425         return
426       end
427
428       opponent_id = nil
429       win         = true
430       case player.player_id
431       when g[:winner]
432         opponent_id = g[:loser]
433         win = true
434       when g[:loser]
435         opponent_id = g[:winner]
436         win = false
437       else
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])
440         return
441       end
442
443       opponent_name = opponent_id.split("+")[0]
444       p = $league.find(opponent_name)
445       unless p
446         log_message("Floodgate: No active opponent found. Estimated %s's rate: %d" % [player.name, player.estimated_rate])
447         return
448       end
449
450       opponent_rate = 0
451       if p.rate != 0
452         opponent_rate = p.rate
453       elsif p.estimated_rate != 0
454         opponent_rate = p.estimated_rate
455       end
456
457       if opponent_rate != 0
458         player.estimated_rate = opponent_rate + (win ? 200 : -200)
459       end
460
461       log_message("Floodgate: Estimated %s's rate: %d" % [player.name, player.estimated_rate])
462     end
463
464     # Return a player's rate based on its actual rate or estimated rate.
465     #
466     def get_player_rate(player, history)
467       if player.rate != 0
468         return player.rate
469       elsif player.estimated_rate != 0
470         return player.estimated_rate 
471       else
472         estimate_rate(player, history)
473         return player.estimated_rate
474       end
475     end
476
477     def calculate_diff_with_penalty(players, history)
478       pairs = []
479       players.each_slice(2) do |pair|
480         if pair.size == 2
481           pairs << pair
482         end
483       end
484
485       ret = 0
486
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
490       end
491
492       # 2. Penalties
493       pairs.each do |p1,p2|
494         # 2.1. same match
495         if (history &&
496             (history.last_opponent(p1.player_id) == p2.player_id ||
497              history.last_opponent(p2.player_id) == p1.player_id))
498           ret += 400
499         end
500
501         # 2.2 Human vs Human
502         if p1.is_human? && p2.is_human?
503           ret += 800
504         end
505
506         # 2.3 a match with likely kin players
507         if (p1.player_id[0..6] == p2.player_id[0..6])
508           ret += 800
509         elsif (p1.player_id[0..3] == p2.player_id[0..3])
510           ret += 400
511         end
512       end
513
514       ret
515     end
516
517     def match(players)
518       super
519       if players.size < 3
520         log_message("Floodgate: players are small enough to skip LeastDiff pairing: %d" % [players.size])
521         return players
522       end
523
524       # Reset estimated rate
525       players.each {|p| p.estimated_rate = 0}
526
527       # 10 trials
528       matches = []
529       scores  = []
530       path = ShogiServer::League::Floodgate.history_file_path(players.first.game_name)
531       history = ShogiServer::League::Floodgate::History.factory(path)
532       10.times do 
533         m = random_match(players)
534         matches << m
535         scores << calculate_diff_with_penalty(m, history)
536       end
537
538       # Debug
539       #scores.each_with_index do |s,i|
540       #  puts
541       #  print s, ": ", matches[i].map{|p| p.name}.join(", "), "\n"
542       #end
543
544       # Select a match of the least score
545       min_index = 0
546       min_score = scores.first
547       scores.each_with_index do |s,i|
548         if s < min_score
549           min_index = i
550           min_score = s
551         end
552       end
553       log_message("Floodgate: the least score %d (%d per game) [%s]" % [min_score, min_score/players.size*2, scores.join(" ")])
554
555       players.replace(matches[min_index])
556     end
557   end
558
559   # This pairing method excludes unrated players
560   #
561   class ExcludeUnratedPlayers < Pairing
562
563     def match(players)
564       super
565
566       log_message("Floodgate: Deleting unrated players...")
567       players.delete_if{|a| a.rate == 0}
568       log_players(players)
569     end
570   end # class ExcludeUnratedPlayers
571
572 end # ShogiServer