PlaneShift
Gameplay => Wish list => Topic started by: JorgeAldoJR on September 11, 2006, 08:37:02 am
-
Natural languages are heavy to interpret and are full of special cases, etc...
What about taking the other way around and make a simpler, english based, regular language for NPC interaction ?
We can even use this language for people to people interaction. Some kind of Esperanto for Planeshift, based on english words...
I can write a C++ class for understanding Esperanto grammar or any other regular language, this solves the "special cases and constructions" problem, and the construction can be understood by the computer using a neural network approach or any pattern matching algoritmic approach.
Process :
STEP 1 : Transform the input string into a stream of tokens
STEP 2 : Expand macros (Like OMG ! translated to "By the gods !")
STEP 3 : Apply spell checking
STEP 4 : Translate each token into a index interger using a words database (The same database can be used to correct spelling), if a new token is found, add it to the database. The token list is translated into a array of unsigned intergers, and a start of phrase and end of phrase is applied to the start and end of the array. Special chars like "?" are to be represented in this database as well.
STEP 5 : Take each word pair (including the phrase start/end markers) and, using their indexes as a 2D array entry, build a word to word transition index. (You will understand this if you search the wikipedia for Markov Chains). This is the "phrase" database. See table 1 for an example. If a new transition is found (When a new word is found), add a new transition to the database. (The tabular format is only a way to represent this database here. It should be easier to use a sparse matrix, ommiting the non-ocurrent entries).
STEP 6 : Take each transition index and apply into a pattern matching system.
STEP 7 : If a pattern sufficiently matches, gives the appropriate answer.
STEP 8 : Else, give a "i am not understanding" answer.
The database should be locked (Not allowed to write to it) when the language system reaches some consistent state.
Each NPC should have their own pattern matching system, and the NPC should rule the context of the conversation (In order to solve the context problems that are IMPOSSIBLE for a computer to solve in the near future... [I can guarantee you, the processing power involved into context-free grammars are out of current technology scope, adding to it the number of concurrent queries for each npc X player interaction only worses this]), you can even force the context by having the NPC's to start the conversation...
Example Table 1
| State X State | Start-Phrase | I | AM | NICE | End-Phrase |
| Start-Phrase | Transition 0 | Transition 1 | Transition 2 | Transition 3 | Transition 4 |
| I | Transition 5 | Transition 6 | Transition 7 | Transition 8 | Transition 9 |
| AM | Transition 10 | Transition 11 | Transition 12 | Transition 13 | Transition 14 |
| NICE | Transition 15 | Transition 16 | Transition 17 | Transition 18 | Transition 19 |
| End-Phrase | Transition 20 | Transition 21 | Transition 22 | Transition 23 | Transition 24 |
*Note that some of these transitions are impossible to happen (Like a start-phrase to start-phrase marker) and that some transitions are not meaningfull (Like start-phrase to end-phrase marker) so can be discarded...
**Note too that this table is one of the elements of the grammar, saying wich word to word transitions are allowed in our "Planeshift esperanto-like grammar"
***Note that the larger the grammar, the larger the database, by the relation N^2 wich is not good but is better than most statistical approaches.
The rest of the grammar is implemmented into each NPC pattern matching system...
Theres a free, C/C++ Neural network library available as GPL (http://leenissen.dk/fann/) wich can be used to build each NPC pattern matching system. Each NPC will have to be trainned into pattern matching (generating a .dat file with the neural network desired state) but will be very good at this after being trainned... Each word to word transition pattern should trigger a NPC state for this player (or, if two players try to address the same NPC, we can have it say "Sorry, wait until i end with <1st player name here> conversation.", this is more natural).
I think with this system, and a restricted language (not a really natural language one) we can have a very good NPC system :)
*I dont really know current game development state, so i dont know if this is already being addressed or if this really suits the developers taste, etc. I dont want to offend anyone here either...
*edit*
Example :
Phrase "I am nice ?"
/* Affirmative and interrogative forms are the same, only "?" denotes interrogation. The only language instances allowed are affirmative and interrogative. Affirmatives could be taken as interrogatives if theres no current context set by the NPC itself (A context is a array of pattern matching instances), in this case the noun "I" selects the context, "Player talking about himself" wich can be the 1st context of the grammar, the second context can be "Player talking about the NPC itself", third "Player talking about other player", Forth "Player talking about other NPC", Fifty "Player talking about city", etc */
Word database :
1 "<<" /* "<<" here denotes start marker */
2 ">>" /* ">>" here denotes end marker */
3 "I" /* 1st real word in the database */
4 "AM"
5 "NICE"
Transition database :
1, 1 to 2 /* can be omitted as it means nothing */
2, 1 to 3 /* a real phrase starting... */
3, 1 to 4 /* ommited as this is a regular grammar */
4, 1 to 5 /* can be meaningfull only if the next transition is 5 to 2 */
Transition of 2 to anything cant really happen, so this whole row is not present in the transition table
All transitions into 1 are ommited as they dont make sense.
Transitions to and from the same word are not meaningfull, so are ommited too.
5, 3 to 2 /* can be omitted or if happens just after transition 2 be a trigger for the NPC doing some jokes about the player, etc */
6, 3 to 4 /* player talking about himself... */
7, 3 to 5 /* can represent something in the grand scheme of the grammar */
8, 4 to 2 /* can be ommited */
9, 4 to 3 /* can be ommited */
10, 4 to 5 /* good construction */
11, 5 to 2 /* good construction */
12, 5 to 3 /* can represent something */
13, 5 to 4 /* inverse order should not be allowed in order to avoid special cases in the grammar, but... */
So we have 5 words and 13 phrase fragments, nowwe do the black magic :
"I am nice" ->tokenize-> 1 3 4 5 2 ->transitions-> 2 6 10 11 ->using the current context "Player talking about himself" (an array of pattern matchers)-> triggers the answer for "iamnice" catchphrase...
Well, this is just a SMALL example and is not really shocking to see, but with really big databases we can see some improvement of NPC communication skills...
By the way, if applied in the reverse order, we can have the NPC's talking FROM the database...
*edit*
I actually have working code for Markov Chains (i used to make a ircbot talk and learn from the users in the channel), but is written in ObjectPascal and then will take some time to translate to C++ ... The current code uses an array to hold everything, but it should be better if you use some kind of database (Like postgre or mysql) and give to the database all the management/search work... Even the neural network .dat files (The contexts) can be stored as BLOB's... and we can have a context table too, holding indexes to .dat patterns and corresponding event triggers in the game's internal interpreted language that coordinates everything...
Please avoid posting two or more successive posts before others have replied. Just "Modify" your last post to add new information. Thanks! --Karyuu
-
Yay - seems like you really have some skills in programming!
Why don't you apply to the dev team?
Greetings!
-
:thumbup:
I really would like to see similar system in PS. If You can dedicate Your free time for implementing this, and You don't mind releasing the code as open source, go for it! You can start right now after setting up Your own PS server, the source code of the game is available.
I'm sure, that there will be voices saying: "Custom grammar is bad, it is unrealistic, it is too hard to learn for newbies, etc...", don't be discouraged by this. If Your solution can recognise simple, proper english sentences, it is good enough. In the end it depends mainly on training of neural network (I think).
Aha! There would be an opprotunity to create new position in development team: NPC trainer ;).
-
Not trying to rip on the devs or anything, but any simple short sentance is better than the curent setup. "about [keyword]" isn't even a sentance.
-
I am thinking about starting a C++ library/engine for this, with mysql and fann support.
I will call this library/engine "Equilibriuum Language Recognition and Generation Engine" (ELRGE), as the markov chain based text generators tends to work best when it reaches a certaim equilibrium point, after this it slowly grinds towards pure crazyness (so the need to "lock" the database after it reaches a consistent state)...
AFTER i get this library working good i will try to integrate it with psserver code...
I think other games would need this kind of library so other non-ps related developers can join to improve the library...
About the Neural Network, im not sure if this thing really needs neural networks, as its possible to reconize the transition sentences using simpler pattern matching schemes, like a regex...
I was brainwashing about this for a week... Its even possible to have the bot talk "non-sense" if the player doesnt hits a catchphrase... (Working this thing in the reverse it will generate phrases FROM the phrase fragments...)
*edit*
I was thinking about this stuff for a while and them... WTF !
I found no need for regex or neural network stuff...
The markov chain is ITSELF the pattern matching system...
Taking the "<<" ">>" aproach a step further, we can have multiple starting and ending markers for multiple triggers... Bot responses are only "states" in the sense that they generate explicit textual responses, but we can have implicit, factual responses...
If we tag starting contexts and ending contexts as <<N and >>N special words, in the 1st order markov chain, chaning the markov chain into a really probabilistic one, we can reconize and generate speech with some success... In this setup each NPC will need to be trainned about their contexts and phrase setups... Geez, this will work REALLY GOOD, without none black magic...
I will post my GPLed Markov Chain text generation bot here (only the two classes dealing with markov things) wich are currently in ObjectPascal language, for the sake of explanation...
*edit*
How to tell developers that i found a simple and nice solution for the NPC chat without resorting to special grammars and etc, only using a Hidden Markov Model (HMM) ?
It was so obvious and simple that i ended up messing up everything...
But now i figured out everything and is damn simple... WTF...
I am willing to devote my spare time to develop this, but looking at current PSSERVER codebase it looks more difficult to integrate this thing into the server than to actually write it in C or C++ ...
Please avoid posting two or more successive posts before others have replied. Just "Modify" your last post to add new information. Thanks! --Karyuu
-
It doesn't need to happen overnight, don't worry about it! Simply devote some of your time to it and ask help from the devs. Might wish to talk to them on IRC, try #planeshift-build.
-
Code for MarkovDict.pas file :
------------------------------------------------------------------------------------------
// Copyright (C) 2006 Jorge Aldo G. de F. Junior.
// This file received some modifications from FPCBot Authors
// This file is part of Pascal Markov Text Generation Library (Called PMFGL).
// PMFGL is free software; you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation; either version 2 of the License, or
// (at your option) any later version.
// PMFGL is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
// You should have received a copy of the GNU General Public License
// along with PMFGL; if not, write to the Free Software
// Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
Unit MarkovDict;
{$mode objfpc}{$h+}
Interface
Uses
Classes, SysUtils;
Const
ccStartToken = '<<';
ccEndToken = '>>';
ccImpulse = 10;
Type
{ TMarkovDict }
TMarkovDict = Class
Private
fName : String;
fWords : TStringList;
function GetCount: Integer;
function GetMarkovCount: Integer;
function GetTransitions(index: integer): TStringList;
Public
Constructor Create(Arq : String);
Destructor Destroy; Override;
Procedure Load;
Procedure Flush;
Function InsertWord(St : AnsiString): Integer;
Function FindWord(St : AnsiString): Integer;
Procedure ImpulsePair(S1, S2 : AnsiString);
Property Words : TStringList Read fWords Write fWords;
Property Transitions[Index : Integer]: TStringList Read GetTransitions;
Property Count : Integer Read GetCount;
Property MarkovCount : Integer Read GetMarkovCount;
End;
Implementation
Function TMarkovDict.GetCount: Integer;
Begin
Result := fWords.Count;
End;
Function TMarkovDict.GetMarkovCount: Integer;
Var
Ctrl : Integer;
TransitionList : TStringList;
Begin
Result := 0;
For Ctrl := 0 To fWords.Count-1 Do
Begin
TransitionList := Transitions[Ctrl];
If Assigned(TransitionList) Then
Result := Result + TransitionList.Count;
End;
End;
Function TMarkovDict.GetTransitions(Index: Integer): TStringList;
Begin
Result := TStringList(fWords.Objects[Index]);
End;
Constructor TMarkovDict.Create(Arq : String);
Begin
Inherited Create;
fName := Arq;
fWords := TStringList.Create;
fWords.Sorted := true;
fWords.Duplicates := dupIgnore;
End;
Destructor TMarkovDict.Destroy;
Var
Ctrl : Integer;
Begin
fName := '';
For Ctrl := 0 To fWords.Count -1 Do
If Assigned(Transitions[Ctrl]) Then
Transitions[Ctrl].Free;
fWords.Free;
Inherited Destroy;
End;
// Loads the list from a file
Procedure TMarkovDict.Load;
Var
Handler : TextFile;
Word : String;
Line : String;
NewTransitions : TStringList;
HitCount : PtrInt;
Begin
If Not(FileExists(fName)) Then
Exit;
AssignFile(Handler, fName);
Reset(Handler);
While Not(Eof(Handler)) Do
Begin
ReadLn(Handler, Word);
ReadLn(Handler, Line);
If Length(Line) > 0 Then
Begin
NewTransitions := TStringList.Create;
Repeat
Readln(Handler, HitCount);
NewTransitions.AddObject(Line, TObject(HitCount));
ReadLn(Handler, line);
Until Length(Line) = 0;
End
Else
NewTransitions := Nil;
FWords.AddObject(Word, NewTransitions);
End;
CloseFile(Handler);
End;
// Saves the list to a file
Procedure TMarkovDict.Flush;
Var
W1,
W2 : Integer;
MarkovText : TextFile;
Transition : TStringList;
Begin
Assign(MarkovText, fName);
ReWrite(MarkovText);
For W1 := 0 to fWords.Count-1 Do
Begin
WriteLn(MarkovText, fWords[W1]);
Transition:=Transitions[W1];
If Assigned(Transition) Then
Begin
For W2 := 0 to Transition.Count -1 Do
Begin
WriteLn(MarkovText, Transition[W2]);
WriteLn(MarkovText, PtrInt(Transition.Objects[W2]));
End;
End;
WriteLn(MarkovText);
End;
CloseFile(MarkovText);
End;
// adds a new word to the list returning his value or
// returns the value of a word if it is already in the list
Function TMarkovDict.InsertWord(St : AnsiString): Integer;
Begin
Result := FWords.Add(St);
End;
// Finds a word in the list, returning -1 if the word
// isn't already there
Function TMarkovDict.FindWord(St : AnsiString): Integer;
Begin
FindWord := fWords.IndexOf(St);
End;
Procedure TMarkovDict.ImpulsePair(S1, S2: AnsiString);
Var
W1,
W2 : Integer;
TransitionList : TStringList;
Begin
W1 := FWords.IndexOf(S1);
If W1 < 0 Then
W1 := FWords.Add(S1);
TransitionList := Transitions[W1];
If Not(Assigned(TransitionList)) Then
Begin
TransitionList := TStringList.Create;
FWords.Objects[W1] := TransitionList;
End;
W2 := TransitionList.IndexOf(S2);
If W2 < 0 Then
W2 := TransitionList.Add(S2);
TransitionList.Objects[w2] := TObject(ptrint(TransitionList.Objects[w2]) + ccImpulse);
End;
End.
------------------------------------------------------------------------------------------
Code for Markov.pas file :
------------------------------------------------------------------------------------------
// Copyright (C) 2006 Jorge Aldo G. de F. Junior.
// This file received some modifications from FPCBot Authors
// This file is part of Pascal Markov Text Generation Library (Called PMFGL).
// PMFGL is free software; you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation; either version 2 of the License, or
// (at your option) any later version.
// PMFGL is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
// You should have received a copy of the GNU General Public License
// along with PMFGL; if not, write to the Free Software
// Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
Unit Markov;
{$mode objfpc}{$h+}
Interface
Uses MarkovDict, Classes, SysUtils;
Type
// Holds the last words used by the engine in order to
// avoid recursions
TLastWordsUsed = Class
Private
fBuffer : Array Of String;
fPos : Integer;
Public
Constructor Create(Size : Cardinal);
Destructor Destroy; Override;
Procedure WordSaid(W : String);
Function WordUsed(W : String): Integer;
Procedure Show;
End;
// A generic markov text generator
{ TMarkov }
TMarkov = Class
Private
fErrorMargin : Byte; // Deviation
fThreshold : Byte; // Limiar level for a construction to be considered "right"
fDict : TMarkovDict;
fUsed : TLastWordsUsed;
fUserUsed : TLastWordsUsed;
Function StartCode : Integer;
Function EndCode : Integer;
// Number of words in the dictionary
Function WordsCount : Integer;
// Number of entries in the markov chain
Function MarkovCount : Integer;
// A random word to follow K, with at least E% usage
Function RandomWord(const S1: string; E : Integer): string;
Public
// D = Markov data file
// M = Deviation
// T = Threshold
Constructor Create(D : String; M, T : Byte);
Destructor Destroy; Override;
// Use talkto when you need to write a new phrase into the database
// without generating a response (I.E. Write-Only)
Procedure TalkTo(W : TStringList);
// Use talkfrom when you want to generate a new phrase from the
// current database
Function TalkFrom: AnsiString;
// Use talk to write to and generate a response at the same time
Function Talk(W : TStringList): AnsiString;
// Change a word in the dictionary, correcting a mispelling ?
// S1 is the current word, S2 is the word to wich it should be changed
Procedure Correct(S1, S2 : AnsiString);
// Error margin is the max deviation from a central threshold level
Property ErrorMargin : Byte Read fErrorMargin Write fErrorMargin;
// Threshold is the level where a construction is marked as good
// language one
Property Threshold : Byte Read fThreshold Write fThreshold;
// The ammount of words in the dictionary
Property DictionaryWords : Integer Read WordsCount;
// The ammount of words in the markov chain
Property EntriesMarkov : Integer Read MarkovCount;
End;
Implementation
// Generates (guaranteed) a random number wich value in the [X, Y] Range
Function RandomFromTo(X, Y : Integer): Integer;
Var
Tmp : Integer;
Begin
Repeat
Tmp := X + Random(Y - X);
Until ((Tmp >= X) and (Tmp <= Y));
RandomFromTo := Tmp;
End;
// TMarkov
Constructor TMarkov.Create(D : String; M, T : Byte);
Begin
Inherited Create;
fDict := TMarkovDict.Create(D);
fDict.Load;
// fTable := TMarkovTable.Create(P);
// fTable.Load;
fUsed := TLastWordsUsed.Create(128);
fUserUsed := TLastWordsUsed.Create(64);
fErrorMargin := M;
fThreshold := T;
// make sure the startToken and EndToken are part of it.
fDict.InsertWord(ccStartToken);
fDict.InsertWord(ccEndToken);
WriteLn('Phrase start code : ', StartCode);
WriteLn('Phrase end code : ', EndCode);
End;
Destructor TMarkov.Destroy;
Begin
fDict.Flush;
fDict.Free;
fUsed.Free;
fUserUsed.Free;
Inherited Destroy;
End;
Procedure TMarkov.TalkTo(W : TStringList);
Var
Ctrl : Integer;
Begin
If Assigned(W) And (W.Count > 0) Then
Begin
// Puts every word in the dictionary if not already
// and mark as context input
For Ctrl := 0 To W.Count - 1 Do
Begin
fDict.InsertWord(W[Ctrl]);
fUserUsed.WordSaid(W[Ctrl]);
End;
// Reinforce start word behaviour
fDict.ImpulsePair(ccStartToken, W[0]);
If W.Count > 1 Then
// Insert/reinforce word pairs in the transition table
For Ctrl := 0 To W.Count - 2 Do
fDict.ImpulsePair(W[Ctrl], W[Ctrl + 1]);
// Reinforce end word behaviour
fDict.ImpulsePair(W[W.Count - 1], ccEndToken);
End;
End;
function TMarkov.StartCode: Integer;
begin
Result := fDict.FindWord(ccStartToken);
end;
function TMarkov.EndCode: Integer;
begin
Result := fDict.FindWord(ccEndToken);
end;
// Number of words in the dictionary
Function TMarkov.WordsCount : Integer;
Begin
WordsCount := fDict.Count;
End;
// Number of entries in the markov chain
Function TMarkov.MarkovCount : Integer;
Begin
MarkovCount := fDict.MarkovCount;
End;
Function TMarkov.RandomWord(Const S1 : String; E : Integer): string;
Var
Ctrl : Integer;
Highest : Integer;
Partial : Array Of Integer;
Possible : Array Of Boolean;
Coeff : Double;
Possibles : Integer;
Chosen : Int64;
Transitions : TStringList;
Begin
Result := ccEndToken;
Transitions := FDict.Transitions[FDict.FindWord(S1)];
If (Transitions = Nil) Or (Transitions.Count = 0) Then
Exit;
Highest := 0;
Possibles := 0;
SetLength(Partial, Transitions.Count);
SetLength(Possible, Transitions.Count);
Write(' Transition matrix with ', Transitions.Count ,' coefficients : ');
// Generates the transition matrix for K
// from K to each possible word
For Ctrl := 0 to Transitions.Count - 1 Do
Begin
// Coefficient : four words in the context cancels out a word being too much used
Coeff := (fUserUsed.WordUsed(Transitions[Ctrl]) + 1) / ((fUsed.WordUsed(Transitions[Ctrl]) + 1) * 4);
Partial[Ctrl] := Round(Ptrint(Transitions.Objects[Ctrl]) * Coeff * 100);
If Ctrl = EndCode Then
Partial[Ctrl] := Round(Partial[Ctrl] * 0.75);
If Partial[Ctrl] > Highest Then
Highest := Partial[Ctrl];
End;
WriteLn(Highest, ' highest.');
// Transforms from "hits" into percentual (%) values
// relative to the highest scoring word in the markov transition table
// If a value is higher than the threshold (E) then this is a "possible"
// word to follow K in a normal text
Write(' Apply thresholds : ');
For Ctrl := 0 to Transitions.Count - 1 Do
Begin
If Partial[Ctrl] > 0 Then
Possible[Ctrl] := Round((Partial[Ctrl]) / (Highest / 100)) > E
Else
Possible[Ctrl] := False;
If Possible[Ctrl] Then
Inc(Possibles);
End;
WriteLn(Possibles, ' words can follow.');
If Possibles = 0 Then
Exit;
// Choose a random from the possible words
Chosen := Random(Possibles); // number to skip
Write(' Select keyword : ');
Ctrl := 0;
While (Chosen >= Ord(Possible[Ctrl])) Do
Begin
If Possible[Ctrl] Then
Dec(Chosen);
Inc(Ctrl);
end;
Result := Transitions[Ctrl];
WriteLn(ctrl, ' ', Result, ' selected.');
End;
Function TMarkov.TalkFrom: AnsiString;
Var
Temp : AnsiString;
Key : Integer;
AWord : AnsiString;
Begin
// Start a fresh phrase
WriteLn(' TalkFrom');
WriteLn(' {');
AWord := ccStartToken;
Temp := '';
Repeat
AWord := RandomWord(AWord, RandomFromTo(fThreshold - fErrorMargin, fThreshold + fErrorMargin));
If AWord <> ccEndToken Then
Begin
// Append the next word in the phrase
Temp := Temp + AWord + ' ';
fUsed.WordSaid(AWord);
End;
// The next word will be the most probable from the current one
Until AWord = ccEndToken;
WriteLn(' }');
TalkFrom := Temp;
End;
Function TMarkov.Talk(W : TStringList): AnsiString;
Var
Temp : Ansistring;
Ctrl : Integer;
Ctrl2 : Integer;
Begin
Temp := '';
Ctrl2 := 0;
If Assigned(W) Then
Begin
TalkTo(W);
WriteLn;
WriteLn('Generating text');
WriteLn('{');
WriteLn(' Input words : ');
WriteLn(' {');
Write(' ');
For Ctrl := 0 To W.Count - 1 Do
Write(W[Ctrl], ' ');
WriteLn;
WriteLn(' }');
WriteLn(' Context box');
WriteLn(' {');
Write(' ');
fUserUsed.Show;
WriteLn(' }');
WriteLn(' Used words');
WriteLn(' {');
Write(' ');
fUsed.Show;
WriteLn(' }');
WriteLn(' Iterating');
WriteLn(' {');
While (Temp = '') And (Ctrl2 <= 1024) Do
Begin
Temp := TalkFrom;
Inc(Ctrl2);
WriteLn(' Try : ', Ctrl2);
End;
WriteLn(' }');
WriteLn(' Result = ', Temp);
WriteLn('}');
WriteLn;
End;
Talk := Temp;
End;
// Change a word in the dictionary, correcting a mispelling ?
// S1 is the current word, S2 is the word to wich it should be changed
Procedure TMarkov.Correct(S1, S2 : AnsiString);
Var
S1Pos : Integer;
Begin
// WriteLn('Searching for mispelled words');
// WriteLn('{');
// S1Pos := fDict.FindWord(S1);
// If (S1Pos = StartCode) Or (S1Pos = EndCode) Then
// Exit;
// While S1Pos >= 0 Do
// Begin
// WriteLn(' Correcting mispelled word : ', S1, ' to ', S2);
// fDict.Words[S1Pos] := S2;
// S1Pos := fDict.FindWord(S1);
// End;
// WriteLn('}');
Raise Exception.Create('Not yet implemented');
End;
// TLastWordsUsed
Constructor TLastWordsUsed.Create(Size : Cardinal);
Var
Ctrl : Cardinal;
Begin
Inherited Create;
SetLength(fBuffer, Size);
For Ctrl := 0 To (Size - 1) Do
fBuffer[Ctrl] := '';
fPos := 0;
End;
Destructor TLastWordsUsed.Destroy;
Begin
SetLength(fBuffer, 0);
fPos := -1;
Inherited Destroy;
End;
Procedure TLastWordsUsed.WordSaid(W : String);
Begin
If fPos >= Length(fBuffer) Then
fPos := 0;
fBuffer[fPos] := W;
Inc(fPos);
End;
Function TLastWordsUsed.WordUsed(W : String): Integer;
Var
Ctrl : Cardinal;
Temp : Integer;
Begin
Temp := 0;
For Ctrl := 0 To (Length(fBuffer) - 1) Do
If fBuffer[Ctrl] = W Then
Inc(Temp);
WordUsed := Temp;
End;
Procedure TLastWordsUsed.Show();
Var
Ctrl : Cardinal;
Begin
For Ctrl := 0 To (Length(fBuffer) - 1) Do
If fBuffer[Ctrl] <> '' Then
Write(fBuffer[Ctrl], ' ');
WriteLn;
End;
End.
------------------------------------------------------------------------------------------
This code will use a not hidden markov model, so its not usefull for our porpuses as it is, it's just a example (for those who can understand object pascal) of a Markov model.
In our case the way it will work is described as a Hidden Markov Model, where we have already a markov chain filled and need to infer what the current pattern matches best (its a pattern recognition tool).
Looking at the way this sample code iterates trought the markov chain, we can see that a correctly phrase will iterate until the >> marker is found, changing from fixed startphrase/endphrase markers into polimorfic ones, where each end of phrase markers triggers a event by the NPC, we can solve three problems :
Incomplete phrases can be infered from the markov chain, tring to generate text foreward from the incompletion point (Ie : "I am nice" is stored in the markov chain, the user types "I am"; "I am" fails to reach a end state, but iterating the markov chain towards the most probably next state, the system choses that the most likely word to follow "am" is "nice", and them tries to reach a end state from there).
Having polimorft end states means that each endstate is itself a tag about the semantic mean of this phrase, wich can be used by the NPC to trigger some event. Using polimorfic phrase start markers we can have multiple equal phrases that means different things in different contexts (the context chooses the phrase start to be used, them the markov chain iteration will end up in a statistically correct end of phrase marker with the context that this phrases triggers).
Each NPC should have his own markov chain (and be able to reconize a limited set of phrases in order to decrease server load), and receive "education" about phrases and meanings...
All this works out of the box, i just need to translate this into a C++ class and do some modifications...
The most basic difference is that in the example code, the user defines the markov states, where in our pattern recognition system the markov chain will run already "educated" and will only be used to try to solve incomplete phrases and determine the meaning of them (IE : They will stay locked in-game, only NPC dialog editors should be able to modify the markov table and its triggers [and what those triggers means]...)
Ahh.. and whit some randomness in the way the server solves each phrase will be an incentive for players to be more concise and carefull about what to say to a NPC... Saying incomplete phrases could lead to the NPC to react in ways not expected (or worse, make the NPC take offense from the phrase said)... Imagine a player saying "I would like to ..." and the NPC taking this as a "I would like to FIGHT YOU UNTIL DEATH !" LOL, NOW RUN GUY RUN ! I think the human misunderstaind will be a nice realistic touch...