crossover just mean you look for values in the neigborhood of two samples - and gradient descent/hill climbing was never limited to only running one at a time. Im not saying hill climbing is good, Im just saying GAs are not any better. It runs pretty much the same and attempt to patch the same flaws with doubtful hacks.


noppanit, sorry about the crossfire here. Im suggesting you study the basis - including operational research and numerical algorithms - until you see why its a bad idea. Besides the argument above about whether its anything better than a hill climbing, there are other reasons not to use it in game AI - notably the difficulty (some would say impossibility) of debugging and tuning the behavior of the AI when its all based on a regression.

Quote: Original post by Kylotan
Firstly, you missed crossover - without that, it's not a GA.

Crossover is just another form of mutation. While I agree that you need some domain specific knowledge to make crossover work effectively, the same can be said of mutation operators-- a bit of domain specific knowledge can make mutation operations much more likely to be effective.

To say that crossover is only another form of mutation is close, but an over-simplification. And, yes, proper domain knowledge is essential to designing a proper crossover operator.

To say that crossover is just looking for values within the neighborhood is a gross misunderstanding of the crossover operator.

Quote: Original post by noppanit
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.

Do you specifically mean "genetic programming" only? As in (quoted from genetic-programming.org, which is probably where you should start looking):

Quote: "Genetic programming (GP) is an automated method for creating a working computer program from a high-level problem statement of a problem. Genetic programming starts from a high-level statement of “what needs to be done” and automatically creates a computer program to solve the problem."

But in the thread title you say "or evolutionary algo" which opens it up to neuroevolution, genetic algorithms, etc... for which there are probably hundreds of AI-related research papers out there and a few games/demos.

http://en.wikipedia.org/wiki/Evolutionary_algorithm

^ Lots of approaches fall under the general category of evolutionary algorithms.

A bit of a stretch, but there does exist an example of a GA (thats not what he called it) used in game AI.

http://www.aliciapatterson.org/APF0704/Johnson/Johnson.html

To quote from the article:
"Then, through a process not unlike genetic evolution, it modifies and combines them into more complex ideas. As structures develop, the most useful and interesting ones-judged according to standards encoded in the program-survive"

Interesting story either way. :)

You could also take a look at the many different techniques developed by Ken Stanley - http://www.cs.ucf.edu/~kstanley/

Everybody around here should LOVE his work - evolution of neural networks. </sarcasm>

Regardless, he presents much of his work within a game domain and has shown some very interesting results.

Quote: Original post by willh

Quote: Original post by Kylotan
Firstly, you missed crossover - without that, it's not a GA.

Crossover is just another form of mutation.

No, it's not.

Crossover and mutation both change the solutions to explore the search space but they are completely distinct in their purpose, which is why you can't leave one out and talk as if you're still using a GA, any more than you could leave out a heuristic and claim you're still using A*.

Mutation alters part of a candidate solution in arbitrary ways, without any reference to other members of the population. It is there for overcoming local extrema and to improve the current value in gradual or limited ways. It adds new information into the population and is necessary for exploration and exploitation of the fitness space.

Crossover generates no new information as such, but replaces part of the current solution with a corresponding part from another member of the algorithm's population. That member of the population is chosen using some routine that favours members with higher fitnesses. Therefore the parts of the solutions that are better persist unchanged into future generations. This is critical as it speeds up convergence, which is its primary purpose - it takes 2 solutions which have often optimised different dimensions of the problem and combines them into 1 solution. Mutation alone cannot do this.

Genetic algorithms require crossover, mutation, and selection. Without implementing crossover properly you've pretty much crippled selection too and all you're left with is a mostly random form of beam search, which of course is going to be worse than pretty much any other algorithm you might throw at it. If that is how people use GAs then it is not at all surprising that they get poor results.

Quote: Original post by Kylotan

No, it's not.

Crossover and mutation both change the solutions to explore the search space but they are completely distinct in their purpose, which is why you can't leave one out and talk as if you're still using a GA, any more than you could leave out a heuristic and claim you're still using A*.

Mutation alters part of a candidate solution in arbitrary ways, without any reference to other members of the population. It is there for overcoming local extrema and to improve the current value in gradual or limited ways. It adds new information into the population and is necessary for exploration and exploitation of the fitness space.

Crossover generates no new information as such, but replaces part of the current solution with a corresponding part from another member of the algorithm's population. That member of the population is chosen using some routine that favours members with higher fitnesses. Therefore the parts of the solutions that are better persist unchanged into future generations. This is critical as it speeds up convergence, which is its primary purpose - it takes 2 solutions which have often optimised different dimensions of the problem and combines them into 1 solution. Mutation alone cannot do this.

Genetic algorithms require crossover, mutation, and selection. Without implementing crossover properly you've pretty much crippled selection too and all you're left with is a mostly random form of beam search, which of course is going to be worse than pretty much any other algorithm you might throw at it. If that is how people use GAs then it is not at all surprising that they get poor results.

^^^^^this X2

noppanit do you mean genetic programming or genetic algorithm? One is really cool and probably not very practical. yet. The other is a pretty straight forward technique with a cool name.

Quote: Original post by Kylotan

Quote: Original post by willh

Quote: Original post by Kylotan
Firstly, you missed crossover - without that, it's not a GA.

Crossover is just another form of mutation.

No, it's not.

Crossover and mutation both change the solutions to explore the search space but they are completely distinct in their purpose, which is why you can't leave one out and talk as if you're still using a GA, any more than you could leave out a heuristic and claim you're still using A*.

Mutation alters part of a candidate solution in arbitrary ways, without any reference to other members of the population. It is there for overcoming local extrema and to improve the current value in gradual or limited ways. It adds new information into the population and is necessary for exploration and exploitation of the fitness space.

Crossover generates no new information as such, but replaces part of the current solution with a corresponding part from another member of the algorithm's population. That member of the population is chosen using some routine that favours members with higher fitnesses. Therefore the parts of the solutions that are better persist unchanged into future generations. This is critical as it speeds up convergence, which is its primary purpose - it takes 2 solutions which have often optimised different dimensions of the problem and combines them into 1 solution. Mutation alone cannot do this.

Genetic algorithms require crossover, mutation, and selection. Without implementing crossover properly you've pretty much crippled selection too and all you're left with is a mostly random form of beam search, which of course is going to be worse than pretty much any other algorithm you might throw at it. If that is how people use GAs then it is not at all surprising that they get poor results.

excellent post! one qualm, GA without cross over is not really crippled and is really not so different from Simulated Annealing - the latter of which I have used to tune an SVM with good result - just with a slightly less interesting way of providing a mutation probability. The superiority of maintaining more than one solution is not so clear cut and is arguably detrimental in certain cases. but I agree with you and definitely smart construction of a crossover operator is very key and non trivial.

If your genetic algorithm implementation appears no different to gradient descent then you have thrown out the baby with the bath water, especially since basic gradient descent is so sickly.

Quote: Original post by alvaro
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.

off topic but are you making a poker bot?