3
$\begingroup$

Pokemon is a game where 2 players each select 6 Pokemon (a team) at the beginning of the game without knowing the other player's team. Every Pokemon has one or two types. Every type is either weak, neutral or strong against every other type. This means that every 2 Pokemon matchup will either have a winner or be a tie. This also means that any team can be ranked against any other team based on the number of winning matchups they have.

I want to write a program that can find the optimal Pokemon team out of a set of 70 provided Pokemon. A team is considered optimal if it has the greatest number of winning matchups against any other team. Basically, I want to calculate which team will have the most amount of favorable matchups if you were to battle it against every other possible team.

What algorithm would be best for doing this? It is not feasible to compute matchups for every possible team. Can I do some sort of A* search with enough pruning to make it computationally feasible?

$\endgroup$
1
+50
$\begingroup$

After my initial comment (where I suggest that it might not be enough info) I believe I actually came up with an idea.

Start with the full set of pokemon. For every possible type, identify the count of pokemon that are strong against that type. For this, you'll end up with a List<(pokemonId, types, List<weakAgainst>)>.

Minimize List<weakAgainst>.Count() and from the possible set of pokemonIds, select one at random. Without knowing anything else besides type, this pokemon is as good as any other with the same weakness count (this is the point of my original comment).

From the list of weaknesses that this selected pokemon has, select a pokemon from your list that is strong against the weakness, minimizing the amount of weaknesses again. Likely more than one will match this criteria, again, select one at random.

Keep repeating this pattern until you obtain the 6 in your team. This is, statistically speaking, one of the best teams that you can gather.

For all the combinations that you might find here, some teams will have less weaknesses, since we're "randomly" walking down a tree of possibilities. This very much sounds like a minimax-prunning algorithm, where each pokemon selection (minimizing your weaknesses) can be met with potential opponents that will maximize your weak points.

Simplified, put together:

input: allPokemon: list<pokemonId, weakAgainst, strongAgainst>

var: teamWeakAgainst: []
var: teamStrongAgainst: []
var: selectedTeam: []

while (size(selectedTeam) < 6)
  goodMatches <- allPokemon.max(p -> size(p.strongAgainst.intersect(teamWeakAgainst)))
  goodMatches <- goodMatches.min(p -> size(p.weakAgainst))
  goodMatches <- goodMatches.max(p -> size(p.strongAgainst))

  selectedPokemon <- goodMatches.random()

  teamWeakAgainst -= selectedPokemon.strongAgainst
  teamWeakAgainst += selectedPokemon.weakAgainst # not counting previously selected pokemon because the current one adds another "weakness", even if it was already accounted for

  selectedTeam += selectedPokemon

output: selectedTeam

From this algorithm is it not obvious where the "max" portion is. We're minimizing our losses (weaknesses) but we're considering all possible opponent teams equally, so there is no real maximization of the opponent choices. For a set of ideas, check below.

Note that this algorithm will give you a set of "teams" that are equally good in the sense that they'll have the same amount of minimized weaknesses and maximized strengths against other possible teams. But even if pokemon are different, the numbers will be the same, just different types.

For a more complex approach, you might want to consider how prevalent some pokemon are (you might not need to optimize against a super rare mythical type, but rather the very common types available in the game), how likely is it that certain pokemon can have better / faster attacks, what is the probability of battle IVs, how frequent can a trainer switch pokemon in battle, etc. Again, I know this is not what you asked for, but for the sake of the example, this will become so complex that instead of a search algorithm, a simulation (Monte Carlo?) approach might be simpler to build teams out of statistical testing.

| improve this answer | |
$\endgroup$
  • $\begingroup$ I'm worried that this algorithm is going to generate an unbalanced team. For example, water is the most common type of Pokemon. Electric is only weak to ground. This means that electric Pokemon are always going to have the most amount of strengths and fewest amount of weaknesses. This algorithm then will generate 6 electric types. This needs to be accounted for somehow. Maybe a weight to someone minimize the value of Pokemon that already have a positive matchup? $\endgroup$ – Tyler H Oct 9 at 12:03
  • $\begingroup$ I see that it will subtract the pokemon from the weak against list so that accounts for the problem of generating 6 of the same type. So if I'm understanding this correctly it will find a team that will always have more strengths than weaknesses, but it will not have the maximum possible amount of strengths. $\endgroup$ – Tyler Oct 9 at 18:50
  • $\begingroup$ Correct, it minimizes weaknesses as first metric and maximizes strengths as secondary metric. If it adds a water pokemon and that makes you weak against electric, it'll likely pick (for example) a rock type next. $\endgroup$ – Alpha Oct 10 at 13:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.