PDA

View Full Version : the gaagle function


smogo
03-06-2004, 11:03 AM
This not a perl quest per se, just a handy pattern you can use in various quests.

It does not require any special component or EMU version (all perl enabled should work).

Overview
one of your NPC has information, that you want available to your players. However, you this information is quite complete, and you don't want to give away everything at once, or you just want your player to be able to investigate freely through more questions to your NPC. Typically, such NPC answers to Hail giving a clue to first part of the information;, like :
P: Hail
N: Hail, Kronnuzic the bald. My name is Larry, and ..[undead] ...
P: what undead ?
N: the undead appeared last month, in a house by the [mines of Toffunir]
P: what mines of Toffunir
etc

This can be quite boring for the player to go, but also to write. It can be very limited, as you would like to match "what ...", but also maybe "where ..." or more combinations. You must also give away clues to allow the player to pull next information, thus the words. It takes much of the natural feeling out.

The gaagle function i give out here is not the miracle function that willl boost AI of quest NPCs, but it can proove quite usefull. It just goes through a list of sentences, indexed by keywords, and returns the one that matches the most of the player's sayings. I'll give an example :

[b]Example 1
The NPC knows (this is no big deal, just an example):
"Freeport is considered by most to be the hub of Antonica ",
"Freeport is the mercantile center of the continent, since it holds the only port with a regular boat to the island continent of Faydwer",
"Freeport holds facilities for most of the artisan trades, and most budding craftsman travel to Freeport to take advantage of the readily available facilities",
"Freeport is also the hub for traffic of all sorts. ",
"The good races travel its streets to go to their guilds and the shops, as well as to the boat to Faydwer.",

we would index first senetence with "Freeport", and "Antonica",
second with “merchant”,”port”,” boat”, and “Faydwer”
third with “facilities”, “artisan”, “trade”,”craft”, and “Freeport”
fourth with “traffic”,”Freeport”, and fifth with “good race”,”Freeport”,”streets”, “guild”,”shop”,”boat”, and “Faydwer“
Now, a player comes in, and says : “i wanna go to Faydwer”. Looking up the index, we find two sentences that match, the second and the last. For now, we just select a random one, and thus NPC replies one of :
"The good races travel its streets to go to their guilds and the shops, as well as to the boat to Faydwer." or
"Freeport is the mercantile center of the continent, since it holds the only port with a regular boat to the island continent of Faydwer"

Now, come and say “where do i find a merchant to trade Faydwer goods with ?”. We would still match the first two sentences on “Faydwer”, but also the second on “merchant”, and third sentence on “trade”. Thus, what we get is 1 hit on first sentence, 2 on second, and 1 on third. If we select only the most matching, we get sentence 2 as a result, which is a fair choice. If we want to allow for more answers, simply assign an acuracy value to each sentence, based on the number of matching words in the input.

There are several issues with this. An IT specialist in search engines (any help appreciated) could explain the best indexing and matching techniques to get relevant results. This is just a first shot. Later we see a few hints to build usefull indexes, and how to improve the match system.

Example 2
We'll see another more playable example ; it is not the typical use of the gaagle function, but, who cares, it should show some of the issues.This is a typical AI problem, commonly used to test expert systems ; it's a kind of riddle. There are 5 houses, each different color, where live 5 fellows each different race, with each a different pet, different drink, and different smoking habit. A group of assertions help to find which relates to what, but they are not exhaustive. In this case, the player willl be the expert system.



sub EVENT_SAY {

if($text =~ /Hail/i){
quest::say("How dare you disturb me ! Ha, I know, you came for The Game. So, beware, you are entitled a single answer. Be it wrong, you meet your fate. There are five houses, each of a different color (red, blue, yellow, ivory and green), inhabited by fellows of different races(Dwarf, Gnome, Erudite, Troll and Barbarian), with different pets, drinks, and smoking herbs. You can ask me about them. But you have to tell me once : who owns the zebra ?");
} elsif ($text =~ /The (\w+) owns the zebra\.?/i){
if($1 =~ /XXX/i){
#correct answer
quest::say("You're not as stupid as you look. Here is your reward.");
quest::say("Now, i have better to do than waste more time with you. Begone.");
quest::exp(1000); quest::sumonitem(12345);
} else {
#wrong answer
quest::say("You're an idiot.");
quest::cast(732);
}
} else {
my %data=(
"0001" => "The Erudite lives in the red house.",
"0002" => "The Troll owns the dog.",
"0003" => "The ivory house is immediately to the left of the green house, where the Wine drinker lives.",
"0004" => "The Hydromel drinker lives in the middle house.",
"0005" => "The fellow who smokes OldGolds also keeps snails.",
"0006" => "The Dwarf drinks Ale.",
"0007" => "The Barbarian resides in the first house on the left.",
"0008" => "The Chesterfields smoker lives next door to the fox owner.",
"0009" => "The LuckyStrike smoker drinks BeetleJuice.",
"0010" => "The Gnome smokes Parliaments.",
"0011" => "The horse owner lives next to the Kools smoker, whose house is yellow.",
"0012" => "The Barbarian lives next to the blue house."
);
my %keywords=(
"ale" => [ "0006" ],
"barbarian" => [ "0007","0012" ],
"beetlejuice" => [ "0009" ],
"blue" => [ "0012" ],
"chesterfields" => [ "0008" ],
"dog" => [ "0002" ],
"door" => [ "0008" ],
"drinker" => [ "0003","0004","0006","0009" ],
"drink" => [ "0003","0004","0006","0009" ],
"drinks" => [ "0003","0004","0006","0009" ],
"dwarf" => [ "0006" ],
"erudite" => [ "0001" ],
"first" => [ "0007" ],
"fox" => [ "0008" ],
"gnome" => [ "0010" ],
"green" => [ "0003" ],
"horse" => [ "0011" ],
#"house" => [ "0001","0003","0003","0004","0007","0011","0012" ],
"hydromel" => [ "0004" ],
"immediately" => [ "0003" ],
"ivory" => [ "0003" ],
"keeps" => [ "0005" ],
"kools" => [ "0011" ],
"left" => [ "0003","0007" ],
#"lives" => [ "0001","0003","0004","0008","0011","0012" ],
"luckystrike" => [ "0009" ],
"middle" => [ "0004" ],
"third" => [ "0004" ],
"next" => [ "0008","0011","0012" ],
"oldgolds" => [ "0005" ],
#"owner" => [ "0008","0011", "0002" ],
#"owns" => [ "0008","0011", "0002" ],
"parliaments" => [ "0010" ],
"red" => [ "0001" ],
"resides" => [ "0007" ],
"smoker" => [ "0008","0009","0011","0005","0010" ],
"smokes" => [ "0008","0009","0011","0005","0010" ],
"smoke" => [ "0008","0009","0011","0005","0010" ],
"snails" => [ "0005" ],
"troll" => [ "0002" ],
"wine" => [ "0003" ],
"yellow" => [ "0011" ]
);
#print "[debug]assume this was not the answer\n";
my $saying="";

$saying=plugin::gaagle(\%data,\%keywords,$text);
#print "[debug]gaagle returned :". ((defined $saying) ? $saying : "<undef>") . "\n";
if(defined $saying){
quest::say($saying);
} else {
#print "pointless chit-chat\n";
quest::say("That was pointless. Don't abuse my time...");
}
}

}


Just cut and paste to any NPC file, and include the gaagle function, as a plugin, or directly in NPC's file.

#returns the most probably matching sentence in %data, indexed by %keywords, given $search.
# %data=( "0001" => "blue tainted sentence", "0002"=>"red tainted sentence", ...);
# %keywords=( "blue" => ["0001"], "red" => ["0002"], "tainted" => ["0001","0002"], ...);
# $search="something blue";
sub gaagle{
my %data=%{$_[0]};
my %keywords=%{$_[1]};
my $search=$_[2];

#print "in gaagle, $search \n";

my @words=split(" ",$search);
my %accuracy=();
foreach $word (@words){
#print "search word $word in keywords\n";
if(defined $keywords{$word}){
my @values=@{$keywords{$word}};
#print "found targets : ",join(",",@values),"\n";
foreach $val ( @{$keywords{$word}}){
#print "increasing accuracy of $val from word $word\n";
$accuracy{$val}++;
}
} else {
#print "not found\n";
}
}

#print "found matches : ", join(",", keys %accuracy), "\n";


my @entries= sort {$accuracy{$a} cmp $accuracy{$b}} keys %accuracy;
my $entry=undef;

my $max=0;
foreach $accval (values %accuracy){ $max+=$accval;}
#print "total accuracy : $max\n";

$max=rand($max);
do {
$entry=shift @entries;
defined $entry && defined $accuracy{$entry} && do{$max -= $accuracy{$entry}};
}while($max > 0 && defined $entry);

if(defined $entry && defined $data{$entry}){
return $data{$entry};
}

return undef;

}


Then try the following input :

/hail
/say where is the red house ?
/say who owns the zebra ?
/say who owns the fox ?
/say who has a pet horse ?
/say how drinks ale ?
/say does the Erudite drink wine ?
/say who drinks wine ?
/say where is the ivory house ?
/say where is the blue house ?
/ooc ...
/say the XXX owns the zebra



The gaagle is at the end of the support file (i'll link later), but one can just paste it in the NPC file. If so, call gaagle(), or main::gaagle(), not plugin::gaagle().

Well, this was just a riddle. Some other index must be set, like “pet”, ”color”, ... and we and want to add more sentences, like “the pets are a dog, a horse, snails, a fox, and a zebra”. Also i commented out the “house” and “own” indexes, as they match on almost every sentence, and thus enforce 'fuzzy' behavior, what we may not want here. I wont go into details of what could be done, it'd make a long, long post.

A few tips
*There is not regexp matching in this version, as it uses perl's hashing facilities. So make sure to index all possible words of same family to a sentence (in the above example, smoke, smokes, smoker are pointing to the same sentences). Indexing with regexp can be extremely powerful, so i'm thinking of writing one later on.

*The match is random, weighted by accuracy (i.e. number of indexed words matching) . You'll need to rewrite part of the gaagle function to match only the most matching sentence (which is not always the more relevant, and often prevents some sentences to show up, on the contrary to this version of gaagle).

*You can enforce accuracy of an index word to a sentence, simply by adding entries to its sentence list. e.g. In the example above “ale” => [“0006”,”0006”,”0006”,”0006”,”0006”,] would boost the chance to get “Dwarf drinks ale” from “who drinks ale ?”. It's important as the “drink” already hits 4 sentences including this one, and the sentence is the only place where to get the Ale info. Doing so improves chance to hit “0006” from 2 in 6 up to 6 in 9.

* also, if you want a minimum requirement to match (i.e. 'at least 3 words', or 'more than half') you'll get much better results, but it makes gaagle function much more complex, and harder to use. For example, you would tune it, but also need to add arguments when you call it.

* Very common words have been removed from the index. It'd make no sense to match agains do, did, the, a, ... as they can appear in any sentence, with no aditional value. I'll discuss that a bit further.

* You can use more than one index on the same data hash. Especially if some information is only to be delivered to some trustful or allied PC, you wan tto write an index that eludes 'hot' words to some “i have no idea what you are talking about”, while, if the PC is in the same guild, as very positive faction, use an index to the full knowledge of the NPC. This amazingly cuts into your scripts, and really keeps them readable, even with high complexity.

If you want to try, you can get a short perl script that creates index, given the sentences on standard input. All you have to do is paste the result to a quest file, remove two extra commmas, and upgrade the index as you wish. And call the gaagle function in your script.

However there is an other strategy, where you add “where”,”what” or even “you” and “me“ to the sentence's index. In this case, you would index “you” to a sentence contining “me”, and “who” to a sentence describing/giving information on someone. I'll give a short example :
“There are 3 skeletons”
“The skeletons appear at night”
“The skeletons appear in the yard”
You would index sentence 1, 2 and 3 with “skeletons”, maybe 2 and 3 with “appear”, but also 1 with “how_many”, 2 with “when”, and 3 with “where”. Doing so, you change accuracy to (25,25,50) on “where are there skeletons”, as compared to (33,33,33). In this simple 3 lines story, it's no big deal, but dealing with more complex scripts is another matter

Summary
This can be usefull, or just waste of time, as you like. Just remember of search engines over www, or even in the EQEMu forums. They can provide very accurate answers, or a zillion useless replies, or just nothing. This time, you get the chance to build the index for the players, so you get in control of what is matched.

This technique is one of the many that can be used with perl scripting. Yet, it allows quick and clean info management. Adding, changing or removing a line does not get you into rewriting the whole if/then/else structure of a file, as you just need to add the line, and update lists of keywords that match.

The output is a bit 'fuzzy', there is no guarantee that a sentence will show up as reply to a keyword, unless you build your index to do so. But, conversation can sometimes get a bit fuzzy, and that's often more enjoyable than plain deterministic behavior.