Programming AI

[Deimos]

Hey all : D.

I've been really looking into AI recently and well, I thought it'd be neat to take a shot at doing an AI Engine (text parsing and what not). Because PERL is also the bomb at doing text parsing, I'd probably use PERL. There is still a chance I'll use C++ though ^_^, oh wells ;p.

So, let's move on to the AI. When I think of AI, I really start thinking of a text parser. Sure, you can get words out of text and so on, but how can you read these words? Have a million if statements based on context? Sub routines? O-o. In reality, you pretty much have to teach the NPC English (or w/e you're writing it for). This means you pretty much have a dictionary and you have the rules of grammar in there. From here, you have instructions on how to treat nouns, pronouns, verbs, etc, this way the NPC knows how to treat them, and if they are special things like I, me, you, and what not, then you have instructions for the NPC on each of those (the most basic of the basic, yes, there are various forms of you, but you only need one of them).

From here, you could actually get the NPC to deal with various ground objects to (for example, if the player is standing next to a chair), and you can add in coords for things like caves and what not. The real hard part I suppose is programming the initial instructions and storing it uniquly for the AI. The next hard part would be adding in various factors which change how they actually talk and respond to these various events (for example, the culture they've come from, their various personality traits, their IQ, what they already know, and so on).

I just really do find it interesting, and I know it's possible. In fact, I might even make a test AI on an EQEMu server and have people talk to it and what not for fun ^_^. If it works out, I could easily make more (tweaking their IQ and what not to make all of them unique) and populate the entire world with smart NPCs : P.

Oh well, what do you guys think?

Also, try posting some ideas on what instructions might be used and how things might be stored. Currently, for storage I'm considering just using a text file for each NPC (like an object) because it's very easy to store an entire NPC and retrieve it. Storing the stuff in SQL would be a hassle and could actually be much slower :\.

So what are your thoughts and ideas? : D.

Btw, I'd use a current AI thing, but I'm not impressed with any of them at all :\. They're not designed the way I'd do it (they're a bit unnatural too because saying the same thing over and over to them will yield the same response over and over again). They need to simulate some sort of emotion and memory ><.

[bristle]

it seems interesting that AI people (game people) dont do any of this.

i would chose something like python, ironpython, or even c#. the opensim is in c# so that is one reason. i the end it doesnt make a difference in what you use since you interface through an npc channel anyway. it just like your people, but not really your people. there server all ready has enough to do without worrying about npcs.

if you bring it out from the server, then you can make one of a kind or groups. personally, i would like to see groups like a troll manager or something like that.

+++

i would like to set a bot language evolve. then going from A to B pick you butt and going back to A would work about anywhere.

[Kobaz]

Getting this stuff to work well is hard. The fact that the contexts should be limited by being in a game will help though.

Typically these sorts of processors are done as Markov chains. This is why they eventually start to repeat themselves. I remember hearing a conference presentation where a researcher was using genetic algorithms to produce dynamic transition matrices to get more natural responses from a bot. I can't recall the guy's name (it was 17 years ago) but he was relying on the idea that the human response should relate to what the bot said if what the bot said made sense. The correlation between responses adjusted the weights in the matrix.

[bristle]

i have had a interest going way back to before microcomputers. but i never went anywhere with it.

i think a.l.i.c.e may be the way to go. i have seen some bots in second life and i believe that are a.l.i.c.e based. of course they cant see so they are limited. i also ran across http://http://www.personalityforge.com/. once again, it is web base.

anyway, there are already things that people can use (even MUDs).

[Deimos]

as I said, I've seen those and I think they're done wrong :p

oh well, half the fun is designing it too ^^

But, those bots have screwy short term and long term memories ><

They also repeat because they don't know that repeating isn't good in most cases.

Another thing is they can't deal with hypothetical scenarios ^^.

And finally, if you give them a word they don't know but you use it in the context of a sentence, they have no idea what the word is, even with the given context, and they'll just go off topic :\.

Example:
I have 9 yuloaifs and I use them to buy things in a market.
Ok.

Do you know what a yuloaif is?
I was hoping you could tell me.

Deduce it on your own.
I'm afraid I don't have those capabilities (or something like that).

Even I, the lowly programmer, knows how to put deduction and reasoning into a bot ><.

If these bots had deduction/reasoning along with a good short term and long term memory (which makes it so they don't repeat so often), then they'd make good bots ^_^.

Since they don't, I'd rather make my own.

And I thought it'd be fun to have a thread to discuss programming AI to see what ideas people had concerning AI :p.

Also, Alice uses pre-programmed responses. An AI should look through a variety of words to make their own response. This is yet another problem.

[Kobaz]

I used to work in a related field (hence being at conferences etc). Issues I recall are:

Some (human) languages have grammars that are purely positional. In those it is much easier to deduce what is the object and what is the subject. English is not one of those languages. This is why it's so easy to make alice produce gibberish.

There are a lot of people working on "context free grammars", particularly those working on the so-called "semantic web". If you can map human language to a CFG then it's much easier to deduce appropriate responses, and to elicit definitions of new terms (like yuloaifs) in interesting ways.

There is a base vocabulary of around 200 words that should be enough to establish the grammatical basis of an expression.

Human language is inherently fractal, in that each clause and sub-clause can be expanded into a phrase that defines it. The problem is that these in turn can be expanded. For example, "water ski" -> (liquid state of H2O) (horizontal slat that is placed on sole of foot for sliding over low friction surfaces) OR (act of sliding over a low friction surface, that being) (liquid state of H2O) -> ((fluid that is not a gas) (energy dependent phase of matter) (substance: H2O) ) ((plane perpendicular to the direction of gravitational field)( thin section of solid substance in form of rectangular prism) (verb: suppositional) (base surface of) (extremity of lower limb) (preposition: purpose of) (moving tangentially with minimal friction) (qualitative comparison: low) (heat producing force opposing direction of motion)) -> etc.

[Deimos]

However, short term and long term memories of previous conversations with a given person play a factor in the context of word as well. For example, if that person talked about water skiing before and came back the next day and said water ski, the AI would analyze it and find that the highest probable meaning was the activity of water skiing that the individual did the day before.

It sounds like you know a lot more about this than I do. I just started working with it =).

Any pointers you have? And any ideas for playing the various factors into the meanings of various phrases and words, and from there using the probability of the greatest meaning to reply?

[Kobaz]

I worked in a faculty where there was a lot of AI research. My area of expertise is using GACA (genetic algorithm cellular automata) for modelling spatially heterogeneous dynamic systems. My colleagues worked on other problems, including chat-bot interfaces to expert systems. There were often complicated conversations over coffee while things compiled or ran where we would bounce our show-stoppers off each other. So take what I say with a large amount of salt, as I'm recalling things that were discussed in brain-storms.

The short-term/long-term memory issue can be handled by using techniques similar to those used in ARIMA time series analysis to monitor serial correlation. The maths is a lot like that used to try to predict what the stock market is doing. The idea is that all concepts have a weight factor, and that the more recent concepts have higher weight than less recent. If a concept is raised that is highly correlated to an older one then the older facts have their weights boosted by a small amount. Over the course of a conversation the topic being discussed tends to have a sufficient weight to stay at the head of a queue of topics. As in all evolutionary computing (ANN, GA, GACA, GP) getting the rate of change of the weights right is damn hard.

I know one fellow was constructing ontologies of the conversations, and was using that to maintain context. He was using multiply threaded trees, and was maintaining the trees in a DB using memory-only tables (for speed), periodically flushing to disk. He was using a B-Tree based DB as I recall.

[Deimos]

Uh... wow o-o.

And for the conversation, did it take these memories into account for understanding the meaning of everything?

I mean, really, the hard part I am having right now (I'm probably going to be doing something like you said, but much less complex and more basic, just to give the appearance of something that looks complex and superior ;p) is getting the thing to understand the concept of itself and of things that are not itself without defining anything : ). Also, teaching it the very fundamentals of the human language based on those 2 concepts and a third (what is me, what isn't me, and what I need), which I believe are the basic concepts every human is born with.

The AI doesn't have to understand the concepts, it just has to know them and have the capability of later coming to understand them.

I believe that's how any living creature fundamentally grows and comes to understand what's around them.

You can correct me if I'm wrong (I haven't read up on it or anything, it's just my own theory that was brought up with my own thinking on the topic).

[Kobaz]

I mean, really, the hard part I am having right now (I'm probably going to be doing something like you said, but much less complex and more basic, just to give the appearance of something that looks complex and superior ;p) is getting the thing to understand the concept of itself and of things that are not itself without defining anything : ).

Seems that what you're trying to get is some form of artificial consciousness. Personally I'd be a bit less ambitious, but there is a history in this kind of work of talented amateurs making profound leaps because they don't have the training that says we can't do this yet. I know that there was a lot of research in this direction at Los Alamos and Berkeley in the mid to late 90s, sponsored by the US military.

Also, teaching it the very fundamentals of the human language based on those 2 concepts and a third (what is me, what isn't me, and what I need), which I believe are the basic concepts every human is born with.

The "what I need" bit is the core of all evolutionary computing. You define what that is (typically it's either specific kinds of input or responses to output) and use that as your "happiness function". Whatever increases happiness is something that should be more likely to happen again, and what decreases it should be less likely (this is a massively simplified version - look into sigmoid functions, integrating nodes and transition functions for more detail, there's a fair bit of hairy calculus in the literature). In your case, if the human response correlates well with what the bot says, then it should "become more happy" and learn that that was a good response.

The other 2 can be either very simplistic or just too damn hard. At the simplest level any input that comes from outside is the second, whilst input from back propagation (i.e. output is looped back as input - once again a gross simplification ) is ideas from Self.

And for your biggest question:

did it take these memories into account for understanding the meaning of everything?

No. The idea was that the expert systems were very good at asking questions and answering them on specific things. For example, an expert system that can simplify medical diagnosis only needed an ontology that covers the knowledge for that purpose. As diagnoses were confirmed or refuted by real human doctors the expert system gets better at asking the right questions and interpreting the human responses. The memories (which are trees of questions and answers with weights) become more refined over time, but the constraints of limited scope means that many things are not remembered as they do not contribute (positively or negatively) to the fitness (happiness) function.

[Deimos]

Hmm... Well, as I said before, I have pretty much most everything planned out except for that one thing, the concept of it understanding itself and understand what isn't itself without defining anything : p.

The reason I am doing it like this is so that I can make it act natural and what not ; ). If I define itself and define what isn't itself, then its responses for those things will be static.

However, I think a good way to look at this would be to perhaps define the itself part and to leave the not itself part undefined, meaning it has no understanding of the outside world and only knows what it wants and so forth.

With this, various behaviors and what not can be put into it and it can understand the concept of I, one, me, etc, and it can define you as a sentient being such as itself that is not itself, but another being. It can define things and what not as things that are not sentient beings.

= )

[Kobaz]

I think that you have to define something. Babies are born having needs that can only be met from external sources. Human babies are born with set responses to faces, boobs and have predefined responses to touch for example. They don't really know anything, that comes later as they categorise things as pleasure or pain. It's debatable when the concept of Self develops - it takes at least a few weeks if my experience as a parent is anything to go by.

An example would be when a baby discovers its own feet. It certainly looks as if there is no idea that these things are a part of Self, until the baby tries to bend them in a direction they don't go. Or when a toddler discovers its shadow - I've seen one of my sons in a panic about this thing that follows him around. Only over time did Zak learn that this was really an image of him (i.e. an extension or projection of Self).

All infants are born with immense amounts of wiring that defines responses to stimuli. Everything else develops as associations to that initial programming.

[Deimos]

Ok, well for storage and initial setup, it's getting kinda complex and it looks like I might have to end up making my own scripting language o-o.

Ok... here goes..

First, each NPC has their own object that they can refer to. The objects are automatically created and what not if they don't exist and all directories are auto made and so on.

From here, initialization of the object takes place in the NPC's local quest file under the INI sub routine. This is only if the file isn't already there : ).

Also, I have something that's getting setup to make NPCs load specific initialization files based on special labels for them and what not. I also setup something so that they load up a config file O_o. Not sure what to use this for yet or how I'm going to read it and store it (this is where I think I might end up doing a custom scripting language).

It's just getting kinda complex ^_-.

I figure I'm going to store memories and what not in their object file. However, I could store anything I wanted in their, so I could let people completely do all of their stuff in that one object (special flags, and so on, w/e they want).

Actually, now that I think about it, the object file can just be custom information people want that NPC to have. The configuration file can be the stuff the AI Engine runs with. I suppose this configuration file could be the thing that really runs the AI. Eh, but loading up lots of files is going to slow things down...

I could add a new table to the DB for NPCs, but no, that wouldn't be good... I think hashes stored in files (that can be treated as extremely dynamic objects) are the best bet. So then... the configuration file can be used simply to run the AI dll and determine how the NPC acts and what not. The object file can store the NPC's memories and everything under the AI Category (which will be reserved I suppose).

What do you guys think?

Am I being too ambitious? (This storage system thingie is all working thus far ^^).

[bristle]

well i hope i can get some ai gone at Mischief i have some tools and things that may help but at first i will have mobs just walking around. that will be enough.

they have some bots projects at second life that feels like EQ -- at least in part. once again, they are using web-based stuff to do that. i want to have npcs that learn and that mean keeping the sims online at least some of the time. i have some stuff in c# but i need to see if it does anything. and of course a robot walk in c# for an example but that is far from doing anytime.

i have stuff at sim and mischief with mischief more for ai. if anyone want to, he can register at the site and we can figure out what we need. i tried this a few years ago but didnt get anyone involved in it.

the thing is the ai could be for anything just like we do as real people. we had model of MUDs, some of the stuff was great. but now most of it has been forgotten.

[Deimos]

Well, I just thought of something rather interesting. You can't have true AI with current programming languages because these languages can't be written in real time (they have predefined commands and operations).

An AI needs to be able to manipulate anything about itself in real time (this includes its very foundations as well), otherwise it'll be nothing more than a very nice looking robot : p.

So, perhaps before creating this AI I write a language that has the ability to write anything in real time O_o, from commands to operations to w/e.

While commands like C++ look powerful, they still have their flaws... They can't dynamically generate a function (not written anywhere) and add it to itself. Until a programming language that can do that is devised, true AI will be impossible. Sure, we can write programs right now with current technology and languages that act exactly like real people, but they won't have true AI. They'll just be mimics. True AI must have the ability to write its own programming... Just like humans... we have the ability to program any part of ourselves to do something. When we do this, that something acts before we can even think about it. A great example would be me with guitar hero. I've gone through a song while thinking about something else entirely. I don't even pay attention to it, my hands just do it on their own (you can imagine how long I played it for for that to start happening though O_o), but the facts are still clear... any sentient being has the ability to reprogram itself in any way that being sees fit.

With current technology, a programming language like this is impossible though. When dealing with things like this, there is no true or false... It would have to work on an entirely different system.

So I guess my objective of writing a true AI Engine would be impossible right now : (... But I suppose I could write a language that would dynamically add functions and what not to itself in real time and use that for the AI engine. That'd be a start. It still wouldn't be true AI though because its very base would still be based off of binary...

Oh well : ).

Before writing this language, I'm going to do some research to see if someone already wrote a language like this or not : ). It has to be low level (cannot be a scripting language) :\.