Evolving Artificial Intelligence

[Hiroshe]

Kinda had an idea for artificial intelligence, though I don't think it's original. I don't know much about AI, so I'm taking a shot in the dark. My idea comes from biology and evolution (not new in computer science).
The 'algorithm' for evolution is simple. Lets say you have a pool of cells. New cells are created only from surviving cells. The new cells have the traits of the old cells, but slightly different. If a cell poseses a trait to allow it to survive, it will make a new cell. If a cell does not poses a trait to survive, or has a bad trait, it will not make a new cell.
I had an idea (though probably not original) about making an artificial intelligence using evolution to "make it self". Lets say you wanted to make a chess evolving artificial Intelligence system. You would make a program that would read data from a file, and interpret it as a "language". For example, 023 001 022 might mean if there is a pond at 2-3, move any peice around to intercept it. Next you write a nex generation program. It would read the data from winning files, and make them slightly random. Lastly you would need to make an emulator, to play different files against eachother, and make sure only winners get to have another generation. You would make random files, and play them in the emulator until you have a good ai.
The problem I see with this is the files might become too big! It might eventually hard code all of the possibilities into the data. The language would have to be made carefully to abstact the data.
Another problem I see would be how much space it would take to predict possible moves. Since it makes moves only based on experience, it would have a hard time dynamicly predicting the next move. To get past this, you can make a hybrid ai by hard coding a possible move finder, and feeding that into the ai part of the program.

Would anyone commennt/expand on this idea?
This would make for a vary interesting school project :P

[swinefish]

Hmmm...

That does sound very interesting. Let me get this straight - the files used to determine possible plays are the "cells" which evolve right? So only the best strategies - the "strongest organisms" - survive through to the next generation right?

I must say I like this idea. The basis is the same as that of learning algorithms - no hard coded strategy, at least not initially, but instead the best strategy is discovered in a number of plays. But I like your evolutionary twist on it.

The way I would handle this is as follows - instead of having narrow strategies as you have suggested - if there is a pawn at 2-3, intercept it, I would suggest, at least initially, have broad strategies, such as "eliminate all pawns". Like this, it shouldn't be too hard to come up with a good initial base of strategies.

Next, you pit strategies against each other. You let them play a game of chess against each other. Some of them may never actually result in a win, so after say 100 moves evaluate them on points. Now, we have a limited number of surviving strategies.

Now comes the fun part. Each of these strategies has 2 offspring:
1) A child. This is derived from the parent, although their might be some slight "replication errors" as in evolution ie the strategy might change slightly.

2) A hybrid: Each strategy is hybridised with another strong strategy, to get potentially more powerful strategies (as far as I know hybrids are often far stronger than either parent).

Now these children, these hybrids AND the original parents are again pitted against each other to determine the strongest, and the process repeats ad infinitum. Well, probably not forever, but a few dozen would get some very strong strategies (probably all of them hybrids of hybrids).

It's a nice take on learning algorithms that I haven't heard anywhere. Never really thought of it.

From their what might be interesting, is to have this AI play against a human. If the computer loses, the current strategy and the user's strategy would go through the same process - a direct child of the user's winning strategy, and a hybrid of the 2 - the best of learned AI and the best of the user's intelligence coming together. These would then play each other and determine the new strongest strategy before another game against a human.

:) sounds like a nice idea. Wish I had time to look at it now

M

[Hiroshe]

Thanks for responding.
>Let me get this straight - the files used to determine possible plays are the "cells" which evolve right? So only the best strategies - the "strongest organisms" - survive through to the next generation right?
Correct.

>From their what might be interesting, is to have this AI play against a human. I thought of doing that too. But it would take way too long. But, making it play online against 100's or even 1000's of players should do it. :P

>instead of having narrow strategies as you have suggested - if there is a pawn at 2-3, intercept it, I would suggest, at least initially, have broad strategies, such as "eliminate all pawns". Like this, it shouldn't be too hard to come up with a good initial base of strategies.
I ment "if there is a pawn at 2-3, intercept it" as an interpretation of the random "DNA". It would be one of the tousands of moves of "eliminate all pawns." I like your idea of having an abstact strategie, and "training" the program to fullfil it. That would speed up the proccess of evolution, and give you more control over how the ai acts.

>Next, you pit strategies against each other. You let them play a game of chess against each other. Some of them may never actually result in a win, so after say 100 moves evaluate them on points. Now, we have a limited number of surviving strategies. Yes. I was also thinking of playing the surviving ai's something a little bit more random so that they learn to handle other situations. Maybe every 20th game or something?

>A hybrid: Each strategy is hybridised with another strong strategy, to get potentially more powerful strategies (as far as I know hybrids are often far stronger than either parent). That would be great. But how would you hubrid both strategies togeather? Hmm... Lets think of breeding dogs. We can divide the "DNA" up, and randomly mix them up until we get a set of "DNA" that can beat it's own parents. Nice idea!

I might try this with a tic-tac-toe game as a school project. Eventually it should figure out the perfect tic-tac-toe algorithm that will never lose.

[swinefish]

Great idea to start with tic-tac-toe. You realise pretty quickly how big chess is lol.

I really like your ideas. Thinking big :) I'll keep an eye out for any more posts you write, I like the way you think.

What's nice about powerful hybrid strategies is that they should be able to deal with multiple styles of play. So although a single algorithm cannot be perfect in any one game, the hybrids would in fact contain "DNA" information of multiple strategies, all the strongest. And I agree that if done right, it should make unbeatable ai...

In my opinion, the only problem with almost every ai project I've ever seen is narrowness. They are written to solve a single problem. What I think would be far more interesting is an "artificial brain" - a system that contains subsystems closely linked to the sections of the human brain - language, colour, motion, things like that. It would also contain a subsystem that, when it received input, would decide which subsystem would be best equipped to handle it, and give it that information.

Those subsystems themselves would implement some kind of learning algorithm - something like yours actually :) - and so would hopefully learn to solve any problem given to them. A robot with that kind of brain would be the perfect dancer, the perfect student... pretty much perfect at everything it did, after it had tried a few times.

Sorry about rambling :)
Good luck with implementing this

[Hiroshe]

I like your rambling :). If were to try to make a human ai (I think tic-tac-toe is a better start), I would do something like you said. Except I would make it develop it's own learning stratigy (nested learning anyone?). I'm not smart enough yet to give details, but I would probably try to make diffrent parts of out brain be developed separately and just link them togeather. Then either using it's developed learning system or my own, I would try to teach it instincts using real examples. Hmm... but getting enough example's would be hard.

This is starting to sound like a multimedia seiries called ".hack". I thought most of it was impossible. The back story is that some programmer wanted to make a perfect ai. To do it correctly, he secretly installed it on to a game to collect information from users. Also, interestingly enough, it said a virus was released in 2010 wiping out all computers except one's that were running a certian OS. That's obviously impossible. But google is releasing their OS in 2010 which will shake up the OS market.

And one last thought. Let's say we had a perfect robot to do all our work for us. There would be no such thing as work or jobs or money. In that world, wouldent it be too easy to live? Wouldent we "devolve" becouse the ability to do work is no longer a factor. Would we become like the people on the ship in the movie "Wall-E"? I think it's better to leave ai's and robots out of the work force for now, untill we can modify our own DNA and stop that from happening.

[swinefish]

Personally, no I don't think peopple would stop working. For the most part, people I've met like doing things, they all have certain jobs they really want... teaching, writing, the arts, things like that. I believe that having incredibly intelligent learning robots would help in two departments.

1) Manual labour. certain things are still only trusted to humans because of our dexterity, and our extensive intelligence. Being able to create robots capable of these jobs would free people up to do the things they wanted.

2) Space exploration. I believe the ability to make thousands of robots with a desired level of intelligence, and alos the ability to learn very fast, would make space exploration significantly cheaper, and more efficient. You don;t have to waste precious human lives, only a non feeling robot, who still has the intelligence to adapt to its environment.

Any thoughts?

[Hiroshe]

Making robots do the dirty work? Sure. But your taking out a large field of the job market. I would guess the customer service market would go way up with all the technology. Not to mention, these AI may need human assistance to learn what thay are suppost to do, or how to use special hardware.

Robots in space. Hmm. It would make dangerous space mission's easer. Going through the astroid belt? No problem. Fixing a space station befor it crashes into the sun? Well it's worth a try and there is no risk.

>Any thoughts?
Drop off simple (well, alot more complicated than tic-tac-toe) one's at Mars that have the ability to make better robots out of what ever is on the planet. Wait 500 years. Come back and see what kind of society and technology they have developed. :P

[swinefish]

>Wait 500 years
You're assuming we're gonna make it another 500 years lol. I've always been an apocalyptic thinker. I think we'll all kill each other off soon enough. But if anybody survives, at least unemployment won't be a problem.

I realise super intelligent robots would remove large portions of the work environment. But IT has always been about making work more efficient, and therefore reducing the number of available jobs in a particular field. However, new jobs have always opened up, and IT has not been shown to cause any predictable trend in unemployment (at least not that I'm aware of) so I suspect other jobs would appear. Maintenance, that kind of thing.

M

[ithelp]

It will not fit in any computer's RAM and if you want to process it from file it will take too much time, anyway I think in a decade from now robots will replace workers in many industries.

[swinefish]

Yeah I do realise the problems with RAM and file access. However I think that the idea is good enough to warrant a lot of thought. And I believe that if we look at this long and hard (and possibly wait for improvements in technology) we will find solutions to the problems, and improve it in general. :)

[Hiroshe]

If you could tree and orginize all the data, you could speed up the AI by alot. However, the positions of the "if statments" might matter.
RAM... Yeah, thats an issue. If it was really big, you could save it on a really big hardrive. :P Since the language is basicly a long set of if statments, man, you would have alot of if statements for chess. Instead of just having the bored as the input to the AI, you can have all the possible move's as user input. That might make it smaller.

[MosaicFuneral]

I wanted to do an evolving cell AI simulation once, but I forgot some of my biology lessons about related topics and was to lazy to walk over and pick up my books on it. :icon_rolleyes:

If you ever get around to writing something like this, let me know I'd optimize it till it could run on a 4004(yes, I'm insane).

[Hiroshe]

Expect a PM this year if I decide to do it. :P

[invisal]

Learning AI is already existed except it is built to serve their specific purpose. I haven't seen any learning purpose-less AI.

[Hiroshe]

Learning AI is already existed except it is built to serve their specific purpose. I haven't seen any learning purpose-less AI.

That would be nearly impossible with today's technology. Not to mention the complexity (though manageable). We haven't experimented enough to know what will happen, or the best way to do it.
Unless, you mean an AI that is built to learn any one thing. With a little human assitance (input/output functions), it's possible.

[tdeck]

I think the big problem would be coming up with some sort of "DNA" language for the "cells" that would have a chance of doing anything with randomly produced code. Otherwise, what you'd probably have in the first generation is a bunch of creatures that don't do anything at all, and so are equally unfit.

You'd need a finite set of instructions and a very simple format for conditionals and looping. Maybe have the "DNA" program loop as a whole and take out looping constructs, leaving only conditionals.

[Hiroshe]

I think the big problem would be coming up with some sort of "DNA" language for the "cells" that would have a chance of doing anything with randomly produced code. Otherwise, what you'd probably have in the first generation is a bunch of creatures that don't do anything at all, and so are equally unfit.

You'd need a finite set of instructions and a very simple format for conditionals and looping. Maybe have the "DNA" program loop as a whole and take out looping constructs, leaving only conditionals.

I was thinking of having an if statment syntax. On evolution, after selecting a statment or adding a new one, it can: a) add an "and" to the statement. b) add an "or" to the statement. c) change the value's of the statement or the action. I'm not sure about looping in a turn baised game, but it would be usefull for other things. The AI would simply be called when the computer need's a move.

Also, for creating the cells, Instead of starting off with a large random DNA, you start off with nothing. When the DNA get's a usefull instruction that will allow it to move one more that it's parent (nothing), it will 'win' and become the new cell. Eventually, it should have instruction's for every single move as long as you play it against either a random move AI (not evolving) for every x games, or play it against a variety of other cells, or both.

This may not be true for a bigger game like chess. You would probably end up doing what swinefish suggested and create seperate sub-cells to do other tasks (ie, "destroy all pawns".)

Thanks for the comment.