Edirlei Soares De Lima

Antonio L Furtado
email: furtado@inf.puc-rio.br

Bruno Feijó
email: bfeijo@inf.puc-rio.br

Storytelling Variants: The Case of Little Red Riding Hood

Keywords: Folktales, Variants, Types and Motifs, Semiotic Relations, Digital Storytelling, Plan Recognition

A small number of variants of a widely disseminated folktale is surveyed, and then analyzed in an attempt to determine how such variants can emerge while staying within the conventions of the genre. The study follows the classification of types and motifs contained in the Index of Antti Aarne and Stith Thompson. The paper's main contribution is the characterization of four kinds of type interactions in terms of semiotic relations. Our objective is to provide the conceptual basis for the development of semi-automatic methods to help users compose their own narrative plots.

Introduction

When trying to learn about storytelling, in order to formulate and implement methods usable in a computer environment, two highly influential approaches come immediately to mind, both dealing specifically with folktales: Propp's functions [START_REF] Propp | Morphology of the Folktale[END_REF] and the comprehensive classification of types and motifs proposed by Antti Aarne and Stith Thompson, known as the Aarne-Thompson Index (heretofore simply Index) [START_REF] Aarne | The Types of the Folktale[END_REF][START_REF] Thompson | The Folktale[END_REF][START_REF] Uther | The Types of International Folktales[END_REF].

In previous work, as part of our Logtell project [START_REF] Ciarlini | Modeling interactive storytelling genres as application domains[END_REF][START_REF] Ciarlini | A logic-based tool for interactive generation and dramatization of stories[END_REF], we developed prototypes to compose narrative plots interactively, employing a plan-generation algorithm based on Propp's functions. Starting from different initial states, and giving to users the power to intervene in the generation process, within the limits of the conventions of the genre on hand, we were able to obtain in most cases a fair number of different plots, thereby achieving an encouraging level of variety in plot composition.

We now propose to invest on a strategy that is based instead on the analysis of already existing stories. Though we shall focus on folktales, an analogous conceptual formulation applies to any genre strictly regulated by conventions and definable in terms of fixed sets of personages and characteristic events. In all such genres one should be able to pinpoint the equivalent of Proppian functions, as well as of ubiquitous types and motifs, thus opening the way to the reuse of previously identified narrative patterns as an authoring resource. Indeed it is a well-established fact that new stories often emerge as creative adaptations and combinations of old stories: this is a most common practice among even the best professional authors, though surely not easy to trace in its complex ramifications, as eloquently expressed by the late poststructuralist theoretician Roland Barthes [3,p. 39]:

Any text is a new tissue of past citations. Bits of code, formulae, rhythmic models, fragments of social languages, etc., pass into the text and are redistributed within it, for there is always language before and around the text. Intertextuality, the condition of any text whatsoever, cannot, of course, be reduced to a problem of sources or influences; the intertext is a general field of anonymous formulae whose origin can scarcely ever be located; of unconscious or automatic quotations, given without quotation marks.

The present study utilizes types and motifs of the Aarne-Thompson's Index, under whose guidance we explore what the ingenuity of supposedly unschooled narrators has legated. We chose to concentrate on folktale type AT 333, centered on The Little Red Riding Hood and spanning some 58 variants (according to [START_REF] Tehrani | The Philogeny of Little Red Riding Hood[END_REF]) from which we took a small sample. The main thrust of the paper is to investigate how such rich diversities of variants of traditional folktales came to be produced, as they were told and retold by successive generations of oral storytellers, hoping that some of their tactics are amenable to semi-automatic processing. An added incentive to work with folktale variants is the movie industry's current interest in adaptations of folktales for adult audiences, in contrast to early Disney classic productions.

Related work is found in the literature of computational narratology [START_REF] Cavazza | Narratology for Interactive Storytelling: A Critical Introduction[END_REF][START_REF] Mani | Computational Narratology[END_REF] a new field that examines narratology from the viewpoint of computation and information processingwhich offers models and systems based on tale types/motifs that can be used in story generation and/or story comparison. Karsdorp et al. [START_REF] Karsdorp | In Search of an Appropriate Abstraction Level for Motif Annotations[END_REF] believe that oral transmission of folktales happens through the replication of sequences of motifs. Darányi et al. [START_REF] Darányi | Toward Sequencing 'Narrative DNA': Tale Types, Motif Strings and Memetic Pathways[END_REF] handle motif strings like chromosome mutations in genetics. Kawakami et al. [START_REF] Kawakami | On Modeling Conceptual and Narrative Structure of Fairytales[END_REF] cover 23 Japanese texts of Cinderella tales, whilst Swartjes et al use Little Red Riding Hood as one of their examples [START_REF] Swartjes | Iterative authoring using story generation feedback: debugging or co-creation?[END_REF].

Our text is organized as follows. Section 2 presents the two classic variants of AT 333. Section 3 summarizes additional variants. Section 4 has our analysis of the variant-formation phenomenon, with special attention to the interaction among types, explained in terms of semiotic relations. Section 5 describes a simple plan-recognition prototype working over variant libraries. Section 6 contains concluding remarks. The full texts of the variants cited in the text are available in a separate document. 1

2

The two classic variants

In the Index, the type of interest, AT 333, characteristically named The Glutton, is basically described as follows, noting that two major episodes are listed [1, p. 125]:

The wolf or other monster devours human beings until all of them are rescued alive from his belly. I. Wolf's Feast. By masking as mother or grandmother the wolf deceives and devours a little girl whom he meets on his way to her grandmother's.

II.

Rescue. The wolf is cut open and his victims rescued alive; his belly is sewed full of stones and he drowns, or he jumps to his death.

The first classic variant, Le Petit Chaperon Rouge (Little Red Riding Hood), was composed in France in 1697, by Charles Perrault [START_REF] Perrault | Little Red Riding Hood[END_REF], during the reign of Louis XIV th . It consists of the first episode alone, so that there is no happy ending, contrary to what children normally expect from nursery fairy tales. The little girl, going through the woods to see her grandmother, is accosted by the wolf who reaches the grandmother's house ahead of her. The wolf kills the grandmother and takes her place in bed. When the girl arrives, she is astonished at the "grandmother"'s large, ears, large eyes, etc., until she asks about her huge teeth, whereat the wolf gobbles her up. Following a convention of the genre of admonitory fables, a "moralité" is appended, to the effect that well-bred girls should not listen to strangers, particularly when they pose as "gentle wolves"

The second and more influential classic variant is that of the brothers Grimm (Jacob and Wilhelm), written in German, entitled Rotkäppchen (Little Red Cap) [START_REF] Grimm | The Complete Grimm's FairyTales[END_REF], first published in 1812. The girl's question about the wolf's teeth is replaced by: "But, grandmother, what a dreadful big mouth you have!" This is a vital changenot being bitten, the victims are gobbled up aliveand so the Grimm variant can encompass the two episodes prescribed for the AT 333 type. Rescue is effected by a hunter, who finds the wolf sleeping and cuts his belly, allowing girl and grandmother to escape. The wolf, his belly filled with heavy stones fetched by the girl, wakes up, tries to run away and falls dead, unable to carry the weight. As a moral addendum to the happy ending, the girl promises to never again deviate from the path when so ordered by her mother. Having collected the story from two distinct sources, the brothers wrote a single text with a second finale, wherein both female characters show that they had learned from their experience with the villain. A second wolf comes in with similar proposals. The girl warns her grandmother who manages to keep the animal outside, and eventually they cause him to fall from the roof into a trough and be drowned.

Some other variants

In [START_REF] Tehrani | The Philogeny of Little Red Riding Hood[END_REF] no less than 58 folktales were examined as belonging to type AT 333 (and AT 123). Here we shall merely add seven tales to the classic ones of the previous section. Since several variants do not mention a red hood or a similar piece of clothing as attribute of the protagonist, the conjecture was raised that this was Perrault's invention, later imitated by the Grimms. However a tale written in Latin by Egbert de Liège in the 11 th century, De puella a lupellis seruata (About a Girl Saved from Wolf Cubs) [START_REF] Ziolkowski | A Fairy Tale from before Fairy Tales: Egbert of Liège's 'De puella a lupellis seruata' and the Medieval Background of 'Little Red Riding Hood[END_REF], arguably prefiguring some characteristics of AT 333, features a red tunic which is not merely ornamental but plays a role in the events. The girl had received it as a baptismal gift from her godfather. When she was once captured by a wolf and delivered to its cubs to be eaten, she suffered no harm. The virtue of baptism, visually represented by the red tunic, gave her protection. The cubs, their natural ferocity sub-dued, gently caressed her head covered by the tunic. The moral lesson, in this case, is consonant with the teaching of the Bible (Daniel VI, 27).

Whilst in the variants considered so far the girl is presented as naive, in contrast to the clever villain, the situation is reversed in the Conte de la Mère-grand (The Story of Grandmother), collected by folklorist Achille Millien in the French province of Nivernais, circa 1870, and later published by Paul Delarue [START_REF] Delarue | The Story of Grandmother[END_REF]. In this variant, which some scholars believe to be closer to the primitive oral tradition, the villain is a "bzou", a werewolf. After killing and partly devouring the grandmother's body, he stores some of her flesh and fills a bottle with her blood. When the girl comes in, he directs her to eat and drink from these ghastly remains. Then he tells her to undress and lie down on the bed. Whenever the girl asks where to put each piece of clothing, the answer is always: "Throw it in the fire, my child; you don't need it anymore." In the ensuing dialogue about the peculiar physical attributes of the fake grandmother, when the question about her "big mouth" is asked the bzou gives the conventional reply: "All the better to eat you with, my child!"but this time the action does not follow the words. What happens instead is that the girl asks permission to go out to relieve herself, which is a ruse whereby she ends up outsmarting the villain and safely going back to home (cf. http://expositions.bnf.fr/contes/gros/chaperon/nivers.htm).

An Italian variant published by Italo Calvino, entitled Il Lupo e le Tre Ragazze (The Wolf and the Three Girls) [START_REF] Calvino | Italian Folktales[END_REF], adopts the trebling device [START_REF] Propp | Morphology of the Folktale[END_REF] so common in folktales, making three sisters, one by one, repeat the action of taking victuals to their sick mother. The wolf intercepts each girl but merely demands the food and drink that they carry. The youngest girl, who is the protagonist, throws at the wolf a portion that she had filled with nails. This infuriates the wolf, who hurries to the mother's house to devour her and lay in wait for the girl. After the customary dialogue with the wolf posing as the mother, the animal also swallows the girl. The townspeople observe the wolf coming out, kill him and extract mother and girl alive from his belly. But that is not all, as Calvino admits in an endnote. Having found the text as initially collected by Giambattista Basile, he had deliberately omitted what he thought to be a too gruesome detail ("una progressione troppo truculenta"): after killing the mother, the wolf had made "a doorlatch cord out of her tendons, a meat pie out of her flesh, and wine out of her blood". Repeating the strange above-described episode of the Conte de la Mère-grand, the girl is induced to eat and drink from these remains, with the aggravating circumstance that they belonged to her mother, rather than to a more remotely related grandparent.

Turning to China, one encounters the tale Lon Po Po (Grammie Wolf), translated by Ed Young [START_REF] Young | Lon Po Po: A Red-Riding Hood Story from China[END_REF], which again features three sisters but, unlike the Western folktale cliché, shows the eldest as protagonist, more experienced and also more resourceful than the others. The mother, here explicitly declared to be a young widow, goes to visit the grandmother on her birthday, and warns Shang, the eldest, not to let anyone inside during her absence. A wolf overhears her words, disguises as an old woman and knocks at the door claiming to be the grandmother. After some hesitation, the girls allow him to enter and, in the dark, since the wolf claims that light hurts his eyes, they go to bed together. Shang, however, lighting a candle for a moment catches a glimpse of the wolf's hairy face. She convinces him to permit her two sisters to go outside under the pretext that one of them is thirsty. And herself is also allowed to go out, promising to fetch some special nuts for "Grammie". Tired of waiting for their return, the wolf leaves the house and finds the three sisters up in a tree. They persuade him to fetch a basket mounted on which they propose to bring him up, in order to pluck with his own hands the delicious nuts. They pull on the rope attached to the basket, but let it go so that the wolf is seriously bruised. And he finally dies when the false attempt is repeated for the third time.

Another Chinese variant features a bear as the villain: Hsiung chia P`o (Goldflower and the Bear) [START_REF] Mi | Goldflower and the Bear[END_REF], translated by Chiang Mi. The crafty protagonist, Goldflower, is once again an elder sister, living with her mother and a brother. The mother leaves them for one day to visit their sick aunt, asking the girl to take care of her brother and call their grandmother to keep them company during the night. The bear knocks at the door, posing as the grandmother. Shortly after he comes in, the girlin spite of the darknessends up disclosing his identity. She manages to lock the boy in another room, and then obeys the bear's request to go to bed at his side. The villain's plan is to eat her at midnight, but she asks to go out to relieve her tummy. As distrustful as the werewolf in the before-mentioned French variant, the bear ties one end of a belt to her handan equally useless precaution. Safely outside on top of a tree, Goldflower asks if he would wish to eat some pears, to be plucked with a spear, which the famished beast obligingly goes to fetch in the house. The girl begins with one fruit, but the next thing to be thrown into his widely open gullet is the spear itself. Coming back in the morning, the mother praises the brave little Goldflower.

One variant, published in Portugal by Guerra Junqueiro, entitled O Chapelinho Encarnado [START_REF] Guerra Junqueiro | Contos para a Infância[END_REF], basically follows the Grimm brothers pattern. A curious twist is introduced: instead of luring the girl to pick up wild flowers, the wolf points to her a number of medicinal herbs, all poisonous plants in reality, and she mistakes him for a doctor. At the end, the initiative of filling the belly of the wolf with stones is attributed not to the girl, but to the hunter, who, after skinning the animal, merrily shares the food and drink brought by the girl with her and her grandmother.

The highly reputed Brazilian folklorist Camara Cascudo included in his collection [START_REF] Camara Cascudo | Contos Tradicionais do Brasil[END_REF] a variant, O Chapelinho Vermelho, which also follows the Grimm brothers pattern. The mother is introduced as a widow and the name of the girl is spelled out: Laura. Although she is known, as the conventional title goes, by a nickname translatable as "Little Red Hat", what she wears every day is a red parasol, given by her mother. One more particularity is that, upon entering her grandmother's house, the girl forgets to close the door, so that finding the door open is what strikes the hunter as suspicious when he approaches the house. The hunter bleeds the wolf with a knife and, noticing his distended belly, proceeds to open it thus saving the two victims. Nothing is said about filling the wolf's belly with stones, the wounds inflicted by the hunter's knife having been enough to kill him. Two prudent lessons are learned: (1) Laura would not forget her mother's recommendation to never deviate from the path, the specific reason being given here that there existed evil beasts in the wood; (2) living alone should no longer be an option for the old woman, who from then on would dwell with her daughter and granddaughter.

Comments on the formation of variants

It is a truism that people tend to introduce personal contributions when retelling a story. There are also cultural time and place circumstances that require adaptations; for example, in the Arab world the prince would in no way be allowed to meet Cinderella in a ballroomhe falls in love without having ever seen her (cf. "Le Bracelet de Cheville" in the Mardrus translation of One Thousand and One Nights [START_REF] Mardrus | Les Mille et une Nuits[END_REF]). Other differences among variants may result from the level of education of the oral storytellers affecting how spontaneous they are, and the attitude of the collectors who may either prefer to reproduce exactly what they hear or introduce corrections and rational explanations while omitting indecorous or gruesome scenes. On the storyteller's part, however, this tendency is often attenuated by an instinctive pact with the audiencewith children, in specialin favour of faithful repetition, preferably employing the very same words. Indeed the genre of folktales is strongly marked by conventions which, to a remarkable extent, remain the same in different times and places. The folklorist Albert Lord called tension of essences the compulsion that drives all singers (i.e. traditional oral storytellers) to strictly enforce such conventions [29, p. 98]:

In our investigation of composition by theme this hidden tension of essences must be taken into consideration. We are apparently dealing here with a strong force that keeps certain themes together. It is deeply imbedded in the tradition; the singer probably imbibes it intuitively at a very early stage of his career. It pervades his material and the tradition. He avoids violating the group of themes by omitting any of its members. [We shall see] that he will even go so far as to substitute something similar if he finds that for one reason or another he cannot use one of the elements in its usual form.

The notion of tension of essences may perhaps help explaining not only the total permanence of some variants within the frontiers of a type, but also the emergence of transgressive variants, which absorb features pertaining to other types, sometimes even provoking a sensation of strangeness. When an oral storyteller feels the urge "to substitute something similar" in a story, the chosen "something" should, as an effect of the tension-of-essences forceful compulsion, still belong to the folktale genrebut what if the storyteller's repertoire comprises more than one folktale type? As happens with many classifications, the frontiers between the types in the Index are often blurred, to the point that one or more motifs can be shared and some stories may well be classified in more than one type. So a viable hypothesis can be advanced that some variants did originate through, so to speak, a type-contamination phenomenon.

Accordingly we propose to study type interactions as a possible factor in the genesis of variants. We shall characterize the interactions that may occur among types, also involving motifs, by way of semiotic relations, taking an approach we applied before to the conceptual modelling of both literary genres and business information systems [START_REF] Ciarlini | Event relations in plot-based plot composition[END_REF][START_REF] Karlsson | Conceptual Model and System for Genre-Focused Interactive Storytelling[END_REF][START_REF] Furtado | Constructing Libraries of Typical Plans[END_REF]. We distinguish four kinds of semiotic relations, associated with the so-called four master tropes [START_REF] Burke | A Grammar of Motives[END_REF][START_REF] Chandler | Semiotics: the Basics[END_REF], whose significance has been cogently stressed by a literary theory scholar, Jonathan Culler, who regards them "as a system, indeed the system, by which the mind comes to grasp the world conceptually in language" [15, p. 72]. For the ideas and for the nomenclature in the table below, we are mainly indebted to the pioneering semiotic studies of Ferdinand de Saussure [START_REF] Saussure | Cours de Linguistique Générale[END_REF]: The itemized discussion below explores the meaning of each of the four semiotic relations, as applied to the derivation of folktale type variants stemming from AT 333.

relation
(1) Syntagmatic relation with type AT 123. As mentioned at the beginning of section 2, the Index describes type AT 333 as comprising two episodes, namely Wolf's Feast and Rescue, but the classic Perrault variant does not proceed beyond the end of the first episode. As a consequence, one is led to assume that the Rescue episode is not essential to characterize AT 333. On the other hand the situation created by Wolf's Feast is a long distance away from the happy-ending that is commonly expected in nursery fairy tales. A continuation in consonance with the Rescue episode, exactly as described in the Index, is suggested by AT 123: The Wolf and the Kids, a type pertaining to the group of Animal Tales, which contains the key motif F913: Victims rescued from swallower's belly.

The connection (syntagmatic relation) whereby AT 123 complements AT 333 is explicitly declared in the Index by "cf." cross-references [1, p. 50, p. 125]. Moreover the Grimm brothers variant, which has the two episodes, is often put side by side with another story equally collected by them, The Wolf and the Seven Little Kids [START_REF] Grimm | The Complete Grimm's FairyTales[END_REF], clearly of type AT 123.

Still it must be noted that several of the variants reported here do not follow the Grimm pattern in the Rescue episode. They diverge with respect to the outcome, which, as seen, may involve the death of the girl, or her rescue after being devoured, or even her being totally preserved from the villain's attempts either by miraculous protection or by her successful ruses.

(2) Paradigmatic relation with type AT 311B*. For the Grimm variant, as also for those that follow its pattern (e.g. the Italian and the two Portuguese variants in section 3), certain correspondences or analogies can be traced with variants of type AT 311B*: The Singing Bag, a striking example being another story collected in Brazil by Camara Cascudo [START_REF] Camara Cascudo | Contos Tradicionais do Brasil[END_REF], A Menina dos Brincos de Ouro (The Girl with Golden Earrings). Here the villain is neither an animal nor a werewolf; he is a very ugly old man, still with a fearsome aspect but no more than human. The golden earrings, a gift from her mother, serve as the girl's characteristic attribute and have a function in the plot. As will be noted in the summary below, the villain's bag becomes the wolf's belly of the Grimm variant, and what is done to the bag mirrors the act of cutting the belly and filling it with stones. In this sense, the AT 311B* variant replaces the Grimm variant.

One day the girl went out to bring water from a fountain. Having removed her earrings to wash herself, she forgot to pick them up before returning. Afraid to be reprimanded by her mother, she walked again to the fountain, where she was caught by the villain and sewed inside a bag. The man intended to use her to make a living. At each house that he visited, he advertised the magic bag, which would sing when he menaced to strike it with his staff. Everywhere people gave him money, until he came inadvertently to the girl's house, where her voice was recognized. He was invited to eat and drink, which he did in excess and fell asleep, whereat the bag was opened to free the girl and then filled with excrement. At the next house visited, the singing bag failed to work; beaten with the staff, it ruptured spilling its contents.

(3) Meronymic relation with type AT 437. In The Story of Grandmother the paths taken by the girl and the werewolf to reach the old lady's house are called, respectively, the Needles Road and the Pins Road. And, strangely enough, while walking along her chosen path, the little girl "enjoyed herself picking up needles" [START_REF] Delarue | The Story of Grandmother[END_REF]. Except for this brief and puzzling mention, these objects remain as meaningless details, having no participation in the story.

And yet, browsing through the Index, we see that needles and pins are often treated as wondrous objects (motifs D1181: Magic Needle and D1182: Magic Pin). And traversing the Index hierarchy upwards, from motifs to types, we find them playing a fundamental role in type AT 437: The Needle Prince (also named The Supplanted Bride), described as follows [1, p. 140]: "The maiden finds a seemingly dead prince whose body is covered with pins and needles and begins to remove them ... ". Those motifs are thus expanded into a full narrative in AT 437.

Especially relevant to the present discussion is a variant from Afghanistan, entitled The Seventy-Year-Old Corpse reported by Dorson [START_REF] Dorson | Folktales Told Around the World[END_REF], which has several elements in common with the AT 333 variants. An important difference, though, also deserves mention: the girl lives alone with her old father, who takes her to visit her aunt. We are told that, instead of meeting the aunt, the girl finds a seventy year old corpse covered with needles, destined to revive if someone would pick the needles from his body. At the end the girl marries the "corpse", whereas no further news are heard about her old father, whom she had left waiting for a drink of water. One is tempted to say that Bruno Bettelheim would regard this participation of two old males, the father and the daunting corpse, as an uncannily explicit confirmation of the presence in two different formsof the paternal figure, in an "externalization of overwhelming oedipal feelings, and ... in his protective and rescuing function" [4, p. 178].

(4) Antithetic relation with type AT 449. Again in The Story of Grandmother we watch the strange scene of the girl eating and drinking from her grandmother's remains, punctuated by the acid comment of a little cat: "A slut is she who eats the flesh and drinks the blood of her grandmother!" The scene has no consequence in the plot, and in fact it is clearly inconsistent with the role of the girl in type AT 333. It would sound natural, however, in a type in opposition to AT 333, such as AT 449: The Tsar's Dog, wherein the roles of victim and villain are totally reversed. The cannibalistic scene in The Story of Grandmother has the effect of assimilating the girl to a ghoul (motif G20 in the Index), and the female villain of the most often cited variant of type AT 449, namely The Story of Sidi Nouman (cf. Andrew Lang's translation in Arabian Nights Entertainment) happens to be a ghoul.

No less intriguing in The Story of Grandmother are the repartees in the ensuing undressing scene, with the villain (a werewolf, as we may recall) telling the girl to destroy each piece of clothing: "Throw it in the fire, my child; you don't need it anymore." This, too, turns out to be inconsequential in the plot, but was a major concern in the werewolf historical chronicles and fictions of the Middle Ages [START_REF] Baring-Gould | The Book of Were-Wolves[END_REF][START_REF] Sconduto | Metamorphoses of the Werewolf: A Literary Study from Antiquity Through the Renaissance[END_REF]. In 1521, the Inquisitor-General for the diocese of Besançon heard a case involving a certain Pierre Bourget [START_REF] Baring-Gould | The Book of Were-Wolves[END_REF]. He confessed under duress that, by smearing his body with a salve given by a demon, he became a wolf, but "the metamorphosis could not take place with him unless he were stark naked". And to recover his form he would "beat a retreat to his clothes, and smear himself again". Did the werewolf in The Story of Grandmother intend to transform the girl into a being of his species? Surely the anonymous author did not mean that, but leaving aside the norms of AT 333 the idea would not appear to be so farfetched.

In this regard, also illustrating type AT 449, there are two medieval lays (short narrative poems) that deserve our attention. They are both about noble knights with the ability to transform themselves into wolves. In the two narratives, they are betrayed by their villainous wives, intent on permanently preventing their resuming the human form. In Marie de France's lay of Bisclavret [START_REF] De | The Lais of Marie de France[END_REF] an old Breton word signifying "werewolf"the woman accomplishes this effect by stealing from a secret hiding place the man's clothes, which he needed to put on again to undo the transformation. In the other example, the anonymous lay of Melion [START_REF] Burgess | Eleven Old French Narrative Lays[END_REF], after a magic ring is applied to break the enchantment, the man feels tempted to punish the woman by inflicting upon her the same metamorphosis.

In the preceding discussion we purported to show how types can be semiotically related, and argued that such relations constitute a factor to be accounted for in the emergence of variants. We should add that types may be combined in various ways to yield more complex types, whose attractiveness is heightened by the occurrence of unexpected changes. Indeed Aristotle's Poetics2 distinguishes simple and complex plots, characterizing the latter by recognition () and reversal (). Differently from reversal, recognition does not imply that the world changed, but that the beliefs of the characters about themselves and the current facts were altered.

In particular, could a legitimate folktale promote the union of monster and girl? Could we conciliate type AT 333 (where the werewolf is a villain) with the antithetically related medieval lays of type AT 449 (where the werewolf is the victim)? Such conciliations of opposites are treated under the topic of blending [START_REF] Fauconnier | Conceptual projection and middle spaces[END_REF], often requiring creative adaptations. A solution is given by type AT 425C: Beauty and the Beast. At first the Beast is shown as the villain, claiming the life of the merchant or else of one of his daughters: "Go and see if there's one among them who has enough courage and love for you to sacrifice herself to save your life" [41, p. 159]but then proves to be the victim of an enchantment. Later, coming to sense his true inner nature (an event of recognition, as in Aristotle), Belle makes him human again by manifesting her love (motif D735-1: Disenchanting of animal by being kissed by woman). So, it is as human beings that they join.

Alternatively, we might combine AT 333 and AT 449 by pursuing until some sort of outcome the anomalous passages of The Story of Grandmother, allowing the protagonists to join in a non-human form. The werewolf feeds human flesh of his victim to the girl, expecting that she would transform herself like he did (as Melion for a moment thought to cast the curse upon his wife), thereby assuming a shape that she would keep forever once her clothes were destroyed (recall the concern of Pierre Bourget to "beat a retreat to his clothes", and the knight's need to get back his clothes in Bisclavret). At the end the two werewolves would marry and live happily forever after, as a variant of an admittedly misbegotten new type (of, perhaps, a modern appeal, since it would also include among its variants the story of the happy vampires Edward and Bella in the Twilight Saga: http://twilightthemovie.com/).

First steps towards variants in computer-generated stories

To explore in a computer environment the variants of folktale types, kept in a library of typical plans, we developed a system in C# that does plan-recognition over the variants of the type indicated (e.g. AT 333), with links to pages of semiotically related types (e.g. AT 123, AT 311B*, AT 437, AT 449). Plan-recognition involves matching a number of actions against a pre-assembled repertoire of plot patterns (cf. [START_REF] Furtado | Constructing Libraries of Typical Plans[END_REF][START_REF] Karlsson | Conceptual Model and System for Genre-Focused Interactive Storytelling[END_REF]).

Let P be a set of m variants of a specific tale type that are represented by complete plans, 𝑃 = {𝑃 1 , 𝑃 2 , ⋯ , 𝑃 𝑚 }, where each plan is a sequence of events, i.e.: 𝑃 𝑖 = 〈𝑒 1 𝑖 , 𝑒 2 𝑖 , ⋯ , 𝑒 𝑛 𝑖 𝑖 〉. These events are actions with ground arguments that are story elements (specific names, places, and objects). For instance, P k = go(Abel, Beach), meet(Abel, Cain), kill(Cain, Abel). The library of typical plans is defined by associating each plan P i with the following elements: (1) the story title; (2) a set of parameterized termsakin to those we use in Logtell [START_REF] Ciarlini | A logic-based tool for interactive generation and dramatization of stories[END_REF] to formalize Proppian functionsdescribing the story events; (3) the specification of the characters' roles (e.g. villain, victim, hero) and objects' functions (e.g. wolf's feast place, basket contents); (4) the semiotic relations of the story with other variants of same or different types (Section 4); ( 5) a text template used to display the story as text, wherein certain phrases are treated as variables (written in the format #VAR 1 #); and (6) the comics resources used for dramatization, indicating the path to the folder that contains the images representing the characters and objects of the narrative and a set of event templates to describe the events textually. The library is specified in an XML file.

Let T be a partial plan expressed as a sequence of events given by the user. The system finds plans in P that are consistent with T. During the searching process, the arguments of the events in P are instantiated. For example, with the input T = {give(Anne, ring, Little Ring Girl), ask_to_take(Marie, Little Ring Girl, tea, Anne), eat(Joe, Little Ring Girl)}, the following stories are generated: Story 1: give(Anne, ring, Little Ring Girl), ask_to_take(Marie, Little Ring Girl, tea, Anne), go(Little Ring Girl, the woods), meet(Little Ring Girl, Joe), go(Joe, Grandmother's house), eat(Joe, Anne), disguise(Joe, Anne), lay_down(Joe, Grandmother's bed), go(Little Ring Girl, Grandmother's house), delivery(Little Ring Girl, tea), question(Little Ring Girl, Joe), eat(Joe, Little Ring Girl), sleep(Joe), go(Hunter, Grandmother's house), cut(Hunter, Joe, axe), jump_out_of(Little Ring Girl, Joe), jump_out_of(Anne, Joe), die(Joe).

Story 2: give(Anne, ring, Little Ring Girl), ask_to_take(Marie, Little Ring Girl, tea, Anne), go(Little Ring Girl, the woods), meet(Little Ring Girl, Joe), go(Joe, Grandmother's house), eat(Joe, Anne), disguise(Joe, Anne), lay_down(Joe, Grandmother's bed), go(Little Ring Girl, Grandmother's house), lay_down(Little Ring Girl, Grandmother's bed), delivery(Little Ring Girl, tea), question(Little Ring Girl, Joe), eat(Joe, Little Ring Girl).

which correspond, respectively, to the Grimm and Perrault AT 333 variants, rephrased to display the names of characters and objects given by the user.

Our plan recognition algorithm employs a tree structure, which we call generalized plan suffix tree. Based on the suffix tree commonly used for string pattern matching [START_REF] Gusfield | Algorithms on Strings, Trees, and Sequences[END_REF], this trie-like data structure contains all suffixes p k of each plan in P. If a plan P i has a sequence of events 𝑝 = 𝑒 1 𝑒 2 ⋯ 𝑒 𝑘 ⋯ 𝑒 𝑁 , then 𝑝 𝑘 = 𝑒 𝑘 𝑒 𝑘+1 ⋯ 𝑒 𝑁 is the suffix of p that starts at position k (we have dropped the index i of the expressions p and p k for the sake of simplicity). In a generalized plan suffix tree S, edges are labeled with the parameterized plan events that belong to each suffix p k , and the leaves point to the complete plans ending in p k . Each suffix is padded with a terminal symbol $i that uniquely signals the complete plan in the leaf node. Figure 1 shows an example of generalized plan suffix tree generated for the plan sequences The process of searching for plans that match a given partial plan T , expressed as a sequence of input terms, is straightforward: starting from the root node, the algorithm sequentially matches T against the parameterized plan events on the edges of the tree, in chronological but not necessarily consecutive order, instantiating the event variables and proceeding until all input terms are matched and a leaf node is reached. If more solutions are requested, a backtracking procedure tries to find alternative paths matching T. The search process produces a set of complete plans G, with the event variables instantiated with the values appearing in the input partial plan or, for events not present in the partial plan, with the default values defined in the library.

After generating G through plan-recognition, the system allows users to apply the semiotic relations (involving connection, similarity, unfolding, and opposition) and explore other variants of same or different types. The process of searching for variants uses the semiotic relations specified in the library of typical plans to create a link between a g i in G and its semiotically related variants. When instantiating one such variant v i , the event variables of v i are instantiated according to the characters and objects that play important roles in the baseline story g i . Characters playing roles in g i that also exist in v i , assume the same role in the variant. For roles that only exist in v i , the user is asked to name the characters who would fulfil such roles.

Following the g i →v i links taken from the examples of section 4, the user gains a chance to reinterpret the g i AT 333 variant, in view of aspects highlighted in the semiotically related v i : 1. the wolf's villainy complemented by a rescue act (AT 123); 2. As illustrated in Figure 2, our system supports two dramatization modalities: text and comics. The former uses the original literary rendition of the matched typical plan as a template and represents the generated stories in text format. The latter offers a storyboard-like comic strip representation, where each story event gains a graphical illustration and a short sentence description. In the illustrations, the scene compositing automatic process takes into account the specific object carried by each character and the correct movement directions. More details on the generation of comic strips can be found in our previous work on interactive comics [START_REF] Lima | Non-Branching Interactive Comics[END_REF]. similarly predefined genre, readers have a fair chance to find a given story in a treatment as congenial as possible to their tastes and personality profile. Moreover, prospective amateur authors may feel inspired to put together new variants of their own after seeing how variants can derive from the type and motif interactions that we associate with semiotic relations. They would learn how new stories can arise from episodes of existing stories, through a process, respectively, of concatenation, analogous substitution, expansion into finer grained actions, or radical reversal.

Computer-based libraries, such as we described, should then constitute a vital first step in this direction. In special, by also representing the stories as plans, in the form of sequences of terms denoting the story events (cf. the second paragraph of section 5), we effectively started to combine the two approaches mentioned in the Introduction, namely Aarne-Thompson's types and motifs and Proppian functions, and provided a bridge to our previously developed Logtell prototypes [START_REF] Ciarlini | Modeling interactive storytelling genres as application domains[END_REF][START_REF] Ciarlini | A logic-based tool for interactive generation and dramatization of stories[END_REF][START_REF] Furtado | Constructing Libraries of Typical Plans[END_REF][START_REF] Karlsson | Conceptual Model and System for Genre-Focused Interactive Storytelling[END_REF].

We expect that our analysis of variants, stimulated by further research efforts in the line of computational narratology, may contribute to the design of semi-automatic methods for supporting interactive plot composition, to be usefully incorporated into digital storytelling systems.

  P 1 = {go(A, B), meet(A, C), kill(C, A)} and P 2 = {tell(A, B, C), meet(A, C), go(A, D)}.

Fig. 1 .

 1 Fig. 1. Generalized plan suffix tree for P 1 = {go(A, B), meet(A, C), kill(C, A)} and P 2 = {tell(A, B, C), meet(A, C), go(A, D)}..

  his belly replaced by ugly man and his bag (AT 311B*); 3. the girl's gesture of picking needles expanded to the wider scope of a disenchantment ritual (AT 437); 4. girl and werewolf with reversed roles of villain and victim (AT 449).

Fig. 2 .

 2 Fig. 2. Plan recognition system: (a) main user interface; (b) comics dramatization; (c) a variant for story 1; and (d) text dramatization.

http://www-di.inf.puc-rio.br/~furtado/LRRH_texts.pdf

http://www.gutenberg.org/files/1974/1974-h/1974-h.htm

Acknowledgements

This work was partially supported by CNPq (National Council for Scientific and Technological Development, linked to the Ministry of Science, Technology, and Innovation), CAPES (Coordination for the Improvement of Higher Education Personnel), FINEP (Brazilian Innovation Agency), ICAD/VisionLab (PUC-Rio), and Oi Futuro Institute.


Vojtech Cerny

Filip Dechterenko
email: filip.dechterenko@gmail.com

Rogue-like Games as a Playground for Artificial Intelligence -Evolutionary Approach

Keywords: artificial intelligence, computer games, evolutionary algorithms, rogue-like

Rogue-likes are difficult computer RPG games set in a procedurally generated environment. Attempts have been made at playing these algorithmically, but few of them succeeded. In this paper, we present a platform for developing artificial intelligence (AI) and creating procedural content generators (PCGs) for a rogue-like game Desktop Dungeons. As an example, we employ evolutionary algorithms to recombine greedy strategies for the game. The resulting AI plays the game better than a hand-designed greedy strategy and similarly well to a mediocre player -winning the game 72% of the time. The platform may be used for additional research leading to improving rogue-like games and general PCGs.

Introduction

Rogue-like games, as a branch of the RPG genre, have existed for a long time. They descend from the 1980 game "Rogue" and some old examples, such as NetHack (1987), are played even to this day. Many more of these games are made every year, and their popularity is apparent.

A rogue-like is a single-player, turn-based, highly difficult RPG game, featuring a randomized environment and permanent death 1 . The player takes the role of a hero, who enters the game's environment (often a dungeon) with a very difficult goal. Achieving the goal requires a lot of skill, game experience and perhaps a little bit of luck.

Such a game, bordering between RPG and puzzle genres, is challenging for artificial intelligence (AI) to play. One often needs to balance between being reactive (dealing with current problems) and proactive (planning towards the main goal). Attempts at solving rogue-likes by AI have been previously made [START_REF] Mauldin | ROG-O-MATIC: a belligerent expert system[END_REF][START_REF]Tactical Amulet Extraction Bot (TAEB) -Other Bots[END_REF][START_REF] Krajíček | NetHack Bot Framework. Master's thesis[END_REF], usually using a set of hand-coded rules as basic reasoning, and being to some extent successful.

On the other hand, the quality of a rogue-like can heavily depend on its procedural content generator (PCG), which usually creates the whole environment.

Procedural generation [START_REF] Shaker | Procedural Content Generation in Games: A Textbook and an Overview of Current Research[END_REF] has been used in many kinds of games [START_REF] Togelius | Search-based procedural content generation: A taxonomy and survey[END_REF][START_REF] Hendrikx | Procedural content generation for games: A survey[END_REF], and thus, the call for high-quality PCG is clear [START_REF] Liapis | Towards a Generic Method of Evaluating Game Levels[END_REF]. However, evaluating the PCG brings issues [START_REF] Dahlskog | A Comparative Evaluation of Procedural Level Generators in the Mario AI Framework[END_REF][START_REF] Smith | The Seven Deadly Sins of PCG Research[END_REF], such as how to balance between the criteria of high quality and high variability.

But a connection can be made to the former -we could conveniently use the PCG to evaluate the artificial player and similarly, use the AI to evaluate the content generator. The latter may also lead to personalized PCGs (creating content for a specific kind of players) [START_REF] Shaker | Towards Automatic Personalized Content Generation for Platform Games[END_REF].

In this paper, we present a platform for developing AI and PCG for a rogue-like game Desktop Dungeons [11]. It is intended as an alternative to other used AI or PCG platforms, such as the Super Mario AI Benchmark [START_REF] Karakovskiy | The Mario AI Benchmark and Competitions[END_REF] or SpelunkBots [START_REF] Scales | SpelunkBots API -An AI Toolset for Spelunky[END_REF]. AI platforms have even been created for a few rogue-like games, most notably NetHack [START_REF]Tactical Amulet Extraction Bot (TAEB) -Other Bots[END_REF][START_REF] Krajíček | NetHack Bot Framework. Master's thesis[END_REF]. However, Desktop Dungeons has some characteristics making it easier to use than the other. Deterministic actions and short play times help the AI, while small dungeon size simplifies the work of a PCG.

And as such, more experimental and resource demanding approaches may be tried. The platform could also aid other kinds of research or teaching AI, as some people create their own example games for this purpose [START_REF] Russell | Artificial Intelligence: A Modern Approach[END_REF]Chapter 21.2], where Desktop Dungeons could be used instead.

The outline of this paper is as follows. First, we introduce the game to the reader, then we proceed to describe our platform, and finally, we will show how to use it to create a good artificial rogue-like player using evolutionary algorithms.

Desktop Dungeons Description

Desktop Dungeons by QCF Design [11] is a single-player computer RPG game that exhibits typical rogue-like features. The player is tasked with entering a dungeon full of monsters and, through careful manipulation and experience gain, slaying the boss (the biggest monster).

Disclaimer: The following explanation is slightly simplified. More thorough and complete rules can be found at the Desktop Dungeons wiki page [START_REF]Desktop Dungeons -DDwiki[END_REF].

Dungeon

The dungeon is a 20 × 20 grid viewed from the top. The grid cells may contain monsters, items, glyphs, or the hero (player). Every such object, except for the hero, is static -does not move2 . Only a 3 × 3 square around the hero is revealed in the beginning, and the rest must be explored by moving the hero next to it. Screenshot of the dungeon early in the game can be seen in Fig. 1.

Hero

The hero is the player-controlled character in the dungeon and holds a set of values. Namely: health, mana, attack power, the number of health/mana potions, and his spell glyphs. The hero can also perform a variety of actions. He can attack a monster, explore unrevealed parts of the dungeon, pick up items and glyphs, cast spells or convert glyphs into bonuses.

Exploring

Unrevealed grid cells can be explored by moving the hero next to them (at least diagonally). Not only does exploration reveal what lies underneath for the rest of the game, but it also serves one additional purpose -restoring health and mana. Every square explored will restore health equal to the hero's level and 1 mana. This means that the dungeon itself is a scarce resource that has to be managed wisely. It shall be noted, though, that monsters heal also when hero explores, so this cannot be used to gain an edge over damaged monsters.

Combat

Whenever the hero bumps into a monster, a combat exchange happens. The higher level combatant strikes first (monster strikes first when tied). The first attacker reduces his opponent's health by exactly his attack power. The other attacker, if alive, then does the same. No other action causes any monster to attack the hero.

Items

Several kinds of items can be found lying on the ground. These comprise of a Health Powerup, Mana Powerup, Attack Powerup, Health Potion and a Mana Potion. These increase the hero's health, mana, attack power, and amount of health and mana potions respectively.

Glyphs

Spell glyphs are special items that each allow the hero to cast one kind of spell for it's mana cost. The hero starts with no glyphs, and can find them lying in the dungeon. Common spells include a Fireball spell, that directly deals damage to a monster (without it retaliating), and a Kill Protect spell, that saves the hero from the next killing blow.

Additionally, a spell glyph can be converted to a racial bonus -a specific bonus depending on the hero's race. These are generally small stat increases or an extra potion. The spell cannot be cast anymore, so the hero should only convert glyphs he has little use for.

Hero Races and Classes

Before entering the dungeon, the player chooses a race (Human, Elf, etc.) and a class (Warrior, Wizard, etc.) of his hero. The race determines only the reward for converting a glyph, but classes can modify the game in a completely unique way.

Other

The game has a few other unmentioned mechanics. The player can enter special "challenge" dungeons, he can find altars and shops in the dungeon, but all that is far beyond the basics we'll need for our demonstration. As mentioned, more can be found at the Desktop Dungeons wiki [START_REF]Desktop Dungeons -DDwiki[END_REF].

AI Platform

Desktop Dungeons has two parameters rarely seen in other similar games. Every action in the game is deterministic3 (the only unknown is the unrevealed part of the dungeon) and the game is limited to 20 × 20 grid cells and never extends beyond. These may allow for better and more efficient AI solutions, and may be advantageously utilized when using search techniques, planning, evaluating fitness functions, etc.

On the other hand, Desktop Dungeons is a very interesting environment for AI. It is complex, difficult, and as such can show usefulness of various approaches. Achieving short-term and long-term goals must be balanced, and thus, simple approaches tend to not do well, and must be specifically adjusted for the task. Not much research has been done on solving rogue-like games altogether, only recently was a famous, classic title of this genre -NetHack -beaten by AI [START_REF] Krajíček | NetHack Bot Framework. Master's thesis[END_REF].

From the perspective of a PCG, Desktop Dungeons is similarly interesting. The size of the dungeon is very limited, so attention to detail should be paid. If one has an artificial player, the PCG could use him as a measure of quality, even at runtime, to produce only the levels the artificial player found enjoyable or challenging. This is why we created a programming interface (API) to Desktop Dungeons, together with a Java framework for easy AI and PCG prototyping and implementation. We used the alpha version of Desktop Dungeons, because it is more direct, contains less story content and player progress features, runs in a browser, and the main gameplay is essentially the same as in the full version.

The API is a modified part of the game code that can connect to another application, such as our framework, via a WebSocket (TCP) protocol and provide access to the game by sending and receiving messages. A diagram of the API usage is portrayed in Fig. 2. The framework allows the user to focus on high-level programming, and have the technical details hidden from him. It efficiently keeps track of the dungeon elements, and provides full game simulation, assisting any search techniques and heuristics that might be desired. The developed artificial players can be tested against the default PCG of the game, which has the advantage of being designed to provide challenging levels for human players, or one can generate the dungeon on his own and submit it to the game. Intermediate ways can also be employed, such as editing the dungeons generated by the game's PCG to e.g. adjust the difficulty or reduce the complexity of the game.

The framework is completely open-source and its repository can be found at https://bitbucket.org/woitee/desktopdungeons-java-framework.

Evolutionary Approach

To demonstrate the possibilities of the Desktop Dungeons API, we have implemented an evolutionary algorithm (EA) [START_REF] Mitchell | An Introduction to Genetic Algorithms[END_REF] to fine-tune greedy AI. A general explanation of EAs is, however, out of the scope of this paper.

Simple Greedy Algorithm

The original greedy algorithm was a simple strategy for each moment of the game. It is best described by a list of actions, ordered by priority.

1. Try picking up an item. 2. Try killing a monster (prefer strongest). 3. Explore.

The hero tries to perform the highest rated applicable action, and when none exists, the run ends. Killing the monster was attempted by just simulating attacks, fireballs and drinking potions until one of the participants died. If successful, the sequence of actions was acted out. This can be modeled as a similar list of priority actions:

1. Try casting the Fireball spell. 2. Try attacking. 3. Try drinking a potion. Some actions have parameters, e.g. how many potions is the hero allowed to use against a certain level of monster. These were set intuitively and tuned by trial and error.

This algorithm has yielded good results. Given enough time (weeks, tens of thousands of runs), this simple AI actually managed to luck out and kill the boss. This was very surprising, we thought the game would be much harder to beat, even with chance on our side. It was probably caused by the AI always calculating how to kill every monster it sees, which is tedious and error-prone for human players to do.

Design of the Evolution

We used two ordered lists of elementary strategies in the greedy approach, but we hand-designed them and probably have not done that optimally. This would become increasingly more difficult, had we added more strategies to the list. We'll solve this by using evolutionary algorithms.

We'll call the strategies used to select actions in the game maingame strategies and the strategies used when trying to kill monsters attack strategies. Each strategy has preconditions (e.g. places to explore exists) and may have parameters. We used as many strategies as we could think of, which resulted in a total of 7 maingame strategies and 13 attack strategies.

The evolutionary algorithm was tasked with ordering both lists of strategies, and setting their parameters. It should be emphasized, that this is far from an easy task. Small imperfections in the strategy settings accumulate over the run, and thus only the very refined individuals have some chance of slaying the final boss.

However, the design makes the AI ignore some features of the game. It doesn't buy items in shops nor does it worship any gods. These mechanics are nevertheless quite advanced, and should not be needed to win the basic setting of the game. Using them can have back-biting effects if done improperly, so we just decided to ignore them to keep the complexity low.

On a side note, this design is to a certain extent similar to linear genetic programming [START_REF] Brameier | Linear Genetic Programming[END_REF].

Fitness Function

Several criteria could be considered when designing the fitness function. An easy solution would be to use the game's score, which is awarded after every run. However, the score takes into account some attributes that do not directly contribute towards winning the game, e.g. awarding bonuses for low completion time, or never dropping below 20% of health.

We inspired ourselves by the game's scoring, but simplified it. Our basic fitness function evaluates the game's state at the end of the run and looks like this:

f itness = 10 • xp + 150 • healthpotions + 75 • manapotions + health
The main contributor is the total gained XP (experience points, good runs get awarded over a hundred), and additionally, we slightly reward leftover health and potions. We take these values from three runs and add them together. Three runs are too few to have low variance on subsequent evaluations, but it yields far better results than evaluating only one run, and more runs than three would just take too much time to complete.

If the AI manages to kill the boss in any of the runs, we triple the fitness value of that run. This may look a little over the top, but slaying the final monster is very difficult, and if one of the individuals is capable of doing so, we want to spread it's gene in the population. Note, that we don't expect our AI to kill the boss reliably, 5-10% chance is more what we are aiming for.

We have tried a variety of fitness functions, taking into account other properties of the game state and with different weights. For a very long time, the performance of the bots was similiar to the hand-designed greedy strategy. But, by analyzing more of the game, we have constructed roughly the fitness function above and the performance has hugely improved.

The improvement lies in the observation of how can the bots improve during the course of evolution. Strong bots in the early state will probably just use objectively good strategies, and not make complete blunders in strategy priorities, such as exploring the whole level before trying to kill anything. This should already make them capable of killing quite a few monsters. Then, the bots can improve and fine-tune their settings, to use less and less resources (mainly potions) to kill as many monsters as possible. And towards the late state of evolution, the bots can play the game so effectively, they may still have enough potions and other resources to kill the final boss and beat the game. The current fitness function supports this improvement, because the fitness values of the hypothetical bots in subsequent stages of evolution continuously rises.

After implementation, this was exactly the course the bots have evolved through. Note, that saving at least a few potions for the final boss fight is basically a necessary condition for success.

Genetic Operators

Priorities of the strategies are represented by floating point numbers in the [0, 1] interval. Together with the strategy's parameter values, we can encode it as just a few floating point numbers, integers and booleans.

This representation allows us to use classical operators like one-/two-point crossovers and small change mutations. And they make good sense and work, but they are not necessarily optimal, and after some trial and error, we have Fig. 3. Graphs describing the fitnesses of the evolution for each of our class-race settings. The three curves describe the total best fitness ever encountered, the best fitnesses averaged over all runs and the mean fitnesses averaged over all runs. The vertical line indicates the point, where the AI has killed the boss and won the game at least once in three attempts. This fitness value is different for each setting, since some raceclass combinations can gain more hitpoints or health potions than other, both of which directly increase their fitness (see Section 4.3).

started using a weighted average operator to crossover the priorities for better performance.

The AI evolved with these settings were just a little too greedy, often using all their potions in the early game, and even though they advanced far, they basically had no chance of beating the final boss. These strategies found quite a strong local optimum of the fitness, and we wanted to slightly punish them for it. We did so in two ways. Firstly, we rewarded leftover potions in our fitness value calculation, and secondly, a smart mutation was added, that modifies a few individuals from the population to not use potions to kill monsters of lower level than 5. After some balancing, this has shown itself to be effective.

Mating and natural selection was done by simple roulette, i.e. individuals were chosen with probability proportional to their fitness. This creates a rather low selection pressure, and together with a large enough number of individuals in a generation, the evolution should explore a large portion of the candidate space and tune the strategies finely.

Results

After experimentation, we settled to do final runs with a population of 100 individuals, evolving through 30 generations. The population seemed large enough to be exploring the field well, and the generations sufficient for the population to converge. We ran the EA on 4 computers for a week, with a different combination of hero class and race on each computer. The result was a total of 62 runs, every hero class and race setting completed a minimum of 12 full runs. A single evaluation of an individual takes about 2 seconds, and a single whole run finishes in about 14 hours (intel i5-3470 at 3.2GHz, 4GB RAM, two instances in parallel).

The data of the results contain a lot of good strategies, their qualities can be seen in Fig. 3. Every combination of hero race and class managed to beat the boss at least once, and the strongest evolved individual kills the boss 72% of time (averaged over 10000 runs). This is definitely more than we expected. Note that no AI can slay the boss 100% of the time, since the game's default PCG sometimes creates an obviously unbeatable level (e.g. all exits from the starting room surrounded by high level monsters).

The evolved strategies also vary from each other. Different race and class combinations employ different strategies, but variance occurs even among runs of the same configuration. This shows that Desktop Dungeons can be played in several ways, and that different initial settings require different approaches to be used, which makes the game more interesting for a human. The different success rates of the configurations can also be used as a hint which race-class combinations are more difficult to play than others, either to balance them in the game design, or to recommend the easier ones to a beginner.

Conclusion

We present a platform for creating AI and PCG for the rogue-like game Desktop Dungeons. As a demonstration, we created an artificial player by an EA adjusting greedy algorithms. This AI functioned better than the hand-made greedy algorithm, winning the game roughly three quarters of the time, compared to a winrate of much less than 1%, and being as successful as an average human player.

This shows that the game's original PCG worked quite well, not generating a great abundance of impossible levels, yet still providing a good challenge.

A lot of research is possible with this platform. AI could be improved by using more complex EAs, or created from scratch using any techniques, such as search, planning and others. The PCG may be improved to e.g. create more various challenges for the player, adjust difficulty for stronger/weaker players or reduce the number of levels that are impossible to win. For evaluating the PCG, we could advantageously utilize the AI, and note some statistics, such as winrate, how often are different strategies employed or number of steps to solve a level. A combination of these would then create a rating function.

Also, it would be very interesting to keep improving both the artificial player and the PCG iteratively by each other.

Fig. 1 .

 1 Fig. 1. Screenshot of the dungeon, showing the hero, monsters, and an item (a health potion). The dark areas are the unexplored parts of the dungeon.

Fig. 2 .

 2 Fig.2. The API, as a part of the game, connects to an application using a WebSockets protocol and provides access to the game by receiving and sending messages.

The game offers no save/load features, it is always replayed from beginning to end.

Some spells and effects move monsters, but that is quite uncommon and can be ignored for our purpose.

Some rare effects have probabilistic outcomes, but with a proper game setting, this may be completely ignored.


Augusto Baffa
email: abaffa@inf.puc-rio.br

Marcus Poggi
email: poggi@inf.puc-rio.br

Bruno Feijó
email: bfeijo@inf.puc-rio.br

Adaptive Automated Storytelling based on Audience Response

Keywords: Social Interaction, Group decision making, Model of Emotions, Automated Storytelling, Audience model, Optimization application End

To tell a story, the storyteller uses all his/her skills to entertain an audience. This task not only relies on the act of telling a story, but also on the ability to understand reactions of the audience during the telling of the story. A well-trained storyteller knows whether the audience is bored or enjoying the show just by observing the spectators and adapts the story to please the audience. In this work, we propose a methodology to create tailored stories to an audience based on personality traits and preferences of each individual. As an audience may be composed of individuals with similar or mixed preferences, it is necessary to consider a middle ground solution based on the individual options. In addition, individuals may have some kind of relationship with others that influence their decisions. The proposed model addresses all steps in the quest to please the audience. It infers what the preferences are, computes the scenes reward for all individuals, estimates their choices independently and in group, and allows Interactive Storytelling systems to find the story that maximizes the expected audience reward.

Introduction

Selecting the best events of a story to please the audience is a difficult task. It requires continued observation of the spectators. It is also necessary to understand the preferences of each individual in order to ensure that the story is able to entertain and engage as many spectators as possible.

Whereas an interactive story is non-linear, because it has several possible branches until the end, the objective of a storyteller is to find out the best ones considering an audience profile, the dramatic tension and the emotions aroused on the individuals.

Empathy is the psychological ability to feel what another person would feel if you were experiencing the same situation. It is a way to understand feelings and emotions, looking in an objective and rational way what another person feels [START_REF] Davis | A multidimensional approach to individual differences in empathy[END_REF]. Based on the empathy, it is possible to learn what the audience likes. This allows selecting similar future events along the story and, therefore, to maximize the audience rating.

The proposed method aims to select the best sequence of scenes to a given audience, trying to maximize the acceptance of the story and reduce drop outs. The idea behind this approach is to identify whether the audience is really in tune with the story that is being shown. A well-trained storyteller can realize if the audience is bored or enjoying the story (or presentation) just looking at the spectators.

During story writing, an author can define dramatic curves to describe emotions of each scene. These dramatic curves define how the scene should be played, its screenshot, lighting and soundtrack. After the current scene, each new one has a new dramatic curve which adds to the context of the story [START_REF] Araujo | Verification of temporal constraints in continuous time on nondeterministic stories[END_REF].

The reactions of the audience are related to the dramatic curves of the scene. If the audience readings of the emotions are similar to the emotions defined by the dramatic context, then there is a connection (empathy) between audience and what is being watched [START_REF] Jones | The actor and the observer: Divergent perceptions of the causes of behavior[END_REF][START_REF] Kallias | Individual Differences and the Psychology of Film Preferences[END_REF].

In this work, we propose a methodology to create tailored stories to an audience based on personality traits and preferences of each individual. The global objective is to maximize the expected audience reward. This involves considering a middle ground solution based on the individual options of the audience group. In addition, individuals may have some kind of relationship with others, characterizing an interaction among the audience and ultimately influencing their decisions.

The proposed model addresses all steps in the quest to please the audience. It infers what the preferences are, computes the scenes reward for all individuals, estimates their choices independently and in group, and allows Interactive Storytelling systems to find the story that maximizes the expected audience reward.

This paper is organized as follows. Section 2 discusses on emotion modeling and on its application to audience characterization and behavior expectation. The following section presents the main aspects of automated storytelling. Section 4 is dedicated to modeling the expected audience reward maximization. The interaction of individuals in the audience is the object of section 5. Section 6 proposes a heuristic to solve the optimization model in section 5. Analysis and conclusions are drawn in the last section.

Emotions and Audience

During film screening, the audience gets emotionally involved with the story. Individuals in the audience reacts according to their preferences. When an individual enjoys what is staged, he/she tends to reflect the same emotions that are proposed by the story. The greater the identification between the individual and the story, the greater are the emotions experienced.

As an audience can be composed of individuals who have very different preferences, it is important that the storyteller identifies a middle ground to please as many as possible. Knowing some personality traits of each individual helps to get the story closer to the audience.

Model of Emotions

The emotional notation used to describe the scenes of a story is based on the model of "basic emotions" proposed by Robert Plutchik [START_REF] Plutchik | The emotions: Facts, theories, and a new model[END_REF][START_REF] Plutchik | A general psychoevolutionary theory of emotions[END_REF]. Plutchik's model is based on Psychoevolutionary theory. It assumes that emotions are biologically primitive and that they evolved in order to improve animal reproductive capacity. Each of the basic emotions demonstrates a high survival behavior, such as the fear that inspires the fight-or-flight. In Plutchik's approach, the basic emotions are represented by a three-dimensional circumplex model where emotional words were plotted based on similarity [START_REF] Plutchik | The nature of emotions[END_REF]. Plutchik's model is often used in computer science in different versions, for tasks such as affective human-computer interaction or sentiment analysis. It is one of the most influential approaches for classifying emotional responses in general [START_REF] Ellsworth | Appraisal processes in emotion[END_REF].

Each sector of the circle represents an intensity level for each basic emotion: the first intensity is low, the second is normal and the third intensity is high. In each level, there are specific names according to the intensity of the emotion, for example: serenity at low intensity is similar to joy and ecstasy in a higher intensity of the instance.

Plutchik defines that basic emotions can be combined in pairs to produce complex emotions. These combinations are classified in four groups: Primary Dyads (experienced often), Secondary Dyads (sometimes perceived), Tertiary Dyads (rare) and opposite Dyads (cannot be combined).

Primary Dyads are obtained by combining adjacent emotions, e.g., Joy + Trust = Love. The Secondary Dyads are obtained by combining emotions that are two axes distant, for example, Joy + Fear = Excitement. The Tertiary Dyads are obtained by combining emotions that are three axes distant, for example, Joy + Surprise = Doom. The opposite Dyads are on the same axis but on opposite sides, for example, Joy and Sorrow cannot be combined, or cannot occur simultaneously [START_REF] Plutchik | The nature of emotions[END_REF]. Complex Emotions -Primaries Dyads:

antecipation + joy = optimism joy + trust = love trust + fear = submission fear + surprise = awe surprise + sadness = disappointment sadness + disgust = remorse disgust + anger = contempt anger + antecipation = aggression This model assumes that there are eight primary emotions: Joy, Anticipation, Trust, Fear, Disgust, Anger, Surprise and Sadness. It is possible to adapt the Plutchik's model within a structure of 4-axis of emotions [START_REF] Rodrigues | Um Sistema de Geração de Expressões Faciais Dinâmicas em Animações Faciais 3D com Processamento de Fala[END_REF][START_REF] Araujo | Verification of temporal constraints in continuous time on nondeterministic stories[END_REF] as shown in Figure 1.

The Plutchik's model describes a punctual emotion and it is used to represent an individual or a scene in a specific moment. In order to describe the emotions of a scene, the Plutchik's model is converted to a time series of emotions called "dramatic curve". The dramatic curve describes the sequence of emotions in a scene in an interval of one second per point. It follows the structure of 4-axis based on Plutchik's wheel and maps the variation of events in a story.

Audience Model

In Psychology, there are many models to map and define an individual's personality traits. One of the most used is called Big Five or Five Factor Model, developed by Ernest Tupes and Raymond Christal in 1961 [START_REF] Tupes | Recurrent personality factors based on trait ratings[END_REF]. This model was forgotten until achieving notoriety in the early 1980s [START_REF] Rich | User modeling via stereotypes[END_REF] and defines a personality through the five factors based on a linguistic analysis. It is also known by the acronym O.C.E.A.N. that refers to five personality traits.

The personality of an individual is analyzed and defined throughout answers to a questionnaire that must be completed and verified by factor analysis. Responses are converted to values that define one of the factors on a scale of 0 to 100. In this work only two traits are used to create the individual profile: Openness to experience O ∈ [0, 1] and Agreeableness (Sociability) A ∈ [0, 1]. Each personality trait is described as follows:

Openness to experience The openness reflects how much an individual likes and seeks for new experiences. Individuals high in openness are motivated to seek new experiences and to engage in self-examination. In a different way, closed individuals are more comfortable with familiar and traditional experiences. They generally do not depart from the comfort zone. [START_REF] John | The big-five trait taxonomy: History, measurement, and theoretical perspectives[END_REF] Agreeableness (Sociability) Agreeableness reflects how much an individual like and try to please others. Individuals high on agreeableness are perceived as kind, warm and cooperative. They tend to demonstrate higher empathy levels and believe that most people are decent, honest and reliable. On the other hand, individuals low on agreeableness are generally less concerned with others' wellbeing and demonstrate less empathy. They tend to be manipulative in their social relationships and more likely to compete than to cooperate. [START_REF] John | The big-five trait taxonomy: History, measurement, and theoretical perspectives[END_REF]

Concept of Empathy

According to Davis [START_REF] Davis | A multidimensional approach to individual differences in empathy[END_REF], "empathy" is defined by spontaneous attempts to adopt the perspectives of other people and to see things from their point of view. Individuals who share higher empathy levels tend to have similar preferences and do things together. In this work, he proposes a scale of "empathy" to measure the tendency of an individual to identify himself with characters in movies, novels, plays and other fictional situations. Also, the emotional influence of a movie to the viewer can be considered "empathy". It is possible to identify a personality based on the relationship between an individual and his favorite movies and books. Furthermore, it is possible to suggest new books or movies just knowing the personality of an individual [START_REF] Kallias | Individual Differences and the Psychology of Film Preferences[END_REF]. Following these ideas, it is possible to relate empathy to a rating index. During an exhibition, if the viewer is enjoying what he is watching, there is an empathy between the show and the spectator. This information is used to predict what the spectator likes and dislikes.

Interactive Storytelling

In recent years, there have been some efforts to build storytelling systems in which authors and audience engage in a collaborative experience of creating the story. Furthermore, the convergence between video games and film-making can give freedom to the player's experience and generate tailored stories to a spectator. Interactive Storytelling are applications which simulates a digital storyteller. It transforms the narrative from a linear to a dialectical form, creating new stories based on audience by monitoring their reactions, interactions or suggestions for new events to the story. [START_REF] Karlsson | Applying a planrecognition/plan-generation paradigm to interactive storytelling[END_REF] The proposed approach of a storytelling system should be able to generate different stories adapted to each audience, based on previously computed sequence of events and knowledge of preferences of each individual on the audience.

Story Model

A story is a single sequence of connected events which represents a narrative. The narrative context may be organized as a decision tree to define different possibilities of endings. During the story writing, the author can define many different ends or sequences to each event (or scene). Each ending option forwards to a new scene and then to new ending options, until story ends. For example, Figure 2 To evaluate the proposed model and algorithm, the tests are performed using an event tree corresponding to a non-linear variation of the fairy tale Little Red Cap [START_REF] Araujo | Verification of temporal constraints in continuous time on nondeterministic stories[END_REF]. The event tree is described in Table 1 and presented in Figure 3. In some events, there are possibilities of branches such as the moment when the girl meets the wolf in the forest. The original story is represented by the sequence of events π : {EV1, EV2, EV3, EV4, EV5, EV7, EV8, EV9, EV10, EV17, EV11, EV13, EV15}. Each scene describes what occurs to the characters and the story, and also has an emotional description called "dramatic curve". The dramatic curves are based on Plutchik's wheel of emotions and describes how emotions should manifest during the scene. Soundtracks, screenshots and lighting can be chosen based on the dramatic curves.

The sequence of scenes tells the story, describes a complete emotional curve and "tags" the story as "genre".

Modeling Emotions to Events

During the story writing, the scenes are described as a tree of events. Each event in the tree is associated to a dramatic curve and must be modeled containing the following information:

-Name: unique name for the event (each event has a unique name); -Text: describes what happens during the event; -Dramatic Curves: emotional time series presented on figure 1: Joy/Sadness (axis x), Fear/Anger (axis y), Surprise/Anticipation (axis w) and Trust/Disgust (axis z).

The Tree of events has different paths, connecting to different future events, until the end of the story. When the story is told, it is selected a single branch to each event. The dramatic curves representing the original story sequence of events are demonstrated in Figure 4. Table 2 illustrates the emotions involved in each of 20 events present in the story. Considering the personality traits, individuals who score high in "openness" like a greater variety of genres (often opposed) in comparison to others. Individuals low in "openness" generally prefer the same things and choose the same genres. In this case, there are less options to please individuals low in "openness".

The task of selecting a scene that pleases a person is to find which of the possible options approaches their preferences. The task selection becomes difficult when we try to find the best option that would please the most people in a group. In this case, it is necessary to consider other information about individuals as "agreeableness" and empathy between individuals. Individuals who score high in "agreeableness" try to approach quickly the choices of others and have more patience than others. They sometimes prefer to accept other preferences and decisions just to please them all.

The empathy indicates the level in a relationship that individuals have. For example, when two people like each other, they may want to do things together, thus it indicates a higher level of empathy. In the other hand, people who want avoid each other have a low level of empathy in this relationship. Generally, individuals in a relationship with high empathy choose the same options or a middle ground.

Maximizing the Audience

Given a tree of events, each ending (a leaf of the tree) uniquely determines a sequence of scenes or the story to tell. This corresponds to the path from the root of the tree to ending leaf. Finding the most rewardable path for a given audience amounts to evaluate an utility function that captures how the audience feels rewarded by the scenes and also the choices the audience makes at each branch. The tree of event can be represented as follows:

Let S be the finite set of events (scenes) of a story. Let also Γ + (s) be a subset of S containing the child nodes of node s. The utility function is given by E(s, i) which determines the expected value of state s for individual i and represents a measure of similarity between 0 and 1. Finally, let P rob(s l-1 , s l , i) be the probability with which individual i chooses state s l to follow state s l-1 . Remark that the probabilities P rob(s l-1 , s l , i)) must add one for each branch and for each individual, since one branch must be selected on each state.

Consider now a sequence of states π = {s 0 , . . . , s k } that represents a path from the root to a leaf. The proposed model evaluates path by computing its expected utility which is given by the expression:

f (π) = k l=1 i∈I (E(s l , i).P rob(s l-1 , s l , i)) (1)
Let R(s) be the maximum expected utility that can be obtained starting from state s. The following recursion determines R(s). where p(s) is the predecessor of s. By computing R(s 0 ), the root's reward, an optimal sequence π * , with maximum expected reward, can be retrieved in a straightforward way. We conclude the model by proposing an evaluation for the individual probabilities of choice on each story branch. This is done by assuming this probability is proportional to the expected individual reward of the branches. This leads to the expression:

R(s) =            i∈I (E(s, i).P rob(p(s), s, i)) + max s ∈Γ + (s) R (
P rob(s, s , i) = IR(s , i) s ∈Γ + (s) IR(s , i) (3)
where IR(s, i) is the expected reward at state s for individual i, which is given by:

IR(s, i) = E(s, i) + max s ∈Γ + (s)
IR(s , i).P rob(s, s , i)

This model allows determining the best sequence of scenes for and audience provided there is no interaction within the audience. We address this case in the following section.

To create tailored stories for an individual it is just necessary to check what he/she likes most, based on its own probabilities but when an individual participates of a group he/she needs to deal a middle ground. The dynamic of choosing the best story to an audience is based on the fact that the individuals will watch the same story, share a minimal intimacy and want spend sometime together. In a similar way, it is possible to say that they are trying to watch television and need to choose a television program that please the entire group. During this interaction, each individual tries to convince others about his preferences. Some individuals may agree with these suggestions based on the relationship they share, but others may introduce some limits. After some rounds, some individuals give in and accept to approach other preferences [START_REF] Tortosa | Interpersonal effects of emotion in a multi-round trust game[END_REF]. The decision of accepting others' do not eliminate personal preferences but introduce a new aspect to the options. According to the proposed model some options that originally are not attractive will be chosen because of the induced social reward imposed by the probability function of choosing it. This means that for some individuals, it is better to keep the group together than take advantage of their preference. Furthermore, as explained in section 2.2, individuals high in "openness" do not care so much about their own preferences because they like to experiment new possibilities. They may be convinced by friends or relatives and will tend to support their preferences.

In order to model the audience behavior, we propose an algorithm based on a spring-mass system. Consider that all preferences are modeled by the real coordinate space ( 2 ) and each individual of the audience is represented by a point positioned on his preferences. Each point (individual) is connected to n springs (where n is the number of individuals). A spring is connected to its original position and other n-1 springs are connected to the other points. Then, we have a total of n×(n+1) 2 springs. The objective function aims to approach each point, considering the constraints of the springs. Each spring is modeled based on the individual personality traits and relationship levels between them.

Let K ii = (1 -O i ), be the openness level of each individual i and K ij = A ij be the agreeableness level for each pair of individuals i and j. In this model, we are assuming that "agreeableness" may also be influenced by the relationship between i and j and it is possible to describe an individual resistance by others' preferences. After some experiments, we realize that it is possible to start an audience from A ij = A i and fine tuning A ij after some rounds.

Given e ij ∈ [-1, 1], the empathy level between each pair of individuals, and x 0 i , the original position in space for each individual i, let d 0 ij = x 0 i -x 0 j be the original distance between individuals and let L ij = (1 -e ij ).d 0 ij be a weighted empathy level. The objective of the following model is to find the final positions x i minimizing the distances between the individuals d ij , weighted by their agreeableness level K ij and considering L ij . min i∈A j∈J:i =j

K ij .(d ij -L ij ) 2 + i∈I K ii .d 2 ii (5)
subject to

d ij = x i -x j ∀i, j ∈ A, i = j (6)
d ii = x i -x 0 i ∀i ∈ A (7)
The constraints (6) link the distance variables d ij with the coordinate variables x i and x j when individuals i and j are different. Constraints [START_REF] Kallias | Individual Differences and the Psychology of Film Preferences[END_REF] are used to obtain the distance d ii which each individual has moved from its original position. Figure 5 describes the operation of the Spring-mass system with 2 individuals.

Since this model is not linear, it is not possible to use a linear solver to obtain the optimal solution. Therefore, we use a meta-heuristic approach based on simulated annealing to obtain a good approximate solution. The simulated annealing algorithm is presented in Section 6. 6 Solving the audience interaction model Simulated annealing is a meta-heuristic for optimization problems based on thermodynamics. Given a large solution space, it solves the optimization problem by finding a good solution near the global optimum [START_REF] Dréo | Metaheuristics for Hard Optimization: Methods and Case Studies[END_REF]. At each iteration of the algorithm, it changes the current solution within a neighborhood and considers the new solution as the current one if there is any improvement on the objective function or, if there is no improvement, it may consider it based on a randomized criteria.

The neighborhood used for the audience problem is defined by all possible movements of each individual in other to minimize the distances between all individuals according to spring constraints. Let -→ a be the current position of individual a, -→ b be the referential position based on all relationships between the individuals and s a be the "agreeableness" level of the personality of individual a. It is possible to calculate the step of a movement δ x for individual a using equations ( 8)- [START_REF] Plutchik | A general psychoevolutionary theory of emotions[END_REF].

- → b =   n j=1 a j y .e ij e ij , n j=1 a j x .e ij e ij   (8)
α = (b y -a y )/(b x -a x ) (9)
δ x = -s 2 a /α 2 + 1 a x > b x , s 2 a /α 2 + 1 otherwise (10)
The final position after moving the individual a is given by -→ a f inal as follows:

- → a f inal = (δ x + a x , δ x .α + a y ) (11)
The simulated annealing method is shown in Algorithm 1. The algorithm receives as input an initial solution S 0 , limits on the number of iterations M , on the number of solution movements per iteration P and on the number of solution improvements per iteration L. During its initialization, the iteration counter starts with 1, the best solution S starts equal to S 0 and the current temperature T is obtained from the function InitialT emp(), which returns a value based on the instance being solved. On each iteration, the best solution is changed within the neighborhood by function Change(S) and the improvement is calculated on ∆F i . This solution is then accepted or not as the new best solution and, at the end of the iteration, the temperature is updated given the factor α.

Algorithm 1 Simulated Annealing procedure SA(S0, M, P, L) j ← 1 S ← S0 T ← InitialT emp() repeat i ← 1 nSuccess ← 0 repeat Si = Change(S) ∆Fi = f (Si) -f (S) if (∆Fi = 0)||(exp(-∆Fi/T ) > Rand()) then S ← Si nSuccess ← nSuccess + 1 end if i ← i + 1 until (nSuccess = L)||(i > P ) T ← α.T j ← j + 1 until (nSuccess = 0)||(j > M ) P rint(S) end procedure
The proposed methodology was initially applied on students of our graduate program in order to evaluate the emotional characteristics of the individuals. This allowed a positive view of techniques and validated the initial hypothesis. Then, the final experiments were conducted using 20 generated audience1 instances with 20 individuals each on instances divided in three groups: 8 entirely mixed audiences with 60% of individuals supporting an emotion, 8 audiences with similar individuals and 4 mixed audiences with one opinion leader. The opinion leader instances were generated by describing an influential individual to others2 . This starting point permitted a qualitative evaluation of the application of the whole methodology based on discussion among the ones involved in the experience.

The resulting story endings for each audience are presented on Table 3. Stories generated to mixed audiences before interaction considered average preferences while stories generated after interaction (SA) tend to select the majority preference. The proposed Red Cap story has a natural tendency for a Sadness + Angry endings (EV12, EV18, EV19, EV20) since there are more final events of these emotional features than Joy + Angry endings (EV15 only). However, the proposed method was able to select expected story endings according to the audience preferences. Also, the preliminary evaluation of an opinion leader suggested there is a sound basis for results that may effectively converge to the choice of audience rewarding paths. Next step amounts to carrying out more thorough and relevant experiments which requires not only larger groups but also stories that truly draws the audience. In this preliminary analysis, an evaluation of the model parameters also allowed to conclude that their determination may lead to conditions which can represent a wide range of groups, thus leading to a representative model.

Our evaluation is that the proposed methodology can still incorporate more factors of emotional behavior, group interaction and storytelling aspects. The goal is to experiment thoroughly on a wide spectrum of stories and audiences.

Fig. 1 .

 1 Fig. 1. Simplified 4-axis structure -families of emotions

Fig. 2 .

 2 Fig. 2. Story as a Decision Tree

Fig. 3 .

 3 Fig. 3. Little Red-Cap story as a decision tree

Fig. 4 .

 4 Fig. 4. Dramatic Curves of Little Red-Cap original sequence of Scenes

  s ) i∈I (E(s, i).P rob(p(s), s, i)), for s a leaf i∈I E(s, i) + max s ∈Γ + (s) R(s ), for s the root (2)

Fig. 5 .

 5 Fig. 5. Spring-mass example with 2 individuals

Table 1 .

 1 Little Red-Cap story events

	Event	Description	Event	Description
	EV1	Mother warns the girl	EV11	Girl escapes
	EV2	Girl leaves her home	EV12	Wolf devours Girl
	EV3	Girl is in the forest	EV13	Girl finds the Hunter
	EV4	Girl finds the wolf in the forest EV14	Wolf gets the girl
	EV5	Wolf cheats the girl	EV15 Hunter kills the wolf and saves Grandma
	EV6	Wolf attacks the girl	EV16	Wolf kills the Hunter
	EV7	Wolf goes to Grandma's house EV17 Wolf attacks the Girl at Grandma's house
	EV8	Wolf swallows Grandma	EV18	Wolf eats the Girl after his escape
	EV9	Girl arrives at Grandma's house EV19 Wolf devours the Girl in Grandma's house
	EV10	Girl speaks with Wolf	EV20	Wolf devours the Girl in the Forest

Table 2 .

 2 Dramatic Curves for Little Red-Cap eventsEvery time an individual likes a scene or story, he/she tells what he/she likes and what does not. This information is then used to analyze and determine which are the individual preferences. The information from the dramatic curve indicates the emotion that has been liked and is used to classify genres. The favorite scenes of an individual are used to ascertain which are the emotions that stand out. The genres of the stories are set primarily by the main emotions of the scenes. Throughout readings of emotions which stand out, it is possible to know which genres the individual prefers and which scenes of a new story are emotionally similar.

	Event	Emotion	Event	Emotion
	EV1	Joy + Surprise	EV11	Joy + Anticipation
	EV2	Joy + Anticipation	EV12	Sadness + Angry
	EV3	Trust + Surprise	EV13	Joy + Anticipation
	EV4	Fear + Surprise	EV14	Angry + Disgust
	EV5	Fear + Trust	EV15	Joy + Angry
	EV6	Angry + Anticipation EV16	Sadness + Surprise
	EV7	Sadness + Anticipation EV17 Angry + Anticipation
	EV8	Angry + Surprise	EV18	Sadness + Angry
	EV9	Joy + Fear	EV19	Sadness + Angry
	EV10	Trust + Surprise	EV20	Sadness + Angry
	3.3 Uncovering audience preferences

Table 3 .

 3 Selected Story Endings for Audiences

	Emotion	Mixed	SA	Similar	Opinion Leader
	Trust	EV 12	EV 15	EV 15 short	-
	Surprise	EV 12	EV 12	EV 20 short	-
	Joy	EV 12	EV 15	EV 15	EV 15
	Sadness	EV 12	EV 12	EV 12 short	EV 12
	Disgust	EV 12	EV 12	EV 20 short	-
	Anger	EV 12	EV 18	EV 18	EV 18
	Fear	EV 12	EV 12	EV 12	EV 12
	Anticipation	EV 12	EV 15	EV 15 short	-

An audience is a set of individuals

We considered that the empathy from others to an opinion leader is near to 1 but his/her empathy to others is low

Acknowledgements

This work was partially supported by CNPq (National Council for Scientific and Technological Development, linked to the Ministry of Science, Technology, and Innovation), CAPES (Coordination for the Improvement of Higher Education Personnel, linked to the Ministry of Education), FINEP (Brazilian Innovation Agency), and ICAD/VisionLab (PUC-Rio).