Artificial Immune Systems and Adaptive Strategies in Game A.I.

A.I., perhaps unsurprisingly, often borrows inspiration, language, and models from the world of biology. Two common examples are Artificial Neural Networks (ANNs) – based on a model of the brain, and Genetic Algorithms (GAs) – based on a model of evolution.

There are plenty of case studies of these biologically-inspired systems being used to develop “intelligent” computer-controlled videogame characters, and there are implementation examples in many game AI textbooks. However, I’ve never heard of an example of a game that makes use of an Artificial Immune System (AIS), i.e. a system based on the structure and processes of the human immune system. In fact, I could barely find any material on it at all, save a few articles in academic journals.

I find this a bit surprising because I can imagine several scenarios in which, following an initial exposure to a player’s actions, an A.I. system could develop an “immunity” to further situations in which the player plays that same action, which I’ll attempt to describe here.

The Scenario : a Simple RTS

Consider a simple Real-Time Strategy game in which two players each build up an army containing a maximum of 60 units chosen from three different unit types. As is common, each unit type is strong against one of the other types, but weak against the other, as follows:

• Type A beats Type C, but is beaten by Type B (i.e. B > A > C)
• Type B beats Type A, but is beaten by Type C (i.e. C > B > A)
• Type C beats Type B, but is beaten by Type A (i.e. A > C > B)

Depending on your gaming preferences, you might prefer to substitute “A”, “B”, and “C” with:

• A:“Scissors”, B:“Rock”, C:“Paper”
• A:“Archers”, B:“Cavalry”, C:“Pikemen”
• A:“Cockroach”, B:“Foot”, C:“Armageddon”…

However, I’ll just stick with A, B, and C for now.

Over the course of the game, a number of encounters take place. In an encounter, one unit is randomly chosen from each player’s army and they do battle. The unit who wins the battle is decided based on the precedence rules above. In a battle between two units of the same type, the winner is decided randomly with 50:50 chance.

Following a battle, the victorious unit survives and returns to the winning player’s army, while the defeated unit is destroyed.

Let’s now assume that both players always maintain their army at maximum strength. In other words, as soon as a unit is defeated in combat, the losing player always build a new unit to replenish their army back to full capacity of 60 units. The strategy of the game therefore comes in deciding which unit types to initially build, and which types to replace them with when they are defeated following an encounter.

 

#1: Balanced Mixed Strategy

In this simple strategy, each player initially builds their army to consist equally of one third each of the different unit types.

When a unit is defeated, the player builds another unit of the same type to replace it, maintaining the same ratio of unit types in their army throughout the entire game.

Player 1’s Army

Player 2’s Army

As you’d probably expect, after simulating 1,000 battle encounters under this balanced mixed strategy, the win ratio between the players averages out to be 50:50:

In this type of simple 2-player, zero-sum game, both players randomising between the three unit types is a Nash Equilibrium and, if both players were rational, their optimum strategy would always be to ensure their army consisted of one third each of the different unit types. Anything other than this could be exploited profitably by the opponent, as we’ll see shortly.

 

#2: Unbalanced Mixed Strategy

Real players aren’t rational, and different people’s play styles often choose them to favour one unit type over another. Suppose Player 1 has a preference to playing with Unit A, and they don’t really like Unit C much at all. So, they build up their army as follows:

• Unit A: 35
• Unit B: 20
• Unit C: 5

Player 2 (the computer-controlled player) has no knowledge of Player 1’s strategy, so starts as before with a balanced army of each type:

• Unit A: 20
• Unit B: 20
• Unit C: 20

Once again, whenever a unit is defeated, the losing player chooses to replace it with a unit of the same type as that just defeated to maintain their chosen ratios, so the makeup of each player’s army over the course of the game remains constant, as follows:

Player 1’s Army

Player 2’s Army

It might not be as apparently obvious as in the first example, but the win ratio between players using these strategies after a series of encounters still converges to 50:50. Even though it is more likely that Unit A will be chosen from Player 1’s army, there is an equal chance of Unit A, B, or C being chosen from Player 2, so it is still equally likely that either player will win a random encounter (this would still be the case even if Player 1 built only one type of unit):

But, is there are a way that Player 2 could exploit the fact that Player 1’s army is now unbalanced? Obviously, computer-controlled A.I. can always “cheat” and simply build the appropriate unit types to defeat the unit types it knows the player is building, but that is a little unfair. Instead, let’s see if we can develop a kind of “Artificial Immunity” through nothing more than knowledge of the unit types encountered in battle, and whether they were defeated or not.

 

#3: Adaptive Strategy using Artificial Immunity

Suppose that, once again, Player 1 favours an unbalanced mix of unit types as in the last example:

• Unit A: 35
• Unit B: 20
• Unit C: 5

And, as before, Player 2 starts with a balanced army of each type:

• Unit A: 20
• Unit B: 20
• Unit C: 20

However, in this example, we’ll attempt to model the idea of Player 2 developing an artificial immunity to Player 1’s actions by changing the strategies regarding unit replacement:

• If Player 1 wins, their successful unit survives while Player 2’s unit is destroyed. Player 2 is no longer constrained to maintain the same ratio of unit types in their army, but is none the wiser about how to defeat this type of opponent, so they build a replacement unit of a randomly chosen type.
• If Player 2 wins, their successful unit survives while Player 1’s unit is destroyed. Player 1 builds a replacement unit of the same type that was defeated (in order to maintain their preferred 35:20:5 ratio of unit types). BUT, Player 2 also chooses to replace one of the existing units of their army (chosen at random) with another unit of the type that just succeeded in battle.

You can consider this second rule to mimic the immune response – having encountered a hostile antigen (Player 1’s unit), and successfully neutralised it, the Artificial Immune System generates more of the appropriate antibodies (the unit type that dominated it) to respond if the same antigen is found in the future. (This at least concurs with my GCSE biology understanding of the immune system!)

So, how does it perform in practice? First, let’s see how the composition of Player 2’s army changes over the course of the game using this strategy:

Player 1’s Army

Player 2’s Army

Player 2’s army starts, as in all the previous examples, equally composed of A:20, B:20, C:20. However, rather than being fixed, notice how the composition of Player 2’s army changes to approximate A:5, B:35, C:20, which best responds to the composition of Player 1’s army of A:35, B:20, C:5. If you prefer to think in colours, notice that the green band of Player 2’s graph approximates the red section of Player 1’s, the red section of Player 2 approximates the blue section of Player 1, and the blue section of Player 2 approximates the green section of Player 1.

And the effect on the average win rate clearly shows that this “immunity” that has developed over the course of previous encounters gives Player 2 the competitive edge, with an average win rate of over 70% after 1,000 encounters :

At this point, it seems reasonable to expect Player 1 to notice that things aren’t going as well as they’d hoped, and to try changing their strategy. Let’s suppose that, after 1,000 encounters, they change the composition of their army, dropping unit A entirely and instead forming their army equally from unit types B and C (i.e. A:0, B:30, C:30). Player 2 continues to play the same adaptive immunity strategy:

Player 1’s Army – switching after 1,000 encounters

Player 2’s Army adapting to change

Notice how Player 2’s strategy quickly adapts to the change in Player 1’s strategy: after 1,000 battles, Player 2 no longer encounters any further Type A units from Player1 (as there are none in her army), so Player’ 2’s own production of Type B units (green) drops accordingly. Likewise, Player 2’s production of Type A units (red) increases to reflect the increased number of encounters with Player 1’s Type C units (blue).

Note that, even after 1,000 iterations with no encounter of a Type A unit, Player 2’s army still contains a residual reserve of Type B units generated by random chance following a defeat, ready to be activated should Player 1’s strategy change again.

This is only a very simple model of how game A.I. could be modelled based on an artificial immune system response, but I think it shows that it’s definitely a technique worth investigating further.