Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

FlamePixel

Function sets and Terminal sets in GP?

This topic is 5720 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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.

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites
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}.

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!