On the textual representation of mana symbols.

I’ve been workin on Gleemin’s ability text interpreter, particularly the part of the grammar that recognises mana expressions. I’ve added a small update on Gleemin’s repository on Git. The following is from the comments in the latest source file (mana_grammar.pl). It will probably be of interest to anyone who is writing or thinking of writing a parser for ability text.

+-Textual mana symbols-+

The text version of the CompRules and the Magic Set FAQs consistently list mana values as capital letters or numbers enclosed in curly braces: {12}{X}{W}{U}{B}{R}{G}, etc.

The Gatherer’s text spoilers and text spoilers from sets’ product pages on the M:tG site take a more liberal approach.

The Gatehrer’s text spoilers list mana values as capital letters or numbers when they appear in cards’ mana costs (the mana symbols in the upper right corner), and as capital letters or numbers enclosed in curly braces when they appear in a card’s text box.

For example:

Name:       Abbey Matron
Cost:       2W
Type:       Creature — Human Cleric
Pow/Tgh:    (1/3)
Rules Text: {W}, {T}: Abbey Matron gets +0/+3 until end of turn.
Set/Rarity: Homelands Common, Homelands Common

On the other hand, hybrid mana is represented on The Gatherer as capital letters enclosed in parentheses in cards’ mana costs and as lower case letters enclosed in parentheses, enclosed in curly braces in a card’s text box:

Name:       Avatar of Discord
Cost:       (B/R)(B/R)(B/R)
Type:       Creature — Avatar
Pow/Tgh:    (5/3)
Rules Text: ({(b/r)} can be paid with either {B} or {R}.)
            When Avatar of Discord enters the battlefield, sacrifice
            it unless you discard two cards.
Set/Rarity: Archenemy Rare, Dissension Rare

- but the other way around minus the curly braces in the text spoilers on sets’ product pages:

Card Name:   Avatar of Discord
Cost:        (b/r)(b/r)(b/r)
Type:        Creature - Avatar
Pow/Tgh:     5/3
Rules Text: ((B/R) can be paid with either B or R.)
            When Avatar of Discord comes into play, sacrifice it
            unless you discard two cards.
Set/Rarity: Dissension rare

It’s also interesting to note that the reminder text in The Gatherer text spoiler refers to a symbol that can not be found in the rest of that text (since it doesn’t use the same notation as the mana cost it is meant to clarify).

Curiously, searching The Gatherer for B/R seems to find the same (7) cards as searching for b/r, while searching for {(b/r)} finds nothing.

Similar considerations apply to:

Monocoloured hybrid mana (listed as {2/W} etc in the set FAQs and CompRules):

Name:    Advice from the Fae
Cost:    (2/U)(2/U)(2/U)
Type:    Sorcery
Rules Text: ({(2/u)} can be paid with any two mana or with {U}. This
            card's converted mana cost is 6.) Look at the top five
            cards of your library. If you control more creatures
            than each other player, put two of those cards into your
            hand. Otherwise, put one of them into your hand. Then
            put the rest on the bottom of your library in any order.
Set/Rarity: Shadowmoor Uncommon

Phyrexian mana (listed as {W/P} etc in the set FAQs and CompRules):

Name:        Act of Aggression
Cost:        3(R/P)(R/P)
Type:        Instant
Rules Text: ({(r/p)} can be paid with either {R} or 2 life.)
            Gain control of target creature an opponent controls
            until end of turn. Untap that creature. It gains haste
            until end of turn.
Set/Rarity: New Phyrexia Uncommon

And also to Snow mana. In particular, the symbol for Snow mana is listed as {S} in FAQs and the CompRules, but appears as {S}i} in Gatherer searches, except apparently in the case of adjacent snow mana symbols where it appears as {S}i{S}i}:

Name:       Frost Raptor
Cost:       2U
Type:       Snow Creature — Bird
Pow/Tgh:    (2/2)
Rules Text: Flying
            {S}i{S}i}: Frost Raptor gains shroud until end of turn.
            ({S}i} can be paid with one mana from a snow permanent.)
Set/Rarity: Coldsnap Common

-while in the text spoiler for Coldsnap, it appears as “oSi” (possibly as some kind of obscure in-joke on standardisation):

CardName:   Adarkar Windform
Cost:       4U
Type:       Snow Creature - Illusion
Pow/Tgh:    3/3
Rules Text: Flying 1oSi: Target creature loses flying until end of turn.
            (oSi can be paid with one mana from a snow permanent.)
Set/Rarity: Coldsnap Uncommon

Fun as all this variety may be, the grammar in this source file will have to focus on one kind of textual representation of mana symbols, lest madness sets in. This has to be the one in the CompRules, which are, after all, the “ultimate authority for the game”. Any other syntax will have to be compensated for at an earlier point in the parsing sequence (most probably the tokeniser).

Estimating the time complexity of traversing a full Magic: the Gathering game tree.

I think the title says it all, really. Let’s cut to the chase and jump straight in to the maffs!

We’ll be using the formula in Russel & Norvig (2003) throughout:

	O( b^m * n^m )


  • b, is the branching factor of the game, that is, the number of sub-trees that hang under a node of our game tree.
  • m, is the number of moves from the start to the end of an M:tG game.
  • n, is the number of unique permutations of a M:tG deck.

Obviously, the first two numbers, b and m, will have to be averaged over rough estimates, or at least I know of no other way to calculate them, but the empirical.

+- Deck Permutations -+

To calculate the number of unique permutations of a Magic deck, we need to take into account repetitions, ie the additional copies of each card that may be included in the deck. If we assume a bog-standard, mono-coloured, 60-card deck with a 36/24 spell/land ratio (we’re going for as general a case as possible), we have 10 different cards, 9 of them repeated 4 times, one of them repeated 24 times. We can find all permutations with:

	60! / ( 9 * 4! * 24! )

- which gives us, in calculator notation (you knew I wasn’t going to do that by hand, didn’t you?):


So a number in the general vicinity of 6 * 10 ^ 55.

+- Branching Factor -+

The branching factor for a game tree (or, really, any search tree) is the average number of branches under each node of the tree. For most games the branching factor is found empirically, by examining a sufficiently large number of games. Unfortunately, there is no database of Magic games recorded move-by-move, as there exist for chess and other games, so we can’t look one up.

The only thing we can say with any certainty about Magic’s branching factor is that it’s going to be larger than that of chess and other similar games. Well, the branching factor for chess is traditionally pegged at 35. So our Magic game tree is going to branch off at least 36 times each level, no? Therefore we will assume that:

	b = 36

If such arbitrariness bugs you, remember that we are trying to estimate the time complexity for a Magic game tree traversal. We know it’s going to be immense anyway so there’s no reason to not make the most optimistic assumptions we can. One way or another, this is not going to turn out to be a game tree that we can ever hope to fully explore in any useful amount of time, no matter how much we reduce it. So 36 it is, and we move on to the next number.

+- Number of moves -+

It’s very hard to know the number of moves that will be taken by all players during a Magic game, and even making a good estimation is very hard. The reason is that the Magic turn structure is not the I Go – You Go turn structure of classic board games like chess and Go. A Magic turn structure is recursive: a player can take any of four actions: cast spells, activate abilities, take special actions and pass priority. If the player does not pass priority, then he or she can again take any of those four actions and so on. So we can’t know how many moves the player will make until we figure out what moves the player will make. That’s not very practical.

Once more we need to make a rough estimate. Let’s say then that in an average two-player Magic game with 60-card decks, each player will make about 3 moves per turn for 10 turns, say play a land, cast a spell and attack with a creature or activate an ability. This gives us 60 moves for both players:

	m = 60.

- and we can go on with the rest of our work.

+- Putting it all together -+

Let’s recapitulate. We have:

  • n = 6.2089109065795883546442647025546e+55 [deck permutations]
  • b = 36 [branching factor]
  • m = 60 [moves in a game]

We can now calculate the time complexity to traverse a full minimax search tree for Magic, as follows:

	O(b^m * n^m) =>
	O( (36^60) * (6.2089109065795883546442647025546e+55 ^ 60) )
	= O(2.272461391808129337799800881135e+5564)

Yes, we knew it was going to be one humongous monster of a number. Just for the sake of it let’s assume that it takes one millisecond to complete each branch traversal, so that would translate to…


… years.

+- Alpha-Beta cutoff -+

Let’s now calculate how many operations we save if we employ alpha-beta cutoff, the garden-variety base algorithm without any frills. This time we need to take the square root of the branching factor, raised to the moves-per-game value:

	O(√(b^m) * n^m)

You may be seeing a “v” where you should be seeing a square root symbol, depending on your browser settings. The formula gives us:

	O( (36^30) * (6.2089109065795883546442647025546e+55^60) )
	= 1.8620901705458035221211890381952e+3394

- or, on our boring one-ms-per-operation machine:


… years again.

+- Where being shallow pays off -+

The above calculations are for traversing a complete Magic game tree, from start to end. Obviously, there’s no point in doing that. The average Magic player (that’s me) probably searches no further than 3 turns when she looks ahead, if she ever bothers to do any look ahead at all (hint: usually she just attacks with everything). Professionals, and more capable players may not even search that far, since their very extensive knowledge of the game possibly makes it unnecessary. But just for fun, let’s find out how many operations it would take to traverse a smaller tree, looking ahead no more than 3 turns each time.

We simply replace the “m” value with “3″, which gives us:

	O(b^d * n^d) =>
	O( 36 ^ 3 *  6.2089109065795883546442647025546e+55 ^ 3)
	= O( 1.1167444081873313441334253928412e+172 )

- for straight miminax, and:

	O(√(b^d) * n^d) =>
	O( √(36^3) * (6.2089109065795883546442647025546e+55^3) )
	= O( 5.1701130008672747413584508927835e+169 )

- for minimax with alpha-beta cutoff.

+- Conclusions -+

It is plain to see that goold old minimax, even with alpha-beta cutoff, is not going to, er, cut it, with Magic. Just with the algorithm on its own, it would be impossible to even lookahead the minimum of 3 turns that most human players should be able to manage. And remember: this is an optimistic estimate, based on an unlikely small branching factor, and a very conservative moves-per-game value.

Of course, there are a great many things we can do to cut down on the largesse of our search space. My preferred solution is to use knowledge, which seems to have worked fine for games like chess, in the past. I’ll discuss that in a later post.

Glee-min, Glee-max. Git it? Well, now you can…

I still haven’t done anything new with Gleemin. However, I’m now in the situation where, if I want to work on my code I have to do it from three or four different locations. So to synchronise everything I put it all on git, here:


You can browse it, read the README if you have some time (no, I mean _some_ time), and play around with it if you like. Note that the code is just that, the sources, no binaries. To run Gleemin you’ll have to download Swi-Prolog, but it’s painless from there, really. Well, it’s painless until somethign crashes. And something will, eventually. Like I (‘m sure I) explained in a previous post, there is a fatal bug somewhere in the AI code, caused by transferring everything from Win-LPA to Swi, and it crashes the game when you choose a deck that Gleemin doesn’t know (that’s everything except the deck “Raspberry”). For a full list of what you can’t do, read the README.

I’ll have to be honest with you: the most interesting part of Gleemin at this point is its MGL parser. And that’s not too extensive. Like I said, I mostly created the repository for my own sake. But, still, someone may want to have a look. In that case, don’t hesitate to drop me a line, etc.

Help! I’m trapped in text mode hell!

Screengrab of my text-mode desktop

mc, alsamixer, mp3blaster and top in tmux

screengrab of Links2


… the Linux text mode hell, if that makes any difference! ^_^

To be honest, I’m not sure exactly what is going on here. All I know is that I can’t load a graphical desktop and that it must be a hardware fault. At first I thought it was my graphics card, because its fan died. I figured I was too late, because I haven’t been able to start Windows (XP and 7) properly since then, neither X11 on my Fedora 12: everything freezes up after a few seconds. On the other hand, I can boot into Win 7 Safe Mode which is all gooey (see what I did there?) and, as you can see, I’ve been having such fun with all sorts of framebuffer-y madness in Fedora. I can even watch video, with mplayer. That’s actual video (with cvidix or fbdev2 as drivers), not ascii’sed video with aalib. Look:

Screengrab from mplayer video showing a frame from Fringe


[Er. Strictly speaking, I shouldn't be watching this. Please don't tell!]

After running a few diagnostics, it seems both of my memory banks have errors, but I doubt those are enough to cause all the trouble alone. I guess the only way to know for sure is to change both and see if there’s any change in the situation. I reckon, seven years is about 80 in RAM chip years, so it’s about time I got some new ones. And that goes for my graphics card too. Seven years- yep, that’s how old my system is. Or most of it anyway- I’ve already changed the motherboard and the graphics card fan, and of course the floppy drive has been dead for ages… I guess I’m going to have to upgrade soon. As soon as I can find work to justify spending money on new hardware that is!

In the meanwhile, I must say I’m having lots of fun, actually. I’ve gotten quite comfortable with all manner of text-mode applications that I’d never have bovverred learning to use properly otherwise. I tell you, dear reader, we are so spoiled for GUI’s these days.

But I digress. This post is really all about the fun I had with an operating system that is entirely free to use, and at its best when it looks its worst! And look:

Screengrab of Vimdiff


I’m even working on that Gleemin release that I promised. Just so you know.

Oh look, an update!

I’m posting to say that I’m still working on Gleemin, and I’m very sorry that I couldn’t keep my promise to Hellfish two weeks ago, now. There are more bugs than I expected… ah, I mean there are even more than I expected there to be more than. Anyway, I’m working on it, but it’ll take a few more days at least.

The truth is, now that I’m going through my code again, with the benefit of two months hindsight, it looks like something the good Dr Frankenstein could have pieced together if he worked with code rather than peoples’ bits. At least, some parts of the code look like that. Those are the parts I was working on as the deadline to deliver my dissertation loomed and I had to work 16-hour days to be able to make it. It’s really all one big hack, and I cringe to look at it.

So I’ll finish migrating the code to Swi and publish a binary, as I promised, hopefully in a few days, just so that anyone who may be interested can have a look at it and see what I’m trying to do. After that however, I’ll have to overhaul big parts of it, particularly everything that has to do with the AI. The reason for this is that I need to add a lot of code to the AI to make it competitive, and also to implement a Monte Carlo algorithm rather than minimax (or maybe come up with something better than Monte Carlo… frankly, I don’t think any existing techniques cut it, with Magic). Then, I’ll also need to add the 40% of rules that are missing from the rules engine, and also many, many abilities to the interpreter’s grammar.

As you understand, I can’t do all of the above with a shaky code base… The bugs that are coming up now that I’m migrating to Swi are an indication that the coding is not as solid as it should be, so I’ll need to stabilise everything before I go on and complete the engine and the interpreter. Then finally I’ll have something to develop the AI on for keeps.

Well, I guess that’s a plan. I’m not setting a timeline though. It will take some time and that’s all I can tell… But, really, the project is not dead, it’s just that I don’t want to make a release that is going to be completely pants :)

In the meanwhile, stay tuned. I was thinking of making some non-Prolog, non-Magic posts for a change, you may find something to interest you, as I’m working on a coding portfolio, so I’ll have various stuff to discuss, in relation with a number of other languages (including C, C++, C#, Java, Python, PhP, Ruby and possibly Erlang), as well as my adventures in Linux text-mode land. I also had a few ideas about another project involving Linux, natural language and Prolog, or possibly Python, or both. So, yeah, stay tuned, if you like that kind of thing.

Transferring Prolog code between Prolog implementations

Last week was my last exam for the academic year and with it the end of the year and the course. Yep, that’s it, university is over. Now the fun stuff begins :D

…and it begins with me starting to rewrite Gleemin for Swi-Prolog, so that it makes some sense to release the code (and related binaries) under an open license.

The reason that the code needs to be rewritten is that Prolog dialects have very subtle differences between them, even as they implement the ISO standard for the language. This means that the more your code increases in size, the more the probability that it won’t run on different Prologs also increases.

1. Homoiconicity.

One such subtle difference is in the way each implementation, well, implements some core features of the language, particularly its homoiconicity. For example, my own code makes heavy use of variable functor names, which are allowed in Win-LPA Prolog, but not in Swi Prolog. A variable functor name does what it says on the tin: it’s a variable used as the name of a predicate. So, in LPA Prolog you can write:

          Functor(Arg1, Arg2)

And then later instantiate the variable “Functor” to whatever functor name you want. For instance, you could bind “Functor” to “member”:

| ?- Functor(Arg1,Arg2) = member(Element,List).
Functor = member ,
Arg1 = Element = _ ,
Arg2 = List = _

This is cool because you can then do things like this:

	receives_priority(Player, State('Untap'), Priority, Play, [], []):-
		State = begins -> output(receives_priority, []).

(“->” is the _implication_ operator in Prolog)

In my code, the “State” variable can take one of three values: “begins”, “ongoing” and “ends”, which lets this particular bit of code execute only when the ‘Untap’ step “begins” (this rule says that no player receives priority at the beginning of the ‘Untap’ step and causes a relevant message to be output. The hint is the last argument of receives_priority/6, which stores the name of the player to receive priority; in this case, the empty list, so nobody).

This won’t work in Swi Prolog, because variable functor names like that are not allowed. Instead, the “=..” operator (pronounced “uneev“) needs to be used, like so:

	receives_priority(Player, Step, Priority, Play, [], []):-
	        Step =.. [State,'Untap'], State = begins ->
                output(receives_priority, []).

Remember that in (all) Prolog(s) you can bind whole predicates to variables. The “Step” variable here should be carrying a tuple of the form: State(Name), where State is as above, “begins”, “ongoing” or “ends” and Name is the name of a step (‘Untap’, ‘Upkeep’, ‘Draw’ etc).

Of course this is something that can be easily avoided, and corrected. To be honest I didn’t want to stop using variable functor names like this because it’s a very neat feature of LPA Prolog, so now I just sucked it up and went through my code to correct it for Swi.

2. Same predicate, different name

Different Prologs also often use different names for built-in predicates that do the same thing. For example, LPA Prolog has a removeall predicate that nondeterministically removes all instances of an element from a list (and binds the rest to a new list). Swi Prolog has a predicate that does exactly the same, but it’s called delete. The two have the same arguments but in different order, so it’s not enough to just replace all instances of “removeall” with “delete” in the source. For cases like this I’ve created a file called “Swi Compatibility Layer” (with tongue firmly in cheek) where I redefine, for example, removeall/3 in terms of delete/3, like this:


Obviously that’s a bit of a hack- there’s a more sophisticated way to do things like this, in Swi (but not in LPA) using goal_expansion/2 (for a discussion of this, look here), but at this point I just want to get the program to work on Swi. Later I’ll just go through the code again and simply replace all the “removealls” to “deletes”, etc, which will also avoid the small performance hit from this translation stage.

3. Different predicate, same name.

A rather more nasty problem is that of “faux amis” predicates. Those are predicates with the same name and arity, but that do different things. You can see how this sort of thing can drive you crazy and lead to bugs that are hard to identify.

For example, in LPA Prolog there is a predicate called atom_chars that converts between an atom and a list of character codes, while in Swi the same predicate converts between an atom and a list of characters.

This is the LPA version:

| ?- atom_chars(abc, Chars).
Chars = [97,98,99]

And this is the Swi one:

?- atom_chars(abc, Chars).
Chars = [a, b, c].

Conversions like that are very useful in Prolog for general IO, and so are very often used. You can bet I snared my foot in that trap.

In this case, I went through the code and changed every instance of atom_chars to atom_codes (the Swi predicate that does what LPA atom_chars does), and also some similar predicates like number_chars/ number_codes etc. Thank the gods for my trusty Notepad++! Then I realised that there’s a quicker way (through use of goal_expansion/2 as explained above) but by then it was a bit late. It’s OK though since I’d have hard-coded it in the end anyway.

4. Come back in ten million years.

I’ll close this with a funny error message I got from Swi Prolog:

?- X.
% ... 1,000,000 ............ 10,000,000 years later
%       >> 42 << (last release gives the question)

Remember that Prolog variables start with uppercase letters and Prolog is not strongly typed, so a variable like “X” can literally take anything as its value. Therefore the query above can bind X to the value of anything in the known universe. Eventually, X would bind to the answer to the question about Life, the Universe and Everything: 42.

Incidentally, this happened in the middle of writing to output and forgetting to flush it afterwards, so some of the capitalised output ended up being read by the Prolog listener as input. This is why it is a good idea to be hygienic and always flush your output when you’re done.

Milestone: Project delivered on 27 April, 2011

(This was originally posted, mostly verbatim, in the CCGHQ forum, in May 1, 2011).

Hi guys! It’s now three days since I delivered my project to the examiners so I guess it’s time for some news. I really didn’t have time (…or a life…) in the last couple of months to update anything.

Anyway, here we go.

Gleemin: the Magic Virtual Machine development update, the short version:

  • You can play a full game: play land, cast spells, activate abilities and do combat.
  • Oracle text is parsed directly and interpreted as a programming language, so that’s how spells/ abilities are implemented.
  • You can play against an AI but it’s currently weak, poor thing. It’s name is Glee-min. Ha-ha.

…and the long version:

- Rules Engine
The engine is some 60% complete, so you can play a more or less full game. By that I mean:

  • you can take most player actions except special actions besides playing land (so no flipping cards, unmorphing morphs etc),
  • triggered abilities are not yet implemented and static abilities are not centrally handled (I need to implement the layer system for replacement effects). You can cast three families of spells, burn, bounce, destroy target and what-I-call “buff/debuff” (Giant Growth/ Sickness). A scant few abilities are implemented: Haste, Infect, Wither and Lifelink (the last three because they’re part of the damage rules).
  • Combat is 95% complete: you can declare attackers and blockers, order blockers and assign lethal damage. You can’t order attackers yet (since most creatures can only block a single attacker anyway).
  • Mana is 80% complete, minus X-spells and hybrid costs. Oh and Phyrexian mana. Damn those Wizards R&D peeps! XD
  • No Loyalty abilities, so no Planeswalkers yet. Also, I haven’t really tested any permanents besides creatures and land, but any permanent with an activated ability (of those that are implemented) should be OK.
  • Did I mention the bugs? There’s two show-stoppers I’ve documented. I don’t think they’ll take too long to fix though (hey, famous last words! Yay!) [actually, those were fixed since this was posted on CCGHQ]

- The MGL (that’s Magic Game Language) Parser.

The parser is working and it’s how the engine resolves spells and abilities. There is also a “phrasal interface”, that lets you enter some commands to:

  • Identify the type of an ability: spell, triggered, activated or static. static and spell abilities are not really easy to distinguish like this, because their main difference is that they one is on permanents, the other on spells. So they still get mixed up a lot (basically, they’re both reported as spell abilities). [actually, this is not correct, as a CCGHQ user remarks: Sorcery and Instant spells can also have static abilities, eg "can't be countered" etc]
  • Verify an MGL phrase; so you can enter your own Magic ability text and see how it is accepted by the parser. It probably won’t be, at this point, as it only recognises a few effects, like I said. Anyway, it’s basically a programming language parser so it’s extremely anal about correct syntax and you’ll want to stick your hand in the screen, drag it out and bite its head off very often.
  • Also, it performs what I call “semantic” and “contextual” verification, by which I mean it needs a proper context for an ability. So if you have the MGL phrase: “Destroy target creature” and there’s no creature in play, it won’t recognise it as valid. It is a bit more practical than it sounds: the interface can be used outside of a game, using the database facts from a previously started game. Also, a different type of verification is possible, a “syntactic” verification which just checks that the syntax of the MGL is correct. However, semantic/contextual verification is used to find and verify the legality of targets during play and it can’t be done separately from semantic verification (a different, game-state agnostic set of grammar rules would be needed). So it’s not implemented yet as a separate feature.
  • Generate new MGL! Yay! You just enter “generate_MGL” in the Prolog command line, give it a type of MGL phrase you want it to generate and it will start returning phrases of that type. You get a lot of stuff like “Each Enchantment with Equip target player controls gains Islandwalk until end of turn” so it needs some more functionality added in, to weed that sort of nonsense out and again you need a valid context (ie, a game). On the upside, you can generate some pretty specific effects, with calls like:
    | ?- generate_MGL(return(Target,Type), Phrase). 
    Target = object('Goblin Balloon Brigade' - 1,['summoning sickness']) ,
    Type = 'Creature' ,
    Phrase = 'Return target Creature to its owner''s hand ' ;
    Target = object('Mountain' - 1,[tapped]) ,
    Type = 'Land' ,
    Phrase = 'Return target Land to its owner''s hand ' ;

    And so on. The phrase you get is given as an atom (a Prolog type), which means it needs to be converted to a comma – separated list for use in the engine (as an actual spell or ability). For now, the identify_MGL command can do that for you:

    | ?- identify_MGL.
    > |: Return target Creature to its owner's hand.
    [Return,target,Creature,to,its,owner's,hand] is an MGL spell ability

    … err, you need to remove the quotes and extra space at the end (inserted by the word-list-to-atom predicate… damn, that needs fixin’) and also add a full-stop, but it’s OK otherwise. Anyway, you can take this comma-separated list and add it to a card’s text box field in the database and that’s it, job done, it will work (but notice a little bug in the capitalisation of “Creature” and other types- that’s not 100% Oracle text. I know, I’ll fix it).

- The AI player.

To be honest, I was bouncing so much after making the parser work that I almost dropped all work on the AI, especially after seeing how Magarena uses Monte Carlo (props!) to great effect. But, I had to do it for the project and there was no time to implement Monte Carlo instead of just minimax, so here’s what I got:

  • The Ai is progarmmable with expert knowledge. That means it has different tactics for different decks and also for specific matchups. Tactics are modular rules that handle any player action: spell-casting, land-playing, mana-spending tactics and so on. They are “modular” in the sense that you can slot them in to any deck or matchup, since some decks will have similar overall strategies and will need, say, to prioritise spell casting in the same way (ie, “cast the fattest creature you have first” and so on). The functionality for using tactics is in place, but with two asterisks I’ll come to shortly.
  • In case the AI doesn’t have any knowledge encoded for its deck or matchup, it falls back to a statistic evaluation of the game. This currently uses a very basic version of alpha-beta minimax for playing land and casting spells. It also uses a separate “combat heuristic” for blocking (for now, it just attacks with everything). It blocks so that:
    • i) the highest possible number of blockers survive and
      ii) the highest possible power of attackers is blocked and
      iii) the opponent gets no better than a one-for-one trade in each instance.

    So it will block an attacker with more than one blocker if the attacker and no more than one of the blocking team bite it. I think it blocks correctly like this but combat was never my fortè. It does do some silly stuff, like blocking a 1/1 with a 2/1 when it has a 1/1 available- that’s because it’s not programmed to block for tempo, only for card advantage. It also doesn’t know that an attacker can kill it, so it won’t chump and will let a fatty through even if it will die to it. Obviously, these need fixin’. This blocking heuristic can be turned around to infer the opponent’s attack plan and try to counter it- this needs to be implemented.

    The two asterisks I mention above:

  • I don’t like the way I coded tactics- they’re normal Prolog, backwards-chaining rules. Figuring out the matchup uses a forward-chaining inference engine that I coded later. This one uses production rules of the form:
  • "if Condition then Conclusion". 

    Those are much more readable by humans. I should re-implement the tactics using this syntax. Btw, Condition and Conclusion can be any Prolog term so you can stuff basically anything you feel like in there, like conjunctions/ dinsjunctions or even full predicate calls.

    One reason I’d like to do that is because I would like to get some non-Prolog programmers (or non-programmers) to help with developping the knowledge-base. On the other hand, I have a more devious plan: to use MGL for creating new tactics. So you could say something like:

    "If an opponent does not control any creatures with Flying, each creature you control with Flying attacks this turn if able". 

    Kinda clunky but I hope you see what I mean. MGL is the scripting language of the engine, so it should be possible to write any sort of, basically, script- and call it from anywhere. Currently, that’s what cards are, MGL scripts, called by the engine predicates that handle spellcasting, ability activation etc. So why not use them in tactics? Well… that’s the (cunning) plan!

  • Like I say above, the expert knowledge database is currently quite poor. There’s only a few tactics that let it play any land, cast the first creature it finds and so on. I’ve been away from Magic for quite a while (since 2005) so I have no idea what decks are current and so on. I wasn’t really planning to do that on my own, so the point above (entering new tactics as MGL, or a more non-programmer-friendly syntax anyway) needs to be taken care of first. Also, since I switched to a proprietary Prolog I can’t make executables. I’ll have to move all the code to the free Prolog, Swi. All this will take some time. I can’t start before June ’cause I still have more assignments and exams to keep me busy ’till then. So I guess, stay tuned for more updates but not earlier than in a couple of months.

Finally, some planned future features;

  • I ‘ve promised an MGL to BNF translator and I’m still up for it, if there is still interest anyway :)
  • A real-play function, so you can play a real-world deck against a human opponent and let the application direct your play. That’s the only way to pit the AI against a human player at a sanctioned tourney, I think (otherwise there’ll be serious concerns about fairness etc). Of course, there’s always Magic Online…
  • A GUI. Ideally, I’d like to use an existing (open-source) one. Prolog can, actually, communicate with Java, C++, Python, C# and more. It depends on the Prolog though and it does take some work. Swi-Prolog (free, open-source) has a Java interface and a C/C++ interface. Win-Prolog (closed, proprietary) has a server that sends text to Java, C++, MS dot-Net languages (including VB) and Python. Ideally, I’d like to interface it with Perl or PhP and have it run on a server. We’ll see.
  • An interface to add cards in the db and also create new decks. Right now you can only do that “by hand” (modifying the source files).
  • Even better, a tool to download cards to the database directly from The Gatherer- but using the parser to filter them by implemented abilities (so you’d only get the ones that the engine can actually play).

OK, so that’s it. Comments, suggestions, flames, anything- I’m here.

Programming the AI with expert knowledge

I have now started to work on the AI in earnest. Before going into the particulars of the evaluation function, I would like to take some time to outline the way the AI decision-making process works.

The AI player -”Glee-min”, consists of a set of rules that are deck-specific and matchup-specific. It will use different rules for playing a red burn deck and different rules to play a mono-blue permission deck. It will also play each deck differently against different opponents, so the red burn deck will play one way against a beatdown deck and another way against a control deck.

These rules are encoded in a symbolic manner, as Prolog predicates that define a precondition and a postcondition for each rule. A precondition is a game state: a board position, a step or phase of the game or a value of a game variable (life, mana etc). When the preconditions for a rule hold true, the rule “fires”. A postcondition is an action to be taken when the rule fires. An action is any action that a player can take: play a land, cast a spell, activate an ability and so on, including making choices during combat. Preconditions are expressed as arguments in the head of a rule, while postconditions make up the clauses in the body of the rule.

Since there are different sets of rules for deck strategy and for the matchup strategy, the overall strategy that leads to Gleemin taking a move is decided when the two partial strategies come to agreement about the move to make. If the rules database cannot find a deck rule and a matchup rule that agree on an action, Gleemin will fall back to an alpha-beta minimax algorithm and attempt to brute-force its way to an acceptable board position. This is where the evaluation function comes in.

All of the above can be expressed in predicate logic as a simple and clear implication relation, of the form:


Where A is a deck strategy, B a matchup strategy, C a move to make and D the fall-back alphabeta evaluation.

In other words:

IF deck strategy AND matchup strategy THEN move OR alpha-beta minimax

And in Prolog:

strategy(Context, Move):- 
	deck_strategy(Context, Move),
	matchup_strategy(Context, Move).

strategy(Context, Move):- 
	alpha_beta(Context, Move).

Where “Context” is a list of preconditions that will allow the appropriate rule to be selected for the current game state; and Move is the move chosen by that rule. If the Move chosen by deck_strategy fails to match with the Move decided by matchup_strategy, Prolog will backtrack over deck_strategy and try to find a different rule to satisfy the preconditions defined in Context. If successive backtracking fails to find a match, the second strategy/2 clause will be tried, calling alpha-beta minimax and attempting to find a statistical solution to the problem. If all else fails, Gleemin will pass, or select and take an action at random …aka “mise”.

The decision-making rules that make up the bulk of deck_strategy and matchup_strategy are clauses of a predicate that defines the preconditions and postconditions of each rule. The tactic to choose is declared as a Prolog fact, for example:

land_tactic('Raspberry', play_any_land).

Where “land_tactic” denotes a tactic for playing land; “Raspberry” is the name of the test deck I’m using currently (well… it’s Red with only Vanilla creatures and burn…); and play_any_land is the functor name of the predicate that defines the land tactic that Glee-min should follow when playing Raspberry. Declaring the name of tactics for each action by deck, like this, allows some modularity of strategy. play_any_land simply selects the first land in Glee-min’s hand, but if a more complex rule is needed, this fact can be removed and a different one declared in its place, for example:

land_tactic('Raspberry', play_primary_land).

Where “primary_land” can be the land of the primary colour of the deck. The same scheme is followed for spell_tactic, activated_ability_tactic and so on.

As you can see, the idea is to program the AI just as one would prepare for a real-life tournament, that is, with knowledge of the metagame and a plan for as many matchups -and situations that may arise during those matchups- as possible. This approach has its distinct advantages and disadvantages.

An obvious disadvantage is that, as with real-world tournament preparation, it’s only good while the metagame lasts that you’ve prepared for. In the same way, since the strategy is deck-specific, once the deck changes, the strategy has to change with it. You may even need to adjust the strategy if you just change a single card in the deck, depending on the card and its role in the deck. Sideboarding (the AI will have to be able to sideboard in the second game) will also need extra rules, to accommodate the change of cards (and also to select the cards to be sided in and out). Finally, the expert knowledge that needs to be coded into the rules is not necessarily an easy thing to come by. Fortunately, deckbuilding and metagaming are my strengths as a Magic player (while thinking on my feet is a definite weakness… I’ve not often done well in tournaments, even when I knew exactly what was coming off the top of the opponent’s deck and, trust me, it takes a lot of effort to lose when you get to that point +_+).

On the bright side, the modularity of the tactics scheme is conducive to a rapid-prototyping approach, where some default tactics can be easily programmed (“play the first land you find in hand”), then replaced with more advanced tactics (“play primary land first”) as deck and matchup strategies are refined.

The most important advantage of course is that this symbolic approach has the potential to minimise the complexity that the AI has to deal with. I will go out on a limb and say that most Magic AI today is not on the same level as human players for the simple reason that, after a certain point in the game, the amount of processing needed to find and evaluate each possible permutation, even for the next couple of plies, is just too much (at least for any computer that’s not a liquid-cooled, multi-cored super-machine). As with other games before Magic, I believe that the problem of a human-defeating AI is not going to be solved by brute force alone and some (rather, a lot!) expret knowledge will have to be used. That’s the theory. Now, all I have to do is prove it!

A parser/ interpeter for the Magic:the gathering Game Language

So… about this parser/ interpreter. In its heart there lies a definition of MGL syntax, using Prolog’s Definite Clause Grammar facility. DCGs is basically syntactic sugar, to represent grammar rules. This syntax is expanded into proper Prolog by Prolog’s interpreter (not to be confused with the MGL interpreter discussed here).

Here’s an example. As per the Comprehensive Rules (602.1) activated abilities are written as:

[Cost]: [Effect.] [Activation instructions (if any).]

The DCG representation of this rule is:

activated_ability  --> cost, [:], effect, instructions.
activated_ability  --> cost, [:], effect.

If it helps you, you can read this as “an activated ability is a cost separated by a colon from an effect, optionally followed by activation instructions”. Enclosing the colon in [square brackets] marks it as a terminal symbol. The non terminals, cost, effect and instructions can be expanded further by Prolog, until an appropriate terminal is found.

Here’s a more full example. The spell, Unsummon, has an ability: “Return target creature to its owner’s hand”. In Gleemin’s database of cards, Unsummon’s text is entered as a comma separated list of Edinburgh-syntax Prolog terms, which is to say, upper-case words must be enclosed in ‘ ‘s and the whole thing must be in square brackets- like so:


This is a spell ability, not an activated ability; we define a spell ability like this (%’s begin a line of comments in Prolog):

ability --> spell_ability. % an ability can be a spell ability
spell_ability --> effect(Target).  % a spell ability is a targeted effect

The particular effect of unsummon needs a target to return:

effect(Target) --> return(Target).

Remember that in Prolog, variables begin with uppercase letters. “Target” will need to be instantiated to a valid target. This is not strictly necessary- the same rule could be written as “effect –> return(Target)”, but it makes it clearer to the human reader that we are dealing with a targeted effect. Of course, we need to know where to “return” our chosen Targets. Generally, things are bounced to players’ hands:

return(Target) --> ['Return'], target(Target), [to, its, 'owner''s', hand].

So what is a valid target to return? Unsummon can only target creatures, but “return” is an MGL directive, if you like, that can take as a target any type of permanent (but not players) (ha ha). Here, the rules for return must branch. We are intersted in the “target creature” clause:

target(Target) --> ['target', 'creature'], {creature_type(Target)}.
% A valid target for an effect that targets a creature, must be a creature.

creature_type/1 is defined elsewhere in Gleemin and simply makes sure that the Magic object it’s passed as an argument is really a creature. Note that the call to creature_type/1 is enclosed in curly braces. This marks it as a Prolog call that must be executed as a side-effect of parsing.

This basically means that while we parse our ability – sentence, we can run any Prolog code that we want to. Basically, if we reach the last clause defined above and creature_type(Target) returns true, we know that we have a valid target for Unsummon’s ability. We can run some code to actually return that creature where it came from.

This is a very cool thing to do- to execute MGL as we parse it. However, I opted instead to keep the actual execution code separately, for clarity. I’ll come to that code in a minute. For now, let’s look at the many cool things that we can do with this grammar. For one thing, we can ask the program what is a valid “return” effect, in MGL, by entering this query to the listener (the Prolog interpeter’s command line):

| ?- phrase(return(X), Y).

Which will then reply with:

X = 'Aether Adept' ,
Y = ['Return',target,creature,to,its,'owner''s',hand] ;
X = 'Air Servant' ,
Y = ['Return',target,creature,to,its,'owner''s',hand] ;
X = 'Armored Cancrix' ,
Y = ['Return',target,creature,to,its,'owner''s',hand] ;
X = 'Azure Drake' ,
Y = ['Return',target,creature,to,its,'owner''s',hand]

(Did I mention that I’m working with the creatures from the M11 introductory decks?)

“phrase/2″ is a Prolog predicate that checks whether something is a valid phrase according to our grammar. If its second argument is left uninstantiated, it returns every valid MGL expression that can follow a call to target(X) (it does that in subsequent backtracking, when the user enters “;” in the console). Since X itself is a variable, phrase/2 also returns each valid target for each targeted effect it finds. In short, it generates pairs of targeted effects and their valid targets. If we keep asking it to backtrack, (by entering successive “;”s in the listener) it will eventually return things like:

X = 'Forest' ,
Y = ['Return',target,permanent,to,its,'owner''s',hand] ;

At least it will if we have told it that a valid target for “return(X) can be any permanent type:

target(Permanent) –> ['target', 'permanent'], {permanent_type(Permanent)}.

That would be Boomerang then! A call to “return” can also bounce all of a type of permanent:

return(X) --> ['Return'], all(X), [to, their, 'owner''s', hands].
all(Creatures) -->
          ['all', 'creatures'], {findall(Creature, creature_type(Creature), Creatures) }.

The second clause defines “all creatures”, using again creature_type/1. Another clause may use a call to permanent_type/1 to return all permanents, and of course different type checking is just as simple. We could also add more logic to selectively find the permanents controlled or owned by a player and so on, but I am leaving that kind of more complicated check separately, as I said.

What else can we do with calls to phrase/2? If we bind both its arguments, we can determine whether a target is valid:

| ?- phrase(return('Plains'), ['Return',target,creature,to,its,'owner''s',hand]).
| ?- phrase(return('Air Servant'), ['Return',target,creature,to,its,'owner''s',hand]).

This is, as they say, where the code thickens. We can use such a call to determine whether a target chosen by a player for a spell is correct and, if so, execute the appropriate effect- which is the one bound in the second argument of phrase/2. Here’s my code to do exactly that:

generate_effect(Object, Player):-
		\+ permanent_type(Object), % NOT a permanent-creating spell
		determine_effect(Object, Effect, Target),
		gen_effect(Effect, Target),
		move_to_zone(Player, Object, 'Stack', 'Graveyard').
		% ^ does what it says on the tin! "Player" is the controller of Object
determine_effect(Object, Effect, Target):-
		Object = copy(Name, _Id, State),
		% ^ The internal representation of MGL Objects in Gleemin!
		member(target(Target), State),
		% ^ State is a list of states the Object can be in.
		% target/1 is a state that defines the Object's targets.
		Target = copy(Target_name, _Target_Id, _Target_State),
		% ^ The target is itself an MGL Object.
		card([card_name Name, _, _, text_box Ability, _, _, _, _]),
		% ^ This is the internal representation of M:tG _cards_ in the db.
		% Remember that the Ability is a list of words separated by commas.
		sublist(Effect, Ability),
		% sublist reads in the Abilty text, word-by-word,
		%  then passes each word-list it constructs on to >
		phrase(effect(Target_name), Effect).
		% phrase/2 will fail while sublist is passing it invalid
		%  effect-phrases. Each failure will cause Prolog to backtrack
		%  into sublist again, generating more permutations of the
		%  Ability word-list. When phrase/2 is passed a correct MGL
		%  effect-phrase, it will succeed and bind it to its second
		%  argument. At that point, deteremine_effect will succeed and
		%  return the effect text, bound to Effect. Then...
gen_effect(Effect, Target):-
		Effect = ['Return',target,creature,to,its,'owner''s',hand],
		% ^ This is the word-list returned by phrase/2 in determine_effect!
		Target = copy(Name, Id, _State),
		% ^ The target is an MGL Object...
		owned_by(Target, Owner),
		% ... its owner is bound to Owner...
		move_to_zone(Owner, Target, 'Battlefield', 'Hand').
		% ... and returned to that player's Hand. Sbroinnng!

This is a substantial quantity of code. I hope it doesn’t hurt your eyes too much :) An uppercase word in the head of a rule, signifies a variable that must be matched in the body of the rule. This is how Prolog passes information from the head of a rule to the clauses in its body. So, for example, in the body of gen_effect (er, I need to rename that! Sorry!!!) you can see that “Effect” is bound to the list of words that is Unsummon’s ability. If this pattern-matching fails, gen_effect will fail and Prolog will backtrack, until it can find a clause of gen_effect with an instantiation of Effect that holds true. If we were trying to cast Boomerang, we’d stop at a gen_effect clause starting with:

	gen_effect(Effect, Target):-
		Effect = ['Return',target,permanent,to,its,'owner''s',hand],

This all probably looks like, well, magic, to anyone who hasn’t spent the last, um, er, uh, oh my god, five months of my life, furiously coding in Prolog! I admit it can be a lot to take in, at a glance. But I hope you can get an idea of how the MGL parser/ interpreter works and does its thing.

So we have managed to make our program read MGL directly. Is it really worth it? Well, like I like to say, nothing happens by magic in programming. There’s still lots of coding to do, in order to add more effects and abilities. However, with this code we have already covered most targeted effects, as long as they don’t have any targetting restrictions beyond type. We can keep adding clauses for effect(X), to handle different effects:

	effect(X) --> tap(X).
	effect(X) --> untap(X).
	effect(X) --> destroy(X).
	effect(X) --> regenerate(X).
	effect(X) --> exile(X).

Then define their targets syntax:

	tap(X) --> [tap], target(X).
	tap(X) --> [tap], all(X).

And so on. The target(X) and all(X) rules don’t need any addition (except to add new types of permanents and also players and zones) Of course, each effect will need its own code, in order for there to be something to execute, but already we have a template for that. Unfortunately this is where Prolog’s weaknesses begin to become apparent: there’s a lot of copy/pasting to be done. Prolog is not Object- Oriented, so code reuse is an issue… though of course there’s remedies, but never mind that for now.

The good thing is that most effects are simple state transitions of the Magic Virtual Machine, all of which need to be defined in the main engine anyway. For example, as we have seen, MGL Objects have a State list that represents their, well… state. In Gleemin, to put a permanent in a ‘tapped’ state is to add ‘tapped’ to its State list. This is done by change_state/4, a predicate used by tap_untap to do what it sounds like it would. The same change_state/4 predicate can be used to append ‘destroyed’ to a permanent’s State list. A permanent that is destroyed is moved to the graveyard as a state-based effect (when a player next receives priority). This too, moving Objects from zone to zone, is an essential part of the MVM functionality, handled by calls to move_to_zone/4 (note it’s used in Unsummon’s effect, above). move_to_zone/4 is used to draw cards (moving them from library to hand), cast spells (moving them from hand, to stack, to battlefield or graveyard) and more.

Ideally, every ability of a Magic card should be possible to execute as a call to a generic MVM fundamental state transition predicate, like move_to_zone/4 and change_state/4. This is in keeping with my concept of the Magic Virtual Machine, as an implementation of the Comprehensive Rules. Everything that a card can do, should be defined in the Comp Rules. Ideally.

Of course, in real life things are always much more complicated than the ideal! So a great amount of tweaking should be needed, and of course my engine is still far from complete so there’s a lot of effects that it wouldn’t know how to handle. Then of course we know that Wizards will often publish errata and refine its own definitions of rules, both in the Comp Rules document and on cards themselves. The next time the Comp Rules are updated, the MGL syntax in Gleemin will need to be updated too.

So this is just a start, then. But I think it’s a good start.

I hope you’re still here, after this mammoth post. Well, judging by my previous output, you probably have a couple of months to read this through anyway :)

Until the next update, good luck and have fun :)

Some good news and some bad news.

An update has been long overdue and I apologise for the delay to anyone who may have been reading the blog. My second semester at the university started with some exams and assignment hand-ins, which slowed me down a little but then I had a couple of weeks of essentially free time to work on Gleemin. I decided to make the best of them so I didn’t have much time to update the blog.

I have good news and I have bad news. First, the bad ones (let’s get them out of the way).

I’m a little (ha ha) behind schedule, as in about a month. I should be finishing with the GUI, at this point. Instead I’m still working on the game engine. To be honest, I can’t be bovvered with a GUI, I’m used to doing everything in text and I took some time to work on Gleemin’s textual output, just to make my work easier. Now I’m comfortable with it and I don’t really want to go back, especially as it means I’ll have to take some time off the AI to do it. Unfortunately my supervisor finds the idea awful, so I’ll have to make a GUI. Oh well.

The really bad news is that this means I’m having to cut corners to meet my deadline and the first thing to go is the Swi-Prolog version of Gleemin. In our last episode, I was developing simultaneously on Swi and Win-Prolog. Unfortunately, no two Prologs are exactly identical, so there are always little things to adjust and that takes extra time… which I don’t have. I could work on Swi, but to be honest Win-Prolog’s source-level debugger is better. I’m very embarassed to go proprietary like this but that debugger really unties my hands and speeds me up :(

I am still on board with open-sourcing my code and adjusting it to Swi Prolog, but that will have to wait until after my project’s deadline (28 April; hey, only two months to go) (OMG I’ll NEVER MAKE IT!!! AAAAAH).

That also means no more executables, until then, I’m afraid. My Win-Prolog student license doesn’t allow it. I’ll upload my code here and anyone who really wants to give it a go can download Win-Prolog’s demo from their site, but as usual, Prolog IDEs are not for the faint of heart.

Allright, now for some good news. Well, just the one really. I have a working version of the game engine finished that handles eveyrthing but static and triggered abilities. Creature combat still needs some tweaking and I need to integrate it with the main engine, but it’s done, basically (and incidentally I coded a little automatic damage assignment algorithm, that could be used in the AI, by mistake… because I forgot that the player must be allowed to assign lethal damage as he or she choses, so I left it to the engine. Heh).

The really good part of this is that the engine incorporates the MGL parser, though now I’m calling it an “interpeter” because that’s what it does really. Over at the CCGHQ boards, I explained that I would probably need to do this now rather than later, since the alternative would be to code each card by hand… and that would… yes, slow me down, you ‘ve got it by now… :o )

I will make a new post about the parser and how it works right away, because there’s a few things to talk about and I don’t want to blow this post out of all proportion. I’ll also cross-post to the CCGHQ, since there was some interest in the parser there.