Laterna Magica: MtG programming

Entities and values

2012-01-10T10:33:00.001-08:00

As so often in programming, one big question arose when I worked on my Undo/Replication framework: What is an entity, and what is a value?

I use the word entity to make clear that I mean something different from objects. An object is something identified by an address pointer, whereas for a primitive value, its bytes in memory directly represent the value instead of an address. What I mean with entity/value is best explained by an example from databases:

Suppose you have a database table storing the data of a company's employees. There is a surname, a prename, a birth date, and so on. Besides others, there's an address. The simplest approach is to handle each of these items as a table column: Surname and prename are strings, the birthdate uses a special date column type. The address can also be simply taken as a string, but there are other ways:

An address is composed of a street name, a number, probably also an appartment number, country, state etc. It could be beneficial to store all these data in a table on its own, give it an ID (the database way of saying address), and only reference this ID in the employee table.

Don't forget the third way! You could use all those columns, but put them directly into the employee table, so there would be prename, surname, birth date, street, stree no., appartment no., etc.

What's the best? Of course, it depends! Variant one is easy to use, but lacks intrinsic validity checks: When the database doesn't know that something should be an (appartment) number, how should it check it's even a number? Variant two can handle a very specific case "better": two workers have the same address. In this case, the same ID can be referenced multiple times, so that both employees not only have equal addresses but also have the same one. In this particular case, the benefit is not too big, but there are use cases where it's important that something can be referenced. About the third, it really combines the downsides of the both above... I personally see no benefit in using it. It there are, I'm sorry I didn't see them.

Now, what should have triggered your attention was the word "ID". As soon as something has an identity, it's an entity. Note how the prename is a String, which is an Object type in Java, but only a value. On the other hand, the address in case 2 has an identifier and is an entity.

And now we're back: What I do is to assign IDs to the objects I want to replicate. The objects have values which can be changed, and I transmit changes like "property XY of object 01 changed from 'ab' to 'cd'."

And now the big question: what about collections? Should it be "element 'ab' was added to list 01" (i.e. they are entities) or "element 'ab' was added to list XY of object 01?"

Replicating Game States - JGroups

2012-01-07T04:55:00.000-08:00

So now I've got it. My goals in implementing Replication was to keep it out of the core functionality while still making it easy to use without worrying about replication yourself. How do you do that? By providing a general interface to other software (in my case, that's a listener) and implementing a specific one for the task at hand.

So my History class, which stores all changes to the managed objects, has a listener for two possible events: A new modification is executed; and the "current" state is moved somewhere else (e.g. undoing something.) My replication listener does not support undo right now, because I haven't figured out how to best identify a state (which is where the program is going) yet, but that should be easy. The other thing, executing modifications, does work. That means, whenever a modification is executed locally, it is sent over the network so that the partner(s) can execute it too.

The only downside is that the partners also "execute it locally", so I had to use a trick to suppress resending these received modifications. And it works pretty well:

//initialization code
final History h = createHistory(createKey("test-history"));
final JChannel channel = new JGroupsReplicationListener(h) {
    @Override
    public void receive(Message msg) {
        Modification m = (Modification) deserialize(msg.getBuffer());
        if(m instanceof Creation) id = ((Creation) m).getId();
        super.receive(msg);
    }
}.getChannel();

//executing the actions (creating an object)
h.pushHistoryForThread();
try {
    TestBean t = (TestBean) h.getObjectStore().get(Creation.create(new TestBean()));
    t.setA(1);
    t.setB(1);
} finally {
    h.popHistoryForThread();
}

//printing the results
System.out.printf("current state: %s%n", h.getObjectStore().get(id));

I made this test a GUI application so that I can control the timing on multiple virtual machines. The public void receive(Message msg)seen above is only needed for this Test, again. It's not necessary to do something like that to get the replication. The code in the middle looks exactly the same as the example last time, except I haven't hidden some of the details in a setTest() method.

Now what's probably the most interesting is how the networking works; let me tell you, I didn't write any! As hinted by me before, and in the title of course, is that I have tried JGroups to do this. In JGroups, you create Channels and let them join into a cluster; all channels in the cluster can receive and send messages, either to only only one recipient, or to all at the same time. JGroups provides a configurable protocol stack that takes care of reliability, synchronity and such things. For my tests, I have used a UDP-based protocol stack. For wide-area connections, a TCP-based approach is probably easier.

Replicating Game States - Working code!

2012-01-05T12:13:00.000-08:00

Before you get too excited - no, there's no multiplayer yet (well, who would have guessed that...). There is, however, working code for undoing and redoing actions (even with multiple, branching histories), and even for replicating the state on multiple virtual machines.

The key to make such a library is that it looks like ordinary Java code from the outside, so that others can use your code without wondering why it looks so weird. Let's take a look:

//Test t = new Test(); is an attribute

//replaced angle with square brackets because of HTML markup
List[StateStamp] states = new ArrayList[StateStamp]();
History h = createHistory(createKey("test"));
h.pushHistoryForThread();
try {
    states.add(h.getCurrentState()); // 0
    print();

    setTest(t);
    states.add(h.getCurrentState()); // 1
    print();

    getTest().setA(1);
    states.add(h.getCurrentState()); // 2
    print();

    getTest().setB(1);
    states.add(h.getCurrentState()); // 3
    print();

    Deletion.delete(getTest());
    states.add(h.getCurrentState()); // 4
    print();

    h.goToState(states.get(3));
    print();
    h.goToState(states.get(2));
    print();
    h.goToState(states.get(1));
    print();
    h.goToState(states.get(0));
    print();
} finally {
    h.popHistoryForThread();
}

It's probably easy to to guess that print(); prints the current state of the test object. Besides that, the only code that looks different from normal operations is marked in bold. Most of it is only necessary for this test case: storing the previous states so that you can go back. Really mandatory is only the colored code (and the actual functional code of course, but that doesn't count.)

Of course, a history for the modifications must be created. Then, the history is set for the thread: Code running in the thread (that is, everything in this method, and nothing more) can access the history without passing it as a parameter (which would make using the library awkward) or declaring it as a static variable somewhere (which is ugly from an architecture standpoint.) Everything after this is wrapped in try/finally, so that the last method is not skipped in case of an exception: this removes the association of the history with the current Thread.

Of course, implementing setTest(), setA() etc. is different from a usual simple setter. But the point here is that using the code is as simple as shown here. The result is this:

Test@732A54F9[a=0, b=0] not in store
Test@7A6D084B[a=0, b=0] in store
Test@7A6D084B[a=1, b=0] in store
Test@7A6D084B[a=1, b=1] in store
Test@7A6D084B[a=1, b=1] not in store
Test@15301ED8[a=1, b=1] in store
Test@15301ED8[a=1, b=0] in store
Test@15301ED8[a=0, b=0] in store
Test@15301ED8[a=0, b=0] not in store

You see here how the test object runs through different states up to its deletion, then goes back to its initial state. What's not shown here, but is working, is adding another branch to this history. Of course, the actual objects have only one state at a time, but the history can be switched arbitrarily between multiple histories:

This is the actual test case I ran: I went back to the state after creating the test object, changed its a value, and then switched over to the state before, and then after, deleting the test again.

I have code for replication of states going, but it's not yet as clean as for undo: a lot of handling is necessary for the network, which should be transparent to the user. I'll show it once I'm finished, but in the meantime you can look here.

Quantum Mechanics and Magic AI

2011-12-31T19:37:00.000-08:00

Okay, the title is kind of a stretch, but Quantum Mechanics sounds so much cooler than probability...

So what do I want to talk about? One thought that I often have is that the computer has the advantage of perfect memory. If it once views your hand, it can perfectly memorize all the cards in it. It follows that it can say that as long as a card doesn't leave your hand, you still have it in hand. But when the game progresses, things get more vague: You shuffle cards into your library without revealing them before. Here, probability comes into play.

I assume that the computer knows my deck list for simplicity. (It could even use heuristics to guess what cards might be in your deck, but that only complicates the matter.) At the beginning of the game, before even drawing your opening hand, each card in the library has an equal chance of being one of the, say, 60 cards in your deck. For example, in your mono green deck, a card has a 24 in 60 chance of being a forest. These chances don't change as you draw seven cards, at least from the computer's point of view. Even so, the computer can say that the probability of you having a Giant Growth in hand is (# Giant Growth in deck)/(# cards in deck)*(# cards in hand), and it can have "fear" that you might play that card during combat. The greater the probability, the greater the fear.

Now comes the "collapse of the wave function": the computer observes the cards in your hand. (You see, I can even use QM terminology here ;)) Suddenly, the probability of every of the cards in your hand becomes 100% for the card the AI has observed. Technically, as the hand is not a sorted zone, the AI should not remember which card is which. Let's say you have 4 different cards in hand, then the AI can assume that every of the cards has a 25% probability of being any of these cards.

When you now shuffle one card back into your library, nothing really changes, except that there's only 3 cards for a total of 75% per previously observed card.

I hope that it's clear what I'm saying. I have the feeling to make too many words about a simple concept, yet at the same time I feel that all this seems abstract and not very understandable... well, I should have made some images, but I'm too lazy...

Let me end with this: Magic is a game of uncertainty, and luckily the computer has the capabilities to process these. When an AI can make decisions based on what it sees, why not on what it doesn't see? Assigning these possibilities is pretty simple; every card in the game has a total of 100% of being some card from the deck list, and every card in the deck list is represented to 100% among all cards in the game.
The problem is to design the AI to use that information; it's often hard enough to process the known information, so even more the unknown. But in principle, there's no difference. And even if it is too hard, there are some shortcuts: If you have only one Morph card and play a Morph card, the AI knows which it is, even though it's face down. Such probability collapses can happen all the time, and it would be a waste to let them go unconsidered.

Replicating Game States - revised

2011-12-31T08:53:00.000-08:00

The last time I talked about my Undo system, which should also allow multiplayer through its structure of storing actions that can be transmitted over the network, was a long time ago. I don't want to directly talk about this today; you'll see.

Especially one thought has gone through my mind in the last weeks: Replicating a state across the network properly is nothing specific to Magic - so why do I implement it in the Core of Laterna Magica? I thought about it, and there doesn't seem to be a specific reason for doing so. Another result of that thought was that there are probably complete libraries out there which do exactly what I want. Well, that's unfortunately not the case, so I'm stuck/blessed with implementing it myself.

I haven't really gotten into development yet. I have a rough skeleton, but no really fancy functionality yet. But I'm having my thoughts. I think stepping away from the application's needs and looking at the general requirements of such a library help in developing a better piece of software. I haven't done this for my current undo system, which I find kind of disappointing. Normally, I don't have problems with spotting such generalizations.

Okay, back to topic: what does a library for state replication need?

There needs to a notion of what has happened on a higher, application level: Transactions
Transactions consist of atomic modifications, which are the core of the state

Optionally, they may also consist of other sub-transactions

Transactions and modifications must be transmittable over the network. If the whole state is represented as a tree of subtransactions under a root-transaction, then there's of course the need to transmit unfinished transactions. Otherwise, it might be enough to transmit finished transactions. I think that the first is generally more flexible. It might be a good idea to give the user a chance to mark transactions as atomic so that it's only transmitted when it is finished.
Probably the most interesting requirement is that, of course, after transmitting the state, both/all states have to be the same!
The system should be able to detect that there are state conflicts and that a transmitted transaction can't be carried out locally.

When we're already speaking of it, it's probably nice (but also probably impossible, so see that as an utopic remark) to resolve/merge such conflicts.

Now guess what I have an example for! Of course for the "most interesting" one in my list! It might seem at first that by defining modification, and making them granular enough to catch all actions in a system, there is no way that states may get out of sync. That's unfortunately not true. Let's take a simple case. This case actually only has a theoretical problem, but it's easier to illustrate and serves the purpose. Our state consists of two variables, foo and bar. The user may only set foo, and when he does so, the program automatically changes bar. Now consider this:

When the state replication system transmits these two modifications, the receiver does its own set operation on bar, because foo has changed. Then, the original set operation is transmitted, setting bar another time (fortunately to the same value).

Until now, I thought that this particular case is just me wanting to be clean. Now that I wrote this, I even see more problems, real ones: If we're able to detect conflicts, then this shouldn't even run through, because the last modification should be the second but really is the third. And even if we don't: this second modification in State 2 needs to be transmitted to State 1. Even if that doesn't result in errors, which is likely, it will waste network bandwidth at least.

Now for the real problem I spotted here before: Let's replace "bar = 1" with "put a token onto the battlefield". Setting a number multiple times is redundant, but creating an Object is not. There is a very definite difference between one and two tokens, you know!

Now, let's solve these problems. There are basically two ways that can lead to this problem: a complex setter, and events.

In the first case, the setter for foo includes code that calls the setter of bar. The problem here is that our replication library can't know that setting foo doesn't really do this: it actually sets foo and bar. So, refactor foo's setter so that it does only what it says, and not more. Hide this from the user by adding another method doSomething() that does what he previously did by setting foo.

Second is events. In this case, the change to foo fires an event that leads to bar being changed as well. In this case, the simple answer that is not so simple to implement is: don't fire events while replicating the state. The more complex answer that is simpler to implement is that this is similar to the first case: Don't write events that fire on state changes and perform state changes. Instead, fire a new Event in doSomething() that triggers the change. As the state replication won't call doSomething(), everything is fine.

Both solutions shown here require changes in the application, not in the library. This might seem bad, but it's actually logical: The library may sanely assume that variables change and objects are created, and that it may do that by itself as well. If the state does not fulfill the contract that it just contains values, but instead employs complex logic that the library can't predict, the task is impossible. The library needs some way to change values without triggering application logic.

Thanks for staying wiht me, and a happy new year to all of you!

Java 5 compatibility is hard

2011-12-30T12:24:00.000-08:00

From the times when I read the bug thread of Forge (about a year ago or so), it seemed to me that a lot of users, especially those on Macs or at work, were still using Java 5. I have no idea how it is now, but I still try to code and compile Java 5 compatible for exactly that reason.

Usually, it works out one way or another, but not today. I wanted to try JGroups (a story for another time, after I actually succeeded in it), but even the releases that are advertised (if you can call it that) as Java 5 compatible seem to be compiled in the Java 6 binary format. Since only part of the featureset I'm trying to implement depends on JGroups, I wanted to at least create compatible class files, even if using these features will fail on a Java 5 runtime.

There are basically two inputs to the compiler: my own Java 5 compatible code, and the already compiled Java 6 compatible bytecode. My output of choice was Java 5 compatible bytecode. After all, this output does not contain anything not Java 5 compatible, so I thought I was good to go. Using a Java 5 compiler will of course fail, because it can't read the necessary classes, but Using a Java 6 compiler with compatibility settings should work...

There are a few features new in Java 5, like generics, annotations, enums and for-each loops. It sounds reasonable that compiling Java 5 source code to Java 1.4 byte code won't work. Java 6 also has a new byte code format. It supports a new verification mechanism, and while the compatibility notes say that the compiler outputs this format only "by default", there is no way (I have found, at least) to change it: The most obvious way of setting the compiler arguments: javac -source 1.6 -target 1.5 gives an errror that source release 1.6 requires target release 1.6 - which exactly contradicts what is said in the compatibility notes.

It turns out that the Java 6 compiler can take Java 6 bytecode input even if the source setting is 1.5. That there's an error for 1.6 + 1.5, even though the Java language hasn't changed, is kind of absurd in my opinion... well, better having an absurd solution than none at all...

Getting more out of Maven

2011-12-26T15:58:00.000-08:00

When I switched to Maven, I knew I wasn't using all of it's potential. I'm sure I still don't, but I've learned much nontheless. For the last months, I worked (for pay, that is) on another software project. The necessary steps to build the software were nontrivial, and I had the task and thus the time to research how to do it. Over the months I worked there, the project's POM has become a stably working thing, whihc indeed is nice when trying a relatively new technology. Speaking of new technologies, I finally managed to learn a little LaTeX, when we had to do the docs in the end... but that's another story. I wonder if I'll be able to ever bring that into a Magic context.

Now that my internship/scholarship ended, I had a little time and wanted to clean up the messy POMs I previously created. My first step was to update my eclipse version. 3.7 Indigo comes with a new version of the Maven plugin. While I was sceptical during my internship, I found that it's pretty usable now. It even has some nice features that make it feel superior to the old one, e.g. the ability to jump to definitions of replacement variables, plugins, dependencies etc.; and the ability to view the "effective" POM. While the old version had that, I was never really sure it worked... could be that my POMs were just so simple that the physical and effective POMs were the same... Whatever, what I experienced was that viewing the effective POM of your project actually shows you how much configurations there are you could take a look at.

I have the feeling that when one tries a tool to automate something, it first seems very nice and practical. Unfortunately, many tools show the "bad behavior" that when the ammount of things to manage grows, even that becomes confusing.
The same thing was with Maven. The only feature I previously used was to declare a project's dependencies. As the Laterna project grew by separating parts of the software into different projects, there were now many components which had dependencies. Let's say I discover a bug in the Config file format project and increment its version number. If multiple modules depend on the file format, I have to change three things in total: the file format version number, and the two modules' dependency version numbers.
As an alternative, I could try to have the dependency number only in one module, and since the second module has a dependency on the first (let's just assume that), it has an indirective dependency on the (now) new version. But that's also not a clean way of doing it; at least if the second really needs Config on its own. When the first module is changed so that it doesn't need config any more, this would mean I had to include it into the second then, and that's not too nice.

Well, luckily, there's two features of Maven which do the job together. The first are the "management" sections: these declare configurations (such as versions) for dependencies, plugins and other things, without making them effective. Together with the second, this even sounds like something useful: parent projects.
Every project can have a parent project from which it inherits its configurations. The dependencyManagement section allows me to specify dependency versions for every library in the parent POM without mandating that every child POM depends on all the libraries. The child POM can then add the identification of the library in the dependency section, and all the configuration from the management section applies to it.
The same goes for plugins: I can specify that if a project uses the antlr plugin, it wants to invoke antlr's code generator so I don't have to duplicate that code over and over.

So, I learned something new and exciting about Maven. I really like the design of it, how the predefined lifecycle is combined with the ability to add any plugin to do whatever job is necessary, and not only there's a way to do the necessary things, there's even a way to specify them in a clean, reusable manner.

The Oracle Parser

2011-10-24T03:01:00.000-07:00

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 18^th, #14 to #19 was on 19^th, #20 to #28 was on 20^th, the others were on 21^st and 22^nd.

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!

What has gone on - Part 2

2011-10-21T03:16:00.000-07:00

Okay, I'm back, and as Google Code nowadays also supports Git, I stayed with it. The wretched old structure where LaternaMagica resided in the same SVN repository with diverse libs is now also gone, as google seems to support multiple repos per "project" now. So you can check out and commit changes to the different libraries without incrementing the revision number of the other projects. And for everyone too lazy to explore the multitude of individual projects, here is an overview.

What has gone on - Part 1

2011-10-21T01:28:00.000-07:00

A lot, actually! Ever since the beginning of August, I found some time again to work on Laterna Magica. In my time "away" I have grown fond of the GIT version control system, using it together with SmartGit.
Two of the things I like about it: Branching is not only central to, but also easily done in GIT, and you quickly lose your fear of it. The second is that it is distributed, which was important because I have no private SVN server available where I work now. The nice extra of this is that many operations are just so much faster than with SVN, because branching, history, committing etc. are all local. The downside is that, even though I try to be a good kid and commit and document my changes, I am the only one to see them...
Which has to be changed! I'm going to upload my projects now to a git SCM site and them come back to post a little about my changes!

Forward and backward chaining

2011-01-06T11:45:00.000-08:00

In the context of rule-based systems, programming means to create rules which are applied by the engine to a fact base. Forward and backward chaining describe the two possible ways how the engine may achieve this. I found a neat explanation here.

Forward chaining starts with the facts: If a fact which triggers a rule exists, the rule is activated and may in turn modify other facts, and so on. A possible rule could be "if the floor is dirty, clean it"; it specifies when to do it

Backward chaining starts with a goal and tries to find the necessary rules to achieve it. The engine goes back through the chain of causality to find the first step. A backward changing rule could be "to achieve a tidy floor, clean it"; it specifies how the goal can be reached, but doesn't explicitly state when to do it

Both mechanisms are of course constantly used by humans, but the reasoning seems to be very different, or otherwise most rules engines would support both.

Forward chaining can be used for implementing the rules, like triggered abilities, and possibly state based actions. Even activated abilities could be handled by modelling them as a sort of triggered ability which "triggers" on playing it.
Characteristic changing effects can be handled effectively, because a rules engine watches its facts and can determine whether it's necessary to recalculate characteristics.
This is actually the main reason I want to use a rules engine. My current approach recalculates characteristics every time they are read, which... well, I'm repeating myself. By getting rid of this need, I hope to have easier access to the core engine from other parts, like AI, GUI and network.

Backward chaining is interesting especially for the AI: Backwards chaining tries to find a way from a current state to a goal, which is exactly what's done in a game. Drools, the rules engine I'm most likely going to use, does not support backward chaining yet, but the project plans to support it in a future release. Since the AI will be modular, such a backwards chaining AI could be supported once it's possible.

Distributed objects, undo and proxies

2010-12-26T09:32:00.000-08:00

I have mentioned a couple of times that the undo system should enable multiplayer games, because every action is encapsulated as an object which can be transmitted over the network and executed there.

Well, that's only half of the story. For the action to do something, it needs references to the affected objects. This means that transmitting an action also means transmitting the dependent objects; in the worst case, the whole game-state is transmitted every time, because all of the objects are interdependent.

And even so, the desired effect is not achieved: the action operates on the transmitted game state, not the one which belongs to the communication partner. The same is true for writing a game state to file, to restore it at a later time. I have been aware of this flaw for quite some time, but ignored it as a problem to the distant future. Now that I have to rewrite the characteristics system anyway, I might as well face this problem too.

One possible solution is proxy objects: A proxy object acts as the communication link between a client and a provider. Proxy objects are commonly used for distributed systems, where the proxy implements the intricacies of accessing the provider over the network.
My use would be similar; instead of passing objects directly to an action, only the proxy is passed. The proxy communicates with the actual object, but instead of transmitting it over the network, the proxy is attached to the other side's equivalent of the object.

This approach has its own downsides, of course: Java has a built-in proxy mechanism which makes it relatively easy to implement transparent proxy classes. It requires to use interfaces for everything, which isn't automatically a bad thing. Designing the interface is moreso:

RMI, Remote Method Invocation, uses proxy classes for transparent - well - remote method invocation. Because network communication can go wrong, this means that every method in those interfaces must declare RemoteException as a possible error. Declaring this exception seems very dirty, because it doesn't have anything to do with what the interface is about. Not declaring it takes me the (direct) possibility to use RMI for a central game state instead of duplicated game states. A workaround would be to use another proxy around the RMI proxy, which only throws an unchecked exception. This seems dirty again, but better than declaring protocol-specific exceptions in an application-level interface.

"Re-attaching" a proxy to the game state on another machine is the next problem: somehow, the transmitted proxies must get access to the new gamestate on the receiver's side. I think that a custom ObjectInputStream which provides this information may cover that.

The third, and probably hardest problem, is the question of object identity: How do I identify identical objects on both sides, so that the right object is attached at the receiver side? RMI's advantage in this regard is that it's not even necessary to do that, because objects are not duplicated. I have yet to find a solution for this problem, wish me luck!

Rule-Based Programming and Magic

2010-11-18T14:48:00.000-08:00

Although I don't have time to work on Laterna Magica right now, I have the occasional thought on it. Before the big pause, I noticed a major flaw in my implementation of characteristics. The problem is that every read-operation on the characteristics refreshes the status. This status change means that only in-game operations may read characteristics; I mentioned a couple of times that, to achieve independence of game and GUI, the GUI must not change the game state.

...and what does this mean in the context of rules-based programming? Let me first explain that term in greater detail: In the last months, we familiarized with the (unfortunately commercial) rule-based programming language "JESS", its interpreter is implemented in Java.
A rule based system operates on a fact base. Facts can be roughly compared to variables or objects. The second important part is, of course, the rules. Rules operate on facts and may be activated whenever a fact changes. An activated rule is not immediately executed! Instead, a call to run() causes the engine to process the activated rules, which may in turn change facts and activate even more rules.

And now combine the two thoughts: The reason for me to re-evaluate characteristics every time they are accessed was to make sure no out-of-date data is used. With a rule-based system keeping track of the game state, this becomes unnecessary, because the rule system would ensure that characteristics are refreshed when necessary. And without the need to do permanent refreshes, there's no problem with the GUI reading characterics.

If anyone knows some free, Java-based rules engines, this would be a great input. I haven't done any research on this, and I won't do it until I come around programming LM again, but concrete user stories and recommendations are always great to hear.

Handling Arrays in web services

2010-11-18T05:31:00.000-08:00

I'm currently working on an assignment to implement a simple web service, and started using the following tutorial: http://www.theserverside.de/webservice-in-java/ (German). I'm not sure if that's a general problem, but the auto-generated WSDL specification, and java's wsimport code generator handle arrays... strangely. So here is my ArrayHelper class. I was searching for something along its lines, but found nothing.

The problem: The code generator generates classes like StringArrayArray instead of using java String[][] objects. A StringArrayArray object is merely a wrapper around a List<StringArray>, and so on.

The solution: Use reflection to determine what type of wrapper you have to deal with (check the generic parameter of the list) and recursively convert the wrapped lists into real arrays.

The file: is free to use and modify, comes without any kind of warranty, and is available here. It was actually tested with String[][]; I'd strongly suggest testing with primitive types before using it. please leave comments if any problems ocurr. The code is nearly 130 lines in total, 70 lines being comments (recursion, you know).

First successes in robotics

2010-10-31T07:32:00.000-07:00

Two months in this school year have passed, and a lot has happened. Most of our project work up to now was just research; we evaluated the JADE framework for distributed agent systems, the rule based language JESS, and the Protégé Ontology API, which all are Java based and can therefore run on the CBC controller.

On friday, Dr. David Miller arrived at Vienna, and our teacher wanted to have a robot prototype to show. On wednesday, we met at university to build something out of lego... which proved to be difficult, because the collection of Lego parts was very limited, and we hardly managed to connect a single motor to the lego gears. So we met at my place the next day and built a robot out of Fischertechnik which is, in my opinion, clearly superior to Lego. The result was this robot:

Each of the tracks is powered by two motors, although that didn't seem to bring much of a performance gain. The thing on top, in case you didn't recognize it, is a camera, and the robot's objective was to follow a blue ball.

We actually programmed the robot twice; once with C, which is natively available on the controller, and once with Java, which was installed on our controller at the university during summer. My part was the Java program, and I tried to add a few abstractions to later reuse the code.

As each of the tracks is powered by multiple motors, I added an abstraction for the motors, to combine multiple physical motors into one logical motor
Next was the drive and navigation. Our robot is tracked, so its steering uses the speed difference of the tracks. I tried to keep the theoretical possibility to use another type of steering, although some adaption is probably necessary.
Last but not least, the robot's construction may make it more convenient to wire it in a specific way. What actuators and sensors are on which pins can be configured, so that a new construction does not necessarily mean to change the program. Especially imagine how many times a motor may be accessed in the program, and what it would mean to change all the occurrences.

Now this is just foundation code, and the real logic, checking the camera and following the ball, was simply implemented in the main method in a loop. And that's the glorious result:

For those of you that don't understand the quiet, german comments: We have adjusted the camera for our lighting, and it already got pretty dark. For the video, we turned on the lights, and suddenly, the robot stopped recognizing the ball. So, the first thing you see in the video is me turning off the lights again, and then you can hear my teacher commenting on it^^

Ontologies

2010-10-02T13:26:00.000-07:00

One part of our project will be to build an ontology for our robot. An ontology is a model of the world, condensed into the relevant parts for a given problem. For example, our robot will have motors, digital and analog sensors, and so on. These would be represented in the ontology, but possibly more, like a simple model of the robot's surrounding: Hills, obstacles and so on.

At school, we're using a really easy-to use Ontology editor called Protégé; it also has some nice visualization features. The result might be an "owl" file; a standard xml file for ontologies that can easily be accessed from a program.

I'm just starting to learn this topic and not quite sure what the advantage of an ontology as opposed to e.g. an object graph is. Both model reality in some way, both are hierarchical and have properties, reference objects and so on.

One of the differences is that an ontology also models the objects, the individual instances. For example, you might model a city's subway network. In a class hierarchy, you could only model things like Subway, Station and whatever is needed for the model. Creating the objects will either mean hardcoding them or writing some code that reads the objects from a file; the former is inflexible and the second is error-prone and redundant. An ontology can (and will) contain the explicit lines and stations of the city along with the definitions, and neither of the above is needed.

The second diference is its position in context with reasoning. Reasoning is the main reason for the existence of ontologies, and therefore there are a few (hopefully good) APIs out there that make it easy to write statements like "how many stations are there on subway line 1?" or "should I go left or right around the obstacle to reach my target faster?"

And this is where we get to rule-based programming. Pulling conclusions out of the ontology is half of the work of writing a rule. See you next time!

Delaying Laterna Magica: Graduation Project

2010-09-20T14:36:00.000-07:00

School has totally got me now. We spent last week in Carinthia and focused completely on the project. It was a great experience and we laid much of the foundation work. Today, we got even more long-term assignments, and my impression is that the difference to our graduation project is not the amount of work, but that the teachers don't give us as much time...

Okay, enough of that. What I really want to tell today is two things. Bad news are always first, so let's get it out of the way: I won't have much (if any) time to work on Laterna Magica in the near future.
And the reason is already the good news: I have a veeery interesting graduation project together with 3 colleagues: We're building and programming a robot to attend a robot competition in the USA.

Okay, to make my excitement clear, let's break this down:
We're building a robot
I think this is pretty clear. The competition consists of a few challenges, and the robot has to reflect these hardware-wise to show optimal performance. The challenges are presented at the end of October; an employee of the competiton's organization visits us personally, because we'd be the first team from Europe to attend.
We're programming a robot
This is probably the most interesting part of it. Our project is sponsored by TU Wien, Vienna's technical university, and our job is not just to program the robot, but to do so using a rule- and agent-based artificial intelligence.

Rule-based is basically a programming approach such as imperative or functional. It means to define a program in terms of condition-reaction pairs. It is supported by a framework which checks the conditions and execites the appropriate actions. While this might not seem spectacular, think about it: have you ever written or seen a program using this approach? Note that this is not another name for an event system; events also result in a reaction, but they only allow for reactions on one-time events (if some event happens), not to states (if some condition holds).
Rule-based systems are good for modelling intelligent behavior. A human reacts to events because of the state-changes they cause, not the events themselves: If a window falls open, you close it because it's cold or loud outside, not because the window has opened.
Agent is just another word for actor. Remember how I wrote about the downloader; it's essentially the same. The only difference is that all this is now integrated into a rule system, which also changes the way how the agents exchange messages. Besides that, the concept of parallel processing stays. In our case, the focus lies on the independence of the actors to cooperatively reach a solution for a problem, and not on simpler multithreading by getting away from traditional synchronization.
Artificial intelligence always sounds good, but what does it really mean? Our parent project at TU Wien has a very specific goal: To build cooperative robots capable of disassembling Lego models. We won't get anywhere near disassembly, but the cooperation is still there, just in the software though. In the end, an artificial intelligence is always task-oriented, and the border where intelligence begins is not well-defined. The question is very interesting, but more philosiphical than technical, so maybe in a later post.

...to attend a robot competition in the USA
This is a goal we all really want to reach, but if we do will depend on how we perform. Our project is definitely complex, so if it doesn't work out too well, we won't go. I'm positive about it, though.
The competition we would attend is BotBall, organized by the KISS Institute of Practical Robotics, and we have the honor to be invited directly to the final "Global Conference of Educational Robotics", without attending any of the qualification tournaments. (I hope you can read from all this how proud I am^^)

So the last point to check for today is: This is definitely good news for me, but how is it for you? Well, I'll write about it, of course. Some things might be off-topic in terms of Magic, but artificial intelligence is definitely in, right? Be sure to check back in a few weeks, there are definitely interesting things to come!

Static and triggered abilities

2010-09-08T08:42:00.000-07:00

Laterna Magica already supports some core functionalities of Magic, but there's still much left. I don't talk about discard and such things; these are effects that just need to be coded, and then they will be there; just a new flavor of an existing thing. I also don't talk about very complicated effects. All cards currently supported in Laterna Magica use the original oracle wording (with the exception that "draw three cards" must be changed into "draw 3 cards"), which won't be possible for all abilities, but such abilities are still not what I'm talking about.

I'm thinking about really new features, like static and triggered abilities, the ability to target, or text changing effects.
Text changing effects are just very hard; they kind of break my concept of "one template, many instances" for abilities: The printed wording can be shared between cards, just its interpretation, the rules meaning, is card-specific.
Targets are currently not my goal; I don't really want to do much UI at the moment, and this in inevitable with giving the player yet another possibility to make a choice.

That neatly leaves behind the two thing I already stated in the title, and they have one thing in common which currently gives me a headache: Scope of influence.

The scope of an ability means in what places and at what times it works. For spells and activated abilities it's comparable to legality, but the big difference is that the user initiates those abilities; static and triggered abilities are around at all times.

There are two ways to handle the situation:

keep all abilities at all times and ask them if they should apply on every single occasion
let the abilities themselves handle it; registering and unregistering using some events

I don't know why, but my initial though was to use the second. Both have good and bad points of course: The first can result in a performance problem, the second might break in strange corner cases.
A more obvious, but still realistic example is controller changes: Imagine you get control of a Glorious Anthem, but it still pumps your opponent's creatures.
But even the first approach has similar issues, namely abilities that didn't exist at the beginning of the game, for example on tokens or from Auras. If you register all abilities at the beginning of the game, those would be ignored.

If you expected a definitive solution here, I'm sorry. I don't have one. There's no right way to do anything, just several ways with different consequences.

Update

2010-09-06T14:52:00.000-07:00

I was kindly brought to a windows incompatibility in my program, so I fixed this. Along with it came an update of the installation, which should make it much easier to update to future versions.

You can see the result here.

First release!

2010-09-04T10:07:00.000-07:00

This is only a short post, but one that makes me proud nonetheless.

This is the day where I put the first release version online. Don't expect too much; the basic rules including combat works, but there are currently nearly only vanilla creatures. Anyway, if you want to try it, or at least see what's there exactly, go to the forums and download it.

When you feel plainly dumb...

2010-08-31T11:22:00.000-07:00

There are time when you work on a problem and nothing seems to help. You have checked everything, yet nothing works. And then you see the obvious answer. I had such a problem today. Until now, Laterna Magica only allowed you to pay costs in advance, first adding all the mana to the pool, then activating an ability or (more likely in LM) casting a spell.

The rules allow it, however, to play mana abilities while playing spells/abilities. So I wrote the code: A piece in the cost to ask the player for input, a piece in the player to handle the GUI. and it didn't work. Clicking on a card was just not recognized.

I first thought it could be that my legality checking code was not working while a spell is being cast, but I couldn't find any line in the code that even bothered about that. Next, I suspected that the asynchronous communication between game and GUI didn't work, and enabled a few debug statements, which in turn made clear that everything went like desired. So I thought to myself: where could I easily check if the action was successfully processed? Well, in the cost, where the player was asked in the first place.

But I never got to writing a debug statement; the bug was clear and simple: While I retrieved the activate action, I didn't execute it. These are the times when you feel plainly dumb...

New Downloader

2010-08-28T05:13:00.000-07:00

Besides working on combat, I played a little more with Jetlang and created a downloader, which works asynchronously and can inform interested listeners over PropertyChangeEvents.
Jetlang's concurrency approach is centered around the actors (who performs a task/where is it performed) and the tasks instead of around the data. Normal multithreading requires you to synchronize on the data you share, while an Actor framework doesn't share data but pass it around, so that only one thread "has" it at a time.
This makes it easier to code, because it is how humans think: You don't worry that two people will write on the same piece of paper at the same time; you wait until the piece of paper is passed to you. That said, it still needs a lot of thinking: Who are the people in your program, what's the piece of paper, and when should you pass it around?

Btw, I made a little comparison between the new downloader and the one used by forge (admittedly, in which I also had a great part).

Program           After 2 minutes  For 1500 images

Laterna Magica    1500 images       2:00 minutes

Forge              200 images      10:00 minutes

I looked at the code for Forge and checked if it is roughly comparable to mine, and it was; otherwise I wouldn't have posted this. I changed two things, however: I increased the buffer size to 8 kB to match Laterna Magica, and I removed a print statement. These are pretty slow and shouldn't be there when measuring time.

Laterna Magica's downloader uses 10 threads, which means that 10 pictures are downloaded at the same time. Even though it might seem at first that it shouldn't make much of a difference, because the total bandwidth stays the same, the numbers clearly say that download speed is five times better. The reason for that is the reduced overhead. Every picture needs the following steps to be done:

Connect to the server
Request the image
Receive the data, store it into a file

The time is lost between step 2 and 3. The first two steps has you upload data (the request), the third has you download data. Between that is only waiting. When using only a single thread, this waiting directly influences the download speed, because nothing else happens in that time. Using multiple threads, waiting only blocks one of the threads, leaving 9 downloads running in the meantime.

Besides downloading card pictures, I adapted Laterna Editor to use the new downloader, which also shown its flexibility: Laterna Editor downloads HTML pages from Gatherer, but doesn't save them to files. Instead, it further processes them to compact card descriptions for Laterna Magica. While it took a little work, the downloader is not limited to Files but can download to any location, such as a string buffer in memory.

The card downloader from Laterna Editor also shows how the task-centric approach helps with programming. This picture pretty much describes how the download process works:

Both Source and Destination are classes implemented by CardDownloader, but implement interfaces specified by Downloader. The source checks if the URL is a search or a single card, and also handles the automatic redirect if Gatherer only finds a single card for a search. The destination saves the HTML page to a string and waits for the download to finish, by registering a property change listener to the download job. If the download was successful, it sends the page to the search- or card processor, depending on the source. If it wasn't, it just discards the downloaded page.
The search processor finds additional result pages (every page has at most 100 cards in the compact view, which is used by the downloader) and of course the individual cards. The download of those is again done by the same process. The search processor simply posts the DownloadJob to the downloader and that's it.
The card processor finds the individual fields like name and mana cost, and stores them into a card. Once that's done, it posts the card to a Channel where the Gui can find it and in turn show the editor.

Combat and concurrency

2010-08-23T12:47:00.000-07:00

It was on July 15th when I titled a blog post "Combat in sight?", but now it really is. Today, I committed a version to my project where players can attack and thus deal damage. Blocking is not possible yet, but that's more a matter of work and not of thinking. Players still can't loose the game, but that's another story...

Now, for those of you not familiar with "concurrency" in programming, it means when multiple parts of a program run at the same time, "competing for the computer's resources" like CPU or RAM. Concurrency is hard for three reasons:

you have to control what happens when, because the classical "everything happens in a fixed sequence" is not true
speaking of "competing for resources", when two concurrent threads of execution access the same data, they can overwrite each other, messing things up
for this reason, locks and synchronizing have come up, which grant exclusive access to a resource to a single thread. This also means that threads have to wait for resources until they aren't locked any more. In the worst case, two threads can wait for each other.

Laterna Magica uses an approach that has two main threads; one for the game, and one for the user interface. While the UI thread is mandated by Java, I could have implemented LM to run on the same thread. The main reason I did not was to make LM independent of the GUI, meaning that the program can use different UIs and even run without a User Interface, say in a Computer-vs-Computer simulation or on a server (while the latter needs more preparation, I believe it will be possible someday).

So there are two threads, which means every GUI interaction means synchronization. The first GUI interaction implemented was playing cards and activating abilities. The code to enable that was pretty wordy and hardly extensible:

private boolean    ready;
private PlayAction a;

public GuiActor(Player player) {
    super(player);
}

public synchronized void putAction(PlayAction a) {
    ready = true;
    this.a = a;
    notifyAll();
}

public synchronized PlayAction getAction() {
    ready = false;
    while(!ready)
        try {
            wait();
        } catch(InterruptedException ex) {
            ex.printStackTrace();
        }
    return a;
}

On the surface, it doesn't look that bad, but it has several issues:

It is low-level: It handles all the synchronization stuff itself, as seen by boolean ready, notifyAll(), synchronized, while(!ready) ... This is all stuff that has to be repeated for every sort of user input: declare attacker, blocker, ...
It moves control away from the actor: putAction takes a PlayAction, which is the result of e.g. clicking on a card. How that click is associated to the PlayAction is not controlled by the actor which violates atomicity

Translating click to PlayAction is specific to playing spells and not compatible with e.g. declaring attackers. This means that the translation, which is not atomic, has to be performed for every type of input

Missing Encapsulation: The interpretation as a PlayAction is only valid when the player has priority, and this fact is not represented here: There is no representation of the fact whether the Actor is waiting for a PlayAction or for declaring an attacker

On the opposite, here is the new variant:

public class GuiMagicActor extends AbstractMagicActor {
    public final GuiChannels    channels = new GuiChannels();

    private static T getValue(Fiber f, Channel ch, GuiActor a) {
        a.start();
        log.debug("Waiting for result...");
        T result = Parallel.getValue(f, ch);
        log.debug("received!");
        a.dispose();
        return result;
    }

    public PlayAction getAction() {
        return getValue(channels.fiber, channels.actions, new ActionActor(this));
    }

    ...
}

This new version is based on the Jetlang concurrency framework, which works using channels and callbacks: Messages published to a channel are - asynchronously - forwarded to registered callbacks, which may then in turn publish new messages. The Parallel.getValue() method is used to get a value back from the channel synchonously, and the ActionActor encapsulates the state, in this case choosing a PlayAction to perform:

public class GuiChannels {
    /**
     * Channel for receiving {@link PlayAction}s to execute when the player has priority
     */
    public final Channel actions      = new MemoryChannel();

    /**
     * Channel for publishing {@link MagicObject}s when the user clicks on them
     */
    public final Channel objects      = new MemoryChannel();

    /**
     * Channel for publishing {@link Player}s when the user clicks on them
     */
    public final Channel      players      = new MemoryChannel();

    /**
     * Channel for publishing when the user clicks "pass priority"
     */
    public final Channel        passPriority = new MemoryChannel();

    public final Fiber                fiber;

    public GuiChannels() {
        PoolFiberFactory f = new PoolFiberFactory(Executors.newCachedThreadPool());
        fiber = start(f.create());
    }

    private Fiber start(Fiber f) {
        f.start();
        return f;
    }
}

public class ActionActor extends GuiActor {
    public ActionActor(GuiMagicActor actor) {
        super(actor);
    }

    @Override
    public void start() {
        disposables.add(actor.channels.objects.subscribe(actor.channels.fiber, new CardCallback()));
        disposables.add(actor.channels.passPriority.subscribe(actor.channels.fiber, new PassPriorityCallback()));
    }

    private class CardCallback implements Callback {
        @Override
        public void onMessage(MagicObject c) {
            log.debug("Received: " + c);
            PlayAction a = GuiUtil.getActionOptional(actor.getPlayer(), c);
            if(a != null) actor.channels.actions.publish(a);
        }
    }

    private class PassPriorityCallback implements Callback {
        @Override
        public void onMessage(Void v) {
            log.debug("Received pass priority");
            actor.channels.actions.publish(null);
        }
    }
}

The ActionActor receives Messages through the objects and passPriority channels and reacts specific to its task.

Hope you liked it!

Scala: Functional programming & DSL

2010-08-21T10:15:00.000-07:00

I first learned about Scala in forge's comment to this post, and the tutorial he mentioned is really great. Just for experimenting, I extended the Calculator example for Variables, Functions and exponentiation. The result is really extensible and took me just 140 lines of code, which really impressed me. So I'm showing you the result:

AST.scala (Scala doesn't require Files to represent the class names, and AST (abstract syntax tree) fits the classes in this file)
package net.slightlymagic.calc {
abstract class Expr
case class Variable(name: String) extends Expr {
    override def toString = name
}
case class Number(value: Double) extends Expr {
    override def toString = "" + value
}
case class UnaryOp(name: String, arg: Expr) extends Expr {
    override def toString = name + arg
}
case class BinaryOp(name: String, left: Expr, right: Expr) extends Expr {
    override def toString = "(" + left + name + right + ")"
}
case class Function(name: String, args: List[Expr]) extends Expr {
    override def toString = name + args.mkString("(", ", ", ")")
}
}

Calc.scala

package net.slightlymagic.calc {
object Calc {
    def simplify(e: Expr): Expr = {
      def simpArgs(e: Expr) = e match {
        case BinaryOp(op, left, right) => BinaryOp(op, simplify(left), simplify(right))
        case UnaryOp(op, operand) => UnaryOp(op, simplify(operand))
        case Function(op, operands) => Function(op, operands.map((x) => simplify(x)))
        case x => x
      }

      def simpTop(e: Expr) = e match {
        case UnaryOp("-", UnaryOp("-", x)) => x
        case BinaryOp("-", x, Number(0)) => x
        case BinaryOp("-", Number(0), x) => UnaryOp("-", x)
        case BinaryOp("-", x1, x2) if x1 == x2 => Number(0)

        case UnaryOp("+", x) => x
        case BinaryOp("+", x, Number(0)) => x
        case BinaryOp("+", Number(0), x) => x

        case BinaryOp("*", x, Number(1)) => x
        case BinaryOp("*", Number(1), x) => x

        case BinaryOp("*", x, Number(0)) => Number(0)
        case BinaryOp("*", Number(0), x) => Number(0)

        case BinaryOp("/", x, Number(1)) => x
        case BinaryOp("/", x1, x2) if x1 == x2 => Number(1)

        case BinaryOp("^", x, Number(1)) => x
        case BinaryOp("^", x, Number(0)) if x != Number(0) => Number(1)
        case BinaryOp("^", x1, UnaryOp("-", x2)) => BinaryOp("/", Number(1), BinaryOp("^", x1, x2))
        case e => e
      }

      simpTop(simpArgs(e))
    }

    def evaluate(expr: Expr, variables: Map[String, Double], functions: Map[String, (List[Double]) => Double]): Double = {
      expr match {
        case Number(x) => x
        case UnaryOp("-", x) => -evaluate(x, variables, functions)
        case BinaryOp("+", x1, x2) => evaluate(x1, variables, functions) + evaluate(x2, variables, functions)
        case BinaryOp("-", x1, x2) => evaluate(x1, variables, functions) - evaluate(x2, variables, functions)
        case BinaryOp("*", x1, x2) => evaluate(x1, variables, functions) * evaluate(x2, variables, functions)
        case BinaryOp("/", x1, x2) => evaluate(x1, variables, functions) / evaluate(x2, variables, functions)
        case BinaryOp("^", x1, x2) => Math.pow(evaluate(x1, variables, functions), evaluate(x2, variables, functions))
        case Variable(x) => variables(x)
        case Function(x, args) => functions(x)(args.map((x) => evaluate(x, variables, functions)))
      }
    }

    def parse(text : String) = CalcParser.parse(text).get

    val standardVars =
      Map(
        "E" -> Math.E,
        "Pi" -> Math.Pi
      )

    val standardFuns =
      Map(
        "sin" -> {x:List[Double] => Math.sin(x(0))},
        "cos" -> {x:List[Double] => Math.cos(x(0))},
        "tan" -> {x:List[Double] => Math.tan(x(0))},
        "cot" -> {x:List[Double] => 1/Math.tan(x(0))},
        "asin" -> {x:List[Double] => Math.asin(x(0))},
        "acos" -> {x:List[Double] => Math.acos(x(0))},
        "atan" -> {x:List[Double] => Math.atan(x(0))},
        "acot" -> {x:List[Double] => Math.atan(1/x(0))},
        "exp" -> {x:List[Double] => Math.exp(x(0))},
        "log" -> {x:List[Double] => Math.log(x(0))},
        "min" -> {x:List[Double] => Math.min(x(0), x(1))},
        "max" -> {x:List[Double] => Math.max(x(0), x(1))}
      )

    def evaluate(expr: String, variables: Map[String, Double], functions: Map[String, (List[Double]) => Double]): Double = {
      evaluate(
        simplify(parse(expr)),
        if(variables == null) standardVars else standardVars ++ variables,
        if(functions == null) standardFuns else standardFuns ++ functions
      )
    }


    import scala.util.parsing.combinator._

    object CalcParser extends JavaTokenParsers {

      def expr: Parser[Expr] =
        (term ~ "+" ~ term) ^^ { case lhs~plus~rhs => BinaryOp("+", lhs, rhs) } |
        (term ~ "-" ~ term) ^^ { case lhs~minus~rhs => BinaryOp("-", lhs, rhs) } |
        term

      def term: Parser[Expr] =
        (factor ~ "*" ~ factor) ^^ { case lhs~times~rhs => BinaryOp("*", lhs, rhs) } |
        (factor ~ "/" ~ factor) ^^ { case lhs~div~rhs => BinaryOp("/", lhs, rhs) } |
        factor

      def factor : Parser[Expr] =
        (exp ~ "^" ~ exp) ^^ { case lhs~exp~rhs => BinaryOp("^", lhs, rhs) } |
        exp

      def exp : Parser[Expr] =
        ("+" ~ expr) ^^ { case plus~rhs => UnaryOp("+", rhs) } |
        ("-" ~ expr) ^^ { case minus~rhs => UnaryOp("-", rhs) } |
        "(" ~> expr <~ ")" |
        ident ~ params ^^ {case name~params => Function(name, params)} |
        ident ^^ {case name => Variable(name)} |
        floatingPointNumber ^^ {x => Number(x.toFloat) }

      def params : Parser[List[Expr]] =
        "(" ~> repsep(expr, ",") <~ ")"

      def parse(text : String) = parseAll(expr, text)
    }
}
}

Wow! I don't want to repeat the tutorial, which is really great, but I want to mention a few features that really improved the way this code is written.

First of all, Scala is a mixture of functional and object oriented: Map[String, (List[Double]) => Double] (Scala uses square brackets for generic types) means a Map of Strings and Functions, which take a list of Doubles as a parameter and yields a Double as the result. To get the same result as standardFuns in the Calc object... Yes, object. This basically means that all members are static. On the opposite, normal classes can't have static members, which doesn't really matter because you can have class and object of the same name. To get the same result as standardFuns using Java, you'd have to define a common interface and several anonymous classes, which means a lot of duplication. Using anonymous functions and the fact that a function can be passed as a parameter, something you don't get from nonfuntional languages, you avoid most of the redundant code. No interface definition, just a single line per anonymous function.

The second thing that you can write method calls in an "unusual way": a.plus(b) is the same as a plus b. Together with the fact that you can name methods, e.g. "+", you basically have overriding operators. This means not much more than you can write short, concise code. But that is very important; just look at the preceding paragraph. The parser package of Scala uses such "Operators" to write short, expressive text parsing code.

Lastly, pattern matching. This is a great feature that is really hard to imitate using Java. It uses case classes, as seen in AST.scala, and the match/case construct. For example:

expr match {

  case BinaryOp(x1, op, x2) => doSomething()

  case BinaryOp(Number(x1), "+", Number(x2) => doSomethingElse() 

}

doSomething() is only executed if the case matches, and at the same time assigns the three variables x1, op, x2. You can build more complex constructs, as the second example shows, including nesting Objects and using constant expressions to narrow down matching cases. This works as long as you use case classes.

And now comes another important part: Scala compiles to Java byte code, which means that you can code a part in scala. For example, the simple Calculator DSL was way easier to write in Scala than it would be in Java. Once it's packed as a jar, you don't even notice that the code was not written in traditional Java, and integrates nicely into the other parts. (Except you'd have a hard time to call "operator methods" or use API that uses Functions as parameters. Consider that for your public, plain-old-java accessible API)
The only downside is that Eclipse integration is not great so far. Maven does a good task in still compiling your Scala code, but the Scala plugin is not very stable, so I use the plain text editor. It works for small things like the Calculator, but I miss obvious features like import organizing, content assist, automatic building on every change, syntax & error highlighting, parentheses matching, folding...

Performance of Software

2010-08-19T05:51:00.000-07:00

I was reading a little about scala these days and think that it's a cool language that would probably make my life a lot easier. For example, the CardCompiler is hard to use; you have to go through a few hoops to implement new effect parsers. I think that I am on the right way, but there is much room for improvement in terms of usability.

But today I don't want to talk about Scala, but software performance. One point with Scala is that it largely uses immutable objects, putting copying over mutating existing objects. The first thought when you hear this is probably how much memory this would waste and that it will also need more processing power all the data has to be copied.

However, performance doesn't mean to use as little resources as possible. It means to use the resources you have the best possible. And nowadays, the resource we have but use the least are multiple processors.

Modern processors work on the edge of physical possibilities. Circuits are not thicker than a few atoms, and currencies are so small that you can almost measure the number of electrons flowing. At this scale, quantum effects matter, and this means randomness. That's about the reason why (semiconductor) processors don't get faster any more and increasing speed does only occur by parralelism.

Writing software that works parallel, however, is hard, because multiple threads can access the same resource at the same time and thus wreak havoc. Which leads back to immutable objects: Data corruption can only occur when writing. when every access is read-only or creates a copy, nothing bad can happen.

This leaves one question: How bad is copying really? Well, every copy you don't need any more can be garbage collected, so memory should not really be a concern. Memory size is also not as restricted as processor speed, so there should be enough potential to support memory-heavy rather than processor-heavy software.
Garbage collection itself, however, uses the processor. It finds objects that are no longer accessed by any thread; that means that it is not constrained to work in the program's normal flow and can work in its own thread. As the garbage collector is not really interested in the objects, it can even be spread to multiple threads if necessary.

Copying itself uses processing power, and can take some time for large objects. Usually, the only type of large objects are arrays. There are really not many possibilities: boolean, byte, short, char, int, float, long, double, Object. All these take up to 8 bytes to store. All that stays are the indexes of arrays, which can go into several millions. If we stay with immutable objects, this is really the only bottleneck we have to deal with, because you don't need to copy the array's content objects, as they can't change.

I guess this wasn't all that interesting to read, but I really wanted to speak this out: parallelism is the future of software, parallelism is hard, so any attempt to make it easier, for example by using immutable objects, is a step into the right direction

To URI or not to URI

2010-08-16T17:35:00.000-07:00

I'm not an English native speaker, so don't blame me if this Shakespeare reference is not recognizable. Maybe "URI or not URI" would fit better for pronunciation...

Anyway, I'll brighten up the situation for anyone who doesn't know URIs: "URI" stands for Uniform Resource Identifier, and the "not to URI" part of the title refers to "URL", Uniform Resource Locator. Seriously, I don't know what the difference between them is supposed to be, just that they behave pretty differently in Java.
(And for anyone who thinks, "Well, so you do know the difference?" No, the Java classes are an implementation of a specification that I don't understand, and not even really know. I know, however, how the implementation behaves. If this behavior follows the original specification, which was not made for the Java language but presumably for the internet, I don't know.)

So, from my point of view, both URIs and URLs are meant to identify some sort of resource, like a network drive of some web site.

In Java, you can directly connect to a URL and read from and write to it. You can't do that for a URI, but you can convert between both forms (if the resource is legal in both representations).
The equals() and hashCode() methods of URL perform a name space lookup, making them very slow. URLs are therefore poor choices for map keys, for example for caching downloaded files.

So, it seems like a tied match. The first one is "obvious", you can see it in the API that URI can't directly open connections. equals() and hashCode() being slow is so subtle that there is an entry in FindBugs, an Eclipse plugin that helps to find common programming mistakes, which is how I learned about it.

The third difference I've experienced so far is very subtle and unexpected, and it is the real reason for this post. wow, about time to get to the point...

You can represent a file inside a Jar (or Zip) archive using a URL or URI; both work. You can also "resolve" a relative URL/URI against another one to get an absolute one. But the combination of both only works with URL!

jar:file:/path/to/archive.jar!/path/inside/archive/

jar:file:/path/to/archive.jar!/path/inside/archive.txt 

are both legitimate URIs/URLs. Say, you want to resolve "hello.txt" against these, you expect:

jar:file:/path/to/archive.jar!/path/inside/archive/hello.txt

jar:file:/path/to/archive.jar!/path/inside/hello.txt

however, this works only with URLs. A URI won't be able to resolve and will just return "hello.txt"

I said that I recently reimplemented TreeProperties, and I did it based on URIs. As you might guess, resolving paths relative to some context is pretty important for a tree structure. Finding the bug was very annoying, because reading from a Jar file, or even multiple Jar files, is not something I have years of experience with. Fixing the bug was way easier once I sorted out its origin.

I'd like to end this post with another Shakespeare quote:

"But none come to mind. I hope I have at least fooled you with the quotation marks. Just be aware or the differences between Uniform Resource Locators and Identifiers"

Migrating to Maven

2010-08-13T16:31:00.000-07:00

This week, I've finally done what I wanted to do for a very long time: I migrated my project to Maven. Warning: Non-programmers will probably be hopelessly bored.

Maven is a build system with many capabilities that are probably beyond my current recognition. For me, it means essentially these things:

Managing dependencies to external libraries, such as Dom4J, an XML API, and also to the different projects that belong to LaternaMagica, like TreeProperties.

For an Open Source project, this also means that I don't have to care that others have all the required libraries, because they can find and download them on-demand. Having the right configurations in the development environment is not that important this way. As a downside, it makes Maven pretty much a requirement for working with my code, but that's just like English is required to read my blog: it's good to know English, no matter what.

Automatic testing and generation of source, binary and documentation archives, or "snapshots"

I said I wanted to do this for a long time. If you're asking why I haven't done it earlier... well, I was dumb. I couldn't get my Eclipse installation working with the Maven plugin. The problem was... that my eclipse installation was owned by root (the administrator, for all the poor Windows users out there^^) and installing the plugin simply didn't do anything as I didn't have the rights.

So finally, everything is alright. I have totally rewritten TreeProperties and Utils, and also greatly reworked LaternaDoc, which finally does what it should. More on those another time ;)

Last Known Information with Undo

2010-08-08T05:55:00.000-07:00

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

2010-08-03T14:28:00.000-07:00

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...

Damage

2010-07-30T23:40:00.000-07:00

I just re-read my post about destruction and realised I should show what it took me to implement damage. This might not be my most interesting post, as it is just code, but maybe some of you are interested. Get ready... there are about 200 lines of code coming for you!

public abstract class DamageEvent extends ReplaceableEvent {
    private MagicObject source;
    private int         ammount;
    private boolean     combat, preventable;

    public DamageEvent(MagicObject affected, MagicObject source, int ammount, boolean combat, boolean preventable) {
        this(you(ofInstance(affected)), source, ammount, combat, preventable);
    }

    public DamageEvent(Player affected, MagicObject source, int ammount, boolean combat, boolean preventable) {
        this(ofInstance(affected), source, ammount, combat, preventable);
    }

    public DamageEvent(Supplier affected, MagicObject source, int ammount, boolean combat, boolean preventable) {
        super(affected);
        this.source = source;
        this.ammount = ammount;
        this.combat = combat;
        this.preventable = preventable;
    }

    public MagicObject getSource() {
        return source;
    }

    /**
     * This method can be used by replacement effects that prevent or increase damage.
     */
    public void setAmmount(int ammount) {
        this.ammount = ammount;
    }

    public int getAmmount() {
        return ammount;
    }

    public boolean isCombatDamage() {
        return combat;
    }

    public boolean isPreventable() {
        return preventable;
    }
}

public class DamagePlayerEvent extends DamageEvent {
    private Player p;

    public DamagePlayerEvent(Player p, MagicObject source, int ammount, boolean combat, boolean preventable) {
        super(p, source, ammount, combat, preventable);
        this.p = p;
    }

    public Player getPlayer() {
        return p;
    }

    @Override
    protected boolean execute0() {
        CompoundEdit ed = new CompoundEdit(getGame(), true, "Deal damage");

        //118.3a. Damage dealt to a player causes that player to lose that much life.
        getPlayer().getLifeTotal().loseLife(getAmmount());

        ed.end();

        return true;
    }
}

public class DamagePermanentEvent extends DamageEvent {
    private static final Predicate legalAffected = and(isIn(ofInstance(BATTLEFIELD)),
                                                                       card(or(CREATURE, PLANESWALKER)));

    private static final Predicate isPlaneswalker = card(has(PLANESWALKER));
    //TODO implement wither and lifelink
    private static final Predicate hasWither      = alwaysFalse();
    private static final Predicate hasLifelink    = alwaysFalse();

    private CardObject                          permanent;

    public DamagePermanentEvent(CardObject affected, MagicObject source, int ammount, boolean combat, boolean preventable) {
        super(affected, source, ammount, combat, preventable);
        if(!legalAffected.apply(affected)) throw new IllegalArgumentException(
                "affected must be a creature or planeswalker permanent: " + affected);
        permanent = affected;
    }

    public CardObject getPermanent() {
        return permanent;
    }

    @Override
    protected boolean execute0() {
        CompoundEdit ed = new CompoundEdit(getGame(), true, "Deal damage");

        //118.3b. Damage dealt to a planeswalker causes that many loyalty counters to be removed from that
        // planeswalker.
        if(isPlaneswalker.apply(getPermanent())) {
            //TODO remove counters
        }
        //118.3c. Damage dealt to a creature by a source with wither causes that many -1/-1 counters to be put on
        // that creature.
        else if(hasWither.apply(getSource())) {
            //TODO add counters
        }
        //118.3d. Damage dealt to a creature by a source without wither causes that much damage to be marked on
        // that creature.
        else {
            getPermanent().setMarkedDamage(getPermanent().getMarkedDamage() + getAmmount());
        }
        //118.3e. Damage dealt to an object or player by a source with lifelink causes that source's controller to
        // gain that much life, in addition to the damage's other results.
        if(hasLifelink.apply(getSource())) {
            getSource().getController().getLifeTotal().gainLife(getAmmount());
        }

        ed.end();

        return true;
    }
}

I don't really like this code, because it has the effects of damage hard coded, but I think it's fine for now. extracting these effects later if it's necessary shouldn't be too hard, as the different effects of damage will only be mentioned here, so I can safely delay this task.

Trying out the card editor

2010-07-23T07:40:00.000-07:00

I just tried out my card editor to download "a few" cards; all the vanilla creatures and old (non-pain) dual lands. If I haven't done anything wrong in my gatherer search, there are 177 vanilla creatures. it's in fact not so easy to search for textless cards; I had to use the regular expressing "m/^$/" ("m/.../" is the gatherer identifier for regexes, "^$" essentially means "the beginning of the text immediately followed by the end")

by the way, I haven't done a full fledged form for gatherer searches; I did the search on the web site and pasted the search URL into my program. takes me much less time^^

there were two problems: first, my download just discontinued after 89 cards. Looking at what card that was, it was Little Girl from Unhinged with a half mana symbol. Second, even after refining my search to exclude Un-cards, my program only wound up downloading 100 cards. my workaround for that problem was simply to download the other cards by reverting the sort order^^

so, putting things short, I now have over 200 cards implemented, including 177 vanilla creatures, 10 classic dual lands, 10 SHM/EVE dual lands, 5 basic lands, Wrath of God, Damnation and Llanowar Elves. It's really time for combat^^

Event Handling

2010-07-22T11:46:00.000-07:00

If you recall what I wrote a long time ago about challenges in programming, event handling would be one of the easy, boring parts. The point of event handling is to inform parts of your program when something happens in another part. This is espacially important for the user interface, as you always want to see what's currently going on, but in the context of Magic, there is another very important reason for event handling: Triggered abilities.

If you now think that the User Interface and Triggered abilities can share the event handling system, therefore effectively reducing the ammount of programming needed for each of them, I fear you'll be disappointed. The reason for this is the undo system. While it enables things like handling illegal actions, the most direct interpretation of what it does prevents me from sharing one event system: Undo means that every action and event can happen in two directions in time.
When you attack with a creature, it becomes tapped. An ability could trigger from that tapping. If you now determine that the creature isn't allowed to attack, everything's undone and the creature is untapped again. You want to see the creature untapped in the user interface, but you don't want abilities trigger from it untapping.

Of course the event handling functions after the same principle, but the events are duplicated - in some sense. There's no real 1:1 mapping between GUI and game events, because the GUI is satisfied by state-changes, while the game needs more high level events: The gui doesn't care if you've drawn a card or just put it into your hand. It just needs to know that your library has become smaller and your hand grew larger.

Fortunately, Java has some built in functionality for handling these low-level events, namely PropertyChangeSupport. It allows you to keep track of properties and notify the listeners whenever a change occurs. Well, you still have to call the listeners on a change, but the major work, managing all the listeners and what properties they are interested in, is done for you.
Along with adding PropertyChangeSupport to Laterna Magica, I have restructured a lot of code. Previously, every class implemented undo support for its properties itself. This is now separated into an extra class, which also allows to use PropertyChangeSupport more easily:

public class EditableProperty extends AbstractGameContent {
    private EditablePropertyChangeSupport s;
    private String                        name;
    private T                             value;

    public EditableProperty(Game game, EditablePropertyChangeSupport s, String name) {
        this(game, s, name, null);
    }

    public EditableProperty(Game game, EditablePropertyChangeSupport s, String name, T initialValue) {
        super(game);
        this.s = s;
        this.name = name;
        value = initialValue;
    }

    public void setValue(T value) {
        new SetValueEdit(value).execute();
    }

    public T getValue() {
        return value;
    }

    @Override
    public String toString() {
        return valueOf(getValue());
    }

    private class SetValueEdit extends Edit {
        private static final long serialVersionUID = 93955529563844615L;

        private T                 oldValue, newValue;

        public SetValueEdit(T newValue) {
            super(EditableProperty.this.getGame());
            this.newValue = newValue;
        }

        @Override
        protected void execute() {
            oldValue = value;
            value = newValue;
            if(s != null) s.firePropertyChange(name, oldValue, newValue);
        }

        @Override
        protected void rollback() {
            value = oldValue;
            if(s != null) s.firePropertyChange(name, newValue, oldValue);
        }

        @Override
        public String toString() {
            return "Set " + s.getSourceBean() + "'s " + name + " to " + newValue;
        }
    }
}

Combat in sight?

2010-07-15T12:04:00.000-07:00

Both destruction and damage are more or less completed concepts by now, and at this point I'm doing combat. What does this mean?
Every turn, you and your opponent can arrange your creatures and planeswalkers in a more or less complex relationship

some creatures attack a player or planeswalker
other creatures block those attackers. A single attacker may be blocked by multiple blockers and vice-versa (granted you have the right abilities around)
all these attackers and blockers have a damage assignment order
in the end, they all deal damage according to it, and they do so simultaneously. my ideas of simultaneity are... well, limited.

so, that's only the rules part. to let the player take all of the many required actions, the Actor class needs a bunch new input methods. And the GUI needs a way to control, display and update what's going on. If you think that's a lot to do, you're right ;)

Destruction

2010-07-01T08:53:00.000-07:00

The last one and half a month were really sparse on working on Laterna Magica. It was the countdown of my school year and I was busy with a lot of stuff. There were loads of very work-intensive homeworks, and my year's project was also due. Anyone with experience on projects knows that half of the work is done in the two weeks before the end date and the other half is done in the two weeks after ;)

I can tell you, I didn't find a single minute to work on my program, but today I finally got back to it. I don't know if I can work on it regularly again, but I will try.

Before my big break, I told you that one of my next steps will be combat, but combat is a big thing and it takes many parts to work. One of these is damage.

Until very recent, damage was a simple concept: Players and creatures can receive damage. When a player receives damage, he looses life; when a creature receives enough damage, it is destroyed. However, two recent changes turned things around a bit: Planeswalkers, but more importantly Wither and the accompanying changes of Lifelink etc. To make things worse, damage has also another special concept found (nearly) nowhere else in the game: sources.

I suspect damage to be very annoying to program, but happily there's another thing to be done before damage really makes sense... Which happens to be what I've done today: Destruction, which was in fact so easy that I can fit it here without worrying that it will overload my post:

public class DestroyPermanentEvent extends ReplaceableEvent {
    private MagicObject o;

    public DestroyPermanentEvent(MagicObject o) {
        super(o);
        this.o = o;
    }

    @Override
    protected boolean execute0() {
        if(o.getZone().getType() != Zones.BATTLEFIELD) return false;
        o.setZone(o.getOwner().getGraveyard());
        return true;
    }
}

execute0() is very straightforward, which is possible because "destroy" only has one meaning, as opposed to damage, which would make a decision based on the receiver's type and both source's and receiver's abilities. Making DestroyPermanentEvent a ReplaceableEvent easily takes care of Regeneration and indestructibility. The only thing I'm not sure about is "... can't be regenerated".

The card editor

2010-05-12T05:23:00.000-07:00

The last weeks had no updates in my main project, but there's a good reason for that. I worked on a card editor that lets you download gatherer card descriptions, edit them and lets you test if the card is correct.

I think I'll explain a bit more how Laterna Magica handles cards. A fundamental thought in my system was extensibility. I'm currently using a text format, but Laterna Magica allows you to use any format, even multiple ones at the same time. So, if I sometime see a reason to use e.g. XML, I can still use the old cards while developing cards for the new one.

A similar thought is true for the text format itself. It is key-value based, and every key is handled by its own class. If a line is "name Llanowar Elves", then the class for "name" gets the input "Llanowar Elves" and sets the name accordingly. If the line is "text {T}: Add {G} to your mana pool.", the "text" handler tries to find an ability parser that can parse the line. Even if I can't represent an ability, I can make a class specifically for that ability and add a line handler that applies an arbitrary class to the card, like "apply laterna.magica.cards.DestroyAllCreatures".

The output of the card parser is a CardTemplate object. All the CardTemplates created are stored in a zip file, so you can think of the card parser like a compiler: There's input of different types, like plain text and XML, but the parser(s) convert it into a uniform format that the program can work with (serialized java objects).
And here, my editor comes into play. After creating a card, the editor can directly feed it into the parser, which implicitly checks if all the lines in the file are correct. The card parser will ignore lines that can't be parsed (like "Dryad Arbor is green." in my last post), but the card creator (e.g. you^^) won't: You can see the parser's warning and correct the lines.

Basic editing, opening, saving and even downloading already works in the editor, but it still needs a few tweaks before it really has a benefit over normal text editors (which you will be more familiar with for sure):

Compiling cards or creating the zip file doesn't work yet
The card downloader does not convert a card's name, I would like to have "Shock deals two damage to target creature or player." as "~ deals two damage to target creature or player."
Maybe even more complex transformations like "target((zone/battlefield & type/creature) | player)" ;)
(that's just speculation. i have no idea how to do targets or even target parsing)
There is a file system tree with all the cards, but currently you can't open a file by double-clicking it
"Save As" should be possible by dragging an opened file (they are shown in a list) onto a folder in the tree.
I want to display already opened/modified files with a different icon

Okay, the last one is just bells and whistles, but the others will really influence the usability. I have already created the shadowmoor hybrid lands, which was lots of copy/paste and changing names and colors. Although these cards are not parseable yet as-is, downloading the cards would have made it easier. It's not in the GUI yet, - currently, you can only download cards by multiverse-ID or card name - but the download functionality can use all of the strength of gatherer searching, so downloading exactly those ten hybrid lands shouldn't be too hard.

This editor is like a pet to me. I know I have better things to do - combat, namely - but right now I want to get this working.

Implementing some cards

2010-05-08T16:10:00.000-07:00

Okay, I think I've spent enough time on how abilities work in my problem, but it's definitely easier when viewing some real cards.

In reality, I haven't done much of the work yet that would make making cards interesting - no targeting, no damage, no destruction or sacrificing - it's essentially creating and spending mana right now.

Before I come to the interesting cards which can't be done yet, I'll show you what already works in this post. I have done a simple parser for cards. In fact, it's quite extensible and can be configured to plug-in different file formats. The only file format by now is a plain text format, for which in turn different line-parsers can be plugged in.

And now to the cards:

name    Forest
super   basic
type    land - forest

The basic land types have the mana producing ability implied, which are also parsed as any other mana ability. I'm not sure how this will work with adding and removing basic land types, but it's like that for now.

name    Graven Cairns
type    land
text    {T}: Add {1} to your mana pool.
text    {B/R}, {T}: Add {B}{B} to your mana pool.
text    {B/R}, {T}: Add {B}{R} to your mana pool.
text    {B/R}, {T}: Add {R}{R} to your mana pool.

Right now, there are only activated abilities. Costs and Effect are parsed separately, and every cost is parsed on its own. By now, any combination of mana costs and Tap or untap costs are working. The only Effect is "Add ... to your mana pool." Things like "{B}{B}, {B}{R} or {R}{R}" are not possible by now, neither are hybrid symbols (they only work for costs), so I write it as three abilities.

name    Dryad Arbor
color   green
type    land - forest
type    creature - dryad
pt    1/1
text    (Dryad Arbor isn't a spell, it's affected by summoning sickness, and it has "{T}: Add {G} to your mana pool.")
text    Dryad Arbor is green.

Here you can see that every type is specified on its own line only with its corresponding subtypes. The two "text" lines here are actually nonfunctional. The "Dryad Arbor is green." Ability is actually implemented by the "color" line, and the mana ability comes from the forest subtype.

Implementing activated abilities: Divide and conquer

2010-05-05T05:41:00.000-07:00

Last time, I showed the technical concept behind abilities (and spells) in Laterna. Today, I want to explain the PlayInformation interface from another perspective.

I hope I have given a good impression of why I use the approach I do: Abilities using a function to create PlayInformation objects which do the work. But why is PlayInformation so "big"? Why does it do all the work from paying costs over targeting to dispatching the effect?

The reason is a simple one: Because it's easier this way. Imagine a "complex" ability: "{X}: ~ Deals X damage to target creature." What this means is that the variable X is mentioned in both cost and effect, as most of the time, and this gives two possibilities:

Make Cost and Effect both interfaces and define some kind of communication, likely using another object between them, or
only use that object from "in between" and make the communication between cost and effect an implementation detail.

The process of playing a spell/ability is a complex one, and putting it into a single class enables more compact code to be written for individual abilities.

Now there's only the question from last time left: How can I still define cost and effect separately, giving me the ability to reuse them?

Delegation is a key concept in OO programming: If a class gets too big, try to find some separated piece of work that it does, and transfer it to a new class. Then, let the original class use the new one. An example in LaternaMagica is the CardCharacteristics class: Cards have characteristics that can modified by various effects. But instead of implementing the characteristics in the MagicObject class, every MagicObject object has a CardCharacteristics object. That does this work.

In that case, it's defined in the interface. With PlayAbility, it isn't. It's an implementation detail of AbstractPlayInformation, which implements PlayInformation. The AbstractPlayInformation class allows you to combine multiple PlayInformation objects into a single, big PlayInformation that carries out your instructions in order.
If you have a cantrip spell, just add in a DrawCardInformation at the end!
If you have a complicated activated ability, implement the effect, but use standard cost Informations and combine them with the AbstractPlayInformation.

Oh, and don't forget to add an information that removes the spell/ability from the stack...

Implementing activated abilities: Getting the effect to the game

2010-05-01T06:22:00.000-07:00

There are two paragraphs in my previous post that I want to further examine:

ActivatedAbility has a method getPlayInformation() which takes an ActivateAction and returns a PlayInformation.
The PlayInformation is the real worker of abilities and implements modes, targeting, costs, effects etc. It depends on the game, so an activated ability can only create the PlayInformation if a game is provided.

First, let me show you the ActivatedAbility and PlayInformation interfaces, so you can see what I'm talking about:

public interface ActivatedAbility extends NonStaticAbility {
    public boolean isLegal(ActivateAction a);

    public PlayInformation getPlayInformation(ActivateAction a);

    //inherited from NonStaticAbility
    //public boolean isManaAbility();
}

public interface PlayInformation extends GameContent {
    /**
     * Returns the action that is used in playing.
     */
    public PlayAction getAction();

    /**
     * Returns the object that was played using this play information.
     */
    public MagicObject getObject();

    public void makeChoices();

    public void chooseTargets();

    public void distributeEffect();

    /**
     * This action is only defined for activated abilities and spells, but not for triggered abilities.
     */
    public GameAction getCost();

    public GameAction getEffect();

    //inherited from GameContent
    //public Game getGame();
}

As you can see, the Activated ability interface is pretty small; its job is primarily to create PlayInformation objects. PlayInformation does the whole work.

This means especially two things:

Although it would seem intuitive, to make a new activated ability, you don't implement ActivatedAbility but PlayInformation. This may be confusing for the first time, but you can get used to it. But:
You still have to implement the getPlayInformation() method to return your new PlayInformation. And this is what really bugged me. An ActivatedAbility class would usually exactly follow a template, and only replace the PlayInformation.

So I thought about what I could do to save me from creating all these redundant classes. The first step was to extract the job "create a PlayInformation for an ActivateAction" out of the ActivatedAbility class. As luck would have it, the Google Collect API, which I was already using, has the right interface for that: Function (simplified):

public interface Function<F, T> {
    T apply(F from);
}

Which led me to the ActivatedAbilityImpl class:

public class ActivatedAbilityImpl extends NonStaticAbilityImpl implements ActivatedAbility {
    private static final long                                           serialVersionUID = -8987886570576715112L;

    private Function<? super ActivateAction, ? extends PlayInformation> object;
    private Predicate<? super ActivateAction>                           legal;

    public ActivatedAbilityImpl(boolean manaAbility, Function<? super ActivateAction, ? extends PlayInformation> object, Predicate<? super ActivateAction> legal, String text) {
        super(manaAbility, text);
        this.object = object;
        this.legal = legal;
    }

    /**
     * Returns if casting the spell using the specified CastAction is legal.
     */
    @Override
    public boolean isLegal(ActivateAction a) {
        return legal.apply(a);
    }


    @Override
    public PlayInformation getPlayInformation(ActivateAction a) {
        return object.apply(a);
    }
}

(Predicate is also from Google Collect and represents a true/false decision about an object)

But that step doesn't really solve the problem. Now I don't have to implement ActivatedAbility, but instead Function. The real solution only came when diving deep into Java's pool of features: Reflection. Reflection means to analyze a program's parts, like, classes, methods, constructors and so on while it's running. So my idea was to make a Function which creates a new object of any class you want:

class B {
    public B(A a) {}
}

Function<A, B> f = new MyFunction<A, B>(A.class, B.class);
B b = f.apply(new A());

...and creating a new class has transformed into creating an object! However, there is still a problem: what if your PlayInformation needs configuration? Your PlayInformation might Implement the ability "<mana cost>: Tap target permanent." How do you set the mana cost? The ActivateAction, which is the function's input, can't provide it. What you need is a per-function configuration in addition to the per-apply parameter:

class B {
    public B(C c, A a) {}
}

C config = new C();
Function<A, B> f = new MyFunction<A, B, C>(C.class, config, A.class, B.class);
B b = f.apply(new A());
//b is equal to
//new B(config, new A());

And that's exactly how I ended up, and I'm quite satisfied with my work. You can look at the source code at FactoryFunction.java.

And the last note for today: PlayInformation has many things to do, among them providing the ability's (or spell's, PlayInformation is used for both) cost and effect. By Implementing both in the same class, you take yourself the opportunity to reuse costs in other abilities. Next time, I'll show you how to mix-and-match these.

Cards - Two views on the same thing

2010-04-29T14:13:00.000-07:00

I would really like to know if you can imagine of what two views I'm going to talk about. I guess it's more obvious for people who have thought about how to structure a magic application. If you like, leave a comment and state what's your background.

When you open a booster pack, how do you read cards? They have symbols and text, and of course you can read them and determine what they do. However, the card can't do anything, because you're not playing a game.
During a game, the card has a complex context that influences how you read it; For example, its color may have changed.

Humans can read a card outside the game and inside the game, but it's hard for a computer. The difference between these two views is very important and currently makes me some problems. A card outside the game (template), like the one from the booster, is a constant thing - it can't change between different copies. This means that multipe cards inside the game can share the same template, but those are then individuals. They have the same template, but that's it.
The same thought can be applied to abilities and spells, I think. Abilities and spells have another, even harder problem: Their effects. While cards just sit there, spells and abilities can directly influence the game, and what influence that is depends on how the spell/ability was played.

So what's the solution to the problem? Well, in a nutshell, the data structure for cards, spells and abilities is duplicated.

Outside of the game is CardTemplate and CardParts, inside the game is CardObject and CardCharacteristics. A CardCharacteristics is assigned to a CardObject is responsible for providing the characteristics, respecting effects and the layer system, but also taking into account the values "printed" on a CardParts object.

Outside the game is ActivatedAbility, inside the game is ActivateAction, PlayInformation and AbilityObject.

ActivatedAbility has a method getPlayInformation() which takes an ActivateAction and returns a PlayInformation.
The PlayInformation is the real worker of abilities and implements modes, targeting, costs, effects etc. It depends on the game, so an activated ability can only create the PlayInformation if a game is provided.
And to make things easier, the activate action has some additional infos like who played the ability and what card the ability is on (like I said, ActivatedAbility is outside the game, so it doesn't know which cards it is on. the ActivateAction knows).

All that happens under the surface. The ActivateAction retrieves the PlayInformation and does all the necessary things, like putting an AbilityObject onto the stack etc.

I hope that you had a chance to look into my program; I know that this is very hard to imagine without directly looking at the code, So I won't try to go into more detail unless you wish so ;)

Hardcoded vs Softcoded

2010-04-26T05:48:00.000-07:00

From a user's perspective, a program's job is to do work, look good etc. If you want to look into a program, and very deep into it, you will notice that all a program does is to move data around. Data and code are two very important things in programming, because the code does the work, and only with data there is work.

But the borders can become unclear when you think of it. Data and code do both lie on your hard disk, or in memory when a program runs, so where's the difference? Well, code is data that represents some kind of work.

Magic is all about doing work. "You lose one life" is a piece of work. After the work is done, I might have lost the game. Still, I wouldn't like to have that effect around in my code - in my Java code, at least.

Hardcoding and softcoding is all about how work is represented.
Hardcoding essentially means "compiled". For example, the five colors and the card types are hardcoded into laterna - to change one, you need the source files and a Java compiler to generate a runnable program from it once again.
Softcoding, on the other hand, means "interpreted". "You lose one life", which might be a spell's effect, could be written in a text file. That file is read when the program is started, and will do its work, although it never was java code.

So softcoding is the better way to do work in all situations? Clearly no. Enabling something to be softcoded needs massive effort. Not only do you need to parse the file and get the important information from it, you also need to translate it into a form the program can handle. For Magic cards, this is very complex, since the work is done much later than the card is read, And a card might do different things everytime you use it. I'll talk about it in more detail the next time.

Spells

2010-04-19T14:45:00.000-07:00

I fear that my blog evolves into a redundant commit log of my project, but I really try to write interesting and original.

First, let me say I'm steadily making progress. Now there's a mana pool and you can play mana abilities. Lands do untap and mana is removed properly. I have Llanowar Elves, my first nonland card, which you can play. It's put on the stack and then resolves. You don't pay costs for it yet...

And that's exactly my topic: What does it take to play a spell? There are several reasons why I started with lands, but the most important is that playing a land is a relatively simple thing: "To play a land, a player puts that land onto the battlefield from the zone it was in".

Playing a land is a single line in a Subpoint of the Subpoint 114.2a of "Special Actions" in the comprehensive rules. "Casting Spells" is Section 601, and 601.2 describes the steps necessary to do so, a to h, each one much longer than 114.2a.

The best known steps for playing spells are choosing targets and paying costs. Targets are a somewhat advanced, and I will rest a little before implementing them, but costs are a really essential part. The hard part is not costs per se, but paying them. Just for paying a mana cost, the player must choose how to pay for hybrid or variable symbols and then choose which mana to use.

Now that I know that playing spells works in general, I can try to fill in the details. When I have costs, and can therefore play simple spells rules-compliant, I might take a break to do some cards, improve the GUI, or implement combat... And swoosh! A game isn't that far away any more!

PS: There's one cost working already: The tap cost ;)

Finally...

2010-04-11T09:23:00.000-07:00

I'm glad to announce the first "playable" version of Laterna Magica. Features:

A rather simple GUI
Drawing a card during your draw step
Playing Lands
An opponent who does... nothing

Before I present you some screenshots, let me explain the "glue" I've talked about the last time, especially the controller.

The class Player in laterna magica is more or less a data structure and can only perform tasks that don't need decisions - like loosing life, drawing a card or discarding a card at random.
Discarding a chosen card is different, because it needs knowledge, which is something the Player class should not have. Different players make different decisions, and in different ways.

The solution is the Actor class. Whenever some decision is needed, like which card to discard, the actor is asked for that decision. The actor may implement an AI algorithm for choosing, it may get the choice over the network, or, most naturally, depend on user input from the GUI.

Although separating actor from player was a clear choice for me, I don't know how that class will look in the end. Magic is a game with tons of choices - there's not only "discard a card" but also "discard two cards", "discard a creature card", "discard a card of each color"... you know what I mean, this can quickly get messy.
For now, there's basically only "You have priority. What do you want to do?", so that problem is still far away.

And now screenies! When you start the program, you get a GUI with an empty board, like this:

But it doesn't stay for long, it will quickly populate your game with cards. You can watch how your library grows and you draw cards!

After passing priority twice, It will be your main, and you can play one of your (many) Plains:

Looks great? Look at that, during your next turn, you can do it again^^

What you have just seen demonstrates some important things:

Laterna Magica has many events. Playing a land doesn't explicitly remove it from the panel. Instead, the panel listens for cards entering/exiting the zone (and later also controller changes) to keep track of what cards are to be shown. When the land is played, the rules engine moves it, and the GUI listens to the rules engine. Similar things are true for the zone size labels, the life total labels and the turn progress label.
And because swing supports it, the game loop (passing priority back and forth, basically) can run in an extra thread. Whenever the player "freak" has priority, the GameLoop queries the Actor for what to do. That actor is a GuiActor and waits for the user to either click "Pass priority" or a Plains card. Therefore, the GUI thread is not blocked when the game loop is working.
The GUI has a utility for finding all the actions possible for clicking a card. Currently, there's only playing a land, but it will also check for playing spells or activated abilities, unmorphing etc. in the future. That Utility also checks if the action is legal (timing, only one land per turn etc.)
what aparently doesn't work is discarding excess cards at end of turn. While it's easy, I've chosen to show you what I have as soon as drawing and playing a land works.
If you would click yourself all the way through until a library is empty, you would notice that the game doesn't end with that. Although the state based action does exist, the loseGame() method of player is a No-Op.

okay, enough for now. Have fun playing some real games ;)

Getting a runnable program

2010-03-30T09:44:00.000-07:00

It's a nice thing to get everything right the first time. I think I have many things working already, among them are characteristic-setting effects, replacement effects, skipping turns, taking extra turns, and more than two players.

But what I don't have is a game, which is rather disappointing. Sometimes, I think "okay I want to really try it out, a real-world situation. just add in the glue that's missing and make a simple GUI", and then I realize how much of the glue is missing.

Even though I have effects, I have neither spells nor abilities. I can't play cards or abilities. I have (vanilla) creatures, but no combat. I haven't even tested zones, not to mention the Stack.

Okay, now that I finished whining, let me say that I'm still on this. I'm not giving up. The last few days, I focused on the tight core of magic. Turn order is done, all with phases, steps and priority. Next comes the zones, excluding the Stack for now. When I'm done with that, I'll try to program playing a land, which is drastically different from playing spells or abilities.

This should be enough "core engine" to let me finally play a game. Draw a card, play a land or not, pass priority back and forth until it's the opponent's turn (myself again, no AI yet), and so forth.
Of course, there are needs besides the core engine. Most obviously, a GUI. The other two that come to my mind are decks, which i have started already, and a "controller". LaternaMagica has a Player class, which handles life points and so on, but there's no way yet to to make decisions. But that's another story ;)

Quick follow-up: an important thing I've forgotten for my to-do list is state-based actions. it would be too bad if a player doesn't die when he has no life (however that should happen without creatures or spells...)

Undo ... and replacement effects!

2010-03-26T07:45:00.000-07:00

I finally got time to work on Laterna Magica again. It wasn't that exciting, just adding undo support to all the classes that already existed. While I browsed the classes and looked for actions that I hadn't revised yet, I found the LifeTotal class. Its job is easy: store the number of life points for a player, and whenever it changes, inform listeners.

...except that there are replacement effects. Only because I want to change life points, that doesn't mean it happens! what could be done?

Surprisingly, the solution looks very similar to my undo engine: Every modification is encapsulated into an edit and stored in the engine. If you want to undo something, the undo engine knows what happened, and every single edit knows how to revert itself. For the caller, it's only addListener(myListener), but inside there's new AddListenerEdit(myListener).execute().

Similarly, the replacement engine is the authority for performing replaceable actions, like gaining life. Calling gainLife(amount) really means new LifeEvent(amount).execute().
Execute uses the replacement engine to apply all replacement effects. Those may replace the event with another event, until all are through. The resulting event is then really executed (the implementation method is called execute0).

Edit and ReplaceableEvent are not connected. Both have an execute method, but that's more or less coincidence. Logically, there is a connection. Look at execute0 from LifeEvent:
public void execute0() {
    ((LifeTotalImpl) getPlayer().getLifeTotal()).fireLifeEvent(this);
}

//...and from LifeTotalImpl

void fireLifeEvent(LifeEvent e) {
    CompoundEdit ed = new CompoundEdit(getGame(), true, "Adjust " + getPlayer() + "'s life by "
            + (e.isGained()? "+":"-") + e.getAmount());

    new AdjustLifeEdit(e.getChange()).execute();

    // Guaranteed to return a non-null array
    Object[] l = listeners.getListenerList();
    // Process the listeners last to first, notifying
    // those that are interested in this event
    boolean gain = e.isGained();
    for(int i = l.length - 2; i >= 0; i -= 2) {
        if(l[i] == LifeListener.class) {
            if(gain) ((LifeListener) l[i + 1]).lifeGained(e);
            else ((LifeListener) l[i + 1]).lifeLost(e);
        }
    }
    ed.end();
}
Two things are of importance here: First, changing the life is done through an edit, so it can be undone. Second, informing the listeners is encapsulated ina compound edit, so that everything related to this event is grouped together.

I'm quite proud about this piece of code; I expected replacement effects to be very hard, but as it turns out, if there are no flaws in this concept, they should be quite easy.

Progress: LaternaCommon

2010-03-24T13:40:00.000-07:00

The second thing I've done in the last months is LaternaCommon. It is more or less a collection of useful utilities:

It provides a single, application-wide TreeProperties object, loaded from a configurable location
Configures log4j from a properties file, either configured directly, or by naming a property which stores the location
Provides an error-handling dialog for uncaught exceptions or to invoke manually
last but not least, it has a tool that can automatically unzip a file inside the jar. this is very useful to init an application on its first launch.
With this utility, you store a regular zip file inside the jar, and configure a destination directory and a check file on the file system. If the check file is not found on launch, the zip file is unpacked to the specified directory. Any number of zip files can be specified this way.

I really like how these features all integrate: if the properties don't exist, unpack them. then, configure logging using the properties. last, use the logging utilities for error handling.
You can use this, too, for free. However, I haven't yet uploaded a jar'ed version of it.

Okay, that's for now, and don't worry, in the last few days I resumed development of the core program!

Progress: TreeProperties

2010-03-20T16:00:00.000-07:00

I just realized that I didn't post anything for about two months. Well, I did do something, and I want to keep you up.

I have to say that code versioning systems like SVN are a great thing. Besides having a backup on the internet, I'm able to trace back my actions in the last two months. You can look here anytime to see what I was coding recently.

My task was to rework the TreeProperties system that i have come up with sometimes. The point behind it is that you can store properties in simple text files and, for example, implement localization this way. Well, java has something like that built in, but my Library allows much more, the biggest pro being that properties can be split over several files and keys are hierarchical. You can read more about - and download - it here.

Then was a long pause, I took a vacation and went skiing. After that, work went on, and I added many features, fixed bugs etc. In a nutshell, what the library is able to do is:

Store properties in a tree structure of multiple files
A file can reference another file, which is then parsed in the same way. Thus, any structure of files may be used to realize the needed properties.
Use hierarchical property-keys, like "/lang/en/save"
The namespace mechanism is independent of the file structure, i.e. not bound to a directory structure. When a file is referenced, it inherits its referrer's namespace. For example, if you reference a file with the key "/lang/en", its "save" property has the full key "/lang/en/save". However, if you prefer, you can reference the file with the empty key and literally use "/lang/en/save" in the included file for the same result.
Support for many data types
Unlike the java Properties class, which only supports unparsed string values, TreeProperties supports many data types out of the box - no more casting and parsing when accessing properties! Data types include all of the java primitive types, String, BigInteger and BigDecimal, Date and Calendar, File, Path and URL. The mechanism of data types is easily extendable. It requires implementing one interface and registering the type - that's it!
Special attention goes to the Path type - it adds an abstraction to regular java files that allows to use system properties to be substituted in the path. for example, the values "~/file.txt" or "${user.home}/file.txt", interpreted using the path type, both represent the file "file.txt" in the executing user's home directory. Including files (see above) uses the path type to parse the include, therefore the included file may be personalized for each user, allowing him to set preferences without annoying other users.
Simple access to the API
Most needs don't go beyond reading and writing existing properties. Therefore there's a class for exactly that - it has convenience methods that return the standard types already cast, allows default values, and supports localization. The only reason to read into the API is if you need to store new properties.
Easy GUI
TreeProperties is a background utility that makes a developer's life way easier. However, now and then there's a case when it steps into the foreground. If you want to show a GUI to the user to let him edit the values, don't build it yourself. It's already there! Setting up a GUI with labels and input components to allow the user to edit properties requires a single method call. what you get is a fully layouted swing panel, ready to add to your GUI. The input components are adjusted for the data type - (formatted) text fields, checkboxes and dropdown fields - and initialized to the current value. Changes to the inputs write to the properties object and are therefore available immediately.

I hope you enjoyed the insight and my work - TreeProperties is open source and can be downloaded as a single jar file. More infos about file formats and usage here.

Next time is about the new sibling of the LaternaMagica project, LaternaCommon, which adds even another level of convenience for the developer in the areas of logging, error handling and deployment.

Implementing Undo: A working approach

2010-01-24T08:37:00.000-08:00

When I realized that the need for an extra parameter really hurts the usability, I had to rethink the way of storing moves. Additionally, moves should be executed immediately, and not simply stored and scheduled for later execution, to make the semantics feel more natural.
By the way, I changed the name from Move to Edit, since that is the classic name for undoable stuff. Not that it would matter too much...

I didn't want to give up the tree, but needed a way to get the parent without using a parameter. Gladly, I found a solution that makes it pretty easy to create the right hierarchy. In a nutshell, the node that is currently appended to is stored in the controller, and when a node is created, it automatically finds the controller that belongs to the game.
This way, I was able to keep my tree structure and only had to do minimal changes. First, I had to change the Edit constructor to add itself to the controller. Second, the controller needed some notion of the current parent node.

Well, there were some problems on the way... I wanted to automatically execute edits at creation. the problem is the order of initialization. Imagine this:

abstract class Edit {
    public Move() {
        //add to the controller...
//then:
        execute();
    }

    public abstract void execute();

    public abstract void rollback();
}

class MyEdit extends Edit {
    private Object importantValue;

    public MyEdit(Object importantValue) {
        super();
        this.importantValue = importantValue;
    }

    public abstract void execute() {
        //do something with importantValue
    }

    public abstract void rollback() {
        //undo something with importantValue
    }
}

execute is called in the Edit Constructor, which is called at the beginning of initialization, before importantValue is set! Although it's logical that the superclass must be initialized first - starting with Object, which reserves memory on the heap to store atributes in the first place - this leads to the requirement for some annoying workarounds. For this, it's just to move the execute out of the constructor - it is essentially done after constructing any move. I will show another workaround later - for the random number generator - until then, my new code is online; i had a hard time with subclipse, but everything's alright now. feel free to peek into laterna.magica.edit, and laterna.magica.timestamp; yet the only classes to use this new development

Implementing Undo: Trial and Error

2010-01-16T15:01:00.000-08:00

I'm working eagerly on undo, and have a few thoughts to share on it. first, let me say that it's really not easy. so many thing can go wrong, since undo should mean "create a state as if the last action had never occured". it's easy to forget one of the implicit things that happen when you change something. if it's an event listener, or updating some kind of cache, there are so many possibilities.

the first thing to do when you start a programming task is deciding your goals. for undo, I had two goals of great importance

it must be possible to divide big actions into several small ones. ideally, every action is so small that it only changes one value. in other words, an action should be simple enough that you can find almost all bugs
it should be easy to use the system. magic has many cards, and if the majority of card code is related to the undo system, that can't be good. coding cards should be easy, ideally fun, so that many of them get implemented.

these don't really sound very compatible. be very precise and document every action, but don't bother me with it...

the second should be looking for help and reference material, but I just skipped over to the third one: error ;)

my first thought was a tree of actions with a controller actually executing of them. the controller checks that actions are executed in proper sequence. the work would be to create and append the action, and then let the controller execute it. the parent action is passed as a parameter to the modifying method so it knows where to plug the action into the tree:
//from laterna.magica.timestamp.Timestamp

private TimestampFactory f;

private int              timestamp;

...

public void updateTimestamp(Move m) {

    //the constructor plugs the move into the tree

    //with m as its parent

    Move parent = new CompoundMove(m, true);

    //plugs in the move which creates the next timestamp

    //for the factory
    f.nextTimestamp(parent);

    //plugs in the move which updates this Timestamp's value

    new UpdateTimestampMove(parent);

}

...

private class UpdateTimestampMove extends Move {

    private int               before;

    public UpdateTimestampMove(Move parent) {

        //Move does the tree stuff

        super(parent);

        before = timestamp;

    }



    @Override

    public void make() {

        timestamp = f.getCurrentTimestamp();

    }



    @Override

    public void undo() {

        timestamp = before;

    }

}

//from laterna.magica.timestamp.TimestampFactory

private int currentTimestamp;

...

public int getCurrentTimestamp() {

    return currentTimestamp;

}

public void nextTimestamp(Move m) {

    new NextTimestampMove(m);

}

...

private class NextTimestampMove extends Move {

    private int               currentTimestamp;

    public NextTimestampMove(Move parent) {

        super(parent);

        currentTimestamp = TimestampFactory.this.currentTimestamp;

    }

    @Override

    public void make() {

        //Set the timestamp after that of this move as current

        TimestampFactory.this.currentTimestamp = currentTimestamp + 1;

    }



    @Override

    public void undo() {

        //Resets to the current timestamp of this move

        TimestampFactory.this.currentTimestamp = currentTimestamp;

    }

}
You know what? a call to updateTimestamp() doesn't even really update the timestamp! and even better, it isn't correct just because of that. the line
currentTimestamp = TimestampFactory.this.currentTimestamp;
is executed when the move is constructed. so, if two such moves are constructed before any of them was executed, they bear the same value.

this is known as "lost update": you expect something to be executed in the order read-compute-write-read-compute-write, but really it's read-read-compute-compute-write-write, or something similar. both compute steps can't take into account the other computation, respectively, and the first write step is plainly overwritten.

this is exactly the problem with the code: what you expect (having the new timestamp stored after the call) ist not what the code does, and such misunderstandings are a major source of bugs. additionally, the second point is almost ignored. this layout requires an additional parameter in every method that does the slightest modification, and a manual "execute" in the controller to do the actual work.

impressing how lines fly if you really have something to talk about! i will continue with this story very soon, until then here's a quick lines-of-code count with cloc.pl:

http://cloc.sourceforge.net v 1.08 T=1.0 s (138.0 files/s, 8966.0 lines/s)
-------------------------------------------------------------------------------
Language          files     blank   comment      code    scale   3rd gen. equiv
-------------------------------------------------------------------------------
Java                138      1497      3126      4343 x   1.36 =        5906.48

Impressing, there are alone 1.5k EMPTY lines in my program ;)

Complex systems

2010-01-07T02:26:00.000-08:00

Previously, I said that business applications were not interesting from a programming perspective. Well, I think this is true in general, but there's probably one big exception: Enterprise Ressource Planning systems. These are pretty complex, allow plugins and customization to a big extent.
Another thing that identifies sophisticated systems is the modelling of not only data but also actions in the software. This is very important in ERP systems, so that decisions are traceable, and the output of employees or departments is visible.

This came to my mind during today's Business Information Management class. It may be a little off-topic, but it's good to see that there's interesting software around besides games.

Pros of Undo

2010-01-04T12:14:00.000-08:00

The following is an interesting idea, and it's not one of mine. I can't find the source at the moment, but it was somewhere in the slightlymagic.net forums.

The idea is that Undo implies the recording of each action during a game, and that this information can be used for many different things: Storm counts the number of spells played during the current turn, War Elemental is sacrificed if no opponent was damaged during the turn.

But the most interesting thing is last known information. This is the concept that if a card changes zones, its state directly before it left the zone is used for effects that referenced it earlier. For example Fling: This card requires you to sacrifice a creature, and then takes its power. However, the power is not taken from the graveyard, but from the last time the creature was on the battlefield: If it was equipped, the modified power is taken, even though its power is back to normal in the graveyard.
Last known information is used more often than that: Every ability that triggers from an object leaving the battlefield may require it.

However, there's a difference to Storm and such: Storm only looks into the past, on what happened, but last known information requires you to actually go back, to see the whole game state at that time, so that you can check the card's characteristics. I'm not entirely sure if Undo is suitable for that, but I will definitely think about it.

Intelligence

2009-12-19T04:40:00.000-08:00

today is nothing about programming, just philosophic thoughts about the concept of Intelligence.
It's hard define intelligence, but one thing that for sure sets us apart from computers (currently) is our extreme potential of learning. No matter if it's the complex rules, or the uncounted combos and strategies, we play magic without any problems. To get a computer to play magic, we need complex programs and have to manually teach it what is good and what bad play.
But intelligence is nothing bound only to the brain. The brain is a very complex structure of neurons that, every one on its own, only does basic tasks. however, the sum is much greater than its parts.

we're able to let computers perform basic operations, so we should also be able, in principle, to develop a really intelligent program.
A nice example is Conway's Game of Life, a cellular automaton with a very simple set of rules. For every state, the next "generation" can be calculated by applying the rules. By this, it's possible to encode programs into the pattern. In principle, this game is mighty enough to do any calculation - even intelligence!
And now, we look at that gigantic pattern as it evolves and changes. It's not able to communicate with us directly, but with the right understanding of what the movements mean, we could "read its mind"... maybe it's thinking about its creator?

Undo

2009-12-17T13:02:00.000-08:00

Imagine we are in such a good mood that we forget all our sorrows, make big business, and one day we notice that our earth isn't very well. We better had implemented undo so that the tropic rain forest is up and fossil oil is down again...

that's one of the hard parts with undo: the consequences of your action must be undoable. the second is not to forget anything.

What are the consequences of playing a card? you tap your lands, pay the costs, and put the spell on the stack. so to reverse that, is it enough to take the card back and untap your lands? in very certain cases, maybe, but not generally. a single triggered ability might crash your concept. there might even be abilities that triggered from untapping lands, because of the undo!

the second point is the other side of the same medal. if you view a triggered ability not as the consequence of playing a spell, but a different thing, the matter goes from "undoing all consequences" to "not overseeing other actions caused by playing the spell". while it effectively means the same - really going back to that same state - it's good to see the different aspects

in my opinion, the deeper you look into the game, the easier it is not to forget an action. if you have looked into the comprehensive rules a few times, you can notice how detailed everything is, timestamps, priority and so on. if we don't only look at huge things:

play a card, triggering an ability

but at the small ones:

tap the land for mana
an ability triggers
the ability is put on the stack
you receive priority again

all these are very small actions that are easily undone, and multiple actions are grouped into bigger ones, like playing a spell (and everything that happened in between), declaring attackers, a full phase, and turns. This way, you can quickly choose what you want to undo.

Program Architecture

2009-12-12T04:29:00.000-08:00

A program's architecture is very important. Like with a real house, it literally prevents the program from breakng down. If you don't make enough preparations (walls not solid enough), your program might not be able to have the features you want (a billard table). If you want to place a billard table in your house, you better make sure it can bear one.

A very common architecture in enterprise- and web-applications is the Multitier-Architecture. in this architecture, there are multiple tiers that communicate with each other and add abstractions. a very popular separation of tiers is the following (from bottom to top)

Data tier
This tier is not much more than a database server, responsible for storing and retrieving data.
Logic tier
The logic tier communicates with the data tier and processes the information. For example, it could sum up the prices of a shopping cart.
Presentation tier
This is where the user comes into play. The presentation tier doesn't know the data tier directly, it only calls the logic tier to get structured information. It then transforms that information into something the user might like, like an HTML-Page.

Enterprise applications are - don't be offended - pretty dumb in my mind. Most of the time, all you do is retrieving data, apply some calculation, and pass it to the user. there's not the "art" in it that makes programming interesting - complex algorithms and data structures; the sort of thing you get your success moments from.
On the other hand, games are by definition complex. It's what makes the game fun - easy to scope, but deep in possibilities. Look at Settlers of Catan, you know what I mean.

So, this "primitive" multitier architecture is perfect for business applications, but not for a game like magic. I have, however, some architecture in mind:

All of these parts are fairly complicated:

The game state includes all of the cards with their abilities, the zones, turns and phases, the players and even a random number generator.
The random number generator should make it possible have two games being absolutely identical, which allows for duplicating a game for network play, saving, replaying and so on. The generator also has to support the "Undo" i described.
The rules engine is the classic of a complicated thing. I don't think it's possible to fully separate this from the game state. For example you control a Glorious Anthemn. Is the +1/+1 bonus part of the game state or of the rules? However, other parts can clearly be separated: A player's starting life and hand size in Vanguard, or alternate winning conditions, and the ability to play the general in Elder Dragon Highlander
The payer abstraction in the next stage is different from the one in the game state. the state's player's purpose is to store his information, like life, cards and so on. In this stage, a player's purpose is to make decisions. The way of making a decision is of course different for the three types of players.

You yourself want to see the game state in a nice GUI.
The AI "only" needs to access the game state and rate its possibilities
A network player has his own GUI at his side of the connection, but what you see is only the decision he sends to you, which is enough because the game states are identical on both sides.

i hope you enjoyed that insight! bye!

Creating a state tree

2009-11-28T16:40:00.000-08:00

I'm back at min-max for a short question: How do you search the possible sequences of moves in a game?

well, there are two ways: one is, you copy the game state to try different plays. this guarantees you that you don't accidetially manipulate the game, even though you only wanted to test some moves for the computer. it has two downsides: one, you have to take some preparations so that your game state is copyable. magic is a complicated game, and it's easy to forget things. two, it takes up space. while this sounds not too much a problem nowadays, java by default starts with 32MB of memory. I did a test, and that didn't even fit the full game tree of the way easier game of quarto, which I presented earlier.

the second way is to enable undo. you work with the original game, make moves and undo them after running the evaluation function. memory is not the problem here, but the first one stays. an undo function is very complicated to implement, because magic has so many facettes.

I think that the second aproach is the better one. While it may take more work, you will want an undo function at some point, and in addition it implicitly allows some cool stuff: given the initial game state (the order of libraries), you can duplicate a game by applying the same actions to that state. this allows for storing a game state as a file, replaying awesome matches, and easily implement gaming over the network by simply transmitting an action.

html-Comprehensive Rules

2009-11-23T14:36:00.000-08:00

To be precise, the title is a little mis-leading, but it is effectively that.
One part of my program is a parser for the comprehensive rules. It converts the text-version that you can download from Wizards into an xml-File, which is formatted as html with xslt. You can view it like any other html page in your browser.
My file has a very convenient features opposed to those directly from wizards: Links. Everywhere there's a cross reference between rules, you have a hyperlink that lets you directly jump to it. My next version should also have images for the mana- and tap symbols.

You can download the result directly here: xml and xsl, both are needed for proper display.

If you want to run the program yourself, you have to take some preparations (you may just ignore this if you're not into programming):

laterna and treeProperties (both on the SVN) are two distinct projects, you will need both. Additionally, I use jdom for creating the xml. You have to configure laterna's build path to contain the both.

I hope you enjoy it!

Code online!

2009-11-20T09:04:00.000-08:00

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

2009-11-12T02:37:00.000-08:00

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.

Performance of min-max

2009-11-09T14:01:00.000-08:00

The min-max algorithm builds a tree of all the possible moves game states and then determines the optimal play. this sounds very expensive, and it is. to emphasize this look at this (I don't optimize anything like symmetric or rotated board positions, and don't terminate before the board is full):

tic-tac-toe, from my previous example, has one type of pieces per player and nine fields. the first move can therefore be one of nine possibilities. The second move has only eight fields free, and so on.
the total number of games is therefore 9*8*...*2*1 = 9! = 362880

Quarto is a "little" more complicated:

there are sixteen pieces with four characteristics:

small/tall
light/dark
hollow/massive
square/round

there are sixteen fields, arranged in a square
for his move, a player may take any piece and place it anywhere on the board
a player wins if his move creates a line of four pieces that share at least one characteristic. Lines can be in any direction, including diagonally

the first player can choose between 16 pieces and 16 positions, creating 16² possible first moves. The second player can choose one of the fifteen pieces and one of the fifteen fields, creating 15² possible second moves for every first move.
the total number of games is therefore (16!)² = 437763136697395052544000000 ~ 437*10²⁴
i had to use a dedicated mathematical program to calculate this, because regular java 64 bit longs weren't enough!

you see, creating every possible move is almost impossible for a game like quarto, and Magic doesn't even have a finite game tree. (for example, if both players have necropotence or something, both players can indefinitely long pass the turn). so how can you apply min-max to magic?
by introducing a reward function: instead of looking forward until the end of a game and saying -1, 0 or 1, you evaluate a board state and assign it some value between -1 and 1.

This is the real art: The reward function will directly influence your AI's performance. The better it evaluates the board, the more accurate the AI will behave.

The Min-Max Algorithm

2009-11-09T07:05:00.000-08:00

I like to say "AI is an interesting topic, as long as you don't have to implement it". I think this is very true, because AI is obviously very interesting, but implementing some "intelligent" algorithm may be anything between annoying, boring, monotonic and challenging, hard.

The Min-Max algorithm builds on this though: Every player takes the move that is the most beneficial to him, and every game state is measurable somehow. The easiest move to measure is one that ends the game: The winning player has a "reward" of 1 (maximum) and the losing player has a reward of -1 (minimum).

You see here the end of a tic tac toe game. Green (and the one yellow) are your (circle's) turns, orange is the opponent.

First, you start building the decision tree from the initial state to the final states. Then, you determine the outcomes of the final states. Most of them are draws in this example, meaning no reward for anybody. Two of them are losses and are assigned rewards of -1.

Now, you go back through the tree to the predecessors of the bottommost states. Since you made the move, you maximize your reward. For example, the maximum reward for the yellow node's predecessor is 0, so that node is assigned 0, too.

The next time, it's your opponent's turn. Stepping up one node again, that node has two predecessors, one with 0 and one with -1. Your opponent minimizes your reward, so the node is assigned the minimum of possible child nodes, -1.

We finally reached the original turn where you have three choices, one leading to a draw and two to a loss. You maximize your own reward and choose the option that leads to a draw, which was the final decision made by the min-max algorithm. At this time you know that the game will be a draw if the opponent has the same thoughts as you. It's tic tac toe after all!

that's the basic thought behind min-max, but i guess you see how this is not applicable to Magic. Check back for the details!

What can a Magic Program do?

2009-11-08T06:42:00.000-08:00

When you do a program, you have to ask yourself what you want from it - at least in Open Source, in commercial projects you tend to as others what they want from it...
my ambitions usually go very high, and it's not very different with Laterna Magica (that's how I named my project). I basically replace the question "What should it do?" with "What can it do?".
I want to list some features that a Magic program can provide:

Rules Enforcement
This is one of the two features that are the most interesting - and most difficult - features.
Rules enforcement means that you have to teach the computer what a player may do. It's hard enough to teach a human to play Magic, and humans are at least intelligent.
Implementing a rules system usually means to describe what the parts (cards, players, but also turns and combat) of the game are, what the possible moves and their outcomes are, and what moves are legal for a game state (the rules).
Human vs Human
Such a game is imaginable without rules enforcement. It's like paper magic, you make sure yourself that no one is cheating. examples for multiplayer Magic programs without rules enforcement are Apprentice and MagicWorkStation. This is relatively easy to implement, because you can skip the very huge rules enforcement part and can focus on a usable user interface and the network aspects. an upside to the user is that you can take shortcuts easily, a downside is that you may accidentally make illegal moves.
Singleplayer Magic & AI
Singleplayer games are harder, because it requires the computer not only to enforce the rules, but also to implement an Artificial Intelligence to make decisions itself, which is likely even harder than rules enforcement itself.
Multiplayer games
Games with more than two players are a challenge for several reasons: you're likely to do it over network, so you have to have a server which maintains game state, or connect every player with each other. Additionally, a user interface that shows three players is hard.
Good User Interface
"Last but not least": having a good interface is very important, because no matter how correct your rules implementation or AI is, in the end it's about playing a game, and that has to be fun after all. Maybe you're interested in This youtube video about the new MTGO interface. Wizards seems to have taken other Magic programs into account when designing this; some of the features seem similar to Incantus.
I list it last here because it's far away from the other topics: my other four points are "low level" (although ideally the AI is also independent from the rest), and in a perfect world you could build a user interface on top of a program that was developed with no thought about it.

Welcome in the complicated word of Magic: the Gathering!

2009-11-07T01:52:00.000-08:00

Magic is a very deep and interesting game. It has several thousand different cards that make every game a unique experience, and hundreds of pages of rules that describe in detail how to manage all those different cards.

while this sounds intimidating for some people, i like the idea of such a well-defined system, and that's why Magic attracts so many programmers, like me.

I hope you enjoy my posts, and please leave comments if you feel like it.