Sunday, August 8, 2010

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.

6 comments:

nantuko84 said...

I like Alternate Universes as well as the fact that your project now uses maven :)

nantuko84 said...

your ActiveChangedListener.Internal extends DrawListener. I believe it should have extend itself, right?

Silly Freak said...

"your ActiveChangedListener.Internal extends DrawListener. I believe it should have extend itself, right?"

right, must have slipped through somehow...

"I like Alternate Universes as well as the fact that your project now uses maven :)"

yeah, maven is cool. I wanted to write about it by now, but I'm still experiencing problems with the new TreeProperties and Utils project. I'll come back to it once that's sorted out.

Forge said...

Warp World is insane and hats off to you for even trying it. Personally I don't understand last known information at all.

I presume you are using the Comprehensive Rules as your guide. The Magic Set Faqs are also good. Checkout the Magic 2010 faq for a detailed explanation of Warp World.

I can't wait until you get something working :)

Incantus said...

Hey Silly Freak,
I had the same problem. I don't have an undo architecture, so I couldn't use that approach, but the idea I came up with is that each card has a set of roles that exist in each zone. I separate the meta-identity of the card from the roles it takes, and those roles (such as OutOfPlayRole, StackRole, PermanentRole, etc) are what the game actually references for characteristics, damage, etc. So when a card changes zones, it instantiates the role that it will become and returns that to the game engine. The great thing about this approach is that when the card leaves that zone, that 'role' object is a frozen snapshot of the way the card looked right before it left. Also, any effect that referenced that card would have a reference to that role object, and when nothing else needed to access it the role would be garbage collected (although I have been considering the possibility of storing the chain of previous roles with the card, but I haven't seen a need for it yet).

Silly Freak said...

This is a great idea! I hope that undo works as good as I hope/expect, but it's good to have a fallback plan

in one way or another, my program will have such thing for targets: when a targeted card changes zones, it is an illegal. I'll need to handle that in a similar way, when the reference is "lost" when the card changes zones