You are correct, in that the core problem is trying to come up with a solid model.

Nevertheless, one can make a pretty good AI if you have sufficient resources, however it involves doing extremely complex evaluations of current state vs. goal state systems. Without a good model, that means lots of brute-force evaluations and very ugly state machines. :(

Consider chess. Chess is a fairly simple game, with well known rules, played on a small fixed board. Despite that, we've only recently gotten super-computers powerful enough to beat master-level human opponents. A MUD is far more complicated, and trying to model the goals of dozens (or hundreds!) of different AI personalities, mixed among hundreds (or thousands!) of NPC instances, and dynamically adjusting this to the changes that players themselves introduce with their activities…. that's tricky.

I thought modern chess programs had the capacity to beat master-level human opponents on their hardest setting, regardless as to whether the program is run on a super computer or not?

I was referring to KaVir's experience, not his credentials. But if one has neither, I can see the danger in making evaluations.

I'd appreciate it if we could try and keep a little context, as I think my comment may have been misinterpretted. It was suggested that I couldn't be very good at my job if I didn't care about my industry. My response was: "There is a lot of crossover between software industries, and while specialised knowledge can give you an edge in one or another, it's not at all uncommon for people to move between them. As someone who has worked in the aerospace, telecoms and medical industries over the last 13 years, I'm more interested in projects than industry".

My point wasn't about credentials, it was simply that having spent quite a lot of time working in multiple industries, and having seen the similarities between them, I've come to care more about individual projects than the overall industries - and that I disagree with the suggestion that this makes me bad at my job.

If you look over my other comments, you'll see that I recommend against accepting views based purely on credentials. Elanthis repeatedly refers to commercial video game developers as 'pros', and they are - but not in our field. There are no doubts some useful bits and pieces we can pick up from them, because there is indeed some crossover between their field and ours, but I think it's a very bad idea to blindly follow their methods. There is a huge difference between developing a hobby mud and developing a commercial video game, and I think it's worth understanding those differences before attempting to copy any of their principles.

Wow, so much has been said. So many golden nuggets(or perhaps entire mountains) of insight. I think most of you have made excellent points. Though I dare say the only reason this thread has gotten this large is due to miscommunication/interpretation and repeated explanations.

I planned to write a long response to everyone, addressing the points where people seemed to "not be getting it" or misunderstanding the point but now I'm tired and the conversation evolved greatly in the last page.

Overall I tend to agree with elanthis' points and overall strategies. They, I feel, will work best for me. :biggrin:

Thank you all for invaluable insight that will undoubtedly guide me not in just my favorite hobby but perhaps in other areas aswell.

The problem is the size of the state space, and the difficulty in coming up with a heuristic to test the current state against goal states without traversing all the states in between. The former is an algorithmic problem in that you have a very large number of states to chunk through; the latter is more of a human problem in that it requires a fair bit of smarts to come up with a good heuristic (or a good heuristic generation via machine learning, etc.).


I'm not sure I agree that a MUD is more complicated. I would say that the rules are less clear, but the state space is quite a bit smaller than chess, I would imagine, and it's probably easier to come up with heuristics. I think the difficulty is in modeling from a human perspective, not chunking through the numbers. Indeed, as Dean said, we can in fact construct chess programs that rip through human players that run on commodity hardware. I really don't think that the CPU is a limiting factor when it comes to modeling goal-driven AI in games: rather, it's in figuring out how to model the state space and coming up with decent heuristics.


Then it's a good thing I went on to cover experience in the very next sentence. :rolleyes:


For what it's worth I don't object to your formulation; I was objecting to the rejection of one person's opinion merely because another person had worked in several fields for a while.

You can't often compete with human brains using the same rules.
No need to create complex models, when we can cheat. :-)

With this I agree. I only wish MUDs had the complexity of chess. I've been trying to implement a similar challenge for years, but I think I'm still falling quite short. In chess, at the master level, a single pawn move can make or break the game for you. MUDs are much more forgiving of each choice, and depend on an averaging of all choices made. And each choice can be evaluated within a much smaller framework.

A MUD does have all that complexity, and more. Just don't think of it from the player's greedy "must hit max level with ub3r gear" mindset. Consider, for a moment, the life of the various NPC agents, since those are the beasties we're trying to develop AI to run.

First of all, we have to decide if there is an overall intelligence to the world, or not. In some cases, the world itself may be designed to smite down the players – you can think of that as having one or more gods in charge. If so, those entities have some goals which they manipulate the world itself to try and achieve. If the players start doing things which affect their reaching their goal state, they may start attacking the players (bad weather, poor harvests, nudging orcs out of the mountains and down towards the players, etc).

If not, then you have gestalt intelligences such as nation states. A nation will typically have the goal of becoming larger and more powerful. It may have an aggressive persona, where it goes to war with neighboring states to take their land or resources or it may try to form alliances. Either way, it will manipulate things within its borders to try and achieve those goals. It does that by offering players quests of a particular kind, attacking players who work against it, adjusting supply/demand/pricing, and yes, mobilizing troops. It may be working for, against, or independently of the gods (if they exist).

That kind of thing goes down to villages, shrines, natural wonders (perhaps that cave really DOES want to eat you?), tribes of goblins, etc. A tribe of goblins might have the primary goal of getting metal weapons and armour which they lack the ability to forge themselves. They may set up a camp near a trade road to try and steal such things, or kill travellers and take them. If they grow larger and become well armed, they may move closer to a village to increase their chances of looting. If they are attacked and driven out, they may move further out into the wilds to recover.

Then you have the individual NPCs, each of which should have some role to play. A plain old villager isn't really. Some may be traders, some might be builders, blacksmiths, scholars, adventurers, farmers…. every NPC has some simple goal for getting through the day. If the fishing is poor, fisherman AI would force them to wander further away from town, and the consequences for the players are higher prices for fish, a more difficult time finding a teacher should they wish to learn fishing, and perhaps additional opportunities for questing. If fisherman are wandering further out of town, they have a higher chance of being killed (find out what happened to Bob quest), or of seeing things which get whispered in the taverns (I saw a black horseman on the road, tall as a tree and faster than Ted drinks beer! – quest).

Of course, as Tyche says, we don't NEED to model the AI for all those things. We can cheat. I'm just pointing out that the potential complexity of your world isn't limited in the way chess is. There are no fixed rules that the pieces have to follow, and if you wanted to put the time and CPU horsepower to it, even a single item sale to a vendor in one town might affect the odds of a war happening.

EDIT: I should probably also say that I'm coming at this from the perspective of a MUD which maintains state. Obviously, you lose a LOT of complexity and opportunity if your world has a giant reset button that goes off every few hours.

Quix, I think it's a fair point to make that were you to model a pervasive world AI, you wouldn't do it down to each individual goblin in every far-flung tribe out there. Even if you did, you wouldn't need to model every single agent as having a wondrously complex life full of choices and paths to choose. A major reason you wouldn't do these things is that people probably wouldn't even notice. There was an interesting talk at AAAI '06 (or was it '07… don't remember when I was there) by the guys who did the AI for The Sims; their key point was "if players can't see it, don't do it". You can give the illusion of an agent with complex plans by making fairly local decisions, with a very vague general idea of what the agent is trying to do.

To be polite, bullshit!

Give us an address. I'd really like to see this.

Should be doable to implement double dragon like combat. If you jump, followed by a kick, you won't hit someone who is ducking. If you duck and kick you perform a trip movement, which misses if someone jumps. Attacks will need to be announced in advance so people can respond, blocking moves need to work 100% of the time, etc. The only problem is adding enough complexity that combat doesn't become stale, and not to add too much complexity, which would make scripting combat or using loopholes a necessity.

Have you seen what KaVir's done with GWII?

You wouldn't *NOW*, because the resources aren't available to make it worth doing. As you say, the players wouldn't notice it, and because it's not trivial, it's not worth doing. That's not to say it's never worth doing…. modeling down to the individual actor level allows you to have emergent behavior which you wouldn't expect when looking down from 10,000 feet.

A good example is the Lord of the Rings movie. The actors in the huge battle scenes were all individual AIs, which were given the simple goal of attacking the enemy. In the initial rendering, many of the combatants at the back edge of the battle appeared to be fleeing, because it was a shorter path for them to run around the world and come at the opposition from behind. Faulty AI, to be sure… but from the perspective of the viewer, emergent behavior.

The key for that kind of stuff to work though, is that NPC's would need to not only be persistent, but they'd need to have memories as well. Let's say one codes a mob and gives it an adventurer AI. This mob acts like a player, wandering the world and doing quests, killing mobs, upgrading gear. At one point, it sees a player being attacked by one too many orcs. It weighs the odds and the AI decides to help the player by attacking the orcs. It *could* have joined the orcs and helped finish the player. In any case, they win. Now, the AI has to remember that it fought beside this player, and is now slightly friendly towards them, their party, their guild, perhaps several factions as well.

One thing to note about that… if the AIs are goal driven, rather than running fixed scripts, they can evolve their own purpose in the game. A low level NPC might be competition with, or allies of, the players. As they gain levels, they may start acting as mentors to lower level players (by offering them quests which further their goals), and they may also act as hirelings to players (who are doing other quests that further their goals). They could also do the same with other NPC's, but one presumes you'd want to code a "home" desire into them, so that only unusual events would get them to leave their current home area. Otherwise, all the mobs would band up and travel around in a giant army, leaving the towns desolate and empty. :)



*chuckle* I didn't say A particular MUD. I don't know of one yet. I do see the problem space being a whole lot bigger than what's possible in chess though, because you CAN add rules, pieces, playing field, AND goals as the game evolves. It's not *MY* fault that nobody has moved beyond the bash-stuff-until-I-hit-max-level mechanics.

Talking of NPC AI reminds me of this thread at mudconnect: http://www.mudconnect.com/discuss/discus...

See my post, no. 46 in the thread, and thereafter.

From what I know GWII uses dice rolls to determine hits?

It does, but a jumping kick will never hit a prone target, nor will a (duck kick) sweep ever hit someone who's jumping. Ducking is sufficient to automatically avoid a backflip kick, but against a somersaulting back-kick it'll just result in you getting kicked in the back of the head instead of in the back.

Part of my point was precisely that if people don't notice it, you shouldn't be worrying about it, and you can implement behavior that looks emergent but actually isn't.


This doesn't strike me as too terribly expensive, considering that individual NPCs already store a fair bit of data, as do players. Presumably, there aren't huge numbers of such smart NPCs running around the world, either.


Being able to add stuff doesn't make something inherently more complex. Complexity in AI problems comes from two main things:
1- size of the search space (affected by branching factor and depth of solutions)
2- heuristic availability

If you have incredible heuristics, then even massive search spaces can be chopped to very manageable sizes. If you have small enough search spaces, you might not even need heuristics since you can just brute-force your way through. If your search space is large but has patterns, you can chop things up into smaller problems where you can construct heuristics for simpler problems.

For example, if your mob is in the middle of a fight, you certainly don't need to be planning out where to buy a loaf of bread later that day for dinner.



Anyhow, a lot of what you're talking about can be handled on the aggregate level. You probably don't need to model every little interaction in a village in order to model what the village's general sentiment is.

Representation is everything. There's the same ol' Missionaries and Cannibals problem that has a very interesting property. If you phrase each missionary and cannibal as an individual unit, and decide in each instance if they should get in the boat or not, the problem is far more complicated than if you think in aggregate terms (i.e., manipulating a total count, instead of individuals). The exact same problem can become orders of magnitude cheaper to solve simply by changing representation.

What does this mean in the current topic? Well, the problem with M&C is that it's hard for AI agents to make this kind of structural observation (it doesn't matter if you move missionary 1 or missionary 2). But in our case, here we are designing the entire model for the AI, and it just has to crunch the numbers. The true intelligence in this event lies with the human in coming up with an appropriate model to make the problem manageable.

That depends. In current games, no… in a game which is trying to get away from the mindless hack-and-slash we have today? Maybe most NPC's would be at least that smart. It boils down to what kind of gameplay you want, and how much work you want to do. I suspect many players would rather fight a smaller number of clever opponants, rather than wading through thousands of stupid mobs that throw themselves on your swords.



True, however if your mob loses the fight, he won't be buying a loaf of bread later that day. If he doesn't, maybe nobody will and the baker will have a surplus. He might choose to throw the stale bread out, making some vagrant live through the night, or he might choose to sell it at half-price tomorrow. He might just take it home, or grind it into crumbs, eating the loss and raising his prices tomorrow.

Of course, you don't need to make a baker AI that decides what to do with leftover goods. It can all just be numbers in a quick formula which adjusts the price of bread each day. But, the emergent behavior you might see will never happen if that's how you do things. The question is, do you care?

You had suggested that we weren't CPU bound. If you intend to model everything on the 10,000 foot overview level, then I agree. If you want the kind of unexpected side-effects that come about from having individual AI's doing their thing, then I would say we're still way too underpowered to do anything realistic.

I'm not saying you can't make a good AI, at present. However, you will have to cheat. :)

Well, in a text-based roleplaying game, cheating is what it's all about isn't? It's all pretty much smoke and mirrors, literary illusions, if you will.

On the CPU thing, I just profiled my game last night, and most of it's time is spent running through three 'wander' updates. Wandering is hardly 'goal driven', just random movement to provide the illusion that the mobs are alive. ("Is he alive?" "Don't think so… he's not moving.") Obviously more 'AI' will cost more CPU, though running through a list of selected mobs is much more efficient than running the char list as the wander updates do. On the other hand, I'm hovering around .01% CPU use right now, and since my current account allows .1%, I could increase the realistic behavior of the mobs considerably if I wished to do so without any actual cost.


In other news, back to the OP, I think the best way to keep on track and stay motivated is with a ToDo list. Seed it with ideas that you want to implement when you start, then add ideas as you go along. Occasionally edit the list, tossing out stuff that's not so good after all, and bringing the most doable and important things to the top. When you go to work on your project, pull out the list and knock off the first appealing item. Drag it to the very top of the list and mark it done. In this way, your ToDo list also becomes your Changes document, and your position on it shows your progress.

The beauty of this is the simplicity. It may crude, but it's effective, and easy enough it doesn't get in the way. "I should do something…" is often followed by "What should I do?", and that question can suck up the time you might have been working on your project. With a ToDo list, you just show up for work and do what you're told. ;)