Turn based games like this live and die with the quality of their AI – Specifically the AI which guides the non-human controlled entities in the game. The code needs to know where to place an entity and what it will do to help it achieve victory. Games would not be as fun if all the enemy entities just moved around randomly! We need to make sure that a human player has a suitable challenge. For those interested, I thought I would take a delve into what it looks like under the hood.
Modules, Features and Weights
The basic structure is a bidding system between ‘modules’. These modules can represent a tactical choice that an entity may make such as ‘Attack’, ‘Purchase’ or ‘Capture’. The module details the steps that an entity will take to fulfill its particular tactical goal – for example for the ‘Capture’ module, it may have a move action to get into position, chained with a capture action to perform the actual capture.
All modules have a collective pool of features which it will use to determine what actions to plan and how effective that action would be. These features are shared across all modules but are weighted differently. For example, the ‘AttackEffectivenessFeature’, which gauges the value difference of performing an attack, the attack module would care a lot about; whereas the capture module does not really care about as it is not planning to attack. Another example such as the ‘PathedClosestProximityFeature’ which can determine for example how close an attacking enemy is, the attack module would care a lot but the capture module would also care about as it wants an interrupted capture. These will all have different weightings in each modules configuration.
- Module – A general tactical option that an entity can take e.g Attack, Capture
- Feature – A specific thing to consider when making a plan e.g Proximity of enemies
- Weight – How much each module cares about each features
Bidding
During each step of the AI turn, a round of bidding commences. Per entity, each module puts up its bid depending on how effective it things its particular action will be. We then take the winning bid over all modules to select the winning module, which itself contains the specific actions that it wants the entity to perform.
This bidding process actually includes multiple entities as entities can be used in any order. The highest bid over all entities therefore is what wins, and the winning entity will perform the actions as defined by its winning module. If an entity still has possible movements after it has done its actions, it will return to the bidding process and the bidding starts again. If an entity has ended its turn, it will be done and simply will not take part in any future bidding for the turn.
How are actions determined
We have discussed how the winning module and actions are determined, but what are these actions and how do they get created. This is slightly less ‘neat’ in that it is very determined by the specific tactic being considered.
An easy example to visualize is the Attack module. For the most part, this considers all possible positions that an entity can move and attack from, and considers the best attack to make against which enemy.
Considering a specific position, we can sum the calculate weighted result of each features:
A worked example of this could be the ‘PositionDefence’ feature. The attack module would care about this so the featureWeight would be large. If a position had defense which would help the entity on it then the featureResult would be increased. The total contribution for a high defense position for the attack module would therefore make a large contribution to the overall effectiveness.
Features come in all shapes and sizes and are not always as clear to fully calculate as a human – that is why delicate weighting is important. For example, the ‘AlliesCanProtectByAttackingAdjacentFeature’ considers if an attacking unit will be left on its own or if on the following turn if it gets attacked there will be allies around to counterattack.
There will be features which are positively weighted and also some which are negatively weighted (for example, the Capture module does not want any enemies near it to interrupt its capture so will favor capturing things outside the enemy’s range). All get calculated and we get our overall effectiveness for that position.
Some features will be very specific to the position i.e the defense is very position determined. However, some lead to other outcomes such as attacks possible after a movement, which enemies to attack when actually performing the attack action, enemy and own team entity compositions etc. There is an exhaustive list but as much as possible is considered to find the best effectiveness.
Now, the attack module has calculated the effectiveness at each position, it can select the position with the highest effectiveness and the corresponding attack with the best effectiveness at that position. With this information, the module can then go off an plan its actions which fit in to that position i.e a move and then attack.
This is the general process of a module but of course each is a bit different and most importantly the weighting of each feature will be specific to the module. Currently there are around 30 different features available and more are being added as the game develops. In principle, the more features to consider the better. There will be a diminishing return on the features weighting as they become more specific and situational but as long as its something that a human would also consider, its valid as a feature for the AI to also consider. This leads us to one of the limiting factors for this AI…. Performance!
Performance
In a perfect world, the AI would consider anything and everything to achieve its goal of winning (at least until it gets too good and we need to make it dumber for us humans to win!). So just keep adding more and more features right?
Yes and no. Consider the AI turn when it needs to take the turn of a large number, lets say 100 entities. Each of those entities has several (5 lets say) modules that it can consider. If each module has a large number of features, lets say 100 then for each bidding round, there will need to be around 100*100*5=50000 features to be calculated. That number is pretty arbitrary but just as an illustration, that’s a lot of feature calculations!
Each feature is by design moderately lightweight and focuses on a specific thing. This allows the weighting to be performed in a pure way and there are not ‘hidden features’ which could arise when a feature takes into account too much and some sub-features could be consumed by the overall design. However, even with this some complexity cannot be avoided. For example, calculating entity movement pathing over multiple turns (in principle as many turns as it takes to be able to reach any square of the map) is needed for many of the modules. While some caching/sharing of calculations between the features has been achieved, when an action such as an entity has moved then a good chunk of it will need re-calculating.
This is a live game such that each bidding process needs to take less than say 100 milliseconds or a user would notice a certain amount of sluggishness and have to wait for the AI turn to complete. There are animations which happen such as movement and attack animations but ultimately I want the AI to be snappy enough so that we could have a quick mode if the user wants to disable much of the animations. Indeed, a story for another post, but we have an AI training harness where battles are simulated thousands of times in parallel with the features tweaked to see if the AI can be improved also relies on a quick AI or training would take much longer.
Overall, you can see that performance considerations are crucial to the AI development process and each feature is evaluated to see if any corners can be cut or make the determination in the most efficient way possible.
Final Thoughts
The AI system is by far the part of RT that I am most proud of and one of the most fun and most frustrating thing to develop. Adding new features in isolation and testing them is a relatively simple process. Finding the correct weighting can be tricky but is incrementally getting better. Its the bizarre thing that its virtually impossible to trace back exactly why the AI did a thing that they did due to the total complexity the mass of features, modules and weights, but that it is making very sane choices that I, as a human, would also have done!