-----------------------------------------------------------------------------
-                            the rumor engine                               -
-           written by ville helin <vhelin#iki.fi> in 2002-2004             -
-----------------------------------------------------------------------------


0. HISTORY

11-dec-2002: * first release
11-dec-2002: * added experience
14-dec-2002: * added decay, remembering the teller,
               counting, priority and the effect of
               intelligence
15-dec-2002: * added an example
16-dec-2002: * added the goodness of a rumor
17-dec-2002: * added the memory of old rumors
18-dec-2002: * added the respect update models (1-3),
               action records and final words
19-dec-2002: * clean ups and added another example
20-dec-2002: * enhanced the false rumors
21-dec-2002: * added memorizing the respect changes
               and the objection rumors
23-dec-2002: * typo fixes and other clean ups
24-dec-2002: * added the rules for handling lies,
               the rules for handling conflicting rumors
               and how to compute the goodness of a rumor.
               also added location in a rumor
25-dec-2002: * typo fixes, and added the rules for
               telling a rumor, telling that a rumor is
               not true and handling a personal rumor.
               added the IDEAS-section.
29-jul-2003: * small cleanups, added one special rumor:
               THEREIS, and its background explanations.
23-aug-2003: * added asking
24-aug-2003: * fixed the equation 1 so that it doesn't
               use the respect for the teller any more.
               now it is used for deciding if the reciever
               believes the rumor or not.
20-dec-2003: * added another way to spread the rumors:
               writing them down to a piece of paper.
03-jan-2004: * added another special rumor: DESCRIPTION.


1. INTRODUCTION

in project lecherous gnomes rumors are messages that creatures
pass to each other to gain information about the world they
live in. here i've tried to make a simple model of how rumors
propagate and affect the lives of the creatures who spread them.
i have no scientific basis for my reasonings and models so they
are highly heuristic and subjective. take this with a grain
of salt. all comments are welcome!


2. SYSTEM OVERVIEW

the creature

every creature C_i has separate memories for rumors R that he's
heard and ready to pass on, old rumors O that C_i has heard and
acted upon (this list must be maintained, because otherwise the
creature C_i can hear (and act upon) the same rumor R_n over and over
again) and a list of experiences (rumors also) that C_i has
experienced and is also willing to tell about.

the creature also has a list N of names of other creatures,
and attached to every name there is a value n_i indicating
the respect the creature feels for that name. every name in
N can appear in the rumor messages R_i. if the creature hears
a rumor about a new person P_i then the name of P_i is added
to the creature's namelist N. every time two creatures share
rumors they also share their names with each other, so the
creatures get to know each other quite quickly.


the rumors

every rumor consists of subject, object and action. e.g.,
"orc1003 stole jasmin's panties". the actions are
separated in the code (or lists) so that handling of each
action is done individually (as parsing each action might
require different kind of operations). subject and object
are creatures' id numbers.

rumors are generated by hearing them from another creature,
or by witnessing a scene that generates them (e.g., creature C_a
witnesses creature C_b drinking lots of cola). it is also possible
to write a rumor to e.g., a piece of paper, and all those
able to read the paper shall know the rumor.

attached to a rumor message there is also the teller's id.
so in time some rumors might get discarded by the fact that the
teller of the rumor has now become unpopular by doing bad things
(no one wants to spread rumors told by an unpopular creature,
who once was really good but turned bad).

every rumor has also a priority. if the topic of the rumor is
serious then it should have higher priority than a rumor that
is of common nature.


location in a rumor

some rumors might tell about a location (e.g., "there is a barrel
of cheese at L". here L might be coordinates (x, y), but it could
also be an identification number of an area. here's an example:
the program would count the steps C_a has made in L. after
exceeding some threshold t depending on L without seeing food C_a
would experience that "there is no food in L" and he might tell
it to other creatures, if the information is of some value.

this kind of rumors must be handled differently from other
rumors as here only two things matter: what was seen and who
told about it. the rumor engine does this, but one must signal
the type of handling via action structure's status field (more
about this later).


descriptive rumors

we also need rumors that tell us how the creatures look like.
for example, we might have heard lots of rumors about creature
C_a, but we really don't know what it looks like. in fact, we
could have already seen it without recognizing it. so, when creature
C_a sees creature C_b, it will experience C_b's looks. this it
can tell to other creatures. the creatures can also ask each other
who they are, if they don't already know.


the respect

if creature C_a hears a rumor from creature C_b and C_b
has low respect in C_a's list, then the rumor doesn't affect
C_a's variables much, but if C_a respects C_b much then the
effect should be big.

depending on the rumors the creatures hear about each other
their respect for each other changes. C_a might respect
C_b a lot, but when C_a hears from C_c, who C_a also respects
a lot, that "C_b took a dump in C_a's kitchen", C_a would lower
his respect for C_b.

initially every creature knows only itself and respects itself
completely (same as 1.0). the initial respect creature C_a
feels for another creature C_b should depend on various
things, e.g., C_a meets C_b. C_b is a warrior orc: how does
C_a feel about orcs in general (perhaps an average of all
orcs C_a knows?)? what about C_b being a warrior?


memorizing the respect changes

every time a rumor or an experience causes a creature to
change the respect he feels for another creature (i.e. when
he experiences the rumor/scene generating a rumor), he must
record the change (to the rumor structure). this record will
be used later to neutralize the effect of this rumor if the
creature finds out that the rumor was false.

e.g., creature C_a hears from C_b that C_c killed C_a's friend
C_d. C_a automatically lowers his respect for C_c. next C_a sees
C_d and realizes the rumor C_b told him was false. now C_a
neutralizes the effect of C_b's rumor (and might lower his
respect for C_b for telling a lie).


the experience

for a creature to be able to say that a rumor about him is false
or true, he must maintain a list of experiences that he has
lived. so every scene that can generate a rumor must also generate
an experience.


the false rumours

it is also possible to spread false rumors. but if a creature
C_a hears that "C_b killed C_c" (R_a), and it didn't happen (there's
no record of such an experience in C_b's experience list), and
creature C_b hears R_a, he will say back that "R_a is untrue"
(this is an objection rumor). if C_a believes C_b more than C_i,
the creature who told C_a R_a, C_a will drop rumor R_a. C_a
should then remove the effect R_a has on his respect for C_b.
C_a and C_b might start to spread the negation of R_a to clear
C_b's name.

the same thing goes for actions that prove a rumor R_b to
be a lie. e.g., creature C_a hears that "there is gold in (x, y)"
(R_b). he goes to (x, y) and sees that there's no gold there.
now he will tell everybody the negation of R_b and creatures
who hear this, and have heard the original R_b, will have to
decide which rumor is the right one.


the objection rumors

all rumors are initially positive. e.g., "C_a killed C_b", "C_a
ate a magical shroom" or "C_a found a treasure". only when
someone finds out that a rumor R_a wasn't true he starts to
spread rumor !R_a, which is an objection rumor. accepting
an objection rumor !R_a means that you must neutralize the
effect of R_a and replace R_a with !R_a.


the decay

depending on the priority of the rumor, the creature carrying it,
might forget it after some time has passed. low priority rumors
(e.g., "C_b drank lots of orange juice") are forgotten faster than
high priority rumors that might never be forgotten.

the intelligence of the creature should affect the decaying speed.
here's one model: creatures with high int would drop low priority
rumors fast and concentrate on spreading only high priority
rumors. creatures with low int would spread lots of low
priority rumors.


the goodness of a rumor

if C_a hears a rumor r from C_b, it first checks if it can trust C_b.
if it can, then it checks who has originally created the rumor r (C_c)
C_a checks his respect for C_b and C_c, and the smaller respect will
tell C_a the goodness of the rumor r (as C_b might be making it up
the goodness cannot exceed C_b's goodness).


asking information

the creatures might also want to ask about things from the others.
this depends completely on the AI. e.g., one might want to know about
water-related rumors, if he wanted to find water.

and if creature C_a heard a rumor that C_b did something, and C_a
sees C_b, C_a could go and ask C_b that if the rumor was true. this
can be useful if the creatures want to confirm what they have heard,
e.g., one rumor (told by C_c) tells that "C_b said that there is
water at (x, y)". before travelling to (x, y), C_a might want to
know if this is true, and goes to C_b and asks.


the action records

there must be a record describing the parameters describing every action
(as heard in the rumors) and its handling and effect on the creatures. here's
the record used in project lecherous gnomes:

struct action {
  int action;            /* action id (e.g., ACTION_KILLED, ACTION_HIT, ...) */
  int status;            /* ACTION_STATUS_IS if the action is about seeing */
  float hear;            /* the weight on hearing about the action */
  float see;             /* the weight on seeing the action */
  float subject;         /* the weight on the respect for the subject */
  float object;	         /*                                    object */
  float teller;	         /*                                    teller */
  float original_teller; /*                           original teller */
  float severity;        /* the severity of the action (<0 -> bad, >0 -> good) */
};

all floats are [0, 1] except the range of "severity" which is [-1, 1].

here's an example of this:

struct action actions[1] = { { ACTION_SALIVATE,
                               0.5, /* to hear a rumor about salivating is nearly */
                               1.0, /* as effective as seeing someone to do it */
                               1.0, /* the person who did it */
                               0.0, /* others aren't affected by this rumor */
                               0.0,
                               0.0,
                              -0.1  /* -0.1 < 0 so this is a bad thing to do */
                             } };

the respect update models

every time a creature hears a rumor it updates its respect for those
mentioned in the rumor (subject and object), and for those involved
in the rumor propagation process (teller and original_teller. that's only
two currently, but you could maintain a list, for each rumor, of those
creatures who have passed it on).

here C_a recieves the rumor. p is a list of respects for persons C_a
knows, e.g., p[C_a] == 1.0 and p[C_b] might be 0.1 if C_a doesn't
respect C_b much. r is the rumor C_a recieves. a is the action record
of the action r->action. if C_a heard the rumor then h=1 and s=0. if
C_a saw the action (rumor) then h=0 and s=1.


the respect update model 1 (basic)

this respect update model is basic in the sense that it cannot deal well
with rumors where the outcome of C_a hearing the rumor would depend on
C_a's respect towards the subject and object of the rumor (e.g., C_b kills
C_c. now if C_a hates C_c C_a feels good, and if C_a loves C_c C_a
feels bad). rule 1 is suitable for rumors where the outcome depends
only on the action. i'll give a better model (model 2) later, but
learning model 1 will be helpful in understanding models 2 and 3.

first we have to decide if we believe the rumor at all. we take a random
number between [0, 1] and if it smaller than p[r->teller], then we
believe the rumor, otherwise we don't let it affect us and store it
into memory for the future (in case we hear it again from the same
creature so we can drop it again).

next we need to create one value, e, that tells the effect of the rumor:

e = (a->hear*h + a->see*s)*a->severity;                       (1)

so e depends on the way C_a obtained the rumor and on the
severity of the rumor.

after this we get to update C_a's respect for the creatures involved

p[r->subject] += e*a->subject;                                (2)
p[r->object]  += e*a->object;                                 (3)
p[r->teller]  += e*a->teller;                                 (4)
p[r->original_teller] += e*a->original_teller;                (5)

here we just weight the effect e on the different creatures. we must be
careful here, because r->subject might be the same as r->original teller.


the respect update model 2 (advanced)

let's upgrade the update model to something more general. we still
need e (1) from model 1. this time we take into account C_a's respect for
the creatures appearing in the rumor (subject and object).

p[r->subject] += e*a->subject*(p[r->object] - p[r->subject]); (6)
p[r->object]  += e*a->object*(p[r->subject] - p[r->object]);  (7)
p[r->teller]  += e*a->teller;
p[r->original_teller] += e*a->original_teller;

let's take a closer look at (6) with an example:

action = ACTION_KILLED and e = -1 (to kill is a bad thing). C_a hears
that C_b (r->subject) has killed C_c (r->object). p[C_b] = 0.1 and
p[C_c] = 1.0. now

p[C_b] += -1 * 1 * (p[C_c] - p[C_b]) = -1 * (1.0 - 0.1) = -0.9
               ^ affects the subject totally (for this example)

so C_b (the bad creature, if you ask C_a) got lots of negative respect
from C_a for killing the good creature (if you ask C_a) C_c.

next let's compute the update when p[C_b] = 0.5 and p[C_c] = 0.5:

p[C_b] += -1 * 1 * (0.5 - 0.5) = 0

two equally good creatures are fighting -> well, it doesn't matter.

next let's compute the update when p[C_b] = 0.7 and p[C_c] = 0.5:

p[C_b] += -1 * 1 * (0.5 - 0.7) = 0.2

here C_b got respect for killing C_c when C_a liked more about C_b than
C_c. this isn't quite good, because here C_a supports killing of good
creatures (e.g., p[C_b] = 1.0, p[C_c] = 0.99, and C_b kills C_c). so
we need to improve on our model even more.


the respect update model 3 (the latest)

to improve on model 2 we need to consider what are the properties
of an evil and good creature. here's a trivial way to do this:

0.0 <= p[C_n] <  0.5  ->  C_n is evil
0.5 <= p[C_n] <= 1.0  ->  C_n is good

this dichotomy is in the right direction, but it's not very useful
as some creatures are more evil than the others. but what if a bad
creature C_b kills another bad creature C_c? should C_b get positive
respect for this. i think he should:

p[r->subject] += e*a->subject*(p[r->object] - 0.5);           (8)
p[r->object]  += e*a->object*(p[r->subject] - 0.5);           (9)
p[r->teller]  += e*a->teller;
p[r->original_teller] += e*a->original_teller;

action = ACTION_KILLED and e = -1 (to kill is a bad thing). C_a hears
that C_b (r->subject) has killed C_c (r->object). p[C_b] = 0.1 and
p[C_c] = 1.0. now

p[C_b] += -1 * 1 * (1.0 - 0.5) = -0.5

so evil creature C_b got negative respect for killing a good
creature C_c. what happens when p[C_b] = 0.3 and p[C_c] = 0.4.
and another example where p[C_b] = 0.4 and p[C_c] = 0.3:

p[C_b] += -1 * 1 * (0.4 - 0.5) = 0.1
p[C_b] += -1 * 1 * (0.3 - 0.5) = 0.2

so the effect is the same: in both situations the evil creature C_b
who killed another evil creature C_c, got positive respect from C_a,
but now the amount of respect depended only on the creature's, who
got killed, goodness.

what if p[C_b] = 0.1 and p[C_c] = 0.0, and another example where
p[C_b] = 0.8 and p[C_c] = 0.0?

p[C_b] += -1 * 1 * (0.0 - 0.5) = 0.5
p[C_b] += -1 * 1 * (0.0 - 0.5) = 0.5

this example shows that regardless of the killer, the reward is
the same. but if bad creature C_b kills another bad creature C_c,
will it make C_b a good creature? i think it will, but not linearly.
let's apply sigmoid function sigm(x) to (8) and (9):

p[r->subject] += e*a->subject*(p[r->object] - 0.5)*
                 sigm((p[r->subject] - 0.5) * 10);            (10)
p[r->object]  += e*a->object*(p[r->subject] - 0.5)*
                 sigm((p[r->object] - 0.5) * 10);             (11)
p[r->teller]  += e*a->teller;
p[r->original_teller] += e*a->original_teller;

what if p[C_b] = 0.1 and p[C_c] = 0.0, and another example where
p[C_b] = 0.8 and p[C_c] = 0.0?

p[C_b] += -1 * 1 * (0.0 - 0.5) * sigm((0.1 - 0.5) * 10) =
          0.5 * sigm(-4) = 0.009
p[C_b] += -1 * 1 * (0.0 - 0.5) * sigm((0.8 - 0.5) * 10) =
          0.5 * sigm(3) = 0.476

here we can see that the worse the killer the harder it is for him
to become a better member of the society.

what if p[C_b] = 1.0 and p[C_c] = 0.1, and another example where
p[C_b] = 1.0 and p[C_c] = 0.8?

p[C_b] += -1 * 1 * (0.1 - 0.5) * sigm((1.0 - 0.5) * 10) =
          0.4 * sigm(5) = 0.397
p[C_b] += -1 * 1 * (0.8 - 0.5) * sigm((1.0 - 0.5) * 10) =
          -0.3 * sigm(5) = -0.298

here we can see that the more respected the killer the more
his actions affect his fame (think about the president killing
someone and a nameless bum killing someone).


an example

creature C_a sees water at (x, y). the occasion creates an
experience to C_a. C_a tells this experience (as a rumor) to C_b,
and C_b will learn (adds to his rumors, if he believes C_a) that
there is water at (x, y).

C_b goes on with his daily life, spreading this rumor to others. at one
point in time he gets thirsty. C_b then checks through his rumor list and
finds out that C_a, who is still in C_b's favour, said that there is
water at (x, y), and the place is the closest one of the "there is water"
rumors. so C_b travels to (x, y) and finds water. this makes C_b
forget C_a's rumor, because now C_b has experienced the same thing (and
this might increase C_b's respect for C_a, because what C_a told C_b was
useful and true).

in the example, replace the word "water" with a variable and you can use
the same routines for food, water, shelter, shop, monastery, etc...

initially you can drop n creatures to your world (and more whenever you
feel like it). there they will learn about the surroundings and spread
the word. after a while you'll have creatures who know a lot about
the local places, but if you have created different kinds of
personalities, not everybody will know everything. it all depends
on what the ai does with the information obtained via the rumor engine...


another example

we have a group of orcs O and a group of humans H. initially the orcs respect
each other (so every orc is a good guy to every other orc), and the humans
respect each other, but both groups disrespect each other. H_i thinks that
every orc O_i is a crook and vice versa.

now life goes on, but one day an orc O_a kills a human H_a. this action
is seen by O_b and H_b. O_b thinks that O_a did a good thing, because
O_a killed a human H_a who O_b hated. H_b on the other hand thinks that
O_a is a bigger villain than ever before, because O_a killed H_b's good
friend H_a.

all this can be achieved just by making a rule that orcs initially
disrespect humans and vice versa. as easily you could generate "mutations"
to the group by giving some orcs the ability to love every creature
(or just humans) they see. some humans they might met with might disagree
on this. with swords and other things.


final words

the model of rumor propagation i've described here could be used as
a part of an larger ai, to create a living and changing world. i hope
to see dynamic game engines capable to handling changing situations.
i don't hope to see any more of prerendered/hardcoded games where
you only get to run inside a tube made of indestructible material
and see static creatures with static minds.


3. IDEAS

- attached to every rumor there should be a list of creatures who have
  participated in spreading it. currently only the teller and the
  alledged original teller are recorded. the length of this list should
  depend on the memory-attribute of the listener, and perhaps on the ai.


4. RULES

handling a lie

C_a discovers that rumor R_i is a lie. next:

1. was R_i actually C_a's own experience (e.g., "there was an
   apple at (x, y)")?
   YES -> has C_a told R_i to someone?
          YES -> remove R_i from C_a's memory and exit
2. create a negation of R_i (!R_i).
3. if R_i was told by C_b (!= C_a) then lower C_a's respect for C_b.
4. remove R_i from C_a's memory and add !R_i there.

note: C_a might want or not to spread !R_i depending on the situation.
e.g., "there wasn't an apple at (x, y)" might be a useful rumor
if the creatures wanted to keep a list of locations they've
visited while trying to locate food (so after hearing this no-one
will go to (x, y) if they believe C_a).


computing the goodness of a rumor

C_a recieves a rumor R_a. next

1. C_a checks his respect a for the teller of R_a, and his respect
   b for the (alledged) original teller of R_a.
2. the goodness of R_a is the smallest value of {respect(a), respect(b)}.

this is based on the fact that the goodness of a rumor is as high
as the respect for the least respected creature appearing in the
rumor's path of propagation. currently only the latest and the
first tellers are recorded in the rumor structure, but nothing
forbids from recording the whole path.


handling conflicting rumors

C_a recieves a new rumor R_a that conflicts with an older rumor R_b
(or C_a's experience). next:

1. C_a computes which one he can trust more, R_a or R_b
2. if C_a trusts R_b more (the new rumor R_a doens't sound so good)
   -> exit
3. the new rumor R_a sounds better
4. if R_b is a true statement (it had an effect on C_a which must
   be neutralized)
   -> neutralize the effect of R_b on C_a
5. if R_b is an objection rumor (it had already neutralized !R_b's
   effect)
   -> experience the new rumor R_a
6. remove R_b from C_a's memory and add R_a there


telling a rumor

C_a tells C_b a rumor R_a. next

1.  C_b checks if he knows C_a. if C_b doesn't then he computes
    initial respect for C_a and adds him to the list of persons
    he knows (this operation is called chadd)
2.  C_a chadds C_b.
3.  C_b will now check his respect for C_a. if this respect is
    less than the threshold t (0.5) then C_b won't listen to C_a
    -> exit
4.  C_a selects a rumor R_a he tells to C_b.
5.  C_b now computes the goodness g of R_a.
6.  if g < 0.5 then C_b won't believe that R_a is true
    -> exit
7.  C_b randomizes a value [0, 1] and if it is greater than g
    (here we check if C_b really believes the rumor)
    -> exit
7.  C_b checks if he has heard R_a before.
    YES -> exit
8.  C_b checks if he is mentioned in the rumor.
    YES -> C_b handles R_a as a personal rumor, and exit.
9.  C_b checks if he knows !R_a or has experienced R_a or !R_a.
10. if C_b knows R_a
    -> C_b handles R_a as a duplicate rumor, and exit.
11. if C_b knows !R_a
    -> C_b handles R_a as a conflicting rumor, and exit.
12. R_a was a totally new rumor for C_b. add R_a to C_b's list
    of old (handled) rumors, and new (spreadable) rumors.
13. C_b experiences the message of R_a.


handling a personal rumor

C_a recieves a rumor R_a from C_b. C_a appears in R_a. next

1. C_a checks if he knows about R_a (i.e. has C_a experienced R_a).
   NO, and R_a is a true statement -> tell C_b that R_a is not true,
       and exit
   NO, and R_a is an objection rumor -> exit
   YES, but C_a knows !R_a -> handle the conflicting rumor R_a,
        and exit
   YES -> handle the duplicate rumor R_a


telling that a rumor is not true

C_a tells C_b that a rumor R_a C_a just heard from C_b, is not true. next

1. C_b checks which one he respects more, C_a or the creature C_c
   C_b heard R_a from.
   C_c -> exit
2. C_b neutralizes the effect of R_a, and forgets it
3. C_b experiences !R_a, and memorizes it