Hello.
I have thought about this question for a while: Is it possible to use algorithms to yield good teams? Since I had some time over this weekend, I decided toprocrastinate test this idea out.
https://github.com/AntonXue/teamgen/
Algorithm TL;DR:
With whatlack of experience I had doing competitive Pokemon, I picked one of the teams that was generated and proceeded to ladder with it:
It doesn't actually seem too bad until you start playing with it. Maybe my sets are just bad :)
Metagross-Mega @ Metagrossite
Ability: Clear Body
EVs: 252 Atk / 4 SpD / 252 Spe
Jolly Nature
- Meteor Mash
- Zen Headbutt
- Ice Punch
- Hammer Arm
Mega Metagross is the king of the ranking algorithm. By sheer virtue of its typing, attack, speed, and versatility, it nets favorable matchups against a great deal of OU and BL. Meteor Mash and Zen Headbutt are staples on Mega Metagross. Because the rest of the team already has two Electric-type users, Ice Punch was chosen to increase overall coverage against Pokemon such as Landorus-T, so that Salamence could have an easier time sweeping provided that it got the opportunity to. The last move slot was a toss-up between Bullet Punch, Hammer Arm, and Earthquake, and frankly I feel that Bullet Punch sometimes helps pick off Pokemon such as Pheromosa and Mimikyu better, but Hammer Arm makes you less dead-weight against Heatran. Interestingly enough, a lot of Heatrans seem to assume that you pack Hammer Arm / Earthquake, so it is possible to, at least at first, to perform well against Heatran teams with Bullet Punch over Hammer Arm.
Salamence @ Flyinium Z
Ability: Moxie
EVs: 252 Atk / 4 Def / 252 Spe
Jolly Nature
- Fly
- Outrage
- Dragon Dance
- Earthquake
Salamence's primary negative matchups are bulky steels and waters, in general netting at least neutral on most things and +1 on things that it can set up on and proceed to kill for a +2 Atk / +1 Spe. The moveset is extremely standard and predictable, although I toyed with the idea of running Choice Scarf at one point. However, this is not B/W. Interestingly enough, Mega Metagross / Salamence / Xirkutree forms a fairly formidable offensive core simply due to their excellent offensive stats and attack typing diversity. Metagross checks Ice, Rock, and Grass for Salamence and Xurkitree; Salamence can set up on Grass and some Fire-types, while Xirkutree can blow past Water with ease. Obviously Ferrothorn is a problem, but a combination of +1 SSSS and Hammer Arm can usually dent it enough to allow Xirkutree to accumulate a +1 Beast Boost later in the match.
Xurkitree @ Choice Scarf
Ability: Beast Boost
EVs: 4 Def / 252 SpA / 252 Spe
Timid Nature
IVs: 0 Atk
- Volt Switch
- Thunderbolt
- Energy Ball
- Hidden Power [Ice]
Scarf Xurkitree has a nice surprise factor and solid sweeping potential, bar against things like Pheromosa. Having Tapu Koko in this slot is probably nicer due to its access to U-Turn, but I was curious to see how well I could do with Xurkitree here. Xurkitree nets clean kills on a lot of Water-types, and being a less common threat, it is somehow able to net more kills than it should with Energy Ball on Ground-type switch-ins. Xurkitree, Salamence, and Greninja-A tend to be my win conditions during matches, as I tend to play Mega Metagross fairly aggressively to wall break for the remainder of the team. As pointed out earlier, Xurkitree covers a much-needed Electric-type offense against bulky waters and Flying-types in general. After the opposing team is sufficiently weakened (i.e. no longer has Chansey or an Electric resist / immunity), Xurkitree can quickly nab +1's for a sweep. Sometimes.
Greninja-Ash @ Choice Specs
Ability: Battle Bond
EVs: 252 SpA / 4 SpD / 252 Spe
Timid Nature
- Water Shuriken
- Hydro Pump
- Dark Pulse
- U-turn
Greninja-A has lots of favorable matchups since it is able to outspeed and nuke a lot of things. I suspect that the reason it was generated was to act as a Fire and Pheromosa check, and indeed that is what it tends to do. OHKOing the likes of Pheromosa and other frail, boosted Pokemon with Water Shuriken is greatly appreciated. Clicking Dark Pulse and Hydro Pump in general breaks a lot of switch-ins for the rest of the team. Lastly, U-Turn along with Xurkitree and Rotom-W's Volt Switch forms a decent Volt-Turn core, and with the rest of the team largely consisting of heavy wall breakers, getting into Ash form is generally easy with lots of weakened Pokemon on the opponent's team.
Heatran @ Leftovers
Ability: Flash Fire
EVs: 4 HP / 252 SpA / 252 Spe
Timid Nature
IVs: 0 Atk
- Stealth Rock
- Magma Storm
- Taunt
- Earth Power
I don't know why this thing was generated, but I guess the reason was because I rated it at a +2 against Ferrothorn, and a lot of other Pokemon on the team are -1 against it, so perhaps this was done as a Ferrothorn counter. Having Stealth Rocks, which a number of the other teams did not, is also useful, as well as having offensive Fire-type coverage. Because Chansey is a big problem for a large fraction of the team, we need to try to kill it, and kill it fast, and this set reflects exactly that. Spamming Magma Storm in general is also nice since it hits lots of things hard. Lastly, Earth Power lets me OHKO other fast Heatrans that I speed tie against, and nabs solid damage against most opposing Fire-types.
Rotom-Wash @ Leftovers
Ability: Levitate
EVs: 248 HP / 240 Def / 20 SpD
Bold Nature
IVs: 0 Atk
- Volt Switch
- Hydro Pump
- Will-O-Wisp
- Pain Split
I am honestly surprised that this thing came up, but it has proven to be extremely helpful in a lot of matches where I need a more passive approach to victory. Rotom-W is a solid defensive pivot and can come in on things such as Celesteela, Landorus-T, and others, without me having to sack a Pokemon or aggressively predict around things. Furthermore, the fact that Rotom-W beats Marowak-A is greatly appreciated, which means that Rotom-W can almost always get off a Volt Switch, since Marowaks tend to not like switching in. In addition, Rotom-W is the first line of defense against Rain, after which I'm generally kind of fucked because Kingdra outspeeds Xurkitree in rain.
I have thought about this question for a while: Is it possible to use algorithms to yield good teams? Since I had some time over this weekend, I decided to
https://github.com/AntonXue/teamgen/
Algorithm TL;DR:
- Rank how well Pokemon A does against Pokemon B in a matchup and encode this into a massive matrix: https://github.com/AntonXue/teamgen/blob/master/matchup.txt.
- Scan through the matrix and try to make a team of 6 Pokemon that minimizes "bad" matchups.
- Return top k (k = 5 at the moment) results.
- The notion of a "good" or "bad" matchup is not well-defined, and does not consider specific sets a Pokemon may run, only in general situations.
- The matrix is generated based only on my limited knowledge of the current OU Metagame, and some results don't intuitively make sense.
- Likelihood of me making a typo when making the matrix is very, very high.
- Matrix (68 x 68) is hard-coded to only account for all the Pokemon currently on Smogon's OU and BL list, and thus yields limited selection.
- Algorithm does not consider type synergy, playstyle, etc. Yet.
- Team generation is most likely a "computationally hard" problem.
There are 68 Pokemon in OU / BL that are considered as possible candidates on a team that is generated. These Pokemon are listed pseudo-alphabetically (OU ends at index 51, BL begins at index 52) in a giant table: https://github.com/AntonXue/teamgen/blob/master/index.txt
A pairwise matchup matrix was then created with lots of tedious effort. The goal is to approximately capture how well Pokemon A performs against B in a matchup situation in general. The performance is ranked as follows:
Because the matchup matrix is a semi-sparse matrix, this means that in order to not drive myself crazy trying to enter every value of the matrix, I only enter some values, and values that are not entered are assumed to be 0. Here is the index: https://github.com/AntonXue/teamgen/blob/master/index.txt, here is the matrix: https://github.com/AntonXue/teamgen/blob/master/matchup.txt and here is how you read it so you can check to see if your favorite Pokemon is entered incorrectly :)
With a team of 6 members, an analysis pass done against the matchup matrix can be seen as going through each of the team members' entry in the matrix, then superimposing a sum of performance against all Pokemon. So if your team is P1 ... P6, and you're facing opponent Q, the value for how well your team handles Q can be seen as: rank(P1, Q) + rank(P2, Q) + ... + rank(P6, Q). Note that these threat values can be weighted by each Pokemon's usage statistic.
As I said, because there are a massive number of teams to consider (68 choose 6 = 109,453,344), and because I don't feel like waiting several minutes for the program to finish generating, the algorithm attempts to prune the search space faster using several heuristics:
A pairwise matchup matrix was then created with lots of tedious effort. The goal is to approximately capture how well Pokemon A performs against B in a matchup situation in general. The performance is ranked as follows:
- [-2] Strongly struggles against (e.g. Ferrothorn strongly struggles against Volcarona).
- [-1] Moderately struggles against (e.g. Marowak-A moderately struggles against Tapu Fini).
- [0] Neutral (e.g. Excadrill neutral against Venusaur-M).
- [1] Moderately favorable against (e.g. Greninja moderately favorable against Tyranitar).
- [2] Strongly favorable against (e.g. Magnezone strongly favorable against Skarmory).
Because the matchup matrix is a semi-sparse matrix, this means that in order to not drive myself crazy trying to enter every value of the matrix, I only enter some values, and values that are not entered are assumed to be 0. Here is the index: https://github.com/AntonXue/teamgen/blob/master/index.txt, here is the matrix: https://github.com/AntonXue/teamgen/blob/master/matchup.txt and here is how you read it so you can check to see if your favorite Pokemon is entered incorrectly :)
- Every Pokemon in the index can be represented as a 3-tuple of (index value, name, usage)
- Every entry in the matrix begins with the index value, separated by a comma, then a long list of values separated by colons. The value before the first comma denotes the index of a Pokemon, every value after is a pair of opponent Pokemon index and matchup performance.
- For instance, the 3rd line of the file can be read as follows: Buzzwole (index 2) has a -1 matchup against Mega Alakazam, a 1 matchup against Beedrill, a -1 matchup against Celesteela, etc.
With a team of 6 members, an analysis pass done against the matchup matrix can be seen as going through each of the team members' entry in the matrix, then superimposing a sum of performance against all Pokemon. So if your team is P1 ... P6, and you're facing opponent Q, the value for how well your team handles Q can be seen as: rank(P1, Q) + rank(P2, Q) + ... + rank(P6, Q). Note that these threat values can be weighted by each Pokemon's usage statistic.
As I said, because there are a massive number of teams to consider (68 choose 6 = 109,453,344), and because I don't feel like waiting several minutes for the program to finish generating, the algorithm attempts to prune the search space faster using several heuristics:
- First generate only teams with 3 member combinations during round 1. At the moment we only keep track of 10 teams, but since this is the first round, the number could be higher, in retrospect.
- In round 2, take these 10 teams from round 1, and generate a combination of the three remaining members for each, keeping track of the top 10 results.
- Index Pokemon by 0 so we can literally use them as matrix lookups, which should be pretty fast.
- Negative sums: Perhaps the most simple (and the one implemented right now) notion for scoring a team is checking how "negative" a team's overall matchup score against the matrix is. The reason why only negative values are considered is because it shows weaknesses in coverage and ignores overly redundant coverage -- for instance having 4 checks against Ferrothorn probably means your team is not weak to Ferrothorn.
- Negative spikes: Maybe some generated team has a net -1 weakness to Gyarados. This could simply mean that 3 of your members are weak to it, 2 is strong against it, and the remaining 1 is neutral. In this case, is Gyarados really still a threat to your team? Perhaps these values can be discarded, and we need to only consider more extreme cases, such as teams that are -2, or perhaps -3 weak to certain Pokemon, and attempt to get results that minimize these "spikes".
- Weighted values: The same as the above two, except scaled by usage statistics.
The analysis process went through a few refinements, but in the latest run these, were the top 5 results: https://github.com/AntonXue/teamgen/blob/master/res1.txt. Translated into text, these are as follows:
The Toxapex Problem
The Toxapex Problem
- Because the algorithm only cares about matchup performance, wall breakers and stall based Pokemon tend to rank higher since their unfavorable matchups tend to be concentrated around the few other wall breakers / nimble fast sweepers.
- Some lesser used Pokemon (Zapdos and Dragonite) occasionally bubble towards on to top teams in the rankings since they just happen to have good matchups against a few "holes" in otherwise very common combinations (Metagross, Greninja, etc)
- Mega Metagross and Mega Charizard X appear many times by virtue of having lots of good matchups. Probably :)
With what
It doesn't actually seem too bad until you start playing with it. Maybe my sets are just bad :)
Metagross-Mega @ Metagrossite
Ability: Clear Body
EVs: 252 Atk / 4 SpD / 252 Spe
Jolly Nature
- Meteor Mash
- Zen Headbutt
- Ice Punch
- Hammer Arm
Mega Metagross is the king of the ranking algorithm. By sheer virtue of its typing, attack, speed, and versatility, it nets favorable matchups against a great deal of OU and BL. Meteor Mash and Zen Headbutt are staples on Mega Metagross. Because the rest of the team already has two Electric-type users, Ice Punch was chosen to increase overall coverage against Pokemon such as Landorus-T, so that Salamence could have an easier time sweeping provided that it got the opportunity to. The last move slot was a toss-up between Bullet Punch, Hammer Arm, and Earthquake, and frankly I feel that Bullet Punch sometimes helps pick off Pokemon such as Pheromosa and Mimikyu better, but Hammer Arm makes you less dead-weight against Heatran. Interestingly enough, a lot of Heatrans seem to assume that you pack Hammer Arm / Earthquake, so it is possible to, at least at first, to perform well against Heatran teams with Bullet Punch over Hammer Arm.
Salamence @ Flyinium Z
Ability: Moxie
EVs: 252 Atk / 4 Def / 252 Spe
Jolly Nature
- Fly
- Outrage
- Dragon Dance
- Earthquake
Salamence's primary negative matchups are bulky steels and waters, in general netting at least neutral on most things and +1 on things that it can set up on and proceed to kill for a +2 Atk / +1 Spe. The moveset is extremely standard and predictable, although I toyed with the idea of running Choice Scarf at one point. However, this is not B/W. Interestingly enough, Mega Metagross / Salamence / Xirkutree forms a fairly formidable offensive core simply due to their excellent offensive stats and attack typing diversity. Metagross checks Ice, Rock, and Grass for Salamence and Xurkitree; Salamence can set up on Grass and some Fire-types, while Xirkutree can blow past Water with ease. Obviously Ferrothorn is a problem, but a combination of +1 SSSS and Hammer Arm can usually dent it enough to allow Xirkutree to accumulate a +1 Beast Boost later in the match.
Xurkitree @ Choice Scarf
Ability: Beast Boost
EVs: 4 Def / 252 SpA / 252 Spe
Timid Nature
IVs: 0 Atk
- Volt Switch
- Thunderbolt
- Energy Ball
- Hidden Power [Ice]
Scarf Xurkitree has a nice surprise factor and solid sweeping potential, bar against things like Pheromosa. Having Tapu Koko in this slot is probably nicer due to its access to U-Turn, but I was curious to see how well I could do with Xurkitree here. Xurkitree nets clean kills on a lot of Water-types, and being a less common threat, it is somehow able to net more kills than it should with Energy Ball on Ground-type switch-ins. Xurkitree, Salamence, and Greninja-A tend to be my win conditions during matches, as I tend to play Mega Metagross fairly aggressively to wall break for the remainder of the team. As pointed out earlier, Xurkitree covers a much-needed Electric-type offense against bulky waters and Flying-types in general. After the opposing team is sufficiently weakened (i.e. no longer has Chansey or an Electric resist / immunity), Xurkitree can quickly nab +1's for a sweep. Sometimes.
Greninja-Ash @ Choice Specs
Ability: Battle Bond
EVs: 252 SpA / 4 SpD / 252 Spe
Timid Nature
- Water Shuriken
- Hydro Pump
- Dark Pulse
- U-turn
Greninja-A has lots of favorable matchups since it is able to outspeed and nuke a lot of things. I suspect that the reason it was generated was to act as a Fire and Pheromosa check, and indeed that is what it tends to do. OHKOing the likes of Pheromosa and other frail, boosted Pokemon with Water Shuriken is greatly appreciated. Clicking Dark Pulse and Hydro Pump in general breaks a lot of switch-ins for the rest of the team. Lastly, U-Turn along with Xurkitree and Rotom-W's Volt Switch forms a decent Volt-Turn core, and with the rest of the team largely consisting of heavy wall breakers, getting into Ash form is generally easy with lots of weakened Pokemon on the opponent's team.
Heatran @ Leftovers
Ability: Flash Fire
EVs: 4 HP / 252 SpA / 252 Spe
Timid Nature
IVs: 0 Atk
- Stealth Rock
- Magma Storm
- Taunt
- Earth Power
I don't know why this thing was generated, but I guess the reason was because I rated it at a +2 against Ferrothorn, and a lot of other Pokemon on the team are -1 against it, so perhaps this was done as a Ferrothorn counter. Having Stealth Rocks, which a number of the other teams did not, is also useful, as well as having offensive Fire-type coverage. Because Chansey is a big problem for a large fraction of the team, we need to try to kill it, and kill it fast, and this set reflects exactly that. Spamming Magma Storm in general is also nice since it hits lots of things hard. Lastly, Earth Power lets me OHKO other fast Heatrans that I speed tie against, and nabs solid damage against most opposing Fire-types.
Rotom-Wash @ Leftovers
Ability: Levitate
EVs: 248 HP / 240 Def / 20 SpD
Bold Nature
IVs: 0 Atk
- Volt Switch
- Hydro Pump
- Will-O-Wisp
- Pain Split
I am honestly surprised that this thing came up, but it has proven to be extremely helpful in a lot of matches where I need a more passive approach to victory. Rotom-W is a solid defensive pivot and can come in on things such as Celesteela, Landorus-T, and others, without me having to sack a Pokemon or aggressively predict around things. Furthermore, the fact that Rotom-W beats Marowak-A is greatly appreciated, which means that Rotom-W can almost always get off a Volt Switch, since Marowaks tend to not like switching in. In addition, Rotom-W is the first line of defense against Rain, after which I'm generally kind of fucked because Kingdra outspeeds Xurkitree in rain.
Because of the way the algorithm runs analyses, it is able to report a "threat list", which is highly useless most of the time. Here is what it claims to be a threat to this team:
- Mega Charizard X
- Greninja
- Greninja-A
- Gyarados-M
- Rotom-W
- Volcarona
- Zapdos
- Mega Slowbro
Metagross-Mega @ Metagrossite
Ability: Clear Body
EVs: 252 Atk / 4 SpD / 252 Spe
Jolly Nature
- Meteor Mash
- Zen Headbutt
- Ice Punch
- Hammer Arm
Salamence @ Flyinium Z
Ability: Moxie
EVs: 252 Atk / 4 Def / 252 Spe
Jolly Nature
- Fly
- Outrage
- Dragon Dance
- Earthquake
Xurkitree @ Choice Scarf
Ability: Beast Boost
EVs: 4 Def / 252 SpA / 252 Spe
Timid Nature
IVs: 0 Atk
- Volt Switch
- Thunderbolt
- Energy Ball
- Hidden Power [Ice]
Greninja-Ash @ Choice Specs
Ability: Battle Bond
EVs: 252 SpA / 4 SpD / 252 Spe
Timid Nature
- Water Shuriken
- Hydro Pump
- Dark Pulse
- U-turn
Heatran @ Leftovers
Ability: Flash Fire
EVs: 4 HP / 252 SpA / 252 Spe
Timid Nature
IVs: 0 Atk
- Stealth Rock
- Magma Storm
- Taunt
- Earth Power
Rotom-Wash @ Leftovers
Ability: Levitate
EVs: 248 HP / 240 Def / 20 SpD
Bold Nature
IVs: 0 Atk
- Volt Switch
- Hydro Pump
- Will-O-Wisp
- Pain Split
Ability: Clear Body
EVs: 252 Atk / 4 SpD / 252 Spe
Jolly Nature
- Meteor Mash
- Zen Headbutt
- Ice Punch
- Hammer Arm
Salamence @ Flyinium Z
Ability: Moxie
EVs: 252 Atk / 4 Def / 252 Spe
Jolly Nature
- Fly
- Outrage
- Dragon Dance
- Earthquake
Xurkitree @ Choice Scarf
Ability: Beast Boost
EVs: 4 Def / 252 SpA / 252 Spe
Timid Nature
IVs: 0 Atk
- Volt Switch
- Thunderbolt
- Energy Ball
- Hidden Power [Ice]
Greninja-Ash @ Choice Specs
Ability: Battle Bond
EVs: 252 SpA / 4 SpD / 252 Spe
Timid Nature
- Water Shuriken
- Hydro Pump
- Dark Pulse
- U-turn
Heatran @ Leftovers
Ability: Flash Fire
EVs: 4 HP / 252 SpA / 252 Spe
Timid Nature
IVs: 0 Atk
- Stealth Rock
- Magma Storm
- Taunt
- Earth Power
Rotom-Wash @ Leftovers
Ability: Levitate
EVs: 248 HP / 240 Def / 20 SpD
Bold Nature
IVs: 0 Atk
- Volt Switch
- Hydro Pump
- Will-O-Wisp
- Pain Split
This iteration of team generation is very primitive and is full of obvious problems. There are some other approaches (among many others) that I've toyed around with:
Larger Matrix
This is probably the simplest solution to refining this method. By introducing more elements in the matrix to account for different move types (e.g. Offensive Heatran and Defensive Heatran get separate entries), this will likely yield better solutions, since it allows greater customization over sets and accurate reporting as such.
Densest k=6 Subset of Complete Synergy Graph
The idea here is even more computationally time-consuming than the larger matrix one. Similar to the idea where we consider more sets for each Pokemon, the goal here is that we consider an inter-team synergy. Say we take a complete graph where each node is a Pokemon + moveset, and every line between nodes has a value that denotes how well two Pokemon synergize with each other (e.g. Ferrothorn + Toxapex have good synergy, Toxapex + every other offensive wall breakers don't have fantastic synergy). To prevent illegal combinations such as multiple Megas or less-preferred situations such as multiple Z-move users, it's a simple matter of assigning a large negative sentinel value for each line between two such conflicting Pokemon nodes. Anyways, the goal here would be to find a set of 6 nodes whose lines between each other sum up to the highest value.
However the data set here is massive, and only increases for each additional unique moveset you consider. A further downside of this algorithm is that it does not account for type synergy, and will as with before, likely favor clusters of pure stall and wall breaker combinations, which tend to have excellent offensive synergy and defensive synergy (typing here is not guaranteed), amongst themselves.
Offensive + Defensive Analysis
It's probably salient to also have heuristics, or perhaps separate generators that try to account for type coverage both offensively and defensively. This can go hand-in-hand with the large matrix and dense subset method, allowing us to filter out bad combinations after those results give us some results (say, top 100?).
Throw Every Analysis Pass We Got At It!
Team building is most likely a computationally hard problem, because there are far too many factors at play: The simpler the model the faster results can be obtained, but at the trade off of accuracy and actual effectiveness. The more complex the model, the better the results, but it would take a long ass time. The most reasonable model is probably to have, as hinted at above, to have multiple passes that apply one heuristic on top of another (role synergy, type synergy, etc). This is future work to be done.
Computationally Hard?
If you have a formal proof for this I'd love to hear it.
Future Stuff
If anyone is interested in theorymoning with me or possibly helping around with whatever data entry we might need in the future, please leave me a PM :)
Maybe we can continue this more in-depth in the future.
Larger Matrix
This is probably the simplest solution to refining this method. By introducing more elements in the matrix to account for different move types (e.g. Offensive Heatran and Defensive Heatran get separate entries), this will likely yield better solutions, since it allows greater customization over sets and accurate reporting as such.
Densest k=6 Subset of Complete Synergy Graph
The idea here is even more computationally time-consuming than the larger matrix one. Similar to the idea where we consider more sets for each Pokemon, the goal here is that we consider an inter-team synergy. Say we take a complete graph where each node is a Pokemon + moveset, and every line between nodes has a value that denotes how well two Pokemon synergize with each other (e.g. Ferrothorn + Toxapex have good synergy, Toxapex + every other offensive wall breakers don't have fantastic synergy). To prevent illegal combinations such as multiple Megas or less-preferred situations such as multiple Z-move users, it's a simple matter of assigning a large negative sentinel value for each line between two such conflicting Pokemon nodes. Anyways, the goal here would be to find a set of 6 nodes whose lines between each other sum up to the highest value.
However the data set here is massive, and only increases for each additional unique moveset you consider. A further downside of this algorithm is that it does not account for type synergy, and will as with before, likely favor clusters of pure stall and wall breaker combinations, which tend to have excellent offensive synergy and defensive synergy (typing here is not guaranteed), amongst themselves.
Offensive + Defensive Analysis
It's probably salient to also have heuristics, or perhaps separate generators that try to account for type coverage both offensively and defensively. This can go hand-in-hand with the large matrix and dense subset method, allowing us to filter out bad combinations after those results give us some results (say, top 100?).
Throw Every Analysis Pass We Got At It!
Team building is most likely a computationally hard problem, because there are far too many factors at play: The simpler the model the faster results can be obtained, but at the trade off of accuracy and actual effectiveness. The more complex the model, the better the results, but it would take a long ass time. The most reasonable model is probably to have, as hinted at above, to have multiple passes that apply one heuristic on top of another (role synergy, type synergy, etc). This is future work to be done.
Computationally Hard?
If you have a formal proof for this I'd love to hear it.
Future Stuff
If anyone is interested in theorymoning with me or possibly helping around with whatever data entry we might need in the future, please leave me a PM :)
Maybe we can continue this more in-depth in the future.