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

   1 from __future__ import print_function
   2 import sys
   3 from ortools.constraint_solver import pywrapcp
   4
   5
   6 num_groups = 2  # NOTE: 2 is hard-coded in some places.
   7 num_teams_per_group = 6
   8 num_teams = num_teams_per_group * num_teams_per_group
   9 num_rounds = (num_teams_per_group * (num_teams_per_group - 1)) // 2
  10 num_matches = num_rounds * num_groups
  11
  12 def excitedness_weight(match_idx):
  13   field = match_idx % num_groups
  14   match_order = match_idx // num_groups
  15   if field == 0:
  16     return match_order + 5
  17   else:
  18     return match_order
  19
  20 def team_name(team_idx):
  21   if team_idx < num_teams_per_group:
  22     return "A%d" % (team_idx)
  23   else:
  24     return "B%d" % (team_idx - num_teams_per_group)
  25
  26 solver = pywrapcp.Solver("schedule_games")
  27
  28 # Create match variables.
  29 matchnums = []
  30 for match_idx in range(num_matches):
  31   matchnums.append(solver.IntVar(0, num_matches - 1, "matchnum(%i)" % (match_idx)))
  32 solver.Add(solver.AllDifferent(matchnums));
  33
  34 # Create list of matches.
  35 match_num = 0
  36 excitedness = []
  37 home_teams_for_match_num = []
  38 away_teams_for_match_num = []
  39 for group in range(num_groups):
  40   for team_idx_1 in range(num_teams_per_group):
  41     for team_idx_2 in range(num_teams_per_group):
  42       if team_idx_2 > team_idx_1:
  43         real_team_idx_1 = team_idx_1 + num_teams_per_group * group
  44         real_team_idx_2 = team_idx_2 + num_teams_per_group * group
  45         home_teams_for_match_num.append(real_team_idx_1)
  46         away_teams_for_match_num.append(real_team_idx_2)
  47         if team_idx_2 - team_idx_1 == 1:
  48           excitedness.append(5)
  49         elif team_idx_2 - team_idx_1 == 2:
  50           excitedness.append(2)
  51         else:
  52           excitedness.append(0)
  53         print("matchnum %2d: %2d vs. %2d, excited: %d" % (match_num, real_team_idx_1, real_team_idx_2, excitedness[match_num]))
  54         match_num = match_num + 1
  55
  56 # Create match variables.
  57 home_teams = []
  58 away_teams = []
  59 for match_idx in range(num_matches):
  60   home_teams.append(solver.IntVar(0, num_teams - 1, "home_team_on_match(%i)" % (match_idx)))
  61   away_teams.append(solver.IntVar(0, num_teams - 1, "away_team_on_match(%i)" % (match_idx)))
  62 matches_flat = home_teams + away_teams
  63
  64 for match_num in range(num_matches):
  65   solver.Add(home_teams[match_num] == solver.Element(home_teams_for_match_num, matchnums[match_num]))
  66   solver.Add(away_teams[match_num] == solver.Element(away_teams_for_match_num, matchnums[match_num]))
  67
  68 # Fields always play opposing groups (FIXME?)
  69 for round_idx in range(num_rounds):
  70   solver.Add((matchnums[round_idx * 2 + 0] >= num_rounds) != (matchnums[round_idx * 2 + 1] >= num_rounds))
  71
  72 # A team can never play on the same field at the same time
  73 #for match_idx in range(num_rounds):
  74 #  solver.Add(home_teams[match_idx * 2 + 0] != home_teams[match_idx * 2 + 1])
  75 #  solver.Add(home_teams[match_idx * 2 + 0] != away_teams[match_idx * 2 + 1])
  76 #  solver.Add(away_teams[match_idx * 2 + 0] != home_teams[match_idx * 2 + 1])
  77 #  solver.Add(away_teams[match_idx * 2 + 0] != away_teams[match_idx * 2 + 1])
  78
  79 plays_in_round = {}
  80 for team_idx in range(num_teams):
  81   plays_in_round[team_idx] = {}
  82   for round_idx in range(num_rounds):
  83     plays_in_round[team_idx][round_idx] = (
  84         (home_teams[round_idx * 2 + 0] == team_idx) +
  85         (home_teams[round_idx * 2 + 1] == team_idx) +
  86         (away_teams[round_idx * 2 + 0] == team_idx) +
  87         (away_teams[round_idx * 2 + 1] == team_idx))
  88
  89 # A team can never play two matches in a row
  90 for round_idx in range(num_rounds - 1):
  91   for team_idx in range(num_teams):
  92     solver.Add(plays_in_round[team_idx][round_idx] + plays_in_round[team_idx][round_idx + 1] <= 1)
  93
  94 # More waiting time is good
  95 tired_matches = []
  96 for round_idx in range(num_rounds - 2):
  97   for team_idx in range(num_teams):
  98     tired = plays_in_round[team_idx][round_idx] + plays_in_round[team_idx][round_idx + 2] >= 2
  99     tired_matches.append(tired)
 100 sum_tiredness = solver.Sum(tired_matches)
 101
 102 # Double-tired is not cool
 103 for round_idx in range(num_rounds - 4):
 104   for team_idx in range(num_teams):
 105     #doubletired = plays_in_round[team_idx][round_idx] + plays_in_round[team_idx][round_idx + 2] + plays_in_round[team_idx][round_idx + 4] >= 3
 106     #tired_matches.append(doubletired * 100)
 107     solver.Add(plays_in_round[team_idx][round_idx] + plays_in_round[team_idx][round_idx + 2] + plays_in_round[team_idx][round_idx + 4] < 3)
 108
 109
 110 ## TFK can not play the first two matches
 111 solver.Add(home_teams[0] != 0)
 112 solver.Add(away_teams[0] != 0)
 113 solver.Add(home_teams[1] != 0)
 114 solver.Add(away_teams[1] != 0)
 115 solver.Add(home_teams[2] != 0)
 116 solver.Add(away_teams[2] != 0)
 117 solver.Add(home_teams[3] != 0)
 118 solver.Add(away_teams[3] != 0)
 119
 120 # Group finals come last, and on the stream field.
 121 solver.Add((matchnums[num_matches - 2] == 0) + (matchnums[num_matches - 2] == num_rounds) >= 1)
 122 solver.Add((matchnums[num_matches - 4] == 0) + (matchnums[num_matches - 4] == num_rounds) >= 1)
 123
 124 # Put the more exciting games later, and on stream fields
 125 sum_excitedness = solver.Sum([(matchnums[match_num].IndexOf(excitedness) * excitedness_weight(match_num)) for match_num in range(num_matches)])
 126 objective = solver.Maximize(sum_excitedness - 10 * sum_tiredness, 1)
 127
 128 db = solver.Phase(matchnums, solver.CHOOSE_FIRST_UNBOUND,
 129                   solver.ASSIGN_MIN_VALUE)
 130 search_log = solver.SearchLog(1000000, objective)
 131 #global_limit = solver.TimeLimit(1000)
 132 global_limit = solver.TimeLimit(100000000)
 133
 134 solver.NewSearch(db, [search_log, objective, global_limit])
 135 while solver.NextSolution():
 136   recently_played_0 = [False for team_idx in range(num_teams)]
 137   recently_played_1 = [False for team_idx in range(num_teams)]
 138   recently_played_2 = [False for team_idx in range(num_teams)]
 139   recently_played_3 = [False for team_idx in range(num_teams)]
 140   for i in range(num_matches // num_groups):
 141     recently_played_4 = [False for team_idx in range(num_teams)]
 142     print("%2d. " % (i), end='')
 143     for g in range(num_groups):
 144       j = i * num_groups + g
 145       home_team = home_teams[j].Value()
 146       away_team = away_teams[j].Value()
 147       matchnum = matchnums[j].Value()
 148
 149       tiredness = 0
 150       if recently_played_2[home_team]:
 151         tiredness = tiredness + 1
 152         if recently_played_0[home_team]:
 153           tiredness = tiredness + 100
 154       if recently_played_2[away_team]:
 155         tiredness = tiredness + 1
 156         if recently_played_0[away_team]:
 157           tiredness = tiredness + 100
 158       recently_played_4[home_team] = True
 159       recently_played_4[away_team] = True
 160
 161       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='')
 162     print()
 163     recently_played_0 = recently_played_1
 164     recently_played_1 = recently_played_2
 165     recently_played_2 = recently_played_3
 166     recently_played_3 = recently_played_4
 167
 168   print()
 169 solver.EndSearch()