I have programmed some basic genetic algorithms in c++, and I ran across the article here at gamedev about applying GP to the snake game(Nokia cell phone game) to make an AI snake that eats the maximum number of eggs. I understood it, except where it talked about the function set and the terminal set. I understand the concept of these, but I am not sure how to implement them. Can anyone give me some insight (or even better, code) that could shed some light on this? Thank you.

If you use a dialect of Lisp as in the article it''s essentially implemented for you. C++ is far from the best tool for this application.

quote: Original post by Dobbs
If you use a dialect of Lisp as in the article it''s essentially implemented for you. C++ is far from the best tool for this application.

I agree that GP is a lot easier in LISP, but it still isn''t entirely trivial.

Function and Terminal sets are just that - the function set is all the functions that can be used by the GP and the terminal set contains all the terminals(end points).
Think of it like a tree, each function is a branch point and each terminal is a leaf.

In the case of the snake control program, the terminals are the commands that tell it to move in a certain direction, and the function set consists of conditionals (if _ then do A, else do B), but you can have a more complex function set. For example, in some image-create GP applications, the function set consists of sin, cosine, aritmatic operators (+-*/), exponential operators, and logarithm and the terminal set contains numbers and variables {like the current x or y coordinate in the image}.

Ok for an implementation in C++... the function set would be a bunch of functions with the signature:

bool (*func) (Snake)

Those are functions that take a Snake as an argument, examine it and its surroundings somehow (eg is there an obstacle directly in front of the Snake?) and return a boolean value. The terminal set would be a bunch of function pointers with the signature:

void (*func) (Snake)

Those functions would modify the Snake in some way (eg make it turn left, turn right, or keep going).

Now you make a binary tree of function pointers. The non-leaf nodes should point at a function in the function set. The left branch should be traversed if the function returns true, otherwise the right branch should be traversed. Leaf nodes should point at a function in the terminal set. To use the tree you just traverse it logically, starting by evaluating the function at the root node and branching left or right accordingly. Continue until a terminal node is reached.

To do genetic work with the trees you can either modify the structure of the tree itself (add branches, remove them, swap them with other trees) or you can modify the function pointers (change a turnLeft terminal to a turnRight terminal).

[edited by - Dobbs on April 21, 2003 3:56:41 PM]

Thank you all. This really helps. I can''t wait to start programming it!