Saturday, December 31, 2011

Quantum Mechanics and Magic AI

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

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!

    Friday, December 30, 2011

    Java 5 compatibility is hard

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

    Monday, December 26, 2011

    Getting more out of Maven

    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.