OSDN Git Service

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