Monday, April 28, 2008

Blue Moon – Human vs AI

I’m interested in trading card games (TCG) that you can play on the computer. I wish somewhere on the Internet there was a complete list, but I haven’t been able to locate it. So I’ll mention any TCG games that I find.

There is a computer implementation of the card game Blue Moon. In the computer version you play against the AI and you each use one of the 8 pre-built decks. Unfortunately the computer version doesn’t let you let you construct your own deck, but each deck has different strengths and weaknesses.

The Blue Moon program also has all of the beautiful card art included and is even endorsed by Blue Moon’s creator. While learning a new set of rules can be irritating and confusing, Blue Moon at least has an “assist” feature that tells you what you should do, so you are never stuck. You may also want to check out author's homepage which includes the source code, its in C or C++ I think.

Blue Moon Download
1. PDF Rules
2. GTK Library – a graphic library so it can run on Windows
3. Blue Moon for Windows


Alex said...

Hi again. I didnt know if you read replies on old posts so i'm just posting right here even if it has no meaning with your post's subject...
So anyways, i just wanted to know your take on a somewhat "goal" AI. There could a global goal predefined by the deck played by the AI and then a general AI under it (with 3 main AI still underneath it, one for game beginning, one for the main game and the last AI for either when the CPU is winning or losing).

I've been thinking of coding my own magic AI for a while and, although your AI is one of the best around for mtg, i don't believe it's optimal. I've read a lot of your previous posts and i understand why you took this road... but then again, the main reason i think your AI is still somewhat weak is because it doesn't know *what* it is playing. He's playing like if you just give a very structured deck to someone who doesn't have a clue of what cards are inside, what strategies to use, what are the combos, etc, etc. So he ends up playing opportunisticaly (does that word even exists?) or even totaly random.

Forge said...

"Although your AI is one of the best around for mtg, i don't believe it's optimal."

I'll be the first to admit it that MTG Forge's AI is passable, lol, the AI was only meant to approximiate a real player.

The first step in developing a Magic AI is to just focus on combat. Forget about all those sorceries, instants, and activated abilities, just focus on simple creature combat. Magic combat is complicated, which makes the game interesting, but very hard to solve. If the AI could figure out when he should trade creatures and when he shouldn't, that would be a big improvement.

The problem with AI's is that they are not very pluggable. How can I write a program so that other people can write the AI for it? And even if I could do that, how can I minimize the work to write an AI?

In version 2.0 I plan to tailor the AI to specific decks so it has an idea what it is doing.

Another problem with many AI methods like min-max and genetic algorithms is that they require a evaluation function, usually a number. Trying to even approximate the evaluation function is hard. I did this once with my program, and the computer would do really weird things, then I would look at the evaluation function and see the problem. But the evaluation function doesn't work well with combat, so in essense they aren't usable.

Not that I have much of a reputation, but I doubt a Magic AI that only used either min-max or genetic algorithms would be very good. Obviously the hard part is disproving my hypothesis.

And finally, the more work that I put into the AI the less cards I program, ha.

Alex said...

Well, the way i see it, there is always a list of patterns in MTG in general (and in all games, even chess). Let's say, for example, one of the most common pattern in most of the decks around, is to get the more mana possible in the least amount of turns. So it's clear that in the early stages of the game, AI should put a big priority towards mana-generating cards (playing llanowar elves or overgrowth) instead of anything else in the first few turns (until he gets around 3-5 playable mana or something). In the case of a discard deck which relies on hypnotic specter, the pattern would be different: get hypnotic out as soon as possible! He should be playing anything to get his hypnotic by turn 2, if possible. Since Hypnotic costs 1BB, the optimal play would be: dark ritual turn 1 -> hypnotic.
So, in these two examples, you have two different goals for the early stage of the game, for two totally different kind of decks. The user who created these deck would just have to check patterns appropriate for the deck, something like "Prioritize mana-generation" or "Get in play card X" as priorities. This, of course, if the AI is in a strong position and doesn't need to counter the player's strategy (in which case, AI will turn into a defensive/counter style of play).
Basically, the big huge task in this, is to find all these paterns and code them in the AI so he never has to rely on randomness...

Alex said...

Evaluating the board is another story, but still would work well with set priorities depending on deck, i think. Take the previous example, the discard deck. Hypnotic would have a higher priority value than abyssimal specter or probably any other card in play. What i'm trying to say is that evaluating the board is extremely hard when you don't know what is important to your strategy or not. By giving the AI some priorities, you also suggest a value for important cards in the deck. For pluggability, each card in the deck should be given a number, or flagged in some way to help the AI evaluate the board.

By the way, i really like MtgForge and by no way i want to criticize your AI, i simply wanted to discuss possibilities with you ;)

telengard said...

An different example of MtG AI that uses Minimax w/ AB pruning is deckbot.


Nanocore said...

Another twist of the same concept of priorities is assigning a state of offense or defense to a pattern or card. I have gone through several thought processes for an MTG AI since the Micropose version came out. I DO see a possibility of defining a visual interface to building up the AI rules for cards. Also, I was working on a way to incorporate a sort of debugger for the game, in which it would save state and allow you to go back several cards, tweak the rules on the card and then proceed forward to allow it to be tested. The AI I was building used a rules engine (Jess) to house the rules. The intent was to put a wizards like construct around selecting rules for cards and then storing the card/rules association in a database. So, the code had to implement the code to support the individual rules, and the game engine would execute them at the appropriate time. The AI player would then interrogate the cards rules to determine if it was appropriate to play, based upon the parameters of the AI player. With this sort of pattern of being able to interrogate the card, the AI player would "see" what is in play and what is in the hand and determine the best course of action. Very similar to the pattern of how a real person plays. In this way, you can have different kinds of AI players; one who would be very defensive, or one could be highly aggressive.

Unfortunately, I didn't get this implemented as real life came in and took my time away. Not to mention, I can't do graphics, so the look of my implementation shot down my enthusiasm.

alex said...

Interresting. What language did you code yours? Would you mind if i had a look at it, i'm intrigued at how you pulled this off..? Honnestly, it looks very similar the what i had in mind.

Nanocore said...

I was doing it in Java as I wanted to be able to play on Linux. I did not get far enough on the integration of the rules engine for there to be anything worth sharing. I got to a point to exercise it, which required "the game" so I spent a huge amount of wasted time trying get a gui going that I got frustrated and gave up. So, out of a lot of thinking and sample code, I don't have anything to show for it. This was also at a time that when ever I would bring up writing an AI to MTG to some forum, that I continually got shot down with "that is impossible, stop working on it, it will never work..." Rather then constructive input. Again, frustration won out. However, I kept looking for someone else to come up with a similar project, and if I had time I could jump into their project. If not to contribute coding, maybe with ideas...

Forge said...

Thanks for everyone's comments. AI is an infinitely deep subject.

Anonymous said...

If you know about Keldon's Blue Moon AI, then I assume you've already seen this wonderful page:

But if you hadn't yet, it's never too late to check it out!