Genetic Tanks
|
|
Plan: To make a simple environment with simple rules and populate it with entities that compete with each other.
Hopefully better robots would evolve, and their genetics would dominate the pool until even better robots evolved.
|
Rules
|
10 robots are put into an arena. Each robot may do the following:
1) Face up
2) Face down
3) Face left
4) Face right
5) Move forward
6) Fire gun
If a robot fires his gun and hits another robot, the other robot is damaged.
When two robots are left, they mate and repopulate the arena.
Each parent will contribute 50% of the genetic code to it's offspring.
Success or fitness would be defined only as survival.
|
The mind of a single robot
|
|
The problem of getting a robot to act in such a way so that it learns is no
simple one. Each robot must have a 'mind' that can be both passed onto it's
children and evolve as it does so. There must be a large possible number of
'minds' that any robot could have, so that evolution will occur, but the mind
must remain simple enough so that it will sit adequately in computer memory.
The first 'mind' method attempted was based on how humans perceive the
world. As we sit down reading this document, we have a good sense of our
surroundings. We know that there is a chair underneath us, a desk in front
of us, and we also know the locations of other people (if there are any)
nearby. They sit in our mind spatially, as a kind of memory hologram; I
know- I feel, that my neighbour in the room next to me is two meters
behind. I know that my bed is to my left, even though I need not look
at it repeatedly to see where it is. When I wrote Secession TM, I found
out that the secret of producing very authentic artificial intelligences
was to model them on my own- to place myself in their shoes, and to figure
out what I'd do if I was in control. The result was a deadly foe or an
valuable ally; realistic what ever side it was on. So in attempting to
understand how my mind places objects I made up a matrix, and placed
objects in each matrix:
|
Example robot mind map
|
|
Each robot was to have as starting point, a two dimensional mind map that would cover everything in the screen, and therefor it's universe. Memory constraints made it necessary to make the minimum size of each square not one pixel large, which would have been most accurate, but 10 or 20 pixels large.
Now the robot has it's mind map, but it still can't actually do anything with it. We can simply enough find the closest threat to the robot, and by simple maths, address the correct part of the mind map, but then what? Well, thinking again if we were in the robot's position, what would we do? If we had a threat directly ahead, we would probably attempt to destroy it. If it was to the left, we would turn left, and so on. But, we can't pre program these robots; we must let them do that for themselves. All we can do is to allow the robots the possibility of the correct action forming in their mind. If we look at the rules that we made a while back, we will see that each robot will have six choices. These choices should be input into each square of the matrix somehow so that the robot will firstly look at the threat square, then decide what to do.
How would we make the robot decide what to do? The simplest and most immediate action that springs to mind is to assign probabilities to each action. A well trained robot would have a 100% chance of shooting at a target that is dead ahead, and a 100% chance of turning left to attack one that is on it's left. This means that each element of the array is going to have 6 entries; one for each possible choice.
|
|
The Elements of a robot mind map
|
 |
|
| Face up % |
| Face down % |
| Face left % |
| Face right % |
| Forward % |
| Fire gun % |
|
|
|
|
|
|
|
|
|
|
Robot |
|
|
|
|
|
|
|
|
|
|
|
|
The total percentages would, of course, add up to 100 percent. Each element of the 2 dimensional array would have these 'ideas' in it, and each idea would have different values to each 'thought'
So to recap briefly, when a robot saw a threat, it would look at the appropriate threat square in it's memory map, and then decide which action to take depending on the probabilities. The way it would do this in a computer program would be for it to pick a random 'thought' (a number between one and six) then pick a random number between 0 and 100. If this number is less than the number held in the thought, then it will perform that action, otherwise it will pick another random 'thought' and start again.
For example we shall use our well trained killer robot. For something directly above, it's idea map would look like:
Face up : 50%
Face down : 0%
Face left : 0%
Face right : 0%
Move forward : 0%
Fire gun : 50%
And, for a threat to it's left:
Face up : 0%
Face down : 0%
Face left : 50%
Face right : 0%
Move forward : 0%
Fire gun : 50%
Just for comparison, an ill robot, or poorly evolved one's idea map for a threat directly above would look like:
Face up : 5%
Face down : 2%
Face left : 42%
Face right : 51%
Move forward : 5%
Fire gun : 20%
This robot would almost definitely spend most of it's time vibrating between facing left and facing right. If the population consisted entirely of robots with this trait, then it wouldn't really be at a disadvantage. If the population was dominated by better robots, however, then it would be. It would oscillate left and right, harming nothing, but it would get destroyed by another robot and it's genes would be lost. This is a good thing though, as it closely mimics actual evolution.
|
|
Mating
|
|
When only two robots are left, they mate. Eight offspring are to be produced, bringing the total population back up to ten. If each 'idea' is to be considered as one gene, then each parent would contribute roughly 50% of it's 'ideas' to it's children. If more than one idea was to be considered a gene, programming would get messy, and if each idea was to be broken up even further, then the gene code wouldn't quite work - the percentages would fall apart and fail to add up to 100 any longer.
Mutation should be considered as the population is so small. This would be easy to add, and there would be two possible main methods:
1) There is a random chance that the gene will mutate and the probabilities would alter slightly.
2) There is a random chance that the gene will mutate so much that the probabilities would be completely rewritten. (This one would be the easiest to program)
Of course, the first option was selected, and if the robot was deemed as a mutant, then a random number was selected, taken off one 'idea' and added to another. This kept the total probabilities at 100%, and didn't alter most of the 'ideas' in the robot's head. The second method would do this drastically, altering almost totally what a robot would do in a certain situation.
Prediction:
As time progresses, robots with tendancies to be better killers would survive, and their genes would prevail. Better and better killer robots would evolve, and the program would end when each robot was a perfect killer with it's idea probabilities locked in the place where it had maximum potential (ie turn left and fire at a threat that is left).
What actually happened:
The robots were left to evolve for two weeks running on a P166 machine in IBM at Hursley, (where my industrial placement year was. The machine was state of the art back then.) The results did surprise me.
Generation 0000:
The robots were all pretty random. Stupid and inefficient, they shot each other
by accident and the generations took quite some time to go by. This was to be
expected.
Generation 0500:
The robots were becoming reasonable effective killers at point blank range, but were almost totally useless at any kind of distance. I think that this happened because when robots met each other at close range, accuracy was much more heavily related to survival than when robots were at opposite ends of the screen. This meant that robots were to become good killers at close range first, and only gradually gain the art of distance combat.
Generation 1000:
A second breed appeared. Robots that fled at close distance and ran away kept popping up every few generations or so and dominating the arena till they were wiped out by the killers. This was totally unexpected, although as I defined fitness as survival only, I really should have guess that it would happen.
Generation 2000:
Highly evolved killers and prey were dominant. As the gene types for killers and prey were so different, some random robots were born, but these were always completely wiped out. The screen looked exciting at this time. Killer robots would chase the prey, which would duck and dive. As target aquasition was so basic, the killer robots switch targets rapidly (as did the prey, but they didn't shoot at their targets) and usually a killer would end up shooting at another killer, or they would both wind up killing each other. The prey often shot too, but more randomly than the killers.
Generation 2500:
The prey robots were becoming dominant. This was odd, I thought.
Generation 3000:
Killer robots had completely vanished. The generations took a long time to pass, as the prey didn't really attack each other. I hoped that killers might re-evolve.
Generation 4000:
Stupid robots were creeping back into the gene pool. I suppose that this was because being good at running away was no longer as importent if nobody chased you. Because of the way that ideas were coded into the computer, the prey robots rarely fired a shot, but the random ones did. This didn't look good for evolution- random robots were becoming dominant again.
Generation 4500:
Stupid random robots were completely dominant.
Generation 5000:
The robots were starting to become good killers at close range again. Evolution had gone full circle.
I would have liked to run this program for longer, but two weeks for a powerful computer was quite some time. When allowed I did attempt to rerun the experiment, but I never got quite the same results. I never ran it for two weeks at a time though, but I think that the time I ran it for two weeks I was lucky enough to get a good gene pool (the 'ideas' were created randomly) that procreated well.
Around generation 3000, the robots could have been said to reach some kind of utopia. There were few deaths, and generations lasted for a long time. Was this bad for the robots though? They de-evolved, at first slightly, then their more primative sons wiped out the peaceful forefathers.
|
Better robots
|
|
There is no doubting the fact that the robot precursors were primitive.
They need improvement, perhaps even rewriting from scratch, but they were only the
first step in a line of genetic programs.
The precursors taught me a lot, and I had a short list of changes that needed to be made:
1) The memory map idea was inefficient and used up too much memory. A more advanced targeting system was needed.
2) Robots should rotate instead of simply face in one direction.
3) Ideas should be converted into 'programs', making the actual program more genetic in it's makeup.
4) The programs should be more simple, containing less commands, but a larger flexibility.
|
The New Memory Map
|
| Ahead Left |
Ahead |
Ahead Right |
| Left |
 |
Right |
Behind |
This memory map will be tied into the following three functions:
1) Move left wheel
2) Move right wheel
3) Fire weapon
As you can see, there are less commands, but more possible combination of commands. By combining these actions, the tank could move forwards, reverse, rotate left and right, turn left and right, and reverse left and right as well as firing it's gun.
A simple program would be inserted into the tank's brain thus:
Command Value
1 1
2 1
1 -1
2 1
3 -
The tank obeying this program would firstly move it's left wheel forward, it's right wheel forward, it's left wheel backward, its right wheel backward and then it would fire it's gun. The main problem that a tank running this program would have is that this program is not parallel; the tank would only be able to move one wheel at a time or fire. Progress along the ground would be very similar to a drunkards walk to say the least.
The tank must be able to perform any of it's functions in parallel. It must be able to move both it's wheels indepenently and still be able to fire. A good possible solution to this problem would be to use three command arrays where each command array controls power to each of the tank's functions:
L R F
1 -1 0
1 -1 0
1 1 0
1 1 1
A tank following this program would turn clockwise, move forwards and fire it's gun.
|
Simple killer robot example
|
|
1 |
2 |
| 5 |
|
3 |
4 |
Quadrant L R F
1 0 0 1
2 1 0 1
3 1 -1 0
4 -1 1 0
5 -1 1 0
6 -1 0 1
This is assuming that the threat is in each quadrant, and the tank looks at that quadrant's program to decide which way in which to point. A target straight ahead would cause the tank to look in quadrant 1, and it would run a program that would make it just fire it's gun. A threat in the third quadrant would make the tank spin around till it was in the 2nd or 1st when it would start to open fire on it.
These arrays are of minimum length; more interesting behaviour would occur if they were longer, perhaps up to 10 elements in length. Then the tank would start the program in the quadrant, and this program would run for several loops.
And what if each there was more than one program to choose from in each quadrant? A complex tank could have 10 programs to choose from, and each program could have a varying length. This would lead to more interesting evolution, which is what we want, but complexity also takes longer to evolve. I should think that 10 programs would take at least 10 times as long to become as effective as 1, and they'd probably take even more time than that.
|
Mapping the mind
|
|
So far, choosing quadrants is easy. The tank can look purely at the relative screen X/Y coordinates and decide on those. However, if the tank is facing another way then things could get confusing
| 6 |
1 |
2 |
| 5 |
 |
3 |
4 |
Unless we used an angular system to target threats, both the tank facing above and the tank facing right would assume that it's threat was in quadrant 1.
| 5 |
| 4 |
 |
6
1
2 |
3 |
The target has to be selected using an angular system. Each tank will have to have a normal coming out of it in the direction that it is facing, and this will have to be checked against a screen vertical line to calculate the angle that the tank is offset by.
 
Theta is found using simple trigonometry
Where the triangle is a simple right handed one and therefor pythagorus' theorum applies, as does basic trigonometry.
Theta = tan-1 (dx/ dy)
If we found the angle that the target was at relative to a screen vertical and the angle that the tank was actually pointing, then we could subtract one from the other to end up with the relative angle that the target was at.
There is a problem however. Consider this diagram
dx- dx+
dy- dy-
-------
dx- dx+
dy+ dy+
Theta won't be accurate unless dy is positive. Some correction has to go into the angle calculation routines. This is simple and can consist only of a check and an addition of 180' to Theta if dy is negative.
So, now we almost have our robot tank. The only problem left is that of reproduction. There are, of course, two main methods for reproduction;
i) Sexual
Two tanks mate, and the genetic code is split 50/50 from each parent to each offspring. The main problems would be that there is a very small number of parents. This is because of memory constraints in the program, limiting the number of active tanks to 10. With XMS access, this number could be raised, but not infinitely. Small numbers inbreed too easily, and with a small amount of genetic code, the problems that arose with the precursors could occur again. This is something that I dearly wish to avoid.
ii) Asexual
Two tanks clone each other, and the mutation rate is raised slightly to allow perhaps one in ten children to be a mutant. This basically corresponds to one tank in each generation being slightly different. The differences would occur in either program length, or different program data. If the program data is bad, then it is likely that the child tank won't survive. If it is good, then the likelihood, although still small (the mutant is outnumbered 10 to 1) is higher. Because 2 tanks are cloning chances of reaching genetic 'dead ends' are lessened slightly, but they are still around.
The only true method to stop genetic dead ends would be to allow for a massive amount of entities. I dream of reproduction being determined by the program itself, not laid out before hand; letting the program choose the best methods for it's own prorogation and improvement.
|
Results
|
|
The tanks were let loose for a week when time permitted. Sampling was unfortunately kept to a minimum due to extensive other areas of workload; University work and the setting up of my own business. However, I did manage to check the tanks every few days on a rough basis. The results were not as pleasing as I'd have hoped, but I guess that you can never predict what is going to happen in a genetic program.
Because bullets had an infinite range, each tank had developed gun turret like characteristics. Moving backwards and forwards randomly had no serious effect on survival, so they moved backwards and forwards randomly, but fired constantly. They did aim in the direction of the closest threat, and generations passed by very quickly. Because there were 10 possible programs to choose from in each memory, behaviour was diverse, but I'd like to see what tanks would do if they only had 1 program in memory. I was initially advised to do this, but I thought that with 1 program to choose from, even though evolution would occur more rapidly, it would also be more limited. It would be easy to change the 10 program tanks to 1 program tanks though.
This will be my next step before giving tanks characteristics like age, energy requirements, and moods; (moods will consist of routines like 'attack', 'mate and 'replenish energy' instead of happy, sad and angry. Of course, each mood would be completely random at first, but tanks that failed to replenish their energy would die out, whereas tanks that did replenish would survive and the replenishing programs would live on in their children. The trick is to make the environment harsh enough to breed out the non-replenishing tanks, but leave enough around that at least have the beginnings of the right idea.)
|
Teaching genetic creatures
|
|
I stumbled upon a very interesting side effect. Because of the way that these robots minds work,
it might be possible to teach them. At the moment, when a robot sees a threat, it goes and access
memory and reads the probabilities to decide which action to take.
What if a human controlled the robot's movements, and the robot still accessed the correct
part of memory, but wrote to that memory instead? Surely the robot would be taught by the
human- it would be given a head start in evolution. And once, the robots were advanced
enough, they could fight amongst themselves, rapidly evolving once they had their foot upon
the first rung of the ladder. Also, if each human was different in his playing style, that
would be reflected in each robot's personality.
I tried this on both the above robot types whilst working for EA, and it worked. Both
"babies" started life as randomly moving creatures. A human controlled robot was also
on the playing area, but it's memory maps were being written to by the user instead
of being read. For example, if a robot tank was ahead of a human tank, that part of
memory was located, but the human's response was written to it instead of
the tank's response read from it.
The baby robots quickly picked up the style of play from the human. They even
picked up aspects of personality - from a tendency to turn left to the ability
to decide to run when damaged. More complex versions of these could be created
very easily by splitting the actions up logically and giving more memory to the
robot. Also, patterning programs and allowing the robot to choose which program
to run whilst it was, say, facing an enemy, would also greatly increase the
flexibility and intricacy of the robots.
Converting this system from controlling a robot on a screen to, for example,
outlining and counting human faces would not be overly difficult; I just wanted
to see if it would work.
|
|
|
|