Playing with Genetics

Genetic Algorithms that is:

I've been toying with the ideas related to adaptive "AI".  The basic idea is:  If you could play a game where the content is adaptive, the game would seem "fresh" longer and you would have more incentive to play the game for an extended period of time.  You can use Genetic algorithms to produce “solutions” to problems automatically….can you then apply genetics algorithms to make games that adapt to the players?  (The answer is “yes”, this isn’t actually a new idea and I’ve already seen research in this area).  However I want to play with some of this stuff, because you learn best by doing things and sometimes you discover things new when you make mistakes doing things you’re trying to learn.

One of the basic requirements of this is to have a “game” that we can control the results of (we want to control the environment and see what the “genetic” aspect will do within it).  So lets define a game where the goal is to "predict" the best move.  One such game we play today is "Rock/Paper/Scissors".  However I want something that can scale to include 5+ players so I've defined the game "Elements".

Elements:  Goal - Choose the element that is opposite of the most popularly chosen element.

Element Choices:

Basic Round Example

5 Players make a choice: E, A, A, F, W

Result:  The players that chose "Air" lose points, the Player that chose "Earth" gains points. 

The goal:  Over a "set" of rounds, maintain a positive score.

So given this kind of game:  If we create a genetic algorithm for making choices, can we make "smart" players (players that are able to react to predictable patterns, and then adapt when changes in those patterns occur). 

So I developed the game and first produced “dumb” players.  Players that that I could dynamically create, but once created would only choose a predetermined choice.

Then I started working on the Smart players:  I wanted a dynamic command set, so I needed to define the command, which then caused a bunch of refactoring because I realized I didn’t just want simple commands like “Choose Fire” but I also wanted complex commands like “Choose the Opposite of the Last Popular Choice”.

So Once I hooked up the command system, I started by creating “random” entities.  And then finally I included the work to do mutation, rewrite an reproduction.  As part of this work I had to write a “fitness evaluation system”.  Basically you need to know when to stop mutating the genetics because you’ve found a solution.  For this particular program, I want something dynamic so I came up with a “generalized” fitness check.  You can be in one of 3 states:  Postiive, Negative, Neutral.  Also we don’t do full evaluation and mutation every round, but rather at the end of a “set” of rounds.  Due to the nature of the game, in most cases any particular player is more likely to have a negative or neutral score rather than a Positive score…so we really only want to make “incremental” mutations if we’re actually keeping neutral.

Mutations and Reproduction:

There’s any number of ways to do this, I chose the “lazy” route, I have a minor and major mutation option:  Minor mutation includes adding (1 or 0) new commands to the (front or back of the) List.  Major mutation involves reducing the size of the list or adding multiple elements. 

Finally we have a “third” case of mutation which is total replacement.  At the point a command set is replaced, in a genetic sense, those genes “died off”.

Hooking up evaluation and mutation:

I decided that I’d track 2 phases of results and during every evaluation phase, I would look at the past results to determine how much to mutate the command set.  If the current and previous results were negative, we have a “dead end” genetic sequence, it dies (replacement).  If either the current or the previous results were negative, we introduce a major mutation.  If we have only neutral and positive results, we introduce a minor mutation and if we only have positive results we don’t change (though we may reproduce if we run a reproduction phase).

And finally, if a command set gets too big, we cause a major mutation (which will reduce the size). 

The final results from initial testing show that given some time, the genetic algorithm can usually stabilize on a solution if there is a stable solution available (simple solutions like “don’t pick Element X or do pick Element X”.  If there are multiple “dynamic” entities involved, it’s possible that they may extend the length of time or make the system unable to stabilize. 

My test app is a bit ugly, but here’s a screen shot of what it looks like:

Possible Future investigation:  Can I get a smart player to predict complex patterns (like all of the “dumb” players play the sequence: Earth, Air, Fire, Water.

I hope you enjoyed my story about delving into genetic algorithms, thanks for reading.

-Kris-