9

Examples of the games I have in mind are Magic: the Gathering and Pokemon Netbattle (the latter is not a traditional card game, but it does involve teambuilding so should be similar).

AI can beat the best humans at a variety of games now (most recently Go and Starcraft 2), so they are undoubtedly good players, but can they build decks? For example, can one feed an AI all the Magic: the Gathering cards currently available in Standard as well as the deckbuilding rules (in Magic: the Gathering, that would be "not more than 4 copies of a card per deck unless it's a basic land", "not less than 60 cards", etc) and have it tell you what the best decks are?

It sounds like a formidably hard endeavour, especially since once your list is known your opponent can "counterbuild" by adding counters vs. your specific deck, so I'm guessing there is no such AI. If that's indeed the case, I would be interested in any attempts at creating such an AI.

11
  • 1
    I would look at Kyle hills video on if it is possible to play a perfect game of magic to see why AI hasn't gone in this directions. Especially with a game like magic you can build a deck to deal with one type of deck but would lose to another type so it is not that there is always one best decks.
    – Styxsksu
    Dec 1, 2021 at 13:53
  • 2
    This seems a challenge AI would be suited for, likely much simpler than Starcraft 2 for example.
    – NPSF3000
    Dec 1, 2021 at 22:02
  • @Styxsksu sometimes there is a "best deck", though.
    – Allure
    Dec 2, 2021 at 0:38
  • @NPSF3000 Magic is Turing-complete. I doubt very much that it's simpler than Starcraft (in the general case).
    – wizzwizz4
    Dec 2, 2021 at 15:01
  • 2
    There are certainly ways an AI could assist. You can create a tool that assigns cards a relative potency (within reason) and use that to help with card selection and/or pruning. And, you can run some basic stats level and even perform a Monte Carlo analysis to maximize your gameplay consistency. (MTG Deck Analyzer does a little of each of these). But, there's somewhat of a rock-paper-scissors mechanism in MTG. I suspect an AI would find many local maxima and almost never find a clear global maximum.
    – svidgen
    Dec 2, 2021 at 15:58

3 Answers 3

12

Don Goodman-Wilson made a program to build decks given a pool of cards. (I guess you could make the pool 60 copies of each card legal for the format).

From his post on Hackernoon:

So I started building just such a tool. Read along to find out how it works, how you can start using it, and better yet, how you can help make it awesome.

In this article, I want to outline at a high level how I approached this challenge, how my approach works, what went well, and what didn’t. If you just want to jump directly to the code, or a deep-dive into the technical nitty-gritty for yourself, you can dig deeper on GitHub.

In particular, I want to talk about an approach to deck building using a technique called genetic algorithms or GAs. GAs allow us to literally evolve good decks using artificial selection. Ooooooooh! Yes, it is as exciting as it sounds!

The article goes on to talk about the approach he used. And it links to a GitHub with the source.

As the comments note, this may not be a high quality attempt nor one that handles any card set set you throw at it, but it is an attempt, as per the original post's request:

I would be interested in any attempts at creating such an AI.

3
  • 16
    His program requires you to manually annotate how many creatures, artifacts, enchantments, instants, sorceries, and lands you wand in your deck, and most importantly requires you to manually annotate how synergistic each card is with certain archetypes. This is functionally most of the work that goes into constructing a deck in the first place. His program has no mechanism to actually read the text on each card other than mana cost and power/toughness, so would not work at all to make a deck from a new set, for example.
    – Brady Gilg
    Dec 1, 2021 at 17:51
  • 6
    @BradyGilg Extracting the text from cards is an easy problem (Arena has it in a nice JSON format). The rest of your criticisms are very valid though. Dec 2, 2021 at 11:40
  • 5
    @PhilipKendall Reading card text is easy, interpreting it for the purposes of deck building is not.
    – Brady Gilg
    Dec 2, 2021 at 15:36
7

First, just so you know where I’m coming from, I’m a professional programmer, and I’ve studied AI, but I don’t work with AI professionally, so there are limits to my expertise. I defer to anyone who is an expert in AI, but I think currently my expertise is most applicable to this question. That said,

There is a major constraint on the way we currently build AI, that makes its application to deck-building games intractable, at least on our current hardware.

Our general approach to AI—“machine learning”—involves the AI trying some random approach, evaluating it for effectiveness, and then doing so over, and over, and over, refining that randomness towards something better and better.

It is absolutely crucial, in this scheme, to be able to tell how good a given random try was. To learn, the AI needs to know that attempt 1354235 was better, or worse, than attempt 1354236. In a large sense, this is all machine learning requires, which certainly makes it very powerful, but it is a hard requirement. We need to be able to assign a number to how good a try something was, because what the AI is really doing is maximizing that number (or minimizing, whatever).

To my knowledge, no deck-building game out there enables any easy calculation of the general quality of a given deck. What do human “optimizers” of the game (e.g. pros) do? They create a deck and play it a lot, leveraging their considerable experience. Not just to see how it does in a variety of situations—but also to learn how to play it, that is, figure out the optimal strategy for playing the cards the deck makes available.

So here, for each deck, the AI wouldn’t just be able to obtain a number for how good the deck is—they’d have to have some sub-AI that’s training with that deck, learning how to optimize play with that deck. Since machine learning requires thousands or millions of iterations, having each deck iteration itself require thousands of strategy iterations just to learn how good the deck is, is going to be a huge problem. Our computers simply aren’t fast enough to get through all of that in a reasonable amount of time.

And there isn’t really any way around this. If you just program some game-playing ability into the AI, so it doesn’t iterate its strategy, it just tries to play, you aren’t really learning about the potential of each deck the AI comes up with. You’re just learning how well that deck happens to match the strategy you pre-programmed, which is probably not going to be terribly interesting or useful.

The way humans get around this is through heuristics—which roughly means something like “rule of thumb.” We have ideas about what is or isn’t a good idea, we can evaluate at least some options on paper as just not worth considering. Our brains are very heavily optimized for this task, and we do it constantly, considering only a tiny subset of the possibilities before us, based on our experience and understanding, to keep everything manageable. But the power of AI is to avoid these human heuristics, try out things that we never would have considered. We don’t want to influence or narrow the potential solution space—the whole point of this exercise is to explore it more thoroughly than a human can do.

We’re not there yet. When we have working deck-playing AIs for one of these games, where the AI can take a random deck and optimize playing that deck, then we can think about optimizing the deck-building part of things. But ultimately, the only way to know if you’ve built a good deck is to play it, so start there.

16
  • " Since machine learning requires thousands or millions of iterations, having each deck iteration itself require thousands of strategy iterations just to learn how good the deck is, is going to be a huge problem" Why is this a problem different than say Chess or Starcraft? There are more possible permutations than any computer could ever calculate. AI is just a method of exploring the problem space and coming up with a reasonable answer using, essentially, statistics.
    – NPSF3000
    Dec 2, 2021 at 16:30
  • 2
    @NPSF3000 The difference is very simple: chess and Starcraft require that number of iterations to play. But we’re talking about building the deck first—and in order to test how well we built the deck, we need to then do that many iterations for each deck. So if we can manage n iterations (which are enough for chess and have been making progress with Starcraft), we now need n ² iterations. Since n was “what we can manage,” we can’t manage n ².
    – KRyan
    Dec 2, 2021 at 17:33
  • 3
    It's also that twice - not only is your deck not a constant, but neither is your opponent's deck. Playing chess is like saying "given these two fixed decks, optimise your playstyle with one against the other". It's not analogous to "make a good deck".
    – Rob Grant
    Dec 2, 2021 at 20:48
  • 1
    @NPSF3000 True; I’d had chess and go in mind with that comment. StarCraft is definitely intense for this approach.
    – KRyan
    Dec 3, 2021 at 3:49
  • 1
    @CainGoldhardt Magic is Turing complete, but that won’t be a problem here. We do not need to solve, in the rigorous, mathematical sense, the optimization problem, which is honestly something that almost never can be solved, often even if the system isn’t Turing complete. That’s why we turn to machine learning in the first place. The distinction here is that we are not attempting to determine the optimum, only to optimize, that is, through successive iterations improve our play in some meaningful sense. And that can be done. (A timeout to turn undecidable cases into ties may help.)
    – KRyan
    Dec 4, 2021 at 5:46
5

You will need a good playing-algorithm.

The most straightforward way is by running a tournament of sampled decks:

  1. Sample decks (randomly / heuristically / using some data)
  2. Play many games using identical playing-algorithm. This way the only difference are the decks.
  3. Keep the winner(s).

bypass: sample strong decks from a DB (for example: hearthstone top decks).

8
  • 2
    This sounds like a "here's how it could be done" rather than an answer to the question (examples or examples of attempts). Dec 1, 2021 at 12:35
  • 1
    ... decks don't play each other. People play decks. Dec 1, 2021 at 14:49
  • 1
    @ArcanistLupus The "many times" constraint somewhat implies that the decks will be played by a computer rather than a human. I doubt that will be too much of a problem, given how strong MCTS algorithms have become at card games like Magic.
    – Stef
    Dec 1, 2021 at 16:28
  • 1
    @Stef is there Magic-playing AI that can match the best players in the world? If so, can you point me to results?
    – Allure
    Dec 2, 2021 at 2:12
  • 1
    @Allure I haven't been following that close; maybe you can find interesting research papers on google scholar: scholar.google.com/?q=magic the gathering ai or on DBLP: dblp.uni-trier.de/search?q=magic+the+gathering
    – Stef
    Dec 2, 2021 at 13:04

You must log in to answer this question.

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