Contents  Introduction  Methods  Results  Conclusion  Printable version

Results

As mentioned in the methods section, there were three types of GP runs made in an attempt to evolve a solution to the snake game: runs using the initial function set, the final function set, and primed runs, also using the final function set. The highest number of hits generated by a run using the initial function set was 123. Three separate solutions were generated using the final function set, although none of them were found to consistently generate a solution. The number of hits achieved by each solution depended on the placement of the food. It was not until the method of "priming" a run, described in the methods section, was used that a consistent solution was generated. Of ten primed runs, using various initial seeds, exactly five of them evolved a solution, all of which were consistent solutions over multiple runs. Comparatively, over twenty runs using the full function set were made, and only three of them produced solutions, none consistent.

A summary of the overall results achieved in each type of run is given in figure 3. Each line on the graph is the average of ten runs. Note that the initial and final function sets produce a roughly equivalent maximum number of hits until about generation fifty. At this point the final function set continues to improve while the initial function set levels off. By generation 200, the initial function set has virtually no improvement, while the final function set continues improving past generation 400. Because the final function set is both more complete and larger, new and more successful individuals continue to evolve while individuals produced by the initial function set max out around 100 hits. Another feature to note in figure 3 is the impressive results achieved by the primed runs. All primed runs were begun with an individual from a final function set run who had achieved at least 150 hits. When taken as the average over four runs, however, these individuals are only able to achieve about 50 hits, as shown in the first generation of the primed runs. These individuals jumpstart the population to great success, and by generation 25 the maximum number of hits has more than tripled to around 160. By generation 150 the primed runs level off to about 200 hits. Following is an evaluation of some of the most prominent strategies evolved during the various GP runs. Specific examples of individuals from each type of run are presented and analyzed, and all function trees are reduced for simplicity sake.

Zig-zagger: One strategy that was prevalent in individuals across multiple runs is what will be referred to as the "zig-zagger." These individuals would trace the board diagonally in a stair-stepper pattern until they either reached a wall or had lined the direction of their movement up with the food. Upon reaching a wall, they would change their direction as if bouncing off of the wall, and continue diagonally tracing the board in a new direction. If they were successful in aligning their movement with the piece of food, they would typically head directly toward the food, perhaps avoiding danger depending on the particular individual. Variations in zig-zaggers occurred between which directions they would head when hitting the wall, how often they would seek the food, and how they would react in enclosed situations, such as corners or heading towards food that was blocked by their body. Obviously the more successful individuals evolved traits that allowed them to avoid danger in close quarters and dodge their body when it blocked progress toward the food. One example of a zig-zagger, who was able to score a maximum of 33 hits in one particular run, is given below:

(ifFoodAhead (ifDangerLeft (right )(ifDangerRight (1forward )
     (ifDangerAhead (left )( 1forward ))))
   (ifDangerAhead (ifDangerLeft (right )(left ))
      (ifDangerLeft (ifDangerRight (forward )( 2right ))
         (progn2 (left )(right )))))

Consider initially the rightmost sub-tree of the function tree, which is given on the last line as progn2 (left)(right). This is the branch executed initially and for the majority of this zig-zagger’s run. When executed repeatedly, this sub-tree will cause the snake to move left then right, progressing diagonally across the board. For this example, the sub-tree is executed whenever there is no food ahead of the snake’s line of movement, and there is no danger in front of or to the left of the snake’s head. This continuous zig-zagging motion allows the snake to examine successive rows or columns of the board in search of the food. Because both branches of the progn2 are executed before returning to the beginning of the function tree, however, the snake will only detect the food if the second argument of the progn2, right, leaves the snake’s head in line with the food.

Once the food is directly in line with the movement of the snake’s head, the left-hand sub-tree, given on the first line above, is executed. As noted with a "1" above, the snake will continue forward if there is no danger to the left, and either there is danger to the right, or there is no danger to the right or ahead. Unfortunately for the snake, if there is no danger to the left, but danger to the right and ahead, this function tree will lead it directly into the danger ahead, noted with the first "1" above. This is exactly what happened to the snake in figure 4, shown one time step before its demise after having eaten 24 pieces of food. This snake, whose head is in (14,5), began moving towards the food in (4,5) after having released from the wall.

Finally, note that when the "right" portion of the "progn2" sub-tree causes the snake to be either facing or next to a wall, the sub-trees on the second and third line above will be executed respectively. Further investigation reveals that each of these sub-trees will cause the snake to move away from the wall in a direction that avoids danger, even in corners. In this fashion, the snake appears to "bounce" from the walls and proceed to zig-zag in an alternate direction. Two examples of this are seen at positions (17,1) and (20,5) of figure 4. In both of these cases the snake made the right turn noted with a "2" above in order to avoid the wall.

Wall-slitherer: The strategy that scored the highest out of all individuals using the initial function and terminal set is what will be referred to as the "wall-slitherer." These individuals would follow along the wall, not simply moving forward, but rather slithering back and forth between the two squares closest to the wall. Once able to align its head with the food, the individual would move away from the wall in a straight line to obtain the food. Than, when the food was eaten, successful wall-slitherers would either double-back along their own body and head for the wall or head in a random direction toward a wall. Variations on wall-slitherers occurred in the direction they would take around the wall and when they would leave the wall to pursue the food. One highly successful wall-slitherer is shown below. This individual scored a maximum of 107 hits in one particular run, and an evaluation of its important characteristics follows:

(ifFoodAhead (ifDangerAhead (left )(forward ))
   (1ifDangerAhead (ifDangerRight (left )(progn2 (right )
         (ifFoodAhead (ifDangerRight (forward )(right )))
         (ifDangerRight (forward )(right ))))
      (2ifDangerRight (ifDangerLeft (forward )(left ))
         (3ifDangerLeft (right )
            (4progn2 (left )(ifFoodAhead (ifDangerLeft (right )
                  (left ))(ifDangerRight (left ) ( 5progn2
                  (ifDangerAhead (right )(ifDangerLeft (right )(left )))
                  (ifDangerRight (forward )(right ))))))))))

In evaluating this individual, first consider the root, which consists of the "ifFoodAhead" function. For any case in which there is food ahead, the very simple left sub-tree is executed. This subtree simply checks for danger ahead and attempts to avoid it to the left if present, otherwise the snake will continue along its current movement path towards the food. While this sub-tree proves both simple and effective, the fact is clear that the individual spends the majority of its run without the food immediately ahead, which is handled by the much larger right-hand sub-tree.

While it appears much more complicated than the left-hand sub-tree, the fundamental strategy of the right-hand sub-tree is to avoid danger. This strategy is executed impressively by the three different "ifDanger*" functions, noted with 1, 2, and 3. These functions provide the roots for the three sub-trees along the right-hand side of the main function tree. The reader can verify that each of these three sub-trees contains schemata that are highly effective at avoiding any impending danger to the snake. Having already taken precautions to pursue food and avoid danger, the final sub-tree provides the snake with its wall-slithering motion, in which it spends the majority of its time.

The final sub-tree, noted with a "4" above, is rooted with a progn2. This indicates that multiple actions will be carried out every time this sub-tree is reached, which proves to be very frequently. Initially the branch will make a move to the left, which is already known to be safe. Following this move, if there is no food ahead and no food to the right, then the second progn2, noted with a "5", is reached, making for a total of three moves to be executed on this single pass of the function tree. This three-move sequence is both common and highly beneficial to the success of this wall-slitherer. In figure 5, note the snake’s body segment at (19,8). At this point in the past, the snake was facing downward and a new parse of the function tree was beginning. As no danger was immediately present, sub-tree 4 was reached and the snake turned left towards the wall. Needing to complete the second argument of the progn2, and with no food ahead or danger to the right, the progn2 at 5 was reached, which caused the snake to turn right twice, leading to the next parse of the function tree. Looking back in history through the illustration, note that the same pattern was carried out at points (19,6), (19,4), (19,2), and numerous other times in the brief potion of the snake’s run demonstrated here. This repeated slithering pattern served to maximize the amount of ground covered by the snake while minimizing the danger that its body would pose to itself. A time step prior to a fatal flaw in the snake’s movement, however, is illustrated.

As the food is in front of the snake’s head, the simple sub-tree on the left is entered. Since there is danger ahead of the snake, it will simply turn left. As shown in the illustration, this turn will lead to the snake’s death, as it hits it’s own body after having eaten 61 pieces of food. While it may seem surprising that this flaw in the left-hand function tree was not encountered sooner, the snake survives by keeping its body along the walls as much as possible. In the illustration, it is clear that the snake left the wall 57 time steps earlier in order to pursue a piece of food across the board. Once the food was eaten, the snake resumed its slither pattern clockwise around the edge of the board. Unfortunately, its body had grown so long that by the time its head was in line with the food at position (19,9) its body was still blocking its path to the food. The snakes evasion tactic of going to the left when danger is encountered with the food ahead had saved in previous similar situations because once a single successful left was made, the snake was no longer in line with the food and it would continue any necessary evasive maneuvers via the much more robust sub-trees, 1, 2, and 3. In this final, fatal case, however, the combination of the snake’s long body, its previous cross-board pursuit of the food, and the placement of the next piece of food three board squares off of the wall caused the evasive left to lead the snake directly into its own body.

Circler: After the function set was enhanced to include the further food-sensing capabilities of "ifFoodUp" and "ifFoodRight" as well as the four "ifMoving*" functions, a new strategy of behavior that evolved is what will be referred to as the "circler." These individuals would follow along the outside of the wall in a circular pattern and only leave the wall to get the food. Once they reached the food they would continue forward until they reached the wall, then they’d start to circle again. Typically they would only attempt to eat the food while moving in one particular direction. While similar to the wall-slitherer, they differ in two key ways. The first is that the circler will always remain directly next to the wall and not move back and forth like the wall-slitherer. The second is that the circler will typically only leave the wall while headed in one direction. Both of these differences are a direct result of the new functions. Before further discussion, consider the following circler, who scored a maximum of 80 hits over a single run:

(ifDangerAhead (ifDangerTwoAhead (ifDangerLeft (right )(left ))
   (ifFoodUp (ifDangerLeft (right )(2left ))(forward )))
      (ifMovingUp (ifDangerRight (ifFoodUp (forward )(3left ))(right ))
         (1forward )))

First note the leftmost branch of the function tree, in which the snake will primarily avoid danger to both the front and the left. Certainly the left-hand sub-tree, though simple, proves highly effective at achieving the snake’s primary goal of avoiding danger. Secondly, take note of the right-hand sub-tree, which is parsed whenever danger is not immediately ahead of the snake. If the snake is not moving upwards, it simply continues forward, which is already known to be a safe move. This proves to be the move that snake most commonly makes. If, however, the snake is moving upwards, and there is danger to the right, then it will turn left as soon as the food in no longer above it. The primary moves of this snake, then, are to continue forward around the outside of the board until either there is danger ahead and it turns left, or the snake is moving upwards and there is food to left, when it turns left. Note that these moves are marked 1, 2, 3 respectively in the function tree above. Hence when seen in action the snake will make a counterclockwise circular motion around the outside of the board with the top of the circle determined by the current piece of food.

Pattern Following Solution: As a final example of an evolved strategy, an individual that was able to score the maximum number of hits, 211, will be considered. All individuals who were able to score the maximum number of hits demonstrated some pattern similar to that shown in figure 2. All of these individuals took little to no consideration of where the food was on the board, but rather followed a set pattern that would cover the entire board, eventually causing them to eat the food. Furthermore, the pattern they followed would be continuous, meaning that their head would eventually reach its original starting position, allowing the pattern to continue indefinitely. One such pattern follower, produced in generation 27 of a "primed" run, is given below:

(ifDangerRight (ifDangerAhead (ifDangerTwoAhead (8left )
      (forward ))(ifMovingRight (6left )( 4,7forward )))
   (ifDangerAhead (ifDangerLeft (ifFoodUp (right )(right ))
         (ifDangerTwoAhead (left )(forward )))
      (ifMovingUp (ifDangerTwoAhead (ifFoodAhead (ifMovingRight
            (3right )( 9forward ))
         (ifMovingDown (left )( 2right )))
            (1progn2 (forward )(forward )))
               (ifMovingRight (right )(forward )))))

This individual followed a pattern exactly the same as that shown in figure 2. There were only a few minor deviations from the pattern that would occur during very infrequent states of the game board. Before considering any such deviations an examination of the major pattern following steps will be made.

The overall pattern followed by the individual above is as follows, with the movement steps noted by superscripts on the individual. To simplify the analysis consider that the snake has already eaten enough food to be as long as the board is high, 11 segments, and that the snake is currently moving upward with its head at position (2,10) of the board:

1. While moving upward, if there is not danger two ahead, move forward twice.
2. Once there is danger two ahead, turn right; snake now moving right one row from the top of the board.
3. Turn right again, to begin heading downward.
4. Continue moving downward until there is danger directly ahead.
5. Once there is danger ahead, turn left; snake now moving right at the bottom of the board.
6. Turn left again and return to step one until there is danger to the right of the snake.
7. Danger right indicated the final right-hand column, so the snake now moves up until danger is one ahead.
8. Once there is danger ahead, turn left to follow the top row of the board (4,7) while moving left; repeat this same step to move down the left-hand side of the board, and when the bottom of the board is reached, return to step 5.

While it is clear that by repeatedly following this pattern the snake will continually trace the whole board, causing it to eat at least one piece of food on each pass of the board, there is one notable exception from the pattern that is made whenever the food is in the top row of the board and the snake is moving upward toward it. In this rare case, when step 2 of the pattern is reached, rather than turning right, the snake will continue forward to eat the food, as noted with a "9" in the function tree. When this case occurs the snake will resume the pattern to the right following its consumption of the food. If, however, this case occurs too far to the right and the snake’s body is long enough, the snake can trap itself on the right side of the board, causing it to die. This is the only way that the way that the individual shown above will not successfully eat 211 pieces of food.

Next : Conclusion