• Advertisement
Sign in to follow this  

What AI for a card game ?

This topic is 4153 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

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]

Share this post


Link to post
Share on other sites
Advertisement
Guest Anonymous Poster
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.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
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.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Didn't realize the 1st one posted

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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!

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
Gorogoro :
Have you got some links to some places where this kind of techniques are used ?
I though about generic algorithm to tune the values that I give to my evaluate function, but I don't know how to go any further

DarkZoulz :
I am confused... How a state machine can tell me which card to play ? I have a given state for the game, for the board ( which card are played, their location, and their current state : HP, and some modifiers ). Sure once I have a robust algorithm to choose the card the AI should play, I can tweak some parameters based on some game state to change the strategy ( like the AI is winning, so get more aggressive, or whatever ), but what I'm really after is the core card chooser algorithm.


stevenmarky :
My current minimax algorithm is with alpha beta pruning ( what other kind of pruning is there ? Pruning branches that are "obviously" bad ones ? ). It uses a depth of 4, with a choice between 12 cards that can be played on 5 locations. All the locations are not free at one time, but I can quickly reach the 200 000 states evaluations with this numbers...
One more thing is that my implementation is in python ( because all my game states transitions, and cards implementation are in python ), so 200 000 takes quite some time.

stevenmarky and Kylotan :
I'm not sure how to use minimax with random :
If I am at one game state, and a card play with a damage of 10 - 15, it will create 6 different states ( for each given damage ) ?
The minimax need some states in its branches, I understand I can use the probabilities to evaluate a given state : eg card A have 25 % attack, and 10-15 Damage makes a 12.5 / 4 global attack value.
But I can't create a new game state, and a new branch from this...the results are really different whether the opponent card is dead or not...

kirkd :
I'm not sure I follow you...
You mean that for 'some' game state, I try all the possibilities a big number of time, and record which one is the better ?
But I have two big issues with such a technique : I have a really important number of possible game states. Even by trying to find some kind of patterns, it still really big.
Second issue, is I don't know how to evaluate whether the result is good, till the result is not 'player One wins', or 'Player Two wins'. If I had such a magic perfect evaluation function, I would just choose the better card. As in a chess game, the result can show how good it was some times after it was played...



Everyone :
Thanks all for your advices...
For the moment, I will try to have a better evaluation function, it seems to be the most important part of it...


Emmanuel

Share this post


Link to post
Share on other sites
Quote:
Original post by Emmanuel77

DarkZoulz :
I am confused... How a state machine can tell me which card to play ? I have a given state for the game, for the board ( which card are played, their location, and their current state : HP, and some modifiers ). Sure once I have a robust algorithm to choose the card the AI should play, I can tweak some parameters based on some game state to change the strategy ( like the AI is winning, so get more aggressive, or whatever ), but what I'm really after is the core card chooser algorithm.

Emmanuel


Well, I was thinking that the "core card chooser" should probably choose a card based on a strategy or personality. What card it plays exactly is really not that relevant. If the AI is aggressive, it plays cards that are marked as aggressive. If you want it to make even more specific card choices you could just make have more states and divid your cards into more specific categories.

Share this post


Link to post
Share on other sites
Genetic algorithms with a greedy-probabilistic selection/deselection of cards during mutation sounds like a method that would produce good combinations, personalized decks and order opponents by skill. Just keep subpopulations for the diversity in which the best combinations are stored and the mutation factors vary greatly. This way, it can explore for "more global" maxima while fine-tuning local maxima. The later kind would seem more natural to the player. If you have many different sort of cards, you could also rank them according to heuristic evaluation and the general level of the decks they participate in. After one or two poor decks with it in,you could for example reduce the probability of it being selected for another deck.

Share this post


Link to post
Share on other sites
Thanks, CWenner...


Actually I already planned to use genetic algorithm to found some deck, to tune the design of my cards, and to tune the evaluation function I can use in order to make it smarter.

However, my trouble is not in the deck creation, but more once I have a deck, to choose the move to make from current hand.

Thanks anyway,


Emmanuel

Share this post


Link to post
Share on other sites
Quote:
Original post by Emmanuel77
stevenmarky and Kylotan :
I'm not sure how to use minimax with random :
If I am at one game state, and a card play with a damage of 10 - 15, it will create 6 different states ( for each given damage ) ?
The minimax need some states in its branches, I understand I can use the probabilities to evaluate a given state : eg card A have 25 % attack, and 10-15 Damage makes a 12.5 / 4 global attack value.
But I can't create a new game state, and a new branch from this...the results are really different whether the opponent card is dead or not...


Minimax is essentially about minimising risk. So to do it properly, the algorithm could assume that an opponent would do 15 damage with such a card, yet the current player would deal 10 damage. However, due to the random aspect, that is overcautions. So if the algorithm was willing to take more risks, it could assume that it will always do 12.5 damage. You could even tune it between these 2 extremes.

However, I don't see why you can't just create the 6 different states each time anyway. 6 is not a large branching factor and many of those will lead to the same response from the opponent anyway. You just have to make sure you're pruning off the unlikely parts of the game tree. You could even generate all the states and then merge the similar ones. In the above example, you might find that damage scores 10-14 result in the target surviving and 15-16 result in it dying, which can be coalesced into one state with the target having taken 'about 12 damage' and another state where the target is dead, with the first fitness score multiplied by 5/7 and the second fitness score multiplied by 2/7 to accommodate the relative probabilities.

Quote:

kirkd :
I'm not sure I follow you...
You mean that for 'some' game state, I try all the possibilities a big number of time, and record which one is the better ?
But I have two big issues with such a technique : I have a really important number of possible game states. Even by trying to find some kind of patterns, it still really big.


That's exactly what minimax and alpha-beta pruning is all about. Chess has exactly the same problem (20 possible moves on turn one, 400 possible by turn 2, probably about 8000 by turn 3, etc).

Quote:
Second issue, is I don't know how to evaluate whether the result is good, till the result is not 'player One wins', or 'Player Two wins'. If I had such a magic perfect evaluation function, I would just choose the better card. As in a chess game, the result can show how good it was some times after it was played...

...

For the moment, I will try to have a better evaluation function, it seems to be the most important part of it...


Definitely. In AI, representation is everything. You have to work out how best to represent your game states, and how to represent the quality of each state.

A good starting point here would be to simply count up the value of everything in play. eg. In Magic: The Gathering, simply counting up the mana cost of cards in play, plus adding a bit extra for the amount of mana producers you have, would yield a decent estimate of how well the game is going. Many simple chess games simply add up all the points values of the pieces on the board, and that is sufficient in many cases. You can then look into adding strategic bonuses for various situations.

Share this post


Link to post
Share on other sites
Quote:

Minimax is essentially about minimising risk. So to do it properly, the algorithm could assume that an opponent would do 15 damage with such a card, yet the current player would deal 10 damage. However, due to the random aspect, that is overcautions. So if the algorithm was willing to take more risks, it could assume that it will always do 12.5 damage. You could even tune it between these 2 extremes.


I didn't think about this that way ( using max Damage). It is interesting. Although it can lead to very incorrect situation ( Imagine a 2-8 soldier against a troll that regenerate 5 pv each round, in real world, the soldier can harm the troll, as it will regenerate all the wounds, and using the max hide this situation ), but I admit this is really a special situation, and I'm not sure it can happens somewhere else than in discussion forums...

Quote:

However, I don't see why you can't just create the 6 different states each time anyway. 6 is not a large branching factor and many of those will lead to the same response from the opponent anyway. You just have to make sure you're pruning off the unlikely parts of the game tree. You could even generate all the states and then merge the similar ones. In the above example, you might find that damage scores 10-14 result in the target surviving and 15-16 result in it dying, which can be coalesced into one state with the target having taken 'about 12 damage' and another state where the target is dead, with the first fitness score multiplied by 5/7 and the second fitness score multiplied by 2/7 to accommodate the relative probabilities.


Generating all the states is definitively too much, as I'm already limited by the number of nodes I generate / inspect, but I was thinking, as you suggest as generating 'range' of damage with probabilities. Really interesting, I'm not sure I will have time to make it concrete, but good thing to think at...

Quote:

That's exactly what minimax and alpha-beta pruning is all about. Chess has exactly the same problem (20 possible moves on turn one, 400 possible by turn 2, probably about 8000 by turn 3, etc).


Wep, I know that, but I think Kird was talking about an offline pre - process, to store all possible states ( he were speaking of millions of iteration to construct the database ).

Last thing, the evaluation function :
I already have a simple evaluation that uses the strength of all cards involved.
but it is not good enougth.
So I was thinking about something more complex.
My problem here is I would like this function not to have knowledge of cards implementation / special power, in order to be able to add cards without changing the evaluation function.
One way to deal with this is to have the cards implement the evaluate interface, that would make them evaluate themselves...


Anyway, thanks for your post, it was definitively interesting !!


Emmanuel

Share this post


Link to post
Share on other sites

However, I don't see why you can't just create the 6 different states each time anyway. 6 is not a large branching factor and many of those will lead to the same response from the opponent anyway. You just have to make sure you're pruning off the unlikely parts of the game tree. You could even generate all the states and then merge the similar ones. In the above example, you might find that damage scores 10-14 result in the target surviving and 15-16 result in it dying, which can be coalesced into one state with the target having taken 'about 12 damage' and another state where the target is dead, with the first fitness score multiplied by 5/7 and the second fitness score multiplied by 2/7 to accommodate the relative probabilities.
[/QUOTE]
Alpha-Beta merely rests on the assumption that all players will choose the best move according to some depth and underlying functions. This does eliminate risk but only such that agents can influence. Taking the best/worst outcomes for uncertan variabales is quite different! What Alpha-beta needs to make in such a situation is as you say, branch and calculate the expected outcome (i.e. the average value of outcomes) after potentially further search. For example, reaching point A at depth 3, taking each of the two outcomes B and C, searching an additional two steps and returning the alpha-beta value for B and C and setting A = P(B) * B + P(C) * C. The extra branching of 6 is generally horrible, at least of you can do some sort of approximations.

General:
Something I wouldn't recommend when searching is simulation unless you either plan on giving it several thousand runs or perform it a few number of times. Since alpha-beta will pick the best value out there, several simulations with a high variance aren't going to give a rational result.
If you for example make pick n random numbers in (0,1), you're going to find the expected maximum of these to be
alpha * Int(p=0..1, p * p^n dp)
alpha^-1 = Int(p=0..1, p^n dp) = 1/(n+1)
=>
Int(p=0..1, p^(n+1) dp) * (n+1) = (n+1)/(n+2)
I.e. avg.
0.5, 0.67, 0.75, 0.8, 0.83, ...
An exception may occur in the case where you can generate random variables ones and reuse these in simulations. An example of this would be the cards current at top in the deck. A hundred or so sets could be generated in advance and iterated during simulation for a much smaller effect due to the variance (a proper modeln would be 50 a ply). Actually testing how much it affects is a recommendation though.

For integer ranges, you could add the random vars to calculate the mean or probabilities to be below or above some value (which generally is what you'd use in utility functions and successor functions - whether a creature dies/fully generates, or if you reach the end, how many points he would have last at average). If the first attack does 3-4 and the second 1-3, then the final damage will be between 4 and 7 but you can also calculate the probabilities for each outcomes as
4 + X. Where 0 <= x <= 3. The weights would be (1,2,2,1) - 1 way to get (3 and 1) or (4 and 3). 2 ways to get the other. If you have some set of weights <a_i> and <b_i>, you could easily construct a new set <c_i> by for the weight of getting a total of c, summing over the probabilities for the first outcome to be i and multiplying by the probability of the second to be c - i. If the outcome should be 3 for example, you go over 0, 1, 2 and 3 for the first outcome, pairwise multiplying with the probability for the second to be 3,2,1,0. Formally, if n_a and n_b is the max values (i.e. 1 less than the number of weights)
<c_i: sum(j={max{0,1-n_b}..min{i,n_a}, a_j * b_(i-j))>.
total = sum c_i
n_c = n_a + n_b
The mean and prob for min/max is easy.
P(c >= k) = sum(i=k..n_c, c_i) / total

Such an approach would allow to take into account probabilities of the more critical actions (creatures dying) by generaling to the possible outcomes: die or don't die and leaving the rest to utility for example (i.e. a branch of two if n_c >= hp - the user would prob. chose a different action after knowing it dies).

The standard approach to card games with incomplete information is generally put on utility functions with sofisticated game theory where probability theory is used essentially. Only a few plies are taken into account. One could perhaps complement the utility function with a generated one (difference wize) with a lesser weight to accomodate for all the generalizations done in the model.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
I'm making a Magic-like game too, and right now, I'm stucked with the abilities and effects of the cards.

Did you think about that ? If you do, please tell me the solution you've found.

The abilities and effects can modify the rules of the game and that's something new for me.

Share this post


Link to post
Share on other sites
You could easily set various variables to reflect what sort of rules currently are in effect. If you for example which to change so that you draw two cards instead of one, then have a variable named CardDrawCount and change it. These rulesets belongs to the state of the game, they can change. Therefor, you construct states with variables and in the successor function, you merely make your alternations. The successor function is a function which takes the current state and returns the resulting state. Seeing how you in your search deals with states, the 'rule' changes will not effect non-descedant states.

Share this post


Link to post
Share on other sites
I have a GetNextState method that gives the next state from current state.

This function is called from the real game, AND for the AI, so the AI search from real states.

Each card has basically 4 functions : Engage, Attack, Defend, Die, that have basic behaviour, and can be overidden for specific behaviour.

And each action can call a modifier the card has subscribed to. This is an action another card have on current card.

Say I have a 'protector card' played, that creates a shield that absorb 1 point of damage for every other card.
All cards have a defense modifier, that will decrement the damage value given to the defense method.
When the 'protector card' die, the modifier is removed on other cards.

Hope it helps,

Emmanuel

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
(i'm the dude who ask about the effects and rules, ... maybe next time I sign up...)

Well, I alredy thought about making the game like a state machine (using a class for changing the actual state of the game, but there are card effects which change the rules of the game, not only those internal variables.

For example, there's a card saying something like: "While this card is on the game, your opponent can't win the game and you can't lose the game", so even if you lose all your lifes, still you can't lose, and that is a modification of a game rule. (when a player's life reach 0, that player lose).

Another example: there's acard saying something like: "You can play 2 lands on your turn", changing the rule "a player can only play 1 in his/her turn".

And there's a lot of cards changing the rules ...


So, how can I manage those effects? (they change the rules, not the regular variables)

Share this post


Link to post
Share on other sites
Quote:

Well, I alredy thought about making the game like a state machine (using a class for changing the actual state of the game, but there are card effects which change the rules of the game, not only those internal variables.

For example, there's a card saying something like: "While this card is on the game, your opponent can't win the game and you can't lose the game", so even if you lose all your lifes, still you can't lose, and that is a modification of a game rule. (when a player's life reach 0, that player lose).

Another example: there's acard saying something like: "You can play 2 lands on your turn", changing the rule "a player can only play 1 in his/her turn".

And there's a lot of cards changing the rules ...


So, how can I manage those effects? (they change the rules, not the regular variables)

The 'rules' in a game are nothing more than a relation between the current state and successor/goal states. If you may play two cards at once, that means your actions of that state includes playing two cards. If the opponent cannot win while some card is in effect, it merely ensures that the goal state function returns false til then. All of these are effects local merely to the current state of the game. If the actions can alter them, they belong to the state, there is nothing else which considers the temporal relationships of the game. The alterable 'rules' are just direct or indirect internal variables (indirect in the sense of the existence of a card but no explicit variable for example).

A state machine is something else than what we're talking about. We're speaking of states in search, an autonoma is similar but it's functionalities wouldn't be of any use here unless you wish to design the AI (meaning the addition of quite specific behaviour which relies much on you, rather than emerging from advanced means of evaluation).

Share this post


Link to post
Share on other sites
Damnit. Why is there no prompt that I didn't entter my username on these forums? I just entered only my password and lost the whole post. Grrr....


Anyway, I'll summarise what I was going to write:

Initially, it's only worth looking ahead to the end of the AI's current turn, i.e
1) AI spellcasting phase
2) AI attack phase
3) Opponent defence phase
4) end of turn

At this level of lookahead you can easily afford to generate just about every possibility, without really worrying about pruning.

Your first goal should be to build an accurate board evaluation algorithm to give a score for the 'end of turn' phase. You could identify as many factors as you can which may affect this (number of life points remaining, creatures in play, etc) and assign each an importance variable. Tweaking these variables thus gives different AI behaviour. You could then run a Genetic Algorithm to get optimum values. If the resulting AI is still really stupid, you need to either improve your GA starting point/evolution procedures, or else add more useful factors to your board evaluation metric.

Once the AI is acting 'smart' for it's current position, then you know you have a good board evaluation metric. After this you start looking forward multiple turns and developing your AI further with pruning techniques.

Share this post


Link to post
Share on other sites
The most important thing is the evaluation of the current game state, i.e. assigning a score to the position on the table. This should take into account the tactical value of cards still in hand, if any (i.e. a one-turn creature upgrade spell); creature strength versus players' life (any enemy creature that does 1 damage is only a small negative score if you're on 20 life, or if you have creatures to defend against it, but a huge negative if you're on 1 life with no defenders); the value of creatures'/permanent enchantments' special abilities.

Once you have that, you can simply calculate the score on the table for all possible moves of playing/not playing the cards in your hand, and pick the best. For a 7 card hand that's only 128 even if you don't assume independence of which cards are good to play.

As for attacks, I'd use a similar system: calculate the estimated value of the attack (just sum(probability*value) for each outcome). Potential attacks with multiple creatures on both sides make things more difficult, as there are a lot of choices to make, and it might be necessary to remember the best (i.e. highest estimated value, even if too low to attack with) 4 or so configurations. Remember that for any one creature there are typically five outcomes: the attack is not blocked and the other player loses life (+ve); the attack is blocked and the blocking creature dies (+ve); the attack is blocked and neither creature dies (usually neutral, though damage-causing abilities on either side could change that); the attack is blocked and both creatures die (variable value); the attack is blocked and the attacking creature dies (-ve).

The use or otherwise of abilities can be treated similarly.

Both parts (playing cards and attacking/spellcasting) will produce lots of tunable parameters, which should probably be the target of a GA to produce decent players.

Part of the reason games like Magic are fun is because they require thinking to play B-) ... so they are naturally hard to write a good AI for.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement