Friday, December 14, 2007

AI – Curve my mana

I was thinking about how to make the AI a little better. I thought if the computer’s land was curved out, the computer would seem a little smarter. The computer’s opening hand is all spells and the computer will draw a land for the next 5 turns. This maximizes the possibility of the computer playing a timely 1 or 2 mana spell. After a few more turns the computer draws 2 more lands.

The rest of the computer’s land is artificially moved to the bottom of the computer’s deck, so the computer will always top-deck something useful. The long game will favor the computer, but the AI is still very beatable since it just plays a random spell. Currently the computer cannot evaluate the board position or anything complicated like that.

I could have gone a step further and guaranteed that the computer would be able to play a spell for the first 6 turns of the game. I might do this later. I had a hard time sorting and alternating the computer’s land so that it would look like this: Mountain, Plains, Mountain, Plains, etc… That way the computer will always be able to play a double costed card like WW as early as turn 3 and always on turn 4.

Other ways to make the computer stronger would be to have him draw 2 cards per turn. I have rested doing this since it would break the illusion that the computer was playing by the rules, but I might test it out to see if it really helps the computer.


Nastyboy said...

Ola, where can I start. first of all AI with just randomly playing effects is not an AI. If you want some sort of AI you could/should use a recursion (or even better genetic algorithems) . So the program would look what is best for him in the future.

Let's say that you have a Royal Assassin and opponent has tapped Erg raiders with paralyze on it. It is better for you to let Erg raiders to live, and you attack with royal assassin instead of killing Erg Raiders. So with recursion you can build the "decision" tree and then select the best choice. The problem is the depth of your recursion. If you look just one step ahead then it is not much of a logic, but still one big step ahead. To be effective it should be more steps.
For our example, our recursion would build 3 steps.
1. Kill the Erg raiders
2. Don't kill Erg raiders, don't attack
3 Don't kill Erg raiders and attack

Then you just estimate what is the best for you. But what is the best for you?? To have bigger difference in life, or maybe to have more creature cards? That's the question. The answer is again in recursion. If you can see one step ahead more than the opponent then you can win...

Second option is the genetic algorithm. What can you do here. Well, you need more computer power. Let's say that you randomly generate new decks... 100000 of them. Then you just randomly play effect, creatures, spells....against each others many time). Because you have so many decks, some of them would be bad, but some of them would be good. Then you can randomly shuffles the good one.. and sometimes you can make a small mutation (just randomly switch one card)
With time you would get better and better decks....(with just randomly playing effects,spells...) Decks that are the best have a better synergy. For more decks just repeat the pattern.

In the next step just combine both algorithms. So the best decks and recursion. And voila :D

Forge said...

Hi, I know a "real AI" wouldn't just play a random card, but it works pretty well. If you didn't know that the AI did that, you probably wouldn't guess.

A good AI would have the computer do an action (like playing a card) and then that action would be given a score, depending on how effective that action was. But this is too complicated for me right now.

Currently the AI card is built into each card separately and whether the computer plays Wrath of God or not depends on a few lines of code. (The computer plays Wrath if he is under 9 life, meaning that he is desparate, or if he will destroy many of his opponents creatures.)

Yannick said...

So, does this mean that you implemented the changes that you were talking about in a previous article a few weeks ago? (Copy/Paste for the win, lol)

Anyway, designing an AI (I'm still very interested about that matter!) for Magic is extremely complicated, since the rules are far from simple, and there are so many different cards, abilities and situations.

There's one important things, I think : the computer must know what the cards do. It must understand the effect of each card (spells and abilities). Otherwise, it won't be able to use them efficiently. I don't know if that's the case in MTGForge? Does the program only check if there are valid targets for a spell before casting it, or does it check if casting the spell is worth it?

For example, a simple card : Immolation (Enchanted creature gets +2/-2). This card may be useful to boost your own creatures, but it is also often used to kill creatures with toughness <= 2. How would MTGForge handle this card? I don't know if you already implemented it or not. I'm guessing that in the AI part of the card, you would check if there's a killable creature on your opponent's side, and if there's a creature with toughness >2 on your side, you can use Immolation to make it bigger (although it may not always be wise). That would be a decent AI, but it could be much better.

It brings my second point : planning. In order to be more challenging, the computer must plan actions before doing them. As you said, in MTGForge, the AI wil for example never use a Giant Growth after attacking, for example. If I take the Immolation example again, a decent AI can kill a weak creature with an Immolation, whereas a good AI can combine it with another spell or source of damage to kill a strong creature like Serra Angel.

There's another thing that (sometimes) needs to be thought about : the kind of deck the AI plays. Spells won't be used in the same way, depending on the deck you play. For example, while most of the times, a player would cast Ancestral Recall on himself (card advantage, obviously), it may be cast on the opponent for some decks (decks killing with Black Vise/Storm Seeker, library depletion decks, etc)

As for the genetic algorithm Nastyboy talks about, I'm not sure it would be good for a magic game. Genetic algorithms are complicated to design (how are the genes represented, how will the operations work - mutation and "crossing" [Sorry, I don't know the english word for that]), and if it's not designed perfectly, the results won't be good. I don't see how we could apply such an algorithm to a Magic game?

I hope we can discuss more on this subject, because it's very interesting, and I wanna read different opinions on this subject.

Take care!