2
$\begingroup$

Apologies if this is a duplicate. I searched for some time and the closest I could find was the Knapsack Problem, which does not fit because I have a fixed team size & a different value function.

I have $N \approx 50$ Pokémon, from which I need to choose a team of six to attack an enemy. Each pokemon can survive for a certain time "$t$" against the enemy, and each pokemon does a certain amount of damage per second "$DPS$" to the enemy. I may or may not defeat the enemy, but I would like to optimize the damage I can do to it within the time limit of 300 seconds without my entire team dying.

These data are sufficient to determine the optimal team. The damage done by a team, which fights in order of highest > lowest $DPS$, is the sum $$Damage(DPS_i, t_i) = \sum_{i=1} DPS_i * \hat{t_i} $$ where $0<\hat{t_i}<t_i$ is the amount of time each pokemon battled for. Typically the first few pokemon will battle until they die ($\hat{t_i}=t_i$), one pokemon will win with a fraction of its health remaining ($0<\hat{t_i}<t_i$), and the rest may never get to battle ($\hat{t_i}=0$).

The optimization problem can be phrased as follows:

  • Maximize the function $Damage(DPS_1, ST_1, ..., DPS_6, ST_6)$
  • Given the constraint that $\sum_i t_i >300$

It is clear that this can be brute-forced by checking the damage and survival time of all team combinations. This is not an option because it takes too long.

Another possibility was to start with the highest-DPS team and then make "trades" in order of highest gain in $t$ per sacrifice of $DPS$. However I'm not convinced this will converge to the optimal solution.

I would be very thankful for any suggestions or references to analogous problems.

$\endgroup$
  • $\begingroup$ Without telling us how $\hat{t}_i$ is calculated, the question is not answerable. What are the inputs? (presumably, $DPS_i$ and $t_i$) How does $\hat{t}_i$ depend on the inputs? Also, it doesn't seem that hard to try all ${50 \choose 6} \approx 2^{24}$ possible teams. Have you tried to implement that and see what happens? $\endgroup$ – D.W. Sep 3 '17 at 3:17
  • $\begingroup$ @D.W. I was brief but I think it sacrificed some clarity. The instruction to find $\hat{t}_i$ is: Loop through the team of Pokemon in order of DPS, summing up their $t_i$ until the current term would push the sum over 300. For the previous terms, $\hat{t}_i=t_i$. For the current term, $\hat{t}_i$ is the remaining time up to 300. For all later terms, $\hat{t}_i=0$. I would like for the algorithm to run quickly because many people might use it & they will have to repeat it ~10 times. But I have considered just brute forcing with elimination of obviously-bad teams. $\endgroup$ – doublefelix Sep 3 '17 at 6:45
  • $\begingroup$ In order of increasing DPS or decreasing DPS? Can you edit the question to specify all of these details in the question (not just in comments; we want the question to stand on its own, so people don't have to read the comments)? $\endgroup$ – D.W. Sep 3 '17 at 7:02
  • $\begingroup$ Giving an example of the damage calculation for an example team might help, too. $\endgroup$ – D.W. Sep 3 '17 at 7:10
2
$\begingroup$

You could use A* to solve this problem. A* is designed to optimally search through a state space to solve a problem based on trying to minimize a "cost."

The first thing I'd do is reframe the problem. Instead of thinking in terms of time and DPS, use time and "damage" by multiplying them together. I recommend this because that's the term you're trying to maximize. It'll make it clearer.

Let's define a "state" in this A* algorithm as a team of 0-6 Pokemon, and their total damage. State transitions consist of adding Pokemon to the team, updating the total damage. Don't forget that this is a combination problem, not a permutation problem. Team ABCDEF is the same as team FEDCBA. The easy way to handle this is to sort by name when adding to the team. (And as a small optimization, if you care, 50 pokemon is small enough to fit into a 64-bit integer, so your teams could be defined by a datastructure as small as an int)

To fit this problem to A*, we have to define a goal function. The goal function defines an "acceptable" solution, but saying nothing about whether its the best solution. The goal function is a team of 6 Pokemon that has a total time greater than 300. This will satisfy your constraint.

We can handle your goal of maximizing damage by using it as our "cost" metric. A simple way to do this is to say the "cost" is equal to $-damage$, that is to say that it's always a negative number. A* doesn't mind the final cost being negative.

The last thing you need for A* is the "heuristic underestimate." You need an estimated cost for finishing out the team that is always an underestimate (a lower "cost" than the real answer, which means a higher damage than the real best answer). This can easily be constructed by finding a "best damage team" using the remaining Pokemon, ignoring the time constraint.

Put those together, and A* will do the rest. A* is "optimal," meaning that it is the most efficient algorithm you can come up with given the information provided. Any more ideal algorithm will need to use more information than what we gave A* (i.e. more than just a cost function and a heuristic underestimate).

$\endgroup$
  • $\begingroup$ Thank you for your answer; I am writing this in Python and will look for a good A* implementation to work off of. Is A* guaranteed to converge to the set of minimal cost, or might it get stuck on some kind of local min? $\endgroup$ – doublefelix Sep 2 '17 at 18:02
  • $\begingroup$ You are not wrong. Consider, however, that your answer reads like "use A*, it's the best solution here" without you giving any indication about why that would be true. That's my criticism. The answer is worth little if you don't give any reasons for why it should be good choice; otherwise, we'd get every available search/optimization technique on every question, which would be useless. $\endgroup$ – Raphael Sep 2 '17 at 18:03
  • $\begingroup$ @doublefelix A* is guaranteed to find the minimum answer, as long as your estimate is indeed an underestimate. It is designed to look at the "most promising" options first, so it's first success is always the best. The price is that it can be less efficient than other methods (which Ralph slides to), but I couldn't think of any of those approaches. $\endgroup$ – Cort Ammon Sep 2 '17 at 19:57
  • $\begingroup$ @doublefelix I'd also recommend writing your own A*. Unlike many optimization algorithms, A* is simple, and a good learning experience. It's good to look through the algorithm and understand why it works. $\endgroup$ – Cort Ammon Sep 2 '17 at 20:03
  • $\begingroup$ @d.w. We may need to go to chat to better identify where the confusion occurs. As for the specific questions you had about the state space and the transitions, those are covered in the third paragraph of my answer. $\endgroup$ – Cort Ammon Sep 3 '17 at 16:44
0
$\begingroup$

After observing the worst case performance of my other answer, I decided to take another swing at it. This time I decided to use dynamic programming approach. In dynamic programming, we break the problem into smaller pieces and then use those pieces to build the bigger solution.

In the case of these Pokemon, we observe that the effect of any subteam of Pokemon is not affected by the performance of any others. If I have a team ABCDEF and look just at the DPS and time of the AB subteam, its identical to AB's performance if it were part of team ABXYZW. Thus, we can maximize the value of subteams, and then bring the results together.

First, note that the original brute force approach has to explore $_{50}C_6$ possible teams -- that is, out of 50 pokemon, it chooses 6 of 50, combinatorially. $_{50}C_6 = 15890700$, so that's the number to beat if we want to be more efficient than brute force. (As an aside, 16 million is actually really small for computers. The brute force approach is actually probably good enough)

Let's drop this number by building teams of 2 pokemon first, then combining those teams into a final answer. To explore teams of 2, we have to study $_{50}C_2 = 50*49 = 2540$ different teams of 2. Now from these teams, we can reject the majority of them as "provably worse" than another team. A team is "provably worse" than another if they are beaten on both damage and longevity. For example, if AB can deal 500 damage and last 50 seconds, and CD can deal 400 damage and last 40 seconds, there is no case where you would want to use CD in which AB would not be simply better.

In the worst case, every single pokemon has a unique lifespan, so there's $50+50=100$ possible lifespans for a team of 2. Realistically, there are likely to be fewer possible lifespans, because many Pokemon will last the same amount of time. However, this guarantees that, at most, we will only have to consider 100 possible 2-pokemon teams in the next step. Why? Because for any given lifespan of a 2-pokemon team, there's no reason to include any teams which are anything less than the best for that lifespan. There's only 100 possible lifespans, thus only 100 worthy teams to consider going forward.

Now we can build up a team of 6. This will involve picking 3 teams of 2. You'll have to make sure we don't include a pokemon twice when you write your code, but that's easy. Thus we have 100 2-pokemon teams, and we choose 3 from that. $_{100}C_3=161700$, so you will have to consider around 161k sets of 3 2-pokemon teams to find your best solution.

Thus, our total number of teams (of any size) built is $2450+161700=164150$. Doing a quick division, this shows that our solution now costs 1.03% of the cost of the brute force. This is, of course, a worst case. In reality, there will likely be more collisions on the lifespan of the different 2-pokemon teams, reducing this even further.

$\endgroup$
0
$\begingroup$

You can solve this problem with dynamic programming. We will first pick the member of the team that wins with partial health remaining; there are 100 possibilities for it, so just try all possibilities, and for each, do the following procedure to pick the rest of the team. That gives you 100 candidate teams; choose the best one.

So now suppose we have picked the team member who wins with partial health remaining; call her Gina. Next, we will pick the team members who die. By assumption, all of those team members have DPS that is at least as large as Gina's DPS. So, discard all Pokemon whose DPS is lower than Gina, and form a pool from the reamining Pokemon.

Now we want to pick a group of at most 5 Pokemon from that pool, such that the sum of their survival times (their $t_i$ values) is somewhere in the range $[300-t_\text{Gina},300]$ and such that the sum of their damages ($DPS_i \times t_i$) is as large as possible. That's a variant of a knapsack problem, and can be solved with dynamic programming. Let $A[j,k,s]$ denote the maximum-achievable sum-of-damages, for a team that uses at most $k$ Pokemon selected from among the first $j$ Pokemon in the pool and that has a sum of survival times equal to $s$. It's easy to write a recursive expression for $A[j,k,s]$; we have

$$A[j,k,s] = \max(A[j-1,k,s], A[j-1,k-1,s-t_j] + DPS_j \times t_j).$$

Applying dynamic programming then gives a way to compute all of the $A[j,k,s]$ values. Now you just take the maximum value of $A[j,k,s]$, where $j$ is the number of Pokemon in the pool, $k$ ranges over $0 \le k \le 5$, and $s$ ranges over $300-t_\text{Gina} \le s \le 300$. That gives you a way to pick at most 5 other Pokemon who die before Gina.

What's the running time? The dynamic programming algorithm fills in the $A$ array in about $100 \times 5 \times 300$ steps, as there are 100 possible values of $j$ 5 possible values of $k$, and 300 possible values of $s$. You have to run the dynamic programming algorithm 100 times, for each choice of who will play the role of Gina. That's $100 \times 5 \times 300 \times 100 \approx 2^{24}$ ... not much better than brute force.

It might be possible to replace the dynamic programming algorithm with a greedy algorithm. You can sort the pool by decreasing value of $DPS_i \times t_i$, then try to pick Pokemon from the pool (in sorted order) until sum of their survival times ($t_i$ times) is over 300. That gives you a team. Repeat 100 times for each possible choice of who plays the role of Gina.

$\endgroup$

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.