Thomas Tregel
email: thomas.tregel@kom.tu-darmstadt.de

Felix Leber
email: felix.leber@stud.tu-darmstadt.de

Stefan Göbel
email: stefan.goebel@kom.tu-darmstadt.de

Incentivise me: Smartphone-based mobility detection for pervasive Games

Keywords: Mobility, Mobility detection, Pervasive games, Context Detection

The ubiquity of smartphones with a plethora of sensors made it possible to develop context-based pervasive games playable by most people without any additional equipment required. However, popular games like Pokémon GO or Zombie, Run! show the minimal influence context has on the gameplay besides the user's position. Furthermore, in the context of movement and mobility the distinction between different modes of transport becomes necessary both for security and for environmental reasons. In this paper we present a system that uses location information combined with public transport data to detect different types of mobility, especially vehicular mobility and uses this information for adaptation purposes in a prototypical location-based game. Our evaluation shows that our system can be used to reliably differentiate between public transport and driving a car within minutes and is able to adapt content in pervasive games according to the context surrounding the current user.

Introduction

With the rise of smartphones, the demand for mobile games has also increased as a result of increased mobile Internet use. As a result, pervasive games that mix the real and fictional world have become more popular. In addition to larger screens, more and more sensors such as GPS receivers or magnetometers are being installed in smartphones. With these sensors it is possible to collect more data, so-called context information, about the user and his environment. One game that uses one of these data types is Pokémon GO, with which pervasive games have experienced a great hype. In 2016, Pokémon GO was the most widely used mobile game, which led to a positive change in behaviour for many users [START_REF] Althoff | Influence of Pokémon Go on physical activity: study and implications[END_REF].

However, current pervasive games use little to no data about the players' movement, besides velocity threshold based approaches to detection potential vehicle usage. The aim of this paper is to detect the players' mode of transportation and individualize the content of pervasive games accordingly by collecting and analysing contextual information based on smartphones. This is especially important for serious games in the areas of eco-friendly behaviour.

Smartphone-based context detection for mobile games

Contextual information related to pervasive games has been defined differently by several researchers. ( 2) and ( 3) present two well-known definitions for context with the latter being that that: "Context is any information that can be used to characterize the situation of an entity."

Current pervasive games already include different context types exemplarily described in the scenario of Pokémon Go. Besides the player position as a main game input, the time context is used as a day-night cycle for both gameplay reasons and security concerns. Weather is detected via many different online services for the user's position, for which open API can be used (4). This weather information both influences game mechanics and notifies the user about upcoming weather changes.

Another information of particular interest with regard to pervasive games is the current activity of the user. This includes, walking, cycling, driving a car or the like. This is done by using sensor-fusion with e.g. the accelerometer, gyroscope, magnetometer, GPS, WiFi, pedometer and others [START_REF] Su | Activity Recognition with Smartphone Sensors[END_REF]. Current games however only use a velocitybased static threshold to differentiate between valid movement and motorized travel.

The differentiation between certain activities is particularly difficult when sensor data hardly differs. In order to distinguish between different modes of vehicular transportation additional logic is required, which we will investigate in the next Section.

Differentiating between different modes of transportation

The detection of the player's current activity plays an important role in context detection. Data when the user is in a vehicle is quite similar, which makes it difficult to tell whether the user is sitting in the bus or in his own car. We have examined multiple approaches regarding IMU-based modality detection in our previous work [START_REF] Tregel | Examining approaches for mobility detection through Smartphone Sensors[END_REF]. The downside here lies within the distinction between different vehicular modes of transportation, as accelerometer sensor data is influenced by many other aspects like road quality or vehicle suspension.

Enriching a vehicle discrimination by location data can be promising as shown by Thiagarajan et al. who have presented three distringuishing characteristics [START_REF] Thiagarajan | Cooperative Transit Tracking using Smart-phones[END_REF]:

 a car is significantly faster outside rush hours than a bus on its route.  the mean distance between consecutive stops is significantly greater for cars during rush hour.  drivers do not tend to stop at stops. Stenneth et al. use routes of trains and bus stops to identify the means of transport [START_REF] Stenneth | Transportation Mode Detection using Mobile Phones and GIS Information[END_REF]. In addition to that Montoya et al. also use timetables and live information of busses (7; 9). Location-based approaches need to incorporate mechanisms that handle variance in location sensor accuracy [START_REF] Grimes | Global Positioning System Standard Positioning Service Performance Standard[END_REF].

However, using position information can lead to significant errors or jumps, especially in large cities. Additionally, bus and train routes often overlap, so a lot of data is needed to distinguish between specific routes.

In Germany the availability of public transport data is very limited, due to the division into different transport associations, which usually do not provide open APIs. However, public transport stop information can usually be downloaded directly from the transport associations [START_REF][END_REF] or obtained via OpenStreetMap.

Detecting public transport and game adaptation

As investigated in (6) using a common API is reliable when detecting basic activities, excluding different modes of transportation. We have evaluated the Google Awareness Transition API [START_REF] Google | Google Awareness API[END_REF], which detected the current activity (running, driving in a vehicle or standstill) in 45 tests (15 per activity) within a maximum of two minutes. Especially the change to running was very fast. It was also noticeable that it makes no difference which activity is changed from, but only to which. An overview of the results of the tests is given in Figure 1. Thereby our approach starts as soon as the user is recognized by a common API as being in a vehicle. As noted in Section 2.1 it is important that all stops are detected. Therefore, we need to determine the minimum sensing frequency for location updates, as stops can be primarily be detected due to no change in player position.

For 30 journeys with bus and train, we have determined ten seconds to be the minimum downtime, which leads us to a required location update every five seconds according to the Nyquist-theorem. Due to higher basic update frequencies in locationbased games, this could easily be increased without additional battery consumption.

At each position, route information is determined for the player's surrounding, which includes nearby routes and stops using our OpenStreetMap approach, which we extended by a public transport module. This information is then stored to reduce the number of consecutive network calls.

■ Standing ■ Running ■ Vehicle Detection time in seconds
After obtaining all required information, we check to see whether a possible route is nearby. The procedure is as follows:

(1) A standstill is assumed at a speed of less than one meter per second. In this case, the determined route information is first searched for stops at a distance of δ=50 meters (step 2). If the speed is higher, only nearby routes are searched (step 4). ( 2) If a stop is found, it is saved. If there is the possibility to query departure times, the departures for all stops found will be retrieved (step 3). If no stops were found, the system also searches for nearby routes (step 4). (3) If a departure is found within the time interval [-2 min, 10 min], the departure is also saved. Ten minutes were selected here due to the ten-minute guarantee of the RMV [38]. The two minutes were selected because the times in the timetable are often departure times, and therefore a short standing time is also taken into account.

The values of the possible routes are then updated (step 5). (4) The system searches for routes at a distance of δ=50 meters around the current position. If one or more routes are found, they will be saved. If no routes are found within a time window of 2 minutes (represents 12 location updates with a frequency of 1 update per 10 seconds), the algorithm terminates and outputs the activity Driving a car. Then the values of the possible routes are updated (step 5). ( 5) Each route that has been detected at least once in the vicinity is assigned a value.

This value for a route r is calculated according to the following formula:

𝑠𝑐𝑜𝑟𝑒 𝑟 = 𝜔 𝑝 * 𝑝𝑜𝑠 𝑟 + 𝜔 𝑟 * 𝑠𝑡𝑜𝑝𝑠 𝑟 + 𝜔 𝑑 * 𝑑𝑒𝑝𝑎𝑟𝑡𝑢𝑟𝑒𝑠 𝑟 #𝑝𝑜𝑠
For this formula the weights 𝜔 𝑝 = 1, 𝜔 𝑟 = 3 and 𝜔 𝑑 = 7 have been chosen initially. 𝑝𝑜𝑠 𝑟 represents the number of positions within the vicinity of route r. Additionally, 𝑠𝑡𝑜𝑝𝑠 𝑟 is the amount of correctly detected stops for route r and 𝑑𝑒𝑝𝑎𝑟𝑡𝑢𝑟𝑒𝑠 𝑟 the amount of valid departures within the given time window of step 3 for successfully detected stops. This sum is then divided by the number of positions processed so far, so that a value is generated as a function of time.

If a route's value succeeds a give threshold τ = 1 the value and route information of the highest scoring route is returned and the respective route is detected (tram, bus, train, etc.). In case all scores are below threshold τ the algorithm returns Driving a car.

In addition, active Bluetooth connections and Wi-Fi information are analysed to influence the decision-making process. In case an active Bluetooth connection with a car is detected Driving a car is returned. Similarly, when the smartphone is connected to public transport Wi-Fi public transport becomes more likely.

Game adaptation based on mode of transportation

Game content adaptation for public transport is especially interesting as, given an attractive reward, these could change the player's mobility behaviour. These can be implemented using a quest-based system, similar to quests current location-based games already provide. One exemplary quest for public transport would be to Use your local public transport for a full workweek in both directions (two times per day). As we further want to encourage users to use available public transport options we modify the allowed radius of interaction. This allows users when e.g. sitting in a tram to interact with content on a larger distance than when going by car. Because trams and buses do not take detours this is both required and convenient to allow enough content to be interacted with when going on a pre-determined route.

Evaluation

In our evaluation we want to investigate the accuracy of our public transport detection approach and look at the feasibility and outcome of adaptation approaches for content selection and quest generation. The system was implemented within our GEOVis framework first presented in [START_REF] Tregel | Geodata Classification for Automatic Content Creation in Location-based Games[END_REF].

4.1

Public transport detection

In order to investigate the temporal aspect of the detection with regard to the means of transport, 20 tests were carried out, half in a car and half in a public transport. The aim was to determine with what accuracy the correct activity was detected and after what time it was valid. The results show that the correct activity or route is detected in 85% of cases during the journey. On average, the correct activity and route is detected after 179 seconds, having faster detection times for cars.

For 50% of journeys, the algorithm started detecting an incorrect activity or route during the journey before it was correctly detected. This happened on average after 65 seconds, which can be interpreted as a required time until a stable prediction can be done. It is also noticeable that at least one 'wrong' stop was detected in all car tests where a wrong route was detected during the journey (50%). This happened especially when stops were near traffic lights and the car had to stop. Due to the higher value of stops in the algorithm, this route was detected as wrong first. For this reason, the correct activity was not detected correctly during a journey. The public transport tests, where no correct route was detected, showed that the journey times were too short. Both consisted of only one stop and a maximum of two minutes of travel time. In both cases the correct activity, but not the correct route, was detected because several routes were driving this route.

Stops and departures of the specific routes were detected properly for real stops and departures which were within the defined time window.

Conclusion

In this paper we presented a concept for context-based adaptation in pervasive games focusing on differentiating between different modes of transportation, which is recognized by a combination of smartphone sensors and openly available APIs. An algorithm was designed to improve the recognition of the user's activity, in particular the distinction between car and bus or train.

The in-game content is customized by player's respective movement context, by both providing him quests that further encourage public transport usage and improve his interaction radius, that allows the access to more content in the vicinity. Our results show that the recognition can be improved with existing departure data of the public local traffic.

Figure 1 :

 1 Figure 1: Detection times of Google Transition API.

Figure 2 :

 2 Figure 2: Public transport detection algorithm in a diagram.

Acknowledgment

The research presented in this paper was partially funded by the LOEWE initiative (Hessen, Germany) within the research project "Infrastruktur -Design -Gesellschaft" as project mo.de.


Oto A L Cunha

Joimar B Gonçalves
email: joimarbgf@gmail.com

Victor T Sarinho
email: vsarinho@uefs.br

Quimi-Crush: A Digital Game for the Teaching of Inorganic Chemistry

Keywords: Chemistry teaching, Educational game, Tile-matching puzzle

Traditional teaching strategies have become increasingly unattractive and demotivating for students in general. Students of inorganic chemistry usually have difficulties in learning the atomicity of the elements during the composition of the chemical compounds, as well as in the understanding of the characteristics and functions of such compounds. This work presents Quimi-Crush, a tile-matching digital puzzle capable of stimulating students to learn and participate in the understanding of inorganic chemistry concepts in a playful and fun way.

Introduction

The teaching of chemistry provides students a basic knowledge on specific phenomena in nature [START_REF] De Fátima Rocha | Formação de Professores: interação Universidade[END_REF]. However traditional strategies of chemistry teaching are often seen as discouraging by students, since such strategies are based on memorization of formulas and calculations making the learning process less enjoyable [START_REF] Oliveira | Desenvolvendo jogos didáticos para o ensino de química[END_REF].

As a result, more dynamic and attractive new approaches need to be incorporated into the chemistry learning and teaching process, in order to create a friendly and welcoming environment to promote a playful approach to learn inorganic chemistry [START_REF] De Barros | Jogos no ensino de quımica: um estado da arte sobre a revista quımica nova na escola[END_REF].

Regarding serious games, "they combine the entertainment value of games with additional objectives such as players acquiring knowledge or skills, receiving guidance and feedback on tasks to perform, or contributing partial solutions to problems" [START_REF] Dalpiaz | Games for requirements engineers: Analysis and directions[END_REF]. They are "intentionally designed to attract, engage, and retain (even addict) players by applying psychology principles" [START_REF] Dalpiaz | Games for requirements engineers: Analysis and directions[END_REF], whose impact for educational purposes has received considerable attention.

This paper presents Quimi-Crush, a tile-matching puzzle serious game capable of stimulating apprenticeship and participation of high school students in inorganic chemistry learning-teaching process.

The Quimi-Crush Game

Quimi-Crush is similar to famous match-3 puzzle games, like "Fat Princess -Piece of Cake" [START_REF]One Loop Games LLC: Fat princess: Piece of cake[END_REF] and "Candy Crush -Soda Saga" [START_REF] Dockterman | Candy crush saga: The science behind our addiction[END_REF] (Fig. 1). One of the main objectives in "Candy Crush -Soda Saga" is making a certain quantity of combinations containing objects that look like soda bottles. In order to reach that aim it is necessary to keep combining "candies" to create opportunities to release the "soda bottles" objects. In "Fat Princess-Piece of Cake", the player must defend himself from waves of enemies that increase according the progress of the player in the game. The player team has characters that perform attack and defense actions from the combination of pieces on the board. Regarding Quimi-Crush, the player controls actions of a hero by combining chemical components in order to perform attacks on the villain, and the player character suffers a damage when compounds that are not oxides are combined. In principle, the spot where combinations occur has a six by six dimension, initially containing five chemical elements: Hydrogen (H), Carbon (C), Sodium (Na), Nitrogen (N) and Oxygen (O) (Fig. 2).

The dynamics of the game consists of turns, in which player searches for basic chemical elements that are able to combine with each other (Hydrogen, Carbon, Sodium, Nitrogen and Oxygen) according to a catalog of combinations (Fig. 3). For each combination of basic elements that does not generate an oxide, the hero of the game will take damage in the turn and consequently lose a heart. When the combination of components produces an oxide, the hero will attack and the villain will lose a heart.

If the player manages to combine enough oxides to destroy all hearts of the enemy, he wins the match. The player loses the match when the number of simple combinations that do not generate oxides is greater than the total number of hero hearts. In case of victory, a new level is unlocked, otherwise, the player will have to try to play the same level again or return to the initial menu.

If the player delays to find a possible item to be combined, the game signals a possible match that can be performed, but this combination will not be necessarily the best for the victory. However, if there are really no combinations, the component area is scrambled again. An introductory tutorial is also provided by the game, thus facilitating the explanation of the basic dynamics of the game itself.

Conclusions and Future Work

Quimi-Crush presents an innovative approach to the teaching of inorganic chemistry. Through the blending of rules and goals of tile-matching puzzle games known to young audiences, the game is able to dynamically exercise the knowledge of atomicity of proposed base chemical elements. As a result, there is an interesting didactic resource in the teaching of inorganic chemistry, which can easily be extended to different inorganic chemical compounds and other known chemistry concepts.

As future work, besides extra improvements and corrections to become more aesthetically attractive for the players, it is intended to evaluate the game us- ability in the process of teaching public high school students. For this, the game will be applied in both the mobile version and in public school PCs in the region.

Mobile and desktop versions of the game, together with developed source code, will also be available at https://github.com/lenda-uefs after the necessary fixes and adjustments.

Fig. 1 .

 1 Fig. 1. Images from the games "Candy Crush -Soda Sag" (a) and "Fat Princess -Piece of Cake" (b).

Fig. 2 .

 2 Fig. 2. Game play screen where chemical combinations occur.

Fig. 3 .

 3 Fig. 3. Combination catalogs of basic elements applied in the game.


Bernard Cheng
email: chengb@gmail.com

T C Nicholas Graham

Playing with Persiflage: the Impact of Free-Form Dialogue on the Play of Computer Role Playing Games

Keywords:

Digital games struggle to blend compelling narrative with interactivity. For example, computer role-playing games (CRPGs) allow players the freedom to explore an open world, yet limit their interaction with the world's inhabitants to selecting from pre-determined dialogue choices. In this paper, we explore how players behave when truly freeform dialogue with non-player characters (NPCs) is supported. In the novel Persiflage game, players converse with NPCs using speech. NPCs are in turn voiced by a human, allowing truly free-form conversation. Through a study of five groups playing the game, we show how players converse, interact, and play using natural language.

Introduction

In computer role-playing games (CRPGs), players enter a virtual world in which they can take on different personas and engage in novel experiences. Players can adopt roles as diverse as a renaissance assassin [START_REF]Ubisoft: Assassin's Creed II[END_REF], a dragon-slaying adventurer [START_REF]The Elder Scrolls V: Skyrim[END_REF], or the commander of a spaceship [5]. Games enable fantasies, allowing players to immerse themselves in new worlds and situations. A large part of these fantasies is the stories that games embody.

In CRPGs, however, players lack the ability to carry out open-ended conversations with the inhabitants of the game world [START_REF] Murray | Hamlet on the Holodeck[END_REF]. This restricts the player's ability to use dialogue to learn about the world or to pursue interests beyond those anticipated by the game's designers. Digital games restrict players' interaction with characters they encounter in the world, allowing only what Lessard terms "dialogue trees of pre-defined utterances" [START_REF] Lessard | Designing natural-language game conversations[END_REF]. Players are presented with a series of dialogue choices from which they must choose, limiting their ability to truly guide a conversation.

In this paper, we explore the effect of permitting truly open-ended conversation with non-player characters in computer RPGs. Since current AI techniques do not allow automation of open-ended conversation, we introduce "voiced NPCs", non-player characters whose dialogue is provided by a human being.

We illustrate this idea in Persiflage, a CRPG where players are represented as avatars in a graphical virtual world, using a traditional game controller to explore this world. Unlike traditional CRPGs, however, when talking with NPCs, players speak out loud using unrestricted natural language. Players are unrestricted in what topics they raise with NPCs, and in how they express themselves.

This paper shows the effect of open-ended conversation on play of a CRPG. We explore how players present themselves verbally and engage in storytelling when given the ability to talk in their own voices. To investigate these questions, we conducted a study where five groups of three people were recruited to play through a murder mystery plot in Persiflage, where their utterances were recorded and then coded. The groups were split into two players and one orchestrator, whose primary job was to give voice to non-player characters. We found that players engaged with the game's goals and used open-ended dialogue to advance the story's plot, sometimes in unexpected ways. Players did not constrain themselves to the game's mediaeval setting, instead opting to import their own humour and anachronisms. We found that permitting open-ended conversation in a CRPG led to vibrant, humorous, and light-hearted interaction, while remaining grounded in the game's setting and goals.

We distinguish this approach of enhancing a CRPG with voiced NPCs from the use of a game master (GM) in traditional pen-and-paper role playing games such as Dungeons and Dragons [START_REF] Gygax | Dungeons and Dragons[END_REF]. Our approach extends CRPGs to have more intelligent NPCs without otherwise changing the presentation or interaction affordances of the game. Voiced NPCs give a hint of how CRPGs would be played if the artificial intelligence directing the behaviour of NPCs were powerful enough to support open-ended conversation using natural language. In contrast, GMs take the much broader approach of narrating and guiding the game as a whole.

In this paper, we first review approaches to improving the flexibility of dialogue in digital games, then describe Persiflage, our game incorporating voiced NPCs, and finally present our study of open-ended conversation in CRPGs.

Related Work

Murray describes the idealized vehicle for interactive narrative as Star Trek's fictional Holodeck [START_REF] Murray | Hamlet on the Holodeck[END_REF], where users assume the role of characters in a holographic environment and interact using natural dialogue. Current digital games are far from this ideal, limiting players' interaction with characters in the game to selecting among choices that have been provided by the game's designer.

Clicking through dialogue trees to advance conversations is a form of hypertext fiction. A story is created through a combination of fragments (or lexia) [START_REF] Ryan | From narrative games to playable stories: Towards a poetics of interactive narrative[END_REF]. Players make decisions by selecting which story-block to follow next. These blocks and the corresponding available choices must be carefully arranged to preserve the logical and temporal consistency of the resulting narrative arc [START_REF] Tanenbaum | Authoring tangible interactive narratives using cognitive hyperlinks[END_REF]. While the player has agency around the choice of which story-block to select, their choices are limited to the content created prior to delivery, and players lack any true sense of authorship over the resulting creation [START_REF] Willerton | Structure problems in hypertext mysteries[END_REF]. This is the state of the art found in popular computer RPGs such as Bethesda's The Elder Scrolls 5: Skyrim [START_REF]The Elder Scrolls V: Skyrim[END_REF], or Bioware's Mass Effect series [5]. Some early explorations have permitted players to interact with games using natural language. In Facade, players speak with AI agents using typed dialogue [START_REF] Mateas | Procedural authorship: A case-study of the interactive drama Façade[END_REF]. In a study of three natural language games, Lessard concludes that players have a large degree of freedom to explore humorous interactions if they are willing to forgive the errors and limited knowledge of parsers [START_REF] Lessard | Designing natural-language game conversations[END_REF]. While artificial intelligence has helped with personalization of narratives, current techniques are still far from allowing open-ended dialogues supporting compelling narrative progression [START_REF] Mateas | Procedural authorship: A case-study of the interactive drama Façade[END_REF].

Another approach is game orchestration, where a human directs the operation of the game at runtime. Crabtree et al., for example, use orchestrators to guide the narrative in large-scale pervasive multiplayer game [START_REF] Crabtree | The cooperative work of gaming: Orchestrating a mobile SMS game[END_REF]; similarly, in Egyptian Oracle, a puppeteer controls an avatar that interacts with an audience in an augmented reality performance [START_REF] Gillam | The Egyptian Oracle project: Ancient ceremony in augmented reality[END_REF]. In game sketching, a designer manipulates the progression of a game in real-time, allowing testing of game ideas before they are fully implemented [START_REF] Agustin | Game sketching[END_REF]. For example, in Raptor, an orchestrator uses a tabletop interface to manipulate the content of a game world, while a play tester plays in real time [START_REF] Smith | Raptor: Sketching games with a tabletop computer[END_REF]. Allison et al. used an orchestrator to implement a helper in the game Minecraft, to aid and advise players in building tasks [START_REF] Allison | How Players Speak to an Intelligent Game Character Using Natural Language Messages[END_REF]. In these approaches, the orchestrator's role is to enhance the experience of players, allowing open-ended interaction that would not be possible with AI alone.

In multiplayer games, voice interaction is often used by players to rapidly coordinate intense encounters where typing would be too slow [START_REF] Allison | Word Play: A History of Voice Interaction in Digital Games[END_REF][START_REF] Carter | Player Identity Dissonance and Voice Interaction in Games[END_REF]. During less frantic episodes, players use voice channels to banter and maintain a social environment in game. However, Wadley et al. find that not all players are comfortable with the increased social presence attendant to broadcasting one's voice online, especially amongst relative strangers [START_REF] Wadley | Voice in Virtual Worlds: The Design, Use, and Influence of Voice Chat in Online Play[END_REF], and tended not to speak in character while using voice technology.

There has been little study into how open-ended dialogue affects play. There has, however, been research into how players interact in traditional pen-andpaper role playing games, such as Dungeons and Dragons [START_REF] Gygax | Dungeons and Dragons[END_REF]. Unlike CRPGs, pen-and-paper RPGs are based on imagination; the game master (GM) describes verbally what players see, and acts out the role of characters they encounter. This affords the open-ended interaction that is absent from digital role-playing games. The voiced NPCs introduced in this paper are best viewed as an enhancement of CRPGs rather than an attempt to digitize the pen-and-paper RPG experience. Nonetheless, it is helpful to review how players interact in pen-and-paper RPGs. Tychsen discusses that control lies mainly with the GM, who has conceived a story from prepared material. The GM is able to retain control whilst providing an illusion of choice to the players. This is likened to the situation in CRPGs where player choice is limited by the predetermined dialogue structure. Although a GM can impose their will on players, there is always some degree of improvisation and change in plans as the game progresses.

Open-Ended Dialogue in Persiflage

We designed Persiflage to explore the effect of open-ended dialogue in digital games. Persiflage is a computer role-playing game where the non-player characters (NPCs) are voiced by a human being. These orchestrators use a special interface to move and animate NPCs and to play the NPC's part in conversations with players. This removes the restrictions of rigid conversational systems, allowing players to express themselves as they choose. Persiflage allows us to address our primary research question of, how do players in fact choose to express themselves when such freedom is given?

As shown in Figure 1, Left, two players each control an avatar using a standard game controller. Players are collocated, sharing a single display. Players view a cartoon-style fantasy village containing streets and buildings (Figure 1, Right). Players move their avatars using the joysticks on their game controllers, and interact with NPCs and objects using buttons on the controller. Various NPC villagers are located around the fictional village of Northaven. To advance the plot, the players must talk to the villagers to gather information.

An orchestrator sits in another room (figure 2, Right), and uses a special interface to control the NPCs (figure 2, Left). The orchestrator can draw a path for an NPC to follow, and can trigger NPC animations (e.g., talking, waving) using buttons on the interface. For context, the orchestrator sees an inset view of the players' view (top-right of figure 2, Right). Players and orchestrators speak to voice their characters. The conversation is transmitted between the two rooms using voice over IP. The orchestrator's voice plays through the speakers on the television, helping to convey that the NPC is talking. Players are aware that a human orchestrator is voicing the NPCs.

Persiflage is a murder mystery with story-driven gameplay where players need to question, coerce, and beg the NPCs for information and clues. The players take on the role of investigators that have arrived in Northaven in pursuit of a fugitive named "Helena". They must interact with residents of the townthe voiced NPCs -to find and bring Helena to justice. As the players explore and interact with the townsfolk, they collaboratively build a story with the orchestrator. Northaven is a mediaeval townscape consisting of homes, farms, a church, an inn and a market square. Six NPCs inhabit the town.

Digital Northaven

The townscape is still and lifeless until the orchestrator starts moving the NPCs and responding to the players in conversation. The items in game are deliberately generic and can take on different meanings under different situations. A vial of red liquid might be an ominous sample of blood or a potent truth serum; a bound tome can become Helena's diary or a priest's lost bible. We leave it up to the orchestrator and players to build their own stories using the digital pieces.

The opportunity for open-ended interaction poses a challenge to both the orchestrator and players. The players are invited to be inventive in the portrayal of their characters. The orchestrator on the other hand must be ready to react to unforeseen player requests.

Players can engage NPCs in conversation by walking up to them and pressing the "A" button on their controller. The interface zooms to focus on the NPC's face. The orchestrator can activate talking animations, giving the impression that when the orchestrator talks, their voice is coming from the NPC's mouth.

None of the dialogue in game is scripted outside of notes that the orchestrator has prepared. Players are initially aware only of the fact that they are searching for a fugitive named Helena, and must invent all their conversation on the fly. The orchestrator must also improvise dialogue during play in response to the players' questioning. This allows players to express their creativity without being restrained by a script.

Study Method

To explore how players and orchestrators approach open-ended conversations in CRPGs, we performed an exploratory study where we observed play of five groups of three participants. We recruited these participants from the university community using an advertisement posted on Facebook. Participants were asked to form their own groups of three members and to choose who would play the roles of players and orchestrator. Participants ranged from 19 to 27 years in age with a mean of 23 years. 6 participants were female, and 9 male.

The orchestrator attended a training session before the study to become familiar with the story and the orchestrator interface. The orchestrator was presented with a document outlining the murder mystery story: the two players play detectives in pursuit of "Helena", a woman wanted for an unspecified crime. The chase has led them to the town of Northaven where some of the villagers have conspired to fake her death. The document briefly described each of six NPCs, to help the orchestrator in creating dialogue for the NPCs during the game. The orchestrator was shown how to move NPCs, activate their animations, engage in conversation with players, and create, move, and destroy items (figure 2). This training session occurred the day before the actual play session.

Play Session

At the beginning of the play session, the game and its user interface were demonstrated to the players, including how to move, enter, and exit a conversation with an NPC, and pick up, drop, and trade items. They were then allowed to experiment and familiarize themselves with the controls, until they reported that they were comfortable. This took approximately five minutes. The players were given the premise of the game, and instructed to solve the mystery as best they could. The play session was allowed to run to its conclusion or for thirty minutes, whichever occurred first.

The session was recorded with two separate video cameras, one for the players and one for the orchestrator. The Skype call between the parties and a screen capture of the orchestrator's screen were recorded. A transcript of their speech during the session was taken from the recordings and coded for interesting behaviours. The transcribed dialogue was split into utterances on which we employed an open coding approach [START_REF] Strauss | Basics of Qualitative Research: Techniques and Procedures[END_REF] to identify interesting speech patterns.

Results and Analysis

Persiflage was created to enable natural language interactions in CRPGs, enabling open-ended dialogue between players and NPCs. These results show how players and orchestrators exercise this freedom of interaction. We coded players' choice of language, indicating how players and orchestrators engage with and invest themselves in this type of gameplay, and the content of their conversation, showing the players' engagement with the game's goals and objectives. The following sections present these codes.

How Players Present Themselves Verbally

In Persiflage, the opportunity to use natural language in conversation with NPCs allows players to adopt richer personalities in the game. The style and language of players' conversation indicates their attitude toward the gameplay. Just as film and theatre might be comedic or dramatic, the atmosphere of a game can vary as well. By looking at how players and the orchestrator chose to present their characters, we can see the atmosphere and tone they intended in their play of Persiflage. We selected three codes as characterizing players' language: the use of slang, external references, and period language. Figure 3 shows the counts of these codes.

Slang indicates that an utterance contains modern vulgarisms or vernacular that are out of place in the mediaeval village in which the game is set. An utterance coded as an external reference alludes to knowledge or ideas outside the game world. External references were further sub-classified as inside jokes, current events, and pop culture. We coded utterances for period language when the speaker deliberately used language outside of colloquial norms to suggest a different setting and era. Such language need not be an accurate representation of mediaeval speech; in particular, Reichert has coined the term "RPG-Dialect" to describe faux-period language "that makes liberal use of 'thous', 'thees', and 'mi'lords"' [START_REF] Reichert | Thou art awesome -the failings of 'RPG-dialect[END_REF].

As shown in Figure 3, the use of slang is by far the most prevalent, and is seen in all five groups. We see 30 (5.6%), 6 (1.3%), 32 (8.2%), 33 (5.2%), and 70 (14.4%) utterances that contain slang in groups 1 through 5 respectively. Of the 171 utterances coded for slang, 111 came from players and 60 from orchestrators. External referencing was seen in four of the five groups. Groups 1, 3, 4, and 5 made 11 (2.0%), 12 (3.8%), 21 (3.3%), and 6 (1.2%) reference utterances respectively. Of 53 utterances coded as references, 7 were made by orchestrators and 46 by players. Period language was present in all five groups, with 33 (6.1%), 7 (1.3%), 23 (5.8%), 31 (3.3%), and 2 (0.4%) occurrences across the five groups. The use of period language was higher in groups one, three, and four, and notably less in groups two and five. We observed 74 of 83 occurrences of period language in orchestrators' utterances and 9 in players' utterances.

The above numbers show that players made use of slang and references more liberally than orchestrators, who in turn were more likely to employ period language. This example from group one shows the players using slang whilst the orchestrator uses more formal language: Player Left greets the magistrate using slang, and the orchestrator voicing the magistrate responds sternly, modeling his character's speech to the game setting. Despite the magistrate's suggestion of the game taking place in a past era, the player insists on using another colloquialism, "where she at?". The resulting dialogue is asymmetric, with a comedic dissonance between the player's and NPC's speech. The absurdity of the interaction is not lost on Player Right, as shown by her reactions and laughter during the dialogue.

Another example shows the use of an external reference. Player Left compares an antagonistic authority figure to U.S. president Donald Trump: This example shows Player Left using her knowledge of the outside world to inject humour into the game. The humour is well-received, as shown by Player Right's laughter. The juxtaposition of modern people and ideas with the setting of a sleepy mediaeval village adds levity to the dialogue. The resulting experience is not unlike a pantomime play where a classic story is presented with a modern and cheery slant, making liberal use of anachronistic references to current events and culture. Whilst the reference in the example above is anachronistic and introduces knowledge that the character would not possess, it nevertheless relates back to the game world, in this case by drawing an analogue between the fictional character and the real-life politician.

External referencing and slang are both used to provide humour and a personalized game experience leveraged from the modern social zeitgeist. Period Fig. 4. Occurrences of utterances coded for storytelling, banter and coordination language, conversely, indicates a desire to play in character and to provide a more (or possibly mock) authentic game experience. Players overwhelmingly display a higher propensity to use slang and external references than orchestrators, whilst the inverse is true for period language. Orchestrators are more invested in authenticity whilst players are content to make jokes and enjoy the experience less rigidly.

Storytelling

The presence of open-ended dialogue gives players the opportunity to contribute to the story by adding to the story arc, or to step out of the story, e.g., by telling a joke unrelated to the game. Coding revealed that utterances fell into one of three categories, denoted as storytelling, coordination, and banter. Figure 4 shows the counts of these codes.

A storytelling utterance seeks to advance the story. These usually take the form of a player posing a question to an NPC, or conversely, the orchestrator responding to a player's question. An utterance that helps participants plan or otherwise coordinate their activities is coded as coordination. These mostly involve players summarizing their gathered knowledge, or planning their next step in the adventure. An utterance is coded as banter if it represents some form of repartee that does not contribute to the game's goals. This could include inserting a joke or an external reference into conversation.

Of the three categories, storytelling utterances are the most common, accounting for 315 (58.6%), 259 (61.1%), 232 (64.1%), 358 (56.5%), and 251 (51.5%) of total utterances over the five groups. Orchestrators devote more of their utterances towards storytelling than the players, averaging 86.4% and 44.3% of total utterances respectively. Storytelling utterances represent the heart of Persiflage, where players interrogate, beg, and intimidate the NPCs for information and clues. The fact that almost half of players' utterances are related to storytelling indicates that despite the levity noted earlier, players were seriously engaged in trying to solve the mystery.

Coordination utterances account for 10.3%, 16.9% 8.3%, 23.0% and 17.1% of all utterances in groups 1 through 5. In theory, these utterances ought to be produced exclusively by players. We expect players to summarize and plan without the involvement of orchestrators, who play exclusively in character as NPCs. However, on rare occasion, we saw orchestrators contributing their own coordination utterances, commenting on players' observations or correcting their erroneous assumptions.

Three groups engaged in significant banter; in groups 1, 4, and 5, banter accounted for 11.9%, 14.5%, and 17.2% of total utterances respectively. The other two groups engaged in little banter, accounting for 3.3% and 5.2% of total utterances in groups 2 and 3. We observed bantering as a behavior more frequently in players than in orchestrators. In all groups, the players made more banter utterances (13.0%) than the orchestrator (4.9%). In the following typical example of banter, the exchange does not advance the story, but stays within context of the game:

Here the players have just finished talking with NPC "Annie", and they jokingly comment on the ambiguity of the the directions they've recieved. Player Left makes a joke referencing the trope of the "crazy cat lady". In the short excerpt, we see the players seamlessly coordinate their movement, banter about the reliability of the NPCs, and tease the orchestrator on his ability to correctly give directions.

Orchestrators devote most of their play to storytelling, accounting for approximately 85% of their utterances on average. The players ask the NPCs questions, but contribute fewer storytelling utterances. This is not entirely surprising considering that the orchestrator controls all the facts of the mystery and slowly reveals them to the players over the course of the game. Players on the other hand, must interact with their co-player to coordinate in addition to talking with the NPCs. We see that participants are content to mix in banter whilst both progressing the story and coordinating between players. Players drive most of the bantering, which is consistent with our earlier observations that players adopt a less formal manner than orchestrators.

Discussion

To better understand how players engage with Persiflage we can look to the concept of the magic circle. Johan Huizinga coined the term "magic circle" to denote a boundary, not only in space and time, but also as a societal construct, that delimits where and how a game and play occurs [START_REF] Huizinga | Homo Ludens[END_REF]. The magic circle establishes behaviours, etiquettes, regulations and their adherent consequences that form the terms of a game, separate from society as a larger whole.

In the context of playing a character, behaviours within the circle are those that an in-game character might exhibit. Behaviours outside of the circle are those that we would expect the player as an individual outside of the game to show, but that their assumed characters could not exhibit. For example, contextually leaving the game and discussing a school assignment breaks the magic circle. Williams et al. argue that roleplay cannot exist without a strong magic circle [START_REF] Williams | Behind the avatar: The patterns, practices, and functions of role playing in MMOs[END_REF]. However, both Consalvo [START_REF] Consalvo | There is No Magic Circle[END_REF] and Castronova [START_REF] Castronova | Synthetic Worlds: The Business and Culture of Online Games[END_REF] argue that the magic circle can be porous.

In the terminology of Montola [START_REF] Montola | Exploring the edge of the magic circle: Defining pervasive games[END_REF], Persiflage expands the magic circle in the societal dimension. Players and orchestrators take on two distinct roles; as a game player as well as an audience to their fellow players' performances. Orchestrators and players, as they were observed in this study, exhibit not only the characters of their game world personas, but also their own personalities. We see this as they incorporate current affairs, private jokes, and shared experiences into their game dialogue. By using the freedom afforded by open-ended natural language, players adapt and modernize Persiflage's environment, expanding the social contract they play under and in turn redefine their shared reality of the game. Fine describes these behaviours in terms of frames, defined as distinct worlds of knowledge [START_REF] Fine | Shared fantasy: Role playing games as social worlds[END_REF]. Players and orchestrators in Persiflage switch fluidly between the primary frame of reality and that of the game world, some-times within the same sentence. The characters within Northaven maintain an open awareness between the two frames, giving rise to quips about contemporary politics and the use of modern slang and colloquialisms whilst playing in a mediaeval fantasy world. Fine explains that in the informal setting of fantasy gaming, this form of banter and the maintenance of multiple selves is common amongst players and does not usually lead to confusion.

Our findings mirror these observations. Players and orchestrators used natural language interactions in full confidence that they would be understood by the others. Participants were aware that they were playing a game with friends, and felt comfortable stretching the magic circle. They took ownership of the game, incorporating their own ideas, views, and experiences to entertain both themselves and their peers. Rather than finding the magic circle porous, we find it to be expansive and elastic, stretching beyond the borders of Northaven to include colloquial vernacular and references to modern day pop-culture and politics. Yet the magic circle is strong enough that the players and orchestrator stayed rooted in the game for the duration of the play session. Figure 3 shows that players were the principal instigators in stretching the magic circle with jokes and slang, whilst period language originated almost exclusively from orchestrators. The clash of styles makes for humorous dialogue exchanges.

Even though orchestrators are not as active in expanding the magic circle, our examples showed that they played along when the players did so. For example, orchestrators happily acknowledged the absurdity of finding cheese on the ground. Both players and orchestrators committed fully to play. When playing Persiflage, all participants gave their full attention to the game. Banter and external references unfailingly alluded to in-game devices or events. We observed no events where players opened topics unrelated to the ongoing game.

As we saw earlier, orchestrators stretch the edges of the magic circle to a lesser extent than players. The banter they engage in is topical to the game setting, providing idiosyncrasies to their characters, and making small talk and gossip that one might expect in a quaint medieval village. Players, on the other hand, incorporate pop-culture and current politics in the service of humour.

Conclusion

In this paper we have explored the effect on play of computer role-playing games of permitting free-form dialogue between players and NPCs. To study this question, we introduced Persiflage, a novel digital RPG that employs a human to voice NPCs. Through open-ended natural language, players deliberately derived humour from the absurdity of mixing modern popular culture with Persiflage's mediaeval setting. The orchestrators who gave voice to the NPCs were more rooted within the game world, using less slang, and more period language, resulting in asymmetric and humorous dialogue.

Fig. 1 .

 1 Fig. 1. (Left) Players of Persiflage are collocated, sharing a couch and TV. In conversation, the orchestrator's voice is played through the television set. (Right) The players' characters are dressed in blue and red in their shared view of Northaven.

Fig. 2 .

 2 Fig. 2. (Left) An orchestrator manage NPCs and items, and uses a headset to voice the NPCs. (Right) The NPC in the centre moves along the path traced out by the orchestrator in red. The blue buttons allow the orchestrator to trigger speaking and waving animations. The window inset in the top-right shows the players' view.

Fig. 3 .

 3 Fig. 3. Occurrences of slang, external references and period language

  What are you doing in my town? Player Left: We're looking for Helena, where she at? Player Right: stifled laughter . . . where she at. . . Magistrate: As far as I know, Helena's passed away.

	Player Left: What up?
	Player Right: laughter
	Magistrate (voiced NPC):

Acknowledgements

The authors wish to thank the Natural Sciences and Engineering Research Council of Canada (NSERC) for its support of this research.

Player Left: Hey. Hamish (voiced NPC): Hello again, it's me Hamish. Player Left: Hey Hamish, so what's up? Hamish: Uh, I've just been enjoying that cheese you gave me, it's quite tasty. Although it was a little dusty from the floor you found it on. Player Left: It's not really our fault, it's the only place that people put cheese around here. Hamish: Well it's mostly your fault. Player Left: Quiet now. Hamish: laughs Player Right: So, we lost the diary?

The orchestrator responds to the open query, "Hey Hamish, so what's up" by recalling a previous interaction and introducing some humour from the absurdity of finding cheese on the floor. This sets off an exchange between Player Left and Hamish which does not advance the story, but adds levity to the conversation. The example concludes with Player Right redirecting the interaction back to storytelling. While banter is humorous and does not advance the story, it remains rooted within the game world. Similarly, players are happy to mix banter and coordination in conversation with each other:

Player Right: We're getting mixed stories here. I feel like a real investigator, okay so. . . Player Left: . . . this is not a field. Player Right: This is not a field. Player Left: This just proves that women with cats are crazy. Player Right: He said to our left? Player Left: Maybe [orchestrator] doesn't know directions; I'd believe that also. Player Right: Maybe he's thinking his left?


Ícaro Goulart
email: igoulart@id.uff.bralinepaes

Aline Paes

Esteban Clua
email: esteban@ic.uff.br

Learning how to play Bomberman with Deep Reinforcement and Imitation Learning

Keywords: bomberman, proximal policy optimization, reinforcement learning, lstm, imitation learning

Making artificial agents that learn how to play is a longstanding goal in the area of Game AI. Recently, several successful cases have emerged driven by Reinforcement Learning (RL) and neural networkbased approaches. However, in most of the cases, the results have been achieved by training directly from pixel frames with valuable computational resources. In this paper, we devise agents that learn how to play the popular game of Bomberman by relying on state representations and RL-based algorithms without looking at the pixel level. To that, we designed five vector-based state representations and implemented Bomberman on the top of the Unity game engine through the ML-agents toolkit. We enhance the ML-agents algorithms by developing an Imitation-based learner (IL) that improves its model with the Actor-Critic Proximal-Policy Optimization (PPO) method. We compared this approach with a PPO-only learner that uses either a Multi-Layer Perceptron or a Long-Short Term-Memory network (LSTM). We conducted several pieces of training and tournament experiments by making the agents play against each other. The hybrid state representation and our IL followed by PPO learning algorithm achieve the best overall quantitative results, and we also observed that their agents learn a correct Bomberman behavior.

Introduction

Building games with agents that learn how to play is a long-standing goal in Game-AI. So far, this has been mainly addressed by Reinforcement Learning (RL) algorithms [START_REF] Sutton | Reinforcement learning: An introduction (in preparation)[END_REF] and, more recently, by combining RL with deep neural networks in the area of Deep Reinforcement Learning (DRL) [START_REF] Li | Deep reinforcement learning: An overview[END_REF][START_REF] Silver | A general reinforcement learning algorithm that masters chess, shogi, and go through self-play[END_REF][START_REF] Mnih | Playing atari with deep reinforcement learning[END_REF]. However, the most remarkable results achieved so far have counted with valuable computational resources to deal with large pixel level-based search spaces.

We would like to thank the Brazilian research agencies CAPES and CNPq, and NVidia.

In this work we take a step in another direction: we focus on the game of Bomberman represented in a grid scenario. Bomberman is a popular and universally pleasurable maze-based strategy video game that requires intelligence. Although at first sight it looks simple, designing an intelligent Bomberman agent faces a number of challenges: a vast search space due to numerous components possibilities (other agents, bombs, blocks, etc), multiplayer mode, strategic reasoning, delayed reward due to the time that the bombs take to explode, and a dynamic environment [START_REF] Resnick | Pommerman: A multi-agent playground[END_REF].

Most of the available work addressing Bomberman learning-agents has focused on table-based RL without exploring the more general function approximation power of neural networks [START_REF] Da | Bomberman as an artificial intelligence platform[END_REF][START_REF] Karasik | Intro to ai bomberman[END_REF]. Only recently, Komerlink et al. [START_REF] Kormelink | Exploration methods for connectionist q-learning in bomberman[END_REF] have used Q-learning coupled with a multi-layer perceptron neural network (MLP), focusing on comparing exploration strategies. Here, we tackle the complexity of the Bomberman game with a combination of Imitation Learning (IL) [START_REF] Li | Deep reinforcement learning: An overview[END_REF] and the recently developed Actor-Critic Proximal Policy Optimization (PPO) strategy [START_REF] Schulman | Proximal policy optimization algorithms[END_REF], developed within the area of DRL. In IL, an apprentice agent learns to perform a task observing an expert. Arguably, this strategy produces a good starting point for the PPO algorithm. We devised the Bomberman game using the Unity game engine and implemented the combined approach on the top of the ML-Agents toolkit [START_REF] Juliani | Unity: A general platform for intelligent agents[END_REF], an open-source project to create simulation environments based on ML and using the Unity Editor. Also, we implemented five vector-based state representation, namely: 1) Hybrid One-hot, 2)ZeroOrOne, 3)Binary Flag, 4)Normalized Binary Flag e 5)ICAART.

The Bomberman game we developed holds the capability of representing cells with more than one element, allowing for more than one agent to be in the same cell, as in the original game. Additionaly, the only information the agents have from the game is the observation of the environment, in the form of the vector-based state representations and the rewards.

We conducted a series of training sequences and tournament among the agents to compare (i.) the five ways of representing the space state, (ii.) PPO trained with MLP or Long-Short-Term memory [START_REF] Hochreiter | Long short-term memory[END_REF] (LSTM), and (iii.)the Behavioral Cloning (BC) IL algorithm followed by PPO compared to training these algorithms singly from each other. The results have pointed out that by using the hybrid state representation and aggregating the experiences of several learners in a PPO+LSTM at once is the best general way of reaching an effective Bomberman agent. Our solution is publicly available 1 2 , allowing for further improvement and usage.

Background

Bomberman 3 is a maze-based strategy game franchise, developed by Hudson Soft Company in 1985. The game is based on placing bombs strategically within the scene, to kill the enemies, and to destroy blocks in the scenario, aiming at opening paths or finding items. In a multiplayer mode, the player's goal is to be the last player alive by killing all its opponents. The explosion of a bomb propagates vertically and horizontally to the neighbor cells, respecting possible obstructions along the way.

Here, we address the Bomberman game with RL algorithms. RL aims at teaching agents by trial and error, mapping states into actions through maximizing a numeric reward. The reward can be positive, when the chosen action leads to the goal, or negative, in the opposite case [START_REF] Sutton | Reinforcement learning: An introduction (in preparation)[END_REF]. To define the interaction between the learner agent and its environment, an RL problem is specified as a Markov Decision Problem (MDP) with a space state S, a set of actions A, a transition function T r(s, a) → s , a reward function R(s, a) → R, and a discount factor γ. The goal is to find a policy function that maps states to actions.

An RL problem can be modeled as a regression function by mapping the space of states and actions to the reward [START_REF] Lapan | Deep Reinforcement Learning Hands-On: Apply modern RL methods, with deep Q-networks[END_REF]. The goal becomes approximating such a function using, for example, a neural network [START_REF] Hornik | Multilayer feedforward networks are universal approximators[END_REF]. Neural networks can focus on optimizing the policies directly or on learning the value functions from them to infer policies. When the underlying neural network used in an RL problem is deep, we have a Deep Reinforcement Learning (DRL) algorithm [START_REF] Mnih | Playing atari with deep reinforcement learning[END_REF].

In this work, we rely on a DRL actor-critic method, using either an MLP or an LSTM network and on Imitation Learning. We briefly describe them as follows.

Proximal Policy Optimization (PPO) is a DRL policy optimization method that uses a stochastic ascent gradient to update the policy function. PPO has the stability and reliability of trust-region methods [START_REF] Schulman | Trust region policy optimization[END_REF], it is a model-free, on-policy RL algorithm, it can deal with a continuous space of observation and actions, and it relies on the Advantage operator instead of Q-values. It is based on the actor-critic framework that, roughly speaking, encompasses two networks, one to act as an estimator of the function value (the critic) and the other to determine the policy itself (the actor) [START_REF] Lanham | Learn Unity ML-Agents-Fundamentals of Unity Machine Learning: Incorporate new powerful ML algorithms such as Deep Reinforcement Learning for games[END_REF]. Accurately, PPO follows the actor-critic A3C [START_REF] Mnih | Asynchronous methods for deep reinforcement learning[END_REF] technique allowing that multiple asynchronous agents can be trained simultaneously in a global supervisor network.

Long Short Term Memory (LSTM) is a recurrent network (RNN) designed to avoid the problem of long-term dependency [START_REF] Hochreiter | Long short-term memory[END_REF] encountered by RNNs. The input information that enters an LSTM network may undergo some small linear interactions or move on to the subsequent iterations. LSTM also can add or remove cell status information through gates, composed of Sigmoid layers and multiplication operations.

Imitation Learning RL algorithms follow a series of interactions with the environment to achieve the goal, which can make the learning process very slow. To speed up the training time, IL techniques learn from expert demonstrations. Here, we use the Behavioral Cloning (BC), a supervised imitation learning method that maps state/action pairs from expert trajectories to policies without learning the reward function [START_REF] Li | Deep reinforcement learning: An overview[END_REF]. The BC method works as follows: i) observe the current state s and the action chosen a by the expert; ii) choose an action a based on the current policy P (initially this policy is selected at random); iii) compare the chosen action a with the expert demonstrated action a using an error function; iv) optimize the policy P using the error function, yielding a policy P ; v) repeats the whole process, now using P as the current policy.

Related Work

Previous work has also focused on Bomberman to implement and experiment with ML techniques. Bomberman as an Artificial Intelligence Platform (BAIP) [START_REF] Da | Bomberman as an artificial intelligence platform[END_REF] In [START_REF] Karasik | Intro to ai bomberman[END_REF] a Reactive, MiniMax, and Q-Learning agents were compared in a discrete-style Bomberman game. The MiniMax-based agent routinely defeats a human player, but it is computationally expensive and unable to run in realtime. The Reactive agent was able to defeat human players most of the time, but cannot beat the MiniMax agent. The best result achieved by their Q-Learning agent was in a static scenario without destructible blocks and with only one enemy standing still.

A Q-learning with MLP strategy was implemented in [START_REF] Kormelink | Exploration methods for connectionist q-learning in bomberman[END_REF]. An Error-Drivenand Interval-Q exploration strategies were compared to five other techniques. As there, we also represent the state of the environment with a vector to feed a neural network. However, we also include other state representations and rely on more sophisticated learning techniques, trying to address the complexity of the Bomberman game.

Pommerman [START_REF] Resnick | Pommerman: A multi-agent playground[END_REF] is a multi-agent environment based on the game Bomberman, consisting of a set of scenarios, each one with at least four players and containing cooperative and competitive aspects. Also, it can be used to create methods such as planning, opponent/teammate modeling, game theory, and communication. A competition track at NIPS 20184 used Pommerman as a framework. The Pommerman scenarios always have 11 rows by 11 columns and, different from the original game, Pommerman agents cannot occupy the same cell. The environment developed in our work allows cells with more than one state, and agents can occupy the same cell as in the original game. Besides that, we developed using a commercial game engine with a large community of developers.

State Representation and Imitation-Reinforcement Learning in Bomberman

In this paper, we investigate the influence of five vector-based state representation and four learning algorithms to make an agent learn how to play Bomber-man. The Bomberman game implemented here resembles the original gameplay. However, we focus on the agent behavior regarding the other agents, the scenario, and its wish to remain alive, disregarding power abilities and not allowing more than one bomb per agent. With that, the agent aims at being the last living agent on the scene to win the match. The game was developed with the Unity game engine, and the algorithms were built on the top of ML-Agents Toolkit.

Dynamic of the Game

The Bomberman scenario has nine rows and nine columns within a 2D grid board. The game computes the time according to the number of interactions between the agent and the environment. Each game may have two, three, or four players battling against each other. The entities in the game are (i.) indestructible blocks, (ii.) destructible blocks, (iii.) agents, (iv.) bombs, (v.) bomb's fires, and (vi.) danger zones. The danger zones are invisible entities that inform the extension of the bomb's fires when it explodes.

At the start of a match, the agents are randomly positioned in one of the four corners, each one in a different position. At each iteration, the agent receives the observation from the environment (detailed next) and takes one action. The agents can put one bomb at a time on the scenario in their current position. After N iterations that the bomb has been activated, it explodes with a range of two cells to each linear direction (up, down, left, and right). It is required to wait for the bomb explosion before putting another one. The fire of a bomb blast is configured to last only one iteration. Some entities within the range of an explosion obstruct its effect beyond them. Thus, the bomb explosion does not pass through the blocks or other bombs. Thus, in the presence of such entities, the explosion of a bomb is limited to one cell in the direction of the block (or another bomb) if it is on the same side of the bomb. However, the fire of a bomb causes the explosion of other bombs inside the two-cells range.

A match ends when there is only one living agent remaining on the scenario, or when they are all dead (draw). The last existing agent in the scenario is the winner of the game. If we do not have a winner after 300 iterations, then we generate a rain of bombs to force the end of the game.

Bomberman training as a Markov Decision Process (MDP)

As usual in RL problems, we design the Bomberman problem as a finite and episodic MDP. The MDP problem is composed of (1) the state set: the states of all the grid cells in the scenario and the position (x, y) of the agent. The state is encoded as a vector to feed the agent's observation. The vector representation can vary according to the type of representation. (2) Actions: the agent can (i.) standstill, (ii.) go up, (iii.) go down, (iv.) go left, (v.) go right, all of these last four moving a single cell, and (vi.) put a bomb. (3) Transitions: the transition from one state to another guided by action is determined by the previous state and the action themselves, with no uncertainty caused by the environment. Thus, the agent tries to execute an action and, if it is allowed, the environment perceives its effect. Other entities may also cause a transition from one state to another, such as a bomb that explodes. (4) Rewards The rewards are distributed according to Table 1. After performing one action, the agent receives a reward according to the new state of the game. One or more type of rewards can be applied combined in the same iteration. For example, the agent can kill an enemy and destroy a block, or the agent can only stay still and suffers the iteration penalty. Every time an agent gets closer to an enemy, it receives a reward for approaching an opponent (the fifth line in the table). For example, if the distance between the two agents in question is x cells, then the reward will only be given to the agent if he gets closer than that to the opponent, i.e., at least x -1 cells. Rewards for approximating and distancing agents are only given after a successful walking action when the observed state has a new position of the agent. The distances are computed as Manhattan distance.

Table 1. Rewards given to the Agent

State

Reward The agent is dead -0.5 An opponent is dead by the agent earning the reward 1.0 The agent is the last man alive 1.0 A block has been destroyed 0.1 The agent is in the closest position so far to an enemy 0.1 The agent is closer to an opponent than before 0.002 The agent is farther to an opponent than before -0.002 Penalty per iteration -0.01 The agent is in a cell within reach of a bomb -0.000666 The agent is in a safe cell when there is a bomb nearby 0.002

State Representations

In RL algorithms, the choice of representation for the observed states may influence the agent's learning ability as, if the state is misrepresented, the agent will probably be unable to find patterns and perform coherent actions. Here, the observation of the current state is represented as a vector. The size of this vector depends on the type of the state representation: if we use only the numerical value to represent a cell, then the observation vector has a numerical value to represent each cell of the grid. If we use an array, then the observation vector has the number of elements in this array to represent each cell in the grid.

We devised four possible representations to the environment: Binary Flag, Normalized Binary Flag, Hybrid, ZeroOrOne. Furthermore, we implemented the state representation devised in [START_REF] Kormelink | Exploration methods for connectionist q-learning in bomberman[END_REF] and named it as ICAART, yielding a total of five state representations. In all of these cases, every cell is first encoded as bit flags. Bit flags are used to store more than one Boolean value in a whole set of bytes, representing the existence of one or more objects of that state type in the cell. Thus, we can inform, for example, that an agent and a bomb are in the same grid cell at the same moment. In this case, if the bit flag representing the agent and the bomb are 01 and 10, respectively, then the bit flag representing the grid cell is 11. Eight possible state types are represented by bit flags: empty cell, indestructible block, destructible block, current agent, enemy, bomb, fire, and danger. The five state representations are as follows:

1. Binary Flag In this case, for each cell in the grid, there is a bit flag to represent what is there, plus the position (x,y) of the agent, making the size of the observation vector as the size of the grid plus 2. After composing the observation vector with the bit flags, it is converted to decimal to provide the agent with this information finally. 2.Normalized Binary Flag This representation only normalizes the previous one to stay between maximum and minimum values. Values are in [0.0, 1.0] range.

3.Hybrid

The hybrid representation combines the Binary Flag representation with a One-Hot Vector representation. A One-Hot Vector is a 1 x C matrix, where C is the number of possible situations, which consists of 0s in all dimensions except for a single 1 in a dimension used uniquely to identify the class or state type. To represent a cell that has an agent ([1,0]) and a bomb ([0,1]) with a One-Hot Vector, the vector dimension must be increased by one, generating a new One-Hot Vector that represents the agent plus the bomb ([0,0,1]). This feature makes One-Hot vectors very costly. Thus, we propose a hybrid representation that allows for using a One-Hot vector similar to the Binary Flag representation. For example, to represent bomb and agent entities occupying the same grid cell, we have the Hybrid vector [1,1] instead of a new vector [0,0,1]. Each cell in the grid is represented using a Hybrid vector. Thus, if there are 4 types of state (plus empty), then the size of each Hybrid vector will be 4 (e. g. [1,0,0,1]). Consequently, the size of the observation vector will be the number of cells multiplied by the size of the Hybrid Vector plus position x, y (e.g. 4 × 4 + 2 = 18, in a 2x2 grid). More accurately, a Hybrid vector is a matrix 1 × H, where H is the number of possible situations, which consists of numbers 0 in all dimensions, except for numbers 1 in each dimension when their respective state is active. 4. ICAART This is the representation used in [START_REF] Kormelink | Exploration methods for connectionist q-learning in bomberman[END_REF]. For each cell in the grid, the number 1 is used to represent an empty cell, 0 if it is destructible or -1 if it is obstructed (indestructible or bomb). After this step, we have a vector of the same number of cells that we have in the grid. Next, for each cell in the grid, the number 1 is included if the agent is in that position or 0, otherwise. Then, we add 1 to the cell if there is an opponent there, or 0, otherwise. Finally, for each cell in the grid, a float value between -1.0 and 1.0 is included to represent the level of danger of a cell, computed according to the time that the bomb has left to explode (less time to explode means more dangerous). The danger value is negative if the bomb was placed by the agent and positive if it was placed by an opponent or by the environment itself. In this representation, the size of the observation vector is four times larger than the size of the grid. 5.ZeroOrOne This representation closely resembles the Hybrid representation, but, instead of adding one hybrid vector to each grid cell, each observation is added to the observation vector separately, as in the ICAART representation. It increases the size of the agent observation vector by seven times the grid size. The order of addition, considering the value of 1 or 0, respectively, is as follows:

(1), free or obstructed cell; (2) destructible or indestructible; (3) the cell contains an agent or not; (4) the cell has an opponent or not; (5) the cell has a bomb or not; (6) the cell is dangerous or not; [START_REF] Karasik | Intro to ai bomberman[END_REF] the cell is on fire or not.

Reinforcement Learning Algorithms

We include four RL algorithms to train Bomberman agents, as follows: (i) the PPO [START_REF] Schulman | Proximal policy optimization algorithms[END_REF] method integrated with a Multi-Layer Perceptron (MLP); (ii)the PPO [START_REF] Schulman | Proximal policy optimization algorithms[END_REF] method integrated with a Long Short-Term Memory (LSTM) network; (iii) the Behaviour Cloning (BC) [START_REF] Li | Deep reinforcement learning: An overview[END_REF] imitation learning method; and (iv) a novel implementation that runs the PPO after learning with BC, i.e., first, we run the BC, save its model, and start PPO with such a model.

The PPO algorithm approximates the policy function using a neural network. To that, the implementation provided by the ML Agents toolkit allows for using either an MLP or an LSTM as such a neural network. In this last case, we benefit from the memory component of the LSTM to allow for the agent to remember its relevant past experiences. The method keeps saving the iterations of the agent with the environment together with the received rewards to compose the batch of examples. More specifically, during each iteration of the game, the method accumulates the experience of each agent composed of the current state, the executed action, the received reward, and the next state. After a certain number of collected experiences, the network (MLP or LSTM) do its job, by executing the value and the advantage function, computing the errors, and updating the policy.

To train the agent using the BC algorithm, we provide a replay file with the expert interactions. The number of opponents in each match may change according to the replay file. The match in which the expert agent has played is exactly reproduced in the replay file so that the expert can demonstrate to the student how to play the game. When the student is learning, all the opponents' moves and matches are synchronized with the replay file. In this case, its opponents react according to the replay, but the apprentices have made their own decisions. After it dies or the number of iterations per match reaches a maximum limit, the next match in the file is loaded.

We also developed a novel combination of the BC and PPO training, by first training with the BC approach, followed by training with PPO. We save the model trained with BC and load this model to initialize the weights of the PPO network. We use a function that forces the network to load even though they are slightly different. All the nodes in the neural network that have the same name are loaded with the values from the previous training, while all nodes that were not present in the last training are initialized with their default values.

Training Process Loop

The entire training process is composed of several matches, corresponding to the episodes of a traditional RL algorithm. At the beginning of each match, the agents are created and randomly positioned in the grid. Since there is more than one agent per scenario, it is necessary to synchronize their observations, actions, and rewards. In this way, one agent does not have advantage over another one due to getting some information first. At the beginning of each iteration in a match, the state of the bombs is updated, and, if the time has come, they explode. It is also necessary to update the blocks since some of them may have been hit by an explosion. Next, each agent receives the state of the environment and the reward corresponding to the observed state. The learning algorithm also receives state observation and the given rewards to update the policy function. Finally, the living agents act in the environment, according to the action computed by the current policy function. At the end of an iteration, we apply the time penalty reward.

Experimental Results

In this section, we present experiments and results related to our proposal and conducted to investigate how Bomberman agents learn under (1) the five state representation, (2) MLP versus LSTM, and (3) the learning algorithms. General Experimental Setting: At the beginning of a match, we create at random 2 to 4 agents per scenario. To train the agents, we created and configured ten scenarios that run in parallel in the same 2D environment, simulating different episodes of the RL algorithm. Among them, five are static, meaning that their destructible blocks are recreated in the same configuration at the beginning of the episode, and the other five are configured at random. Table 2 shows the learning algorithms' hyperparameters. After the training phase, we conducted tournaments with the agents composed of a 100 matches (T100) whenever we want to compare agents learning within the same environment and tournaments with 1000 matches (T1000) to compare distinct agents.

To select the most appropriate way of representing states, we train PPO with only one ML-Agents toolkit's brain learning from the experience of all the agents in the scenario. We repeat the training five times for 2M iterations for each one of the five types of state representation (Binary Flag, Normalized Binary Flag, Hybrid, ICAART, and ZeroOrOne). Thus, we have a set of homogeneous brain = {BF, NBF, H, I, ZO}, with each element in the set corresponding to one of the five state representations. Each element in homogeneous agents set unfolds into five training sets, i.e., BF = {BF 1 , . . . , BF 5 }, NBF = {N BF 1 , . . . , N BF 5 }, where the first element corresponds to a whole training execution, the second element corresponds to another independent training execution, and so on. Thus, we have a total of 25 training executions, taking, on average, 20 hours of training. The larger is the observation vector, the more time the training takes to finish.

Fig. 1 shows that the cumulative rewards of the Binary Flag and Normalized Binary Flag representations are lower than the other for almost the entire training phase, achieving the average performance of the others only over the end of the training. Meanwhile, the other agents keep all taking the lead until the step 651K, when the ICAART representation gets the best average cumulative reward and surpasses the rest of them until the end of the training. The average cumulative reward of both ZeroOrOne and Hybrid Brains were similar. Note that standard deviation behaves similarly for all Brains.

The behavior of the cumulative rewards of the PPO with LSTM and the BC agents are very similar to the one presented in Fig. 1. Thus, due to lack of space, we do not show them here. Next, we select four out of the five agents of each representation according to their cumulative rewards (we keep the four agents with the largest accumulated rewards). Then, the selected agents battle against the other agents that learned with the same representation as in a T100. The tournaments are accomplished with four agents because this is the maximum number of agents allowed in the same scenario.

The percentage of wins considering each battle in the T100 tournaments are: BF 2 (28.5% of victories), N BF 1 (28.2%), H 1 (38.5%), I 4 (27.2%), ZO 1 (29.7%). Next, we would like to make these winners fight against each other in a new tournament. Again, as we have at most four agents in a scenario, we must discard the worst of these five. For so, we rely again on their training accumulated reward. Then, we have a new set composed of the winner agents W = {H 1 , I 4 , ZO 1 , N BF 1 } as BF 2 was the worst of them in the training phase. By analyzing the behavior of the agents in W when battling, we observed that they were able to learn how to play the Bomberman game correctly. They usually put bombs and escape from them, except for N BF 1 , which only sometimes acts as expected.

Finally, we yield a T 1000 tournament to make the agents in the set W to battle against each other, aiming at verifying the best state representation for the Bomberman environment. The results are listed in Table 3. We can see that H 1 was the one reaching the most significant number of victories (4442), pointing out that this should be the best way of representing the environment.

Next, we experiment with LSTM to approximate the policy function within the PPO algorithm and verify if this would improve the performance of an agent that uses the Hybrid representation (the winner of the previous tournament). As LSTM requires a lot more parameters than MLP, we change some hyperparameters to alleviate the runtime. We trained five models with LSTM and did a T100 with the four models that obtained the best cumulative rewards. The winner of them was the second model generated in the training, achieving 31.4% of wins.

Then, we created another tournament called T1000-LSTM to compare two LSTM agents with two hybrid-MLP agents, the winner of the T1000-representation battle. As can be seen in Table 4, an agent trained with LSTM won the tournament with 61.02%. These results indicate that by activating LSTM in the PPO algorithm, we can induce agents that learn better from their environment to the point of winning other agents. This is due to the memory capacity of LSTMs that allows for the agent learn what to do, even when the reward is in a long way ahead in the future. Finally, we trained an agent with the BC algorithm and the Hybrid representation and tried to continue its training with PPO. Before training, we recorded 40 matches in a replay file where we play at least three matches in static scenarios and 20 matches in random ones, fighting against others that use LSTM. This replay file acts during the BC training as the expert so that the student agent can learn to play from it. In the BC training, we use the same hyperparameters used in Table 2 except that we changed max steps to 100K and set batches per epoch to 5. If the learner dies or if the game is taking more than 400 iterations to finish, we reset the scenario and load the next match of the replay file.

After finishing the BC training, we may still improve the policy function of the agent following two ways: i) (BC+PPO Only1): we run PPO starting from the policy learned by BC to train one agent against enemies already trained with the PPO-LSTM-Hybrid-state setting; ii) (BC+PPO All): In the second way of continued training, PPO runs after BC as before, but all the agents in the scenario are still learning. We create a series of T100 and T1000 tournaments to observe the BC agents behavior and found out the following: (A) (T1000 BC-vs-LSTM): The BC agent plays reasonably only when it is in the exact scenarios he has trained before, and when his enemies behave in the same way as in the replay file. When the BC agent battles against the LSTM in a T100 one-vs-one agent tournament, it wins only 9.7% of the matches. (B) (T1000 BC+PPO Only1 vs LSTM): In this case, the BC-PPO Only1 wins the LSTM in 91.3% of the matches. This result shows that it is useful to start from a trained BC agent and refine it with PPO. (C) (T1000 BC+PPO All vs. LSTM): Here, the winning agent was the BC+PPO All with 56.69% of wins against 39.98% of the LSTM agent. These results further confirm that BC provides a good starting point to PPO and that the knowledge acquired in the previous training with BC has not been forgotten. (D) (T1000 BC+PPO Only1 vs. BC+PPO All): The BC+PPO All won 49.5% of the matches whereas the BC+PPO Only1 won 42.3% of the matches. This result shows that the agents may learn better when facing other agents that are learning as well. However, this was the most closely results from all the others. Note that the LSTM opponents used in BC pre-training are also used in the BC+PPO Only1 training. However, in BC+PPO All training, LSTM opponents are not used, as all the agents are using the same controller and, therefore, the same policy function. This explains why BC+PPO All wins fewer matches against LSTM opponents than BC+PPO Only1 as this later becomes an expert at beating LSTM because it trained only with these opponents.

Conclusions

In this work, we investigated five state representations and four learning algorithms to build Bomberman agents that learn how to play. Regarding the state representations, the results pointed out that our proposed hybrid representation achieves the best results in test time, experimented with tournaments conducted after the learning phase. Regarding the learning algorithms, we experimented with the actor-critic-based PPO algorithm using either an MLP or an LSTM, the BC imitation learning, and a novel approach developed by us that starts with BC and continues the training with PPO from the function learned with BC. The results pointed out that by coupling LSTM within the PPO algorithm produces smarter agents and training beforehand with the BC algorithm can influence subsequent training with PPO. As future work, we would like to enhance the Bomberman agents by giving them the ability to put several bombs at once and acquiring power, variable-size scenarios, multi-players and testing other RL and IL algorithms.

  is a Bomberman-based graphical, open-source, agnostic language platform, able to assist in the study and development of new AI techniques. It includes agents based on heuristics, searching, planning, and RL methods. Agents that use RL techniques were not able to play the same version of the game as heuristic and search agents.

  Cumulative rewards in the Bomberman training sessions with the 5 types of state representation. Vertical lines stand for standard deviation.

		1.00
		0.75
	Cumulative Reward	0.25 0.00 0.25 0.50
		0.75 0.50				Binary Flag Norm. Binary Flag Hybrid ICAART ZeroOrOne
		1K	201K	401K	601K	801K 1.001M 1.201M 1.401M 1.601M 1.801M 2.000M Number of steps
	Fig. 1.

Table 2 .

 2 Hyperparameters used in the learning process

	Name	Value	Name	Value	Name	Value
	batch size	128	# hidden layers (MLP)	3	# hidden units (MLP) 128
	learning rate (MLP)	0,0003	time horizon	128	beta	0,005
	buffer size (MLP)	2048	epsilon	0,2	gamma	0,99
	lambd	0,95	max steps	2M	normalize	false
	# epoch (MLP)	3	sequence length (LSTM) 32	memory size (LSTM) 256
	# hidden layers (LSTM)	1	time horizon (LSTM)	64	buffer size (LSTM)	1024

Table 3 .

 3 Results of a T1000 tournament that compares agents with different state representations

	Results No. of Wins
	Draw	263 (2,63%)
	N BF1	319 (3,19%)
	H1	4442 (44,42%)
	I4	1782 (17,82%)
	Z1	3194 (31,94%)
	Total	10000 (100%)

Table 4 .

 4 Results of a T1000-LSTM Versus Hybrid tournament

	Results No. of Wins
	Draw	395 (3,95%)
	LSTM 2 6102 (61,02%)
	H1	3503 (35,03%)
	Total	10000 (100%)

https://nips.cc/Conferences/2018/CompetitionTrack