AI War:AI Design

What Makes The Design Of This AI Unique From An Under-The-Hood Perspective?

Q: So I've heard that the AI here is something new and different, but I'm wondering what the high points of this explanation are?

Response from Chris Park, AI War's Lead Designer:

This explanation is geared more towards AI programmers and those familiar at least to some degree with AI. For a more concise, brief explanation geared towards non-AI programmers, please see part 1 of the series of longer articles I've written on my blog. So, in no particular order of importance, but in an order that hopefully makes them easier to follow as an explanation here:

Extremely hybrid nature: Not using any one particular approach, so the system has highly emergent aspects as well as very procedural aspects, as well as more traditional AI aspects.

Not Trying To Create True AI: Perhaps this is obvious for most real game AI programmers, but a lot of AI books and articles seem to indicate that game and truly sentient AI are in some way related, whereas I feel like they are (at present) not at all related. This was a core design decision for my approach, to never try for true intelligence, but just to do everything I could to simulate the effect of true intelligence by whatever trickery was best suited at the time.

Procedural world population: Maps are seeded based on a variety of factors, including map style (4 in the base game, more coming in expansions), AI types (26 in three difficulty tiers in the base game, more coming in expansions), the enabled ship levels (three complexity tiers) and ship types (players can disable certain types of ships that they might find too difficult or annoying, given their playstyle). This procedural population is nothing amazing, but uses a lot of very simple interlocking systems to create variety and complexity. For example, procedurally seeding where "upgraded" AI planets are, where special capturables and AI special weapons are, etc. The population of individual ships is based off of purely random selection from sub-groups of ships by level or function (turrets, mobile ships, mines, etc), which leads to different results than a pure-random algorithm.

AI Thread On Host Only: The AI thread runs on the host computer only, and issues its commands as "game commands" in the same way that a human player's commands are issued. Thus the AI logic can be on the host only, which lets single-core clients run the game with the best possible speed.

No Significant AI Memory: The AI is built around being able to come to the board clean, with no historical knowledge, and make intelligent, interesting decisions. The reasons for this are several -- not increasing the size of save files is the main one, but also letting a client or a host save the game, when the client's don't have any of the AI decision data present on their machines, is another one. Not using historical data as a guide also allows for the AI to react to changing situations more quickly.

Tier 1 of 3: Central Intelligence: There is a main processing loop on the AI thread, which gets messages and updates from the main thread and then takes actions as needed. Some of these include scheduling defensive reinforcements or offensive waves, triggering the individual-unit tactics, or expensive decisions for non-combat decisions (such as pathfinding for "astro trains" and similar).

Extremely Random Offensive Waves: AI War is part RTS, part 4X, part grand strategy, and part tower defense. The tower defense angle comes in with the offensive waves of the AI, which are announced in advance and which show a countdown timer to their arrival. These waves are only allowed to strike at planets where certain conditions (that the players can affect) are true, but from that available list of planets the AI chooses completely randomly. The type of ships it sends is also completely random. My reason for making this completely random was that oftentimes this can result in really surprising situations, and when the AI comes in and is completely overmatched, it will then try to escape and do something else more valuable, if it survives.

Tier 3 of 3: Distributed Unit Intelligence: There is no overall coordination of individual units. As in, they make no effort to move in groups, though they frequently will. The units individually use a sort-based algorithm for determining optimal targets (previously using LINQ, but now just using raw sorts), and add a fuzzy-factor to that. However, they also weigh how many other ships are attacking a given target as part of their logic, so that can make them subdivide and group in certain ways to take down targets as efficiently as possible.

Tier 2 of 3: The Missing "Agent" Controllers: From what I have read, most RTS games have agents that are in control of various groups of units, and manage them as a whole. This was a bit incompatible with my goal of having the AI not have any significant memory, and in general the concept would have introduced a lot of complexity that I did not feel was beneficial. Instead, by having the third tier, above, give some weight to what peers are doing, I was able to simulate n number of "agents" that dynamically subdivide and combine as the changing situation warrants. Thus the end effect to players is that there seem to be these sub-commanders present based on what the ships do, but it's a lot less predictable. If you've read Ender's Game, think of how Ender's troops acted, with splitting and merging as needed, versus how the fixed platoons of his opponents acted.

Planet-Based Decisions: AI War is divided into anywhere from 10 to 120 separate planetary battlefields. All of the decisions that the tactical-level AI makes are based on the current planet only. This makes it so that the AI agents have a certain level of desirable myopia, which lets them be surprised by incoming player actions or which lets them fall into traps on adjacent planets. This feels very realistic. However, it also has many benefits for CPU load, as well as for letting the AI make "planet-wide" decisions, such as: we really outnumber the player, let's go for the throat; or the player really outnumbers us, let's run away.

"Escape And Try Again" Behavior: The AI ships will stick around for at least 30 seconds on any planet, which gives them time to get their bearings and for imminent incoming AI ships time to arrive. However, if they later realize that they are heavily outnumbered, they will retreat. When they retreat, they go to a random AI-controlled planet that is 3-5 hops away from the current planet. Once they are then to their destination, they will turn around and choose a new player target, largely at random. This makes for a huge amount of uncertainty for players, and the randomization of where the returning AI forces will be coming from as well as where they will be going, makes for a lot more simulated realism, too.

Avoiding Trees: Decision trees have the drawback of being very linear, even if they are branching, unless there is copious use of gotos or other constructs that make understanding the program harder. My database background led me to use LINQ instead in these situations, and later I optimized this to just using raw sorts. The idea is that you can have incredibly complex and deep pseudo-trees, with much cross-use of code that would normally be duplicated in far-down branches, simply by using sort-style logic. Pairing this with some very simple one-level if-else branching for multiple sort algorithms leads to even better results.

Using Agent Differences To Create Complexity: There are over 30 different major ship classes within AI War (with 4-5 levels of ships in each), not counting the 80 or so turrets, starships, warheads, and specialized defensive/economic/capturable ships. A subset of these ship classes and other specialists are in any individual game, of course (perhaps 20% to 40%, depending on the game and the number of players), but this is still a lot of variety. This is relevant to the AI! Each ship has different other ships that it is best against, and so it will make different decisions. When you add all of that together, with fuzzification on top, this is where the emergence really comes out the best, because players see a net effect that is seemingly divorced from the relatively simple behind-the-scenes logic that powers it.

AI Reactiveness: The AI in AI War is not a "learning AI" by any stretch of the imagination. However, in many ways the end effect is somewhat similar to a learning AI for players, because as the players grow in skill, the AI behaviors notably change. This is because the players are creating different "board states," to use the Chess term, and that causes the AI to evaluate the situation differently (and then apply its fuzzy factor to that new situation). It's sort of an arms race -- players see the AI doing some activity, and think up a clever new response to that AI activity. The AI sees the new board state and changes its behavior in response, rinse and repeat. Paired with a very heavy fuzzy factor (no more than 50% chance of any given behavior, if that, on average), this leads to AI that is far less predictable than most other systems.

Players Anthropomorphize: Obviously, this is a well-known fact and something that all AI developers rely on. The players see purpose and intent from AIs where often there is none, and AI War is no exception. However, I think I have found a way to maximize the effectiveness of this anthropomophization. Players tend to start seeing "the man behind the curtain" once they learn to predict AI behavior. By having such a huge fuzzy factor, and having the AI be so reactive to player actions, the AI always seems to be doing something a little bit different. Even for players who play for hundreds of hours (and there are players in the core community who have played at least that), there is a tendency to anthropomorphize intentions. I think the value of this cannot be underestimated when discussing AI that seems really intelligent to players.

NEVER Code The Best Choice In: This comes back to my classic "gap in the wall" exploit (my play group is expert at exploiting RTS AI), but also relates to the retreat behavior in AI War. In AI War, ships retreat through a random wormhole, rather than choosing the least-defended one. The least-defended one would make them predictable, and would let players lay traps that would be all too effective. With the random approach, traps are largely ineffective. The drawback is that sometimes the AI War ships will make a mildly stupid decision, such as impaling themselves on defenses on one wormhole, when there is another wormhole that is undefended, but sometimes this surprise factor can lead to unexpected benefits, anyway. In general, try to find the pool of almost-best choices along with the best choice, and choose randomly from them in order to keep players on their toes. Often when a slightly nonideal situation is seen, the temptation is to "fix" that by making the AI use the ideal choice, but the predictability this causes allows experienced players to exploit this to a heavy degree. Resist the urge to over-fix!

Minimizing AI Opportunity Costs Through Game Design: In general, since I'm the designer/programmer of the game as a whole, as well as of the AI, this gave me a lot of flexibility to set myself up for success with the AI. If some aspect of the game design was bad for AI, I would change it. Activities that have a high opportunity cost (such as expensive one-shot attacks, or very expensive ships that gain value over time and should be protected, etc), were generally something that I avoided for combat in the main, as this had a much smaller pool of almost-best choices. Anything that had only a few ways to manage it, or which requires a lot of hand-holding to use correctly (ala warheads) was something that I made player-only, while the AI received its own AI-only ships that are geared towards a larger decision space. In your traditional RTS, this could manifest itself as having specific AI units that replace the units that the AI is not good at wielding. This negates the role of the AI as a true player standin to some degree, but carries many benefits.

Skipping The Economic Simulation: This is something I have written about at length, and suffice it to say that some AI programmers might find this a distasteful decision for various reasons, but I don't want to bog down the entire discussion on this one aspect. Suffice it to say, I decided to not have the AI go through the same player activities regarding the economy, because they were complicated and carried many high opportunity costs in most cases, and most of these decisions are not visible to the players in the first place (players are never sure if the AI is "cheating" on its economy when the AI does well, since the players can't watch the AI while it builds up). So I decided to short-circuit that entire process and just populate the AI's economy based on simpler rules entirely divorced from the player, which scale up with the difficulty to simulate smarter AIs in this regard. No players have had an issue with this, and they remain impressed with the tactical AI, which plays completely fairly.

Giving Players The Tempo: In AI War, in order to include aspects of grand strategy, one big part of that was letting players set the tempo to some degree, and make long-term decisions that they then carry out and adjust over the course of hours-long games. By having capturables and AI planets largely be populated at the start of the game, this lets players choose plans. Similarly, letting the players affect how AI planets reinforce based on a visible "alert level" on AI planets, gives players some feeling of control over their immediate environment, and makes for interesting decisions to the players. AI's reinforce their planets periodically based on a weighted random algorithm based on various factors such as if the players are nearby, if the planet is being attacked, how many AI ships are already on the planet, if the planet is highly valuable for defending (such as home planets), and how many alerted planets there are in general. Thus there is some degree of intelligence in how the AI reinforces, but it's not very dynamic except in response to player actions. This makes reinforcements largely pretty predictable in the main, which is actually a good thing as it relates to player planning. This aspect helps players feel a bit more in control.

Bounding Intelligence: Similar to the above, there are other rules on how the AI is allowed to use its various ships, and this helps players feel in control while challenged at the same time. The AI starts the game outnumbering the players 10,000 to 1 (literally), and so if all of those AI ships just ran at the player, the game would be over in minutes. Instead, similar to who line of sight is simulated in other genres of game, the AI awareness and interest in the players is simulated here. That is partly via the AI Progress, which increases the AI's technology level and aggression based on player actions. But it is also partly based on varying rules for the AI ships (see below).

AI Ship States: AI ships are all in one of the following modes: Guard, Special Forces, or Free. Ships that are Free can act however they want, traveling between planets, retreating, attacking, etc. This is the full-blow tactical AI, but is not used for the majority of AI ships at any given time. Most AI ships are generally in Guard mode, where they are tied to a radius around a specific guad post. They will act fully intelligently against any player ships that come into that area, but they will not leave that area. They become Free if the guard post is destroyed, or sometimes if the player takes control of the planet on which their guard post resides. Ships that are in Special Forces mode are mobile, and just travel around the galaxy at random. When they would enter player territory, they group together before going over. When they encounter player ships on any planet, they become Free. There are some other more minor modes, but these are the main ones and they provide enough overlapping complexity with the other subsystems already mentioned to provide a good balance of the players feeling like they are in control, while also not knowing what is coming next.

How To Simulate 30,000 Ships: Many of the AI War games actually reach more like 60,000 ships. The keys to making this work are subdivision -- having the various ships be spread across multiple planets makes it somewhat like quad trees in other games -- and revolving minimizing or scheduling calculations. The game only calculates target acquisitions for 1,000 ships per second, for instance, and has similar scheduling for collision detection, which has a bit of a different meaning in a 2D game that is in pseudo-3D space (where ships can pass each other because they are presumably in different Z-axes, even though that is not shown). Additionally, having all of the heavy lifting of the AI be on a host-only separate thread really lets it do anything I need, intelligence-wise. If a process is really long and slow, and takes several seconds in order to come to a good decision, that's no problem because it doesn't slow the simulation (and, reasonably, an AI that reacts within several seconds is still as fast or faster than most players... and the AI generally has sub-second response time on most machines, anyway, even with all the heavy lifting).

Delegation: Part of mitigating the complexity of managing so many ships for players is a fair degree of automation. Having all parts of the game do a pretty good job in the players absence basically lets the players delegate when needed, and micromanage when they are inclined. Micromanagement generally gives a better result, but having intelligent automation makes it so that micromanagement is not required. This is similar to a lot of games, including turn-based ones like CivIV, where I can manage cities to a very detailed degree, or let them do "pretty good" in my absence. Having a system like this in a realtime game forces players to consider the opportunity cost of any micromanagement that they might undertake, since other systems are getting less attention while they do so. This lets expert players really perform a variety of actions while intelligently weighing where their time would best be spent, and it lets less-expert players just focus more on the parts of the game that they like. Some detest detailed management of the military or the economy, and this sort of AI-assisted setup allows them both to schedule activities to follow a certain path, and to otherwise just focus on the parts that they really enjoy. Having various options such as Attack-Move mode, player-set waypoint paths, Free-Roaming Defender mode, looping queues, all contribute to this "set up and forget it until later" mentality.

Auto-targeting: Auto-targeting is one big part of the delegation, since ships need to do a good job in the absence of player attention. Often players are being attacked on multiple fronts at once, so this is non-optional in the design here. The auto-targeting uses similar logic to the AI target selection logic, only without the fuzzy factor and with ships always choosing the absolute-best target whenever possible. Thus players can predict the outcome of a battle based on the ship mix, if they were inclined to. Players can override some of this by setting preferred target types for groups of ships if they want to fine-tune this, which many expert players prefer to for any given situation. Ships that are out of range of their primary target will fire at any other ships that are within range as they move to their primary target, so even for AI ships this sort of logic comes into play. The auto-targeting is one of the most CPU-intensive parts of the main simulation thread for the game.

For more information: If you're looking for yet more information, I've written about the AI at great length in a series of articles on my blog.

AI War:AI War