Optimizing MOBA Free Hero Rotations

by Philippe Olivier
Created 2023-06-08

Multiplayer Online Battle Arenas (MOBAs) are a genre of video games where two teams of heroes face each other on a battlefield. Popular MOBAs include League of Legends, Dota 2, and Heroes of the Storm. Players can typically choose to play one of a hundred or more heroes. Most heroes are initially locked, but can be unlocked with real or in-game money. In-game money is typically earned by playing games and completing quests. To give players a taste of the various heroes, a few of them are available to everyone on a rotation basis each week. Each hero has a particular role, such as tank, healer, etc.

We are going to consider how the generation of free rotation compositions could be optimized for the game Heroes of the Storm. There are 90 heroes: each has one of the 6 possible roles (Bruiser, Healer, Melee Assassin, Ranged Assassin, Support, and Tank), and they are each from one of the 5 possible universes (Diablo, Nexus, Overwatch, Starcraft, and Warcraft). There are 14 heroes per rotation.

The quests for this game are:

Play 3 games as a Melee or Ranged Assassin Hero
Play 3 games as a Bruiser or Tank Hero
Play 3 games as a Healer or Support Hero
Play 2 games as a Diablo Hero
Play 2 games as an Overwatch or Nexus Hero
Play 2 games as a Starcraft Hero
Play 2 games as a Warcraft Hero

Let's modelize this problem. In each rotation, we will want heroes of every role and universe, so that all the potential quests can be completed with heroes from the free rotation. The same hero should not appear in nearby rotations, and rotations should be different from each other (we want each rotation to be as diverse as possible).

1. Data

The player can choose from among 90 heroes, each of which is defined by a universe and a role.

  HEROES = {
      "Abathur": {"Role": "Support", "Universe": "Starcraft"},
      "Alarak": {"Role": "Melee Assassin", "Universe": "Starcraft"},
      "Alexstrasza": {"Role": "Healer", "Universe": "Warcraft"},
      "Ana": {"Role": "Healer", "Universe": "Overwatch"},
      "Anduin": {"Role": "Healer", "Universe": "Warcraft"},
      "Anub'arak": {"Role": "Tank", "Universe": "Warcraft"},
      "Artanis": {"Role": "Bruiser", "Universe": "Starcraft"},
      "Arthas": {"Role": "Tank", "Universe": "Warcraft"},
      "Auriel": {"Role": "Healer", "Universe": "Diablo"},
      "Azmodan": {"Role": "Ranged Assassin", "Universe": "Diablo"},
      "Blaze": {"Role": "Tank", "Universe": "Starcraft"},
      "Brightwing": {"Role": "Healer", "Universe": "Warcraft"},
      "Cassia": {"Role": "Ranged Assassin", "Universe": "Diablo"},
      "Chen": {"Role": "Bruiser", "Universe": "Warcraft"},
      "Cho": {"Role": "Tank", "Universe": "Warcraft"},
      "Chromie": {"Role": "Ranged Assassin", "Universe": "Warcraft"},
      "D.Va": {"Role": "Bruiser", "Universe": "Overwatch"},
      "Deathwing": {"Role": "Bruiser", "Universe": "Warcraft"},
      "Deckard": {"Role": "Healer", "Universe": "Diablo"},
      "Dehaka": {"Role": "Bruiser", "Universe": "Starcraft"},
      "Diablo": {"Role": "Tank", "Universe": "Diablo"},
      "E.T.C.": {"Role": "Tank", "Universe": "Warcraft"},
      "Falstad": {"Role": "Ranged Assassin", "Universe": "Warcraft"},
      "Fenix": {"Role": "Ranged Assassin", "Universe": "Starcraft"},
      "Gall": {"Role": "Ranged Assassin", "Universe": "Warcraft"},
      "Garrosh": {"Role": "Tank", "Universe": "Warcraft"},
      "Gazlowe": {"Role": "Bruiser", "Universe": "Warcraft"},
      "Genji": {"Role": "Ranged Assassin", "Universe": "Overwatch"},
      "Greymane": {"Role": "Ranged Assassin", "Universe": "Warcraft"},
      "Gul'dan": {"Role": "Ranged Assassin", "Universe": "Warcraft"},
      "Hanzo": {"Role": "Ranged Assassin", "Universe": "Overwatch"},
      "Hogger": {"Role": "Bruiser", "Universe": "Warcraft"},
      "Illidan": {"Role": "Melee Assassin", "Universe": "Warcraft"},
      "Imperius": {"Role": "Bruiser", "Universe": "Diablo"},
      "Jaina": {"Role": "Ranged Assassin", "Universe": "Warcraft"},
      "Johanna": {"Role": "Tank", "Universe": "Diablo"},
      "Junkrat": {"Role": "Ranged Assassin", "Universe": "Overwatch"},
      "Kael'thas": {"Role": "Ranged Assassin", "Universe": "Warcraft"},
      "Kel'Thuzad": {"Role": "Ranged Assassin", "Universe": "Warcraft"},
      "Kerrigan": {"Role": "Melee Assassin", "Universe": "Starcraft"},
      "Kharazim": {"Role": "Healer", "Universe": "Diablo"},
      "Leoric": {"Role": "Bruiser", "Universe": "Diablo"},
      "Li Li": {"Role": "Healer", "Universe": "Warcraft"},
      "Li-Ming": {"Role": "Ranged Assassin", "Universe": "Diablo"},
      "Lt. Morales": {"Role": "Healer", "Universe": "Starcraft"},
      "Lúcio": {"Role": "Healer", "Universe": "Overwatch"},
      "Lunara": {"Role": "Ranged Assassin", "Universe": "Warcraft"},
      "Maiev": {"Role": "Melee Assassin", "Universe": "Warcraft"},
      "Mal'Ganis": {"Role": "Tank", "Universe": "Warcraft"},
      "Malfurion": {"Role": "Healer", "Universe": "Warcraft"},
      "Malthael": {"Role": "Bruiser", "Universe": "Diablo"},
      "Medivh": {"Role": "Support", "Universe": "Warcraft"},
      "Mei": {"Role": "Tank", "Universe": "Overwatch"},
      "Mephisto": {"Role": "Ranged Assassin", "Universe": "Diablo"},
      "Muradin": {"Role": "Tank", "Universe": "Warcraft"},
      "Murky": {"Role": "Melee Assassin", "Universe": "Warcraft"},
      "Nazeebo": {"Role": "Ranged Assassin", "Universe": "Diablo"},
      "Nova": {"Role": "Ranged Assassin", "Universe": "Starcraft"},
      "Orphea": {"Role": "Ranged Assassin", "Universe": "Nexus"},
      "Probius": {"Role": "Ranged Assassin", "Universe": "Starcraft"},
      "Qhira": {"Role": "Melee Assassin", "Universe": "Nexus"},
      "Ragnaros": {"Role": "Bruiser", "Universe": "Warcraft"},
      "Raynor": {"Role": "Ranged Assassin", "Universe": "Starcraft"},
      "Rehgar": {"Role": "Healer", "Universe": "Warcraft"},
      "Rexxar": {"Role": "Bruiser", "Universe": "Warcraft"},
      "Samuro": {"Role": "Melee Assassin", "Universe": "Warcraft"},
      "Sgt. Hammer": {"Role": "Ranged Assassin", "Universe": "Starcraft"},
      "Sonya": {"Role": "Bruiser", "Universe": "Diablo"},
      "Stitches": {"Role": "Tank", "Universe": "Warcraft"},
      "Stukov": {"Role": "Healer", "Universe": "Starcraft"},
      "Sylvanas": {"Role": "Ranged Assassin", "Universe": "Warcraft"},
      "Tassadar": {"Role": "Ranged Assassin", "Universe": "Starcraft"},
      "The Butcher": {"Role": "Melee Assassin", "Universe": "Diablo"},
      "The Lost Vikings": {"Role": "Support", "Universe": "Nexus"},
      "Thrall": {"Role": "Bruiser", "Universe": "Warcraft"},
      "Tracer": {"Role": "Ranged Assassin", "Universe": "Overwatch"},
      "Tychus": {"Role": "Ranged Assassin", "Universe": "Starcraft"},
      "Tyrael": {"Role": "Tank", "Universe": "Diablo"},
      "Tyrande": {"Role": "Healer", "Universe": "Warcraft"},
      "Uther": {"Role": "Healer", "Universe": "Warcraft"},
      "Valeera": {"Role": "Melee Assassin", "Universe": "Warcraft"},
      "Valla": {"Role": "Ranged Assassin", "Universe": "Diablo"},
      "Varian": {"Role": "Bruiser", "Universe": "Warcraft"},
      "Whitemane": {"Role": "Healer", "Universe": "Warcraft"},
      "Xul": {"Role": "Bruiser", "Universe": "Diablo"},
      "Yrel": {"Role": "Bruiser", "Universe": "Warcraft"},
      "Zagara": {"Role": "Ranged Assassin", "Universe": "Starcraft"},
      "Zarya": {"Role": "Support", "Universe": "Overwatch"},
      "Zeratul": {"Role": "Melee Assassin", "Universe": "Starcraft"},
      "Zul'jin": {"Role": "Ranged Assassin", "Universe": "Warcraft"}}

  UNIVERSES = (
      "Diablo",
      "Nexus",
      "Overwatch",
      "Starcraft",
      "Warcraft")

  ROLES = (
      "Bruiser",
      "Healer",
      "Melee Assassin",
      "Ranged Assassin",
      "Support",
      "Tank")

We put this data in 0-1 format for the model:

  # universes["Diablo"][h] == 1 if hero `h` is from the Diablo universe, 0 otherwise
  universes = {}
  for u in UNIVERSES:
      universes[u] = [1 if h["Universe"] == u else 0 for h in HEROES.values()]

  # roles["Bruiser"][h] == 1 if hero `h` is a bruiser, 0 otherwise
  roles = {}
  for r in ROLES:
      roles[r] = [1 if h["Role"] == r else 0 for h in HEROES.values()]

Since the data in a Python dictionary is naturally sorted in the order of insertion, this 0-1 mapping is consistent with the original data.

2. Parameters

The only parameter that can be specified is the number of rotations to generate. We could make the model more customizable, but we will instead choose automatic but sensible defaults.

  NUM_ROTATIONS = 20

3. Initialization

We first initialize the model:

  import math
  from ortools.sat.python import cp_model

  model = cp_model.CpModel()

We then define some constants.

  NUM_HEROES = len(HEROES)
  ROTATION_SIZE = 14

A hero can only appear once in any sequence of SPACING rotations (to make sure that a hero does not appear in rotations that are too close together):

  SPACING = math.floor(NUM_HEROES / ROTATION_SIZE) - 1  # -1 to give us a bit of leeway

We also want to make sure that rotations are as different as possible from each other. Each rotation must contain a unique set of UNIQUE heroes that are not found together in any other rotation:

  UNIQUE = 3

4. Decision variables

We have a NUM_ROTATIONS × NUM_HEROES matrix of binary decision variables, indicating which hero is selected in which rotation:

  # rotations[r][h] == 1 if hero `h` is selected in rotation `r`
  rotations = [[model.NewBoolVar(f"rotations_{r}_{h}") for h in range(NUM_HEROES)] for r in range(NUM_ROTATIONS)]

5. Constraints

We enforce the size of the rotations:

  for rotation in range(NUM_ROTATIONS):
      model.Add(cp_model.LinearExpr.Sum(rotations[rotation]) == ROTATION_SIZE)

We should expect that the number of heroes per universe and per role be balanced in each rotation. At 90 heroes and 14 heroes per rotation, here is the breakdown in the average types of heroes we should be seeing in each rotation per universe:

Universe	# Heroes Total	# Heroes/Rotation
Diablo	18	2.80
Nexus	3	0.47
Overwatch	9	1.40
Starcraft	17	2.64
Warcraft	43	6.69

And per role:

Role	# Heroes Total	# Heroes/Rotation
Bruiser	17	2.64
Healer	16	2.49
Melee Assassin	10	1.56
Ranged Assassin	30	4.67
Support	4	0.62
Tank	13	2.02

We will enforce rules stating that each rotation should have between floor(# Heroes/Rotation) and ceil(# Heroes/Rotation) heroes from every universe and every role.

  UNIVERSES_FREQ = (
    ("Diablo", 2.80),
    ("Nexus", 0.47),
    ("Overwatch", 1.40),
    ("Starcraft", 2.64),
    ("Warcraft", 6.69))

  for rotation in range(NUM_ROTATIONS):
      for universe, freq in UNIVERSES_FREQ:
          model.Add(cp_model.LinearExpr.WeightedSum(rotations[rotation], universes[universe]) >= math.floor(freq))
          model.Add(cp_model.LinearExpr.WeightedSum(rotations[rotation], universes[universe]) <= math.ceil(freq))

  ROLES_FREQ = (
    ("Bruiser", 2.64),
    ("Healer", 2.49),
    ("Melee Assassin", 1.56),
    ("Ranged Assassin", 4.67),
    ("Support", 0.62),
    ("Tank", 2.02))

  for rotation in range(NUM_ROTATIONS):
      for role, freq in ROLES_FREQ:
          model.Add(cp_model.LinearExpr.WeightedSum(rotations[rotation], roles[role]) >= math.floor(freq))
          model.Add(cp_model.LinearExpr.WeightedSum(rotations[rotation], roles[role]) <= math.ceil(freq))

A hero should not appear in nearby rotations:

  for rotation in range(NUM_ROTATIONS-SPACING):
      for hero in range(NUM_HEROES):
          model.Add(cp_model.LinearExpr.Sum([rotations[rotation+i][hero] for i in range(SPACING)]) <= 1)

Heroes should appear a similar number of times overall, i.e., between floor(NUM_ROTATIONS * ROTATION_SIZE / NUM_HEROES) and ceil(NUM_ROTATIONS * ROTATION_SIZE / NUM_HEROES).

  for hero in range(NUM_HEROES):
      model.Add(cp_model.LinearExpr.Sum([rotations[rotation][hero] for rotation in range(NUM_ROTATIONS)]) >= math.floor(NUM_ROTATIONS * ROTATION_SIZE / NUM_HEROES))
      model.Add(cp_model.LinearExpr.Sum([rotations[rotation][hero] for rotation in range(NUM_ROTATIONS)]) <= math.ceil(NUM_ROTATIONS * ROTATION_SIZE / NUM_HEROES))

Each rotation should be as unique as possible:

  for rotation1 in range(NUM_ROTATIONS-1):
      for rotation2 in range(rotation1+1, NUM_ROTATIONS):
          common_heroes = [model.NewBoolVar(f"common_heroes_{rotation1}_{rotation2}_{hero}") for hero in range(NUM_HEROES)]
          for hero in range(NUM_HEROES):
              model.AddBoolOr(rotations[rotation1][hero].Not(), rotations[rotation2][hero].Not(), common_heroes[hero])
              model.AddImplication(common_heroes[hero], rotations[rotation1][hero])
              model.AddImplication(common_heroes[hero], rotations[rotation2][hero])
          model.Add(cp_model.LinearExpr.Sum(common_heroes) <= ROTATION_SIZE - UNIQUE)

Finally, there is a special hero called "Cho'gall" that is controlled by two players (one plays Cho, the other plays Gall). We add a special constraint to ensure that these two heroes always appear together in rotations:

  NAMES = list(HEROES.keys())
  CHO_INDEX = NAMES.index("Cho")
  GALL_INDEX = NAMES.index("Gall")

  for rotation in range(NUM_ROTATIONS):
      model.Add(rotations[rotation][CHO_INDEX] == rotations[rotation][GALL_INDEX])

6. Objective

We have defined a problem without using an objective, as we consider that any solution satisfying the constraints is going to be a good solution.

7. Solving the problem

Finally, we invoke the solver and print the solution:

  solver = cp_model.CpSolver()
  status = solver.Solve(model)
  if status not in (cp_model.OPTIMAL, cp_model.FEASIBLE):
      print("No solution exists")

  for rotation in range(NUM_ROTATIONS):
      c = 0
      for hero in range(NUM_HEROES):
          if solver.Value(rotations[rotation][hero]) == 1:
              c += 1
              print(NAMES[hero], end="")
              if c < 14:
                  print(", ", end="")
      print()

For 20 rotations, we get the result:

Alexstrasza, Blaze, Dehaka, Diablo, Gazlowe, Lt. Morales, Nova, Sonya, The Lost Vikings, Thrall, Valla, Whitemane, Yrel, Zul'jin
Chen, Cho, Gall, Malthael, Muradin, Murky, Nazeebo, Probius, Raynor, Rehgar, Sgt. Hammer, Stukov, Tassadar, Tychus
Artanis, Azmodan, Cassia, Hogger, Kharazim, Li-Ming, Maiev, Mal'Ganis, Mei, Ragnaros, Rexxar, Samuro, The Butcher, Varian
Illidan, Imperius, Jaina, Johanna, Junkrat, Kael'thas, Kel'Thuzad, Leoric, Li Li, Lúcio, Medivh, Mephisto, Uther, Zarya
Abathur, Anduin, Anub'arak, Auriel, Brightwing, D.Va, Deckard, E.T.C., Falstad, Fenix, Garrosh, Gul'dan, Stitches, Tracer
Alarak, Alexstrasza, Ana, Arthas, Blaze, Chromie, Deathwing, Dehaka, Diablo, Gazlowe, Greymane, Hanzo, Lt. Morales, Valla
Chen, Cho, Gall, Kerrigan, Lunara, Malfurion, Orphea, Rehgar, The Lost Vikings, Tychus, Tyrande, Valeera, Yrel, Zeratul
Artanis, Azmodan, Cassia, Kharazim, Li-Ming, Maiev, Mal'Ganis, Muradin, Probius, Rexxar, Samuro, Stukov, The Butcher, Varian
Jaina, Junkrat, Kael'thas, Leoric, Lúcio, Malthael, Medivh, Mei, Mephisto, Murky, Nazeebo, Ragnaros, Raynor, Zul'jin
Anduin, Anub'arak, Auriel, D.Va, Deckard, E.T.C., Fenix, Garrosh, Genji, Gul'dan, Hogger, Illidan, Stitches, Tassadar
Abathur, Alarak, Ana, Arthas, Greymane, Imperius, Johanna, Kel'Thuzad, Li Li, Lt. Morales, Nova, Qhira, Xul, Zarya
Kerrigan, Lunara, Malfurion, Orphea, Sonya, Sylvanas, Thrall, Tracer, Tychus, Tyrael, Uther, Valeera, Whitemane, Zeratul
Kharazim, Li-Ming, Maiev, Mal'Ganis, Muradin, Probius, Rehgar, Rexxar, Samuro, Sgt. Hammer, The Lost Vikings, Valla, Yrel, Zagara
Azmodan, Blaze, Brightwing, Cassia, Chen, Cho, Chromie, Deathwing, Dehaka, Diablo, Falstad, Gall, Hanzo, Junkrat
Alexstrasza, Anduin, Artanis, Auriel, Gazlowe, Genji, Gul'dan, Hogger, Illidan, Lúcio, Murky, Stitches, Tyrande, Zul'jin
Abathur, Alarak, Ana, Anub'arak, Arthas, D.Va, Deckard, E.T.C., Garrosh, Greymane, Imperius, Kel'Thuzad, Nazeebo, Ragnaros
Fenix, Jaina, Johanna, Kael'thas, Leoric, Li Li, Lunara, Malfurion, Malthael, Medivh, Mei, Mephisto, The Butcher, Tychus
Kerrigan, Orphea, Qhira, Raynor, Samuro, Sgt. Hammer, Sonya, Stukov, Sylvanas, Tassadar, Tracer, Uther, Valeera, Varian
Brightwing, Cho, Deathwing, Falstad, Gall, Hanzo, Nova, Thrall, Tyrael, Whitemane, Xul, Yrel, Zagara, Zeratul
Arthas, Cassia, Chromie, Genji, Greymane, Qhira, Rexxar, Stitches, Sylvanas, Tyrael, Tyrande, Xul, Zagara, Zarya