I'm just curious that has anybody used genetic programming for Game AI before? I mean I'm doing my project and I just need some experience.

I will count to 3, and you will snap out of it and realize that a GA is just a sugar-coated gradient descent.

1
2
3...

Quote: Original post by Steadtler
I will count to 3, and you will snap out of it and realize that a GA is just a sugar-coated gradient descent.

1
2
3...

Hmmm... I don't think that's true. You can use genetic algorithms in situations where the fitness can only be evaluated with lots of noise, where computing the partial derivatives of the fitness function is impossible and where the only thing you can even try to measure is the relative fitness of a setting of the parameters with respect to another setting of the parameters. As an example, tuning parameters in a poker bot has all of these difficulties that make gradient descent basically useless in this case.

That having been said, I have never actually used GAs for anything more than toy problems, and I don't see much use for them.

Although its approach is not very scientific, this program did use GAs to learn an evaluation function for checkers. It's the closest thing I know to what the OP was asking.

Notice he said "genetic programming" rather than "genetic algorithm". One modifies data, the other modifies the code itself.

Quote: Original post by InnocuousFox
Notice he said "genetic programming" rather than "genetic algorithm". One modifies data, the other modifies the code itself.

Oh, I see. "Genetic programming" is GA where the parameter space consists of programs. I don't have any examples of this in Game AI, and I doubt there are any.

Quote: Original post by InnocuousFox
Notice he said "genetic programming" rather than "genetic algorithm". One modifies data, the other modifies the code itself.

Yes, because doing a gradient descent over the space of all possible code makes much more sense that over the data space :) But yeah, I shouldnt have written GA, but my comment stands.

Quote: Original post by Alvaro
where computing the partial derivatives of the fitness function is impossible and where the only thing you can even try to measure is the relative fitness of a setting of the parameters with respect to another setting of the parameters

Doesnt that sound like a finite difference? :)

Quote: Original post by Steadtler

Quote: Original post by Alvaro
where computing the partial derivatives of the fitness function is impossible and where the only thing you can even try to measure is the relative fitness of a setting of the parameters with respect to another setting of the parameters

Doesnt that sound like a finite difference? :)

Actually, no. Imagine you are trying to optimize the strength of a poker bot. The only measure of strength you have is matching one bot against another for a number of hands and seeing who makes money off of whom. I don't see what a finite difference have to do with anything.

Quote: Original post by alvaro

Quote: Original post by Steadtler

Quote: Original post by Alvaro
where computing the partial derivatives of the fitness function is impossible and where the only thing you can even try to measure is the relative fitness of a setting of the parameters with respect to another setting of the parameters

Doesnt that sound like a finite difference? :)

Actually, no. Imagine you are trying to optimize the strength of a poker bot. The only measure of strength you have is matching one bot against another for a number of hands and seeing who makes money off of whom. I don't see what a finite difference have to do with anything.

Because of the mutation step in GAs, the other bot will most likely be a neighbor in the search space. I say most likely because GA are very loosely defined and thus can end up being just about anything.

In its most basic form, a GA takes a point, find points in the neighborhood ("mutation"), then compare those points and keep the best(s) according to some test ("fitness"/"selection"). Like I said, a sugar-coated gradient descent. The more they deviate from this formula and the more they look (and perform!) like a random search.

Thanks for you all replies. So, there is no evidence that GP has been used in Game AI before?

Hmm, That's rough for me now. Thanks everyone.

Quote: Original post by Steadtler
In its most basic form, a GA takes a point, find points in the neighborhood ("mutation"), then compare those points and keep the best(s) according to some test ("fitness"/"selection"). Like I said, a sugar-coated gradient descent. The more they deviate from this formula and the more they look (and perform!) like a random search.

I'd say that's a miscategorisation.

Firstly, you missed crossover - without that, it's not a GA. Crossover attempts to exploit correlations between the various dimensions of the data. It requires some domain-specific knowledge to write a good crossover operator and like any domain-specific knowledge, if it's accurate, it will improve the search over a naive method. (And vice versa: no free lunch, and all that.) It means that parallel searches over two different parts of the landscape can end up being combined usefully, even if the area is completely discontinuous between them.

Secondly, generic algorithms exploit information shared across the population, not just in the crossover, but in the selection system. For this reason running gradient descent 100 times is not likely to be as effective as running one (similarly specified) GA with a population of 100. In this sense a GA has far more of the characteristics of beam search. Gradient ascent is typically the optimisation of 1 value. Repeating that a few times with the best of several successor values is still just optimising 1 value. GAs attempt to optimise many in parallel. You wouldn't ever reduce your population to just 1 value until the final generation of the search.

Thirdly, what you are calling "random search" is what another person calls "avoidance of local minima/maxima". Unadorned gradient ascent is pretty useless on all but the most continuous of fitness landscapes. Adding a random sample of perturbations help to get over that, and several useful algorithms do that, not just GAs.

So yeah, there's "sugar-coating", but it all serves a purpose. GAs are a pretty good match for a problem where you have a large number of dimensions to optimise, can see there are broad relations between them, and don't have a more specific algorithm that is provably better for the fitness landscape in question.