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?

Timmy, Johnny, and Spike Meet the Bartle Types

I recently noticed an article by Mark Rosewater for Magic: The Gathering in which he discussed player types (or, as Rosewater calls them, psychographic profiles).

This was a December 2006 expansion of a previous article, which proposed three types of playing styles -- that is, three player types -- for Magic: The Gathering: Timmy, Johnny, and Spike. As Rosewater describes these types in the updated article:

Timmy wants to experience something. Timmy plays Magic because he enjoys the feeling he gets when he plays. What that feeling is will vary from Timmy to Timmy, but what all Timmies have in common is that they enjoy the visceral experience of playing.

... Johnny wants to express something. To Johnny, Magic is an opportunity to show the world something about himself, be it how creative he is or how clever he is or how offbeat he is. As such, Johnny is very focused on the customizability of the game. Deck building isn't an aspect of the game to Johnny; it's the aspect.

Spike plays to prove something, primarily to prove how good he is. You see, Spike sees the game as a mental challenge by which he can define and demonstrate his abilities. Spike gets his greatest joy from winning because his motivation is using the game to show what he is capable of. Anything less than success is a failure because that is the yardstick he is judging himself against.

In the update, Rosewater goes on to further break down each of these three styles into four subgroups:

Timmy: Adrenaline Gamers, Power Gamers, Diversity Gamers, Social Gamers

Johnny: Uber Johnnies, Combo Players, Offbeat Designers, Deck Artists

Spike: Analysts, Tuners, Innovators, Nuts & Bolts

Reading the names and descriptions of these subgroups, I had that very familiar feeling of seeing another iteration on the four original player types proposed by Richard Bartle. Each of the four subgroups for all three MtG styles sounded very much like one of the Bartle types, simply zoomed in a bit to be specific to each of the MtG styles.

Based on Rosewater's effectively characterized descriptions of all twelve subgroups, it was surprisingly easy to see each one aligned with one of the Bartle types. (Naturally, that's "Bartle types as I understand them." None of this has been endorsed by Richard; all interpretations and extensions of his player types model described in this blog are my own and should not be blamed on anyone else.)

Bartle	Timmy	Johnny	Spike	Goal of Play
Killer [Manipulator]	Adrenaline Gamers	Uber Johnnies	Analysts	plays for the sensation
Achiever	Power Gamers	Combo Players	Tuners	plays for the win
Explorer	Diversity Gamers	Offbeat Designers	Innovators	plays for mastery
Socializer	Social Gamers	Deck Artists	Nuts & Bolts	plays for self-expression

(Note that this chart should be considered an extension of Styles of Play: The Full Chart showing the deep correspondences I believe exist between several theories of personality and player styles.)

As always, it's possible that I'm seeing just what I want to see here. But considering how very neatly each of the four subgroups for the Timmy, Johnny and Spike styles matched up with the four Bartle types (at least to my perception), I have to wonder whether Rosewater deliberately drew from the Bartle types to create the various subgroups.

Whether he consciously adapted the Bartle types to his three-style psychographic model or not, I thought the juxtaposition of these models was interesting enough to be worth mentioning. There are many styles of play for many kinds of games and gamers; I'm fascinated by the possibility that there might be some utility in recognizing four deep patterns of play in particular.

Is Mark Rosewater's assessment of styles of play in Magic: The Gathering yet another confirming instance for this theory?

Is There Now a Language of Game Design?

In "Analysis: The 5 Major Trends of GDC 2009," Gamasutra editor Chris Remo mentions a particular exchange between veteran game creators Will Wright and Warren Spector:

Warren Spector and Will Wright observed that indie developers are exploring design avenues that are nearly impossible for older designers to have conceived, because younger indies are building on a lifelong fluency.

"It’s like we developed this language we had to learn as non-native speakers," said Wright of his generation of designers. "They grew up with that language."

"They're almost like commentary on the games that have come before," Spector offered.

As I read it, this is the notion that today's game designers are inheriting (and fluently speaking as natives) an immediately usable language of gameplay mechanics that until now has had to be invented on the fly.

That's a wonderfully provocative comment. (Actually, I suspect it explains not only a good deal about the success of W.W. and W.S., but also why it's great to have them on conference panels!)

Some random reflections:

1. The "language" W.W. mentions seems to be more at the level of design patterns than the atomic-level game grammar that Raph Koster, among others, has been exploring. That's not to undercut the potential value of being able to reduce gameplay to low-level factors; it's more a recognition that the working language of a designer may usually be at the higher chunking level of patterns.

2. In terms of expressive capability and maturity, how does this game design language compare to the language of film direction? After a hundred years of movie-making, film directors today have a rich, specific, and broadly-understood vocabulary of verbs and nouns to work with -- how near or distant to that standard is today's language of game design?

3. How dependent on the computing, networking, and presentation technologies is the language of game design? Do non-computer games (such as tabletop RPGs) have useful "words" that today's computer game designers might not be aware of? Or is most of the utility of computer game design patterns driven by what the technology allows, in which case, what happens to a language of game design when the technology changes radically (as OnLive may do, which W.S. noted)?

4. As the flip side of the previous question, do some words in the language of game design ever die? That is, are there some game design patterns that are permanently abandoned? If so, why and how does that happen?

5. What's left to invent? Considered solely on its own merits, how complete is the current language of game design? Are there any obvious gaps; are there useful intentions and directions that are currently hard to communicate even between experienced designers?

6. Can new words in the functional language of game design simply be made up through conversation or general writing? Or must each new word prove its utility by being implemented in a game or games? Does the popularity of a game have anything to do with whether a new game design word is perceived to have enough value to enter the lexicon? Should it?

7. To put the above question in a different context, who invents new words in the language of game design? Game designers? Or non-designing game players?