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 1^st 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)

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