OSDN Git Service

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