Breeding Better NPC Opponents

During the course of a discussion on specific gameplay mechanics that could be used to define the challenge level of NPC opponents in a space combat game, one of the ideas involved eliminating NPC ships that don't perform well. That got me thinking -- how interesting would it be to work out a more-or-less evolutionary model for letting NPC opponents get better over time?

What follows is a first cut at a system for letting NPC ships "breed" themselves into combat excellence. It's not intended to be The Perfect Solution -- it's just some starter ideas to beat up on.

It's In Your Genes

The first step is to define the "genes" of NPC ships. These would be a set of fields corresponding to types of actions that an NPC ship could take, where each action type could have several possible values corresponding to specific kinds of actions of that type.

Here's one possible set of NPC ship genes:

• maneuver
• 1 = maintain close range
• 2 = kite (circle opponent at medium range)
• 3 = maintain long range
• 4 = hide behind cover between attacks
• 5 = randomly jink
• offense
• 1 = fire when 3 or more weapons are ready
• 2 = fire any weapon as soon as it's ready
• 3 = fire only when facing opponent's weakest shield
• focus
• 1 = review targeting every ten seconds
• 2 = review targeting every minute
• 3 = never change active target
• aggressiveness
• 1 = maximize power to life support
• 2 = maximize power to auxiliary systems
• 3 = maximize power to engines
• 4 = maximize power to shields
• 5 = maximize power to weapons
• mercy
• 1 = allow opponent to run away
• 2 = allow opponent to surrender
• 3 = no quarter asked or given
• defense
• 1 = turn to keep all shields evenly charged
• 2 = turn to keep forward shield overcharged and facing strongest opponent
• 3 = turn to keep weakest shield away from strongest opponent
• targeting_focus
• 1 = personal targeting only
• 2 = if grouped and internal damage = 0%, group targeting, else personal targeting
• 3 = if grouped and internal damage < 75%, group targeting, else personal targeting
• 4 = group targeting only
• personal_targeting
• 1 = target strongest opponent
• 2 = target weakest opponent
• 3 = target nearest opponent
• group_targeting
• 1 = target same shield of same opponent targeted by nearest allied ship
• 2 = target weakest opponent firing at weakest group member
• 3 = target strongest opponent firing at weakest group member
• 4 = target nearest opponent firing at weakest group member
• self_preservation
• 1 = take defensive action when internal damage > 25%
• 2 = take defensive action when internal damage > 75%
• 3 = fight until victory or destruction
• defensive_action
• 1 = run
• 2 = surrender
• crew_morale (not really a gene... exactly)
• 1 = 25% bonus to effectiveness
• 2 = 50% bonus to effectiveness
• 3 = 75% bonus to effectiveness
• 4 = 100% bonus to effectiveness

What other genes would be appropriate/useful/fun? Code Is Law The next step is to define the code that uses these genes to select the "fittest" NPC ships for future generations. Since NPC ships will always need to actively exist in the gameworld, it's not possible to follow the usual GA approach of performing all genetic actions on the entire current population in clear-cut "generations." Instead, breeding new ships will have to occur in an asynchronous way, and the only way to determine the population's characteristics will be to take a snapshot at some arbitrary moment in time.

#POOL = 10000 #MUTATION_RATE = 95 fight(): // do combat stuff according to genetic predispositions with some random variance as appropriate // for example, "close in" maneuvering would have the ship randomly move to remain within a short range of the target ship if NPC ship survived the fight increment "winner" field in ship table for this ship if crew_morale gene < 4 increment crew_morale gene by 1 else if crew_morale gene > 1 decrement crew_morale gene by 1 spawn_new_ship(type, tier): select into temp table the #POOL ships from the desired type/tier table with the largest "winner" field value randomly select first_ship from temp table if random > #MUTATION_RATE% new_ship = mutation(first_ship) else randomly select second_ship from temp table new_ship = crossover(first_ship, second_ship) add new_ship to NPC ship table with "winner" field value set to 0 spawn new_ship mutation(ship): create newship randomly pick one gene of "ship" randomly change the selected gene's current value to a different value return(newship) crossover(ship1, ship2): create newship, newship1, newship2 randomly select the number of genes to swap (any number from 1 to 1/2 [rounded down] of the total number of genes) randomly select the specific genes to swap newship1 = selected genes from ship1 + selected genes from ship2 newship2 = unselected genes from ship1 + unselected genes from ship2 newship = randomly pick either newship1 or newship2 return(newship)

Questions On Genetics Naturally there'll be questions about some/all of this! I have some myself, such as: how would the usual "culling" function work in an asynchronous breeding model? Would it happen naturally as a side-effect of allowing only the most successful #POOL of ships to "breed" new ships? (I suspect so, but I'm open to other opinions.) Is 10,000 ships too small a number for a breeding pool given the number of fights with NPC ships that are likely in a normal day's worth of many people playing the game? What's the right number to create a fitness metric that leads to a satisfying rate of breeding better (not just different) ships? Should this number be one thing when the game launches and change to something else later? Is a 5% mutation rate too high or too low? Should this number be one thing when the game launches and change later? Would this system eventually lead to too few different types of ships? How long would it take to reach that point? How could this system be tweaked to avoid this problem? Do non-Tactical ships need any special bonuses in order to avoid becoming extinct? Should there be some fitness metric other than "combat winner" that non-Tactical ships would use to allow them to breed better new ships? What genes should non-Tactical ships have, and what version of the fight() function would test their fitness? At what point should the breeding process be stopped? When will opponent ships be "good enough?" Could they ever become "too good?" Application of an NPC Opponent Breeding Program Having considered just the core mechanics of an "opponent breeding program," it's also true that while a gameplay mechanic might be cool on its own merits, in an actual game it needs to be fun for anyone who's likely to experience it. So let's consider now some of the meta-level design possibilities for how to make a "ship-breeder" mechanic like the one we've been knocking around here fun for all players who engage in ship combat. There might actually be a simple solution: impose a rule that new kinds of ships get created through breeding only 5% of the time. In other words, most of the time when the game needs to spawn a new hostile NPC ship, it can randomly instance a ship of the appropriate tier, win/loss ratio, and (perhaps) type from the current table of ships. (Did I not mention that each ship would store the numbers of times it has won and lost battles with players? Silly me. ) This would satisfy the usual "appropriate for your ability level" requirement for spawning opponents. Note, however, that this is still pretty simplistic. For one thing, it assumes that only one opponent is being spawned, rather than considering how multiple opponents could produce a desired challenge level. And it doesn't address at all the issue that spawning a new kind of ship through breeding might sometimes produce a ship that's either bizarrely stupid or unexpectedly clever -- that's a problem if one of the high-level design goals for challenges is that they always be close to the ability level of the character/player for whom those challenges are being spawned. (Side note: by "ability level" I mean a general capability of the player/character/ship/crew combination in combat -- I am NOT talking about some magical "character level" or "mob level," two things I hope with great enthusiasm never to see anywhere in any online game I'm otherwise looking forward to playing. Dynamically generating a numeric challenge rating from multiple sources -- character rank and skills + (ship tier/type * current_readiness) + (crew skills * crew morale), for example -- is appropriate in order to be able to create/select appropriate challenges on the fly. I even support providing a text designation roughly describing any combatant's challenge/capability level, such as "Commander-level" or "Admiral-level." But to turn those into static numbers... "I'm a Level 37 -- ooh, look, there's a Level 28 mob!" I don't believe it would feel right for this particular game for that to be the standard way that every player thinks of and talks about the difficulty level of problems, whether tactical or engineering or scientific in nature. OK, side note over. ) Another possible issue with the ship-breeding mechanic is that over a long time the population of "successful" ships stored in the ships table might become much larger than the number of average- or poor-performing ships. At that point the only "dumb" ships (i.e., really easy challenges) that players would ever see would be the 5% spawned by genetic chance (and a small number of those might turn out to be really smart). So if most ships at various tiers/types are generally "smart" (in other words, good opponents at any challenge level), would be be a problem? Or a win? Are there other issues that should be considered when thinking about how to actually integrate into a MMORPG a genetic mechanic for breeding better opponents? Thanks for considering these ideas!