Archived

This topic is now archived and is closed to further replies.

Suggestion on AI Algorithm in game like Magic The Gathering

This topic is 6058 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I''m currently handling a game project and I''m new and inexperienced.Can anyone has any suggestion on suitable AI algorithm to be used in a game like Magic The Gathering card game?

Share this post


Link to post
Share on other sites
Well, if you are new and inexperienced, I suggest you read stuff on classic card games first.
The main problem I see for you, is that unlike classical card games where the rules are clearly set and the card limited to a 52 card set, Magic is extendible.
Thank God the rules themselves are clearer now, and the stack system works wonders from a programmer''s point of view.

But you still have the card-rules.
And for this my friend, you gonna need something different.
The way I see it, you need an AI that can understand what the rules mean, and then use that to its advantage. I always forget the buzzword, but you''ll need something better than simple search algorithms...

well, at least that''s my semi informed opinion.

maybe someone else would like to give an opinion, if you don''t know what Magic the Gathering is about, please ask

youpla :-P

Share this post


Link to post
Share on other sites
Well first of all you need to understand how AI work so I suggest you read about it, well as much as you can. Then I suggest you program samller programs like youpla said you have to start small.

First you could amke a program that handles 3 cards. Siccor bag and stone game sort of. easy to do and easy to get the AI tounderstand what everycard means.

well that is my point of this view!

greetings Illgar

Greetings Illgar

Share this post


Link to post
Share on other sites
I''ll analyze more and come out an appropriate search algorithm 1st. Think I''ll build my AI on top of certain limitations like limit the type of cards and rules 1st.
Thank you both of you for the invaluable advise =)
BTW, I still welcome any good opinion.

Share this post


Link to post
Share on other sites
Well, I dont know how familiar you are with Magic, but there is one suggestion :
Start small

For instance, take the approach they took when they did Portal. Not all the tricks that Magic allows, but the core principles : creatures, lands, spells. A stack system that works, and a limited set of cards that try to minimize the head wrecking situations.
Maybe this would actually be doable.

My remark was mainly directed at the fact that Magic is by nature extendible, which means you have to have some way of allowing that. And much more importantly, your AI has to have a way to accomodate this.

Even with a limited set of cards, you still have the problems of the AI being able to *understand* the rules of each card...
In chess, the computer doesnt have to understand as much so the task is "simpler", but with Magic and the hundreds of cards available .... I think you get the idea.

Please don''t take this as a "give up, you never gonna make it" post. Quite the opposite, really, as my Masters is partly about this kind of stuff
But if you want to do Magic, I strongly suggest you read a manual on AI so that you get a good grasp of the different fields and techniques. The point not being to understand them, but rather to allow you to get a better idea of the different options you can choose from to tackle the problem.

Good luck anyway

youpla :-P

---------------------------------------
"-Where did you get that guy ?!
-He is French !" - Godzilla

Share this post


Link to post
Share on other sites
Well, I think it is important to know your own rules before you can program the AI

I am a dedicated Magic player... Once you have played the game enough times, you can often see a patern in the way players play it.

Basicly, a Magic player does the following in a turn: try to lay down a land, then observe his/her cards. Observe the creatures the enemy has, and your own. Check whom has more lives. Then make a choice:

When the enemy has a lot more creatures, it is useless for you to lay down one at your side, unless it is really strong. When you are equal in creatures, you can get an advantage by summoning one.

When you are ahead, you may want to increase your number, or save your mana for other things.

Etc, etc :p

Now, before you do anything, you take a look at your spells. Do you have any good combinations? Do you have a card/cards that can kill the enemy instantly? Or can you kill a few creatures? Again, check the advantage you are creating. When it is big, do it. When it is insignificant, well, dont

After checking all of this, make a move... And hope your enemy does not kill you...

Share this post


Link to post
Share on other sites
Mmmmmh :/
I dont want to sound snappy, but I think this is a bit simplistic (although it might be exactly what cklim needs )

For instance, in my 5 colors "domain" deck, my goal is to get five different lands out as fast as possible. But the catch is that my deck has a LOT of spells whose effectiveness is tremendously increased by the number of *basic land types* in play. And since they are really cheap, most of the time I don''t need a lot of lands in play. Furthermore, the fact that I play 5 colors means that I have only a few lands of each, which means if I get my three blue lands out, and they get destroyed, I am in big trouble...

Also you must not forget that the creatures are not there just to attack. Most of the time you want the creatures that will fit your style of play.
My friend who plays white has tons of "dont tap to attack" creatures, so that he can also defend. VERY annoying, and it also means that he doesnt need as many creatures.

One thing I learnt in my years of play (and it works for a lot of other games), is that you have to stick to your plans.
If you don''t, you are reacting, which means the opponent is having an advantage.
For instance, another of my friends has a Red/Black deck. Direct damage, annoying creatures. But he plays often against the White deck guy. What happens is that rather than making his Red/Black deck faster so that he can take out the other guy before he is settled, he tried to modify his deck to make it Anti-White, making it slower, hence less effective.

Ah ... time to go. I will try to post a bit more about this later.

youpla :-P



Sancte Isidore ora pro nobis !

Share this post


Link to post
Share on other sites
OK, I''m kinda stuck right now and looking for some suggestions
My questions are :
1 ) In game like Magic, should the AI be well informed on what''s the player''s cards on hand and the incoming card in future?
2 ) Do a rule-based + learning algorithm seems to be a good solution in game like Magic?

Share this post


Link to post
Share on other sites
I would not try a learning algorithm for *playing* Magic. Simply because it would take very long for it to learn the game... It would be easier to catch the rules in your program...

However, as ahw said, the way someone plays depends on his deck. Perhaps it is possible to create an AI that can analize it''s own deck, and decide on a playing strategy? It might take some time for it to understand it''s deck, but you could save the data.

In the game itself, once it has a strategy, you can play by simple rules whom are modified by the information it has about it''s deck...

Does this make sense?

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
make a different AI for every deck the computer will use. Then maybe use fuzzy logic to let it evaluate the game state and generate a random response. If it wins the game have it strengthen the chance of it doing what it did before when under similar states.

Share this post


Link to post
Share on other sites
quote:
Original post by cklim78

OK, I''m kinda stuck right now and looking for some suggestions
My questions are :
1 ) In game like Magic, should the AI be well informed on what''s the player''s cards on hand and the incoming card in future?

2 ) Do a rule-based + learning algorithm seems to be a good solution in game like Magic?


2)
Again, I''ll assume that you have a good knowledge of the game itself. I think it REALLY helps if you do.
Why ? Because the best method for figuring out what to do is generally to think about what *you* are actually doing when you play.
Now think about it. When you play, what do you generally ask your opponent before you play ? The colors they play. And eventually if they are nice what "style" of deck. But generally, knowing the colors gives you a fair idea of the kinda guy you are against.
Red ? Direct damage and land destruction.
Green ? Mana plentyful to summon PHat creatures.
Blue ? Counterspells, and flying creatures.
White ? Defense and counter-attack, White weenies.
Black ? Antiplay and suffering.
you get the idea.
Blue-black is usually an annoying deck with denial spells (counterspell and "discard cards") and the creatures to go with, usually flying.
Green-Red is fast and furious (a horde of little creatures and direct damage)

You get the picture.

The way I see it, you hav to study the game to see different areas that can be used to win. Think about it, how do you win ? By killing your opponent, or him running out of cards.
How do you do that ?
Damage : Direct damage, creatures.
Running out of cards is a bit more straightforward.
To damage your opponent, you have to choose diverse methods. Do you want to go for pure direct damage, do you want to use massive creatures, do you prefer a horde of little ones, or other methods.
Rather than rely on your own strength, you could just deny your opponent play, by destroying his lands, by countering him constantly, by making him lose cards, etc, etc

See, there are plenty of ways to reach your goal, and these different ways are all different styles of play that you could give your AI.
My idea is that you should define some sort of personality to your AIs. That conditions the strategy that you will chose to play, which conditions the type of cards you will need.
This works backwards, of course. Looking at one''s cards, one will quickly catch an idea of the strategy the opponent will use.

How can you code that ???
I would use a rule-based approach.
something like
"killing your opponent is good"
"direct damage spells hurt your opponent"
"spells costs mana"
"lands produce mana"
"Artifact A produces 3 mana, costs 1"

And use good old logic to let the computer figure out that
"In order to win, I need to hurt the player, hence I need to cast spells, hence I need mana, hence I need land."
"If I have one land already out, casting Artifact A is better than playing another land, as it gives me more mana"

Does that make any sense to you ?

1) Now to answer your first question, if the computer knows the hand of the player and his deck... this kill the use of cards like Urza Glasses (your opponent shows his hands), or other nice spells that let people play with their hand up. As well, it kills the side effect of some spells that let you search your opponent library that they let you look at the opponent library ("Hey! I thought you didnt play with that card!")
So it seems quite obvious that it''s a Bad Idea (tm) to let the computer cheat.
Use the above ideas to figure out what the opponent has.
He is playing blue ? He probably has some counterspell up his sleeve. He''s green, I betcha he has some Fog waiting for my horde to attack. Etc

youpla :-P

Hope I am of some help



Sancte Isidore ora pro nobis !

Share this post


Link to post
Share on other sites
Wow, thx for all the reply guys, especially youpla, thx for all the help. I get the idea of letting AI knows all the card a player had will spoil the fun. Hmm, seems too early to say I fully understand the whole picture on the rule based approach, gonna take me some time to come out idea and clearer picture to implement them. But I really appreciate all your help and idea.
I''ll still welcome any invaluable opinion as it definetely will help my project. Thx again guys

Share this post


Link to post
Share on other sites
I was thinking about this thread and thought I might post another idea I had for your cklim.

Rather than aim very high, why not start with something equally interesting but maybe more feasible : a deck designer.
Basically you would give the system criteria for your deck, and it would give you a list of cards that match those criteria, and eventually why they are there ?
Imagine this : "I want a 60 cards deck, Green Red, fast, Kavu based". You could choose criteria such as color, extensions allowed (for tournaments decks), eventually styles of play (Denial decks, Burn decks, Weenie hordes, etc)

This would still imply a good amount of work, but it cut the part of playing the game. I think designing a deck is 80 % of the job in MAgic. Playing is jsut a question of getting the cards you want at the good time, and that''s what good design of deck do, get you the cards you need, when you need them.

So why not focus on that part. I am sure it would teach you a lot. And it''s very much a "classic" AI problem : designing an expert system. Now go and get a good book like that one. It''s the basics, it goesn''t go into games, but it will give you good basis for knowing where to go next.

Good luck

youpla :-P

PS: "youpla" is not my name, it''s just a stupid thing I say like other people say "Regards"



Sancte Isidore ora pro nobis !

Share this post


Link to post
Share on other sites