Friday, 19 September 2014

Adding evolution to the mix

My second experiment was about using a simple evolutive algorithm to fine adjust the goal strengths in order to get the best possible set of strengths given the environment you place the players in.

I added a "magic" check box on the app so you can switch on this evolution, then add new players if desired, goals, and let the population grow and the best adapted selected over time.

A set of changes take place to the simulation when you turn this on:

-Players that get a 100% of energy automatically duplicate them selves, dividing available energy into halves so each one has 50%. The new born copy its progetinor's goals strengths and then changed those strength a given random amount, let say in the range -10/+10%.

-Rockets are not allowed to recharge its energy by landing. They can land, but energy will not fill up anymore. They need to get drops to survive, as intended.

-Karts are the hunters. They can't take energy drops, instead they can hunt the rockets to take their energies into its own battery. If rockets run out of energy they will die after crashing somewhere, and then they will get smaller and smaller until they shrink away, leaving room for newcomers. Karts will still be able to suck energy from the died rockets, so karts will jump over dead rockets as zombies.

Thats all, only this took to make things evolve over time, but it is difficult to see the evolution happend just by watching the game on the screen, so I also added a couple of graphic changes to make it clearer:

-Players get theirs colours depending on the first goals strengths (the most important ones, runing, energy and health) so green ones are different from red ones, but different tones of green makes quite similar players. Just looking the screen you see the predominant color of the population and how it change over time.

-A new graph upper left shows the "ADN" of the population: Each player draws a horizontal line on his own player color showing the strenghts of all its goals. This looks like a mountain, with peaks on the stronger goals and valleys on the weake ones.

That said, the video itself is quite long and depressingly boring, I suggest you skip to different points on the time line of the video to see how the new graphic shows different colonies of similar players evolve, dissapear over jump to another color.

Surely the rules were not fair for the rockets as eventually the last one is hunted down by a miriad of hungry karts. Well, it made the video shorter anyway!

What could this approach be good for?

Basically it is way to fine tune your goals strength before going into "production". You could think of that as a way to choose the right setup of the pilot, instead of the kart's physical setup, but it could be widened to make other params, like the kart size, power, etc. to get the best kart configuration for a given track.

In my opinion it is just a strange and slow way to do things. I wanted to make a try on it, but this kind of work of fine tunning params can be made way more efficiently and real time instead of using precalculated params, using a second layer (as I described in my last post Follow my orders!).

There is an scenario in witch this evolution approach could be quite powerfull: evolving the player design itself.

By doing so we will need to make decisions like "Add a new thruster to the rocket in that position, angle and with this power". As you can see, there are yes/no decisions involved, like adding or not a new thruster, and this is not sometinhg a second layer will be able to do easily, but an evolutive phase would.

I am not quite interested on those possibilities, but may be I will come back later to it and try to make a spider evolve into some other more adapted insect by adding or taking legs, wings, etc. I can't promisse I will finally do it. 

Follow my orders!

After some months without working in this algorithm, I am back with some new ideas to code, but before this, I want to show you a couple of experiments I made before the summer break.

First one, showed at the talk in Miguel Hernandez University in an early stage, is just a concept test: could this intelligence be used to drive a vehicle without effort and safely, but following you directions in real time?

Imagine a real car using this algorithm to drive you anywhere, you can let it drive for you as in a google car, but with an added hability of a "semi-autonomous mode".

In this mode, you could let know the car where you want to go just by pointing in a map, or by moving a fake driving wheel inside the car. The method is not important, but the resulting behaviuor is potentially interesting: your 5 years old kid could take this car, point with is finger the direction he wants to go, and the car will drive him safely around the city.

How could it work? Imagine your kid is reaching a cross-road full of traffic, he points with his small finger to the road on his left, as he knows grandma home is over there. The car will try to go this way but avoiding collisions, red lights, pedestrians and so on. It will for instance stop, wait for a clear moment, and carefully turn left as the kid pointed, but safely and following all the "rules".

As a prof of concept I added to the software -download V1.2 if you want to play with it- a new menu option "Follow the mouse" and another one "Avoid the mouse", useful for giving the car instructions on where not to go (candy shop, for instance). As a result, all the players on the track will do their best to follow your mouse orders.

As you can see at some point in the video, the players will even go the long way if it is neccesary, meaning the kid could point to a forbiden road and the car will still understand it and go around the block and get to the point you defined in the right driving direction.

I also added this "Follow the mouse" feature as a early fake test of a possible "second layer" of intelligence. The mouse position X and Y could be a goal parameter instead of a ad-hoc added menu option.

I could define a new kind of goal called "FollowMyFinger" with X and Y as parameters. The second layer of intelligence is clearly seen in action when applied to those two parameters.

In the same way I used my brain to decide moving the mouse here or there, this second layer could test what would happed if I move this "atractor" point the left a little bit, and then let the game run for 60 seconds. On each delta time in the simulation, the "atractor" mouse point is moved again and again randomly, so think in the mouse as moving randomly while those 60 seconds runs.

After those 60 seconds of simulation, you have a future asociated with the firt move being to the left. Repeat another 99 times and you have 100 ending points for the "second layer" option "left", so you can again, like in level 1 I always used, discard similar ending ponts, count the remaining ones, and use this N to get an aproximation of the "second layer option" go left.

Repeat for right, up and down and you have all you need to decide where should you move the mouse at this instant.

This could be the second layer of intelligence changing params used in the first layer dinamically, if I had already coded it, that I haven't.

Once this mouse has been moved by second layer, the algortihm could follow with first layer as it is doing now: consider mouse static (they are params again on this first level, as in level two they where used as free params) and decide your move simulating 5 seonds in the future, as always.

Note the differences: First layer decide on cark movements using 5 seconds futures and considering mouse position as fixed params. Second layer is used before and decide about mouse movements, so mouse position is a couple of free params controlled by AI instead of fixed params, and the futures are calculated for 60 seconds using level 1 as part of the simulation itself.

This last point is crucial: if in first layer the kart was driving by mad monkeys, so more than 5 seconds was too optimistic, now you can think 60 seconds ahead while deciding where to move the mouse.

A more realistic example could be controlling one of the first layer goals strength with this second layer. The second layer could then change the kart behaviour from a conservative setup to a more agressive one if it is better in some point of the race.

Let say you need to pass two karts that run side by side, so this second layer would proyect 60 seconds to the future each of the two options (get more conservative, get more agressive) and get as a result that being a little more agressive gets more entropy (there are more different endings at 60 seconds, in some of them you don't pass them as when being conservative, but in another futures you get past them and they open new possibilities).

This power that a second layer adds without any additional work from you, just by using it to dinamically adjust the already existing goals of the players, is the first great advantage of a second layer, but a second  one could be even better if you can set a different goal set for this second layer.

This could open new posibilities like having a manager that cares about being able to run the next race also, not only winning or lossing this one, for instance.