Implement Wildcard and/or Deck Evolution features

[GoogleCodeExporter]

This is a catchall thread for discussing Wildcard/Evolution features for CLI.

(My initial comments are based on CLI 480 and all of this is here to avoid 
clutter on the Kongregate threads.)

During the past week I have implemented a rough set of Python scripts that 
implement a straightforward deck evolution algorithm. The work is relatively 
well segmented so that its core can be reused for a Wildcard implementation as 
well.

This weekend I hope to shove it all somewhere so we have real code to discuss 
and compare but that will have to wait.

----

The core algorithm works with a few assumptions:

* The CLI is a black box; decks go in, a win count comes out
* All game logic is handled by the CLI
* Card and deck hashing has been reimplemented in Python
* Limited card data is processed from cards.xml
* Legendary and Unique restrictions are also reimplemented

The basic evolution algorithm is as such:

* Define a Deck of 1 commander and 10 non-commander cards
* Define a set of Target decks to score against
* Define the full set of Eligible replacements
* For each Eligible commander, replace the Deck's commander and run N 
simulations against each Target deck and sum the scores
* Split the set of non-commander Eligible replacements into 10 Subsets
* For each non-commander card in the Deck, choose one of the 10 Subsets and...
* For each Replacement card in that Subset...
* Run N simulations against each Target deck with the Replacement card
* After all simulations have been run, return the best scoring deck

So what I did is make a set of 10 random decks as E0 and then told it to make 
E1 by feeding in each deck from E0 with the whole set of E0 as the target deck.

Which takes quite a bit of time to run; setting N at 100 simulations results in 
a new Evolution every hour. If I hit a crash in the CLI it brings the whole 
script down, however, so I just filter out problem cards and start the script 
up again from the last successful evolution.

There are complications in determining what "eligible" cards are at any given 
point but here is the basic logic for that:

* Take full card set (or custom set if so desired)
* Remove any uniques from eligible set if they are already used by Deck
* If Deck has a legendary, remove all legendaries from eligible set
* Later, when comparing a legendary for replacement, add the legendaries back 
in only for that comparison
* Don't forget to include the non-evolved deck's score to make sure you don't 
devolve (this also allows us to avoid complicated unique handling)

----

What I have learned from implementing the above:

* The CLI works great for single deck simulations

* Deck hashes are nice but not very human readable; getting a basic hash to 
deck converter is handy. There are three deck "formats" worth noting: Hashes; 
Ids; Names.

* A wildcard feature is the above algorithm run on only one card index from a 
deck at any given time. I have this prototyped in my code but have not tested 
it yet.

* I made quick decisions on how to record multiple decks per file and chose to 
also record their scores against each other. I keep only one evolution step per 
file but will probably switch over to a more thorough XML format at some point. 
This would be a good thing to coordinate.

* The above algorithm should work great for wildcard comparisons against 
miscellaneous batches of decks; the essential inputs of each step of the 
process are accessible. This means people can do [Deck A set to Wildcard at 
Index 4] vs. [Current metagame set of decks]. I imagine this will be the most 
common use case.

* Mission decks and raid decks should be as simple as using the appropriate 
parameters in the CLI.

* If I could add one feature to the CLI at this point it would be a [Deck] 
versus [File of decks] feature that kicks out a list of win counts separated by 
spaces.

* The second feature I would add is better output flags. In my case, I only 
really care about win count. I have to parse the output string from the CLI and 
instead of having to react to any output changes from your end I would prefer 
to send in a -quiet flag that will always output *just* the win rate (and a -1 
on failure).

* Other, less important, features: "Scoring mode" that returns things like 
Faction War scoring (summed across all simulations); "Defensive mode" which 
includes all stalls as wins; tournament mode (maybe you already have this?); 
some way to get the "order of cards" info used in the old GUI application

----

As far as where to go from here, I am happy polishing up my scripts as part of 
my learning of Python. If you want to see them I can send you the code; you can 
use whatever you find useful.

My opinions on whether to use just the one CLI program are mixed. On the one 
hand, it is nice to have just the one application. On the other, I like being 
able to rely on the core program for simulations. Most of the features we 
really want do not need to interact with a simulation once it has been started.

But, if it were my call, I would split things into a "Simulator-CLI" or Core 
and then implement all the bells and whistles in a separate program that just 
calls the first when it is time for simulations. Here is a short list of 
benefits:

* It makes it easier for others to use the simulator in their own tools
* When expansions or modifications need to be made, we can get a new Core up 
and running faster
* Chances are extremely high that getting the Core updated will make most of 
the tools people use automatically work
* If someone decides to write a fancy GUI, all they have to do is call the 
simulator and people working on the Core (*cough* you *cough*) do not have to 
"own" any of the GUI. Likewise, if someone wants to fix the Core if you find 
different hobbies, they do not feel pressured into picking up the GUI too.
* If someone else wants to make their own Core, they will probably mimic the 
CLI interface and, ideally, that will make it work with any other tools being 
created

My two cents.

----

My personal goals at this point:

* Finish the actual Wildcard version
* Upload the code somewhere people can play with it
* Hook into the old ownedcards.txt used by the GUI
* Hook into the Mission/Raid settings in the CLI
* Get a C++ development environment set up to help out more generically

Thanks for reading. :)

PS) Here are the current ten decks from Evolution 28, sorted by how well they 
score against each other.

QVKFJdIWLWDvJdE7CDJdKk  781
RLgv+iJeKLLMKvLM+jhF    737
RLLM+igvKvLMLwKLKvgv+i  730
RLLfKLJeLfLM+kgoLM  673
QVhFKvIGCtLMKCLFLMLfJw  652
QVLhIGLhKoKDLhKkfnLh+i  645
QVLMIYLM+ifZIGLwJwKDJe  641
QVIbLfLhKoLhKDLh+iB+KD  638
RLJeLMIGLfLwH8LMJwLMgj  611
P5JwJ5LMIGLMLFLMLfJeKC  584

After only 28 replacements, the top deck is well on its way to a Syncophant 
deck. Watching the evolution steps, the most popular starting replacements was 
Monarch. The most popular cards in general across the various evolution steps 
(in no particular order):

* Heracles
* Monarch
* Zarak
* Radio Officer
* Dracorex
* Any commander with Siege (mostly because of all the Zaraks that showed up in 
E10-20; yay metagame.)

As you can tell from the ten decks, Awaking is where almost all the winning 
cards are and Righteous Summon is the most dominant archtype. I am curious to 
see how they solve the Syncophant problem.

Original issue reported on code.google.com by malats...@gmail.com on 7 Sep 2012 at 1:58

[GoogleCodeExporter]

It seems your evolution is similar to mine. 
Basically I defined "mutations" on decks.

Your concerns for keeping this seperate are understandable and I agree. There 
is no tight bound currently and I will try to keep this lose.

I will try to show you what I did.

Original comment by fabianku...@web.de on 7 Sep 2012 at 3:57

• Added labels: Type-Other, Priority-Low
• Removed labels: Type-Defect, Priority-Medium

[GoogleCodeExporter]

So, this is my general approach. Input is the usual input: two decks.
The first will be mutated, the second obviously not.
The following mutations will be applied each round:
// 1) do not modify at all
// 2) change commander
// 3) remove a card (if not empty)
// 4) add a card (if not full), for ordered consider positions
// 5) replace one card with another (if not empty)
// 6) swap order of two cards (for ordered decks with at least two cards)
// 7) order an unordered deck
// 8) unorder an ordered deck
Then they are compared to each other, the best is kept, all others are removed.
The process restarts until it converges.

Original comment by fabianku...@web.de on 7 Sep 2012 at 8:16

[GoogleCodeExporter]

Oh, adding and removing cards is a good idea. How many simulations are you 
typically running per step?

I did not get as much time this weekend as I was hoping so I have nothing 
interesting to show for it.

Original comment by malats...@gmail.com on 10 Sep 2012 at 3:19

[GoogleCodeExporter]

It is not working good right now, so I can not give an estimate about the 
number of simulations: That changes all the time.

Original comment by fabianku...@web.de on 12 Sep 2012 at 8:16

[GoogleCodeExporter]

My progress from the past few days:

I have hacked in a way to limit cards to only use those found in the 
EvaluateDecks ownedcards.txt. Don't have command line args up for it yet.

My first attempt at profiling Python scripts was not very fruitful; I need to 
find a better way to do this on Windows. Most of the good solutions I found 
were *nix and I didn't feel like compiling things this week. :P

Rarity filters working but not hooked up to arguments yet.

I am assuming that there is less of an interest in these scripts now that 
NETRAT is back; when I get brave enough to upload things I will probably just 
drop it on my GitHub -- unless you want it here. I don't personally see much of 
a reason to keep it here since it is fairly orthogonal to everything except the 
core.

Original comment by malats...@gmail.com on 14 Sep 2012 at 4:10

[GoogleCodeExporter]

Sure it is orthogonal. However I think this is still relevant: The GUI only has 
a very basic wildcard feature, there is room for much more.

Original comment by fabianku...@web.de on 15 Sep 2012 at 9:46