Java-Gaming.org Hi !
Featured games (83)
games approved by the League of Dukes
Games in Showcase (522)
Games in Android Showcase (127)
games submitted by our members
Games in WIP (590)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1] 2
  ignore  |  Print  
  My working Genetic Algorithm  (Read 6487 times)
0 Members and 1 Guest are viewing this topic.
Offline K.I.L.E.R

Senior Devvie




Java games rock!


« Posted 2005-08-25 10:06:25 »

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?

Vorax:
Is there a name for a "redneck" programmer?

Jeff:
Unemployed. Wink
Offline Orangy Tang

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


« Reply #1 - Posted 2005-08-25 11:30:28 »

What does it do? Huh A little description wouldn't go amiss.

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Offline K.I.L.E.R

Senior Devvie




Java games rock!


« Reply #2 - Posted 2005-08-25 12:38:09 »

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?

Vorax:
Is there a name for a "redneck" programmer?

Jeff:
Unemployed. Wink
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Orangy Tang

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


« Reply #3 - Posted 2005-08-25 13:05:50 »

I want to use GA to be able to pathfind first.
The trick is how?

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.

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Offline K.I.L.E.R

Senior Devvie




Java games rock!


« Reply #4 - Posted 2005-08-25 13:39:21 »

So GAs are good for general AI such as that in a FPS or an RTS?
How do neural nets compare in that regard?

I want to use GA to be able to pathfind first.
The trick is how?

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.

Vorax:
Is there a name for a "redneck" programmer?

Jeff:
Unemployed. Wink
Offline jfelrod1960

Junior Devvie




Use the source Luke, use the source!!!


« Reply #5 - Posted 2005-08-25 14:48:13 »

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

Jeffrey F. Elrod
Complexsive Systems
Offline K.I.L.E.R

Senior Devvie




Java games rock!


« Reply #6 - Posted 2005-08-26 05:28:22 »

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?


Vorax:
Is there a name for a "redneck" programmer?

Jeff:
Unemployed. Wink
Offline jfelrod1960

Junior Devvie




Use the source Luke, use the source!!!


« Reply #7 - Posted 2005-08-26 06:15:06 »

Basically you're saying neural nets can be used in conjunction with a GA to find an optimal solution to the problem?

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.

Jeffrey F. Elrod
Complexsive Systems
Offline blahblahblahh

JGO Coder


Medals: 1


http://t-machine.org


« Reply #8 - Posted 2005-08-26 09:14:19 »

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!)

malloc will be first against the wall when the revolution comes...
Offline K.I.L.E.R

Senior Devvie




Java games rock!


« Reply #9 - Posted 2005-08-26 09:44:41 »

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?

Vorax:
Is there a name for a "redneck" programmer?

Jeff:
Unemployed. Wink
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline cfmdobbie

Senior Devvie


Medals: 1


Who, me?


« Reply #10 - Posted 2005-08-26 11:52:50 »

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.

Hellomynameis Charlie Dobbie.
Offline K.I.L.E.R

Senior Devvie




Java games rock!


« Reply #11 - Posted 2005-08-27 11:47:55 »

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.

Vorax:
Is there a name for a "redneck" programmer?

Jeff:
Unemployed. Wink
Offline blahblahblahh

JGO Coder


Medals: 1


http://t-machine.org


« Reply #12 - Posted 2005-08-27 13:04:24 »

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.

malloc will be first against the wall when the revolution comes...
Offline jfelrod1960

Junior Devvie




Use the source Luke, use the source!!!


« Reply #13 - Posted 2005-08-28 03:20:03 »

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.

I suggest you read Genetic Algorithms and Neural Networks by D. Whitley.

This may help.

Jeffrey F. Elrod
Complexsive Systems
Offline K.I.L.E.R

Senior Devvie




Java games rock!


« Reply #14 - Posted 2005-08-28 03:26:36 »

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.

Vorax:
Is there a name for a "redneck" programmer?

Jeff:
Unemployed. Wink
Offline blahblahblahh

JGO Coder


Medals: 1


http://t-machine.org


« Reply #15 - Posted 2005-08-28 11:02:29 »

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)?

malloc will be first against the wall when the revolution comes...
Offline K.I.L.E.R

Senior Devvie




Java games rock!


« Reply #16 - Posted 2005-08-29 08:32:06 »

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.

Vorax:
Is there a name for a "redneck" programmer?

Jeff:
Unemployed. Wink
Offline Breakfast

Senior Devvie




for great justice!


« Reply #17 - Posted 2005-08-30 22:38:20 »

When I complete my Epic World-Beating Masterpiece (tm) 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.
Offline K.I.L.E.R

Senior Devvie




Java games rock!


« Reply #18 - Posted 2005-08-31 05:18:53 »

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.


When I complete my Epic World-Beating Masterpiece (tm) 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.

Vorax:
Is there a name for a "redneck" programmer?

Jeff:
Unemployed. Wink
Offline Breakfast

Senior Devvie




for great justice!


« Reply #19 - Posted 2005-09-01 20:35:23 »

But how could it be used?
Offline K.I.L.E.R

Senior Devvie




Java games rock!


« Reply #20 - Posted 2005-09-01 23:28:17 »

Are you talking about how a GA could be used?
Sorry misinterpreted and misread your post.

How it can be used will heavily depend on your game.
I'm not going to know where it can be used unless you give out all the details.

But how could it be used?

Vorax:
Is there a name for a "redneck" programmer?

Jeff:
Unemployed. Wink
Offline Raghar

Junior Devvie




Ue ni taete 'ru hitomi ni kono mi wa dou utsuru


« Reply #21 - Posted 2005-09-03 18:06:24 »

Did you seen this?

http://www.well.com/~xanthian/java/TravellerDoc.html
Offline Breakfast

Senior Devvie




for great justice!


« Reply #22 - Posted 2005-09-03 21:09:32 »

Yes, that was my point. I was wondering what type of in-game problems could besolved by applying GA techniques that wouldn't be easier to solve another way.

I'm not thinking about any particular game but in terms of the type of problem you encounter in game construction I was finding it very hard to see how GAs could be used to solve them.

It occurs to me that it would be possible in an Action RPG or similar to use genetic techniques to choose enemy strategies, pushing enemy behaviour towards previously successful methods and making the game more challenging as a user progresses, so that's one example. Any others welcome...
Offline K.I.L.E.R

Senior Devvie




Java games rock!


« Reply #23 - Posted 2005-09-04 04:18:22 »

Tactical simulation in any shooter or action RPG.

Counter Strike Source could even benefit from a GA.
You could use a GA to determine what's the best pattern of attack based on previous results.
IE: Dust, everyone loves to defend the 3 enterances, however majority of humans tend to gang up in a single area.

I don't think CS:S would benefit from it with the current maps because they don't allow much variation due to size.

Vorax:
Is there a name for a "redneck" programmer?

Jeff:
Unemployed. Wink
Offline ryanm

Senior Devvie


Projects: 1
Exp: 15 years


Used to be bleb


« Reply #24 - Posted 2005-09-04 11:39:17 »

I remember an article in Edge a few years ago about a company that was making a Ferrari-licenced racing game. They were using neural nets as driver AI. Each generation was given some track time, and then scored on how far they got around the track.
Eventually, the AI drivers were putting in lap times only a few seconds short of the developers themselves.

At any rate, the developer subsequently went bust, or was bought out and the project aborted, or Ferrari pulled the licence, or some such depressing fate.

Another interesting example is the SodaRace competition. In this, humans and computers vie to create the fastest-moving structure. IIRC, the GA-based solutions quickly began exploiting flaws in the physics system, creating unstable structures that would "explode" accross the screen.
Offline Orangy Tang

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


« Reply #25 - Posted 2005-09-04 11:48:08 »

IIRC, the GA-based solutions quickly began exploiting flaws in the physics system, creating unstable structures that would "explode" accross the screen.
This always tends to happen with GA solutions.. two occurences of note:

- An artificial life simulator of a friends with some simple animals. The GA was used to evolve a 'balanced' eco system where no one species would dominate. Unfortunatly one of the earliest solutions evolved 'rocks' - all the animals figured that if they stayed still they never expended energy so could live forever.

- I was evolving a simple football AI to play an equally simple game of football. After some time one team started flicking the ball straight up from the center, then heading it into the goal, scoring every time. I still don't know how this happened, as the only availible action was pass and shoot. Shocked After tweeking the behaviour of the pass interception code, this magically went away...

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Offline Mark Thornton

Senior Devvie





« Reply #26 - Posted 2005-09-04 18:55:16 »

IIRC, the GA-based solutions quickly began exploiting flaws in the physics system, creating unstable structures that would "explode" accross the screen.
This always tends to happen with GA solutions.. two occurences of note:
It is common with optimisation algorithms of all types --- flaws in the model get exploited in unexpected ways.

I remember a case where someone decided to improve performance by rounding times to integer minutes. The theory being that in the real world times to the nearest minute be easily accurate enough. Unfortunately the algorithm being used was minimising time and thus tended to choose values which had been rounded down. It was necessary to work in seconds to eliminate unwanted artifacts.
Offline Raghar

Junior Devvie




Ue ni taete 'ru hitomi ni kono mi wa dou utsuru


« Reply #27 - Posted 2005-09-05 00:30:16 »

GA are used only when no reasonable other solution exist. Such algorithms might have some simillarities with GA, but often are/should be optimalized to don't have problems with speed/memory.
Memory overhead of GA could be drastical. 1000:1 in comparison to reasonable algorithm. CPU demands are high too. So one way how they could be used is pregeneration of some solutions on developer's computer. In this way speed problems are reduced, and memory demands are lower as well.

Fitting function could be an another problem with GA. While some problems have easily defineable fitting function, others are more easily solvable than a programer could create a function that could decide if that solution was optimal, or not.  Actually sometimes is hard to create a function that just reasonably aproximate effectivity of a solution.

Funny thing is that some GA methods are based upon myths created from Darwinism, and also on some racism.

If you'd look at that link I typed few posts ago, you could find another problems with GA. Being stuck in local optimum.
Offline K.I.L.E.R

Senior Devvie




Java games rock!


« Reply #28 - Posted 2005-09-05 04:15:32 »

"Being stuck in local optimum."

That's not a problem when it comes to complex games.
Humans are lucky if they can even reach a local optimum under most circumstances.

Multi-core CPUs could increase the effectiveness of a GA.
One CPU core would be playing the game, the other doing an evolutionary AI, maybe even training an AI(run on core 1) over time.

Vorax:
Is there a name for a "redneck" programmer?

Jeff:
Unemployed. Wink
Offline Riven
« League of Dukes »

« JGO Overlord »


Medals: 835
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #29 - Posted 2005-09-05 07:27:50 »

"Being stuck in local optimum."

That's not a problem when it comes to complex games.
Humans are lucky if they can even reach a local optimum under most circumstances.

What makes you think that local optimum is anywhere near what a human is capable of? That local optimum might as well be running into a wall for most of the time.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Pages: [1] 2
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

trollwarrior1 (29 views)
2014-11-22 12:13:56

xFryIx (71 views)
2014-11-13 12:34:49

digdugdiggy (50 views)
2014-11-12 21:11:50

digdugdiggy (44 views)
2014-11-12 21:10:15

digdugdiggy (38 views)
2014-11-12 21:09:33

kovacsa (62 views)
2014-11-07 19:57:14

TehJavaDev (67 views)
2014-11-03 22:04:50

BurntPizza (64 views)
2014-11-03 18:54:52

moogie (80 views)
2014-11-03 06:22:04

CopyableCougar4 (80 views)
2014-11-01 23:36:41
Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-09 22:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-02 22:36:02

List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!