New Magic program: Gleemin

[Ye Goblyn Queenne]

Arch, hi. Here's the full source:

http://www.goblinopera.com/Gleemin/Gleemin_tests_01-03-11.tar

It will run in Win-Prolog if you compile main.pl and enter "main." at the listener. Please remember it's a working version that I'm still hacking at like mad (but I reckon you've seen source code before). Do be gentle while running it and keep a flamethrower handy for the bugs (think Starship Troopers).

To your Prolog questions.

Variables that start with an underscore are "don't-care" variables, as long as each is only encountered once in the body of a rule. Otherwise, Prolog will try to match them. A single underscore is truly don't-care, so two or more won't be matched. As you say, I'm using the named ones as reminders of what each unused field is.

The card structure is actually a Prolog list. You could see it as

Code: Select all

card(Characteristics)

or as

Code: Select all

card([Name, Cost, Type, Text, P, T, Loyalty, State])

In fact, you can query it like that and you'd get the same information. What looks like keys ("mana_cost", "text_box" etc) are in fact operators that I have defined for the project. They don't do anything, just make the list more readable. So, if you ask:

Code: Select all

card([card_name 'Maritime Guard', _, _, _, P, T, _, _]).

You'll get the answer:

Code: Select all

P = power [1] ,
T = toughness [3]

If you ask:

Code: Select all

card([card_name 'Maritime Guard', _, _, _, power P, toughness T, _, _]).

You'll get:

Code: Select all

P = [1] ,
T = [3]

(Enclose P and T in [ ]'s to return their naked values).

The traditional way to do key-value pairs in prolog is to have lists of the form:

Code: Select all

map([Key_1 - Value_1, Key_2 - Value_2... Key_n - Value_n]).

I'm using some of those too You can define your own operator to use as a key-value separator, if the Prolog implementation allows it.

Yes, unfortunately if you want to modify the data structure then you have to modify everything that uses it. Prolog is not object oriented. Basically, it's kind of pattern-based, so when you change one pattern you have to change everything that's trying to match it. You can of course define OOP-like hierarchical relationships, for which there's some code floating freely on the internet and L-space, but I wanted to get stuck in with the Magic right away. I'll probably have to do some more elaborate organisation at a later point.

The "state" field is there from the beginning of the project, when I was trying to figure out how to do things. It's kind of useless at this point but I left it in just in case. I might use it for cards with a comes-int-play tapped effect etc. There's lots of garbage in my code that I just can't bother fixing right now. I'm no software engineer, see )

[Ye Goblyn Queenne]

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 (apparently long posts are acceptable ):

- 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 (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!)

- The MGL (that's Magic Game Language) 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).
  
  
• 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:
  
  

  Code: Select all

  | ?- 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:
  
  

  Code: Select all

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

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

  Code: Select all

  "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:
  
  

  Code: Select all

  "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. Oh, I'll upload the code in a few days, but as usual it needs the Win-Prolog IDE to run it...

[MageKing17]

- Oracle text is parsed directly and interpreted as a programming language, so that's how spells/ abilities are implemented.

I would love to see your work on this.

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.

Ah, not quite. Spells can have static abilities too, you know. "CARDNAME can't be countered" comes to mind.

[Ye Goblyn Queenne]

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.

Ah, not quite. Spells can have static abilities too, you know. "CARDNAME can't be countered" comes to mind.

Hm. You're quite right! I just checked the Comprehensive Rules again. Instants and Sorceries can also have activated or triggered abilities, so letting the source define the type of the ability (as I was planning to do) is not a good idea.

I'll have to define spell or static types by the form of the ability: imperative directive for spell, declarative statement for static. Meh. That's gonna be a hassle...

- Oracle text is parsed directly and interpreted as a programming language, so that's how spells/ abilities are implemented.

I would love to see your work on this.

I just uploaded the full code, here:

http://www.goblinopera.com/Gleemin/Gleemin_01-05-11.7z

Like I said, if you want to run it you need the Win-Prolog IDE, from here: http://www.lpa.co.uk/dow_tri.htm

The file you want is: mgl_interpreter.pl

Most definitions of effects and lower level terms (eg, targets, objects, players etc) have a block of comments with an example of how to test them in the Prolog command line. They help me remember how they're supposed to be invoked so they'll help you figure out how they work. Like I said, there's only the four effects I mention above that work (I added destroy on the 29th, I think...).

The first part of the file is the grammar. If you want the part that does the actual interpretation, ctrl+f for:

generate_effect/2

That should take you to the header of the predicate that generates effects as they resolve from the Stack. The other two interpreter predicates are determine_effect/3 and gen_effect/2. The latter is the one that distinguishes between effects and does all the hard work.

Note that the way gen_effect/2 is implemented is a bit crude- it disambiguates between effects using their whole syntax, while my newest version uses the general forms of effects as they are in the grammar section (so instead of "Destroy target creature" it calls destroy(X,Y) ). OK, that's probably too much info at this point. I'll let you have fun with it.

Oh, I also put the section fom my report that's about the parser in two pdf files, here:

http://www.goblinopera.com/Gleemin/The% ... Parser.pdf

The report is crap unfortunately, I must apologise. I didn't sleep much in the last week of the project...

I'm happy to explain anything that needs explaining, btw. Also, let me know if you have any problem with the Win-Prolog trial.

[Ye Goblyn Queenne]

Btw, MageKing, I just realised that you have a parser also.

You guys have been busy too, lately

[MageKing17]

Yes, but ours is very simplistic; I just stuck a bunch of if-else branches together, occasionally using regexps, and every effect is more-or-less hardcoded. It speeds up work by filling in common abilities automatically, but a true parser, especially one incorporated into the program itself, would be much better.

[Ye Goblyn Queenne]

Yes, but ours is very simplistic; I just stuck a bunch of if-else branches together, occasionally using regexps, and every effect is more-or-less hardcoded. It speeds up work by filling in common abilities automatically, but a true parser, especially one incorporated into the program itself, would be much better.

Well, from what I saw of your program, it generates code so it's at the same level of abstraction as mine. You read in Oracle text, then populate some classes (other containers?) with attributes. Then you call the new code at run time?

So, basically, you're implemeting a compiler while I'm implementing an interpreter. You get to the end of your parse-tree branch, find some code hanging there and make copies of it, then fire it at run-time. I find some code and fire it immediately, 'cause I'm parsing at run-time. If you want to do the same thing you probably need to pass some functions as parameters- I think Python can do that no?

In any case, it's not necessary to do it my way and I think it's probably faster if you do it your way ('cause compiled is generally faster than interpreted). Or maybe I got the way your editor works all wrong (I lost the url to it again...).

[MageKing17]

Well, Python code is compiled... to bytecode. There's not a huge speed increase to pre-generate the code as opposed to run-time parsing, especially since the program is turn-based.

[Ye Goblyn Queenne]

Well, Python code is compiled... to bytecode. There's not a huge speed increase to pre-generate the code as opposed to run-time parsing, especially since the program is turn-based.

What I meant to say is that if you have a program that reads Oracle text and generates code, then that's a parser. Once you generate a parse tree, you can create new code or execute some on the spot, it's still the same thing.

Anyway, the thing is I thought nobody else had written a parser, because I basically didn't search the forums very carefully after November 2010 or so, I was so engrossed in my own project. Now, I took some time to do just that and I realise you have a parser too and also MagicWars (from what I can tell from this: http://www.slightlymagic.net/forum/viewtopic.php?f=23&t=2575&p=46366&hilit=parse#p36125). In my project report I presented my parser as unique, basically, which is not true after all. If the examiners find out, I'll blame you for not calling what your online editor does "parsing"

Btw, what I say about you guys being busy- I also meant ubeefx's use of a Monte Carlo -based AI in Magarena, which I also found out about a week before I delivered my project, so I just had time to put it in my report.

I should 've organised my work better and properly referenced that of others, is what I'm saying...

Ah, in case anyone wondered, I praised the community of Magic developers to high heaven and I guess I bashed proprietary programs just a bit. (But it's fair, given that the official games have official support and all, but the community projects still have more cards, better AI, parsers, gorgeous graphics and so on so forth... and all for free).

[lad1337]

hi all
i have read the thread now two times, i am just that excited about the work being done.
i always had the dream of such a rule save mtg client, i started work on one a few years back.

seeing magarena and Incantus really sets my hopes high.

now i recently had the urge to tackle this game / client and i found gleemin and the blog about it
since i (used to) know prolog and it capabilities it is a great project to work with.
i see that some updates are posted after the last commit to the gleemin ... is it out of date on github ?
i already took the liberty of converting to UTF-8 files in my fork

i have a few questions about gleemin, magarena and Incantus:
- is still work done on gleemin ?
- are there plans to integrate network capabilities / multiplayer to magarena ? (just looking at the program now)
- is Incantus still in development ? last commit was on 2011-04-01
- what are your thought of cockatrice ?

now i am totally willing to help develop on these matters
my first idea was to integrate the logic / AI parser of gleemin into cockatrice but seeing magarena makes me wonder what to do
i am also all for cross platform (i am on a mac)

i just played just two turns with magarena and i am amazed ! i will look at it a little more incl the codebase

[Huggybaby]

hi all
i have read the thread now two times, i am just that excited about the work being done.
i always had the dream of such a rule save mtg client, i started work on one a few years back.

Welcome! I share your dream, and that's why this forum is constructed the way it is.
I can answer a couple of your questions:

- are there plans to integrate network capabilities / multiplayer to magarena ?

No.

- is Incantus still in development ? last commit was on 2011-04-01

Mageking is still tinkering with it. Thousands of cards are waiting to be converted/programmed, and it's easy to do.

- what are your thought of cockatrice ?

I haven't looked at it in a while. The lack of posts here about it makes it look undeveloped but development is still very active at their own forum: http://forum.cockatrice.de/index.php

now i am totally willing to help develop on these matters

Fantastic, you're in the right place.

[MageKing17]

- is Incantus still in development ? last commit was on 2011-04-01

Mageking is still tinkering with it. Thousands of cards are waiting to be converted/programmed, and it's easy to do.

The bitbucket is just where Incantus (the user) puts his commits, and he hasn't worked on it since... well, since 2011-04-01; all of my work is done solely on my computer and released in this thread, with the last update being this May. In fact, I'll probably put out a new version soon, to fix a few bugs I found in v0.7.1c and add a few new features. Also, as you can see from this page, I've coded all but 9 cards from Magic 2013 (and those 9 cards can't be added without major engine changes).