Contents  Introduction  Methods  Results  Conclusion  Printable version

Abstract: This paper describes the evolution of a genetic program to optimize a problem featuring task prioritization in a dynamic, randomly updated environment. The specific problem approached is the "snake game" in which a snake confined to a rectangular board attempts to avoid the walls and its own body while eating pieces of food. The problem is particularly interesting because as the snake eats the food, its body grows, causing the space through which the snake can navigate to become more confined. Furthermore, with each piece of food eaten, a new piece of food is generated in a random location in the playing field, adding an element of uncertainty to the program. This paper will focus on the development and analysis of a successful function set that will allow the evolution of a genetic program that causes the snake to eat the maximum possible pieces of food.

Introduction and Overview

Artificial intelligence (AI) techniques have been proven highly successful at the problems of navigation, task prioritization, and problem avoidance. Traditionally, humans have encoded rule-based AIs to create the behaviors necessary to allow an automaton to achieve a specific task or set of tasks. Genetic programming (GP), however, has been proven to allow a computer to create human-competitive results. Specifically, examples such as the wall-following robot (Koza 1992) and Pac Man® (Koza 1992) demonstrate the effectiveness of GP at evolving programs capable of navigation and task prioritization behaviors which are competitive with human-produced results.

In an original approach to demonstrating the effectiveness of GP at producing human-competitive results, this paper describes the evolution of a genetic program that can successfully achieve the maximum possible score in the "snake game." The problem posed by the snake game is of particular interest for two main reasons. First, the size and shape of the area through which the main game character, the snake, can move is constantly changing as the game progresses. Second, as the snake eats the single available piece of food on the game board, a new piece is generated in a random location. Because of these two factors, the snake game presents a unique challenge in the developing of a function and terminal set to allow GP to evolve an optimal solution that is generalized for successive runs of the snake game.

The "Background" section of this paper outlines the rules and discusses the specific details of the "snake game." Next, "Statement of the Problem" explains the problem being addressed by this paper. The "Methods" section provides the GP specifics of how the problem was approached. The "Results" section gives numerous examples of results produced by the GP runs along with a discussion and analysis of those results. The "Conclusion" section summarizes the ultimate results achieved by the paper. The "Future Work" section discusses potential for further study in line with the work discussed in this paper. Finally, the "References" section provides a bibliography for the paper.

Background

The "snake game" has been in existence for over a decade and seen incarnations on nearly every popular computing platform. The game begins with a snake having a fixed number of body segments confined to a rectangular board. With each time step that passes, the snake can either change direction to the right or left, or move forward. Hence the snake is always moving. Within the game board there is always one piece of food available. If the snake is able to maneuver its head onto the food, its tail will then grow by a single body segment and another piece of food will randomly appear in an open portion of the game board during the next time step. The game ends when the snake’s head advances into a game square that is filled with either a snake body segment, or a section of the wall surrounding the game board. From a task prioritization standpoint, then, the snake’s primary goal is to avoid running into an occupied square. To the extent that this first priority is being achieved, its second priority is to pursue the food.

The version of the game used for this paper, shown in figure 1, is a replica of the game as it currently exists on Nokia cell phones. In this version, which is available for play online at www.nokia.com/snake, the game board is made up of 220 total squares, 20 horizontal and 11 vertical, and the food begins in position (11,6) on the game board, represented by a diamond in the figure. The snake is initially made up of 9 body segments, occupying positions (1,11)-(9,11) on the board, with the head in position (9,11) and the snake moving to the right, represented by the arrow in the figure. The maximum number of pieces of food that can be eaten is the size of the game board minus the initial size of the snake. With the given parameters, then, this equates to 220-9=211 pieces of food. This is because with each piece of food eaten, the snake grows by a body segment, reducing the amount of free space in which it can move. Hence when it has eaten 211 pieces of food, its body will fill the entire game board, rendering any further movement impossible. One critical piece of information is whether or not it is even possible for the snake to eat the maximum amount of food. Indeed it is conceivable that after eating a certain amount of food, the snake will have grown so large that it restricts itself from access to a portion of the board. Upon close inspection, however, the reader will note that by tracing certain patterns repeatedly over the board, it is possible for the snake to cover every square exactly once and return to its initial position. One such pattern is shown in figure 2, which features a snake of 210 body segments about to eat the final piece of food. Hence by continually tracing the pattern shown, the snake can eat the maximum possible pieces of food.

In evolving a genetic program to successfully eat the maximum amount of food, a human competitive solution, in terms of score, will have been obtained. With that in mind, there are some important differences in the game when being played by a human as opposed to a computer-generated program.

For a human player, the fact that the snake is always moving adds an element of pressure, forcing him/her to make decisions in a timely manner. When using a computer to play the game, this is not a concern, as the computer will have the time between each move to parse through a program tree and determine the next move. The nearest equivalent to "pressure" for a computer is any limitation imposed on the size and depth of the genetic program’s function tree. These limitations restrict the possible number of decision trees that can be generated, thereby ensuring that the computer will have a finite amount of time in which to determine the next move for the snake. The particular function tree limitations imposed for this problem will be discussed in the following "methods" section.

Statement of the Problem

The fundamental problem of the snake game is to eat the maximum number of food pieces before "dying" by running into either a wall or a segment of the snake’s body. The problem being addressed in this paper is to provide a function and terminal set that will allow for the evolution of a GP that will maximize the number of food pieces eaten by the snake. The maximum goal for the particular configuration of the snake game used in this paper is 211 pieces of food.

Next : Methods