Forums Tyrant

Automatic deck optimization

1333 posts

Flag Post

TO with user interface can be found at http://www.hunterthinks.com/to/gui :
latest version http://www.hunterthinks.com/to/gui/releases/tyrant_optimize_gui_mingw_v151.zip

And without the user interface can be found at http://www.hunterthinks.com/to :
latest version http://www.hunterthinks.com/to/downloads/tyrant_optimize_1_1_6.zip

|||||||||||||||||| Old stuff below, out of date ||||||||||||||||||

Source:
Hosted on github

Usage information: (the program is command line only)


usage: ./tyrant_optimize.linux64 <attack deck> <defense decks list> [optional flags] [brute <num1> <num2>] [climb <num>]
<attack deck>: the deck name of a custom deck.
<defense decks list>: semicolon separated list of defense decks, syntax:
deckname1[:factor1];deckname2[:factor2];…
where deckname is the name of a mission, raid, or custom deck, and factor is optional. The default factor is 1.
example: ‘fear:0.2;slowroll:0.8’ means fear is the defense deck 20% of the time, while slowroll is the defense deck 80% of the time.
Flags:
-c: don’t try to optimize the commander.
-o: restrict hill climbing to the owned cards listed in “ownedcards.txt”.
-r: the attack deck is played in order instead of randomly (respects the 3 cards drawn limit).
-s: use surge (default is fight).
-t <num>: set the number of threads, default is 4.
Operations:
brute <num1> <num2>: find the best combination of <num1> different cards, using up to <num2> battles to evaluate a deck.
climb <num>: perform hill-climbing starting from the given attack deck, using up to <num> battles to evaluate a deck.

Useful stuff:
Create ownedcards.txt: you need this file to use the -o flag. To create it, you need to be registered in the fansite and copy/paste the list of your owned cards into a file named ownedcards.txt (go to cards → export to sim).

Custom decks: you can add decks to the Custom.txt file.

Examples:
To optimize for Mission 204, starting from an ogre deck, using climb and 8 cores:

./tyrant_optimize.exe “ogre-spam” “Mission 204” climb 100000 -t 8

Optimizing a deck against
(1) 20% of the time a sycophant defense
(2) 80% of the time a slowroll defense
on surge and up to 100000 battles per deck evaluation:

./tyrant_optimize.exe “azure-spam” “fac-sycos:0.2;fac-rs:0.8” climb 100000 -s

Finding an ordered deck for a raid, limited to your owned cards, up to 25000 battles:

./tyrant_optimize.exe “azure-spam-5” “Lernaean Hydra” climb 25000 -o -r

 
Flag Post

Would you release your code as open-source?

 
Flag Post
Originally posted by catepillar:

Would you release your code as open-source?

Probably eventually, but not yet, because it is too ugly and hard to use :). Also there is no GUI. I plan on just explaining the principle at first.

 
Flag Post
Originally posted by commonkey:
Originally posted by catepillar:

Would you release your code as open-source?

Probably eventually, but not yet, because it is too ugly and hard to use :). Also there is no GUI. I plan on just explaining the principle at first.

I love the idea of no gui ;)
What’s your development platform?

Edit: To add on to a wish list of features that I (personally) would like to see (and trust me, when I get the time, if there is nothing out there that has these features, I will begin a development process):
1. The ability to simulate a battle AFTER it has started. So (the way I envision it), I would see my deck lay my first card. Update the simulator letting it know what card I played. Then my opponent drops a card. I again update the simulator. The simulator then looks at the 3 cards in my hand and runs similuations to completion letting me know which card gave me the best odds of winning.
2. A comprehensive CLI. I want to be able to have CLI switches that can do everything. I (personally) am not opposed to making my own wildcard file (of cards I own) to run simulations on.

Those are all I can think of at the moment. I am sure more will come to me.

 
Flag Post

I love the idea of no gui ;)
What’s your development platform?

Not a specific one really, mostly windows, sometimes on linux. It’s in c++ and compiles with gcc (on linux) and its port mingw32 on windows.

 
Flag Post
Originally posted by commonkey:

I love the idea of no gui ;)
What’s your development platform?

Not a specific one really, mostly windows, sometimes on linux. It’s in c++ and compiles with gcc (on linux) and its port mingw32 on windows.

I like you. I like you a lot. lol. You might just be my hero. I have wanted something that works well on Linux, and I even went so far as to try and port NETRAT’s code. And I kept running into issues that I couldn’t trace to a particular problem, so I ended up taking a break.

 
Flag Post

I think it would be fine for missions and raids.

 
Flag Post

Maybe this is my academic background speaking, but, except in the short run, it’s not like you can stop knowledge.
It’s not that hard for anyone with a bit of background in programming to do what you describe. I would probably do it if I had more time.

As for the claim that deckbuilding is an important part of the game, that is true. For one, people don’t have to use such tools if they don’t want to. Second, if some part of the game can easily be automated, the easiest way to fight this is to CHANGE THE GAME and not ban the tools. I speak from experience with many MMORPGs, etc… For example, the devs could try to make enemy decks much more sensitive to card order, etc…

Finally, I disagree that building a good manual deck would require “true AI”. It’s not like you’re finding a real optimum for the auto problem anyway. Similarly, I can think of many ways to heuristically build good manual decks for missions and raids, it’s just one more layer to optimise. You could do it like EvaluateDecks does at the moment and just consider a fixed play order first, using some kind of hill-climbing algorithm, then you can later consider more complicated options. I agree that for tournaments, it’s again more complicated because the opponent is not playing on auto.

 
Flag Post

Do not release its code. Never!=)
Tyrant will turn into a bot competition… If catepillar wants something for his bots let him at least put some effort in it =)

 
Flag Post

lulthyme: I agree with all that you said. If there is a part in a game that is easy to automate, then it will be automated. Even if it’s not so easy to automate ;). I’m thinking about the diablo 2 bots for exemple which were actually more efficient than real human players. For manual decks, it’s true that simple heuristics could be used to provide decent results, but it’s very hard to design a really good deck without being able to play the cards smartly, and for that you would probably need some kind of state space search to predict ahead of moves, or maybe a learning based algorithm.

 
Flag Post

Well, it is hard to stop knowledge.

However, what I think would be a large help is if you shared the theory behind the code (the psudocode if you will). And do it in the form of a “how to build a good deck” sort of post. This might help educate the community on how to build a good deck for a specific situation. This of course assumes that you do not “brute force” the choice by some min-max algorithim, and instead use analyis of the deck to be beat as a starting point for the deck optimization.

Do what you will though. Knowledge is power. I am still hoping that the next iteration of Tyrant comes with some sort of more dynamic battle senerios (so to make them more “unbottable” and difficult to go to the web for a 99% auto solution).

-Pip

 
Flag Post

@above – like raids? but with more variety? hell no.
I want an easier, more fun game, not a more troll-like game.

 
Flag Post
Originally posted by TheRealPip:

Well, it is hard to stop knowledge.

However, what I think would be a large help is if you shared the theory behind the code (the psudocode if you will). And do it in the form of a “how to build a good deck” sort of post. This might help educate the community on how to build a good deck for a specific situation. This of course assumes that you do not “brute force” the choice by some min-max algorithim, and instead use analyis of the deck to be beat as a starting point for the deck optimization.

Do what you will though. Knowledge is power. I am still hoping that the next iteration of Tyrant comes with some sort of more dynamic battle senerios (so to make them more “unbottable” and difficult to go to the web for a 99% auto solution).

-Pip

My method is dumb (but that’s why it works), it’s much more similar to brute force than to a “smart” analysis. I tried “smart”, but it didn’t work well, because the effect of cards is wildly unpredictable. There is no obvious rules, and even counter cards are not necessarily good against the card that they supposedly counter. So, it’s difficult to analyse the strength or weakness of a deck, and sometimes a good deck is non intuitive even for a human player.

 
Flag Post

Well, it doesn’t seem like this will improve too much on auto-decks we already come up with using Eval Decks (aside from maybe some glitches from Eval Decks). However, I guess it’ll save a bit of time and perhaps provide a second evaluation for logic error testing.

Even if we use this to automatically optimize a deck, we’d still be trying to manually optimize it further anyway… I guess the most difficult thing to do is to optimize a manual deck. By any chance, does your optimizer support ordered decks?

 
Flag Post
Originally posted by Shadowhopeful:

@above – like raids? but with more variety? hell no.
I want an easier, more fun game, not a more troll-like game.

Actually, I was speaking to the Quest idea shared in a seperate post and (from what I understand) largly embrased by the users on this form and chat that I have spoken with. I would akin them closer to achievements but much more diverse and random (and you don’t necessarly know what you are going to get at the start).

-Pip

 
Flag Post
Originally posted by Moraku:

Well, it doesn’t seem like this will improve too much on auto-decks we already come up with using Eval Decks (aside from maybe some glitches from Eval Decks). However, I guess it’ll save a bit of time and perhaps provide a second evaluation for logic error testing.

Yep, that’s a good point, it just saves some time.

Even if we use this to automatically optimize a deck, we’d still be trying to manually optimize it further anyway… I guess the most difficult thing to do is to optimize a manual deck. By any chance, does your optimizer support ordered decks?

No, I wanted to add it, but I didn’t have the time to do that yet.

 
Flag Post

The Quest idea is great imo.
Also, more achievements.

 
Flag Post
Originally posted by catepillar:

Edit: To add on to a wish list of features that I (personally) would like to see (and trust me, when I get the time, if there is nothing out there that has these features, I will begin a development process):
1. The ability to simulate a battle AFTER it has started. So (the way I envision it), I would see my deck lay my first card. Update the simulator letting it know what card I played. Then my opponent drops a card. I again update the simulator. The simulator then looks at the 3 cards in my hand and runs similuations to completion letting me know which card gave me the best odds of winning.

This would be ridiculous. Not that i would mind playing against someone using this bot, after all in this game there is a counter to basically any strat so instead of playing versus a person i would be playing versus an algorythm. But why would you let a piece of software play for you? Is marginally improving your winrate so important to you that you wouldn’t mind let it take all the fun out of the game?

 
Flag Post

I think I need to clarify my position a bit here. I was thinking mainly for missions and raids, and especially doing achievements with less than optimal decks.

 
Flag Post

Since the concept of optimal is only valid for auto I think your only argument against this is invalid, so shoot!
also: I am interested to hear the algorithm :)
maybe I can help you get out of the local maximum you got stuck in for Pantheon Perfect ;) and possibly more that we dont know better solutions of yet

question: whats the processing time to find an “optimal” deck from zero?

 
Flag Post
Originally posted by necksnapper:

Since the concept of optimal is only valid for auto I think your only argument against this is invalid, so shoot!
also: I am interested to hear the algorithm :)
maybe I can help you get out of the local maximum you got stuck in for Pantheon Perfect ;) and possibly more that we dont know better solutions of yet

question: whats the processing time to find an “optimal” deck from zero?

The order of finding the PERFECT order to play against any single (player) deck is 10, which is astronomically large (1.31681894 × 10^13 ). Modern computers are unable to run an algorithm like that in a reasonable amount of time. (For instance let’s say we have a dual-core 3GHz machine, and each simulation takes 1000 clock cycles (that’s probably on the very low side), then you are still looking at a run time of over 4 MILLION seconds (or approximately 45 days). And with the large amount of randomness in this game that (10) is a lower bound. If there is only one strike card, then that jumps up to potentially 10x10! which results in a run time of nearly 500,000 years.

Note that I made quite a few assumptions, but nearly every assumption I made was to underestimate these numbers, so the real numbers will be more than likely MUCH MUCH larger. It is my conclusion that finding “THE” optimal deck is nearly impossible, and with today’s computers, completely unfeasible.

 
Flag Post
Originally posted by catepillar:
Originally posted by necksnapper:

Since the concept of optimal is only valid for auto I think your only argument against this is invalid, so shoot!
also: I am interested to hear the algorithm :)
maybe I can help you get out of the local maximum you got stuck in for Pantheon Perfect ;) and possibly more that we dont know better solutions of yet

question: whats the processing time to find an “optimal” deck from zero?

The order of finding the PERFECT order to play against any single (player) deck is 10, which is astronomically large (1.31681894 × 10^13 ). Modern computers are unable to run an algorithm like that in a reasonable amount of time. (For instance let’s say we have a dual-core 3GHz machine, and each simulation takes 1000 clock cycles (that’s probably on the very low side), then you are still looking at a run time of over 4 MILLION seconds (or approximately 45 days). And with the large amount of randomness in this game that (10) is a lower bound. If there is only one strike card, then that jumps up to potentially 10x10! which results in a run time of nearly 500,000 years.

Note that I made quite a few assumptions, but nearly every assumption I made was to underestimate these numbers, so the real numbers will be more than likely MUCH MUCH larger. It is my conclusion that finding “THE” optimal deck is nearly impossible, and with today’s computers, completely unfeasible.

of course a pure brute force approach is too slow, there are other ways…

 
Flag Post

Netrat’s Sim gives a pretty good indicator.
Throw the best deck you have in for 1000000 runs, look at which play orders have the highest success rates, test those, rinse, repeat.

 
Flag Post
Originally posted by necksnapper:

of course a pure brute force approach is too slow, there are other ways…

Please do enlighten me. As a comp science student, I would love to hear a better approach, but unfortunately, I do not see one (mainly due to the large amount of randomness in what get hit by strike or gets enfeebled, or what gets sieged and when).

Originally posted by Shadowhopeful:

Netrat’s Sim gives a pretty good indicator.
Throw the best deck you have in for 1000000 runs, look at which play orders have the highest success rates, test those, rinse, repeat.

So why not have something that can simulate the 3 cards in your hand, and figure out which is the best play? And keep doing that for each card that you draw? I feel like it is a very practical way to not waste energy. And some of the acheivement decks only have a win rate of 10%, but with “optimal” play can reach as high as 30%. Why not try to take that 30% to 40-50%?

 
Flag Post

There are shortcuts to solving problems like optimal card order.
For example, if you find that moving Hephatat one slot to the left decreases your winrate, stop moving it to the left, and try moving it to the right. That’s just one basic method to cut down the number of runs.