Ok, so it's a horribly general thread title, I know! I am starting an honors project, and I have an idea about what I wish to do with the project. I am hoping for some general feedback on the idea. For instance, general opinions on whether or not it is a useful project would be fantastic, or perhaps some people know where this sort of thing has been done before, etc etc ... I'm one of those people who is always going on about how it would be nice to have games which included better social behavior. You know, quoting Chris Crawford every second sentence, that sort of thing (actually, I hope I'm not THAT extreme, but ... well, you get the picture!). One of the problems (as I understand it, but feel free to correct me) of implementing social reasoning in an AI, is the fact that no one really knows exactly how we think in such situations. We have a pretty damn good intuition about how to behave in these situations, but it doesn't seem to me that anyone really has a good idea about how to transfer that intuition into a workable algorithm. This problem isn't just relevant to theoretical in-the-future games which implement awesome social behavior. An example I give is of the AI in the Hitman games. I haven't played the latest games, but I remember playing the earlier ones and thinking that the AI often wasn't very intuitive when deciding whether or not I was acting suspiciously. The game was designed so that you got a lot of feedback when you were acting suspiciously, so it helped smooth over that problem, but it would still be nice if the AIs response could be intuitively predicted. The trouble is that it isn't obvious what exactly is considered suspicious. Of course, we have a general idea of what we consider suspicious, but most of it just comes down to a gut-feeling. In my honors project I want to investigate the possibility of using machine learning to help an AI (or an AI programmer) appreciate what is involved in that gut-feeling. The basic idea is that you sit a bunch of player's (or a writer, or anyone really, depending on who is supposed to best know how the AI should behave) and give them a whole bunch of scenario's in which the AI needs to make a decision, and record what decision they think the AI should make in that scenario. The data is then classified, and the results are either fed into the AI as a black box, or displayed to an AI programmer to help them understand what is required in the situation. Of course there are a whole bunch of issues: how costly will it be to gather the data? How accurate will the data be? How many dimensions will be needed to get a good approximation of a person's gut-feeling? Is it feasible to gather the required amount of data? Should the results be used as a black-box, or is it better to use them as a tool to increase the AI programmer's understanding of the task? Will it be useful? What do people think? Is it a good idea? Has it been done before? Is it worth investigating? Any feedback would be appreciated. Let me know if I need to clarify or condense this post!

The other part of the problem is how to convert a game situation into a symbolic world representation where all the irrelevant factors have been removed/eliminated so that you can do a pattern match against your knowledge base. An equivalent summarization would be needed to build the patterns. Complexity of representations (patterns) are often complicated by temporal aspects (sequences of event in time instead of a static snapshot).

You will also need testing passes to verify that the knowledge base logic you have created from your 'experts' is actually appropriate for generalized circumstances. Very subtle differences in situational factors can drasticly change what the correct/approriate reactions is. You would then decide whether your accumulated knowlegde could handle enough variations of the game scenarios they are being built for.

Thanks for the feedback, woninoneeye!

I am somewhat embarrassed to admit that I don't fully understand your post ... I think it's because I am coming at this from a maths background, and don't have all the lingo down pat. But that's good, it gives me topics to research!

This is my best guess as to what you are saying:

1. Another part of the problem I am facing is to work out which features of the game world are relevant to my classification task. This may be quite tricky.

2. This will be tricky because there are so many little things that might contribute to the decision, and it will probably not be possible to avoid some level of co-variation between these variables. So I might classify on one variable (A), which might vary roughly in accord with another variable (B) that I don't take account of. If the true underlying classification depends on B I am stuffed.

3. Given the problems above it will be a good idea to test the results of the classification by running more trials after I've classified. However, I need to be careful to make sure that the co-variation I mentioned above doesn't stuff up my tests.

Anyway, let me know if I've misunderstood you. I wouldn't be surprised if I did!

Thanks, Sam

Yes you got the idea.

Your program has to look at the gamestate (from the NPCs point of view) and then classify factors of what it sees (and different object may in a more detailed system might interpret things differently). Once you have that data then you can have the NPC digest the combination of those classifications (if-then logic) to determine a generalization for which a reaction would be proscribed.

MMORPG worlds are complex and have many optional details, so even the classification logic may be complicated: ex -- 'is objectX armed' requires testing all the different game mechanics options ('posesses weapon object', 'wielding weapon object', 'dressed like a soldier', etc...) and that classification might result in not just a true/false value but be a numbers representing a degree/magnitude of 'being armed'. [investigate Fuzzy Logic]


And think not of single variables, but in sets/vectors of variables making up a relational representation. For efficiency you would create/cache a tracking token/object corresponding to each game object observed and add attributes to it for the different classifications that you decide to use. That way you dont alway have to recompute all of it. Some attributes may only need to be calculated once, while others like positional relation constantly update or even are a delta of position (moving away vs moving closer...)

Actions themselves are factors in a situation and a recent history of relevant actions might be kept to be able to spot a trend. (ex- An object that just attacked one of you allies is likely going to attack you .... or seeing something strange happen is a sign to be cautious and that its not time for mundane activities).

Broader situational classifications might be :

Object is getting nearer/further (within a interaction threshold)
Do I have a safe escape route
How strong are ALL the enemies in my proximity
How strong are ALL my allies ...
Do I have cover between me and my enemy (or is such a place close)
What is the reputation (a vector) of the NPC Im taling to
Is the NPC a member of my faction or a faction Im allied to
Has the object made a hostile move already.

Notice that many of these require a summation of multiple objects in the current situation and several are deltas of their gamestate.

Consider that situations change quickly and you may need to reevaluate it to change current actions. For efficiency you want to avoid recalculating things that havent changes. (A metalevel 'classification' might be has the situation changes so much that I need to reevaluate everything...)


Again you dont have to go quite this far in your project and you can simplify it
by having all objects use a standardized classification system (and even put predigested tags/flags on all objects). You could limit your analysis to a simpliefied system of only reacting to the current situation/gamestate (not tracking deltas, maintaining histories) and sharing a world representation between all the objects. Using a simple box distance check to easily filter/identify all the objects that AI object is able to see/interact with.
A limited choice of actions to be taken will simplify how much logic you need (as will the simplified game world).

Your training mechanism sits ontop of all that and there are different ways to generate the knowledge base. Random reactions with extensive situational logging and digesting offline to build a sttaistical model, having the program observe what a real player does and build up a smaller statistical model. Both need the factoring/classification and possibly THAT might be a query system to the operator to identify which factors are relevant to a specific situation (of course all the factors have to be preidentified -- manually created). Combinatorica brute force factorizer probably would only work in the most simple world mechanisms (and still require predefining all simple factors).




------

The decided reaction may not be a simple action primitive, but a task sequence [investigate Finite State Machines] of actions with logic and retry looping, termination criteria, etc...

In more complex behavioral AI the intelligent object may plan out a sequence of tasks/subtasks to achieve goals appropriate to the current situation. This usually requires evaluating which goal(s) are the highest priority and then selecting the best solutions (tasks) to achieve those goals. [investigate Planners]

Of course more complicated response/reactions make it harder to judge what the outcomes are for success/failure (measuring success can be a complex task too...) and which actions really led to the desired results.

You have to spell out what results even are 'good' so that they can be identified. In MMO games there may be many types of results and even combinations from particular actions.

----------------

Look at how much CPU might be needed to do reasonable behavior simulation for just one NPC. Its one of the reasons why you dont see much AI like that in games. Its why Im looking into multi-cores and cluster computers for the simulation project Im working on. Social interaction are a magnitude jump in complexity, so it might be some time before we see them done adaquately in our computer games (and the companies will continue to use choreographed scripts and limited reaction logic tailored to precanned situations).

Thanks, wodinoneeye. There is a lot of stuff to think about in what you have posted, and are being a big help by suggesting things to look at. :)

For the purposes of this project I will definitely try to keep the classification task as simple as possible. Rather then try to classify what an AI's behaviour should be in any general situation, I will try to narrow the scope of the classification task (and so unfortunately, the decision to be made) as much as possible.

As you note, however, it is not a trivial matter to narrow the scope of the classification task, because the decision which the NPC should make might rely on hundred's of little things. In particular, taking the history of the game-world into account will really blow things out unless I am careful. I think you are spot on about the need to condense this information into a much smaller number of "meta-variables".

However, I think there is also a good reason to just pretend that a lot of that complexity doesn't exist.

After all, I am not trying to produce an AI which behaves realistically, or optimally. I am trying to produce an AI which fits well in a given game. The AI won't behave in ways that make sense to the player if it takes to many variables into account, or the classification boundary is too complex, or the variables it takes into account were from a long time ago or a long way away.

Well, that is what I am hoping will help, anyway!

Hi.

I have used machine learning for various tasks, as I come from a speech technology background.
Have you thought about what kind of machine learning algorithm might be suitable for this problem?
The way you described it so far naive bayes comes to mind but you could try something fancy like maximum entropy or support vector machines. There are packages for these algorithms that you could probably rig to work for your project.

Also I was wondering if you could try to use clustering, like decisions trees, to come up with suitable classes?

Anyway, sounds like an interesting project. Keep us posted :)

Thanks for the interest, zynek. :)

Unfortunately, the university I attend only has one official data mining course (geared towards undergrad IT students with a limited maths background). I am trying to make up for it during my honors year by doing complimentary courses with one of the lecturers (basically I get given a topic each week and have to research it online and prepare a presentation).

So far I have only covered 4 classification algorithms: hidden markov models (which don't seem obviously applicable to this problem), support vector machines, multi-layer perceptrons, and decision trees. I also have a small amount of experience using radial basis function splines.

Of the techniques I have covered so far, I would say that SVM's are promising, but being limited to making boolean decisions is a pain in the ass. MLP's seem to require too much data, and DT's are too bad at classifying complex surfaces. But maybe I am being a bit too hasty with these judgments, considering I have not yet actually tried any of them! :)

I haven't been able to spend any time properly looking at the fundamental "issues" which could give me a good handle on how to evaluate each algorithm with respect to one another. If you had any advice on key words to research I would greatly appreciate it.

So I guess what I am trying to say is that I don't yet know how to go about choosing the best classification algorithm!

The only experience I have with unsupervised learning is in the undergrad degree I mentioned earlier, so while I would be very interested in looking at the possibility of using techniques like clustering, I don't really know enough about them at the moment. Another thing to look into!

At the moment I am busy trying to gain more familiarity with the psychological side of things. There are some psychological models which represent emotional reactions as points in a dimensional space. I have a feeling that in situations where many possible emotional reactions are possible, replacing the discrete emotional reactions with these points may let the learning algorithm take advantage of more information (because it then uses information about how the emotions relate to one another).

Anyway, have to go!

Thanks,
Sam