# 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