Galactic Arms Race

In our previous article on the Mario AI competition, we discussed the application of procedural content generation within games and recent efforts in researching the development of PCG systems.  One of the key points this article establishes is the importance of finding means to establish how useful a piece of procedurally generated content is in the hands of a player.  Now we argue strongly against the idea of ‘fun metrics’: where we would quantify how useful a piece of content is courtesy of some formula or algorithm.  This is largely because whether a piece of content, be it procedurally generated or hand craft, can only really be considered useful by players.  Even then, this usefulness is highly subjective: given what one player thinks is useful or interesting may not suit others.

In the previous article, we focussed on the level-generation track of the Mario AI Competition: a now defunct AI competition that challenged researchers to create levels within the Infinite Mario clone. Meanwhile, in this second article in the series, we focus on a game that was developed with these challenges in mind and deploys an interesting technique that result in varied content for a range of player types.

GAR-Title

Galactic Arms Race

Galactic Arms Race (GAR) is a rarity in that it is a game that has been built in a sense to showcase a research method.  The game is developed by Evolutionary Games, which work in conjunction with Evolutionary Complexity Research Group (EPlex) based at the University of Central Florida (UCF).  This co-operation is derived largely from the fact that key members of Evolutionary Games have history with EPlex.  Dr Erin Hastings, who leads development of GAR is a PhD. alumni of the research group.  Meanwhile, Associate Professor Kenneth O. Stanley who oversees GAR is the director of EPlex.

GAR is an isometric shooter set in space, where players can team-up online to conduct missions and eliminate ships and fortifications belonging to the Xindo alien race.  Players have the ability to upgrade many facets of their spaceships: notably armour, weapon power, shield strength and warp-drive capabilities.  However, the most interesting gameplay element comes from the weaponry.  Players are provided with three weapon slots that, initially, all carry the same type of particle weapon.  Players can find new weapons by destroying enemy bases and have the option of to swap-out old weapons for those found in the vastness of space.

GAR-1

What makes GAR so interesting is that the particle weapons are procedurally generated.  Differences in weaponry are not simply cosmetic, with guns that fire particles that vary in their patterns of movement: instead of moving forward they can spiral, stop, strafe or head off at particular angles.  This results in a large number of unique weapons that while adhering to the same principles, provide a range of different opportunities for gameplay.

Note: A good example of the variety the game can generate comes from one of the first videos released of GAR in 2009. This video showcases the alpha build of the game when in development at EPLex.

As stated in the game, the weapons are derived from ‘Neuralium Isotopes’.  Each isotope is unique to a given weapon and is what drives their look and behaviour.  Naturally, this is just a little bit of fun: there is no such thing as a neuralium isotope.  In fact, the weapons are built using neural networks, a topic we have previously discussed in the EvoTanks article.  However, the technique deployed for GAR is far more advanced and interesting to boot!

The SCIENCE! Part

The weapons of Galactic Arms Race are built courtesy of the Content Generating Neuroevolution of Augmenting Topologies algorithm (cgNEAT).  To clarify, NEAT in itself is an established algorithm for evolving artificial neural networks.   However, the cgNEAT variant is designed to specifically for creating content based upon user preference.

NOTE: This section relies heavily on an understanding of neuroevolution: specifically evolutionary algorithms and artificial neural networks. If you are not familiar with these topics, please consult ‘Evolving to Shoot a Sitting Duck’: an article detailing my first experiences with these methods.

To give you an indication of how cgNEAT works, first we must talk about the original NEAT algorithm: how it works and what what so interesting about it that it caught the attention of the larger AI/Game research community.

The NEAT Algorithm

In a previous article we discussed how neuroevolution is adopted: we typically take a neural network design and then alter it over time by having the weights – and in some cases the topology – become chromosomes that are tailored courtesy of our evolutionary algorithm.  As you may recall in the EvoTanks article, we were only interested in evolving the weights of the network, while the topology remained fixed.

The NEAT algorithm differs from what we have previously established in four key ways.  While we summarise these in the following sections, enthusiastic readers should consult (Stanley and Miikkulainen, 2002) which covers this in far greater detail.

Genetic Encoding

NEAT adopts a system whereby a chromosome stores not only the number of neurons, but the connections between neurons and their weighting.  This is a rather powerful technique, given that this representation of a neural network allows for genetic crossover and mutation to occur with relative ease.

An example from (Stanley & Miikkulainen, 2002) of a genotype encoding in NEAT and the corresponding phenotype (neural network).  Note that in the genotype the structure of the network is dictated.  This can be changed as part of the learning process.
An example from (Stanley & Miikkulainen, 2002) of a genotype encoding in NEAT and the corresponding phenotype (neural network). Note that in the genotype the structure of the network is dictated. This can be changed as part of the learning process.
Historical Marking

Another key innovation that NEAT introduces is historical markings, referred to as an innovation number.  As shown in the diagram above, each connection gene carries an innovation number.  This neural network is arguably at an early stage, given that all of the innovation numbers for each of the connection genes are unique.

A new innovation number is assigned when a gene is created through mutation.  It does not occur by genetic crossover, given that it is exchanging data to create new chromosomes.  It does not change the actual genes.

If we consider the diagram below, we see two types of mutation that are applied in NEAT: adding a new connection between existing neurons, or adding a new neuron on an existing connection.  In each case new genes are created and carry new innovation numbers.

A diagram from (Stanley & Miikkulainen, 2002) which highlights how mutation occurs in the NEAT algorithm.  Note the creation of new genes which also receive new innovation numbers.  These help identify the 'ancestry' of a given gene.
A diagram from (Stanley & Miikkulainen, 2002) which highlights how mutation occurs in the NEAT algorithm. Note the creation of new genes which also receive new innovation numbers. These help identify the ‘ancestry’ of a given gene.

These innovation numbers allow for historical ancestry of genes to be modelled.  This is useful on a number of fronts, though two immediately spring to mind.

  1. We can see at the end of a learning phase which genes stood the test of (simulated) time.  Since after generations of learning are completed, we can see how ‘old’ a gene is and study it in order to ascertain its value in the context of the final network (and the problem at large).
  2. It makes genetic crossover much easier.  Since, as shown in the diagram below, we can have two different networks attempting to merge together, which could prove messy.  Instead in this instance, the innovation numbers help identify which genes in each parent correspond with one another.  This means that the process to create offspring is much easier.  Since we only need to establish which genes are either disjoint or excess and simply remove them.
An example of genetic markers at play from (Stanley and Miikkulainen, 2002).   This shows two networks that being matched up for genetic crossover.  The historical markets allow us to identify how the network should be constructed from two separate chromosomes.
An example of genetic markers at play from (Stanley and Miikkulainen, 2002). This shows two networks that being matched up for genetic crossover. The historical markets allow us to identify how the network should be constructed from two separate chromosomes.
Speciation

If we consider the example discussed in the image above, we are dealing with two chromosomes that achieve crossover with few disjoint or excess genes as a result.  Of course, this is not always going to happen.  If anything, we will be seeing chromosomes attempting to merge that are completely different from one another, which could lead to a lot of stray genes being created and ultimately cast aside.

To address this, NEAT establishes ‘species’ of evolved solutions.  This means we can ensure that particular species are preserved within a niche of the population.  This particular species can then attempt to optimise itself by breeding among itself.

Incremental Development of Topologies

When evolving candidate solutions, we can take different approaches to the network topology.  In the case of EvoTanks, we used a simple yet fixed topology.  This forced us to find a solution within the confines of the network we designed.  In other cases, we may start with random topologies and then allow the learning process to develop them from there.  In the case of NEAT, neural networks can start as simple as two layers: an input layer connected to an output layer.

The NEAT algorithm actually encourages network structures that are as uniform as possible.  Mutations to the topology of the network are only accepted by the learning process should they prove useful after being evaluated.  One of the reasons this is really important is that each new synapse in a neural network increases the dimensionality of the search space.

Why is this so important?  Well, the greater the dimensionality, the more possible solutions that exist.  Larger numbers of neurons in a given networks provide more opportunity to find potential solutions because there are more unique configurations of synapse weights and neuron connections.  This is of course a double edged sword, since it means you have a much larger and more complex search space to navigate.  You may stumble upon a good solution, though it may be more due to blind luck rather than a product of the search algorithm.

So in effect, NEAT attempts to make life easy for itself, by preventing you from building massive and unwieldy neural networks.  They only become larger if the evolving population imply that it is a good idea.

Note: While not related directly to this article, I would encourage those who are interested in seeing how NEAT works in its original form to consider looking at NERO.

NERO, which is discussed in (Stanley et al., 2005) allows players to evolve armies of non-player characters in a sandbox environment. You can watch in real-time as characters learn new behaviours using the NEAT algorithm. More information is available on the NERO website.

The cgNEAT Algorithm

With our previous section highlighting how the original NEAT algorithm works, it’s now time to discuss how the cgNEAT variant is applied and, more importantly, how this results in the particle weapons seen in Galactic Arms Race.

cgNEAT is designed such that it automatically generates content based on user behaviour at runtime.  Meaning that as you the system, more content is being created that is influenced by your actions.  This is achieved by conducting some modelling of the users interests, courtesy of usage statistics.  These statistics provide implicit knowledge that can prove useful for the content evolution.

The system is reliant upon the user ultimately replacing the fitness function of the learning algorithm.  Unlike previous examples, we are now reliant solely upon the human to tell us whether this new content is remotely relevant.  This is referred to as Collaborative Content Evolution (CCE).

This image, courtesy of (Hastings, et al., 2009) gives a breakdown of Collaborative Content Evolution (CCE).  Starting with a range of unique content, the players act as the fitness mechanism.  Identifying what is worth keeping, which ultimately influences future content being created.
This image, courtesy of (Hastings, et al., 2009) gives a breakdown of Collaborative Content Evolution (CCE). Starting with a range of unique content, the players act as the fitness mechanism. Identifying what is worth keeping, which ultimately influences future content being created.

CCE works with the user at runtime to determine which content should be exploited as part of the future expansion.  At the beginning of the learning process, the content that is provided is either generated at random, or selected from a starter pool, which contains previously established ‘good’ solutions to work from.  While the starter solutions may not suit the users tastes, they are not intended for evolution process and cannot be selected as part of the CCE method.  However, they can gain fitness as the user continues to use (or ignore) that content.  This allows for the preference metrics to be influenced at the beginning of the learning process when no clear user metrics have been defined.  Essentially jump-starting the learning process.

As the users metrics become more established, they are used to dictate what new content is evolved using the NEAT algorithm.  As the learning process continues and more content is generated, some may be entered into the the archive pool.  The archive pool is designed to help retain content that has achieved a  high level of fitness thanks to the users metrics.

So, how does all of this work in practice?  Let’s take all of this on board and see how it applies in the context of the GAR game.

cgNEAT in Galactic Arms Race

The definition of cgNEAT previously can quite easily be applied in the context of a video game.  What is arguably the most useful tool that cgNEAT has at its disposal, is the ability to infer `good’ ideas from gameplay and continue to develop as a result.

In the case of Galactic Arms Race, new content is evolved and then placed as pick-ups within the world.  These can only then be used as part of the evolution process, once the player has actually picked them up.  This means that the population size for the learning algorithm can vary, given that new content derived as genetic offspring, only become part of the actual population once the player has acquired it.  If this does not occur, then it exists a temporary state until either the player takes it, or it is removed after a certain amount of time.

Gun Design

As mentioned previously, the weapons that are part of GAR are in fact neural networks.  However, they are based on a variant that of neural nets known as Compositional Pattern-Producing Networks (CPPNs).  CPPNs are unique in that the neuron activation functions (and how they are applied) differ when compared to traditional ANNs (Stanley, 2007).  Typically, an ANN will rely on sigmoidal activation functions.  Meanwhile CPPNs can adopt a range of different function types: such as periodic functions (sine/cosine), symmetric functions (gaussian), linear (slope-intercept) and non-linear (polynomial) functions.

What does this mean for the resulting network?  The use of multiple unique functions can yield really interesting results.

ComposingGradientFunctions
An example from (Stanley, 2007) of how adopting multiple functions in sequence can produce patterns with multiple regularities.

As shown in the diagram above, when we start using multiple functions in sequence (which is what an ANN boils down to) we can potentially built patterns.  This is rather exciting, given that it moves away from the notion of how we typically use ANNs to control non-player characters.  Instead, we can use it to regulate patterns on an input.  These regulated patterns are exactly what we need to create particle weapons.

This diagram, from (Hastings et. al., 2009) highlights the differences in ANN vs CPPN design.  While the network topology is the same, note the use of different activation functions in the neurons.
This diagram, from (Hastings et. al., 2009) highlights the differences in ANN vs CPPN design. While the network topology is the same, note the use of different activation functions in the neurons.

So unlike traditional NEAT, which uses ANNs, cgNEAT for Galactic Arms Race uses CPPNs.  This is how the patterns are produced in the gameplay videos throughout the article.  At each point in time, the current state of the gun particles are fed into the network and the CPPN dictates how that particle behaves on each frame.  Each particle provides the position and distance relative to their initial firing position and the CPPN tells the particle the velocity and colour it will have for that particular frame.

This CPPN design for GAR, shown in (Hastings, et. al. 2009) takes the position and distance of a particle in the weapon and tells it the velocity and colour to apply to that particle for a given frame.
This CPPN design for GAR, shown in (Hastings, et. al. 2009) takes the position and distance of a particle in the weapon and tells it the velocity and colour to apply to that particle for a given frame.

Game Design

Hopefully this is all beginning to make more sense: the CPPNs are evolved at runtime, the learning algorithm is influenced by the behaviour of the player as the use the weapons derived from the CPPNs and the cycle continues on from there.  cgNEAT continues to create new weapon content based on the weapons you continually use.  As a player continually fires a weapon in their arsenal, not only does the fitness of that weapon increase (towards a maximum of 1000), but it decreases the scores for all other weapons currently owned (towards a minimum of 0) (Hastings et al., 2009).

What makes this even more interesting is that GAR is an online multiplayer game: meaning that as players continue to play on a given server new weapons are being created by their behaviour.  It is therefore possible for players to be given new weapons created by other players behaviour and potentially allowing for cross germination of gameplay styles as players ‘share’ weapons with one another in a totally different manner from how it is achieved in Borderlands.  While there is an offline mode for the game, this results in differing behaviour in the learning model.  For the sake of this articles length we will go into detail.  However, it is work reading (Hastings et al., 2009) for more detail.

Closing

Galactic Arms Race is a prime example of how AI can be adopted as part of game design in an interactive fashion.  While the cgNEAT system is responsible for the creation of the content, it’s the player who decides whether that content is ‘good’ or not.  Ultimately this means the system continually adapts the content it is generating to try and suit the players taste.  While an intimate understanding of what those tastes are is unknown, the game builds this into the core design: allowing for players to continually experiment with the weapons they find as they explore the game.

This game is still one of a rather rare breed: a game that is built around research in AI in order to highlight what these new methods can achieve.  In an effort to curate games such as Galactic Arms Race, a host of researchers (including myself) organise the website aigameresearch.org.  This website hosts a collection of games that have been developed as part of AI research projects.  I would encourage checking out the site: it provides links to relevant papers as well as either online playable versions, or links to demos of each game.  There is a wealth of further reading available for those interested in the science behind Galactic Arms Race.

Meanwhile, the latest version of Galactic Arms Race is currently preparing for a full release on Steam, having been approved in Steam Greenlight.  In the meantime, you can pick up the full version of the game from Desura.

References

  • Stanley, K.O., Cornelius, R., Miikkulainen, R., D’Silva, T. and Gold, A. (2005). “Real-Time Learning in the NERO Video Game”Proceedings of the Artificial Intelligence and Interactive Digital Entertainment Conference (AIIDE 2005) Demo Papers.
Enjoying AI and Games? Please support us on Patreon!
Tommy Thompson Written by:

Tommy is the writer and producer of AI and Games. He’s a senior lecturer in computer science and researcher in artificial intelligence with applications in video games. He’s also an indie video game developer with Table Flip Games. Because y’know… fella’s gotta keep himself busy.