7
\$\begingroup\$

How would one approach developing an AI for a trading card game(e.g. Magic The Gathering, YuGiOh, etc.)?

I'm not sure where to even begin. How would "Easy", "Normal", and "Hard" AI difficulties differ under the hood?

\$\endgroup\$
0

4 Answers 4

5
\$\begingroup\$

This is my experience from implementing a MTG AI.

If the AI is not considered from the start, adding it later can be challenging.

Your engine needs a way to copy the game state. It also needs a way to to quickly undo a move, so search tree can be generated efficiently.

Every AI thread should operate on its own copy of the game.

When computer makes a move it simulates possible outcomes of the game by simulating the effects of every possible move.

The basic algorithm is:

Create a list of valid moves (spells, abilities, pass ...). Execute each move to generate a new state then create a new list of valid moves. Repeat this until the game ends, or until you reach a certain depth. Remember you simulate the game for both players.

This process will generate a tree. Each path on the tree represents a valid sequence of actions in the game. Assign a score to each leaf node of this tree. This score should be an indicator which player has a greater chance of winning the game. Using minimax algorithm propagate this score to the root of the tree.

Every move from the original list now has a score, pick the best move.

Unfortunately MTG is rather complicated and the basic algorithm will not perform very well...

Things to improve:

  • Mana abilities (e.g land tapping) need to be treated differently.
  • Do not declare all possible combinations of attackers and blockers, use some 'quick combat' heuristics.
  • Spells which require targets will kill the performance, use heuristics to pick only 'good targets'. (Each card which requires targets, should have a ranking algorithm)
  • Assigning a timing rules to each card to limit when AI can consider playing it.
  • If a card has X, it should know how to calculate a good X value and only try this when it is played.
  • If a card can be activated repeatedly, use an algorithm to calculate how many times and do this as one move.
  • Force only one option when playing spells that have multiple, based on the game state.

Here is a card implementation which uses some heuristics from above:

public class LightningBolt : CardTemplateSource
{
    public override IEnumerable<CardTemplate> GetCards()
    {
      yield return Card
        .Named("Lightning Bolt")
        .ManaCost("{R}")
        .Type("Instant")
        .Text("Lightning Bolt deals 3 damage to target creature or player.")
        .Cast(p =>
          {
            p.Effect = () => new DealDamageToTargets(3);
            p.TargetSelector.AddEffect(trg => trg.Is.CreatureOrPlayer().On.Battlefield());
            p.TargetingRule(new EffectDealDamage(3));
            p.TimingRule(new TargetRemovalTimingRule(removalTag: EffectTag.DealDamage));
          });
    }
}
\$\endgroup\$
6
  • \$\begingroup\$ It would be a more elegant solution when the AI would not need to cheat by knowing which cards the player can play and which cards will be drawn in the future. \$\endgroup\$
    – Philipp
    Aug 27, 2014 at 22:46
  • 1
    \$\begingroup\$ @Philipp. I forgot to mention this. The AI does not cheat. This is done by not including the 'hidden' spells in the list of valid moves. Cards in opponent hand are hidden by default, as are cards in both libraries. \$\endgroup\$ Aug 28, 2014 at 7:44
  • \$\begingroup\$ The idea of including "good target" and similar hint logic inside the cards has an interesting side benefit: you can use this in tutorial modes to help highlight useful moves for the player, or select sensible defaults (particularly if the tutorial decks are tailored to cards with robustly hintable behaviour). By running an instance of the AI on the human turn, you can weigh the benefits of multiple cards this way and suggest a set of actions that work well together. \$\endgroup\$
    – DMGregory
    Oct 27, 2014 at 21:21
  • \$\begingroup\$ Dang, a MTG AI in C# that's clean, well organized and open source? This answer is a goldmine among answers on gamedev.se =) \$\endgroup\$
    – Ken
    Mar 13, 2015 at 20:50
  • \$\begingroup\$ wow, I haven't thought of that; The automaton can operate in its own world and play out a bunch of its' possible plays, and decide which one generates the most value relative to the automaton's subjective value system. Instead of having every automaton make predictably perfect plays based on knowledge of opponents' deck, statistical analysis of every possible scenario in the metagame based on popularity, it can just play out its' own strategy with varying degrees of consideration about the opponent or the metagame, depending on the personality you want for the automaton. \$\endgroup\$
    – Dmytro
    Jul 5, 2019 at 20:21
4
\$\begingroup\$

1) A Value Heuristic. You need a heuristic that the AI can evaluate how "good" a particular game state is. For example, in MTG, a very simple heuristic could assign 2 points for every card you have in play and 1 point for each point of life the enemy has, so one of the AI's goals would be, all other things being equal, to play as many cards as possible, but it would also be willing to sacrafice any card to do 2 or more damage to the enemy. Note that this heuristic probably depends on the deck in play -- for Mill decks, for example, you'd need to incorporate the opponent's deck size as a primary point source.

2) Move Lookahead. The game rules describe all the legal moves available to a player, including drawing/discarding/placing/activating a card. Each move can be rated according to the heuristic you came up with in step 1. However, this is only reading one move. More successful strategies should consider the opponent's subsequent move, and the AI's move after that, and so on. Typically you use a minimax strategy.

  • One step ahead: for each of your moves, determine the value of the resulting game state and choose the one with the highest points.
  • Two steps ahead. for each of your moves and for each of your opponent's responses, determine the highest point value, assuming your opponent picks the optimal response to your first move.
  • Three steps ahead. foreach [your move, opponent move, your move again], pick the best game state, again, making sure the opponent move is optimal for the opponent.

3) Further Optimization Naive move search increases exponentially the further ahead you search.. Using a technique similar to alpha/beta pruning, you don't evaluate paths that are really bad. If you can figure out a game state is strictly dominated by another game state, you do not have to continue looking down that branch of the move tree. Also, while the heuristic gives a general "sense of direction", the outcome of specific card combinations might not be apparent. Especially when using themed decks, you could keep a list of potent combos, especially gambits that take multiple steps before the heuristic could recognize the value of the combo.

\$\endgroup\$
2
  • \$\begingroup\$ Move lookahead is of questionable feasibility in a setting where there are simply too many moves available at any given stage and so the gametree explodes quickly. Minimaxing makes sense in chess, for instance, but it makes next to none in a game like Go, and I imagine it'd be even worse in TCGs. I think a planning-based approach would be better. \$\endgroup\$ Aug 9, 2012 at 22:17
  • \$\begingroup\$ The minmax algorithm doesn't work well in a game where the AI doesn't know what moves the other player can make. In a TCG, this is usually not the case because the AI doesn't see the players hand and doesn't know which cards the player and itself will draw. Unless, of course, you let the AI cheat. \$\endgroup\$
    – Philipp
    Aug 27, 2014 at 22:41
3
\$\begingroup\$

Magic: The Gathering Duels of the Planeswalkers has AI that simulates possible future game states. Different AI difficulties are allowed varying lengths of time to plan advance turns. Additionally, the decks of easier AI opponents are sorted so that rarer cards are more likely to appear near the bottom of the deck.

Here is a detailed article with pictures(!):

http://www.wizards.com/Magic/Magazine/Article.aspx?x=mtg/daily/feature/44

\$\endgroup\$
0
1
\$\begingroup\$

Well, you have to do several things:

  1. The AI needs to know rules for the game.
  2. Next the AI has to know a strategy, as these card games generally have multiple sections and/or possible types of cards. example: magic, attack, monsters, abilities, weapons and so on...
  3. For the actual difficulty; the AI should just be a better strategist, so a possible looking ahead algorithm, say an easy AI might plan ahead for an attack, but not a trap, whereas a hard AI shall plan for more types of possibilities, and multiple depths of thinking.
  4. The AI should be able to combine techniques, as well as know general strategy for an effective game.

Thats the basics of it. Of course it may vary with how the game is itself.

\$\endgroup\$
4
  • \$\begingroup\$ How does any of that translate into code? Especially No.1 \$\endgroup\$
    – Steve
    Aug 9, 2012 at 20:10
  • \$\begingroup\$ Hmm, if @Steve is new to programming, he might require a less abstract answer with more examples. I'll try to write it up later, but I've got work to do now. \$\endgroup\$
    – jcora
    Aug 9, 2012 at 20:23
  • \$\begingroup\$ @Steve, what language do you plan to do this in? \$\endgroup\$
    – Rivasa
    Aug 10, 2012 at 2:25
  • 1
    \$\begingroup\$ @TheEliteNoob There was an attempted edit by an anonymous user to the question saying "@TheEliteNoob Actionscript 3.0", so I assume that was answering this question, I guess Steve lost his info? I don't know. \$\endgroup\$
    – House
    Aug 10, 2012 at 15:07

Not the answer you're looking for? Browse other questions tagged .