Open Interview
ken

Applying Evolutionary Algorithms to the Galactic Arms Race

Andrew Armstrong on December 11, 2008

While AI is playing an increasingly important role in the games industry these days, games entirely based on AI are few and far between. One in particular though, is Neuro-Evolving Robotic Operatives (NERO) which was released in 2005 by Kenneth Stanley and his team at the University of Texas at Austin, and totaled over 100,000 downloads. NERO involved evolving AI bots navigating and fighting in virtual battle grounds.

In this exclusive interview, AiGameDev.com caught up with Ken Stanley to find out about his next project, which is also based on neural networks and genetic algorithms, and a technique called Neuro-Evolution of Augmented Topologies, a.k.a. NEAT, which we covered previously on the site.

His team at the University of Central Florida now is working on a project titled Galactic Arms Race (GAR) which expands the use of NEAT into weapons and procedural content generation, and a more player-friendly game overall. You can find more about this project by reading this interview and visiting the project website and Ken’s own site.

GAR Screenshot 1

Screenshot 1: GAR in action

Andrew Armstrong: Hi Ken, thanks for offering to do this interview. Firstly, can you explain who you are and what your current work involves?

Kenneth Stanley: I’m an assistant professor in computer science at the University of Central Florida. Before that, I was a graduate student at the University of Texas
at Austin. My broad interest is artificial intelligence, specifically focusing on evolving artificial neural networks. I developed the NEAT algorithm for evolving increasingly complex neural networks while at UT Austin working with my Ph.D. advisor, Risto Miikkulainen. My research group at UCF, called the Evolutionary Complexity Research Group (EPlex for short), aims to expand on the NEAT legacy by producing more powerful algorithms that can evolve even more complex neural networks and other interesting artifacts (HyperNEAT is a recent example). One of my favorite application domains for machine learning research is video games. Some AIGameDev.com members may be familiar with my work on NERO, which is a video game in which the player can train robot soldiers in real team.

Related Links:

AA: Can you explain what the game Galactic Arms Race (GAR) is about and who is working on it?

KS: We are currently developing GAR at UCF with the goal of releasing it within the next few months. GAR is an action-packed online multiplayer space combat game in the tradition of such classics as Asteroids and Maelstrom. However, like NERO before it, it is also a platform for demonstrating the potential of evolutionary techniques to change the way video games are made. In particular, the distinctive feature of GAR is that the particle-based weapons themselves evolve based upon which weapons users like. In other words, the game generates its own content in the form of weapons. Of course, shooter games often offer a variety of weapons and players enjoy finding new weapons and learning their strengths and weaknesses. GAR takes this idea to the extreme by continually creating new weapons that players can discover and then deploy on their spaceships. Thus the “Arms Race” part of GAR is meant literally: Players are literally in a never-ending arms race to find the coolest weapons.

“if we can show that such evolutionary content generation is actually fun, then the game industry may begin to see its commercial potential.”

What we want to show with GAR is that games can produce their own content, and that evolution (i.e. genetic algorithms) is the natural choice for making that possible. Think about it: Players naturally spend more time with content that they like than with content that they do not like. Therefore, the fitness function is simple: How much does each piece of content get used? In GAR, that question translates to how much each weapon is used. The most popular weapons become parents of new mutant weapons that are spawned in the universe to be discovered in the future. That way, new content is an elaboration of the old content that people liked. With multiple simultaneous players, the process is enhanced by all the feedback coming from multiple users. The cool thing is that nobody knows what weapons will be like in the future, but whatever they are like, they will be derived from weapons people enjoyed in the past. In other words, players do not need to understand the evolutionary process for it to work!

Our hope is that if we can show that such evolutionary content generation is actually fun, then the game industry may begin to see its commercial potential. We also want to make a fun game that is enhanced by the endless potential to find something new.

GAR is spearheaded by Erin Hastings, who is a Ph.D. candidate at UCF co-advised by myself and Professor Ratan Guha. Erin has been focusing on interactive evolution of particle effects for his Ph.D. research, which leads naturally to GAR’s evolving particle weapons. He previously developed an application called NEAT Particles that served as a proof of concept. Erin programmed most of the game and content-generation code, but as with NERO, there are other student volunteers that have worked or are currently working on the game as well, including Nathan Sriboonlue, Kristin Martin, and Derrick Janssen. Music and sound effects are by Fabian Moncada.

NEAT Particles: Design, Representation, and Animation of Particle System Effects
Erin Hastings, Ratan Guha, and Kenneth O. Stanley
Proceedings of the IEEE Symposium on Computational Intelligence and Games (CIG’07)
Download PDF

AA: How will players progress through the game and what is the gameplay like?

KS: The player can become more powerful and advance to more dangerous zones by advancing in levels through destroying alien ships. There are also different alien species that give the game a role-playing element. A preliminary space map is here.

In single-player mode the player battles aliens and accumulates points. In general, if the player succeeds in breaking through the defenses of a particular swarm of enemies, there will be a base that, if destroyed, yields a new weapon. The player can then pick up the weapon and test it out. The player has three weapon slots and can shoot whichever weapon is desired. We expect that players will generally keep the coolest weapons that evolve and shoot them a lot.

GAR Screenshot 2

Screenshot 2: A pirate Minedo LP-9 ship and player Vulpan Gerobe Kyomi scout ship

In multi-player mode, many players will occupy the same universe on a server simultaneously. We are considering having player-killing and non-player-killing servers to suit different players’ tastes.

AA: How did the technology affect how you designed the game?

KS: The technology does indeed affect the game design. We need to encourage players to collect new weapons and try them out often, so the game play is largely designed to draw players towards new opportunities to find new weapons. Also, players need to make tough choices about which weapons to keep because of the limited number of weapon slots. These choices impact the evolutionary algorithm behind the scenes that is deciding which weapons should be parents of the next ones to spawn.

AA: How does the project relate to your previous game NERO?

KS: One similarity is that NEAT (the method I developed for evolving neural networks) is the evolutionary engine behind both NERO and GAR. However, it is applied in very different ways in both games. While in NERO NEAT evolves robot behavior, in GAR it evolves particle guns. In NERO, the user explicitly controls evolution as a mechanism for training soldiers. In contrast, in GAR, evolution runs behind the scenes and users simply search for new weapons without worrying about it.

GAR Screenshot 3

Screenshot 3: NEAT being applied to particle effects

Perhaps most noticeably, NERO is an intellectual game while GAR is mostly action. Furthermore, while NERO was designed to demonstrate evolutionary AI for NPC control, GAR is about a very different application: automatic content generation.

AA: What successes from the NERO project did you bring forward to GAR? **Conversely, what problems did you attempt to fix?**

KS: An important lesson I learned from NERO is that if there is one technology that can inspire students to produce near-commercial quality products, it is video games. Undergraduate and graduate students are extremely capable and very creative. They are generally willing to think completely outside the box and try things that no commercial enterprise would be willing to risk. I have to thank the Digital Media Collaboratory at UT Austin, particular DMC Coordinator Aliza Gold, for showing me that this kind of student-driven development model can really work. Thus at UCF we’ve taken the same model and applied it to GAR, which is also largely the product of student programming.

“…integration of automatic content generation has obvious implications…”

Something that we want to do differently with GAR is target a more mainstream gaming audience. We recognized with NERO that it would be niche game, but when it comes to exotic new technologies, I think the game industry is motivated mostly by mass market potential. NERO has been downloaded over 100,000 times, which is a lot for an academic project, but you have to think creatively to see how it can extend to more mainstream genres. With GAR, we are aiming for a more direct and obvious implication. Running around shooting and collecting guns is a ubiquitous gaming activity and the integration of automatic content generation has obvious implications for that and many other genres as well.

AA: Can you explain how the cgNEAT element of the game works?

KS: The cgNEAT method is a variant of NEAT that makes it work for automatic content generation. The algorithm should be applicable to all kinds of content in all kinds of games, i.e. not just weapons. What we found with content generation is that it creates situations that regular evolutionary algorithms do not encounter. For example, the population size is variable because ultimately only weapons that people are holding are considered to be in the mating pool. Also, GAR spawns weapons that people may never pick up, which means that offspring are created that may never actually be evaluated. Furthermore, because the hope is that content will evolve to satisfy the players’ preferences, if you assume that different players have different preferences, there is less need for diversity preservation to be enforced by the evolutionary algorithm (because users are inherently diverse in their
opinions anyway). These circumstances are unique to content generation in a multiplayer world, so we needed to alter NEAT to make sense in such a situation. The result is cgNEAT, which optimizes content under such realistic gaming circumstances.

For those familiar with interactive evolutionary computation (IEC), cgNEAT borrows some ideas from it as well. You can see an example of classic IEC here, which is also created by the EPlex group at UCF.

AA: Has there been any interesting or surprising developments from the use of your cgNEAT work in the game?

KS: Sure, the most interesting developments are the weapons that have evolved. We’ve already seen a lot of cool weapons that we would not have imagined, and it’s always fun to see what might come up next.

AA: How much content in the game is automatically generated in one way or another?

KS: The only content generated for now is the particle weapons. However, I do hope that GAR will become a research platform in which we may be able to add other types of evolvable content in the future. In any case, the first release will focus on weapons. I think that’s a promising place to start because with particle weapons we don’t need to hire a bunch of artists on a non-existent budget to help us parameterize different types of content. For example, the creatures and artifacts in Spore could also theoretically be evolved with cgNEAT (although they are in fact designed by users), but we don’t have the budget to create a space of creatures like Will Wright does. Hopefully particle weapons will be enough to prove the concept, and it will be possible to expand the idea to many other types of content in the future with more industry support.

AA: Do you think automated content generation is important in games, and how do you hope this will help game developers in the future?

KS: I think it is critical to the future of gaming. Content generation is among the greatest bottlenecks faced by commercial gaming companies. As more games go online, the demand for a continual stream of novel content in persistent worlds is exploding, creating spiraling costs for the industry. As gaming worlds become increasing detailed and realistic, the time and effort required to supply all this novel content is becoming intractable. Thus there is a need for a technology that can radically diminish the cost of content. Automatic content generation is one such technology. It means that companies can simply parameterize a space of content and let evolution create an endless stream of novelty that is focused on what people want without the need for a massive perpetual team of artists. There is an up-front cost to parameterizing any class of content, but it is worth it compared to the cost of producing it in perpetuity.

GAR Screenshot 4

Screenshot 4: GAR player weapon called “Triple Barrel”

Furthermore, evolutionary content generation is intriguing because the fitness function is implicit in what people do in games anyway. Designers may argue about what people really want (for example, do people really like spray guns or do they like focused lasers?) but evolutionary content generation means that the argument is moot. Players will simply use what
they like and settle the question themselves. Then evolution will create new variants of the stuff people actually like, and so on. It takes the uncertainty out of the design process.

Of course, nothing is a panacea. There are always downsides to automated search. In particular, it means that sometimes, people will find things they don’t like or want. However, I believe that players finding a few duds here and there is a small price to pay for an endless stream of cool new stuff in the long run. I believe the trade-off will become commercially
viable, if not essential.

As far as how GAR helps, I think it can help a lot because every new technology requires risky investment to develop it to maturity and prove that it can work. If GAR succeeds, then that job will be done and the industry will have an algorithm that is shown to work. Ideally, that will change the perception of risk and open the floodgates for automated content
generation across the industry. Of course, because there is obvious risk involved, we don’t know what will happen, but it certainly is worth the risk to try to show it can work.

AA: What kind of AI will enemies in the game use? Will there be any bots or use of interesting AI techniques for them?

KS: In fact, there are flocking algorithms developed by Nathan Sriboonlue controlling the enemy ships. Nathan created a variety of behaviors and difficulty levels to give a range of experience. However, their behavior is not evolved like in NERO. Nevertheless, I think he did a great job and hopefully players will find them challenging and fun.

GAR Screenshot 5

Screenshot 5: GAR particle effects created using the cgNEAT techniques

Thanks to Kenneth for the interview, you can find more about the project on the project website.

Discussion 0 Comments

If you'd like to add a comment or question on this page, simply log-in to the site. You can create an account from the sign-up page if necessary... It takes less than a minute!