Sign in to follow this  
noppanit

genetic programming or evolutionary algo for game AI

Recommended Posts

alvaro    21246
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.

Share this post


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

Share this post


Link to post
Share on other sites
Steadtler    220
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? :)

Share this post


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

Share this post


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

Share this post


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

Share this post


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

Share this post


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

Share this post


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

Share this post


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





Share this post


Link to post
Share on other sites
willh    160
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. :)

Share this post


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

Share this post


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

Share this post


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

Share this post


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

Share this post


Link to post
Share on other sites
Daerax    1207
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?

Share this post


Link to post
Share on other sites
alvaro    21246
Quote:
Original post by Daerax
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?


No. I thought about it for a while and I will probably get to it some day. But I have too many other projects right now and too little time to finish them. My job is getting in the way of my hobbies once again!

Share this post


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


Crossover IS a mutation operation. This is a mathematical certainty.


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


The logical conclusion of this is that all members will eventually become nearly identical. At this stage cross-over will have little effect as it becomes no different than a 'simple' mutation operation.

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

That is not necessarily true for two reasons.

1. It is very possible for a mutation operation to introduce the exact same effect as would have happened with crossover.

2. If you look at convergence as TIME spent (i.e. milliseconds) and not generations required, then having an effective crossover scheme (which may work very well for the first few generations of a population) could actually result in a decrease in convergence time. This is due to the number of poor candidate fitness evaluations that are required for each generation, resulting in wasted cycles. It's like exploring obviously dumb moves in a gametree-- wasted time with no return.

In other words, an environment having 2,000,000 members that convereged in 10 generations sounds a lot better than one that took 10,000 generations to reach the same goal-- but if the 10,000 generation one took 5 minutes and the 10 generation one took 5 hours, then they don't stack up so well.

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


We'll have to agree to disagree that crossover is required for a GA; it's not a requirement in nature so I don't see why it should be a requirement when talking of algorithms.

In practical terms I do not think it is important to always include crossover in to a framework. You could go a step further and include multiple different crossover strategies (one point, two point, etc..) but in many cases I think the effort would be better spent on implementing more intelligent mutation operators (or any number of things).

Share this post


Link to post
Share on other sites
Daerax    1207
Quote:
Original post by willh
Quote:
Original post by Kylotan
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.

That is not necessarily true for two reasons.

1. It is very possible for a mutation operation to introduce the exact same effect as would have happened with crossover.

2. If you look at convergence as TIME spent (i.e. milliseconds) and not generations required, then having an effective crossover scheme (which may work very well for the first few generations of a population) could actually result in a decrease in convergence time. This is due to the number of poor candidate fitness evaluations that are required for each generation, resulting in wasted cycles. It's like exploring obviously dumb moves in a gametree-- wasted time with no return.


mathematical certainty is a term I have always found redundant.

A genetic algorithm with no crossover is a waste of time, there is no point maintaing multiple solutions. at this point you may as well be using another algorithm, SA say.

Certainly you can look at cross over as a type of mutation just as you can look at them both as a probing blind search, randomly looking for serendipitous solutions near a point. GA are not related to nature so what you find in nature has no impact here, saying cost minimization and random combination of list elements is genetics is like saying drawing a square and building a house is the same since they both contain a four sided polygon.

Your point 2 is interesting because studies show that GA performs better for certain problems over long runs than SA (no crossover) which tends to arrive at and settle near its optimal solution quicker. A cleverly coded crossover could be the difference here, for certain problems. Although SA also sometimes outperforms GA for reasons you mention, as always there is no clear winner.

If you look at my earlier post you will see that I do not disagree with you in essence. Just in presentation. I agree that crossover is not necessary for this type of stochastic search (again , ala SA) but if your *Genetic* Algorithm doesnt do this then you have no business calling it such.

Share this post


Link to post
Share on other sites
Kylotan    9853
Quote:
Original post by willh
Crossover IS a mutation operation. This is a mathematical certainty.

The two concepts are different in the algorithmic sense. Of course it would be possible, if you wrote your mutation operation in a certain way, to alter a solution such that it could change in a similar way to applying a crossover operation. But the chance of a typical mutation creating the same change as a typical crossover would make would be tiny. The point of crossover is to make use of the information elsewhere in the population, and the point of mutation is to introduce new information. The fact that these two can possibly overlap in their result is not terribly relevant.

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


The logical conclusion of this is that all members will eventually become nearly identical. At this stage cross-over will have little effect as it becomes no different than a 'simple' mutation operation.

Yes, they typically become closer together. That's convergence, and is exactly what you're looking for. Compare to other optimisation algorithms which typically just follow a single solution from start to end - they only had 1 possible option all the time, not just near the end. And of course convergence slows down as the algorithm progresses - this too is quite common in optimisation problems. Once you home in on the optimum there is often less room to improve.

But it doesn't become the same as a simple mutation operation. Quite the opposite in fact - as the solutions converge, mutation will produce quite different results to crossover.

Quote:
2. If you look at convergence as TIME spent (i.e. milliseconds) and not generations required, then having an effective crossover scheme (which may work very well for the first few generations of a population) could actually result in a decrease in convergence time. This is due to the number of poor candidate fitness evaluations that are required for each generation, resulting in wasted cycles. It's like exploring obviously dumb moves in a gametree-- wasted time with no return.

Compare this with many other optimisation algorithms, which don't even have a game tree - they just explore one promising looking route and often need some sort of added stochastic element or restarting procedure to get them out of local extrema.

Fitness evaluations in GAs are not particularly different from heuristics in other search or optimisation algorithms. Their usefulness is proportional to the quality of the heuristic.

Selection is only as expensive as you make it, also - tournament selection is incredibly cheap for example.

Quote:
We'll have to agree to disagree that crossover is required for a GA; it's not a requirement in nature so I don't see why it should be a requirement when talking of algorithms.

Genetic algorithms use a biological metaphor to explain their constituent parts, that's all. It doesn't mean that anything that may exist in biology makes up a valid GA.

Quote:
In practical terms I do not think it is important to always include crossover in to a framework. You could go a step further and include multiple different crossover strategies (one point, two point, etc..) but in many cases I think the effort would be better spent on implementing more intelligent mutation operators (or any number of things).

Without crossover you're not sharing useful information across the population, so there is little point maintaining that population. If you have a problem where there is no useful information to share, that's fine, but I can't think of one myself. If such a problem did exist then it would probably be better to run many instances of a cheaper single-member optimisation algorithm serially rather than dressing it up as a GA.

Share this post


Link to post
Share on other sites
willh    160
While I don't agree with everything in this article, I thought it might be useful to share this bit from Wikipedia regarding Genetic Algorithm
Quote:
Wikipedia Genetic Algorithm
Reproduction
Main articles: Crossover (genetic algorithm) and Mutation (genetic algorithm)
The next step is to generate a second generation population of solutions from those selected through genetic operators: crossover (also called recombination), and/or mutation.

(Bold added for emphasis)

Daerax: I have a hard time accepting that the Genetic in Genetic Algorithm has no relation to the biological term 'Genetic'. Having read (one of) John Hollands descriptions first-hand, and the amount of space devoted to discussing biological genes, I'm pretty sure he would agree.

Quote:
Original post by Kylotan
But it doesn't become the same as a simple mutation operation. Quite the opposite in fact - as the solutions converge, mutation will produce quite different results to crossover.


For a problem where population convergence and high-fitness are both achieved at approximately the same time then I agree with you. If population convergence happens before high-fitness then I still hold that crossover essentially becomes a simple mutation operation. There has a been a lot of research put in to strategies to maintain popluation variance specifically for this reason.

Quote:

Selection is only as expensive as you make it, also - tournament selection is incredibly cheap for example.


Some problems are expensive to evaluate and there is no way around it. Complex simulations, large data crunching exercises, etc.. I think we agree at this point, we're just looking at it from different angles.


Quote:

If you have a problem where there is no useful information to share, that's fine, but I can't think of one myself. If such a problem did exist then it would probably be better to run many instances of a cheaper single-member optimisation algorithm serially rather than dressing it up as a GA.


I can think of quite a few actually. As a complex problem space is 'explored' there are times when having fewer members is more effecient. There are also times where it is neccessary to branch out and 'explore' different variations on the same theme.

In fairness, I have always included crossover in my own frameworks. I also track how often each mutuation operator causes an improvement in fitness; crossover is (almost) always the least effective.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this