Today, I went to an awesome presentation by Vadim Bulitko about his most recent research. Here’s the presentation, but I’ll summarize what the presentation was about for general use. (I just found that the pdf didn’t come through the pdf export very well, apparently.) This was a presentation at UBC-Okanagan, in Kelowna, BC for reference. Vadim is thinking about taking his sabbatical here at UBC, yay!

Its a rather innovative technique, and delivers great results for only a bit of computer power.

Read more

And now for the promised RPG AI part II, a follow up of part I. The second arena of AI in an rpg, are the npcs, non-player characters.

That has been most of the focus for AI work in most rpg games. Consequently, the state of the art is much more advanced. The reasoning behind this, is to tell a story. To tell a good story. And people standing around repeating the same thing ruins the effect of the story. It takes the player out of the game, which is not a good thing. In fact, its exactly what the designer does not want. The player ends up noticing small things, tiny details, that did not bother them before. This serves to lower their enjoyment of the game. Again, a bad thing.

Good NPC AI is supposed to prevent this from happening, but I think there is something similar to the Uncanny Valley when it comes to NPC dialog. The closer to reality, the harder it is to believe, but if its sufficiently cartoon-like, its somehow easier to immerse yourself. (Of course, the opposite is also true, where the more ridiculously bad the dialog is, the harder it is to be immersed. And so you end up with kind of a bell curve, balanced between really unpredictable and random, to really really bad.)

One particularly effective example I have seen was used in the Golden Sun series. In that game, you could use psynergy, kind of like magic, and one of the moves was Telepathy. Using it next to an NPC, you could hear their thoughts. And by changing the thoughts based on any current events, it gave the npcs a hidden dimension, a personality.

The writing itself in those games was particularly brilliant, which also helps. However, in addition to good dialog writing there have been some interesting efforts to provide personality and unpredictability to npc AIs. The first is the “job system”, where npcs go around do jobs, live their lives, go shopping, have needs and wants, and react accordingly when you disrupt them.

I see often on indie rpg games their breathless promise of a job system like that, where all the npcs have “real lives, real personalities!”. What kind of benefit does this bring to the player? Well, for one, it does provide a kind of personality, as in, “Thats a blacksmith. He’s in the blacksmith building for eight hours, then goes home, eats, and sleeps.” Yep, thats a lot of personality.

Thats what happens often with job systems. You’ve just added a huge dimension of things to make and define for your designers, more than maps, items, doors, main plots, etc etc. And due to the sheer size, it becomes a copy+paste affair, where every blacksmith in the towns previous are identical to this town’s blacksmith. Real personality, oh my!

Then there are the dialog trees. This works a bit better to tell the story, provide some personality, but there are still a few major issues. The first is simple, and horrific. Dialog trees end up almost being like those phone menus. Thats right, imagine those dialog trees as being read our loud, with your options each as numbers.

If you’re like me, you shuddered at this image. Or rather sound recording or…okay, I’ve stretched the analogy too far. But back on point. The second issue is the representation. You get a bit of dialog, then have a bunch of dialog choices presented to you. Again, this commits the big story-teller no-no. You remove the player from the story, by showing them the different choices they could be, and maybe should be making. What if they think their character would do something different?

Also, lots of choices do not make people happy. When I’m faced with six or seven different dialog choices, I suddenly begin wondering, okay, okay, what if I pick the wrong one, and I don’t hear more about the story like I’m supposed to? And I begin worrying. Then if you can start the dialog tree over again, you can try the other choices.

Oh wow, more personality! I can do all the dialog choices to find out all the information! Yeah, thats totally realistic. But the designers did decide to make that choice because of the sheer number of choices they gave the player, and it made the test group happier.

Therefore, to fix dialog trees, I have a few ideas. First is cut down the number of choices you give the player! Fewer choices means more happiness, and less “min-maxing”. It also serves to tighten up your story-telling such that no npc should need more than three choices at any one time. If you find yourself needing more, then you need another npc.

By separating different parts of the plot to different npcs, you can focus more easily on developing them, or give it to someone else. It makes the writing more parallel. So, by making the user happier, and making it easier to make the game faster, this solution works pretty well.

The second idea is to not use real sentences, but a vague concept. After all, rpg stands for role-playing game. Make the player play a role. Make them pick a response that fits their character, and let the player know this! Have responses that fit that vague concept, like if the player expresses boredom, the npc becomes more insistent, maybe even angry based on the context.

And there we have it. More brilliance. Till next time.

My fellow blogger, The Recursion King, has made an interesting post over here, talking about an initial brainstorm for a model of AI.

I say initial, because its nowhere near complete. In fact, what he proposes has been done before.

Its not the data access and storage that makes consciousness, its what happens with that information that we do not yet understand. I’ll use the example of a friend of mine, whom we’ll call Ruby. She’s an artist, a great one in fact. We were discussing how creativity works, and this is what she told me about artists: “We need to be able to picture the way shadows fall, how materials look under light, partial light, two lights. We need to be able to picture how an object looks from different angles, and how to draw that possibly very strange and unique shape. We need, in short, a 3d engine in our minds.”

Our brains are capable of some great, fantastic stuff, intuition being the best example. The true difficulty in AI comes from giving it the capability to expand its perceptions, and make intuitive guesses.

Data mining as it stands today is probably the most advanced method of analyzing disparate data, and finding connections. But even that pales in comparison to what the human mind can deduce if properly trained. Semantic linking is a good start, however, as far as I can see, its only 10% of the solution.

What true AI would be able to do is take small amounts of information, and infer more information from that, based on internal reasoning. Ever had a hunch? That is your subconscious working on information you may not be aware of, and synthesizing it together into a whole for your conscious mind to act upon.

Take for an example, an AI that could solve murders. It takes humans years and years of experience to solve some of the toughest cases, and even then, they can be foiled by proper planning.

An AI that could solve murders would need to be able to decipher body language, understand the difference between lies and reality, infer missing pieces of information, like motives or methods. And even then, a well-executed murder may not ever be solved. However, with intuition, the human would have a guess as to which course to follow, and have an advantage over the AI.

But I’m not being fair, solving murders is a hard problem, despite how easy Sherlock Holmes may make it appear. How about an easier one? Say, Starcraft? Its quite possible in this day and age to make an AI that can beat any human player most of the time, without needing semantically linked memories. In fact, an AI that was not constrained by game developers would always beat human players in FPS games(due to perfect reaction speed, perfect aiming).

My point however, in all of this, is that semantically linked concepts and memories do not an AI make. The Recursion King has some great points, and I look forward to see what more he comes up with. But true AI is in the class of problems that some computer scientists think are Hard, or NP-Complete. Semantics will not solve it for us, unfortunately.

As some of you may know, I am currently working on an rpg.(Who isn’t it seems like).

However, I was thinking about different AI ideas that could be implemented in an RPG. For this post, I will focus only on monster/enemy AI.

Now, the first thing that can make rpg battles/dungeons a bit more interesting is a context outside of battle, where what happens in battle does affect the overall dynamic of the dungeon. Here is one possible idea, similar in aspect to a genetic algorithm. Each enemy has a fear and an intelligence rating, randomly assigned within a predetermined racial standard deviation. Say, slimes are smarter than kobolds for example, on average.

Now what this means is that if you cross an enemy’s fear/intelligence barrier, ie, “They’re really tough, maybe I should run.” So they’d try to escape. If they do escape, what happens? Normally, you’d never see that enemy again, or at the very least, never be able to tell. However, what if the enemies that survive or escape you, communicate with each other? And even are able to formulate plans and groups to take advantage of whatever they learn.

This can be done by giving escaping monsters a memory, a kind of statistical observation of your performance. Then in a background task, have a couple or more of such monsters communicating their knowledge to each other. Now, based on the length of time since the knowledge was obtained, the detail, and what is observed, different information will be valued more than others. By sharing the information between the monster memories, the background task is able to determine your weaknesses. Say it saw your white mage fall to two hits, but your knight took 10. That would be taken into account.

Then, the enemies would lead a charge against you, with slightly modified battle AI’s. As per our example, focus on the white mage!

And since this would be largely time and number of battles based, the longer you are in the dungeon, the tougher the enemies get.

To balance that, we make it so that when you leave the dungeon, the monsters all forget about you.

This behaves similarly to a genetic algorithm, where the fitness test is fighting you. And the sharing of information is similar to swapping genes, but, in this instance, its a method that can deal with unexpected shifts of the problem space. Whereas, in genetic algorithms, the genes have to fit the problem well, and take a while to adapt. By data-mining observed actions, the enemies can adapt faster than with a genetic algorithm.

Another idea I considered was enemy genes, where each enemy you manage to kill does not reproduce, and thus, the more you fight in an area, the tougher the monsters. However, without a very flexible genetic system(IE, one too powerful to adequately simulate) this would only lead to monsters with stronger and stronger genes. Also, the algorithm would have to be tweaked to show results quicker than most GA’s.

Next post: RPG AI Part II