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.

One AI is Easy, but FOUR?!?!?

I have implemented my own FSM and Behavior Tree systems for AI in games. I know how to properly use them in most cases. They’ve worked really well. I honestly think I already have the working knowledge for the AI of the kind of games I’d like to make… until Party Animals came. I felt stupid and incapable.

FSMs and Behavior Trees are good for single agent AI. Single agent here means that the simulated behavior is only responsible for itself. It doesn’t see other agents and try perform tasks together more effectively. For example, let’s describe a single agent behavior of an enemy unit guarding a gate:

  • Unit stands still near the gate
  • If it sees a player unit within its range,
    • Chase and attack that player unit
    • If player unit dies or goes out of range, go back to gate

Now let’s say we assign two enemy units on that gate with this behavior. It will still work but probably not the best strategy to defend the gate. Both of them will chase the target as soon as it sees one. They could have decided that one of them chases the player’s unit while the other one remains on guard. This is no longer single agent. Multiple agent behavior is another beast with its own set of complexities.

AI vs AI in Action!

In Party Animals, a player controls 4 units. They are called “Staff”. One is the candidate character himself and the other 3 could be any combination of Police, Accountant, Investigator, PR Manager, or Goon (we’ll add more). Each staff has a common and unique sets of abilities. The game is turn based. Each Staff can execute one action and can also move to an adjacent district once in every turn. The player may choose to move then execute an action or execute first then move to another district for each staff. Aside from this, the player also has to assign budget for each action. The budget allocated affects the effect of the action.

Here’s the college project: implement an AI opponent that controls 4 Staff units that should pose a challenge to the player. It may not play the best moves, but should at least be smart enough to pick and order its actions sensibly. Sounds easy? (If yes, email me your solution please.)

I think the main difference between single agent AI systems and multiple agent AI ones is the concept of planning. There’s no planning in FSMs or Behavior Trees. You can simply pick which branch to choose based on some conditions and let the agent perform the behavior described in that branch. You can’t simply pick a branch of behavior for a multiple agent AI. There are questions to be answered before letting agents do their tasks:

  • Are the agents assigned the best task for them in the current situation?
  • Is the order of execution of agents’ tasks give the highest benefit?
  • Are the selected actions sensible enough in the player’s perspective? Is the AI playing the game right?

Single agent systems just can’t answer these questions. I had to look for other ways.

Solution 1: Genetic Algorithm

I love brute force solutions. A genetic algorithm could certainly be used for Party Animals. Since the game is turn based, there’s no pressure for the AI to run as fast as possible. I don’t need the best answer either. I was thinking that I could run 1000 generations for each turn and select the best gene as the set of actions that the AI would take in that turn. In the end, I decided against it because I’m not so sure how long 1000 generations would take. I mean sure the game is turn based but we don’t want the player to wait too long for the AI to execute. The chromosome encoding/decoding itself would take too much time to implement as there are lots of possible actions. The fitness scoring would be quite complicated, too. There are lots of variables to consider.

Solution 2: SHOP Planning System

Here’s the link to the paper of the algorithm. It looks simple but I’m not quite sure how to implement it. I don’t even know if it’s a multi agent solution. It’s more like a distant cousin of GOAP.

Solution 3: Resource Assignment Algorithm

I found this one in Gamasutra. I liked this one because it’s really easy to understand and convert to code. It’s very straightforward. I implemented it as soon as I understood it. The current AI actually uses this solution. The algorithm is somewhat brute force but wouldn’t take as much time as in Genetic Algorithm. These are the major steps:

  1. Generate all possible tasks
  2. Generate all possible assignments (all possible agent-task pair)
  3. Assign a score to each possible assignment (this is based on game rules)
  4. Sort possible assignments by score in descending order
  5. Assign tasks to agents from the sorted possible assignments until all agents has a task

The hardest part of this solution is step 3. There’s no one rule how to compute the score for each task. It highly depends on the rules and the current conditions of the agents of the AI. In a way, you’re like turning the quality of a task that is to be assigned to an agent into a number. This value should at least be comparable for all types of tasks since they are all treated the same way when sorted in step 4. Coming up with these computations is not easy. I think I need to study a special math for this.

For instance, the Campaign task has various factors like population, the platform value of the candidate, the concern value of the target district, and the distance of Staff that will carry out the task. Another task called Gift has another set of factors. These are population, inverse of platform value of the candidate (meaning the lower the value, the more likely the task should be done), and distance. Campaign has 4 factors while Gift only has 3. How do I come up with a formula or system of scoring such that it gives reasonable values among these two tasks? There’s also the case of precedence. Campaign should be a more important task than Gift but because it has more factors, it could happen that it has a much lower score. The scoring system should be able to compensate for this.

Resource Assignment main function
Resource Assignment main function

Solution 4: Dynamic Task Allocation

This is a lengthy Master’s Thesis material. I did not understand it the first time I read it. I learned to appreciate it when I ran it through again. It’s actually very clever. The algorithm was inspired from swarm colonies like ants, bees, and wasps. It turns out that colonies don’t have a central command that assigns tasks, not even the queen. How does the colony know which tasks to prioritize then when certain circumstances arise?

The individuals of the colony emit pheromone stimuli. Larvae emit pheromone to signal their hunger, sentries emit pheromones to signal intruders, etc. Each caste in the colony has a set of thresholds associated to each stimulus. When a stimulus becomes greater than an individual threshold, that individual will answer to that stimulus with great probability. Answering to that stimulus will in turn lower the stimulus. For example, worker ants would have a low threshold for a task say “gather food” but has a high one for “defend colony” task. This way, worker ants will respond to hunger stimuli more than to intruder alert stimuli. You can probably imagine by now what a soldier ant’s threshold values looks like.

I would have used this algorithm had I understood it earlier. I was almost finished with the implementation of Resource Assignment Algorithm. I could not afford to tear it down and start again. We need a working AI soon. Either way, I could still add this algorithm in another AI profile in the future, if there’s still time.

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!