The poset of mana costs
Oct. 14th, 2017 01:44 amHere's an interesting question: Given two Magic cards A and B, how do we determine whether A has a cheaper mana cost than B?
We'll have to specify what we mean here, of course. We'll say card A costs no more than card B if any amount of mana sufficient to pay for B is also sufficient to pay for A.
If we're just using the usual mana symbols -- {W}, {U}, {B}, {R}, {G}, and generic mana -- this is easy. Card A is costs no more than card B if, for each color, there are no more mana symbols of color M in card A than there are in card B, and if the total ("converted") mana cost of A is no more than that of card B. (Any instances of {X}, obviously, should be ignored.) Obviously adding the colorless mana symbol {C} doesn't change the basic method, you just now have to include that as one of your "colors". And, moreover, while it's never appeared in the mana cost of a card, and technically works a little differently, it's not too hard to see that adding the snow mana symbol {S} acts the same way.
But what about hybrid mana? This complicates things substantially. We effectively have three sorts of hybrid mana: The usual hybrid between two colors, such as {W/U}; "2-brid", such as {2/W}; and Phyrexian mana, such as {W/P}.
Now, if you're working with mana costs that actually exist on cards, this should never be a hard problem, because Wizards of the Coast avoids printing confusing mana costs. (Mostly, anyway. There is Reaper King.) But say you want to write an automated procedure for this. You could write it by special-casing the sort of mana costs that actually exist, but that's pretty clunky; and maybe you want to compare against a mana cost that doesn't currently exist.
So how can you do this in an automated fashion? An obvious way is, given your two input mana costs, try every way of disambiguating them into mana costs using just the usual symbols (and an imaginary {P} symbol representing 2 life). Then A costs no more than B if, for every disambiguation of B, there's a disambiguation of A that costs no more than it.
But that seems pretty clunky compared to just checking some numbers against each other. I mean, think about the run-time; naively, it's exponential in the lengths of the mana costs. Really of course it's not exponential, because when multiple of the same type of hybrid appear in the mana cost, you only need to consider how many of them go one way or the other; their independent identity doesn't matter. This means that instead of the running time being exponential in the length of the input, it's merely... bounded by the 20th power of the input. (Because there are 20 possible hybrid symbols.) That's, uh, not very good.
(Consider: Generic mana is effectively a type of hybrid. But nobody would ever suggest comparing mana costs with generic mana in them by disambiguating the generic mana...)
What would be nice would be to just have some linear inequalities to check, like we do for cards without hybrids. Then it would be linear time. Fortunately, we can do this! Well, mostly. Not quite entirely, as far as I can tell.
The problem is the 2-brids; these can stand for either one mana or two, and that causes some problems. (Remember, we're considering 2 life a type of "mana" here, so Phyrexian mana symbols still always represent 1 mana by this accounting.) But let's say we ignore those for now.
In that case, a bunch of linear inequalities is indeed sufficient! There are unfortunately a lot of them. But all we need to check is that the counts of the following are no greater for A than for B:
1. Colorless mana symbols.
2. For each color, ordinary mana symbols of that color.
3. For each color, ordinary or Phyrexian mana symbols of that color.
4. For each pair of colors, ordinary mana symbols of either of those colors, and the corresponding hybrid symbol.
5. For each pair of colors, ordinary or Phyrexian mana symbols of either of those colors, and the corresponding hybrid symbol.
6. For each triple of colors, ordinary mana symbols of any of those colors, and hybrid symbols from among those 3 colors.
7. For each triple of colors, ordinary or Phyrexian mana symbols of any of those colors, and hybrid symbols from among those 3 colors.
8. For every set of four colors, ordinary mana symbols of any of those colors, and hybrid symbols from among those 4 colors.
9. For every set of four colors, ordinary or Phyrexian mana symbols of any of those colors, and hybrid symbols from among those 4 colors.
10. Ordinary mana symbols of any color, and ordinary hybrids of any pair of colors.
11. Ordinary or Phyrexian mana symbols of any color, and ordinary hybrids of any pair of colors.
12. Total ("converted") mana cost, excluding Phyrexian mana symbols.
13. Total ("converted") mana cost.
14. Snow mana symbols, if we want to count that.
(Sketch of proof that this works: Use Hall's marriage theorem.)
Now, that's a lot of inequalities to check... 66 of them, all told, or 65 if we don't count snow. But hey -- it's linear time! Even though in practice it would probably be slower than the naive 20th-power or exponential algorithm, given that there's no Magic card with a converted mana cost higher than 16, and most of them are way less than that, and (ignoring Reaper King, which uses 2-brid) no card has more than 4 hybrid symbols.
But OK, what about 2-brid? Unfortunately, I can't find any elegant way of handling this. The best way I can think of is to disambiguate 2-brids and then apply the method above to the result. Resulting in a method with 5th-power time. (But presumably pretty fast in practice. With Reaper King as I guess the worst practical case.)
It would be nice if there were some way to extend the inequalities above to handle 2-brid. I don't know of such a way and I don't think I'd expect there to be one. But hey, maybe one exists...
Edit: I've turned some questions about easier ways to handle 2-brid into a MathOverflow question!
-Harry
We'll have to specify what we mean here, of course. We'll say card A costs no more than card B if any amount of mana sufficient to pay for B is also sufficient to pay for A.
If we're just using the usual mana symbols -- {W}, {U}, {B}, {R}, {G}, and generic mana -- this is easy. Card A is costs no more than card B if, for each color, there are no more mana symbols of color M in card A than there are in card B, and if the total ("converted") mana cost of A is no more than that of card B. (Any instances of {X}, obviously, should be ignored.) Obviously adding the colorless mana symbol {C} doesn't change the basic method, you just now have to include that as one of your "colors". And, moreover, while it's never appeared in the mana cost of a card, and technically works a little differently, it's not too hard to see that adding the snow mana symbol {S} acts the same way.
But what about hybrid mana? This complicates things substantially. We effectively have three sorts of hybrid mana: The usual hybrid between two colors, such as {W/U}; "2-brid", such as {2/W}; and Phyrexian mana, such as {W/P}.
Now, if you're working with mana costs that actually exist on cards, this should never be a hard problem, because Wizards of the Coast avoids printing confusing mana costs. (Mostly, anyway. There is Reaper King.) But say you want to write an automated procedure for this. You could write it by special-casing the sort of mana costs that actually exist, but that's pretty clunky; and maybe you want to compare against a mana cost that doesn't currently exist.
So how can you do this in an automated fashion? An obvious way is, given your two input mana costs, try every way of disambiguating them into mana costs using just the usual symbols (and an imaginary {P} symbol representing 2 life). Then A costs no more than B if, for every disambiguation of B, there's a disambiguation of A that costs no more than it.
But that seems pretty clunky compared to just checking some numbers against each other. I mean, think about the run-time; naively, it's exponential in the lengths of the mana costs. Really of course it's not exponential, because when multiple of the same type of hybrid appear in the mana cost, you only need to consider how many of them go one way or the other; their independent identity doesn't matter. This means that instead of the running time being exponential in the length of the input, it's merely... bounded by the 20th power of the input. (Because there are 20 possible hybrid symbols.) That's, uh, not very good.
(Consider: Generic mana is effectively a type of hybrid. But nobody would ever suggest comparing mana costs with generic mana in them by disambiguating the generic mana...)
What would be nice would be to just have some linear inequalities to check, like we do for cards without hybrids. Then it would be linear time. Fortunately, we can do this! Well, mostly. Not quite entirely, as far as I can tell.
The problem is the 2-brids; these can stand for either one mana or two, and that causes some problems. (Remember, we're considering 2 life a type of "mana" here, so Phyrexian mana symbols still always represent 1 mana by this accounting.) But let's say we ignore those for now.
In that case, a bunch of linear inequalities is indeed sufficient! There are unfortunately a lot of them. But all we need to check is that the counts of the following are no greater for A than for B:
1. Colorless mana symbols.
2. For each color, ordinary mana symbols of that color.
3. For each color, ordinary or Phyrexian mana symbols of that color.
4. For each pair of colors, ordinary mana symbols of either of those colors, and the corresponding hybrid symbol.
5. For each pair of colors, ordinary or Phyrexian mana symbols of either of those colors, and the corresponding hybrid symbol.
6. For each triple of colors, ordinary mana symbols of any of those colors, and hybrid symbols from among those 3 colors.
7. For each triple of colors, ordinary or Phyrexian mana symbols of any of those colors, and hybrid symbols from among those 3 colors.
8. For every set of four colors, ordinary mana symbols of any of those colors, and hybrid symbols from among those 4 colors.
9. For every set of four colors, ordinary or Phyrexian mana symbols of any of those colors, and hybrid symbols from among those 4 colors.
10. Ordinary mana symbols of any color, and ordinary hybrids of any pair of colors.
11. Ordinary or Phyrexian mana symbols of any color, and ordinary hybrids of any pair of colors.
12. Total ("converted") mana cost, excluding Phyrexian mana symbols.
13. Total ("converted") mana cost.
14. Snow mana symbols, if we want to count that.
(Sketch of proof that this works: Use Hall's marriage theorem.)
Now, that's a lot of inequalities to check... 66 of them, all told, or 65 if we don't count snow. But hey -- it's linear time! Even though in practice it would probably be slower than the naive 20th-power or exponential algorithm, given that there's no Magic card with a converted mana cost higher than 16, and most of them are way less than that, and (ignoring Reaper King, which uses 2-brid) no card has more than 4 hybrid symbols.
But OK, what about 2-brid? Unfortunately, I can't find any elegant way of handling this. The best way I can think of is to disambiguate 2-brids and then apply the method above to the result. Resulting in a method with 5th-power time. (But presumably pretty fast in practice. With Reaper King as I guess the worst practical case.)
It would be nice if there were some way to extend the inequalities above to handle 2-brid. I don't know of such a way and I don't think I'd expect there to be one. But hey, maybe one exists...
Edit: I've turned some questions about easier ways to handle 2-brid into a MathOverflow question!
-Harry
