Monday, October 24, 2011

The Oracle Parser

Besides the structural changes to my software, the probably most visible evolution was the creation of a grammar to parse card text. To test my works, I use Arch's Magic Data, Version 2011-10-01, from where I extracted the abilities and replaced card names by a "~".
Based on that, it seems that there are currently 19710 abilities (including duplicates) in Magic, of which I'm able to parse 5661 abilities. Of these, 4282 are keyword abilities (I didn't add the following keyword abilities yet: Landwalk, Protection, Affinity, Bands with others, Offering, Splice, Typecycling). This makes a total of 1379 non-unique, non-keyword abilities I currently support. It sounded better before calculating the numbers for the post :S

Below is a diagram showing the evolution of my parser; the builds are made on a new-feature-available basis, and I usually deleted the statistics of any build that broke something that worked before.

For a rough guidance, the builds 1 through 13 were made on October 18th, #14 to #19 was on 19th, #20 to #28 was on 20th, the others were on 21st and 22nd.

Between #10 and #17, you can see how I added the keyword abilities, sometimes only a few, sometime a lot.
The next ten builds seem to have done little, although it is a total of 300 abilities that were now supported. The changes included generalizing costs and effects, so that both "Discard a card: do something." and "Pay something: Discard a card." worked; additional costs: "As an additional cost to cast ~, pay something."; generalizing object matching for effects like "Counter target instant or sorcery spell."; and even modal effects like "Choose one — ~ deals 3 damage to target creature; or ~ deals 3 damage to target player."
The small cut of 103 abilities that follows was a bug that accepted things such as "Counter target spell. You gain 3 life.", although gaining life was not yet supported: If there was a second sentence that could not be parsed, it was dropped without errors.
Up to the present, I mostly extended object matching for things like "nonblack artifact creatures", generalized abilities (instead of only "Draw a card", I now also support "Target player draws two cards" and "each opponent draws X cards") and added easy new ones like life gain, life loss and paying life for a total of 257 newly supported abilites.

But what is it worth to parse abilities without giving my program the opportunity to understand them? Remember, what I did is parse rules text, not (yet) support new cards/abilities in Laterna Magica. Out of the unstructured text format that is magic rules text, the parser creates a tree structure that is easier for software to work with. To show a few selected supported abilities:
"As an additional cost to cast ~, discard a card."
The "you" shows which player it is who discards a card. An alternative could be "target player".
"Choose one — Counter target red spell; or destroy target red permanent."
This one is a "SPELL_EFFECT": not an ability, but a part of a spell's resolution effect.
As you see, "Choose two" and "Choose X" are equally supported.
The "counter" and "destroy" effects both have their own targets that must be red spells or red permanents, respectively. The logical "and" shows that both conditions are necessary.
"When ~ enters the battlefield, destroy target nonartifact, nonblack creature."
 The trigger is actually not so nice yet. I will restructure this, so that it's not "ETB SELF" but "ChangeZone ANY Battlefield SELF" or something like that.
The destroy effect, again, uses logical predicates, this time including negations.
"Suspend 4—{1}{U}"
The keywords are all pretty similar. "KEYWORD" is a marker; neither "ACTIVATED_ABILITY" not "STATIC_ABILITY" nor anything else is universally applicable for keywords. The suspend keyword has a number of counters and a cost.

That's it for now. I hope you get something out of this post!


Unknown said...

"This one is a 'SPELL_EFFECT': not an ability, but a part of a spell's resolution effect." Actually, those are called "Spell Abilities" and are, in fact, abilities. They're just abilities that describe effects that occur as the spell resolves.

Silly Freak said...

I became aware of this shortly after my blog post, too, but chose not to change it in the post. In the meantime, I adapted it into my grammar, so now I'm a bit more correct in terms of magic naming rules. Thanks!

Stassa said...

Wow, very nice!

About the keywords, I think you'll need to determine their particular type, like which is an activated ability etc. This would be useful in cases where a card turns off all activated abilities on permanents and so on. I'm not sure how you do that. Can you infer an ability's type on the fly, by matching its syntax to a pattern? Otherwise you may need to explicitly include "suspend" in the category "activated abilities", as you do for "keyword", kind of like multiple inheritance.

I'm very excited about this and rather embarassed that I find out about it this late :0)

Have a great New Year!

Silly Freak said...

Hi Stassa!

My program uses multiple stages for the abilities. What is described here is just the syntax of possible abilities. Although I need to know syntax-wise that a destroy effect cannot have a duration, I just need to know that a certain keyword is a keyword. The syntax has no notion of how the rules of that keyword work.

When the program runs, this AST of abilities is converted into Ability objects that the Rules Engine can work with. At this stage, a keyword more or less results in one or more abilities. For example, the Equip keyword represents a very definite (and relatively simple) activated ability. The rules engine could interpret the ability without knowing that it was built from a keyword, and the only point where it's necessary to know the keyword is when removing and adding abilities.

So, although my parser does not generate this information, it is/will be implicitly available later, but not through analysis of a keyword's syntax.

In the end, there's no 1:1 mapping between keywords and abilities (for example, Mirrodin's Modular works both when the card is played and when it dies), so a keyword is really neither activated nor static nor triggered; it's just a shorthand for writing one or more abilities with these properties.

As for multiple inheritance, this is a very static mechanism. Much more flexible is to use an attribute that identifies the source keyword of the ability. Such abilities can then be handled specially, e.g. hidden from the user, because there's already the keyword.

Thanks for reading, I hope you get somethin gout of my posts!