Using the Forge AI and Machine Learning to build better deck

[shlarin]

I see that in Forge, you can have 2 AI players play each other. I've tried testing the effectiveness of various decks in forge by having the AI play against another AI using 2 different ideas.

So I got an ambitious plan to design some really powerful decks by using data mining and machine learning. This would involve writing a separate data mining program. At a higher level, this program would do the following:

- Download the top decks from Tappedout and TCGPlayer.
- Randomly vary the cards in the decks to try to come up with even better decks.
- Use the Forge AI and game engine to simulate games between Deck X and Deck Y for all possible pairs of decks you've generated.
- A genetic algorithm would be ideal since what we're basically doing is trying to find the best decks through simulating a survival of the fittest process.
- After crunching through, it'll give you some proposed decks that have had the most wins in those simulated wins.

Does this sound feasible or would this require a ridiculous amount of computing power to pursue?

[rikimbo]

It sounds like a very ambitious and exciting project. You should definitely try it out.

I'm not sure about the feasibility in terms of compute power, but can control your solution space by limiting the card pool. You can start by working in block constructed, which might be small enough so that you can converge to solutions quickly, even if evaluating "Deck X vs Deck Y" pairings is costly.

If you go with the genetic algorithm approach, I'd be very interested to read about your crossover and mutation operations. For crossover especially, if you mate two decks based in completely different colours, the child deck could have a broken mana base. (Granted, a deck like that would be weeded out pretty quickly by the selection step.) You could do something like match chromosomes according to only non-land cards, and then generate a new mana base for the child.

A similar thing could apply to the mutation operation. Do you allow a mutation to a card that is outside of the deck's colours? Do you allow it but only at a low probability?

I think the solutions a project like this will converge to will be decks featuring cards/strategies that work especially well against AI opponents. That might mean they're not optimal when it comes to facing human opponents, but the results would be very fun to analyze, for sure.

EDIT: Actually I'm also interested in how you'd do your selection in the genetic algorithm. You can't easily define a fitness function that you can evaluate for any one deck by itself, so I guess that's why you would evaluate all possible pairs to determine one. That will grow to be very large. You might have to develop a heuristic to evaluate the performance of a deck based on only a set amount of opponents, and determine the fittest individuals that way -- sort of like a tournament, I suppose.

Anyway, TLDR I'm very interested in the whole thing. Definitely keep posting more about it as you get underway.

[Marek14]

I think there's no need to evaluate all possible pairs. Imagine the decks like animals on the steppe. You can start with, say, 1000 decks, which will be all the same. Each individual deck can fight with any other deck, but only randomly (animals in real world don't really fight ALL other animals). Let's say we'll have 10 fights started by each deck (the total number of fights the deck can participate in might be larger if other decks select is as an opponent). Population could be kept constant, which would make each generation take the same time regardless on card pool. After each generation, throw out decks whose win rate is in bottom 50% and replicate (sexually or nonsexually) the winners.

[friarsol]

Forge does have a way to simulate matches (without the UI), but I don't think it's available in the releases. I'm not sure what would be needed to make it available in the releases, but right now if you have a compiling project, you can send a few parameters and it'll run matches for you and output the results. I'd imagine you could easily wrap that a bit with however many decks you want to play against each other, and pipe the output to a file of each match. Then after all the matches are done, you can go back through and tabulate all of the results.