What about using a special language for NPC interaction ?

[JorgeAldoJR]

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

[peeg]

Yay - seems like you really have some skills in programming!
Why don't you apply to the dev team?

Greetings!

[Wired_Crawler]

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 .

[neko kyouran]

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.

[JorgeAldoJR]

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

[Ralleyon]

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.

[JorgeAldoJR]

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...