The Oracle Parser

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

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


For a rough guidance, the builds 1 through 13 were made on October 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

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

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

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

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

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

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