Tag: AI

,

  • AI dive in

    How does the AI work under the hood? Lets have a dive in!

    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!

  • Show off – Purchasing, Capturing and AI

    A speedy demo of the Hacktics game mode showing off some of the latest features

    As things progress, its hard to capture all changes in a single illustration. So here is a lightning example of two AI players battling over a network (hacktics game mode):

    The Hacktics game mode is all about capturing ground which generates more income which allows more expensive units to be purchased. This mode uses the ‘network’ concept such that only continuously connected captured locations generate income. Therefore it is possible to cut through an opponents network and disrupt their income. As you can see, the AI occasionally purchases additional units from one of its construction buildings.

    There are 3 units available:

    • Workers which can capture network but not attack
    • Viruses which have a direct attack
    • DDOS which have a range attack

    Each unit has a different cost and although not very visible in this video there are 3 different currencies at play. The more expensive units using the rarer currencies. In addition each location generates a different amount of income – the two ‘generator’ locations for example generate a high amount of the rarer resource.

    It takes a worker 2 actions to capture a location and the worker has 2 actions per turn. This leads to the ‘ability’ config where each type of ability that any entity can do can have associated ability config – detailing how many action points each ability costs, if it can be used multiple times a turn, if it ends the entities turn etc.

    The AI in this scenario acts reasonably intelligently (currently no training has been performed so not bad considering!). It understands the concept of the network and attempts to capture continuous locations in order to expand its income. It also attempts to purchase the most useful units it can given its current wealth. The units also attempt to engage intelligently and cause damage with an aim to get the best attack value while preserving themselves.

    Note that each entity in this scenario have direct attacks although other forms of attacks are available which have been experimented with – in particular splash attacks which causes damage to multiple units at a time.

  • New game modes!

    A visual example of a new game mode currently being added

    With the alpha version of the game pretty much complete, new game modes are being added as the ‘content’ of the game is only a couple of maps currently. The most recent is the ‘Medieval’ game mode which is a classic style of traditional warfare with swordsmen, archers and catapults etc.

    Here is a demo of the gameplay from two AI players battling. It is just a few units put on a map and no interesting terrain yet but just an illustration of what is possible.

    These are sample graphics and only a few units added so far but it does show the power of the engine as this was achieved in a few hours. More impressively the AI is not half bad considering that it is currently still completely untrained and has not been altered in any way for this game mode!

    It is so easy to add new game modes using the configuration system and achieving this is pretty straight forward when you get a grips of the structures of the configuration files.

    Also another disclaimer is that the timings of the AI turns are a bit quick and currently the units effectively throw particle effects at each other (which can land when the unit has already been registered as defeated!). All of these are just things that I have not got round to improving yet!

  • How to make an enemy – Giving the enemy some brains with artificial intelligence (AI)

    Making the enemy intelligent is no easy task. The complexity of the final game will be a real challenge to make the enemy both tactical and adaptable to be an enjoyable opponent.

    I do love the idea of being able to play against human opponents. However it would also be great to be able to play the game against non-human players. Therefore an AI system will need to be created. This… how shall I put it…. will be extremely difficult. Obviously a lot of games have AI systems. Most games the AI can seem relatively complex but are actually made up of lots of individuals following simple rules that overall create complex outcomes. There are exceptions such as real time strategy games where the AI is complex but can very much make or break a game. For strategy games, if the AI is not clever enough, random enough and adaptable enough it can severely damage the gaming experience. Every time the AI does something non-human or particularly stupid, a player will learn how to replicate that situation and start exploiting the AI and ultimately break the gameplay.

    Moving back to this game, a turn based strategy game with multiple entity types and actions that each entity can perform. Games like chess it is possible to effectively simulate a bunch of possible moves and construct a decision tree, finding the best move to make based on the most favorable branches. In principle it would be possible to do the same for this game except for one thing – there are way too many possibilities. If there is an entity that can move 1 space, there are 4 possible destinations. If they can move 2 spaces, there are 12 possible spaces. 3 there are 24 spaces, 4 there are 40 etc. This is a situation that can easily get out of control when you have a lot of entities that are relatively mobile, not to mention all of the possible actions that can be taken (attack, capture etc). Considering I am wanting this to run on a phone in real time, that is very much off the table.

    So there has to be a more restrained solution where it figures out a subset of possibilities. The solution which I have come up with and currently exploring is adding ‘Features’ to a ‘Heatmap’. During an AI turn, the system will loop over all entities on the AI team and will calculate features and add them to a heatmap. Once all of the features have been calculated, the ‘hottest’ square of the heatmap is proposed, escalating to the next if the move is invalid.

    As an extra layer of abstraction, there will also be the concept of separate ‘Modules’. A module is a collection of features which link to a particular tactical decision that an entity can do. For example the ‘Attack’ module, a feature could be ‘Is enemy entity in range’ or ‘Is attack cost effective’, whereas a ‘Capture’ module feature could be ‘Distance to enemy headquarters’. Each module will calculate its best square on its heatmap and bid for its associated action to be taken.

    This will leave a hierarchy:

    • Modules which define a particular tactical decision (attack, capture, run away etc). Each module has multiple Features and a resulting action.
    • Features which are calculable values for each entity in the current map configuration. The collection of features for a module added are calculated at each position on the map, summed and added to the modules heatmap.
    • Heatmap The map grid which collects the features for a module. The best position can be found which dictates both the modules resultant action and the bid – The modules reckoning as to how effective its action will be.
    • Resulting action will be performed by the module if it wins the bid. It will move the entity to the best heatmap square and perform the modules action.

    For example, the Capture module will have a feature to capture the enemy headquaters. The best position on the heatmap will be the position closes to the enemy headquaters. If the capture module wins the bid, it will move the entity to that position and if it has reached the desire square then captures the enemy headquaters.

    The specific modules and features will need to be somewhat manually defined from experience but down the line it may be possible to train the relative weights of each feature. In theory with enough features and weighting, it would be possible to have a learning system but that is very much down the line in the distant future.