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 if NPC ships themselves could get better by repeated interactions?

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 to see if the notion might have some merit.

It's In Your Genes

The first step is to define the "genes" of NPC ships. According to my naïve understanding, these would be fields enumerating the kinds of decisions that an NPC ship could make, where each decision mode could have several possible values corresponding to decisions of each kind.

So 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 any weapon as soon as it's ready
• 2 = fire when 2 or more weapons are ready
• 3 = fire when 3 or more weapons are ready
• 4 = fire only when facing opponent's weakest shield
• 5 = fire only when facing opponent's strongest shield
• 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 - maneuver to remain engaged while checking self_preservation
• defensive_maneuver
• 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
• targeting_focus_updates
• 1 = review targeting every ten seconds
• 2 = review targeting every thirty seconds
• 3 = review targeting every minute
• 4 = review targeting if internal damage > 25%
• 5 = never change active target
• self_preservation
• 1 = fight until internal damage > 25%, then take defensive_action
• 2 = fight until internal damage > 75%, then take defensive_action
• 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 of different kinds 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.

Some quick sample pseudocode:

#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 move ship randomly to remain near 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 number of genes to swap (any number from 1 to 1/2 [rounded down] of total number of genes)
  randomly select 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 this. :)

I have some myself. For example, 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 gameplay session? What's the right number to create a fitness metric that leads to a satisfying rate for breeding better (not just different) ships? Should this number be one thing when the game starts, then change to something else later?

Is a 5% mutation rate too high or too low? Should this number be one thing when a new game is started 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?

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 fun for most players who engage in ship combat.

One way could be to 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 pre-defined ship of the appropriate tier, win/loss ratio, and (perhaps) type from the current table of ships.

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 player for whom those challenges are being spawned.

Another possible issue with the ship-breeding mechanic is that it might be too good. Over a long time the population of "successful" ships currently 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 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 that be a problem? Or a win?

What other issues should be considered when thinking about how to actually include a genetic mechanic for breeding better opponents?