I'm interested in writing a genetic algorithm. I'm sure my idea for it is nothing new or breathtaking, but I'd like to imlement it as follows: There is a world grid of arbitrary size. Food is present distributed more or less randomly. The creatures are placed randomly at the start. They wander around eating food and their fitness will be how many foodstuffs they ate. At the end I'll create a new population of the same size by iterating over the population n times and allowing them to reproduce with a likelihood in proportion to their fitness. I'll have some mutation and crossover. Simple and elementary. Now for my problem.. and I'm sure this is probably the hardest part to figure out for any GA. How will the genetic information work for individuals. More details: The creature can make one of four choices, to move up, down, left, or right. Moving onto a food eats it and causes another food to spawn in a random location (not ontop of a creature or another food) and two creatures can't occupy the same spot, though a creature could elect that his move will be onto a square that another creature occupies. Assuming that the second creature moves away for his move, then the first creature will be able to move there, otherwies he will sit still. The creatures have their genetic code AND are able to see everything in a 5 by 5 grid centered around themself. The world wraps top to bottom and left to right and if they are at an edge, their field of vision is still 5x5 and just wraps around the world to the other side. The problem at last: How do I make some genetic code that can operate on this 5x5 bit of data to yield a result in which direction to choose? I thought at first of having four 5x5 matrices and just multiplying the vision state matrix with each of thoes fuor (one for each direction) and having the creature choose a direction based on which product was largest or smallest or closest to some value. But I realize that with the world being random and there being nothing special about up, down, left, or right from one world to the next, this would not accomplish anything. What I want is for there to be some genetic information that the creature can use to help it decide a direction to take based on it's current 5x5 vision matrix. I'm hoping to see little patterns evolve.. like here are some examples i envision: -creature sees 2 foods to it's lower right, but another creature is in between it and th food. it sees 1 food to it's upper left... and it goes for the food in the upper left.. because evolution wise, those that went for that.. would be more likely to get to get any food at all.. but if there were no creature present.. it would go for the 2 foodstuffs instead of the 1.. or maybe.. if there were 3 or 4 foodstuffs, with another creature in between, and 1 in the upper left, it would go for the 3 or 4, knowing that even though it won't get there first, it would still be more likely to get at least 1 or maybe 2 than if it went for the lone foodstuff well that basically encapsulated the majority of my hopes for the creatures. i realize that this type of behavior is very complex and would probably involve making the genetic code very very long and require hundreds or thousands or millions of generations to evolve.. but i don't care about that. i just want to know how to code some dna that could somehow operate on the 5x5 vision matrix to produce behavior relevant to the current vision state. just this moment i've had a slight idea.. that is probably trash. but maybe.. a vector for each of the 24 non-center squares in the 5x5 vision matrix.. weighted by what it is pointing to.. a foodstuff, an empty square, or an enemy, and by the contents of the few squares near what it's pointing to.. then summing all the vectors up to get a resultant direction.. maybe that's not such a trashy idea after all.. in fact maybe that's a perverse and gross and grossly oversimplified analogue to the way real brains make decisions.. i don't know.. if anyone has a better idea.. or has knowledge of this type of thing and can point me in the right direction, i would appreciate it. thanks. edit: now that i think about it.. my comment about what i figured is probably the hardest part for any GA was probably wrong. i bet it's the fitness function, but since that's so simple in this problem.. i'm just refering to what's the most difficult for this problem.

I've given it more thought since the post and have developed that vector idea a little further.

The creature sums up all the 24 vectors. (actually i think i could do it with 5 since there are 5 independant vectors... the others are just symetric to those 5... so i could have 5 distinct vectors.. and use them repeatedly to get 24 vectors (all 24 of which could be distinct.. just the.. template.. the formula for the vectors would draw from 5.. aka.. adjacent diagonal, diagonal by 2, adjacent 2 away, and 2 away and up one)) it sums up all these 24 vectors to decide it's direction.

each of these vectors has a direction (simply the line connecting the creature to that square) and a magnitude which could be determined by having each vector weighted for the three possible values (empty, food, creature) but then i figured this wouldn't allow very complex behavior. so how about.. each vector is in turn weighted by sub-vectors specific to it... to all the squares once again.. and i could even take it to a tier 2, 3, etc.

does this seem like a good way to go about it? are there significantly better ways?

i intend on trying to introduce the concept of "remembering past vision states" later on.. but i'm not worried about that yte.

This isn't so easy. You're trying to evolve a decision making process, one that has rules for "given this state, do this". The problem is that, with 5x5 vision, you have a huge number of possible states.

So you could go for a brute-force method if you wanted, and list every possible state in a look-up table, and then try to evolve the actions. Your dna string wouldn't need to include the state representations, as they will be in order, just the actions. Still, this string would be, what, 3^25 digits long, if every space represents food, creature and empty.

Also, you can try for some kind of chunking of data -- dividing the 5x5 area into four areas, forward, back, left and right. This wouldn't lead to behaviours as complex as above, since the information isn't as fine-grained, would would probably be several orders of magnitude easier to evolve.

I'm not certain I understand the vectors method you propose. I assume what you would be evolving would be the weights that the three categories of space should be? So a vector towards food would be weighted highly and a vector towards a creature might be negative? That could possibly work, but they wouldn't provide any decisions in balanced scenarios, if I understand right. What happens when all squares in the 5x5 area are empty? The creature would have an equal pull in all directions. What happens if the creature is situated exactly between two items of food?

There's quite possibly a good idea there, but you'll have to be sure to work it through.

Of course the standard way of doing this is to use a neural network. Evolutionary neural networks are very easy to create, and require no knowledge of backprop or anything. You simply have 24 input neurons, one for each square, x hidden neurons, say 5, and then perhaps four output neurons to represent a vector in each direction. The resulting direction is the sum of the vectors. The dna string is then all of the weights in order.

ANNs may sound hard when you first begin, but actually this is the most common way of solving this problem, as they are quite easy to program.

As for the fitness, that shouldn't be any problem. Any function that reflects the amount of food eaten will do that. You can either run each generation for a set period of time, and have fitness be directly proportional to the amount eaten. Alternatively you could have creatures die if they haven't eaten for x epochs, and then collect the survivors. Any method will produce a result.

I don't think I fully understand your "24 vectors" idea, so I'll hesitate to comment on that just yet.

One thought that I had was to introduce a true function that rated each square available to move into. For example, let's say your creature can only move in the 4 cardinal directions per tick - N, S, E, W. Each of these squares could be evaluated by a neural network and you move in the direction with the highest evaluated value.

The network's inputs could consist of the states of the 24 non-central squares. It sounds like each square can be empty, contain another creature, or contain food. Each square could easily be represented by a single input to the network with 3 possible values - -1=creature, 0=empty, 1=food. Then you'll have some hidden layer (or not), and the output. You could make it have 4 outputs, one for each cardinal direction, and take the direction with the highest value.

This is just one idea - you could come up with dozens of possibilities.

-Kirk

edit: Asbestos! You posted just before I did! Nice to see we converged on the same option. 8^)

If I were doing this I would create a system of weights from 3 input arrays to the 4 outputs. 24x2x4 = 192 variables per AI(maybe go short or byte on that one). Loop through the areas and add a 1 or 0 times each weight to determine how good it is to move in each direction.

for each space{up += (food on space * weight for food on that space)+(unit on space * weight for unit on that space)down+=...right+=...left+=...}

This is fairly similar to what a neural net does, but notice I used 2 arrays of weights instead of one. This should allow for more behaviors if other units are not interpretted as negative food. If they are then of course your AI will run away because it's doing the opposite of what it would do if there was food there, and if you already know what you want it to do then why would you be evolving it in the first place?

yep I was considering neural networks.. i'll elaborate on my vectors method when I finish my long drive to houston.

and yeah.. already said i'd probably just use the amount of food they ate as a fitness, but like you said, anything proportional to that amount would work too.

actually just having a value for each of the 3^25 state configurations seems like a fun way (moving it down to 3x3 probably of course.. or lines of site like you said) and i might implement that. but I think I will try with these vectors or with a neural network first.

would I need four neural networks, one for each direction? or just one neural network with four outputs and take the largest output?

neural networks seem so primitive.. could a neural network really evolve to have the kind of complex behavior i described?

the way my vectors work is it weights each square with respect to it's environment, then weights the creature with respect to all those weights.. so really we have an analysis of all the spatial relationships of everything.. that could evolve some complexity..

A neural network would definitely be able to capture what you want. The beauty of a neural network is that it would be able to capture more complex behaviors as well. The solution described by Alrecenk is a simple summation of weights times states. This is equivalent to a neural network with no hidden layers, and I would bet that most likely its behavior would be to move toward the largest concentration of food with the lowest concentration of creatures. More or less downhill. The neural network, however, would potentially be able to capture more complex behaviors. Suppose you make the system a little more complex and put in some predators that eat the creatures you're evolving. The creature will then have to balance feeding and avoiding being eaten. Another similar example would be PacMan - he has to eat the dots, avoid being eaten by a ghost, eat the power pellets, and eat ghosts when their blue. A rather complex set of actions.

-Kirk

U can find a lot of information on this website
http://www.ai.it360.ru

Quote: Original post by sharpnova
would I need four neural networks, one for each direction? or just one neural network with four outputs and take the largest output?

Absolutely not -- just one network with some number of outputs.

Then there are any number of ways that you can go from outputs to direction. You can take the largest of the four directions and head towards there, if you want, although this movement might look rather static, like they were moving around city blocks. Personally, I prefer the idea of looking at the output values as the length of the individual vectors, and summing them to get the final direction. This way each output gets a "vote" as to the overall direction: If one neuron really wants to head to the East, because food is over there, and one neuron really wants to head North, because there is another creature to the South, the creature will head North-East. Note that with this method you could even have just three neurons, each being a vector 120 degrees from the other. Or you could even have two neurons, if you allow them negative values.

Quote: Original post by kirkd
Another similar example would be PacMan - he has to eat the dots, avoid being eaten by a ghost, eat the power pellets, and eat ghosts when their blue. A rather complex set of actions.

-Kirk

:o)