It is currently 14 Nov 2018, 10:59
   
Text Size

Genetic algorithm to find the strongest AI decks

Moderators: timmermac, friarsol, Blacksmith, KrazyTheFox, Agetian, CCGHQ Admins

Re: Genetic algorithm to find the strongest AI decks

Postby austinio7116 » 16 Aug 2018, 12:21

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.
User avatar
austinio7116
 
Posts: 380
Joined: 10 Mar 2017, 11:59
Has thanked: 47 times
Been thanked: 124 times

Re: Genetic algorithm to find the strongest AI decks

Postby Arcanist » 16 Aug 2018, 22:44

austinio7116 wrote: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.
Arcanist
 
Posts: 68
Joined: 20 Jun 2015, 20:12
Has thanked: 5 times
Been thanked: 10 times

Re: Genetic algorithm to find the strongest AI decks

Postby austinio7116 » 19 Aug 2018, 22:03

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
User avatar
austinio7116
 
Posts: 380
Joined: 10 Mar 2017, 11:59
Has thanked: 47 times
Been thanked: 124 times

Re: Genetic algorithm to find the strongest AI decks

Postby Arcanist » 20 Aug 2018, 11:18

austinio7116 wrote: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.
Arcanist
 
Posts: 68
Joined: 20 Jun 2015, 20:12
Has thanked: 5 times
Been thanked: 10 times

Re: Genetic algorithm to find the strongest AI decks

Postby austinio7116 » 20 Aug 2018, 11:36

Arcanist wrote:
austinio7116 wrote: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.
User avatar
austinio7116
 
Posts: 380
Joined: 10 Mar 2017, 11:59
Has thanked: 47 times
Been thanked: 124 times

Re: Genetic algorithm to find the strongest AI decks

Postby ageor » 03 Oct 2018, 21:28

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.
ageor
 
Posts: 2
Joined: 02 Oct 2018, 21:56
Has thanked: 0 time
Been thanked: 0 time

Previous

Return to Forge Decks

Who is online

Users browsing this forum: No registered users and 4 guests


Who is online

In total there are 4 users online :: 0 registered, 0 hidden and 4 guests (based on users active over the past 10 minutes)
Most users ever online was 279 on 11 Jul 2013, 22:03

Users browsing this forum: No registered users and 4 guests

Login Form