Combat Genetics

View the stand-alone site here: www.andymakes.com/extras/combatgenetics

This simulation attempts to create effective spaceship shooter AI using a genetic algorithm. The game itself is roughly based on Combat for the Atari 2600. When it starts, all ships are created with a completely randomized set of rules that govern their behavior. Once all of the ships in a given generation get a chance to compete, the ones that got the most kills (with a bonus for not dying themselves) are allowed to continue to the next generation and to have children. The children inherit the same set of behaviors that the parents had, but mutate them slightly: a value gets changed here and there, maybe a rule gets removed or a new one gets added. Even though these changes are random, over many generations the natural selection process selects for mutations that make them more effective pilots.

I recommend maxing out the ticks-per frame and letting it run for a while, slowing it down when you want to check in. Check out how different your ships are 100 generations in and 1000 generations in!

This project was inspired by Genetic Cars 2 by Rafael Matsunaga which is worth gazing at for hours.

Behavior Rules

At the core of the ship AI is a set of behavior rules. Each new ship gets between 8 and 20 rules, and these rules specify some condition and an action to take if that condition is met. With every tick of the game, each ship goes through its list of rules starting with the first one and checking if the board state meets the condition. When it finds one whose condition is satisfied, the ship takes that action and is done for that tick. Rules can have a cool down time so that they can't go off twice in a row, allowing subsequent rules to have a chance.

The FIRE action is special in that ships cannot fire every tick. All rules with the FIRE action are ignored unless enough ticks have passed since the last time the ship shot. Currently a ship can only fire every 150 ticks.

When a child inherits and mutates a parent's behaviors, all numerical values (including cool down time) have a chance of going up or down slightly, and the conditions for a rule have a small chance of changing (for example, a minimum distance requirement might become a maximum distance requirement, or a rule might stop being concerned with the angle that another ship has in relation to itself). There is a slight chance that the action for a rule will change as well.

Generations and Natural Selection

Once every ship in a given generation gets a chance to compete, they are all given a score that starts as their number of kills in their game. This is multiplied by 1.5 if they were the last ship standing in their game. If a game ended by running out of time, no ship in that game get this bonus. The top 25% are allowed to continue to the next generation and the remaining 75% are removed.

Besides being allowed to continue, the ships that survived are allowed to reproduce. All ships that survived get one child, and the top 1/8th from the previous generation get two additional children (three total). The remaining slots are filled with brand new ships with completely randomized behaviors.

The scoring only takes into consideration the most recent round. Results from games played in previous generations are listed in the ship's stats on the right, but do not factor into whether or not it will be allowed to survive and reproduce. Even if a ship came out on top 5 generations in a row, if it has a game where it gets no kills, it's out (although presumably its offspring will be numerous at that point).

Names

To track particular family lines, I created a simple name generator, which basically just strings letters together and makes sure that there are a few vowels in there. Every ship has a first, middle, and last name. When a brand new ship is created, all three of these are randomized.

When a ship is the child of an existing ship, it takes the last name of the parent and uses the parent's first name as its middle name. The child then generates a brand new first name.

All ships that share the same common ancestor will have the same last name, making it easy to track the effectiveness of a given clan.

Technical

This was originally written in openFrameworks. Because I wanted it to exist on the web, I converted it to p5.js. This is only my second foray into p5.js so I'm still figuring it out (my first was a simple video experiment, satan.dance).

Both code bases are available here: https://github.com/andymasteroffish/combat_genetics.

Takeaways

AI in games is a fascinating topic, and one that I have largely ignored in my own work. I've always opted for extremely simple opponents, and I think that in general simple works best. In a lot of ways, this genetic algorithm approach to Combat AI is also very simple: I defined the rules and the various "senses" that each ship has, but I never had to dictate strategy. I've always felt more at home with system design than level design, so this feels natural to me.

I've also been thinking about why I find it so appealing to watch these little ships fly around; why they feel like my babies. My friend Ben Johnson was talking to me about game AI for an e-sport he was making a while back, and he said that he no longer attempts to make whip-smart AI: instead, he prefers to make what he called "puppy AI." Puppy AI runs around and will try to some extent to reach the game goals, but the main focus is to appear playful. His AI had slightly erratic movement and would often just run very quickly at its human teammate. The result was an AI that I felt very comfortable playing with and which I regarded warmly. It wasn't until he told me about his puppy design scheme that I realized that my AI teammate wasn't a particularly good player.

Because there is randomness in the way these ships operate, even after many many generations, they feel more lifelike. Genetic algorithms are often seen as a way to bring a large amount of computing power to bear on a problem in order to find a solution. But at the end of this I do not have a perfect Combat AI. However there is a certain liveliness and personality to the ships which I think would have been nearly impossible to define by hand. I love creating game systems because I love being surprised by what can emerge from them. The natural selection process on display here amped that up considerably. Playfulness was not an expected outcome, but I'm glad to see it join the party!

Javascript and editing help from Jane Friedhoff.