Character Generation [technical/theoretical]

[Fractalwave]

That's what you need the (potentially massive) database table for--the alternative is to have every object register with every other, but then each object, as it's notified of another object's change, has to know whether that change will affect it, and if so, how. So again you still need a database table that tracks these cascading effects. I'm not saying the problem isn't solvable or that the pattern you've described isn't the right way to go--just that, even if the basic concept of the pattern is trivial, the implementation still isn't.

That's why you end up limiting the implementation to what is commonly used. The problem with that is you also might end up with something that is so generic it can't handle some of the really great things that we love about the different systems.

(edit--P.S.) Another issue is that some cascading effects can happen when you add or delete an object rather than just changing its data, so objects also have to notify other objects when they are created or destroyed, and the other objects have to know how to deal with that too.

This is something that we have run into in a limited extent within Campaign Suite. You think something is unrelated but it isn't.

You don't have to completely link all the pieces of the database. In other words, you can create an npc that's an elf, then delete the elf race. It doesn't matter because it picks up what it needs when you created it. The problem then becomes what happens later when you need that npc to have something else that is elf-only after a certain level and you inadvertently deleted the item or the race so it can't run a check.

You can end up with a database that is not optimized and repeated information in different tables. Then you have to remember to update all the different tables and it potentially runs slower. So go for a happy medium, perhaps?

 

[Fast Learner]

Constrained Design

Very interesting idea.

This doesn't really strke me as an expert system, though the random generation portion would have elements of such a system.

It seems to me that character generation (or entity generation) is a problem that I'll call Constrained Design (I'm sure there's a real term). A lot of the (non-random generation) issues seem to resemble the kinds of issues you deal with when designing anything within a set of constraints.

Software that, for example, is used to design computer chips works like that. It lets you draw connections and gates and such, but always insisting that you perform your design within a set of constraints. It keeps track of resistance and power levels, the physical constraints of the 3-D layered environment, and only allows you to work within whatever rules you set in the software itself (size of the chip, form factor, voltage, etc.). With such software you can design chips that do just about anything, as long as you meet the constraints programmed into this session. It might have semi-random features like pathfinding and auto-calculation of various best-times, and might even allow you to simulate the chip running within the environment.

I have no idea what kinds of concepts and algorithms have sprung up around this kind of design, but I'm sure they're out there.

Sorry I don't have more to contribute -- while I program, my education and work experience were CIS focused rather than CS, so a lot of these terms are well outside my realm of knowledge.

 

[Fyrie]

Wow, what a great thread. I definately fall under the newbie programmer title as I have only been programming professionally for a little over a year.

I find this topic to be extremely interesting, and I would hope that Jamis would document his program and design process and design diaries so people like me could learn from him.

 

[Archimedes]

Thanks for the lucid exposition. I understand the pattern, and it's basically what I was thinking, but the issue is that at run time, each object has to know as it's created which other objects it needs to register with. That's what you need the (potentially massive) database table for--the alternative is to have every object register with every other, but then each object, as it's notified of another object's change, has to know whether that change will affect it, and if so, how. So again you still need a database table that tracks these cascading effects. I'm not saying the problem isn't solvable or that the pattern you've described isn't the right way to go--just that, even if the basic concept of the pattern is trivial, the implementation still isn't.

My thought is the Rules Definition would contain these dependencies. The program would know what object to construct when it reads a rule and what other objects it would need to keep an eye on. The Abilities would know they need to keep an eye on Race, the Reflex Save would know it needs to keep an eye on Dexterity, and AC would know to keep an eye on the Ring of Protection after equipping said ring initializes that observer releationship. These dependencies can be listed once in the Rules Definition and you can forget about them.

Peter Donis

(edit--P.S.) Another issue is that some cascading effects can happen when you add or delete an object rather than just changing its data, so objects also have to notify other objects when they are created or destroyed, and the other objects have to know how to deal with that too.

Would having your familiar killed be an example of what you’re talking about, or, as Dee was saying, are you talking about removing an element from the game completely?


Sam

 

[Davin]

Jamis,

The more I read and think about this stuff, the more I'm thinking you'll need to proceed in one of three directions, depending on your tolerance for complexity and difficulty. (I'm guessing you'll want to aim for #2, vague though I may be about it.)

1. The first and easiest (logic-wise) method is something of a combination between an expert system and a simple AI. It would be based on an inference engine design and any implementation of code would be unexpectedly simple. Offsetting this would be that the data structure input would be extremely large and complex. You'd have a huge set of fuzzy rules that defined your problem (inputs, constraints, and goals) and the inference engine would simply handle connecting all that stuff together and evaluating results. Different problems would simply get a different (huge) rule set.
2. The second possibility I see (but I don't have enough experience here to see clearly) is a "pure math" sort of solution. I know there are tremendously complex methods out there for actually calculating answers to problems of this complexity (though I don't know what they are offhand). But the basic concept here is to find and implement (even if just in theory) a mechansim that will deal with your problem. The problem itself would be defined by a large set of numeric and pseudo-numerical inputs to the algorithm, the creation of which would itself be a daunting challenge.
3. Finally, the "ultimate" option is so extreme that others here have written it off as impossible (though it's not). However, it's a subject well beyond a Master's (or probably even a Doctoral) thesis. What I'm speaking of is a common-sense AI! Such things are being worked on, with some considerable success, but building such a framework takes man-decades and computer-years of work. Lest you think I jest, visit Cycorp (here) and prepare to be astounded at what they've been doing for the last decade or two. I even see now that their site has changed from a "pure research" orientation to one that is now selling commercial "knowledge" products based on it. (I hope they still have some of their fundamental research concepts available for perusal.) You know... now that they're opening up to outside use of their system, maybe you could make use of their fundamental work by buying into it (probably not cheap!), if you could provide it enough "common sense" knowledge about your particular tasks of interest.
   [/list=1]

 

[Davin]

Whoa!! I've just been browsing through the Cyc site and finding that they've been BUSY. (The site itself is full of information that will take longer than I've got just to skim through.) But the real news I wanted to mention is that they've gone public with OpenCyc, with full systems available on SourceForge and community development and use of nearly their entire system.

Jamis, it looks like your project may have been obsoleted already. Or perhaps it's just been redefined to "implementing a generic constructor technology in OpenCyc."

Good luck!

 

[Davin]

Oh, just to whet your appetite a bit further, here's a short quote from the "Overview" page at their web site:

The Cyc product family is powered by an immense multi-contextual knowledge base and an efficient inference engine. The knowledge base is built upon a core of over 1,000,000 hand-entered assertions (or "rules") designed to capture a large portion of what we normally consider consensus knowledge about the world. For example, Cyc knows that trees are usually outdoors, that once people die they stop buying things, and that glasses of liquid should be carried rightside-up.

This foundation enables Cyc to understand and reason about its application domains:

• Cyc can find the match between a user's query for "pictures of strong, adventurous people" and an image whose caption reads simply "a man climbing a cliff."
• Cyc can notice if an annual salary and an hourly salary are inadvertently being added together in a spreadsheet.
• Cyc can combine information from multiple databases to guess which physicians in practice together had been classmates in medical school.
• When someone searches for "Bolivia" on the Web, Cyc knows not to offer a follow-up question like "Where can I get free Bolivia online?"

So, do you think it has possibilities for use with D&D or more generic conceptual work?

 

[PeterDonis]

My thought is the Rules Definition would contain these dependencies. <snip> These dependencies can be listed once in the Rules Definition and you can forget about them.

I agree, the rules definition would have to contain all the dependencies. The question is, how? Dependency information is often not explicit when rules are defined. Example: the Timeless Body feature of monks and druids in d20/3E. Say you have a monk who is already middle-aged (and hence has suffered aging penalties) when he reaches high enough level to gain this feature. All three of his physical ability scores are affected, but only indirectly, because the feature doesn't change the ability scores themselves, it just changes the way ability scores are changed by aging; the program has to be smart enough to spot this and go back and re-calculate the new aging effects (or non-effects, in this case) without an explicit dependency on the item that was just added. (This example is interesting to me because it's one of the bugs I've observed in E-Tools, and I'm wondering if the above is the reason why it wasn't caught.) Again, nothing here that isn't do-able, but it does add complexity.

Would having your familiar killed be an example of what you’re talking about, or, as Dee was saying, are you talking about removing an element from the game completely?

I was talking about more or less what Dee was talking about--deleting an item from a character (her example was deleting the elf race after having made other changes that are triggered by the character being an elf). The program would have to be able to spot that deleting "elf" should undo everything that was done when "elf" was added, or else the character becomes potentially inconsistent with the rules.

Peter Donis

 

[jmettraux]

I don't think I'm understanding you. Wouldn't it be better for a knowledgeable user to build the Game Definition than the Shakespeare Monkeys? How does this genetic algorithm help?

The 'knowledgeable user' would just then rank definitions that were automatically selected as usable by the batch test program rather than write definitions.
Of course, and before, he would have to write the selection criteria.

I was rather fuzzy when talking about using a genetic algorithm approach (idea introduced by Davin). I think (haven't measured) it would be easier for a 'knowledgeable user' to write a basic constraint test and then separate good performing definitions from sufficient performing definitions.

(I stop writing about this subject, I have to take my morning coffee)

 

[JamisBuck]

Davin: thanks for the information on OpenCyc--it looks like an incredible project! And wonderful, too, that it's (at least partially) open-source. I think it is definately an avenue to consider.

I want to consider to investigate other avenues as well, though, because I hope to compare various approaches and find those that are most appropriate to this problem. The KB approach, though very generic, may not be the best way to model entity generation. I definitely need to read more about it, but because of the non-deterministic nature of entity generation (especially random generation) I have to wonder how well a KB would do in this case. It may be that the KB would be only one component of a successful generator, perhaps performing the validation of generated entities. Like I said, I need to do more reading.

Archimedes and Charles Greathouse have both contacted me and expressed an interest in theoretical discussions of the underlying concepts of complex entity generation. If anyone else would like to be involved in these discussions (active involvement only, please -- no lurking), please e-mail me.

Thanks, everyone for your comments and suggestions!

(on an unrelated side note: we let our 8-month-old son play with a percentile die the other day, and he managed to fit the entire thing in his mouth...it was quite a task getting it out again! so, parents, beware: percentile dice may not be the best toy for your infants...)

- Jamis