I Created a Politically Corrupt AI

(This was originally posted in Squeaky Wheel’s website.)

Advertisements

(This was originally posted in Squeaky Wheel’s website.)

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.

New Stuff and a Tip on Starting Coding Momentum

Development of Party Animals has been hanging around for over a year already (or years) but the truth is that the game’s mechanics are not yet zoned in. We’re still looking for the fun part. We’re at the stage when we are adding new mechanics and testing them out as soon as we can then decide whether to keep them, change, or discard. If we’re not having fun with it, our target players most probably won’t. While we unanimously agree that what we have is fun enough, something is still missing. This post will be enumerating what we’ve done so far. As a bonus, if you stay a while, you’ll get a tip on how I start my coding momentum.

Command Points

As context, Party Animals is a game about winning an election. The main mechanic unit of the game are the Staff which the player can move around in different districts and make them execute actions. The game is basically an attrition with an opponent through Staff actions.

We introduced the concept of Command Points (CP) to control the movement of Staff such that players are forced to strategize on which district to move next as usage of such units now have cost. CP cost is simply defined as the shortest district distance of a Staff from its Candidate (a Candidate is just another Staff with special abilities). If a Staff is in the same district as its Candidate, then CP cost for the Staff is zero. CP resource is assigned to each candidate at the start of the turn. It is increased when certain campaigning days are reached. In real life, we’d like to think of this as the cost of planning with your Staff that is in another city or province.

During playtesting, Command Points had a direct effect on Staff movement. During early game, players only move their Staff along one adjacent district distance from their Candidate.

Pay CP first before you can use your Staff
Pay CP first before you can use your Staff

New Meaning of Reputation

Reputation is one of the most important metric in our game. It directly tells whether or not people will vote for a candidate in a certain district. It used to be a percentage of the population in the district that is willing to vote for you. It’s a value between 0 – 100. Not anymore. It’s now the actual count of people that will vote for a candidate. This implies that districts with more population is now harder to own (get at least 50% of voters).

Due to this change, we introduced the concept of Reputation Decay. A percentage of a candidate’s reputation in a district is deducted if the Candidate has no Staff stationed in that district. The message is that voters are fickle. They won’t vote for someone unless they constantly stick around, or the candidates give them money. 🙂

Raise Funds

We finally have this Staff action. It’s in the game design papers ever since. We designed it such that the more Reputation a candidate has in a district, the more money it can raise. That’s how it is in real life. People are willing to give you money if they like you.

Now players can use the people they've convinced to give them money
Now players can use the people they’ve convinced to give them money

Patrons

I had a direct hand in introducing this mechanic and I’m happy with it. Before this change, each district has a Kapitan which Candidates can have a relationship with (in a friendly way). The only effect it had was during elections. If you’re closer to the Kapitan, then people will vote for you in that district.

As a strategy gamer, I feel that the game doesn’t have much avenue in acquiring ‘things’ that generates resources, which I really like in such games. Mechanics like building an expansion in Starcraft to exploit new resources, building that Bank to generate gold in Civilization, etc. I suggested what if there are patrons or sponsors that players can court. They could be an influential family in the district, a business man, celebrity, or another politician. You gain some effects if you can get them to support you like giving you funds per turn, or slowing Reputation Decay.

Our game designer, Tristan, came up with Patrons. Kapitans were discarded. There are now 3 Patrons in each district. Each Patron has a distinct effect depending on a player’s relationship with such. One Patron had an effect when Raising Funds, another one for CP cost (reduced or increased), and last one had an effect when doing Sortie (increases or decreases the amount of reputation gained). A player can decide to make a good relationship with one or more of these Patrons using the Gift action.

Patronage politics at its best!
Patronage politics at its best!

Scandals

Everybody loves scandals… as long as you’re not implicated. Our political climate is rife with it, even during elections. I’ve heard in an interview with a local election campaign consultant that there’s this one politician who didn’t win but spent so much. He was running for Senator. When he was asked to compute his expenses divided by the votes he got, he spent around Php5000 per voter. The election campaign consultant then said “Imagine if he bought votes instead. That’s only Php500 per voter. He would have gotten ten times more votes.” Vote buying is a big scandal, but if you’re the one running the election, it could be very tempting.

Given such fact, the concept of Scandals is a vital mechanic in Party Animals. Of course the representation is rather simplified. Scandals in our game is just a number of scandalous acts that a candidate has done in a district. Actions like Bribe and Smear Campaign increases the Scandal Count. Other neutral actions like Campaign, Sortie, Gift can become scandalous (increases the Scandal Count) if a bigger amount of money was used to carry out such actions. If you didn’t know, COMELEC has a prescribed amount of election money to be spent. It differs per location and position. You can get sued if you’re found spending more.

Red means "scandalous"
Red means “scandalous”

At the start of the next turn, each “unchecked” Scandal are then “checked” if it is revealed or not. We are running a formula to this. If it gets revealed, the game imposes harsh penalties for the candidate on that district. The penalties are in the form of reduction of Patron relationship, Reputation and increased CP cost on the district. The higher the Scandal Count, the higher the probability of it getting revealed.

As simple as it looks, implementing Scandals gave us a lot of headache. There were a lot of design issues that we’ve encountered; there were some cases that we needed to consider. As of writing, I’m still working on the final touches of the mechanic.

The Tip

As promised, the tip I’m sharing is about how do I start my coding momentum. It may not work for everybody but it certainly worked for me. Programmers are peculiar creatures. They need to be in a certain state so that they can work productively. But reaching that state is hard because programmers must be working to reach it. It’s kind of like an “almost” chicken-egg problem. Reach that state to get work done but work to reach that state.

As I ponder upon this, I thought about working out. People hate it. It’s tiring. The time used for it could have been used for something else. To make things worse, the main benefit of working out is kind of an abstract bullshit: health. Then I thought of myself. I go to a martial arts gym but how could I do it? I know I need to do it but what really gets me to go there and tire myself? The answer is really quite simple. “I packed up my gym stuff.” Packing up gym stuff is easy. It doesn’t take a lot of will. But it starts there. Next, I go out and commute to the gym. While I’m at a bus, it’s already hard for me turn back and change my mind.

Back to programming work, I can ask the same analogous question, “What’s the least and simplest thing that I can do to start coding?” My answer is “write one line of code”. It works for me like sorcery. It might be different for you, so go find yours.

The Party Base Code

After implementing some of the basic features of the game, I could definitely say I’m now an official Party Animals programmer. There’s no turning back now. I’ve invested huge amounts of time, effort, and code already. Might as well make a blood oath that I’m going to code for this game until it is released.

Starting a code base is both challenging and exciting. I have to learn new stuff and unlearn some things that I used in my previous game. I have to reset my mindset that the project is still in its early stage. Lots of tools and systems are still missing. It’s unlike the code base of a built game where the systems are already in place and I have the thought process on how to change things. This time, I’m also not a lone programmer anymore. I have to take that into consideration.

In this post, I’ll show you what I’ve done so far.

Camera Settings and Resolution

I’d like my camera and 2D Toolkit settings to be consistent. I want the orthographic size of my cameras to be 1 because it feels more consistent rather then specifying some other number. It also helps with resolution independence. We’ve also decided to use 1366×768 as the base resolution. In short, I have to rip apart the current settings (sorry Julius). I’ve requested Ryan to resize the assets to make it suitable for the new resolution. 2D Toolkit sprite collections have to be regenerated. With this, fixing the positions and colliders of the districts was also inevitable.

IslandResized
Resized districts. Still used Julius’ clouds and wave simulator. They’re cool!

uFrame

Party Animals is a systems heavy game where game rules could change a lot. I’ve decided that I should incorporate some form of framework to it so we could at least have some structure to where code goes. Julius used StrangeIoC. Then I was able to buy uFrame because it was on sale. I found uFrame to be superior than Strange. So I had to rip apart the current code base (sorry again Julius).

I’ve got to say don’t buy this product if you’re not a programmer or even a newbie coder. It’s hardcore code framework rather than a utility extension like most other asset store products. I wonder how they sell this thing. Only programming nerds are excited by this.

I really like it, though. It forces me to adhere to MVVM and have some kind of structure and separation on where the appropriate code goes. It forces me to follow the rule that views should react to changes in models. Only controllers can mutate models. I had a really hard time understanding it at first. Data initialization is not that straightforward. I even asked dumb questions to their forums. One reply said “Ugh, awkward questions… but here’s what you do…” I’m starting to get used to it now. I’ve implemented the features so far using uFrame.

uFrame
Models in uFrame are code generated. They are authored like this.

Staff Movement

The Staff and Districts are the main movers of the game. Obviously, these two had to be implemented first. The first action I’ve done is movement. Things have to be implemented a little different when using uFrame. If I had done it like I always do, I just move the staff avatar then change its current district. Not anymore. In uFrame, you have to go through a controller. I have a command called ChangeDistrict() which updates the current district in the model. The avatar (view) has been bound to the current district. It is notified whenever the current district changes. When it does, that’s the only time that I could move the avatar to the new district. See the difference there? The direction of execution is always Model changed then View reacts to it, not the other way around.

Staff Campaign and Unity UI

Party Animals is so UI heavy. I haven’t played with Unity UI yet because Warrior Defense’ UI was still using 2D Toolkit. I have no escape now. Julius is using it and highly recommends it. I hate to say that I do like it after trying it out. RectTransform is freaking awesome! I hope it won’t bite us later. I’m still not sure how to go about atlasing, hi-res assets replacement, and draw calls.

Campaign is one of the basic Staff actions. This action has a lot of parameters so I decided to use a uFrame model for it. I’m glad I did because I learned a lot of the uFrame flow when I implemented it. The major one is UI catch cases. There were lots of these. Since I have to implement in uFrame mindset, working around it is also very different. I always say “update model then UI, update model then UI…”

My first complex uFrame and Unity UI combo!
My first complex uFrame and Unity UI combo!

Generally, I’m happy with the base code right now. I’ve got two basic actions implemented. I now have prior knowledge on how to implement the next ones. Can’t wait to show you minimum playable version of the game!