AI 'Natural Selection' Experiment

[yoyo1505]

Hi All,

I'm currently studying for a BSc in Evolutionary Biology, and I've been toying with an idea for a while of an AI experiment that mirrors natural selection in animals. I anticipate that to get it to work I would need an advanced understanding of the inner workings of the game code and how to write functions myself. This would take a lot of time and effort, and basically I need to know if it would even be possible to get this working, because if it's not then I will have wasted a lot of time before I work that out for myself. So here are the basic elements of what I am planning:

The concept of natural selection is that every generation, variation in an animal's genome - caused by mutation - influence its ability to survive and reproduce in its environment, therefore passing on copies of its genome.

For the experiment, all the various evolutonary terms have their equivalents in game:
- 'Animal' - an AI company running a specific NoAI script.
- 'Genome' - the code making up the company's NoAI script.
- 'Mutation' - random changes in the code of the NoAI script.
- 'Generation' - a single game run through to 2050.
- 'Reproduce' - if a company reaches 2050, it passes into the next game with its code, with possible added mutations.

I plan to run games consisting purely of AI players, and then at 2050 I will take all those NoAI scripts left surviving and enter them into a new game. Obviously not all companies will survive each 'round', so for those that do I will enter several copies of their script into the next game. I will introduce random changes to the NoAI scripts before each round, just as happens with mutation in the natural world. The 'mutations' may cause none of the companies to survive the next round, but that result would be just as interesting as any other.

This process will continue happening for many rounds/generations, and I wish to simulate a changing environment by gradually altering the game parameters over the generations. Theoretically if the simulation were run for long enough (we're talking 1000s of rounds), the end result would produce a NoAI script that is very competitive no matter what the game parameters.

The main challenges I see are:
- Gathering the appropriate information at the end of the previous round
- Making changes to the NoAI scripts between rounds.
- Making changes to the game parameters between rounds.
- Writing my own script that can handle all the processing between rounds automatically.

What do you think? Is this possible? If it is, then is it interesting enough to justify the effort involved in making it work?

Thanks for any advice you can give!

[planetmaker]

Sounds like a very nice idea. It also sounds like a very ambitious idea. The most ambitious part is IMO the "adapt AI code between rounds". The other parts are something which could be solved with a moderate amount of effort. The part with genetic AI code... I guess you could spend at least a whole PhD thesis on that part. But it'd be a very interesting thing!

Cheers,
pm

[Zuu]

For tuning parameters of an already written AI your idea sounds good, but to make a program that writes AIs out of nothing sounds very complex.

Adopting OpenTTD to give you the output you need will probably be the easy part.

[FHS]

The only problems I would see, are that running a game for the standard period of time consumes a lot of time and that this idea generates a new specialised AI for every difficulty setting.

Apart from that I would like this idea to be tried.

[yoyo1505]

My main motive for this is not to produce a good AI, although it would be satisfying if that were the result. I'm more interested in simulating evolution in an AI. Compared to most organisms the generation times are wonderfully short!

[Michiel]

Sounds very cool, and very hard
You might wanna focus on just road AIs, which are a lot easier than rail and more interesting than ships/planes, but still offer lots of possibilities. You would probably need to hardcode certain primitives, such as building stations and buying vehicles, but maybe you could evolve algorithms for station site selection and road building. That'd be pretty cool!

[XeryusTC]

Seems like you want to use evolutionary algorithms (EA), something which can be quite useful in optimising AIs. You can't just build a load of functions and hope that the code will improve itself so that it becomes the best AI around, that sounds more like a job for a proper neural network, but I think that those are too heavy to properly use with OTTD.
Another downside of EA is that you need to run loads of game to get the job done, it can take several hundred generations before you get any satisfying results.
The up side is that you get an AI which would be pretty much fool prove in any kind of situation as it has experienced everything and improved itself over time. Or well, that is the general idea behind EA

[FHS]

Ofcourse if someone would modify OpenTTD to run all these tasks automatically and display the current generation too, it would be one of a hell a lot easier.

[cmoiromain]

Maybe a way to do that would ne to build functions with many different parameters (for example, a "build station" algorithm that has a variable length, width, that can be ro-ro or terminus; another for train length; another for money manking lines...), and another global algorithm that takes all the parameters used by one AI (plus the settings of the map played), and on that tries to create the best configuration for every kind of round. This is the tricky part. It consists of a complicated version of creating a block diagonal matrix out of all the data gathered.
This is a really interesting experiment, though having games last until 2050 is maybe a little too long. maybe 50 year games using fast forward would suffice, and allow for more generations to go through, therefore a theoretically more efficient AI at the end. Ideally, you can access a supercalculator and run the tests there, but I hardly see how you could get your ands on one

Good luck with your project, please let us know iabout the progress you make, it could be very interesting.

[comp615]

Perhaps if you build an AI with a good number of CONSTANTS defined, you could alter the constants between rounds to compete against each other and see which one rises above the rest and propagate changes that way...

[Blustuff]

Generating random mutation in the code will generally produce syntactically or semantically incorrect programs. You could generate valid mutations by using a grammar of Squirrel, but then, if you try to generate AI from nothing they won't survive at all. Not a problem either you can start from a basic AI.

At this point you might want to know how many mutations have to be tried to get a satisfying result. Like for natural organism, almost all of the mutations will only shorten the life of your AI. Programs are basically trees with thousands of nodes. Each of these nodes could be mutated into many other nodes. If you want to count the number of possibilities for some size of an AI it would probably be higher than the number of atoms of the universe. Considering the human lifetime you'll never see a good AI produced by your algorithm.

That's why in such algorithm we never try to generate a totally random behaviour. The hard thing is to find what must be random and what must be fully deterministic. As mentioned before, you could only try to choose random parameters for existing AI. But personally I think that these parameters could be chosen with more direct algorithm like learning or optimisation.

[zooks]

Tune down your scope if you want to use genetic algorithms. In this case your fitness function is running a full game, which takes really too long. As said before, with such an enormous search space you will need millions of generations before you'll even see any behavior at all.
So instead of using GA's on the whole AI, use it on a small aspect, like optimal station configuration or something like that. I also tried to give a go at this kind of AI for ottd but I can't find the time to work on it.

Best

fyi. I am a 3rd year student in Artificial Intelligence at the university of Nijmegen, the Netherlands

[Kogut]

Unfortunatelly in reality evolution is very, very, very slow. And almost all mutations have bad effect (no income) or are even lethal (compile error)

I think the most important problems are:
- what and how should be mutated (whole functions from various ais, lines of code, letters)
- how accelarate evolution (to very slow) - probably by automatic running next games.

It seems rather impossible to get working (or even compiling) ai from permutations of signs, so sigle gene should contain more complex structure.

And I think that it may be good idea to start from helicopters/planes only - it is probably the simpliest type of transport to use.
But I fear that even that may be too complex.

[IQuit]

Is there a No-GUI mode so the game can ran faster?

[CommanderZ]

Is there a No-GUI mode so the game can ran faster?

There is dedicated server, but zooming on a unchanging flat water area has very similiar effect (=virtually zero slowdowsn by graphics), but the games will still take at least minutes to finish, which is too long for genetics. It would take weeks to get some results even if one game lasted a minute.

[Kogut]

I thought about years.

[IQuit]

I was hoping for "openttf -v null" and stdin/stdout becomes console ...
It is OK to take weeks, as long as they can be run in batch mode.
Still need "fast_forward" and "exit_on_game_end" commands though.

[Rubidium]

"-v null" is implicitly fast forward. "-v null:ticks=n" can be used to tell how many ticks it should run for, e.g. 27010 is 365 days (74 ticks per day). With -d ai=n (don't know the exact value of n) it will output anything printed to the AI debug window to the console (don't know whether it's stdout or stderr). There is no console input.

[Blustuff]

I thought about years.

I thought about the lifetime of a star, but that's only because I don't know about astrophysics and if anyone knows something longer, it could probably be a more suitable comparison.