Genetic algorithm to find the strongest AI decks

[austinio7116]

The main issue with that youtube video as far as I can see is that each generation would take such a long time to run (especially given it is rendering the UI as it goes) that to get meaningful results in the search space he is working in would take years if not longer. I tried to constrain the search space using the Latent Dirichlet Allocation based deck generation tools trained on human generated deck data to help increase the quality of the population and reduce the number of iterations required to get interesting results. Running the algorithm for longer would be interesting, but for my purposes the decks generated were "good enough". I hope to find some time to rerun this again soon once I have updated the LDA deck generation tools with a more mature post-M19 dataset.

[Arcanist]

The main issue with that youtube video as far as I can see is that each generation would take such a long time to run (especially given it is rendering the UI as it goes) that to get meaningful results in the search space he is working in would take years if not longer. I tried to constrain the search space using the Latent Dirichlet Allocation based deck generation tools trained on human generated deck data to help increase the quality of the population and reduce the number of iterations required to get interesting results. Running the algorithm for longer would be interesting, but for my purposes the decks generated were "good enough". I hope to find some time to rerun this again soon once I have updated the LDA deck generation tools with a more mature post-M19 dataset.

Aaaah, that explains it. I skimmed over the sentence where you detailled your initial population when I read your original post. As a result I was very confused by the fact that you stopped only after 20 generations. That seemed way lower than what the YouTuber was describing. Thanks for the clarification. Your approach makes way more sense with that clarification.

By the way I remember an old thread that I read on the MtgSalvation a long time ago. Someone was running an experiment called Mill It to Win It in which they would try to build the best mill deck. If you tweaked your optimization criteria to match theirs, you could try doing the same and compare the performance of your deck to theirs since all the results are still available online. This could give you a comparison point to gauge the performance of your approach.

[austinio7116]

Here are some decks from Standard M19 using this approach:

https://drive.google.com/folderview?id= ... JWX-_PwScT

Lots of mono coloured decks in M19 that the AI plays well: Angels, Cats, Flyers and Zombies

[Arcanist]

Here are some decks from Standard M19 using this approach:

https://drive.google.com/folderview?id= ... JWX-_PwScT

Lots of mono coloured decks in M19 that the AI plays well: Angels, Cats, Flyers and Zombies

Thanks! Looking at the first deck (GAS_1_66_Mono White Angels Generated Deck_823_17.dck), a couple of things look off:

• The deck list includes different types of Plains, which seems to indicate that the algorithm consider them as different cards. If true, you could easily reduce the size of the search space by treating all basic lands of a given type as the same card. Same thing for cards with multiple printings.
  
• It is supposed to be a mono-white deck, yet the sideboard contains three black cards and no swamp. Am I right in assuming that your algorithm never uses the sideboard? If that is the case, you should either remove it from the deck list (since it is just noise). Alternatively you could modify your approach to include side-boarding for all games but the first of each match.

[austinio7116]

Here are some decks from Standard M19 using this approach:

https://drive.google.com/folderview?id= ... JWX-_PwScT

Lots of mono coloured decks in M19 that the AI plays well: Angels, Cats, Flyers and Zombies

Thanks! Looking at the first deck (GAS_1_66_Mono White Angels Generated Deck_823_17.dck), a couple of things look off:

• The deck list includes different types of Plains, which seems to indicate that the algorithm consider them as different cards. If true, you could easily reduce the size of the search space by treating all basic lands of a given type as the same card. Same thing for cards with multiple printings.
  
• It is supposed to be a mono-white deck, yet the sideboard contains three black cards and no swamp. Am I right in assuming that your algorithm never uses the sideboard? If that is the case, you should either remove it from the deck list (since it is just noise). Alternatively you could modify your approach to include side-boarding for all games but the first of each match.

Basic lands are added at the end, to ensure a good mana base for the cards in the main deck and are taken from sets present in the main deck that have basic lands in them. The forge AI doesn't sideboard, so those cards are not included in the manabase generation. Also, decks named Mono are not always going to be mono colour, it depends on how the clusters end up after the LDA analysis and random sampling of those clusters. The names of the archetypes use words most commonly present in the input human named decks.

[ageor]

Genetic algorithms on slightly magic! Yup, always go for the low hanging fruits when doing data science.
Would like to contribute to this, hopefully will get some free time in the next month.

[mercazole70]

I always have fun playing with your deck.
Is there an updated version of AI deck for modern rules?

[austinio7116]

I always have fun playing with your deck.
Is there an updated version of AI deck for modern rules?

I'll try to do an update after Ravnica Allegience

[mercazole70]

I am looking forward to the new deck
Your deck is a wonderful battle partner every time.

[austinio7116]

Coming soon

[austinio7116]

Here are the results from running a 20 generation genetic algorithm on data generated with the LDA deck generation tools on Modern data with deck data from the last 6 months. Not a huge change to this meta from recent sets, but a couple of cards here and there.

Winning decks are:
Merfolk
Goblins
8-rack
Affinity Robots (with Experimental Frenzy from GRN)
Soul Sisters
GW Aggro
GW Bogles

[austinio7116]

Izzet drakes was a no-show in the final standings

[austinio7116]

I accidentally ran the Modern algorithm without deck conformance on, so some decks generated had fewer than 60 cards. I am running again with that fixed so will post some more decks. In the meantime here are some Standard decks.

[austinio7116]

Here are the updated Modern winners - should all be 60 cards this time. Merfolk was the clear winner.

[mercazole70]

Thank you for offering a wonderful deck.
This time I was able to win the GA deck using my deck.
Personally, Benalish Marshal first posted first feels most speedy and strongest.
However, as all the GA decks are strong, fighting is a lot of fun:)