Contents  Introduction  Methods  Results  Conclusion  Printable version

Methods

Table 1 provides the tableau for the initial runs of the snake game. Following over twenty initial runs of the program, the maximum score that had been achieved was 123 hits. As it was apparent that a maximum solution would not be obtained using the initial function set, the function set was expanded to enhance the snake’s movement and environment sensing capabilities. For the remainder of the paper, any GP runs performed with the function and terminal sets given in Table 1 will be referred to as a run made with the "initial" function set. Any run made with the enhanced function set, which includes the complete initial function set as a subset, will be referred to as having been made with the "final" function set. A discussion of both the initial and final function sets follows.

Table 1. Tableau for Snake-Game Problem

Terminals: The terminal set chosen for the problem was right, left, and forward. Each terminal was a macro that would cause the snake to take the corresponding action during a time step as follows:

Right: the snake would change its current direction, making a move to the right

Left: the snake would change its current direction, making a move to the left

Forward: the snake would maintain its current direction, and move forward. This is the same as a no-op, as the snake must make a move during each time step.

These three terminals represent the minimal terminal set with which the snake can effectively navigate its surroundings. While some problems consisting of navigation in a two-dimensional grid can be successfully navigated by way of only one direction changing terminal, that is impractical for the snake game because the facts that the game board is enclosed and that the snake has an extended body that is impassible necessitate the ability for the snake to move in either direction in order to avoid death. More advance terminals, such as moving the snake along the shortest path to the food, were not implemented. Rather, the function set was constructed in such a manner that the GP could evolve the necessary capabilities to achieve the maximum score.

Functions: Initially the snake was given very limited functionality. One function gave it information about the location of the food, three other functions gave it information about any immediately accessible danger, and progn2 was provided as connective "glue" to allow a function tree to make multiple moves in a single pass. All functions were implemented as macros of arity two, and therefore would only execute one of their arguments depending on the current state of the game, except for progn2, which would execute both of its arguments. Even though no expressions evolved from this initial function and terminal set were able to achieve the optimum score of 211 pieces of food, this set served as a baseline by which to evaluate progress and determine enhancements the would lead to the eventual optimal solution. Following is a description of the initial function set:

ifFoodAhead: If there is food in line with the snake’s current direction, this function will execute its first argument, otherwise it will execute the second argument. This was the only initial function that gave the snake information beyond its immediate surroundings.

ifDangerAhead: If the game square immediately in front of the snake is occupied with either a snake body segment or the wall, this function will execute its first argument, otherwise it will execute its second argument.

ifDangerRight: If the game square immediately to the right of the snake is occupied with either a snake body segment or the wall, this function will execute its first argument, otherwise it will execute its second argument.

ifDangerLeft: If the game square immediately to the left of the snake is occupied with either a snake body segment or the wall, this function will execute its first argument, otherwise it will execute its second argument.

progn2: This is a connectivity function that will first execute its right argument, then its left. It is the only function that allows execution of more than one terminal in a single parse of the function tree. Although this function will always execute both of its arguments, it was necessary to implement it as a macro because of the way that the software used to make GP runs, Dave’s Genetic Programming in C (DGPC), evaluated functions vs. macros. To avoid unnecessary modification of DGPC, implementing progn2 as a macro proved the simplest option.

As mentioned previously, no GP runs performed with the initial function set were able to score greater than 123 hits. In order to increase the probability of evolving a function tree capable of achieving the maximum number of hits, the initial function set was enhanced. Functions were added to extend the snake’s capabilities for detecting food and danger, as well functions that were conditional on the snake’s current movement direction. Following is a discussion of the additional functions that, along with the initial function set, make up the final function set.

Additional Functions, all of arity 2:

ifDangerTwoAhead: If the game square two spaces immediately in front of the snake is occupied by either the wall or a segment of the snake’s body, this function will execute the first parameter, otherwise it will execute the second.

ifFoodUp: If the current piece of food on the board is closer to the top of the game board than the snake’s head, then the first parameter of this function will be executed, otherwise the second parameter will be executed.

ifFoodRight: If the current piece of food on the board is further to the right of the game board than the snake’s head, then the first parameter of this function will be executed, otherwise the second parameter will be executed.

ifMovingRight: If the snake is moving right, then the first parameter of this function will be executed, otherwise the second parameter will be executed.

ifMovingLeft: If the snake is moving left, then the first parameter of this function will be executed, otherwise the second parameter will be executed.

ifMovingUp: If the snake is moving upward, then the first parameter of this function will be executed, otherwise the second parameter will be executed.

ifMovingDown: If the snake is moving downward, then the first parameter of this function will be executed, otherwise the second parameter will be executed.

There are two characteristics of the final function set that should be given special attention. First, note that the "ifFoodUp" and "ifFoodRight" functions are direction independent, meaning that the direction in which the snake is moving has no impact on the function’s behavior. This is in contrast to the initial set of functions, such as "ifDangerAhead", in which the direction that the snake was traveling would have an impact on the return value of the function. The reason for the difference is to maintain simplicity in the function set. The snake can potentially be surrounded by danger, but there will only be one piece of food on the board at any one time. If the "ifDanger*" functions were direction-independent, then two significant complexities would be added to the problem.

1. An additional function would be required, as there would need to be one for all cardinal directions in order to account for all possible surrounding dangers. An added downfall of this complexity is that one of the "ifDanger*" functions will be virtually meaningless depending on the direction of snake’s travel, since the snake’s neck segment adjacent to the snake’s head is always an adjacent danger, although not one of any consequence to the snake, since it is unable to move back on itself.



2. Anytime an "ifDanger*" function was used, it would need the aid of a helper function, such as the new "ifMoving*" functions in order to make intelligent moves based on an assessment of the danger.

Taking the second complexity into account, the reader may now note that the same disadvantage is true of the two new functions, "ifFoodUp" and "ifFoodRight." Indeed this is true, but an important difference between the role of food and the role of danger in the game makes for a worthwhile tradeoff. The difference is that there will only be one piece of food on the board at any time. This allows the new "ifFood*" functions to serve as two functions each. To clarify, consider the ifFoodUp function. When not true, it is indicating that the food is either down, or on the same horizontal plane as the snake’s head. Now consider a hypothetical "ifDangerUp" function. If this function were not true, it would tell nothing about whether or not danger is down, because it can be anywhere simultaneously. Likewise is would not even tell whether existing danger that was "up" posed a immediate threat to the snake, as the further information of the snake’s current moving direction would need to be known, as discussed earlier. For the second special characteristic of the new functions, consider the new "ifMoving*" functions. These functions can be used as helper functions with the two new "ifFood*" functions to create beneficial schemata.

As an example of a beneficial schemata, consider "ifFoodUp(ifMovingRight(left, ifMovingUp(fwd, right))))", which will orient the snake to pursue food that is upward. As will be seen in the results section, not only does the GP learn how to use these functions in conjunction with the two new "ifFood*" functions, but they also prove useful in helping the snake discover patterns that greatly extend its life. Discussion of other schemata is given below in the description of schemata, and specific examples are given in the "Results" section.

Fitness Cases: For initial runs of the problem, only a single fitness case was used to determine the fitness for each individual. Because the food placement is random both during a single run, and from one run to another, occasionally individuals would score a number of hits because of fortuitous placement of the food, and not as much on the merit of their function tree.

To better ensure that the most successful individuals achieved high fitness measures primarily on the basis of their function tree, new GP runs were often made featuring a "primed" population in which the fitness was measured as the average of four runs of an individual. The procedure for this is as follows: once a run had completed without obtaining a solution, or if a run had stalled on a single individual for a large number (100 or more) of generations, a new run was begun with this final individual as one of the initial individuals. For this new run, however, the fitness was taken as the average fitness of an individual over four runs instead of merely a single run. The averaging of the fitness over four runs helped eliminate the possibility of an individual having a high fitness due simply to lucky placement of the food. Using this averaging method to determine fitness was only used in primed populations because it increased the time of a GP run fourfold. Furthermore, it was common for the generations that timed out to feature an individual who had scored a high fitness as a result of a lucky run. By beginning a new run with this individual in the initial population, it not only assured a more realistic fitness measure, but it introduced an entirely new mix of randomly generated schemata that could potentially benefit the stalled individual. Details of results produced by primed runs are given in the results section.

Fitness Measure: The fitness measure used is the maximum possible pieces of food eaten, 211, minus the actual number of pieces of food eaten. Furthermore, if the snake was unsuccessful at eating any food the fitness would be penalized by the number of board squares that it was from the food. This additional criterion was added to favor individuals who moved toward the food in early generations of snakes who were unable eat any food.

Parameters: Population was set to 10000. The maximum number of generations was set to 500. The size of a function tree was limited to 150 points. These parameters were chosen mainly based on available computer resources, covered in computer equipment and run-time explanation below.

Designating a result and criterion for terminating a run: The best of generation individual will be the one that is able to eat the most pieces of food. A run will end when one of three termination criteria are met:

1. The snake runs into a section of the game board occupied by a wall



2. The snake runs into a section of the game board occupied by a segment of the snake’s body



3. The number of moves made by the snake exceeds a set limit. This limit was set to 300, slightly larger than the size of the game board. This will prevent a snake from wandering aimlessly around a small portion of the board.

The reader may note that there is no termination criterion for the completely successful snake. That is because upon eating the final piece of food, the snake’s tail will grow onto its head, causing it to satisfy termination criteria 2 above. Hence even the optimal solution will end in death for the snake.

Crossover, mutation rates: Crossover of nodes was the primary genetic operator employed during the GP runs. The crossover fraction for leaves was set to .10; the crossover fraction for a node was set to .80; the mutation fraction was set to 0. Additionally, primed GP runs were used to improve genetic diversity, as described above in the description of fitness cases.

Computer equipment and run time: The majority of the computer runs were performed on a 550MHz Intel® Celeron Processor running Microsoft® Windows 98 SE Operating System. The software used was Version 2.0 of Dave’s Genetic Programming In C, and Microsoft® Visual C++ 5.0. In addition, a stand-alone simulation of the snake game was created that was able to read in the function trees produced by DGPC and graphically display a run of a particular function tree. This utility proved invaluable, as it provided a fast, visual method to determine the overall optimization strategy represented by the function tree. The alternative of hand-evaluating each function tree would have proven not only more time consuming, but much less conclusive. A complete run of 500 generations took around 20 hours to complete. Because of the length of time for each run, many runs were farmed out to separate computers, all with approximately equivalent computer power.

Schemata: Given the initial function set, there were a few highly desirable sub-tree schemata that could be produced. First, considering a minimal sub-tree of 3 points, any sub-tree that would evade impending danger by changing directions is certainly the key to survival of an individual. One such sub-tree is "ifDangerAhead(right, forward)." Secondly, a basic sub-tree that will avoid changing directions into impending danger is solely beneficial to an individual. One example is "ifDangerRight(forward, right)." The reader will note that anytime a change in direction is about to be undertaken, it would be wise to have such a check before making the move. Thirdly, a 3-pointed sub-tree that aims at pursuing the food, and modifying directions if no food is ahead, is required to give the individual more than a random opportunity to eat the food pieces. One such individual is "ifFoodAhead(forward, right)."

As explained previously, the "ifFoodAhead" function will return true for a piece of food any number of squares in front of the snake. Therefore, in addition to seeking the food, it would also be desirable for the individual to continually scan for impending danger while the food is being sought. Hence a final example of a desirable schemata is any combination of the above three examples that effectively combines the goals of each. For example, consider the following function tree of 7 points: ifFoodAhead(ifDangerAhead(right, forward), ifDangerRight(left, right)). This schema will cause the snake to pursue food ahead as long as no immediate threat is observed. If however, there is a threat or no food ahead, the sub-tree will cause the individual to change direction avoiding any observed danger, or pursuing a new vector to find food. Specific examples of the emergence of such schemata will be given in the results section.

In addition to the potential beneficial schemata, touched on above, there are also "detrimental" schemata. The detrimental schemata would be any function branch whose primary goal is to either seek danger or avoid food. Examples of detrimental schemata are essentially the converse of the previously outlined beneficial schemata, and their further consideration is left to the reader.

Certainly all schemata are not strictly beneficial or detrimental, and any such schemata will be called "neutral schemata." Consider, for example, the simple subtree "ifDangerRight(left, forward)." This function will turn left if danger is present to the right, and continue forward otherwise. This schema makes either a left or forward move without having any apparent knowledge of what lies in those directions. This could certainly prove to be detrimental, but the move to the left when danger is right is at least avoiding the danger to the right. Schemata such as this can actually prove beneficial when placed in the context of a complete function tree. An examination of actual schemata produced during the GP runs in question follows in the results section.

Next : Results