Welcome to the Cheesiest Blog on the Web

Welcome to the blog of The Killer Nacho, known to most mortals as Timothy J. Sharpe, a Computer Science graduate of Messiah College and currently a Systems Analyst for Sunoco Logistics. Within this tome of pages, one will find my innermost thoughts about various things concerning things that I enjoy. These subjects include, but are not limited to, roleplaying, gaming, American Football (the NFL), things to do with computers, philosophy, movies that are awesome, TV shows that are awesome, my own writings and creative works, and dangerous Mexican snacks.

Sunday, October 10, 2010

Evolution AI Experiment

Inspired by my Artificial Intelligence class taught my Dr. Gene Rohrbaugh, I decided to work on a side project in my spare time in which I dubbed "AI Evolution". It was actually an idea I've had for a long while, but I decided to give it a try now because I finally built up enough will to actually proceed. Artificial Intelligence is a fascinating subject for solving problems with computers, by far one of the most interesting fields in Computer Science. It can be used to beat us in a game of chess, search for the right strings we want on Google, and solve problems that would take humans decades. It also has moral, ethical, and philosophical implications and studying it can help us better understand ourselves. Although, this is not the main purpose of this post.

Screen-shot of the application
Sometimes, programming a response to ever input can be tedious. In a game like chess where the number of game states are virtually infinite, programming a direct response to every game state is impractical. Even trying to write an algorithm to handle every input would be tedious and lead to ineffective results. For problems that the problem is too hard or too complicated for to program, programmers turn to a method known as Genetic, or Evolutionary AI. The concept is quite simple... The program actually modifies itself slightly each time it plays. Of course, there is little way for the program to know whether the changes are good or bad. To compensate, we can apply the theory of Evolution's natural selection. For our chess example, chess programs who preform well will continue to mutate while failed attempts will be discontinued. However, this would take several games of chess against a human opponent - millions, perhaps to get something worth playing. So instead, we can pit the computer programs against eachother and simulate thousands of games quickly to enhance the evolutionary process.

That is what I decided I want to do. AI Evolution is a "simple" game - 20 entities working competitively to eat food and avoid hazards that implements the Evolutionary AI technique. Entities that fare well in the round will produce children in the next round... entities that fare poorly will simply die off. I will now explain, in detail, how the game is played:

Environment:

A 20x20 grid that has a random population of food, poisoned food, walls, and hazards. Each square has a % chance to contain:
40% nothing (160 average)
45% food (180 average)
5% poisoned food (20 average)
5% hazard (20 average)
5% wall (20 average)

Goal:

To score the most points by the end of the round between 20 separate entities. Entities have several different possible precepts they can act on, and many different actions they could do given those precepts. Each precept has two different actions, a standard action and a move action. The standard action always happens before the move action. Each precept also contains Priority, a value 1 to 100, which is determined by the entity, which determines which precepts get priority over others in case both are true. In the case of a priority tie, there is a 50/50 chance which takes priority per instance.

They also each have eight separate “stats” that for each entity adds up to 400. Each stat cannot exceed 100 or go below 1. The stats are Strength, Dexterity, Constitution, Efficiency, Recovery, Charisma, Mutation, and Wisdom. For the 1st round, these entities are completely randomized.
Strength gives the entity a better chance to push other entities. When two entities come into contact, the entity with the higher Strength wins the push (after a random number between -5 and 5 is added to each contestant's Strength temporarily). The winner also steals 1 score point from the loser.
Dexterity determines how long it takes in ticks for the entity to act upon a precept. Dexterity 1 entities activate once every 5 ticks, Dexterity 100 entities activate every 1 tick.
Constitution reduces damage from poisoned food and hazards. Constitution 1 entities reduce no damage from hazards or poisoned food. Constitution 100 entities reduce damage by 75%.
Efficiency determines how long an entity can operate before requiring a rest period. Efficiency 1 entities must rest once every 3 activations. Efficiency 100 entities must rest once every 7 activations.
Recovery determines how long an entity rests for. Recovery 1 entities rest for 30 ticks, Recovery 100 entities rest for 18 ticks.
Charisma rewards extra points for eating food. Charisma 1 entities get no bonus to eating food. Charisma 100 entities receive 50% more points for eating food.
Mutation grants no bonus round to round, but does determine how fast an entity evolves between rounds. Mutation 1 parent entities have a 1% chance to change an action per precept, a 10% chance per precept to change that precept's priority, changes priority a random number from -3 to 3, a 25% chance for stats to be increased, have a chance to increase up to 2 stats, and increases stats up to 3. Mutation 100 parent entities have a 5% chance to change an action per precept, a 20% chance per precept to chance that precept's priority, changes priority a random number from -10 to 10, a 50% chance for stats to be increased, have a chance to increase up to 6 stats, and increases stats up to 10.
Wisdom represents the entity's awareness. Given a precept, there is a chance an entity does not notice the precept. Wisdom 1 entities have a 30% chance to ignore a precept. Wisdom 100 entities have a 1% chance to ignore a precept.

In general, points are rewarded for eating food (automatic, as soon as the entity enters the zone, he eats any food there). Food rewards 10 points. Some food is poisoned. Poisoned food subtracts 10 points. Hazards subtract 1 point (per ticks spent in hazard), and are not removed upon use like food. Walls and other entities are impassible. If an entity tries to enter a square that will contain or contains another entity (simultaneously), each entity has a chance to inherit the square based upon Strength. If the loser is entering the square, he remains in his current square. If the loser is currently in the square, it will move to a random adjacent square.


After 250 ticks, the round is over. Entities who score highly will be brought into the next round via children. Entities that have a low score are discarded. The 1st place scorer will receive 6 children to the next round. The 2nd place scorer will receive 4 children in the next round. 3rd will get 3, 4th and 5th will get 2. The last three will be completely random. In addition children will mutate slightly from their parents. There is a chance, based on the parent's Mutation, that a child's stats will change slightly. When a stat is increased, it is increased in value by a random number determined by parent's Mutation (Stats cannot go above 100). Then, a different random stat is reduced by the same amount (If this would put a Stat below 1, randomly choose a different stat). Next, for each precept each child has, there is a chance based on parent's Mutation the action will change to a different random action (including null action). When this happens, there is a 20% chance the precept's move action will be changed, and an 80% chance the precept's standard action. There is also a chance, based on the parent's Mutation, for each precept's priority to be increased or decreased by an amount determined by Mutation (But precept priority can still not go below 1 or above 100).

New random entities start with a random distribution to their stats from the 400 max stat pool, a random priority for each precept, and all precepts get random move and standard actions.

State:

Entities only have a few values that change over time.
They keep a Energy counter, which is based upon Efficiency at start or after rest, and decreases by 1 for each activation.
They have a Score counter, which keeps track of the entity's current Score.
They have three different Memory (Yellow memory, Blue memory, Red memory) booleans, which can be true or false (default false).
Finally, entities have a Facing variable that can equal North, South, East, or West.

Types of Precepts:

Some definitions...
Nearby means the object is within 3 squares.
Obstacles are either walls or hazards.
Food refers to both poisoned and nonpoisonous food.

General Precepts (not changed by surroundings)
  1. Default, or no precept whatsoever (priority always = 0, cannot be ignored)
  2. Finished Resting
  3. Denied movement last round
  4. Ate food last round
  5. Entity no longer nearby (after being true previous activation)
  6. Hit hazard last round
  7. Was pushed since last round
  8. Energy less than 3
  9. Food nearby (only after being false previous activation)
  10. Obstacle nearby (only after being false previous activation)
  11. Other Entity nearby (only after being false previous activation)
  12. Food no longer nearby (only after being true previous activation)
  13. Obstacle no longer nearby (only after being true previous activation)
  14. Red memory is true (only after being false previous activation)
  15. Blue memory is true (only after being false previous activation)
  16. Yellow memory is true (only after being false previous activation)
  17. Red memory no longer true (only after being true previous activation)
  18. Blue memory no longer true (only after being true previous activation)
  19. Yellow memory no longer true (only after being true previous activation)
  20. Random chance, 10%
  21. Wall at Front
  22. Wall at Left
  23. Wall at Right
  24. Wall behind
  25. Hazard at Front
  26. Hazard at Left
  27. Hazard at Right
  28. Hazard behind
  29. Food at front
  30. Food at left
  31. Food at right
  32. Food behind
  33. Entity at front
  34. Entity at left
  35. Entity at right
  36. Entity behind
  37. Nothing adjacent
  38. Wall adjacent
  39. Hazard adjacent
  40. Food adjacent
  41. Entity adjacent
  42. Poisoned Food at front
  43. Nonpoisonous Food at front

Types of Actions:

All precepts have one of the following “standard” actions:
  1. Do nothing
  2. Turn left
  3. Turn right
  4. Turn around
  5. Face towards nearest nearby food
  6. Face towards nearest nearby wall
  7. Face towards nearest nearby hazard
  8. Face towards nearest nearby entity
  9. Rest early
  10. Red memory = true
  11. Red memory = false
  12. Blue memory = true
  13. Blue memory = false
  14. Yellow memory = true
  15. Yellow memory = false
  16. Do last standard action
  17. Do random other standard action
And, in addition, all precepts have one of the following “move” actions:
  1. Move forward
  2. Move backward
  3. Strafe right
  4. Strafe left
  5. Do not move
  6. Do last move action
  7. Do random other move action
Results:

The entity builder.
Now what fun would this be if I didn't also include my findings? I ran several tests far above 500,000 games played, and each time I had different results - different ending entities. Each times, the precepts were mapped with fairly intelligent actions but they were never truly the same. There were also some trends for stats that I noticed, and found interesting. During early games, entities with stats that directly influence energy manipulation are popular. You will find many entities during this phase have a high Charisma, Constitution, and Strength. Also, about half of the time, I see that Mutation is a popular early stat since entities that evolve quickly are usually the ones who survive in the long run. However, as precepts to actions becomes more and more evolved, the stats switch to a lower Mutation (since they are getting closer and closer to perfection) and higher emphasis on intelligence and energy-manipulation stats. Creatures with a high Wisdom, Dexterity, Efficiency, and Recovery are widespread in the late game. Not all of the results I fully expected and the entities that evolved I could never really come up with myself - which was part of the idea.

I will also attach the program itself for others to play around with if they would like. I have also built an Entity Builder, programmed right in, to allow you to make your own entities and see if they can pass the test of time and compete with other entities. I've found that it is very difficult to program effective entities that will last longer than 100 games. You can also save (export) entities to view them in the Entity Builder, so there is plenty to experiment with, give it a try.

Link to download: http://www.filedropper.com/aievolution1

No comments:

Post a Comment