Gamestudio Links
Zorro Links
Newest Posts
Newbie Questions
by fairtrader. 12/05/23 14:22
Zorro Trader GPT
by TipmyPip. 12/04/23 11:34
Square root rule
by Smallz. 12/02/23 09:15
RTest not found error
by TipmyPip. 12/01/23 21:43
neural function for Python to [Train]
by TipmyPip. 12/01/23 14:47
Xor Memory Problem.
by TipmyPip. 11/28/23 14:23
Training with command line parameters
by TipmyPip. 11/26/23 08:42
Combine USD & BTC Pairs In Asset Loop
by TipmyPip. 11/26/23 08:30
AUM Magazine
Latest Screens
A psychological thriller game
SHADOW (2014)
DEAD TASTE
Tactics of World War I
Who's Online Now
2 registered members (3run, AndrewAMD), 667 guests, and 1 spider.
Key: Admin, Global Mod, Mod
Newest Members
fairtrader, hus, Vurtis, Harry5, KelvinC
19019 Registered Users
Previous Thread
Next Thread
Print Thread
Rate Thread
Page 1 of 5 1 2 3 4 5
Genetic Algorithms and Games #115132
03/05/07 11:40
03/05/07 11:40
Joined: Jul 2004
Posts: 1,205
Greece
LarryLaffer Offline OP
Serious User
LarryLaffer  Offline OP
Serious User

Joined: Jul 2004
Posts: 1,205
Greece
Hello people!

Genetic Algorithms is a very new, and still grossly underappreciated part of computer science, so I thought of doing my part in changing that, by informing as many people as I can. I won't get into any specifics about how GAs work as there are already a lot of great tutorials on the net about this, I will only try to give you a brief overview and hopefully get you intrigued to do your own research.


Why learn Genetic Algorithms?


Genetic Algorithms are inspired by nature's way of evolution, and contain one amazing ability: The power to solve any given problem without formulating a plan!

In other words, we can make the computer do anything we want, WITHOUT having to tell it HOW to do it. Sounds crazy? It is... But it works.

I'll give you the first example, coming from nature itself. Do you know why geese always fly in a group forming a V shape?



We found out that when geese fly this way, aerodynamic forces allows them to fly 70% further than a single bird using the same amount of energy. Now geese sure ain't the best physics in the world, but there they are, flyng in the BEST way possible.

Now we humans have great physics who can use their minds to consider all possible physic laws and come up with great formations... Did we ever came up with anything better than geese flying? No..




Didn't you ever wished you could just tell your computer to do something, and have it do it, instead of having to instruct it, step by step by step, before you can have it get anything done? Now with GAs you can, geese style


I still get to write code, right?

Obviously. Your computer only understands code, and in Gamestudio's perspective, c-script. So you will instruct gamestudio how to do the GA(or use someone else's code for that), and tell it what you want it to do. Then run the GA, and leave it to the amazing nature-inspired laws to find the optimal way for you in order to solve your problem.

Once the GA is done, you will have your solution. You won't be able to understand WHY this works, but it will.. probably better than any solution that you could ever come up with.



What do you mean when you say problems? Can GAs write code and make a game for me?

Yes, but that wouldn't be very practical... Academics define problems into two categories: easy, and hard. Not really a scientific term... but it does the job for them..

Easy problems are said to have a polynomial complexity, which means that the candidate solutions for this problem are trackable, or easy to visit all of them in order to identify the best. Sorting is such a problem... Pathfinding is another..

You won't need GAs for those kind of problems. For example, if you want to have the player model to move FORWARD when you press the W key. This is an easy problem with a limited search space(all possible directions that your player can move), and there also exists a conventional algorithm that solves the problem with one line of code (make him c_move forwards...)


Hard problems are those that have an exponential complexity, and this is when GAs come in. Most real-life problems are hard, because there are so many possible different ways to try and solve them. The geese flying with optimal speed is a hard problem. You, walking, is a hard problem. You could be crawling, hopping around, rolling over, or walking on your hands instead. Instead, you chose normal walking, probably after a lot of trial and error from when you were a baby. You still don't understand the fine physics and friction that allows you to walk, but you can rest assured that millions of evolutions of humans before you, has assured that the way you move now is the best way for a human being to move.


Since we are simulating real-life a lot in games, lots of hard-problems come in our way when programming. It could be AI, hard math problems, or even simplier logic stuff that you just can't get them to work or fine tune with all those Ifs and Whiles. For these problems, forget trying to understand how to solve em, and code a GA. It will take you a day, and the results will be breathtaking.



Show us...


Later today i'll post in User Contributions my take on a hard bin packing problem using GAs, in c-script. Here's the problem description:


There are a set of N items, and each item has a given weight. Also, each item has a given type (there are T different types of item). The items have to be arranged into C containers, in such a way that the total weight of each container is as similar as possible. However there are constraints involving the types. Items of type i and i+1 (modulo T) cannot be in the same container.


The data I've used is N=1000 items, C=50 containers, T=5 different types. (from 0 to 4). So i'll have to pack these 1000 items into 50 containers, and distribute the weight the best i can. Furthermore, i have to make sure that there are no neightboring types inside the same container( types combinations (0 and 1), (1 and 2), (2 and 3), (3 and 4), (4 and 0) are forbitten).


I challenge any good mathematician or programmer to give me a good solution to this problem. You can use the same data that I used.



How will GAs solve this?


First, they'll just randomly place all items inside the containers. It doesn't matter if they don't meet the restrictions or anything. Then, by doing small changes and LOTS of trial and error, they will eventually come to an optimal solution.


Isn't that like trying ALL possible solutions to see which one is best?


Yes, but GAs don't investigate ALL candidate solutions that exist, because they are slightly biased towards solving the problem rather than investigating the whole search space.


Investigating all candidate solutions would also work, and the result would be GUARANTEED as the best solution to this problem. I actully did the math to see how fast would c-script go through all possible solutions....

With 1000 items and 50 containers, there are 9e+1698 candidate solutions.

C-script needs 0.00378 seconds to evaluate 1 solution. So... that would take 3e+1696 seconds, or 1e+1689 years.. That's trillions of times longer than the current age of the universe.



Well, who cares about bin packing anyway?

The possibilities with GAs are limitless. I urge you to continue reading to this site, where Matt explains GAs in practise in only 3 pages. After you're through, keep what you've just learned somewhere in the corner of your mind. Next time you get stuck while trying to figure out how to do something in your game, GA might be just what you need



At some point, i intent to throw a big team deathmatch or capture the flag fight using IntenseX bots. One team would be normal IntenseX Professional bots. The other will be IntenseX GA optimized Bots. I think the results will be dramatic, and will give proof of GAs being used on a practical AI problem.


I hope this post gave you a bit of an insight to the magical world that it is Genetic Algorithms. Any comments welcome and desired.

Cheers,
Aris


INTENSE AI: Use the Best AI around for your games!
Join our Forums now! | Get Intense Pathfinding 3 Free!
Re: Genetic Algorithms and Games [Re: LarryLaffer] #115133
03/05/07 12:09
03/05/07 12:09
Joined: Jan 2003
Posts: 4,305
Damocles Offline
Expert
Damocles  Offline
Expert

Joined: Jan 2003
Posts: 4,305
The GA approach ist certainly very interesting.
Especially if you combine this with neural networs,
by altering for example the connectivity or start-weights of the network
when it learns. This could for example mean, that the network can
not train (alter conection weights) of all neurons, but
instead is buil out of a genetic pattern that sets a part of the
weights.
The Genetic Algorythm then is used to evolve the best (better) genetic
starting pattern for the netbuildup (next to connection weights, aslo
the connectivity and amount of neurons).
The performance of the net determines
the reproductivity of this net with other nets, and thus alters
the genetic evolution.


The hard part of using GA is, that you need to
be able to set up the enviroment to
make the algorythm evolve. This also
include the evaluation function, and how to
manage new combinations and mutations.
Would be interesting to see, how to include this into
a workable tool for a "newbee" to actually gain sensefull results.


To Your container problem:
Does it really make sense to allow
invalid combinations? Because the possibiliy of an error in the
combination (must be only one false items) is so much bigger (more then millions of times) than
a correct but imperfect combination.
And in biological evolution, only genetic combinations, that
are able to survive until they are born (mature for mating)
have the ability to contribute to genetics. So defective genes -> error,
can not even create a survivable offspring, as long as these are not only small mutations)

Generating a random combination, that is still valid, is not that big of a problem.
(they are valid to the restrains, but not perfect)
I would generate a couple of valid combinations, (lats say 20)
take the ones with the least unbalance in the containerweight. (top 10)
then let the top-rated have a genetic combination with the
second rated. 3 with 4, and so on.
The problem about the combination is, that they can return
invalid results. Building the genetic struture smartly can
make you have combination without having errors.
Offsprings with errors are sorted out imidiatly (they die)
Correct offsprings (no errors) get a mutation with a certain
probability. other stays like this.

After this round, the resulting "creatures" are evaluated for
thei unbalance again, and the process restarts.

Just some first thoughts on the way to realise this.

Re: Genetic Algorithms and Games [Re: Damocles] #115134
03/05/07 12:34
03/05/07 12:34
Joined: Nov 2004
Posts: 7,121
Potsdam, Brandenburg, Germany
Machinery_Frank Offline
Senior Expert
Machinery_Frank  Offline
Senior Expert

Joined: Nov 2004
Posts: 7,121
Potsdam, Brandenburg, Germany
Very interesting. I thank you very much for this interesting post and I really appreciate that you share your thoughts with us.


Models, Textures and Games from Dexsoft
Re: Genetic Algorithms and Games [Re: Machinery_Frank] #115135
03/05/07 12:47
03/05/07 12:47
Joined: Jan 2003
Posts: 4,305
Damocles Offline
Expert
Damocles  Offline
Expert

Joined: Jan 2003
Posts: 4,305
Creating a (a number of) starting combinations.

1-

there are only 3 types of "valid" containers
with the allowed box-type combinations:
0 and 2 - I
1 and 3 - II
2 and 4 - III

(oops, my fault: 3 and 0 , 4 and 1 also... but is the same structure)

2-

Boxtypes 0,1,2,3,4
are seperated to teir group, and sorted, starting
with the heaviest.

Now the 50 Containers are evently assigned
to be type I , II or III
(a bit random variation, for each trial)


3-

The boxes are put into the valid containers.
Starting with the heaviest boxes of each boxtype.
Whenever all boxtypes placed one of the heavy boxes in
each valid container, the loop starts again,
until no boxes are left to insert.


This will give you a more or less balanced, and valid
set to start with.
The genetic Algorythm will have a smarter and faster start from this point on.

Re: Genetic Algorithms and Games [Re: Damocles] #115136
03/05/07 16:50
03/05/07 16:50
Joined: Jan 2003
Posts: 4,305
Damocles Offline
Expert
Damocles  Offline
Expert

Joined: Jan 2003
Posts: 4,305
It is actually 5 combinations, I counted them wrong,
but the approach is the same

Re: Genetic Algorithms and Games [Re: LarryLaffer] #115137
03/05/07 16:59
03/05/07 16:59
Joined: Sep 2002
Posts: 8,177
Netherlands
PHeMoX Offline
Senior Expert
PHeMoX  Offline
Senior Expert

Joined: Sep 2002
Posts: 8,177
Netherlands
Quote:

In other words, we can make the computer do anything we want, WITHOUT having to tell it HOW to do it. Sounds crazy? It is... But it works.




No, this is not entirely true. The evaluating function needs to be able to, call it 'predict' certain things and act accordingly so new actions that evolved from this method can be used or actually make sense. I think it's a bit overrated in it's concept, it's just a different method.

As for aerodynamics, birds and aircraft, they are all bound to the same laws of physics, wether we like it or not. The only thing the analogy proves is that birds are well adapted to their environment and are able to make the most out of their own limited capabilities. However, it's still part of their abilities!! Doesn't matter if it evolved or not, when you wish to apply something like GA to for example intelligent pathfinding or AI in general you would need a evaluating function that would be very complex and extremely smart. That's because the process of actual 'mutation' would have to be mimicked too, unless you fancy deleting source code and let the real code 'mutate'.

I haven't looked into this very deep yet, so I'm probably wrong in my assumption that this is not thát useful just yet.

Cheers


PHeMoX, Innervision Software (c) 1995-2008

For more info visit: Innervision Software
Re: Genetic Algorithms and Games [Re: PHeMoX] #115138
03/05/07 17:19
03/05/07 17:19
Joined: Jan 2003
Posts: 4,305
Damocles Offline
Expert
Damocles  Offline
Expert

Joined: Jan 2003
Posts: 4,305
This concept works best, if your
evaluation function is not set to works, or works not,
but rather to a fuzzy result, (works good, works better than the other)

Lets say you have a pathfinding controlled by some
Neural net or so.
The evaluation function must then only say:

-path persued a possible way (not going though walls)
-path reached destination (or the endpoint is close enough and reachable by a straight line)
-path has a certain lenght (the shorter, the better)

additionaly you could say:

-path did not come too close to enemies
-path varied, so the units path is not so predictable

or whatever you want want as result else.

Whriting the evaluation function is still easier than writing
the algorythm itself. But whatever is being used to
"run" the algorythm (generating actual code, generating a neural net, or just some
steering commands that react on simple sensordata)
must be able to actually accomplish the task.

But running the search for the result might take quite a long time,
and could end up in a dead end. (local maximum)

Interesting topic, but shurely not suitable for "beginners" who want to
write an AI logic after all.

Re: Genetic Algorithms and Games [Re: PHeMoX] #115139
03/05/07 17:22
03/05/07 17:22
Joined: May 2002
Posts: 7,441
ventilator Offline
Senior Expert
ventilator  Offline
Senior Expert

Joined: May 2002
Posts: 7,441
interesting!

i like projects like this one:

http://newtondynamics.com/forum/viewtopic.php?t=2486&start=0
http://www.lri.fr/~devert/videos/

the hexapod kind of learned how to walk.

Re: Genetic Algorithms and Games [Re: ventilator] #115140
03/05/07 22:43
03/05/07 22:43
Joined: Jul 2004
Posts: 1,205
Greece
LarryLaffer Offline OP
Serious User
LarryLaffer  Offline OP
Serious User

Joined: Jul 2004
Posts: 1,205
Greece
thank you all for your comments!

You can now get the c-script GA implementation from here! . The test has been a success, and I can now get a solution to the mentioned problem with 0 invalid type pairs and a maximum container weight difference of 145!


After a lo-ong day of programing, i really feel like going for a beer, so i'll reply to all of your comments tomorrow!

Cheers!
Aris


INTENSE AI: Use the Best AI around for your games!
Join our Forums now! | Get Intense Pathfinding 3 Free!
Re: Genetic Algorithms and Games [Re: Damocles] #115141
03/05/07 23:37
03/05/07 23:37
Joined: Sep 2002
Posts: 8,177
Netherlands
PHeMoX Offline
Senior Expert
PHeMoX  Offline
Senior Expert

Joined: Sep 2002
Posts: 8,177
Netherlands
Thanks for explaining Damocles, yes that makes a lot of sense indeed!

Cheers


PHeMoX, Innervision Software (c) 1995-2008

For more info visit: Innervision Software
Page 1 of 5 1 2 3 4 5

Moderated by  checkbutton, mk_1 

Gamestudio download | chip programmers | Zorro platform | shop | Data Protection Policy

oP group Germany GmbH | Birkenstr. 25-27 | 63549 Ronneburg / Germany | info (at) opgroup.de

Powered by UBB.threads™ PHP Forum Software 7.7.1