Saturday, December 19, 2009

Intelligence

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?

Thursday, December 17, 2009

Undo

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.

Saturday, December 12, 2009

Program Architecture

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!

Sunday, November 29, 2009

Creating a state tree

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.

Monday, November 23, 2009

html-Comprehensive Rules

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!

Friday, November 20, 2009

Code online!

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

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


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





//The matcher defines a set of cards to be affected
Matcher m1 = getCardMatcher(getMatcher(ENCHANTMENT));

/* Then, an effect is registered in the game with that matcher.

 * In sum, this represents a static ability saying,
 *  "All enchantments are green."
 * Well, not exactly. It's more like,
 *  "All enchantment cards in all zones are green."
 */

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


/* 

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

 */

MagicObject card = new MagicObjectImpl(g, new CardTemplateImpl());
 

//Here are some effects - should be obvious
//The order matters here - the effects get timestamps

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


//All these effects are added to the card.

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


//now, the result is printed out

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



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

Thursday, November 12, 2009

Traps in the rules system

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

Monday, November 9, 2009

Performance of min-max

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

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!

Sunday, November 8, 2009

What can a Magic Program do?

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.


Saturday, November 7, 2009

Welcome in the complicated word of Magic: the Gathering!

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.