Emergent Intelligence

well if you want to find stuff on "swarming" try googling "flocking". you can find _tons_ of algorithms and demos. i believe there are some on this site in the articles section.

Quote:

Original post by Prozak What other work is being done in AI that deviates from the "lets build a brain" process, and goes more towards a "lets build a few million quasi-intelligent" bots, and watch them better themselves...?

heh, pretty much all of the work being done in AI deviates from the "lets build a brain" process. it's pretty much impossible with our current understanding of the brain to try and build one. we simply don't know enough about how the actual system works to build anything resembling the same complexity.

you can look at state machines, path finding, neural networks and genetic algorithms to start. i'd also suggest sitting down and reading all the articles under the AI section on this site to give you some ideas about what's out there. i'm sure there are a number of good books suggested in the books section as well that can get you on the right track.

-me

"Emergent behavior" is really just a fancy way of saying "a coincidence that really looked cool". If you build an agent based model where each agent is thinking for itself using rules to define it's own behavior, sometimes these agents may do things that seem to be working with each other. In fact, there IS no cooperation happening - each agent is only secondarily aware of the other agents (if that), but they have started to do things "near" each other that makes them look like they are cooperating.

With a simple flocking behavior, this can be seen as each "boid" doing it's own thing... (i.e. the rules for moving with the world objects but not coliding with the world objects) and yet the perceived result is that they are moving "together".

In RTS games, there is a high degree of perceived emergent behavior. This happens when simple rules for each agent (unit) is designed in such a way that it tends to compliment other units' simple rules.

When I had a chance to ask Peter Moleyneux and Will Wright about designing and testing emergent behavior, Peter talked about how horrifying it is to watch your little system working along, doing amazing things that you didn't really design into it... but all the while knowing that at any moment it could collapse in on itself!

First off, 'Swarm Intelligence' is NOT the same as flocking behaviours (c.f. Craig Reynold's Boids). It's about 'Hive minds'.

As to Dave's comments...

Quote:

Original post by InnocuousFox "Emergent behavior" is really just a fancy way of saying "a coincidence that really looked cool". [ ... ] In fact, there IS no cooperation happening - each agent is only secondarily aware of the other agents (if that), but they have started to do things "near" each other that makes them look like they are cooperating.

This is absolutely NOT the definition of emergent behaviour or cooperative agents as used widely in the AI community and with reference to those definitions, the above carries several errors.

I don't have the time at the moment to spell out everything that is wrong with the above... I urge anyone who wants to know the truth about emergent behaviour and/or cooperative agents to read some literature.

For the time being, all I will say is that emergent behaviour is (typically) the result of nonlinear feedback mechanisms within sub-units of an entity that aren't specifically encoded to produce these 'emergent' outputs... while 'cooperative agents' specifically take into account the state and actions of other agents when making their own decisions (so cooperation IS encoded in individual entities). Hive minds are examples of BOTH of these systems... the sub-units act indivually yet display cooperation and the hive as a whole displays emergent behaviours that aren't specifically encoded within singular sub units.

Cheers,

Timkin

Thanks Timkin, either I didnt make myself clear, or got completely missunderstood, but the thread was going off in the wrong direction...

Im not looking for flocking behaviour, im looking for cooperative problem solving behaviour, even if that problem solving "emerges" from the "hive", an example would be how ants solve the "find the path between A & B that takes the less energy to make"...

..no one ant solves it, its a group effort, although I dont think any one of them realizes that...

So I would like to know what other practical works, even "visual" simulations are being worked upon with basis on EI...

*shrug*

Well, I'm just repeating what game AI designers, programmers and litterature consider "emergent behavior" to be. Perhaps it is different in the "real world"... but seeing as this is a game AI board, I didn't bother addressing contexts other than that of game AI.

Look at particle swarm optimization.
Theres at least 1 good article on it at citeseer.
Its rather interesting.

What it is designed for is stochatic finding of a single tuple(a maxima/minima) over the reals.

I've worked with it this summer, so I can answer questions regarding it. ^_^

Quote:

Original post by InnocuousFox *shrug* Well, I'm just repeating what game AI designers, programmers and litterature consider "emergent behavior" to be.

Could you provide some references Dave or perhaps identify these people? Either these people are wrong and are propogating erroneous information (in which case they should be correced before they set the industry back another 5 years) or you have misunderstood what they were saying/writing. All I can say is that I've never heard a game designer or programmer talk about emergent behaviour in the way you have, nor have I seen Game AI literature that refers to it as coincidence and involving no contextual awareness.

Cheers,

Timkin

Quote:

Original post by Timkin All I can say is that I've never heard a game designer or programmer talk about emergent behaviour in the way you have, nor have I seen Game AI literature that refers to it as coincidence and involving no contextual awareness.

Perhaps in my being flipant and terse, I did not express myself fully and/or overcompensated. However, since we have determined that this is not the goal of the OP, it is not appropriate for me to detail the differences here.

Prozak: Have you read anything about neural networks or genetic algorithms? A lot of times those can get some emergent behavior going on. NNs and GAs evolve in a way to solve their problems as best as possible.

EDIT: Here's an example of sort of emergent behavior I got once. I made a program that pitted 2 armies of triangles against eachother. The rules were, if you killed a guy on your own army you lost a some points, and if you killed a guy on the other army you gained some points. Every few minutes, I stopped the battle, and the guys with the best score moved on and "breeded" a new army. Then I would start over. Well, what I expected was that these armies would fight, but that's not what happened. At the beginning of each battle, the triangles would always shoot all of their bullets right away and never move. Obviously, since my triangles were lined up in rows and columns, a lot of friendly fire was happening. Well, after a few generations, my armies learned to shoot all of their ammo right away but not kill eachother. Right when the battle started they would all turn to a precise angle such that they could shoot everything and not kill anything. It was pretty neat, even though they weren't doing exactly what I had wanted them to do.

nice
your armies learned that world peace was the best answer
takes a bunch of triangles to figure that out what people cant...

That's pretty cool, but it sounds more like genetic algorithms than emergent behaviour. Although I guess the two are somewhat similar.

well, what was happening was that the genetic algorithm(it approximated it, k?), was displaying emergent behavior.
Interesting, tho.

Well, we could dive into the definitions of EI, but I think i'll stick to my original defenition, that EI is demonstrated by a group of "limited" individuals coming together and solving problems none of them could solve alone.

The triangle army experiment indicates that each triangle came to its own conclusion on how it should operate, its wasnt a communal achievement... and also lets not forget that "breeding" in those digital universes many times means "chaotic cloning" more than anything else...

From the original post is Emergent Behaviour really the right thing to be looking at rather than Genetic algorithim/Programming
(never quite know the difference) or a mix of the two?
Creating a million bots which display emergent behaviour would not have any of them learn from the experience. Somebody at BlitzCoder wrote a simple FSM battle similar to the triangles
example. The flee/attack code made it look as if weaker/smaller
'triangles' were hiding behind stronger/larger triangles and ganging-up on stronger opponents. 'Ganging-up' was never coded but occurred as a by-product of the programming.
However, this would not allow...
"and watch them better themselves...?"
Maybe those triangles that flank or box around larger enemies
to reach smaller enemies should be rewarded etc etc.

I have done some reading on the topic, but am certainly not an expert. Here are a few sites with ideas/definitions about emergence at varying levels of depth. If nothing else, they probably have some good references:

http://people.imise.uni-leipzig.de/alexander.heussner/files/Emergence_in_ALife.pdf

http://www.arch.usyd.edu.au/~rob/study/EmergenceAndArtificialLife.html

http://sites.inka.de/moebius/origami/dessau2003.pdf

Yep. I suck. In fact, I should be so embarassed by myself that I should post anonymously thereby avoiding all responsibility for what I post.

From AI-depot.com

Quote:

"Emergent behavior is behavior that looks complex and/or purposeful to the observer but is actually derived spontaneously from fairly simple rules."

From Emergent Behavior, Cellular Automata, and Our Game “Mr. Froggy”

Quote:

"Recently, emergent behaviors have become crucial in game design and implementation, where it is important to increase game’s intelligence by adding more unpredictability into the game. Chris Crawford in his book [6], states a game he would like to build, “Attack of Cellular Automata”. He quotes that it might be fun in fighting a war with cellular automata. The cellular automata have emergent behaviors, which gives rise to interesting game-play. In this paper, we report our approach to realize some of the above ideas using conceptual framework of cellular automata. Sections II and III briefly review use of Emergent Behavior (EB) and Cellular Automata (CA) for games. Section IV reviews open source Java applet MJCell v. 1.50. Our framework for software architecture for developing CA games is described in Section V. Section VI discusses our game “Mr. Froggy”, and Section VII gives concluding remarks. II. EMERGENT BEHAVIOR AND GAMES “Emergent behavior is that which cannot be predicted through analysis at any level simpler than that of the system as a whole… Emergent behavior, by definition, is what’s left after everything else has been explained” (Dyson & George, 1997 [9]). Emergence is also defined as the action of simple rules combining to produce complex results (Rollings et al., 2003 [17]). A game with emergent properties can create an illusion of intelligence to a game AI (Scott, 2002 [19]); it can make even the game designers surprised on how the game runs, how the game evolves, and even they do not know the best strategy to win the game. Emergence has become a popular buzzword over the past decade (Kreimeier, 2000 [12]). Kreimeier [12] reports that Marc LeBlanc attempted to make a case for emergent complexity as a possible source for "fun." In his view, such emergence creates larger spaces to explore, offering the player more features to discover and more challenges to meet"

From a Gamasutra article about the state of the industry:

Quote:

One nice side effect demonstrating the intrinsic power of such a straightforward approach to AI can be seen in something called "emergent behavior." A developer faced with coding a complex AI can instead break it down into smaller pieces. Rather than having to code thousands of rules for every conceivable situation that could arise in a game, lower-level behaviors are coded individually and then linked in a decision-making hierarchy. The interaction between these low-level behaviors can cause higher-level, more "intelligent" behaviors to emerge without any explicit programming. This is the basis behind flocking, an AI technology that seeks to emulate the behavior of large groups of animals, such as flocks of birds or schools of fish. No one member of a flock actually knows anything about the motion of the flock, and yet through individual actions their motions are coordinated and fluid. Flocking has found its way into a number of first-person shooters and RPGs as the basis of sort of artificial life, another form of AI technology seeing more use in games.

Quote:

Original post by Anonymous Poster I've been a game programmer for 10 years at 4 different companies and we all consider emergent behavior to be what InnocuousFox says.

[sarcasm]Gee... but you don't have any "credentials". Obviously YOU aren't snootty enough to provide us with an opinion or observation that matters.[/sarcasm]

(Crap... I'm not a doctor with medical training and all that credentially stuff, but I can sure as hell diagnose a broken arm, can't I?)

Quote:

Oh no, we must not use an improper definition!

As I've made the point before, some people spend so long fine-tuning their little definitions and theorems in the land of academia that they don't actually DO anything.

Thanks for your input. I wish you weren't anonymous too.

Back on topic:

Prozak, has your question been answered yet? If not, can you provide any more context about what you are interested in? What kind of 'problems' are you interested in solving?

Depending on the problems you are interested in, there may be a better field to look at than emergence.

Gee, I wish I had joined in on this one sooner.

Prozak: I think InnocuousFox said it best with:

Quote:

Emergent behavior" is really just a fancy way of saying "a coincidence that really looked cool"

As far as most _games_ are concerned he's bang-on. In your game you just need a way of presenting an illusion of intelligence (or cooperation) to the player. Graphics programmers fudge lighting, Game AI programmers fudge intelligence. :)

You wanted examples, so I give you mine. :)

Not long ago I wrote a tank-battle game in which the enemy tanks choose (mostly randomly) from a set of actions. Each of these actions is comprised of a set of other actions (which are selected sort-of randomly).

For example, a tank could decided to turn towards the player, and move forward at the same time. This makes the tank look like it's chasing the player, although the tank itself has no concept of chasing. Turn and move forward are separate actions that could be applied at the same time.

When a tank bumps in to an obstacle, it can take a number of different actions-- back up, back up and turn, just turn, wait, turn towards the player, shoot, etc..

Everything had to be kept really simple because the game needed to run on a slow cell-phone-- every spare drop of processing power needed to be saved for the 3D wire-frame graphics. lol

People who played the game we're generally happy with the different tank opponents, and found these opponents very tough yet still 'tank-like'.. Many people commented on how smart the tanks were for using obstacles as cover; they would duck out, fire, and then retreat back behind the obstacle always keeping the players line of fire blocked.

This particular behaviour was coincidence. The simple rules that the tank sort-of-randomly decided to follow ended up making it LOOK like the tanks were using cover, but in reality they had no concept of cover, or blocking, or hiding.

Technically what was happening was this:
-Tank would randomly choose to chase player (or drive around).
-Tank would bump in to a wall.
-Player would turn to lock on to enemy tank because a stuck target is easy to aim at.
-Enemy tank would back away from wall.
-Enemy tank could not move forward much because of the wall, therefor enemy tank spent more time turning towards player.
-When player was within enemy tanks randomly generated firing arc, tank would fire.
-After shooting enemy tank would randomly pick a new action.
-If new action resulted in tank moving forward, it was likely to bump in to a wall.
-Bake in preheated over at 350 degrees for 50 minutes or until evenly brown and you now have one tank that looks like it's using cover.


I was very happy with the results.

Good luck!
Will