The following is a blog by our programmer Marnel, talking about AI in a strategy game.
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:
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.
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:
Single agent systems just can't answer these questions. I had to look for other ways.
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.
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.
Thanks for reading. If you actually do have a suggestion for Marnel regarding AI please comment here or email him. If you want to be up to date on the latest Political Party Animals news, please sign up for our mailing list.
 |
| Our AI in action |
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:
- 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.
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
 |
| Sample code |
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:
- Generate all possible tasks
- Generate all possible assignments (all possible agent-task pair)
- Assign a score to each possible assignment (this is based on game rules)
- Sort possible assignments by score in descending order
- 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.
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 ants. 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.
Thanks for reading. If you actually do have a suggestion for Marnel regarding AI please comment here or email him. If you want to be up to date on the latest Political Party Animals news, please sign up for our mailing list.
