Hi all, I'm working on a little Magic-like card game ( although I don't really know Magic ). But I'm not sure how to handle the AI. Is there any known algorithm for this kind of games ? I tried an alpha beta search, but it limits my design to have absolutly no random : the attack / defense / damage values have to be fixed, and I can't have a card deck ( but that's less important for me, I didn't wanted one anyway ). The second issue I have with an alpha beta is that performance is depending on the number of card I can play at one time, and the combinaisons can be quickly really high, so performance quickly degrades... What other kind of technics can apply to this kind of games ? Should I make a long term hi level strategy layer, and a low level layer following the strategy and deciding which card to use ? Any help is welcome, Thanks, Emmanuel [Edited by - Emmanuel77 on August 10, 2006 5:58:55 PM]

What about personality? In card games some opponents are aggressive and favor playing attack cards. Others favor playing defense cards and become aggressive as a reaction. A way to do this would be to weigh each card's offensive/defensive values and let the AI factor them in with their initial setting for preference and allow the preference to shift based on the agression of the player.

You can vary the AI by an aggression factor. A more aggressive factor favors cards that attack the opponent, while a more passive factor favors cards that set up defenses against current or future attacks. The opponent could be stubborn (initial agression stays the same through the game) or reactionary (aggression shifts a little each time a player's card is played. The reaction could be towards the agression of the player of against it. This is a simple matter of weighing the offensive and defensive qualities of each card separately and favoring them depending on the passive/aggressive state of the computer opponent.

Didn't realize the 1st one posted

Thanks APs for your answers, but I'm looking for algorithms that could help find a decent card to play for the AI.

Once I have the base algorithm, I think it would be easy to tweak it to make different kind of opponents.
Actually it is already what I have with my alpha-beta algorithm.
I can have different evaluation function for different AIs, to have some players favorising some ways to play.

But my alpha beta is a little too slow, and I can't put any random in it.

I though about dealing with the random part by using average values in place of real values, but it just won't work (tm) :
if I have a creature card with 10D6 attack, but with a huge amount of hit points against a creature with 11D6 defense, but with only a few hit points, a algorithm using average values will always find the attack to fail, although it should hit from time to time...


So I was wondering if there was an academic way of dealing with this.


thanks for your help anyway,

Emmanuel

Quote: Original post by Emmanuel77
Thanks APs for your answers, but I'm looking for algorithms that could help find a decent card to play for the AI.

Once I have the base algorithm, I think it would be easy to tweak it to make different kind of opponents.
Actually it is already what I have with my alpha-beta algorithm.
I can have different evaluation function for different AIs, to have some players favorising some ways to play.

But my alpha beta is a little too slow, and I can't put any random in it.

I though about dealing with the random part by using average values in place of real values, but it just won't work (tm) :
if I have a creature card with 10D6 attack, but with a huge amount of hit points against a creature with 11D6 defense, but with only a few hit points, a algorithm using average values will always find the attack to fail, although it should hit from time to time...


So I was wondering if there was an academic way of dealing with this.


thanks for your help anyway,

Emmanuel

I've seen aproches for that kind of problems using Neural Nets or genetic algorithms or both!

Quote: Original post by Emmanuel77
I though about dealing with the random part by using average values in place of real values, but it just won't work (tm) :
if I have a creature card with 10D6 attack, but with a huge amount of hit points against a creature with 11D6 defense, but with only a few hit points, a algorithm using average values will always find the attack to fail, although it should hit from time to time...

That's just a statistics or probability problem. Each range has a probability curve and from that you can work out the percentage chance of the attack succeeding. That percentage can be used to modify the perceived value of the attack. eg. A 25% chance of a win = 1/4 as much benefit from this move as if it was a guaranteed win.

I think I understand your problem - you can have randomness in an alpha-beta search.
For each possible outcome you need to multiply the result of your evaluation function by the probability of that event happening. So events that have tiny chances of happening are taken least into account.



Also I thought that Alpha-Beta is a good choice for a card-game if you are doing pruning.
What is the depth of your tree and how many cards do you have?

[Edited by - stevenmarky on August 11, 2006 8:37:49 AM]

How about a finite state machine type AI?

I believe it would work great for a cardgame. You could create different agents that would resemble different personalities or strategies.

I've thought about this one myself quite a bit. The biggest hurdle I face is that I don't know the rules of the game well enough, but I may have an idea that would be useful.

The finite state machine suggested above is a possibility, but I think you need a probabilistic state machine such that transitions between states are not deterministic. You need to introduce the random component, as you mentioned above, but at the same time, you want to bias the result such that you maximize your probability of winning.

The question is how to determine the transition probabilities. The way I thought to approach it is to set up a random simulation where you have various scenarios of which card is played. You then follow the standard rules of play, which include the random dice throw, and record the results. After running this numerous times (probably millions of iterations), you'll start to collect sets of probabilities, and those can then be related to which cards were played. These could then be used to construct your state machine.

Your really monitoring a stochastic process and trying to come up with proper rules.

I hope that makes sense.

-Kirk