This is our first blogpost on our new website. Previously we blogged here. In this post, Marnielle writes about creating a new AI for Political Animals:
I've been using Genetic Algorithm as an aide for game design and development. It fills me with excitement that I can simulate natural selection to help me look for the best solutions to problems. Now I'll tell you the story of how I used it to improve our AI.
My GA knowledge is still somewhat limited. I learned how to write code for it using this website (Go read it. It's awesome! So unlike smarty academic papers.) To give you an idea in casual speak, GA is basically simulating the theory of evolution to look for the most “fit” solution. In this simulation, the species or “individuals” are the solutions to the problem. At the start, a certain number of individuals are spawned with random configurations. As such, most of them are dumb solutions at the beginning. Each of them are then assessed and given a fitness score. The ones with higher score means they are closer to the solution. Based from this initial population, we spawn the next generation. To do that, we either mutate or let them breed (Yes, solutions can mate) with a rule that those with higher fitness score has a higher chance of being selected for mutation or breeding. With this new generation, we repeat the process of assessment and spawning the new generation until we can find that one individual that solves our problem.
When coding a GA, you need some important pieces. These are the individual representation, the fitness assessment function, mutation function, and crossover function. If you have these four, you can run a GA. Individual representation is a bit tricky. How do you represent a solution that can also be mutated and bred? One of the most common is a list of bits. This can be represented by a list of booleans or just integers and use bit manipulation. Mutation is just then flipping a random number of bits. Breeding or crossover is simply exchanging a certain number of bits from two individuals.
Representation by bits is the only representation I know of. It's what AI Junkie taught me and I sticked with it. That's until I've read a book called “Essentials of Metaheuristics”, a highly recommended book. The contents are written in an informal way, not in an academic bullshit way. It's a primer on different algorithms in the field of metaheuristics. Most of it, though, is GA. From there, I learned that you can represent an individual with anything. It can be lists, trees, graphs, your own data structure. Mutation and crossover can be any made up alteration of your representation. It can be adding a child, removing a child, changing a value, swapping nodes and edges. Anything! I realized how dumb I was for not going to that thought.
That gave me an aha moment. What if I automate the creation of our AI using GA. Our AI configuration is very simple. At the same time, AI is also the most neglected part of our game. We haven't touched it for a long time. We have a working AI that I configured by hand. But then, our mechanics have already changed too much that we don't know if it's still competitive. Configuring a new AI would take time.
My team gave me a week to work on this, May 2-8, 2016. I'm not so sure if it would work. What if looking for a better AI takes time, like it would take days running the simulation. I certainly thought so because the assessment function is to let two AI players pit against each other. The one who wins has a bigger fitness score. Now, a single playthrough takes time, even if I speed it up. The point is, making the GA could be a waste of time.
The first thing I did is I made a fast mode of our game. No animations, movement becomes teleportation, removed the standby/wait times, etc. It wasn't easy. I don't have time to write another version of the game solely for GA. Instead, I'm using what we have now and provided a mode that it can be played extremely fast. Finally, I have a mode where AI vs AI takes around 1 minute to complete 15 turns. Still not fast enough, but quite good already.
Then I made something called a “multi frame” GA. Basically, it's GA that is spread in multiple frames. Note that the assessment function is for AI to play the game. So the GA must wait for such game to end before it can move to the rest of the algorithm. In fact, if there are 10 indiduals in a generation, 10 games must be played before moving on to spawn the next generation.
Our AI configuration is all code. We use a utility based AI, by the way. It is represented as a set of “task scorers”. Each scorer has an arbitrary set of “considerations”. These considerations are classes that help compute the score for the task. The AI generates all the possible tasks, scores them using the scorers, and picks the one with the highest value.
My plan is to use GA to generate different combinations of these scorers and considerations until we get the one that beats the current best configuration. Before anything else, I needed my configuration to be saved in a file. Every time the GA finds a better AI, it should save the configuration in a file. So I turned the AI configuration into XML. I used the class names and variables of consideration classes in this file. I load them back using reflection. It looks like this now:
<ScorerSet id="IndividualZero" fitness="1" timestamp="">
<Scorer taskId="Bribe">
<Consideration name="BlockadedDistrictConsideration" />
<Consideration name="TerrorizedConsideration" />
<Consideration name="MinimumBudgetConsideration">
<Variable type="NamedInt" name="minimumBudget" value="1000" />
</Consideration>
<Consideration name="ReachableConsideration">
<Variable type="NamedFloat" name="multiplierIfUnreachable" value="0" />
</Consideration>
<Consideration name="MustHaveMatchingPlatformConsideration" />
<Consideration name="ReachReputationConsideration">
<Variable type="NamedFloat" name="populationPercentage" value="0.85" />
</Consideration>
<Consideration name="BonusTuningConsideration">
<Variable type="NamedFloat" name="bonusToSet" value="1.0" />
</Consideration>
<Consideration name="CommandPointsConsideration" />
<Consideration name="NeighborCountConsideration">
<Variable type="NamedInt" name="desirableCount" value="4" />
</Consideration>
<Consideration name="OpponentStaffCountConsideration" />
<Consideration name="BribeBetterThanCampaignConsideration">
<Variable type="NamedInt" name="minReputationGainDifference" value="1000" />
<Variable type="NamedInt" name="rankIfMet" value="17" />
<Variable type="NamedInt" name="bonusIfMet" value="10" />
<Variable type="NamedFloat" name="multiplierIfMet" value="5" />
</Consideration>
<Consideration name="ScandalCountReachedConsideration">
<Variable type="NamedInt" name="scandalCount" value="4" />
<Variable type="NamedFloat" name="multiplierIfMet" value="0" />
</Consideration>
</Scorer>
<Scorer taskId="RaiseFunds">
<Consideration name="BlockadedDistrictConsideration" />
<Consideration name="TerrorizedConsideration" />
<Consideration name="ReachableConsideration">
<Variable type="NamedFloat" name="multiplierIfUnreachable" value="0" />
</Consideration>
<Consideration name="HasSignificantFundsConsideration">
<Variable type="NamedInt" name="preferredAmountToRaise" value="1000" />
</Consideration>
<Consideration name="BonusTuningConsideration">
<Variable type="NamedFloat" name="bonusToSet" value="1.0" />
</Consideration>
<Consideration name="LowFundsConsideration">
<Variable type="NamedFloat" name="fundsThreshold" value="0.3" />
</Consideration>
<Consideration name="CommandPointsConsideration" />
<Consideration name="HigherReputationConsideration" />
<Consideration name="NeighborCountConsideration">
<Variable type="NamedInt" name="desirableCount" value="4" />
</Consideration>
<Consideration name="NearBailiwickConsideration" />
</Scorer>
<!-- ... Rest is ommitted -->
</ScorerSet>
The mutation function then is just a matter of:
Add random consideration
Remove random consideration
Change some random variables
Crossover between two individuals is simply swapping a random number of considerations.
For the initial population, I used our existing AI as a starting point. I called it “Individual Zero”. The first population are individuals that are mutated versions of him. Now with all the pieces together, I have a GA that looks for a better AI.
First Runs
When I was about to finish, I was too excited to run it. I know it will take time so I plan to run the simulation overnight when I'm asleep. It was Saturday night. I'm sleepy and tired. I fixed some errors that would potentially halt the simulation. I set the settings for the fast mode. Every game lasts only 15 turns. The population size is set to only 10. Then finally I let the baby run. I watched the first few AI matches. After a while, nothing goes wrong, I locked the laptop and went to bed.
When I woke up, I checked it immediately. The simulation had hung. I looked at the Task Manager. 90% RAM usage. So I closed it. But lo and behold, it generated 10 AI configurations, each one better than the last one before it. So I was like “that went well”. I pushed my work and restarted my laptop. Then my laptop won't start. It only said “Diagnosing Your PC”. But I wasn't worried. I know I didn't do anything stupid. The simulation just probably messed up the memory. An hour later, my laptop was alive again. I immediately fixed the memory leak. Lesson learned when writing a resource intensive GA like this one.
After coffee, I decided to play a game against the new AI and see if it's really indeed better. Maybe it's just better against other AI but not humans. So I used my usual strategy. Bribed supporters on the first few turns. I acquired districts as soon as I can. I was winning. Every 5 turns, the game shows this graph about how many supporters each candidate has. I beat his numbers every time. I even have more acquired districts than him. Am I really playing against a better AI? On the last turn, I've made my actions. I knew I was gonna win. I controlled more districts than him. That dread that I probably just wasted time returned again. Election came... the AI won an unbelievable landslide. Jaw dropped. Turns out he didn't care about the voters and was befriending more patrons than me. Well, I guess I created a monster.
Thanks for reading. If you'd like to be updated on the latest Political Animals, please sign up for our mailing list!