quote: Original post by MikeD

Regarding mis-spelt words, you could use some heuristic to compare an unknown word with all the words in the dictionary and try to guess the meaning. You could cut down the search by analysing the type of word you're expecting (verb, noun etc) and search those word lists first.
So if "Give me a sord" matches a verb phrase best then the computer knows that sord is most likely a verb, searches the list of verbs comparing word length, word ordering and word fragments against the verb dictionary and hopefully come up with the word sword as the most likely answer.

I think this would start to encroach upon CPU usage somewhat. Especially if you are dealing with statements, orders, and questions, as you have different words orders in each this makes it harder to guess what to expect. I think it might not be worth the effort to support misspellings.

quote:
You can then use the fact that the word was mis-spelt to ask the player a question. "Did you say you wanted a sword?".

This starts to get more complex. The NPCs now have to be able to construct meaningful questions and phrase them properly. Understanding text is one thing, but putting it together is another. You would probably have to do one response for pretty much every verb that NPC could understand. And for what? Why waste your players' time asking them if they wanted a sword, if your search function had shown it to be pretty obvious in the first place - so much so, that the NPC suggests it?

Not to mention that the player's instinctive response will be "yes", meaning that you now have to encorporate some sort of 'history', or a conversation context, and to be able to combine that with the current sentence to obtain the meaning... this is not trivial even for advanced NLP applications and is not really practical for a game. It is almost definitely overkill too.

quote:Also, it would be useful to have many different examples of each phrase type, from
"I would like a sword"
to
"Ug want sword"

Every extra phrase type supported makes it more difficult to accurately guess which type of word comes next, as you don't know what phrase type it is before analysing it. Therefore this reduces the chances of an accurate interpretation rather than increasing it.

Edited by - Kylotan on 4/13/00 3:22:55 AM

quote:Original post by GeniX

Maybe even having the language ''rules'' not too strict. Thus if a sentance is entered with slightly incorrect grammar, the parser would try to find the closest matching rule or such.

Problem - although you may think this makes it easier to code or use, you would most likely be mistaken - English is a very redundant language and there are usually several ways of saying something. So just changing 1 word or rearranging 2 words in the grammar can mean totally different things - so you are more likely to misinterpret it. Example "you can get the sword" and "can you get the sword". The first is either a statement or a polite order, the second is more of a question. If you are not strict with what you accept, you will find it much harder to make sense of it.

quote:A recent ''history'' is also a must. It would be nice if not only could the NPC match the pronoun to the last spoken about object (with gender), within a short period of time ofcourse, but also if the NPC could also use pronouns in its responses.
May seem more realistic.

Store a little lookup table of LastItem (for ''it''), LastPerson (for ''he/she'') etc. Then generate the sentence as normal, and go through your table and post-process the output, substituting in the relevant pronoun for whatever noun was there if possible.

quote:
--------------------------------------------------------------------------------
Also, it would be useful to have many different examples of each phrase type, from
"I would like a sword"
to
"Ug want sword"
--------------------------------------------------------------------------------


Every extra phrase type supported makes it more difficult to accurately guess which type of word comes next, as you don''t know what phrase type it is before analysing it. Therefore this reduces the chances of an accurate interpretation rather than increasing it.

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

"I want a sword"
"I would like a sword"
"I want to buy a sword"
"I would like to buy a sword"
"Ug want sword"

If you want reasonable syntactic parsing you''re going to have to deal with the first four anyway. The fifth one is no different just a different construction of verb and noun phrase to compose a sentence. It''s not a whole different grammar just an extension of the current system.

I agree with your other points however.
The overhead for calculating mis-spellings would be overkill but, perhaps, fun to try and certainly not impossible or even too CPU intensive. It would just take time to write.
Your point about language generation, that "The NPCs now have to be able to construct meaningful questions and phrase them properly. " is fair as well. However you could use templates for simple question asking and there would only be certain places where you would ask a generated question. Time consuming again but not impossible or particularly CPU expensive.

Mike

quote:Original post by MikeD

"I want a sword"
"I would like a sword"
"I want to buy a sword"
"I would like to buy a sword"
"Ug want sword"

If you want reasonable syntactic parsing you''re going to have to deal with the first four anyway. The fifth one is no different just a different construction of verb and noun phrase to compose a sentence. It''s not a whole different grammar just an extension of the current system.

Still, the system you describe above is already based on assumptions rather than literal intepretations.
"I want a sword" can be more literally translated as "I desire a sword". It is not the same as "give me a sword" or "sell me a sword". All your above phrases are statements, and parsing statements is fraught with assumptions. That is one reason why many games stick with just orders, starting with the imperative verb, as then you nearly always know exactly what is needed.

As for spelling checking... a exact check for string equality is quick and will almost always return after the first character in both strings are compared, whereas checking strings for almost-equality will most likely have to go through the entirety of every string. This will introduce a substantial relative performance hit - although whether this increases your CPU usage from 10% to 40% or 0.00001% to 0.00004% will depend on just how good your computer and other algorithms are

Not to mention that "ug want sword" could be "I want sword" or "you want sword" (assuming the question mark was omitted) which adds another decision that the parser has to make.

The fact is, and I think we both agree here Kylotan, that it is possible to do all the things we talked about. Whether it is feasible depends on the implementation and programming skills of the individual carrying out the work.
My third year project was in Natural Language Generation and I know a fair bit about AI (pro-programmer), so I''m sure, given enough time, I could pull it off. For a beginner though, it''s rightly correct to take one step at a time. Forget about spelling, forget about generation, take parsing, make it simple and see what you can do.
If you can''t find the info you need here or at www.gameai.com then I suggest going to Amazon and buying the best sounding book there. In the end that''s all you need.

Mike

i predict that this will be an even bigger thing once voice recognition and text-to-speech becomes mainstream in games.

it would definitely be worthwhile to come up with something like this that could be plugged into any game (just add voice and text2speech later), and i have a feeling there will be many third-party "plugins" available to do this type of thing, once it''s been around for a while.

in fact, microsoft will probably implement a similar system to parse commands sent to Windows 2075.
"Please open the CD-ROM folder without crashing."



crazy166
some people think i'm crazy, some people know it

Go to http://www.botspot.com
Look up chatter-bots. There will be one called Alice. It''s open source, so you can download the code, it uses XML to store data, and let me tell ya, it''s capable of doing some amazing stuff.

quote:Original post by MikeD

The fact is, and I think we both agree here Kylotan, that it is possible to do all the things we talked about.

Given enough programmer time, CPU time, and resources, you can achieve anything I guess what I am referring to is that you get diminishing returns - for every slightly more obscure use of the language you attempt to accommodate, you have to do a lot of extra processing not only to accept the new form, but distinguish between the new form and the old, more regular forms. As Felonius said, it''s very hard to do well. For most game projects, it is not unreasonable to expect some ''client-side parsing'' (ie. spell it properly, damn user! ) to save 75% of development time and 50% of computer resources.