23
$\begingroup$

Imagine we have a wizard that knows a few spells. Each spell has 3 attributes: Damage, cooldown time, and a cast time.

Cooldown time: the amount of time (t) it takes before being able to cast that spell again. A spell goes on "cooldown" the moment it begins casting.

Cast time: the amount of time (t) it takes to use a spell. While the wizard is casting something another spell cannot be cast and it cannot be canceled.

The question is: How would you maximize damage given different sets of spells?

It is easy to calculate the highest damage per cast time. But what about in situations where it is better to wait then to get "stuck" casting a low damage spell when a much higher one is available:

For example,

1) 100 damage, 1 second cast time, 10 second cool down.

2) 10 damage, 4 second cast time, 0 second cool down.

So, in this case you would cast #1, #2, wait. Cast #1

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ Maybe the game dev section might be more suitable? $\endgroup$ – J. M. is a poor mathematician Nov 15 '10 at 15:30
  • 1
    $\begingroup$ Thanks, but it was suggested that I try here first since if you remove the spell casting theme it is a game theory question $\endgroup$ – aaronfarr Nov 15 '10 at 15:42
  • 16
    $\begingroup$ @aaronfarr: it's not really a game theory problem, it's an optimization problem. In fact it is really a type of scheduling problem. I don't understand the votes to close since it is far from obvious to me how to maximize damage / time in general. Consider this a vote against closing. $\endgroup$ – Qiaochu Yuan Nov 15 '10 at 15:59
  • 2
    $\begingroup$ @aaronfarr: do you want to put any constraints on the numbers here? For example, are they all positive integers? If certain ratios are irrational I think you can arrange it so that an optimal casting schedule is aperiodic. $\endgroup$ – Qiaochu Yuan Nov 15 '10 at 16:49
  • 2
    $\begingroup$ We would just be dealing with integers >= 0 for all three variables, thanks for pointing that out $\endgroup$ – aaronfarr Nov 15 '10 at 18:34
19
$\begingroup$

It is worth noting that, in extreme special cases, this problem degenerates to the Knapsack Problem, which is NP-complete to solve exactly. To see this, imagine that there is one spell, henceforth called the Megaspell, which does a very, very large amount of damage, has zero casting time, and has some positive cooldown $n$. If all the other spells do much less damage than the Megaspell, it will clearly be optimal to cast the Megaspell every $n$ seconds and then optimize the cooldown time with the weaker spells.

Now, assume all the other spells also have cooldown $n$. If one optimizes a given $n$-second downtime with these spells, then the same spell-sequence will also be possible in the next $n$-second downtime, and so we can assume the solution is $n$-periodic.

The problem then reduces to optimizing the $n$ available seconds with the lesser spells, each of which may only be cast once. If one replaces casting time with 'weight' and damage with 'value', one recovers the Knapsack Problem for maximum weight n.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ @Greg: Nice idea. Thought about the same thing earlier today. It seems like the spell with the highest damage per cast time basically becomes the "backbone" spell. You want to cast this as often as possible. So it simply becomes a matter of fitting in as many other "filler" spells in between. However, this does not address the scenario where some "gaps" in between backbone spell casts will result in higher damage per second. Very simple example: 1) 100 damage, 2 second cast, 10 second cooldown. 2) 50 damage, 9 second cast, 0 sec cooldown. $\endgroup$ – aaronfarr Nov 16 '10 at 4:39
  • 1
    $\begingroup$ Sure, and I wasn't claiming that this kind of solution is general, or even all that common. My aim was to show that the Spellcasting problem actually contained the well-known Knapsack problem, which is already known to be 'hard' in several precise senses. However, there is already an extensive literature on the Knapsack problem, and I wouldn't be surprised if some of the approaches can be extended to the Spellcasting problem. Unfortunately, I don't really know it at all. $\endgroup$ – Greg Muller Nov 16 '10 at 6:05
  • $\begingroup$ Very nice. I was trying to reduce to the knapsack problem earlier but couldn't manage it. $\endgroup$ – Qiaochu Yuan Nov 16 '10 at 11:34
  • 1
    $\begingroup$ The knapsack solution only applies to spell sets that satisfy two properties: (A) all cooldown times are the same, and (B) one spell has MUCH larger damage than all the others. Finding an exact threshold needed for a spell to be a Megaspell is a little fiddly (that is, for it to be best to cast it as often as possible). $\endgroup$ – Greg Muller Nov 18 '10 at 6:20
  • 2
    $\begingroup$ In such a situation, it is easy to show that at least one optimal spell sequence is periodic with period n. Therefore, we can focus on the first n seconds. Then, we notice that it doesn't matter what order we cast the spells in for those n seconds; we can cast them in any order without changing the damage or the total time. Therefore, it becomes a problem of which subset of spells to cast. Each has a 'cost' (casting time) and a 'benefit' (damage), and we have finite cost to spend (n). Maximizing this is the knapsack problem. $\endgroup$ – Greg Muller Nov 18 '10 at 6:25
5
$\begingroup$

I don't have an answer, but I just want to point out that the greedy algorithm fails. That is, if we choose to cast, at any point, the available spell which maximizes $\frac{ \text{damage} }{ \text{cast time} }$, we don't actually maximize our damage output because of cooldown. Consider the pair of spells $(300, 5, 12)$ and $(50, 3, 0)$ (where the three numbers are damage, cast time in second times, and cooldown time in seconds): the greedy algorithm suggests the casting schedule

  • Cast spell 1 ($300$ damage, $5$ seconds),
  • Cast spell 2 ($50$ damage, $3$ seconds),
  • Cast spell 2 ($50$ damage, $3$ seconds),
  • Cast spell 2 ($50$ damage, $3$ seconds),
  • Repeat

which gives about $32.1$ damage per second. However, the casting schedule

  • Cast spell 1 ($300$ damage, $5$ seconds),
  • Cast spell 2 ($50$ damage, $3$ seconds),
  • Cast spell 2 ($50$ damage, $3$ seconds),
  • Wait $1$ second,
  • Repeat

gives about $33.3$ damage per second. So a correct algorithm must take into account which spells are about to finish cooling down.

|cite|improve this answer
$\endgroup$
1
$\begingroup$

How about this algorithm? At each moment your decision is which spell to cast next. Having decided, if the cool down time for that one has expired, then go ahead and cast it. If not, wait until it has expired, then cast it. To make the decision, rank the spells in damage/time where time is from now to completion (including any cool down time left). Then see if you can fit in one of the other spell without delaying the best one. Taking Qiochu's example, at the start spell 1 is 300/5=60 dam/sec and spell 2 is 50/3=16.7dam/sec. Having cast spell 1, it is now 300/17=17.6 dam/sec, still better than 2. But we can get 2 done twice before 1 is available, so we should do that. The question would be whether you can change the parameters so that you should use the weaker spell even though it will delay the strong one by just a little bit.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ I considered this, but I don't think it's that simple. You can't just account for the cooldown time left; I think you also have to account for future cooldowns. I don't have an explicit counterexample, though. $\endgroup$ – Qiaochu Yuan Nov 16 '10 at 1:15
0
$\begingroup$

Let's rephrase to: what's the maximal damage that I can cause in, say, 100 seconds? The constraints then become:

  1. Can't spend more than 100 seconds casting
  2. Can't cast a single spell more than $\frac{100}{cast\ time + cool\ time}$ times

Let $n_i$ be the number of times I cast spell i. I want to maximize $\sum_i n_i damage_i$ subject to $\sum_i n_i cast_i < 100$ and each $n_i(cast_i + cool_i) < 100$.

This can be rewritten to a linear programming problem as follows:

  1. The first constraint is $[cast_0 \dots cast_m] [n_0 \dots n_m]^T<100$
  2. The other constraints are $[0 \dots (cast_i + cool_i) \dots 0] [n_0 \dots n_m]^T < 100$

EDIT: My assumptions are

  1. You cannot cast two spells at the same time. Constraint #1 ensures that this is true.
  2. You can only cast a spell once every $cast + cool$ period. Constraint #2 ensures this is true. (Note that this does not say you cannot cast a different spell in this period; only that you cannot cast the same spell in this period.)
|cite|improve this answer
$\endgroup$
  • $\begingroup$ This is an interesting approach, but I'm not sure if ignoring the ordering of the spells like you do won't cause problems. In any case, you can't ignore (1) because otherwise the optimal solution will always be $n_i = 100/(\text{cast}_i + \text{cool}_i)$. Also, you should mention that this is an integer linear programming problem, which is harder. $\endgroup$ – Rahul Nov 16 '10 at 1:07
  • $\begingroup$ Actually, since cooldown begins the moment you begin casting, (2) should just be $100/\text{cool}_i$. $\endgroup$ – Rahul Nov 16 '10 at 1:09
  • $\begingroup$ The second condition is wrong. The point of the problem is that we can cast some spells while waiting for others to cooldown, and this formulation doesn't take that account. $\endgroup$ – Qiaochu Yuan Nov 16 '10 at 1:16
  • $\begingroup$ @Rahul: you are right, #1 cannot be ignored. @Qiaochu: I examined this, and I do not understand your objection. I tried to make my reasoning more clear - could you let me know where I went wrong? $\endgroup$ – Xodarap Nov 16 '10 at 1:39
  • $\begingroup$ @Xodarap: ah, right. In any case, these conditions are only necessary, not sufficient, so I don't see how this helps. $\endgroup$ – Qiaochu Yuan Nov 16 '10 at 11:35
0
$\begingroup$

I was able to solve the problem with a computer algorithm but am still not certain how it can be done mathematically. It was pointed out by @Greg Muller that the knapsack problem is applicable but I just don't have the mathematical prowess to apply it. If someone could show how that can be done please do.

Will share my logic here, hopefully it is useful to someone out there.

The first step is to determine the spell with the most damage per cast time.

This spell becomes the "baseline" spell since it will guarantee the highest damage per second. Meaning, you should always cast this spell if the following 2 conditions are met: 1) The baseline spell is available (not on cooldown). 2) You are not currently casting a spell.

So it then becomes a matter of filling in other spells while the baseline spell is on cooldown. Between (cast time) and (cooldown - cast time). However, some overlapping can occur (rule 2 above is false).

It then becomes a matter of recursing through all non-baseline spells to find all sequences of spells which do not violate the 2 rules.

For spells which DO overlap you must penalize them for potential damage the baseline spell could have done (up to its maximum damage).

Take for example, 2 spells

1: 300 damage, 3s cast time, 10s cooldown

2: 290 damage, 3s cast time, 3s cooldown

The most damage comes from the sequence 1 - 2 - 2 - 2. Which causes an overlap of 2 seconds into a potential #1 cast. However, this is still beneficial since if you dont cast the third spell (ie. 1 - 2 - 2) you will do 880 damage with 1 second to spare. If you cast the extra #2 spell you will do 1170 - 2 second of #1 which is 200. So 970 damage is your relative damage.

This algorithm is significantly faster than other algorithms which look for sequences that match a target goal: ie. time limit or damage.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ I do not agree that the spell with the most damage per cast time should always be a baseline spell. From this post, though, I can't really tell what your goal is. Do you actually want the optimum damage per time or do you just want a reasonably good amount of damage? $\endgroup$ – Qiaochu Yuan Nov 19 '10 at 9:47
  • $\begingroup$ There is no time constraint. So you are trying to maximize damage per second. In what situation would the highest damage per cast time not be optimal? $\endgroup$ – aaronfarr Nov 19 '10 at 15:46

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.