The 2013 reboot of fighting game Killer Instinct on Xbox One has proven a popular game in the modern e-sports arena. While it successfully revives the long-dormant franchise from the Super Nintendo and Nintendo 64 era, it also introduces a new approach for fighting game AI. One that could revolutionise practice towards developing non-player character (NPC) behaviour in the genre.

The Shadow Mode system — a free update released in season 2 of Killer Instinct in 2015 — allows for players to construct AI-driven fighters that are designed to match your own capability when playing as a given character. After spending three training sessions in the dojo, your shadow AI is capable of replicating a portion of your behaviour: with many of your strategic decisions being mapped to the non-player character. Once established, your shadow can be sent off to fight your friends or other players on Xbox Live. Perhaps more interestingly, it can act as something of a training tool, given it exposes flaws in your own fighting style and allows you the chance to reflect on your attack strategies. Fortunately, your shadow can be updated over time, with the opportunity to add data from later battles into the AI model that builds your shadows decision making system.

So in this article (and the video above) we take a look at how it all comes together: the AI techniques used to deploy it and the inspirations that drove it. But before we do that, we need to talk a little about complexity of the problem this is trying to address. For those unfamiliar, fighting game strategy is actually rather complex, but the methods used to deliver fighting game AI seldom reflect that experience.

A Word on Fighting Games

Fighting games are typically built on multiple tiers of mechanics: ranging from basic movement, to the introduction of special attacks and combos. The template set by Street Fighter II has since been adapted over the years by pretty much every successful 2D fighting game franchise, such as Mortal Kombat, King of Fighters, Samurai Shodown, the Capcom Vs series and of course, Killer Instinct. The subsequent strategies that emerge are often highly contextual, as we need to think not only about what our opponent is doing, but also what we want them to be doing in order to do maximum damage.

This introduces a number of high level strategies such as:

Now much of this requires fast and fluid response to the game environment, with most players responding to game signals at around 12–19 frames in a 60 frames-per-second game. A big part of playing fighting games at a competitive and professional level is to be able to minimise that response time as well as build your understanding of how you will respond to changes in the game: the ability to plan ahead, anticipate player action and react to enemy behaviour. This establishes fighting games as something akin to speed chess: with the risk/reward of the current setup being re-evaluated on a per-second basis.

Now the truth is that most AI implementations in fighting games don’t really replicate that level of strategic complexity. In fact most of their actions are built as reactive agents where in the event of a specific player action, they will respond using a series of pre-built macro’s: executing multiple actions in sequence in order to achieve a desired outcome

These macros are accompanied by a number of individual variables that dictate the response rate of the system itself. Block frequencies, block and counter accuracy and time to execute specific actions or action macros are parameterised. As these frequencies and accuracy are reduced, we establish ‘easy’ fighting game AI, which is often rather stupid and fails to respond to player behaviour. Meanwhile expert AI systems are often a subject of frustration given their perfect blocking and counter reflexes. This often leads to cheap and frustrating boss battles in fighting game arcade modes, such as Gill from Street Fighter III, Shao Kahn of Mortal Kombat and of course Eyedol from the original Killer Instinct. In these instances, players need to exploit weaknesses or gaps left in the AI’s behaviour in order to defeat it.

Ultimately, a high-level AI fighter doesn’t fight like a human does: what it gains in block and counter accuracy it lacks in any intelligent or nuanced strategic decision making. This is rather ironic given the meta-game at e-sports level is the long-term strategic play in each round or match. Previous efforts in other fighting games such as the Amiibo fighters in Super Smash Bros. or the AI training mode in Virtua Fighter 4 still adhered to the parameterised template. But in this case, shadow mode aims to fully replicate your fighting style on a per-situation basis: very much adopting the ‘Drivatar’ approach from Forza and applying it to fighting games. Given the shadows are stored online, you can arrange to fight against your friends shadow for practice for the big match-up or even see how well you stack up against competitive professional players. It not only provides a near-unlimited stack of player-generated opponents within Killer Instinct, but gives casual or novice players a chance to stack up against the other human players. This can prove really useful in bridging that gap from the AI single-player modes, to the online arena: given that shadow AI more accurately reflect the challenges faced when heading into ranked online multiplayer and allows players to recognise how people actually play the game online.

The Shadow AI System

The shadow AI that is built for a given character is achieved by recording every action in every match that the player participates in. This includes every movement, jump, block, counter and combo sequence. The rates at which information is recorded varies depending on the action itself: with fixed duration for standard attacks with movement and combos being modelled in a more continuous thread. Combos are recorded right down to the animation frame count, which will prove really critical later on.

At the same time, the current state of the match is recorded: character health bars, shadow meters, distance between players, time remaining and much more. The shadow system records every single piece of information in a given match, with absolutely zero data being ignored.

With these actions and states recorded, the next process is to establish what is known as ‘patterns’: associations between actions that take place over small periods of time to states of the world. A parsing system is able to read the low-level actions and establishes what higher level behaviours are occurring: special move setups, zoning, traps, combos, combo breakers, counters, shadow counters, even when you taunt your opponent. This is achieved courtesy of Iron Galaxy’s Derek Neal — an ex-tournament player and director of production on Killer Instinct — who helped establish how information should be parsed, but also — later on — how it should be recognised.

This process typically results in 400–700 patterns being established in each match and three matches in the shadow dojo — which we’re watching right now — are required for your shadow to have a base level of competence. The shadow system retains information on up to 40 matches for a shadow when fighting against a specific opponent. This means any given shadow could store up to 28,000 patterns for a single match-up with a given player.

Each collection of patterns to world states for a given match-up is known as the model for that shadow against a given opponent. With that model in place, we now have a collection of pairings that tell us in a given state what our shadow should do to mimic the players behaviour. But how do you pour through all this data so quickly to give the best possible response? The answer can be found in an AI technique known as Case-Based Reasoning.

Case-Based Reasoning: A Short Overview

Case-based reasoning is an AI principle of inductive reasoning that is derived from human approaches towards problem solving: more specifically it is driven by the notion that human reasoning derives from prior experience. By modelling our prior experiences, we can then make intelligent decisions towards new problems by considering how similar they are to ones we have already solved.

Case-based Reasoning is typically modelled as a four-step process, sometimes referred to as the four R’s: retrieval, reuse, revision and retention that is driven by modelling examples of a given problem and the action made to resolve it, known as cases. Having accrued a collection of cases stored in a compact but quickly accessible format, we can then use the 4R methods to make intelligent decisions, but also update and maintain our knowledge base.

This process enables a decision making system that generalise our previous experiences in order to make intelligent decisions in the future, but can also update our knowledge of the problem the more times we discover it. It’s a technique that proves highly useful in commercial and industry areas where a continued influx of new data can be used to improved its accuracy. As such it’s found useful applications in areas such as fault diagnosis in engineering, anticipating court decisions based on legal precedents, recommendation systems in online shopping and customer support as well as fraud detection.

The application of this process to Shadow Mode now makes sense: the recording of actions and states as patterns are the cases used by the reasoning system. The tricky part is how this information can then be retrieved and updated in real-time during a match. So let’s take a look at how that works.

Model Retrieval for Shadow AI

Given the large set of action patterns, the trick is to now make the right decision at any point during a match. Bruce Hayles of Iron Galaxy — developer of the Killer Instinct shadow AI — revealed that the system is reliant upon an known as nearest neighbours: where over 40 metrics are used to define how similar a state from a recorded pattern is to those currently happening in-game. These metrics range from recognising if both players are on the ground or in the air, to more nuanced understandings of play: establishing whether the player is playing defensively or ready to commit anti-air attacks. Some metrics are even character-specific: such as the locations and status of Maya’s knives. Using these metrics, the retrieved collection of actions in those gameplay patterns provide viable option for the shadow to execute. The shadow AI then ranks based on the perceived value of each action and selects what it deems appropriate, but with a small probability may switch to a lower-ranked action in order to trick its opponent.

Now in order for this process to be accurate, the system often records data in a way that is relative to a specific in-game moment, rather than a 100% accuracy to the original state. So for example distance and health are often recorded relative to your opponent rather than specific values. This means that the action associated with that pattern will be applicable in different circumstances — allowing for the system to establish context.

Retrieval also considers the sequence of actions preceding the current moment in the game such that it can establish the appropriate response. If it’s clear that the opponent is setting up an attack, the shadow can respond with a counter. This boils down to the relevance of whether a player or an opponent is executing a combo and the stage it is currently at: given this ensures the Shadow can either progress their combo or attempt to counter the opponents at just the right moment in time. This is why animation frame counts are recorded during the annotation process, so the shadow knows exactly when to trigger a breaker or reversal. Otherwise, given the nature of Killer Instinct, it would almost never work.

When retrieval takes place and the shadow executes an action: it models how the success of a specific action or strategy and updates its relevance during the match. Allowing the shadow to adapt and change its strategy during gameplay. This means that if a shadow is repeatedly being punished for making a specific action in a particular moment, it will shift priorities to another strategy mid-match.

This re-evaluation can even be executed on a much more granular level: if the shadow is executing a combo and the patterns conditions will no longer hold — then a similar valid pattern overlapping and taking control. This is pretty useful when say a combo is meant to kick in off of following a successful action, but the player actually blocked it. A fallback plan of how to respond to that attack being blocked can now kick in instead.

However, the system is still limited in many respects due to the expert knowledge required to craft it, as well as the data it needs to accumulate from training. The metrics being used for the retrieval and storage process are reliant upon a designer with an intimate knowledge of how to actually play the game at a competitive level. An issue that doesn’t impact Killer Instinct for sure, but it’s important to consider when developing your own case-based shadow AI techniques. In addition, the shadow needs to be able to watch its human counterpart execute specific actions several times in order for it to really establish that pattern in its model. Hayles himself admits that in some cases even the 40-match limit per opponent can still prove insufficient in building a complete and rich set of behaviours.

Closing

The shadow AI system is a versatile system capable of adapting to changes in a players strategy. It’s behaviours appear far more realistic in their behaviour and are able to provide a fun and interesting addition to a players training regime.

Killer Instinct is a free-to-play game on both Xbox One and Windows 10 PCs and you can try you hand at creating your own shadows. You can even fight against the shadows I created that you can see in the video at the top of this article. Be sure to look up my profile at GET TUDA CHOPPA and try it out yourself.