http://members.optusnet.com.au/ksaho/algorithm/GeneticAlgorithm.jar
It’s VERY slow.
Don’t put in any silly values.
What do you guys think?
What does it do? ??? A little description wouldn’t go amiss.
The algorithm advances the chromosomes throughout the generations.
This is what I’m trying to get practical with. In games I want to use this.
Currently I have very little experience with it.
I want to use GA to be able to pathfind first.
The trick is how?
Any tips on improving the performance?
You really don’t want to use a GA to do pathfinding, it’s about as poorly fitting for the problem as you can get. GAs work best with big ‘fuzzy’ problem spaces where you’re trying to find some optimal configuration. Besides, pathfinding is a (largely) solved problem with methods which will be guranteed to produce the optimal answer in a finite amount of time - something no GA is going to be able to do.
So GAs are good for general AI such as that in a FPS or an RTS?
How do neural nets compare in that regard?
A Genetic Algorithm (GA) is a search optimization technique. It is mostly used to find the optimal or near-optimal solution to a problem. If the problem is path finding, then each individual in the population has to represent a solution to the path finding problem. But in order to find that optimal or near-optimal solution, each individual has to be tested and that will represent one generation. It may take hundreds or even thousands of generations to find the best solution.
I’m working on a similiar situation. I’m currently working on a Real-Time AI Animation of a spacecraft flying through an asteroid belt. I planned to use a neural flight controller that is optimized by a GA. The initial optimization will run off-line to find the best set of weights for the neural network. Then the neural network would be used during the animation/simulation. Consider using your GA to optimized either the weights or the topology of a neural network in an offline process. That neural network could be part of your path finding algorithm used during your game once the neural network is optimized.
Just my two cents
Thanks.
It’s funny how you use the term “search optimisation”.
Maybe it’s just my algorithm that’s slow?
Source is inside the jar if anyone’s interested.
Basically you’re saying neural nets can be used in conjunction with a GA to find an optimal solution to the problem?
What can be classed as a fuzzy problem?
Winning a game of naughts and crosses?
This has been done for quite some time now. For example a neural network is used to control a cart-pole system where a pole is hinged to a cart on a track. Input into the neural network would be the angle of the pole with respect to the y-axis, the angular speed of the pole, the position of the cart on the track with respect to the x-axis, and the speed of the cart. Output from the neural network is the force applied to either side of the cart to keep the pole balanced. The individuals in the GA can represent either the weights of the network or the topology of the network. The GAs responsibility will be to search for the individual that can balance the pole the longest. Letting time be the fitness score for the individuals.
I personally believe that fuzzy logic, neural networks and genetic algorithms can be used to make a strong AI Engine. But a powerful processor is required for such an AI engine.
EP is particularly good at playing games as a human player would. It is not a panacea for implementing the game itself (and is generally useless or worse than useless at that job).
EP imitates humans; unsurprising, therefore, that it’s only really good at … imitating humans.
The things EP generally needs in the problem in order to do really well are:
- no single perfect solution, nor any single always-best tactic (if so, WTF are you wasting time with EP for?)
- lots of solutions that seem pretty good given any particular scenario within the game, but different scenarios cause different sets of possible solutions, and different weightings of them
- fine-grained feedback on how successful the player is with their current strategy (score in a shmup is a good one, number of resources in an RTS is absolutely awful - high resources does NOT mean they are currently doing well!)
Thanks blah cubed.
I guess I shouldn’t try to have a genetic algorithm create the game itself.
jfelrod1960, that is quite an interesting way of using GA.
I would like to start off letting my GA play Naughts and Crosses.
What would be the fitness?
At this current time I really can’t think of a way to implement a GA to do what I want.
Is there any place where I can get ideas about implementations?
Noughts-and-crosses is best brute-forced. GAs really need lots of different variables to track, the ultimate effects of which aren’t immediately obvious to the creator.
Avoid “procedural” solutions - aim for something where a number of variables dictate the approach that needs to be taken to solve a problem, like the balancing act described above.
I’ve just re-read the pole GA example.
What gets my goat is how can each gene represent a solution if I don’t know any solutions to the problem?
Currently I’ve thought about what to use my GA for, a card game. Something like Magic the Gathering style.
They would be good for playing M:tG, yes. Although thats sufficienlty complicated and multi-valued that you’d need fairly massive computing power to get any decent programs.
jfelrod1960 :
Thanks.
Currently reading Artificial Intelligence by Muchael Negnevitsky and the book is quite vague about GA.
Blah^3:
How big of a system do you think I’d need to have a GA playing M:TG?
I’d hate to think that my A64 3000+ will be playing M:TG at 1fph.
You would probably want something like 200 islands with a thousand or maybe 5-10k individuals per generation.
Maybe a few k generations to get a vaguely interesting deck?
But that assumes you’ve already got an algorithm that plays the game optimally given a deck; if you’re making algorithms taht both play the deck and select it, I’d say you probably have to quadruple the population size, maybe mroe.
Those pop sizes may also turn out to be out by a factor of 10, potentially.
So, the question becomes: how long does it take you to run a few billion games of magic (to get a “vaguely interesting” deck)?
I’ve just had a good idea.
GAs for the Java VM.
The JVM is complex enough and an optimised GA could make improve performance over the current VM.
Of course computers will need to increase in performance before the benefits outwiegh the cons.
When I complete my Epic World-Beating Masterpiece ™ in which the majority of the gameworld will be automatically generated (this is a plan I will be completing either when I grow up or when I suddenly and inexplicably become rich and have loads of time on my hands) I plan to use GA stuff for some of the AI development but I would only ever think to use it in scene-setting rather than in-game. I can’t even think of a way it could be used in-game, but I may be entirely unimaginative in this respect.
You can inline the GA’s loops within the game loop.
You can iterate through generations v = S/t.
With a little bit of fiddling you can achieve marvellous performance with a GA in real time.
But how could it be used?