Last Known Information with Undo

Last Known Information is one of the hardest parts of the Magic rules to implement. It is important when handling effects that use a card that changed zones, for example Persist ("When this permanent is put into a graveyard from the battlefield, if it had no -1/-1 counters on it, return it to the battlefield under its owner's control with a -1/-1 counter on it.") or Swords to Plowshares ("Exile target creature. Its controller gains life equal to its power."). These effects happen when the card is already in the graveyard/exile, but need information of the card when it was on the battlefield. For us, this seems very natural, but from a programming point of view, we have to save the relevant values long enough so that interested effects can look it up.
The two main questions of this concept are already in the previous sentence:

• What values are "relevant"?
• What is "long enough"?

An this is where Undo steps in! Why store the values separately when we can travel back in time and look at the original ones? with that approach, there is no chance that we need a value that was not saved - because we look at the original.
Well, when we talk about time travel, of course there are problems: We have to get back to the future after looking up the needed information, but this is only possible if we didn't change history: The game will discard any actions that lie in the future if we change the past. Unfortunately, even simply looking up the power of a creature will change the past, because it results in evaluating continuous effects etc.
Well, I have another science fiction reference up my sleeve to save the day: If we must not change history, "simply" do it in a parallel universe: Create an exact copy of the game up to the point in the past we need to look up the information, then use it in our regular space-time continuum.

So much for the theory of time travel and parallel universes, the reality is a bit more complex, though. I think I can eventually work it out so that this is possible. This is also the way I expect a potential AI to work: Try out multiple variants in a parallel universe and do the best in the real universe.
But right now, only regular time travel is possible, with the limits set by changing history. The problem is that I can't transfer actions between games yet: If you tap a creature, I can't copy that action and execute it in another game, because the action stores the permanent that was tapped, which is exclusively associated with that game. The solution probably needs hashing or another type of identifier associated with each part of the game.

I hope you enjoyed the short Science-Fiction sequence. I definitely did, and I would never have guessed to talk about Time Travel and Alternate Universes as a serious metaphor for a programming problem.

Simultaneity: Warp World

The first time I mentioned simultaneity is with combat. It was just a coincidence that this was the first time, but it is very reasonable, because simultaneity happens very often during combat: Technically, creatures become attacking creatures simultaneously, then the same happens with blockers, damage etc.

Simultaneity means multiple things, and I'm not sure if I have a full understanding of these. I'll take the example of Warp World, which is a classic example for discussing timing:

Each player shuffles all permanents he or she owns into his or her library, then reveals that many cards from the top of his or her library. Each player puts all artifact, creature, and land cards revealed this way onto the battlefield, then does the same for enchantment cards, then puts all cards revealed this way that weren't put onto the battlefield on the bottom of his or her library.

First, all permanents are shuffled into their respective owner's library, triggering from leaving play. All these abilities see all the cards leaving play, meaning that an ability like "leaves the battlefield" sees all the permanents. There is no variant where that ability leaves early and isn't active when the permanents leave play.

The "then"s in the card's text neatly separate the parts that happen simultaneously. All "enters the battlefield" abilities of cards trigger for cards that enter the battlefield at the same time as them; it seems like the abilities are active just a little earlier than they are in play... it's a little awkward in my opinion.

now hold on - Auras with "Enchant Enchantment" won't make it on the battlefield, because Enchant is not a triggered ability. The Comprehensive rules don't specify a wording for Enchant but rather give it extra rules. It feels, however, like a replacement effect, just like "As ... enters the battlefield" (which don't use the stack at all - they are effects generated by static abilities).

Lands with additional costs, like the painlands, are worded like this, because if it was a triggered ability, you could play the mana ability in response to the cost. So, just like "Enchant Enchantment" enchantments (^^) don't make it, lands like "As ... comes into play, return a land you control to your hand. If you don't, put ... into your graveyard instead." won't, too. Champion, however, is a triggered ability, so your champions can survive. you can even enchant the creatures you wish to exile, because the triggered abilities won't resolve or even be put onto the stack until Warp World finished resolving.


One last thing: after resolving the spells, all the abilities are put onto the stack, in an order depending on player seating and player choice. you can put abilities from entering the battlefield on the stack earlier that those from leaving the battlefield, even though these happened in another sequence...

Code online!

I don't have anything runnable, but I understand that talking about something you can't touch doesn't draw much interest. Well, "touching" over the internet is a vague concept, and code isn't physical, but putting my code online is as close as it can get. you can find it at http://code.google.com/p/laterna-magica/, and download it via SVN. The code is located in svn/trunk/laterna.

Well, as i said, it's not a runnable game or something, but you can still see something:
magica.card.utils.LaternaMagica shows a JTextPane that is filled with a String including mana symbols.
magica.card.impl.MagicObjectImpl features the layer system. It applies some effects to a simplified Llanowar Elves (just a 1/1 Elf for G):


//nothing runs without a game!
Game g = new GameImpl();





//The matcher defines a set of cards to be affected
Matcher m1 = getCardMatcher(getMatcher(ENCHANTMENT));
/* Then, an effect is registered in the game with that matcher.
 * In sum, this represents a static ability saying,
 *  "All enchantments are green."
 * Well, not exactly. It's more like,
 *  "All enchantment cards in all zones are green."
 */

g.getGlobalEffects().getEffects().put(new ColorChangingEffectImpl(g, ADDING, GREEN), m1);


/* 
 * This creates a Llanowar elves card (currently,
 * CardTemplateImpl implements a Green 1/1 Elf)

 */

MagicObject card = new MagicObjectImpl(g, new CardTemplateImpl());
 
//Here are some effects - should be obvious
//The order matters here - the effects get timestamps

CharacteristicEffect e1 = new PTSwitchingEffectImpl(g);
CharacteristicEffect e2 = new PTChangingEffectImpl(g, 0, 2);
CharacteristicEffect e3 = new TypeChangingEffectImpl(g, ADDING, ARTIFACT);
CharacteristicEffect e4 = new TypeChangingEffectImpl(g, SETTING, ENCHANTMENT);
CharacteristicEffect e5 = new OverridingCharacteristicEffectImpl(g, L3, MANA_COST,
        ManaFactoryImpl.INSTANCE.parseSequence("{R/W}"));


//All these effects are added to the card.

card.getEffects().add(e1);
card.getEffects().add(e2);
card.getEffects().add(e3);
card.getEffects().add(e4);
card.getEffects().add(e5);

//now, the result is printed out

CardCharacteristics c = card.getCharacteristics().get(0);
System.out.printf("%s - %s%n", c.getName(), c.getManaCost());
System.out.println(c.getColorCharacteristic());
System.out.printf("%s %s - %s%n", c.getSuperTypeCharacteristic(), c.getTypeCharacteristic(),
        c.getSubTypeCharacteristic());
System.out.printf("%d/%d%n", c.getPower(), c.getToughness());



Running this will give you the following output:
Llanowar Elves - {R/W}
+[White, Red, Green]
+[] +[Enchantment] - +[]
0/0
The card's name is Llanowar Elves, and it costs R/W. Red and white come from it's mana cost, and it's green again because it's an enchantment. Because It's not a creature, if doesn't have the "Elf" subtype, and also no P/T

Traps in the rules system

I think you can divide the rules in several complexity stages:

• The "dumb" parts, like damage assignment order. These are things that aren't too hard, but you have to do them. When assigning blockers, you have to store a collection of the blockers anyway, letting the user sort it is not much more work. Another thing is mulligan, this is a check at the beginning of the game, and you just do it or not.
  
• The challenging parts. I consider the layering system of Magic is such thing. The layering system is quite complex: Effects that modify different characteristics are applied after each other, so you have to store the basic characteristics (as printed on the cards) and the effects that modify it. it's not enough to store the results, because of cases like:
  some 1/1 creature
  attach Bonesplitter (+2/+0) --> 3/1
  switch P/T --> 1/3
  unattach bonesplitter --> -1/3
  well, this is obviously wrong. you have to do a bunch of work (not dumb work, though) to get this right, but it's not undoable
• The very hard parts. I think text-changing and replacement effects fall under this category. text changing effects require a very good structure for storing card text, that makes it possible to change any interesting part. well it may be simple to change "Goblin" into "Elf", but think about changes like "Choose one" into "Choose two", that don't only affect what the outcome of the effect is, but actually what happens.
  Replacement effects have a similar problem as Triggered ability. Both need an event system that makes it possible to track changes to the game, but replacement effect don't only listen to events, they also negate those events on the fly.

obviously, the second category is the most fun to program. i actually have a working layer system, it took me around 3,500 lines of code in about 40 classes.