Programming in Magic

So… about this parser/ interpreter. In its heart there lies a definition of MGL syntax, using Prolog’s Definite Clause Grammar facility. DCGs is basically syntactic sugar, to represent grammar rules. This syntax is expanded into proper Prolog by Prolog’s interpreter (not to be confused with the MGL interpreter discussed here).

Here’s an example. As per the Comprehensive Rules (602.1) activated abilities are written as:

[Cost]: [Effect.] [Activation instructions (if any).]

The DCG representation of this rule is:

activated_ability  --> cost, [:], effect, instructions.
activated_ability  --> cost, [:], effect.

If it helps you, you can read this as “an activated ability is a cost separated by a colon from an effect, optionally followed by activation instructions”. Enclosing the colon in [square brackets] marks it as a terminal symbol. The non terminals, cost, effect and instructions can be expanded further by Prolog, until an appropriate terminal is found.

Here’s a more full example. The spell, Unsummon, has an ability: “Return target creature to its owner’s hand”. In Gleemin’s database of cards, Unsummon’s text is entered as a comma separated list of Edinburgh-syntax Prolog terms, which is to say, upper-case words must be enclosed in ‘ ‘s and the whole thing must be in square brackets- like so:

['Return',target,creature,to,its,'owner''s',hand]

This is a spell ability, not an activated ability; we define a spell ability like this (%’s begin a line of comments in Prolog):

ability --> spell_ability. % an ability can be a spell ability
spell_ability --> effect(Target).  % a spell ability is a targeted effect

The particular effect of unsummon needs a target to return:

effect(Target) --> return(Target).

Remember that in Prolog, variables begin with uppercase letters. “Target” will need to be instantiated to a valid target. This is not strictly necessary- the same rule could be written as “effect –> return(Target)”, but it makes it clearer to the human reader that we are dealing with a targeted effect. Of course, we need to know where to “return” our chosen Targets. Generally, things are bounced to players’ hands:

return(Target) --> ['Return'], target(Target), [to, its, 'owner''s', hand].

So what is a valid target to return? Unsummon can only target creatures, but “return” is an MGL directive, if you like, that can take as a target any type of permanent (but not players) (ha ha). Here, the rules for return must branch. We are intersted in the “target creature” clause:

target(Target) --> ['target', 'creature'], {creature_type(Target)}.
% A valid target for an effect that targets a creature, must be a creature.

creature_type/1 is defined elsewhere in Gleemin and simply makes sure that the Magic object it’s passed as an argument is really a creature. Note that the call to creature_type/1 is enclosed in curly braces. This marks it as a Prolog call that must be executed as a side-effect of parsing.

This basically means that while we parse our ability – sentence, we can run any Prolog code that we want to. Basically, if we reach the last clause defined above and creature_type(Target) returns true, we know that we have a valid target for Unsummon’s ability. We can run some code to actually return that creature where it came from.

This is a very cool thing to do- to execute MGL as we parse it. However, I opted instead to keep the actual execution code separately, for clarity. I’ll come to that code in a minute. For now, let’s look at the many cool things that we can do with this grammar. For one thing, we can ask the program what is a valid “return” effect, in MGL, by entering this query to the listener (the Prolog interpeter’s command line):

| ?- phrase(return(X), Y).

Which will then reply with:

X = 'Aether Adept' ,
Y = ['Return',target,creature,to,its,'owner''s',hand] ;

X = 'Air Servant' ,
Y = ['Return',target,creature,to,its,'owner''s',hand] ;

X = 'Armored Cancrix' ,
Y = ['Return',target,creature,to,its,'owner''s',hand] ;

X = 'Azure Drake' ,
Y = ['Return',target,creature,to,its,'owner''s',hand]

(Did I mention that I’m working with the creatures from the M11 introductory decks?)

“phrase/2″ is a Prolog predicate that checks whether something is a valid phrase according to our grammar. If its second argument is left uninstantiated, it returns every valid MGL expression that can follow a call to target(X) (it does that in subsequent backtracking, when the user enters “;” in the console). Since X itself is a variable, phrase/2 also returns each valid target for each targeted effect it finds. In short, it generates pairs of targeted effects and their valid targets. If we keep asking it to backtrack, (by entering successive “;”s in the listener) it will eventually return things like:

X = 'Forest' ,
Y = ['Return',target,permanent,to,its,'owner''s',hand] ;

At least it will if we have told it that a valid target for “return(X) can be any permanent type:

target(Permanent) –> ['target', 'permanent'], {permanent_type(Permanent)}.

That would be Boomerang then! A call to “return” can also bounce all of a type of permanent:

return(X) --> ['Return'], all(X), [to, their, 'owner''s', hands].
all(Creatures) -->
          ['all', 'creatures'], {findall(Creature, creature_type(Creature), Creatures) }.

The second clause defines “all creatures”, using again creature_type/1. Another clause may use a call to permanent_type/1 to return all permanents, and of course different type checking is just as simple. We could also add more logic to selectively find the permanents controlled or owned by a player and so on, but I am leaving that kind of more complicated check separately, as I said.

What else can we do with calls to phrase/2? If we bind both its arguments, we can determine whether a target is valid:

| ?- phrase(return('Plains'), ['Return',target,creature,to,its,'owner''s',hand]).
no

| ?- phrase(return('Air Servant'), ['Return',target,creature,to,its,'owner''s',hand]).
yes

This is, as they say, where the code thickens. We can use such a call to determine whether a target chosen by a player for a spell is correct and, if so, execute the appropriate effect- which is the one bound in the second argument of phrase/2. Here’s my code to do exactly that:

generate_effect(Object, Player):-
		\+ permanent_type(Object), % NOT a permanent-creating spell
		determine_effect(Object, Effect, Target),
		gen_effect(Effect, Target),
		move_to_zone(Player, Object, 'Stack', 'Graveyard').
		% ^ does what it says on the tin! "Player" is the controller of Object

determine_effect(Object, Effect, Target):-
		Object = copy(Name, _Id, State),
		% ^ The internal representation of MGL Objects in Gleemin!
		member(target(Target), State),
		% ^ State is a list of states the Object can be in.
		% target/1 is a state that defines the Object's targets.
		Target = copy(Target_name, _Target_Id, _Target_State),
		% ^ The target is itself an MGL Object.
		card([card_name Name, _, _, text_box Ability, _, _, _, _]),
		% ^ This is the internal representation of M:tG _cards_ in the db.
		% Remember that the Ability is a list of words separated by commas.
		sublist(Effect, Ability),
		% sublist reads in the Abilty text, word-by-word,
		%  then passes each word-list it constructs on to >
		phrase(effect(Target_name), Effect).
		% phrase/2 will fail while sublist is passing it invalid
		%  effect-phrases. Each failure will cause Prolog to backtrack
		%  into sublist again, generating more permutations of the
		%  Ability word-list. When phrase/2 is passed a correct MGL
		%  effect-phrase, it will succeed and bind it to its second
		%  argument. At that point, deteremine_effect will succeed and
		%  return the effect text, bound to Effect. Then...

gen_effect(Effect, Target):-
		Effect = ['Return',target,creature,to,its,'owner''s',hand],
		% ^ This is the word-list returned by phrase/2 in determine_effect!
		Target = copy(Name, Id, _State),
		% ^ The target is an MGL Object...
		owned_by(Target, Owner),
		% ... its owner is bound to Owner...
		move_to_zone(Owner, Target, 'Battlefield', 'Hand').
		% ... and returned to that player's Hand. Sbroinnng!

This is a substantial quantity of code. I hope it doesn’t hurt your eyes too much An uppercase word in the head of a rule, signifies a variable that must be matched in the body of the rule. This is how Prolog passes information from the head of a rule to the clauses in its body. So, for example, in the body of gen_effect (er, I need to rename that! Sorry!!!) you can see that “Effect” is bound to the list of words that is Unsummon’s ability. If this pattern-matching fails, gen_effect will fail and Prolog will backtrack, until it can find a clause of gen_effect with an instantiation of Effect that holds true. If we were trying to cast Boomerang, we’d stop at a gen_effect clause starting with:

	gen_effect(Effect, Target):-
		Effect = ['Return',target,permanent,to,its,'owner''s',hand],

This all probably looks like, well, magic, to anyone who hasn’t spent the last, um, er, uh, oh my god, five months of my life, furiously coding in Prolog! I admit it can be a lot to take in, at a glance. But I hope you can get an idea of how the MGL parser/ interpreter works and does its thing.

So we have managed to make our program read MGL directly. Is it really worth it? Well, like I like to say, nothing happens by magic in programming. There’s still lots of coding to do, in order to add more effects and abilities. However, with this code we have already covered most targeted effects, as long as they don’t have any targetting restrictions beyond type. We can keep adding clauses for effect(X), to handle different effects:

	effect(X) --> tap(X).
	effect(X) --> untap(X).
	effect(X) --> destroy(X).
	effect(X) --> regenerate(X).
	effect(X) --> exile(X).

Then define their targets syntax:

	tap(X) --> [tap], target(X).
	tap(X) --> [tap], all(X).

And so on. The target(X) and all(X) rules don’t need any addition (except to add new types of permanents and also players and zones) Of course, each effect will need its own code, in order for there to be something to execute, but already we have a template for that. Unfortunately this is where Prolog’s weaknesses begin to become apparent: there’s a lot of copy/pasting to be done. Prolog is not Object- Oriented, so code reuse is an issue… though of course there’s remedies, but never mind that for now.

The good thing is that most effects are simple state transitions of the Magic Virtual Machine, all of which need to be defined in the main engine anyway. For example, as we have seen, MGL Objects have a State list that represents their, well… state. In Gleemin, to put a permanent in a ‘tapped’ state is to add ‘tapped’ to its State list. This is done by change_state/4, a predicate used by tap_untap to do what it sounds like it would. The same change_state/4 predicate can be used to append ‘destroyed’ to a permanent’s State list. A permanent that is destroyed is moved to the graveyard as a state-based effect (when a player next receives priority). This too, moving Objects from zone to zone, is an essential part of the MVM functionality, handled by calls to move_to_zone/4 (note it’s used in Unsummon’s effect, above). move_to_zone/4 is used to draw cards (moving them from library to hand), cast spells (moving them from hand, to stack, to battlefield or graveyard) and more.

Ideally, every ability of a Magic card should be possible to execute as a call to a generic MVM fundamental state transition predicate, like move_to_zone/4 and change_state/4. This is in keeping with my concept of the Magic Virtual Machine, as an implementation of the Comprehensive Rules. Everything that a card can do, should be defined in the Comp Rules. Ideally.

Of course, in real life things are always much more complicated than the ideal! So a great amount of tweaking should be needed, and of course my engine is still far from complete so there’s a lot of effects that it wouldn’t know how to handle. Then of course we know that Wizards will often publish errata and refine its own definitions of rules, both in the Comp Rules document and on cards themselves. The next time the Comp Rules are updated, the MGL syntax in Gleemin will need to be updated too.

So this is just a start, then. But I think it’s a good start.

I hope you’re still here, after this mammoth post. Well, judging by my previous output, you probably have a couple of months to read this through anyway

Until the next update, good luck and have fun