Genetic Algorithms ...

Huuum, for my knoledge fo GA this is like simulating a real world, if you mix a black woman and a white man you ussually get a mixed boy now try if you mix a carnivores creature and a vegetable eating creature you probbaly get a mixed food creature (stupid comparahion and don't know if possible) and this set of "laws" tend to dictate how the creatures act, i bet a carnivures creature will try to eat a carrot or so

------------------
Bruno Sousa aka Akura
Founder and programmer - Magick.pt
magick_pt@geocities.com
http://magickpt.cjb.net

Genetic algorithms dont really deal too much with the realtime behavior. its generally aggregate behavior over a long period of time, although ga DOES dictate what happens to individuals. take the game of life for example. so many neighbors cause birth, too many cause death, not enough cause death. the survival criteria are for individuals, but are highly dependent on environmental factors.

We tried something like this in our UooS emulator...
Basically rabbits, zombies, and dragons were placed in a limited space (a dungeon). They were given the following simple possible reactions: attack, retreat, wait, group. The focus of the creatures as a race were to gain experience points. Staying alive gave small (time-based) points. Killing another creature gave larger points, largest for the dragons, smallest for the rabbits. Note that the races were not allowed to kill others within their race.
After leaving the thing on for 48 hours without interference, it was found that the rabbits ran like heck whenever anything moved. Dragons went around relatively confidently, though when faced with a group it would retreat. The most interesting behaviour was that of the zombies, who were wandering the dungeon in groups of 7-13.

Sadly the calculations and storage involved caused far too much lag to allow it to be used large-scale in an actual game, but... it was very interesting.

-fel

Genetic algorithms are a method of self adaption by means of evolution.
Basically, take a group of characteristics which define your problem solver. The problem solver could be an ALife agent, obviously with a variety of control methods. For this example I'll use a neural network control method.
The agent has a number of inputs and outputs, inputs including information about the surrounding area, such as number and proximity of predators, amount of food. The outputs are the agents effectors, which include moving in a given direction, the speed of motion, eating or defending itself.
With a traditional neural net architecture you need a training set. A group of inputs with their correct outputs, to allow the neural network to setup the weighting of the connections between the neurons.
With genetic algorithms you would create a hundred agents with random networks of randomly connected neurons. They would then be set free in the world and their actions monitored. A fitness function would be used to find the best ten agents. For this example you could simply use the last ten agents to die of starvation or from being eaten or the ones who managed to get the most food or the ones who evaded the predators best.
The point being that you have to decide what problem you're solving before you can decide how fit an agent is to solve the problem.
You would then take the ten neural networks of the best agents and breed them together, pairing them off so that each agent breeds with every other agent, creating 81 new agents (you could make more or less, your choice). By breeding I mean you would take the characteristics of the neural nets and meld them together using crossover and mutation. If the architecture of the neural net was fixed i.e. x inputs y outputs z hidden layers, then you would be simply choosing the weights from either the father or the mother or possibly averaging them out.
You could then randomly adjust some of the weights by increasing or decreasing them.
If you mutate them too much then you destroy the breeding side of the algorithm.
Ones the offsrping have been generated then you start the experiment over again with the new agents, finding your next ten best and continuing for hundreds of generations.
Hopefully you would eventually come out with the perfect agent for your testbed.
No guarentees though.
Does this answer your question?

Erm, felisandra I was wondering, what is your Uoos Emulator? and how'd you make it, I.e., does it havea gui, isit directX, etc..

thanks.

------------------
-Dom:)
Visit - http://www.eisa.net.au/~sdgrab/contents.html

The UooS emulator (Ultima Object-Oriented Server) pretends to be one of the servers that Origin Systems provides at a fee of $10/month to play Ultima Online. Basically you run the emulator on your computer, tell all your friends who want to play with you your ip address and provide them with passwords, then log your Ultima Online client into the server. Because the emulator is a server, it contains none of the information taken care of by the client (most notably the graphics and GUIs of the game) so unless you have Ultima Online, you will not be able to use the server. Technically the use of emulators became a violation of the user's agreement of Ultima Online when T2A came out, however, the legality of that change in the contract is under question.
The emulator is open source and can be found at http://www.uoos.com
It no longer contains the AI code I discussed due to the lag problems caused by that many calculations when multiple users were connected, however, the AI is a lot better than the "real" Ultima AI (while testing it out I ran all over Serpents Hold with a pack of bunnies chasing me and I never managed to lose any despite trying all the tricks I could think of)

-fel

Cool, belive it or not I have Ultima Online, I played it for about 3 months at the start of the year and the end of last year, I gave up because it was soo boring, and so I unsuccessfully tried to optimise the UOX3 code (Boy is that UNOPTIMISED!!!) but yeah, cool I'll give it a shot.

------------------
-Dom:)
Visit - http://www.eisa.net.au/~sdgrab/contents.html

Yes, I looked at UOX3, decided that the single 830k source file was a hopeless pile of spaghetti, and looked around some more until I found UooS.
Ironically enough, I cancelled my UO account last Sunday... I wasn't playing anymore except to log on to do tower-tending duties. The game just got really boring for me too. Why work on something when the powers that be are going to nerf it way too hard in the next patch and make your effort useless?

-fel

well, you might try and make a server for the basic UO version, like the one when you first install it, that way it'll be easy to play and easy to code. But personally I'd rather just make my own game, it'll probably be way cooler, and run way faster... BTW how long did you play it for fel?

You misunderstood me... that was my reason for quitting regular UO. The calculations like damage and to-hit are done server-side, so we didn't nerf much unless we really had to (and unlike Origin, we actually listened to the people who play our server)

-fel

What hasn't been mentioned is that a Genetic Algorithm is a class of Blind Search Algorithms . What most people understand as a Genetic Algorithm is John Holland's Canonical Genetic Algorithm which has 3 operators: selection , single point crossover and mutation ... applied to a haploid (single string) chromosome.

GA's are called a blind search method because the only information they have available to them is a function evaluation of the decoded chromosome. So, consider a chromosome that encodes values between -1 and 1 and an objective function of the form f(x) = 1-x². Each chromosome has a fitness equal to its objective function value. Applying the GA operators (selection, crossover and mutation) to a population of chromosomes (each representing a value in [-1,1]) would allow you to find the optimal (maximal) value of f(x), since the GA reproduces fit chromosomes.

In other words, the GA searches the state space of the encoding scheme - using genetic-like operations on an abstract enconding of state values - and returns an optimal value.

GAs are particularly useful in search problems where you can only obtain objective function values by evaluation (as opposed to an analytic function), in stochastic domains, multimodal domains (where hill-climbers fail) and discrete domains (step functions). GAs don't work well in domains where the region of the state space occupied by the dominant mode is small compared with the overall size of the state space.

As Mike suggested, you can apply this search technique to finding optimal parameter values in a neural network. In this situation, the objective function is the world in which the agent acts and the value returned is some measure of success of the agent. I won't go into the difficulties with this approach to parameter fitting in ANNs as they are many and detailed.

There are as many application domains for GAs as you can think of search problems. However for many of those domains other search algorithms might be appropriate.

Finally, canonical GAs have an asymptotic convergence rate to the optimal objective function value. This can be overcome though with some rather simple modifications to the implementation.

I hope this has helped!

Cheers,

Timkin

[edited by - Timkin on June 11, 2002 9:44:28 PM]