okay, just an idea that''s been going around in my head. i''ve been trying to think of a way to let agents learn (forget what, just learn). i thought of using neural nets, but i didn''t like the idea of try, die, try, die and so on. I wanted them to learn in real-time. So, i came up with the idea of AI tags. let''s take a (well, in this case) simple setting. you need to destroy a crate, but arn''t strong enough to do it by hand (you have no weapons). So, the agent analysis everything around the area. It sees a large object suspended over the crate by a rope. The object has the "DROP" and "HEAVY" tags, i.e. it can fall down and is very heavy. Using some basic math which the agent can work out if the drop would break the crate. the answer is yes. So, how to drop the object. The rope (dont ask how the agent knows it''s holding the object up, it just does). The rope has the "CUT", "UNTIE1" and "UNTIE2" tags. "CUT" means it can be cut, "untie1" means it can be untied at the first end (holding the object), and "untie2" means it can be untied at the other end (on a rail). now, first of all it checks to see if it can cut the rope. nope, nothing around to cut it. secondly, it checks to see if it can untie it. Untying a rope requires you to be within reaching distance (again, that can be calculated). can it get within range? no. now, lets check for untie2. yep, it can reach the rail. so, the agent then finds a way to reach the rail and walks to it. it then remembers what it had to do then (untie end 2), which will then cause the object to drop, causing the crate to smash. very simple. the end result is a rope that has two tags remaining (untie1 and cut), an object that has 1 tag remaining (heavy) and a broken crate. one problem - how to implement in C, or preferably, a C library which exports functions into lua thanks in advance

I see what you are saying, but not exactly sure how the agent actually learns from that. That seems more like scripted AI than anything. TO make it more like learning, the AI would need to start randomly activating tags in the environment.

Furthermore, how exactly does the AI know that the box will hit the crate will hit the box when it falls. Sure, you can code it to do that, but how do you abstract and generalize that concept enough to make it work in other situations?




Gamedev for learning.
libGDN for putting it all together.
An opensource, cross platform, cross API game development library.

Ah, the impossibilities are endless!

It sounds more like some sort of finite-state machine, where you supply the agent with a number of alternative functions he shall try out.

If (breaks){success}; elseif{try next function};else....

Neural nets in conjunction with tags similar to those could be cool, though...

At first glance, it also seems to have some things in common with Annotated Objects...

ZealousElixir: yeah, pretty much what i thought .

*sigh* back to the notepad (.exe) i go

Could some of this trial and error be modelled as imagination? Without giving the agent an "awareness" of the percentage chance that something will work, could you have them "think it through" and look for snags? I''m not much for AI or CompSci work, but I remember in my CogSci courses we spent some time talking about models of imaging for problem-solving. This sounds a lot like one of them.

Remember in that Xiao Xiao #7 movie (#8? #6? Beats me) when the little stick hero is trying to decide which guard to throw the knife at? That was a great illustration of what I''m thinking of. I think newgrounds has the movie, and it''s worth watching for the violence even if I''m wrong.

quote: Original post by Iron Chef Carnage
Could some of this trial and error be modelled as imagination? Without giving the agent an "awareness" of the percentage chance that something will work, could you have them "think it through" and look for snags? I''m not much for AI or CompSci work, but I remember in my CogSci courses we spent some time talking about models of imaging for problem-solving. This sounds a lot like one of them.

The problem with imagination is that you need an internal model of causality (even one that doesn''t truly represent the world) to actually do anything useful. Imagination is really just a form of prediction except that you can instantiate the causal rules for yourself. One theory is that humans imagine outcomes based on arbitrarily created hypotheses of causal relationships and then ask how likely those relationships are if they are performing prediction. With experience, we learn better estimates of the likelihoods of certain causal relationships over others and hence we can use our imagination for planning.

So, the problem with using imagination in your game (as described above) is that the agent would need to store all of the physical laws of the universe (or worse yet, learn them and THEN store them)... and if you can build an agent to do that (in more than a very limited environment) then you shouldn''t be making games... you should be making billions!

Cheers,

Timkin

The way you described to solve the problem with the rope and the crate was described long time ago (I don''t remember now if it was in the 60s or in the 70s) and is called "Means and Ends Analisys", it was implemented in a program called the GPS (General Problem Solver).

About imagination, in your hypothetic game. I think that it''s just that the agent has an internal model of the world, and in his model, he tests the "action plan" (untie the rope). If in his internal model, the plan works,then he implements it in the real world. The rolw of learning here can be placed in adjusting the right parameters for the internal model of the world, to be able to make good predictions.

Almost all of this was actually implemented in a program called SHRDLU, that is coded in Lisp, and that was executed in a PDP-11 (those of you who know something about computer history will know how old is that machine)

You could just use another instance or dimension of the gamephysics engine to implement imagination. Two parallell game-engines, that is.

The agents IMAGINATION-ENGINE and the PHYSICAL-ENGINE are the same, but the imagination-engine incluses a genetic algoritm that runs through a series of trial-and-error behaviours (ie. imaginatory versions of himself tries different stuff in imagination-engine; judges from result; evolves), until he succeeds.

Then he follows the successful pattern in the physical-engine.

To make for IMPERFECT DECISIONS:

-The imagination-engines WORLD PARAMETERS could be random estimations of the physical-engine at birth of the character, which with experience gets more tuned to the physical-engines parameters.
Thus, the more experienced the character is, the less prone to failure will the actions he decide to implemet be.

-The LEVEL OF IMAGINATION of the character could be managed by regulating a random-at-birth imagination parameter, that sets the number of cause-and-effect steps that the character can go through his mind. If the character has low level of imagination, the level could be set at two, meaning that he could only run through behaviouralpatterns in his imagination-engine that required at most two steps to complete. For instance, he could come to discover (through the genetic algorithm in his imagination-engine) that he can (1) climb a ladder, and then (2) cut a cord sustaining the weight you talked about = crushing the bos. But he could not figure out to do deeper stuff, like (1) opening a box of sorts to get a knife (2) climb the ladder (3) cut the rope = crushing the box, since this would require more imaginatory steps. There could be a variable that made the levels increase as time went by, or was managed by the number of trials he had gone through (giving him experience, and deepening his imagination). Of course, this could be better modelled with parameters that was more fuzzy.
Thus, the more imagination the character has, the more complex will his solutions be.

-ITERATION OF SOLUTIONS: There could also be a restriction on the number of times the genetic algorithm would itereate in the imagination-engine. In real life, some people spend a lifetime going through alternative solutions to a single problem, while others decides for the first solution that pops in to their mind. This could be more of a personality-parameter that was random from birth, and relatively stagnant. Or, it could be a dynamic parameter that changed due to the success/failure rate of the actions implemented in the physical-engine. If, for instance, lots of the decisions derived in the imagination-engine turned out to fail in the physical-engine, it would only be natural that the character would be scared and now more cautious, thus taking more time to think through alternative decisions in the imagination-engine. It would even be cool to implement stuff like trauma, where too much failure would make the character go bananas :D
Thus, the more iterations the character goes through in the imagination-engine, the better will probably his solutions be. But since some characters randomly are born with deeper levels of imagination, and better estimations of world parameters, they need less numbers of iterations to come to a good solution...which takes me to the next topic.

-SPEED OF THOUGHT: If time is of essence in the physical-engine, then it is important that the character arrives at a good decision in the imagination-engine fast. Deep level of imagination, and many iterations of possible solutions are things that will make a decision more accurate, but also slow down how fast the character arrives at a solution. So this is a trade-off, to make for better gamebalance.
Thus, characters with great speed of thought are less prone to be eaten by a tiger while thinking of ways to tie his shoe-laces.

-MEMORY BANK: Well, this is a very important subject when it comes to learning. Since I have not studied NNs very much, someone else should probably find some cool solutions here...but perhaps it could be done with multiple arrays, representing memories.
With Neural Nets, you could construct arrays of data that represent objects and other stuff in the physical-engine to the imagination-engine. For instance, a hollow rectangle (2d) viewed with a eye with 4x4 resolution, would render a visual memory-array with the numbers {(1,1,1,1)(1,0,0,1)(1,0,0,1)(1,1,1,1)}.
When the character is introduced to a problem, the relevant objects included in the solution that he derives are memorized as visual-arrays (for instance: knife, ladder etc.).
Other arrays that represent actions (verbs) that are needed for the solution are already memorized, since the character when given birth to already knows what kind of motions and actions he are able to perform (for instance: walk, climb, cut etc.).
Combining viewable object-arrays and different action-arrays in different ways (genetic algoritm) in the imagination-engine is what actually makes the character arrive at a solution he thinks plausable, and tries to implement in the physical-engine.
So, when a solution is successful, the character memorizes the memory-arrays (problem; objects; actions; result - the problem could be introduced as an array of some kind, and the result could be a number indicating the level of success compared to some absolute parameter, such as...energy gained - energy waste = result) in the correct order.
For instance, if the solution was:
(0) problem = problem-description(crush box);
(1) climb = action-array(ladder);
(2) ladder = object-array(ladder);
(3) cut = action-array(cut);
(4) knife = object-array(knife);
(5) rope = object-array(rope);
(6) success = success-parameter(5 energy units gained);
...then these parameters, descriptions and arrays (in binary mode, or some other way) are memorized in that order.
When the character comes across this problem the next time, he checks the memorybank for a similar description of problem; checks if there are the same object-arrays available in the physical-engine as in the memory; and checks if the success-rate is really worth it (he could be in need of more than 5 energy units). If so, he instantly "recalls" the behavioural-pattern, and implements it. The behavioural-pattern to success is ofcourse the ordered action-arrays (climb, cut).
These memory-arrays could also be used for association (for instance, partial solutions to complex solutions could be used as partial solutions to other problems), but thats a more advanced topic.

Well, I have to go now, so sorry if the text is full with typos and stuff - havent the time to go through it now.