Etherlords: Big O
Comments(5) In my last post, I described a very effective combo using Kobold Elders and Kobold Shamans. By the end of map 4, I had two high-level heroes, one of whom was using this combo. The other, which had progressed around the map by a different route and had encountered different spells, was using a different technique, one that’s more elementary (so much so that I hesitate to call it a combo) but also quite effective: a deck made mostly out of rats and anger.
The common stink rat is the beginner’s monster for team red: it’s 1/1 and costs 1 mana to cast. Anger is an enchantment that gives all your creatures +1 to their attack power. This bonus stacks, so your damage potential increases with both the number of rats and the number of Angers. Of course, the same bonus applies to non-rats, and that’s important sometimes — I put a couple of bats into this deck as well, because a couple of the enemies had a spell called Flood that disables anything that can’t fly — but the rats were cheap and disposable, and the strategem works better with lots of creatures than with a few powerful ones.
Both of these decks have the advantage that they start damaging the opponent immediately: kobold shamans and stink rats both cost 1 mana, so you can summon them on your very first turn. But more importantly, they’re both O(n2). That is, your potential to do damage on a turn, barring interference, is roughly proportional to the square of the number of turns that have passed. Even though the amount of mana available to you increases with every turn, you still only get to draw cards at a constant rate per turn. So in the long run, the number of instances of a spell active at any moment is going to be linear on the more limiting factor, time. But the damage potential of these strategems is determined by the product of the number of instances of two different spells.
There are other combos with this property; it may in fact be a feature of every deck that wins at high levels. In fact, there’s one instance I’ve observed of a spell that’s O(n2) without a combo: Grass Snakes. Every time a grass snake hits the opponent hero for damage, its attack power (and health, but that’s not what I’m considering here) increases by 1. I suppose this means that a snakes-and-anger deck would be O(n3). [Edit: Not really, see comments.] (Actually, that combo is impossible: Anger is red, and snakes are green, and never the twain shall meet. But apparently there are a few rare green spells that have a similar buff-all-friendlies effect.)
But I doubt that such a deck would actually function as O(n3) in practice, because the bonus on the snakes is per-snake, which makes it vulnerable. Every time a snake dies, any bonus it built up dies with it. The other decks I described are more robust: if you kill my rat, the next rat I summon will be just as angry. Catching up to where you were is linear (that is, O(n)) on the number of rats killed. For snakes, in the worst case it’s linear on the number of turns the oldest snake was alive… which, now that I think about it, makes it also linear on the number of snakes killed, because both the maximum age and the number of snakes are linear on the number of turns played so far. I guess big-O notation doesn’t tell us everything.
Here’s a better analysis: If you can kill my (oldest) snakes at the same rate as I can summon replacements, my damage potential from snakes will never increase. Whereas in the rat/anger deck, a rat equilibrium will just slow me down from O(n2) to O(n), because I’ll still be casting Anger at a constant rate. Unless you have spells that remove enchantments and we have equilibrium there too. I suppose what I mean by “robust” is that disrupting it completely requires more things.
But if you had a green buff like the ones you mention, then wouldn’t killing your elder snakes just reduce you from O(n^3) to O(n^2), thus making that a more robust combination than the rats?
A snake-and-anger deck wouldn’t be O(n^3) anyway, even in theory if you kill no snakes, and even if snake-strength was retroactive to the start of the game.
Your number-of-snakes-in-play is O(n).
Your damage-increase-from-snake-hits is O(n).
Your damage-increase-from-“anger” is O(n).
But the last two do not multiply, they add. So it’s O(n) * (O(n)+O(n)); i.e. it’s only O(n^2) regardless.
However, if you look inside the big O(), there’s an important difference: the snakes increase in power every turn they hit, which can be every turn, i.e. a rate of 1*n. Anger increases snake damage only as often as you cast anger, which is presumably only 1/k turns, so a rate of n/k.
So effective per-snake damage is something like (1+1/k)*n after n turns. Of course, they’re only that powerful if they came out at the beginning; the ‘n’ factor for anger is turns from the beginning, and for snakes is ‘since they launched’.
So if a snake launched m turns ago, it’s really getting (m+n/k) bonus damage. The number of snakes after n turns is also going to be something like n/k, so the anger component is doing something like n^2/k^2 damage per turn; the snake-power-up (assuming hitting every turn) is doing something like the sum of (1..n), but with k sparsity, which to a first approximation I would guess is something like n^2/(2k). So assuming they never got killed, the snake effect is doing something like a factor of k/2 more damage than the anger factor, where k is the number of unique cards in the deck, but still O(n^2).
Note that your analysis about why the snake deck not being as effective in practice kind of jumps trains: you talk about it not being O(n^3) in practice, implying you’re talking about snake anger, but then you switch to just talking about snakes without anger. Surely at the level you’re talking about, snake anger is superior to rat anger, even though the extra damage from the snake is subject to the issues you talk about. (Presumably the snake has some disadvantageous offset, like costing more mana.)
PS: For some reason all plus symbols in my post did not show up, which may make it tricky to decipher.
Drat, you’re right about the bonuses on the snakes adding rather than multiplying.
If I’m reasoning correctly, though, there is a way to get O(n3), by means of spells that allow you to draw extra spells. All such spells seem to be instant effects — that is, they give you 2 or 3 cards right now, rather than increasing your draw rate — but since your draw can contain more instances of the draw-more-cards spell, you can potentially keep casting it repeatedly as long as you still want to spend the mana on it. Since your mana pool is O(n), the number of draws per turn becomes O(n) and the number of instances of any persistent spell (including creatures) becomes O(n2). O(n2) snakes with O(n) damage potential each yields O(n3), and O(n2) rats with O(n2) anger would be O(n4).
However, relying on the draw-more-cards spell would use up mana and slow down the rate at which you cast other spells, and the benefits of having O(n4) damage potential probably wouldn’t manifest fast enough to be worthwhile. Unless you’re in a match with really high level heroes who have hundreds of hit points.
Also, I’ve added back your missing plus signs. Seems like this problem could result from faulty URL-encoding: spaces are encoded as in HTML form data. What browser are you using?