git.sesse.net Git - ultimatescore/blob - roster/twofields_sat.py

   1 #! /usr/bin/python3
   2 from __future__ import print_function
   3 import sys
   4 import time
   5 from ortools.sat.python import cp_model
   6
   7
   8
   9 num_groups = 2  # NOTE: 2 is hard-coded in some places.
  10 num_teams_per_group = 6
  11 num_teams = num_teams_per_group * num_groups
  12 num_rounds = (num_teams_per_group * (num_teams_per_group - 1)) // 2
  13 num_matches = num_rounds * num_groups
  14
  15 class SolutionPrinterWithObjective(cp_model.CpSolverSolutionCallback):
  16   def __init__(self, home_teams, away_teams, matchnums, objective):
  17     cp_model.CpSolverSolutionCallback.__init__(self)
  18     self.__solution_count = 0
  19     self.__start_time = time.time()
  20     self.__home_teams = home_teams
  21     self.__away_teams = away_teams
  22     self.__matchnums = matchnums
  23     self.__objective = objective
  24
  25   def OnSolutionCallback(self):
  26     current_time = time.time()
  27     self.__solution_count += 1
  28     print('Solution %i, time = %f s, objective = %d' %
  29           (self.__solution_count, current_time - self.__start_time, self.Value(self.__objective)))
  30     num_times_on_stream = [0 for team_idx in range(num_teams)]
  31     num_times_tired = [0 for team_idx in range(num_teams)]
  32     recently_played_0 = [False for team_idx in range(num_teams)]
  33     recently_played_1 = [False for team_idx in range(num_teams)]
  34     recently_played_2 = [False for team_idx in range(num_teams)]
  35     recently_played_3 = [False for team_idx in range(num_teams)]
  36     for i in range(num_matches // num_groups):
  37       recently_played_4 = [False for team_idx in range(num_teams)]
  38       print("%2d. " % (i), end='')
  39       for g in range(num_groups):
  40         j = i * num_groups + g
  41         home_team = self.Value(self.__home_teams[j])
  42         away_team = self.Value(self.__away_teams[j])
  43         matchnum = self.Value(self.__matchnums[j])
  44
  45         if g == 0:
  46           num_times_on_stream[home_team] = num_times_on_stream[home_team] + 1
  47           num_times_on_stream[away_team] = num_times_on_stream[away_team] + 1
  48
  49         tiredness = 0
  50         if recently_played_2[home_team]:
  51           tiredness = tiredness + 1
  52           num_times_tired[home_team] = num_times_tired[home_team] + 1
  53           if recently_played_0[home_team]:
  54             tiredness = tiredness + 100
  55         if recently_played_2[away_team]:
  56           tiredness = tiredness + 1
  57           num_times_tired[away_team] = num_times_tired[away_team] + 1
  58           if recently_played_0[away_team]:
  59             tiredness = tiredness + 100
  60         recently_played_4[home_team] = True
  61         recently_played_4[away_team] = True
  62
  63         print("%s vs. %s  (matchnum %2d, excitedness %d*%2d, tiredness %3d)  " % (team_name(home_team), team_name(away_team), matchnum, excitedness[matchnum], excitedness_weight(j), tiredness), end='')
  64       print()
  65       recently_played_0 = recently_played_1
  66       recently_played_1 = recently_played_2
  67       recently_played_2 = recently_played_3
  68       recently_played_3 = recently_played_4
  69     print()
  70     print("Number of times on stream: ", end='')
  71     print(", ".join(["%s %d" % (team_name(team_idx), num_times_on_stream[team_idx]) for team_idx in range(num_teams)]))
  72     print("Number of times tired: ", end='')
  73     print(", ".join(["%s %d" % (team_name(team_idx), num_times_tired[team_idx]) for team_idx in range(num_teams)]))
  74     print("Stream opponents for non-top-teams:")
  75     for team_idx in (2, 3, 4, 5, 8, 9, 10, 11):
  76       opp = []
  77       for i in range(num_matches // num_groups):
  78         home_team = self.Value(self.__home_teams[i * 2])
  79         away_team = self.Value(self.__away_teams[i * 2])
  80         mark = ""
  81         if abs(home_team - away_team) == 1:
  82           mark = "*"
  83         if team_idx == home_team:
  84           opp.append(team_name(away_team) + mark)
  85         if team_idx == away_team:
  86           opp.append(team_name(home_team) + mark)
  87       print("  %s: %s" % (team_name(team_idx), ", ".join(sorted(opp))))
  88
  89
  90 def excitedness_weight(match_idx):
  91   field = match_idx % num_groups
  92   match_order = match_idx // num_groups
  93   if field == 0:
  94     return match_order + 5
  95   else:
  96     return match_order
  97
  98 def team_name(team_idx):
  99   if team_idx < num_teams_per_group:
 100     return "A%d" % (team_idx)
 101   else:
 102     return "B%d" % (team_idx - num_teams_per_group)
 103
 104 model = cp_model.CpModel()
 105
 106 # Create match variables.
 107 matchnums = []
 108 for match_idx in range(num_matches):
 109   matchnums.append(model.NewIntVar(0, num_matches - 1, "matchnum(%i)" % (match_idx)))
 110 model.AddAllDifferent(matchnums)
 111
 112 # Create list of matches.
 113 match_idx = 0
 114 excitedness = []
 115 home_teams_for_match_num = []
 116 away_teams_for_match_num = []
 117 for group in range(num_groups):
 118   for team_idx_1 in range(num_teams_per_group):
 119     for team_idx_2 in range(num_teams_per_group):
 120       if team_idx_2 > team_idx_1:
 121         real_team_idx_1 = team_idx_1 + num_teams_per_group * group
 122         real_team_idx_2 = team_idx_2 + num_teams_per_group * group
 123         home_teams_for_match_num.append(real_team_idx_1)
 124         away_teams_for_match_num.append(real_team_idx_2)
 125         if team_idx_2 - team_idx_1 == 1:
 126           excitedness.append(5)
 127         elif team_idx_2 - team_idx_1 == 2:
 128           excitedness.append(2)
 129         else:
 130           excitedness.append(0)
 131         print("matchnum %2d: %2d vs. %2d, excited: %d" % (match_idx, real_team_idx_1, real_team_idx_2, excitedness[match_idx]))
 132         match_idx = match_idx + 1
 133
 134 # Create match variables.
 135 home_teams = []
 136 away_teams = []
 137 for match_idx in range(num_matches):
 138   home_teams.append(model.NewIntVar(0, num_teams - 1, "home_team_match%i" % (match_idx)))
 139   away_teams.append(model.NewIntVar(0, num_teams - 1, "away_team_match%i" % (match_idx)))
 140 matches_flat = home_teams + away_teams
 141
 142 for match_idx in range(num_matches):
 143   model.AddElement(matchnums[match_idx], home_teams_for_match_num, home_teams[match_idx])
 144   model.AddElement(matchnums[match_idx], away_teams_for_match_num, away_teams[match_idx])
 145
 146 # Boolean variables
 147 home_team_in_match_x_is_y = [[
 148       model.NewBoolVar('home_team_in_match_%d_is_%d' % (match_idx, team_idx)) for team_idx in range(num_teams)
 149 ] for match_idx in range(num_matches)]
 150
 151 away_team_in_match_x_is_y = [[
 152       model.NewBoolVar('away_team_in_match_%d_is_%d' % (match_idx, team_idx)) for team_idx in range(num_teams)
 153 ] for match_idx in range(num_matches)]
 154
 155 match_x_has_num_y = [[
 156       model.NewBoolVar('match_%d_has_number_%d' % (a, b)) for a in range(num_matches)
 157 ] for b in range(num_matches)]
 158
 159 for match_idx in range(num_matches):
 160   model.AddMapDomain(matchnums[match_idx], match_x_has_num_y[match_idx])
 161   model.AddMapDomain(home_teams[match_idx], home_team_in_match_x_is_y[match_idx])
 162   model.AddMapDomain(away_teams[match_idx], away_team_in_match_x_is_y[match_idx])
 163
 164 # Fields always play opposing groups (FIXME?)
 165 for round_idx in range(num_rounds):
 166   field_0_is_group_0 = model.NewBoolVar('field_0_round_%d_is_group_0' % (round_idx))
 167   model.AddMaxEquality(field_0_is_group_0, [match_x_has_num_y[round_idx * 2 + 0][match_idx] for match_idx in range(num_rounds)])
 168   field_1_is_group_0 = model.NewBoolVar('field_1_round_%d_is_group_0' % (round_idx))
 169   model.AddMaxEquality(field_1_is_group_0, [match_x_has_num_y[round_idx * 2 + 1][match_idx] for match_idx in range(num_rounds)])
 170   model.AddBoolXOr([field_0_is_group_0, field_1_is_group_0])
 171
 172 # A team can never play on the same field at the same time
 173 #for team_idx in range(num_teams):
 174 #  for round_idx in range(num_rounds):
 175 #    plays_on_field_0 = model.NewBoolVar('plays_on_field0_t%d_r%d' % (team_idx, round_idx))
 176 #    model.AddMaxEquality(plays_on_field_0, [
 177 #        home_team_in_match_x_is_y[round_idx * 2 + 0][team_idx],
 178 #        away_team_in_match_x_is_y[round_idx * 2 + 0][team_idx]])
 179 #    plays_on_field_1 = model.NewBoolVar('plays_on_field1_t%d_r%d' % (team_idx, round_idx))
 180 #    model.AddMaxEquality(plays_on_field_1, [
 181 #        home_team_in_match_x_is_y[round_idx * 2 + 1][team_idx],
 182 #        away_team_in_match_x_is_y[round_idx * 2 + 1][team_idx]])
 183 #    model.AddBoolOr([plays_on_field_0.Not(), plays_on_field_1.Not()])
 184
 185 plays_in_round = {}
 186 for team_idx in range(num_teams):
 187   plays_in_round[team_idx] = {}
 188   for round_idx in range(num_rounds):
 189     plays_in_round[team_idx][round_idx] = model.NewBoolVar('plays_in_round_t%d_r%d' % (team_idx, round_idx))
 190     model.AddMaxEquality(plays_in_round[team_idx][round_idx], [
 191         home_team_in_match_x_is_y[round_idx * 2 + 0][team_idx],
 192         home_team_in_match_x_is_y[round_idx * 2 + 1][team_idx],
 193         away_team_in_match_x_is_y[round_idx * 2 + 0][team_idx],
 194         away_team_in_match_x_is_y[round_idx * 2 + 1][team_idx]])
 195
 196 # A team can never play two matches in a row
 197 for round_idx in range(num_rounds - 1):
 198   for team_idx in range(num_teams):
 199     model.AddBoolOr([plays_in_round[team_idx][round_idx].Not(), plays_in_round[team_idx][round_idx + 1].Not()])
 200
 201 # Also, double-tired is not cool
 202 #for round_idx in range(num_rounds - 4):
 203 #  for team_idx in range(num_teams):
 204 #    model.AddBoolOr([plays_in_round[team_idx][round_idx].Not(), plays_in_round[team_idx][round_idx + 2].Not(), plays_in_round[team_idx][round_idx + 4].Not()])
 205 #
 206 # More waiting time is good
 207 #tired_matches = []
 208 #for round_idx in range(num_rounds - 2):
 209 #  for team_idx in range(num_teams):
 210 #    tired = model.NewBoolVar('team_%d_is_tired_in_round_%d' % (team_idx, round_idx))
 211 #    model.AddMinEquality(tired, [plays_in_round[team_idx][round_idx], plays_in_round[team_idx][round_idx + 2]])
 212 #    tired_matches.append(tired)
 213 #sum_tiredness = sum(tired_matches)
 214
 215 # Each team gets play-rest-play exactly once, for fairness
 216 for team_idx in range(num_teams):
 217   tired_matches = []
 218   for round_idx in range(num_rounds - 2):
 219     tired = model.NewBoolVar('team_%d_is_tired_in_round_%d' % (team_idx, round_idx))
 220     model.AddMinEquality(tired, [plays_in_round[team_idx][round_idx], plays_in_round[team_idx][round_idx + 2]])
 221     tired_matches.append(tired)
 222   model.Add(sum(tired_matches) <= 1)
 223 sum_tiredness = 0
 224
 225 # TFK can not play the first two matches
 226 model.AddBoolAnd([plays_in_round[0][0].Not(), plays_in_round[0][1].Not()])
 227
 228 # Group finals come last, and on the stream field.
 229 model.AddBoolOr([match_x_has_num_y[num_matches - 2][0], match_x_has_num_y[num_matches - 2][num_rounds]])
 230 model.AddBoolOr([match_x_has_num_y[num_matches - 4][0], match_x_has_num_y[num_matches - 4][num_rounds]])
 231
 232 # Count how many times each team has been on stream.
 233 stream_penalties = []
 234 for team_idx in range(num_teams):
 235   playing_on_stream = []
 236   for round_idx in range(num_rounds):
 237     s = model.NewBoolVar('team_%d_plays_on_stream_in_round_%d' % (team_idx, round_idx))
 238     model.AddMaxEquality(s, [
 239         home_team_in_match_x_is_y[round_idx * 2 + 0][team_idx],
 240         away_team_in_match_x_is_y[round_idx * 2 + 0][team_idx]])
 241     playing_on_stream.append(s)
 242   times_on_stream_this_team = sum(playing_on_stream)
 243   model.Add(times_on_stream_this_team >= 1)
 244
 245   times_stream_var = model.NewIntVar(0, num_teams_per_group, "team_%d_stream_count" % (team_idx))
 246   model.Add(times_stream_var == times_on_stream_this_team)
 247   #model.Add(times_on_stream_this_team <= 4)
 248
 249   is_n_times_on_stream = [
 250     model.NewBoolVar('team_%d_is_%d_times_on_stream' % (team_idx, i)) for i in range(num_teams_per_group)
 251   ]
 252   model.AddMapDomain(times_stream_var, is_n_times_on_stream)
 253   stream_penalties.append(is_n_times_on_stream[1] * -50)
 254   stream_penalties.append(is_n_times_on_stream[4] * -10)
 255   stream_penalties.append(is_n_times_on_stream[5] * -50)
 256
 257 # Make sure each team has at least one exciting match on stream.
 258 #for team_idx in range(team_idx):
 259 #  stream_matches_for_this_team = []
 260 #  for round_idx in range(num_rounds):
 261 #    stream_matches_for_this_team.append(home_team_in_match_x_is_y[round_idx * 2 + 0][team_idx] * excitedness_weight(round_idx * 2 + 0))
 262 #    stream_matches_for_this_team.append(away_team_in_match_x_is_y[round_idx * 2 + 0][team_idx] * excitedness_weight(round_idx * 2 + 0))
 263
 264 # Put the more exciting games later, and on stream fields
 265 excitement = []
 266 for round_idx in range(num_rounds):
 267   for match_idx in range(match_idx):
 268     excitement.append(match_x_has_num_y[round_idx * 2 + 0][match_idx] * excitedness[match_idx] * excitedness_weight(round_idx * 2 + 0))
 269     excitement.append(match_x_has_num_y[round_idx * 2 + 1][match_idx] * excitedness[match_idx] * excitedness_weight(round_idx * 2 + 1))
 270 sum_excitement = sum(excitement)
 271 objective = sum_excitement - 30 * sum_tiredness + 3 * sum(stream_penalties)
 272 model.Maximize(objective)
 273
 274 solver = cp_model.CpSolver()
 275 solution_printer = SolutionPrinterWithObjective(home_teams, away_teams, matchnums, objective)
 276 status = solver.SolveWithSolutionCallback(model, solution_printer)