Olivier Cavadenti

Victor Codocedo

Jean-Franc ¸ois Boulicaut

Mehdi Kaytoue

What did I do Wrong in my MOBA Game?: Mining Patterns Discriminating Deviant Behaviours

Keywords: video game, moba game, contextualized trajectory, expert model, discriminative pattern mining

The success of electronic sports (eSports), where professional gamers participate in competitive leagues and tournaments, brings new challenges for the video game industry. Other than fun, games must be difficult and challenging for eSports professionals but still easy and enjoyable for amateurs. In this article, we consider Multi-player Online Battle Arena games (MOBA) and particularly, "Defense of the Ancients 2", commonly known simply as DOTA2. In this context, a challenge is to propose data analysis methods and metrics that help players to improve their skills. We design a data mining-based method that discovers strategic patterns from historical behavioral traces: Given a model encoding an expected way of playing (the norm), we are interested in patterns deviating from the norm that may explain a game outcome from which player can learn more efficient ways of playing. The method is formally introduced and shown to be adaptable to different scenarios. Finally, we provide an experimental evaluation over a dataset of 10, 000 behavioral game traces.

I. INTRODUCTION

The video game industry has been dramatically expanding over the last few years, targeting several populations (new, casual and extreme players) and electronic devices (PC, consoles, smartphones, etc.). Indeed, over the last decade, the annual turnover generated by the electronic entertainment industry went beyond those of both cinema and music industries, making video games production one of the most lucrative business ever developed. In the meantime, a new scene called electronic sports (eSports) has emerged, where the most skilled players (also referred to as gamers) are hired by professional teams and supported by sponsors to take part in large international competitions [START_REF] Taylor | Raising the Stakes:E-Sports and the Professionalization of Computer Gaming[END_REF] widely followed on live streaming platforms such as Twitch.tv [START_REF] Kaytoue | Raïssi. Watch me playing, i am a professional: a first study on video game live streaming[END_REF].

The success of eSports has also brought also new challenges for developers and gamers alike. Although eSport games represent only a tiny proportion of all video games, they gather masses around an game title and its sponsors, thus coming with new and lucrative business models. For example, the League of legends 2015 World Finals counted 36 million unique viewers and awarded the winner with a US$ 1M prize [START_REF]Worlds 2015 viewership[END_REF]. From the point of view of the game publisher, a video game designed to be an eSport should not be only interesting to professional players, but it also requires to attract a fan base of amateur Contact: mehdi.kaytoue@insa-lyon.fr players. Fans should know the game, while understanding and appreciating the style of playing of professional gamers (mechanics and strategy [START_REF] Cheung | Starcraft from the stands: understanding the game spectator[END_REF]).

Consequently, video games should be designed to be interesting for a wide variety of skills, a task that have proven difficult for publishers. In a nutshell, we can use the famous board game Othello's slogan to describe the required learning curve of eSports: "A minute to learn, a lifetime to master". A well known example of the difficulties involved in the design of such learning curve can be found in the game StarCraft 2 (Activision/Blizzard) which has been constantly patched since its release in 2012. David Kim, the game designer responsible of balancing the game states this difficulty as: "Obviously we want both ends of the spectrum. On the one end the pro players, they want the game harder to show off their skill better. Other end is casual players, who want an easier game than Starcraft 2 is currently'' [START_REF]David kim and the impossible balancing act of starcraft 2: Legacy of the void[END_REF].

In order to support players in overcoming this learning curve, our goal in this article is to analyze player behaviors (movements and strategic choices) and compare them to expected behaviors under different circumstances. When a behavior is detected as abnormal (deviating from expected behaviors), we seek the context of such abnormality.

We consider Multiplayer Online Battle Arena games (MOBA) and particularly Defense Of The Ancients 2, commonly known as DOTA2. This game is a high level eSport strategy game with rich behavioral data containing both, mobility traces and strategic choices. Given a set of game logs (historical data), our goal is to discover strategic patterns that can help the player to understand his game decisions and improve his skill. For example, considering all the games of a player in the current season (or patch), we would like to answer questions such as: What are the particular choices (e.g. build orders, map trajectories, team composition, etc.) that discriminate victory? What did I do wrong in my game, that is, that deviates from the norm (how other similar gamers play) no matter the outcome? Simple database queries can hardly answer these questions, as the number of possible queries/contexts is exponential w.r.t. such features. Hence, we have designed a data mining-based method that aims to discover patterns composed of strategic choices that explain strong deviations w.r.t a Reference Model.

A Reference Model represents a background of matches with common characteristics, e.g. all of them ending in victory. Reference Models can also be adapted to handle different scenarios. Finally, we provide an experimental evaluation of pur approach over a dataset of 10, 000 behavioral game traces.

The paper is organized as follows. We introduce MOBA games principles and our problem setting in Section II. Basics from pattern mining are introduced in Section III which are necessary for understanding the our methodology discussed in Section IV. An experimental evaluation along with the description of the dataset used is presented in Section V. Finally, related work is detailed in Section VI.

II. PROBLEM SETTINGS

A. Multiplayer Online Battle Arenas (MOBAs)

MOBA is a specific video game type that mix aspects of real-time strategic game and role-play game. Whole in this article we focus on Defense of the ancient 2 (DOTA2, [START_REF]Dota2, wikipedia[END_REF]), there are several other well-known MOBA games that share the same principles with slight differences (e.g. Heroes of the storm, League of Legends, etc.). The choice of game was made because of data availability and has no impact on the methodological aspects developed hereafter. A DOTA2 match is played on a map where two teams of five players battle each other in real time. Each team has to defend their own stronghold and destroy the opponent's one to win. Each player controls a hero which he moves through the map by providing instructions using mouse clicks. Furthermore, the player needs to improve the hero by collecting gold, new items, abilities, and by fighting heroes of the opposing team. Figure 1 displays the map of the game along with the initial influence zone for both teams. Team red (called Dire) and team blue (called Radiant) defend their strongholds located at the top right corner and bottom left corner of the map, respectively. Three lanes on the map (top, mid, bot) separate both teams with series of defensive towers. Players have well defined roles depending on the hero they initially picked from a current pool of 110 available heroes. For example, one role consists of defending and extending the influence zone in a specific lane while another role is to quickly switch lanes to attack by surprise. Like rugby, certain positions and moves are really important and can determine the outcome of a match (strong defense of towers and base, attacking players by surprise, make a concerted and synchronized attack on certain targets, etc.). Knowing that a team only sees controlled map zones, estimating enemy positions and triggering team fights at well-chosen times and in strategic areas is key to success.

B. MOBA behavioural data

DOTA2 provides a log system based on replay files which players can recover after each match. In a nutshell, each match is completely recorded in a single file (called replay) for all of the 10 players involved. A replay contains all users' actions and positions as well as other system generated events. We will refer to the information of a single player's hero in a replay as a trace, however this notion will be later extended and formalized. Replays have been extensively used by developers,publishers and players alike to analyze behaviors and strategies that allow better understanding the in-game interactions of the entities involved (human and non-human controlled). Concerning DOTA2, replays contain among other pieces of information:

• Positions: For each hero expressed in x,y coordinates on the map where (0,0) is the center (Figure 1). • Builds: Upgrades applied by a player to his hero.

These should be carefully chosen as they are definitive and interdependent. A wrong build usually leads to poor performing heroes.

C. Mining patterns explaining deviant behaviors

A new player learning how to properly use a given hero is likely to lose several matches if his team is not able to compensate for his lack of experience. A useful way for the new player to learn what he is doing wrong is looking at skillful players' replays. He will encounter that some strategies are different to what he has been doing so far and thus he will adopt those new strategies while dropping his own incorrect ones.

We can consider the last scenario in the context of data mining. Indeed, the new player is looking for frequent patterns in a reference model and contrasting them to frequent patterns in his own unsuccessful attempts to play the game. We will consider that a pattern that is prevalent in the latter set and not in the former corresponds to what the new player is doing wrong. An example (extracted from [START_REF][END_REF]) is given in Figure 2 depicting positions as points in the map in a given stage of the game for a different MOBA. Zones densely populated can be considered as normal behavior. In section IV, we describe and illustrate this more sophisticated approach.

III. BACKGROUND ON PATTERN MINING

In this section, we introduce the some basic notions of pattern mining through the use of an example. Firstly, we introduce the problem of Frequent itemset mining [START_REF] Agrawal | Fast algorithms for mining association rules in large databases[END_REF] considered the simplest form of frequent pattern mining. This choice was made for the sake of simplicity as it makes the method easier to follow, although generalizable to other kind of patterns. Secondly, we explain how to discover Emerging patterns that is, itemsets that discriminate a class label [START_REF] Dong | Efficient mining of emerging patterns: Discovering trends and differences[END_REF].

A. Mining frequent itemsets

Consider a set of transactions, where each transaction is composed of a set of items (in the original problem formulation, a set of items bought in a supermarket [START_REF] Agrawal | Fast algorithms for mining association rules in large databases[END_REF]). An arbitrary itemset is said to be frequent if the items it contains appear jointly in several transactions (i.e. more transactions than a user defined threshold). One can easily draw a parallel with MOBA: a transaction could be the set of items bought by a single player during a given game.

Definition 1 (Frequent itemset): Let I be a set of items. A transaction t is a set of items t ⊆ I. A (transaction) database is a set of transactions D = {t 1 , t 2 , ..., t n } with t i ⊆ I, ∀ i ∈ [1, n]. Given an arbitrary itemset X ⊆ D, its support is given by the transactions that contain all items in X:

supp

D (X) = |{t | t ∈ D, X ⊆ t}|
The frequency of an itemset is the proportion of transactions in the database that contain the itemset:

f req D (X) = supp D (X)/|D|
The frequent itemset mining problem consists in efficiently finding all the frequent itemsets in a transaction database D, that is, with a frequency higher than a minimum frequency threshold θ: all X ⊆ I such that f req D (X) > σ. Equivalently, a minimum threshold on the support size is denoted by min sup.

t id transaction t 1 {a, b, c} t 2 {a, b, c} t 3 {c} t 4
{a, b, e} t 5 {a, e}

Table II: Transaction database

Note that several constraints other than minimal frequency can be used, such as minimal size of the itemset, minimal cost of an itemset (in the case where each item has a cost assigned), maximization of a function given by a mathematical model or several condensed representations that reduce the number of patterns [START_REF] Boulicaut | Constraint-based data mining[END_REF]. Indeed, as there is an exponential number of itemsets (2 |I| in the worst case), a naive exploration of all itemsets is intractable while the mathematical properties of constraints can be taken into account for an efficient extraction. Algorithmic issues will be discussed in the Section IV.

Example. Consider a database where each transaction consists of the set of items bought by a single player in a single a game. Given five items I = {a, b, c, d, e}, and the transaction database shown in the Table II we have: supp D ({a, b, c}) = 2, supp D ({a, b}) = 3, f req D ({a, b}) = 0.6 and f req D ({a, b, c}) = 0.2. If we set the minimal frequency threshold σ = 0.3, we have that {a, c} is frequent while {a, b, c} is not a frequent itemset.

B. Mining itemsets that distinguish a class label

Consider now that each transaction is provided with a single label, say positive or negative, for win or lose 1 as depicted in Table III. Patterns for which one of the labels is more prevalent give interesting and comprehensive hypotheses for that label. The main idea is to consider two transaction databases, made of positive and negative examples respectively and then to compute the support of an itemset in both databases separately. Intuitively, if their difference is high, the pattern may be a signature of one specific base. More formally, the mapping class : D → {+, -} associates to any transaction its class label (positive or negative). Then, we can define the positive and negative bases:

D + = {t | t ∈ D, class(t) = +} and D -= D\D +
Thanks to this partitioning, we can compute a measure that expresses how an itemset discriminates a class label in favor of the other. Such an itemset is denominated an emerging pattern and the associated measure is called the growth-rate [START_REF] Dong | Efficient mining of emerging patterns: Discovering trends and differences[END_REF].

Definition 2 (Normalized growth-rate): Given databases D + and D -, the normalized growth-rate of pattern X ⊆ I is:

φ(X) = |supp D + (X)| -|supp D -(X)| |supp D + (X)| + |supp D -(X)|
where supp D + (X) (resp. supp D -(X)) counts the number of transactions supporting X in the positive database (resp. negative). This means that if φ(X) = -1 (resp. 1) then the itemset X appears only with a negative (resp. positive) label.

On the other hand, if φ(X) = 0 then X appears as much in the positive than in the negative database.

t id class(t id ) t 1 + t 2 + t 3 + t 4 - t 5 -

Table III: Label of each transaction

Example. We consider the same example as before, but we add as class attribute the outcome of the game, see Table III. The positive examples (resp. negative) correspond to a win (resp. loss). We have:

φ({a}) = (2 -2)/(2 + 2) = 0, φ({a, b}) = (2 -1)/(2 + 1) = 0.33, φ({a, b, c}) = (2 -0)/(2 + 0) = 1 and φ({e}) = (0 -2)/(0 + 2) = -1. Consequently,

IV. METHOD

In the following, we describe a methodology for discovering descriptive patterns of deviant behaviors in four steps:

1) Contextualized Trajectory Generation 2) Reference Behavioral Model Construction 3) Trajectory Deviation Evaluation 4) Discriminant Pattern Mining

A. From traces to contextualized trajectories

As described in Section II-B, a trace for a hero is a sequence of events that describe its states and positions throughout the game, as well as other actions executed by the player controlling it. A trace also contains global information of the match such as its length, winning team, etc. However, when considering positioning it is rather hard to work with map coordinates, as those shown in the example of Table I, given the high number of points created for each hero on each game (a coordinate each 33 ms). Instead, we will define arbitrary points in the map which we will refer to as points-of-interest or POI. Series of coordinates are converted to POI sequences or trajectories by taking the nearest POI at each coordinate (ignoring POI repetitions), similarly to [START_REF] Drachen | Skill-based differences in spatiotemporal team behaviour in defence of the ancients 2 (dota 2)[END_REF]. An example is shown in Figure 3 where the table contains 9 different POI with their corresponding coordinates and labels (arrows in the figure will be explained later). Definition 3 (Player trace): Let A = {A 1 , ..., A n } be a set attributes, where each attribute is either numerical or categorical (that is, takes either numbers or symbols as values). A Definition 4 (Contextualized trajectory): Let t ∈ T be a player trace. The trajectory of t is a sequence of POI trajectory(t) = v 1 , ..., v n where v i ∈ V and V is a set of POI. The description of t is a set of items description(t) ⊆ I, that are chosen/computed from the player trace. As such, a pair (trajectory(t), description(t)), ∀t ∈ T can be understood as a contextualized trajectory.

Example. Player traces in Table I have been transformed into contextualized trajectories in Table IV using the POI introduced in the Figure 3. For the sake of readability, descriptions are split in two columns: one with the objects purchased by the player, the other with the abilities acquired by the hero at specific experience levels.

B. Building a Reference Behavioral Model

The Reference Behavioral Model (or Reference Model) can be understood as the encoding of an expert opinion or more formally, as an expert model. Experts models are ideas, hypotheses or a priori knowledge of a given domain. In the most general case, an expert model is a function that returns a score for a given input to quantify an aspect of data (utility, outlier score, or a domain specific score). For example, the risk of soil erosion is assessed by a formula built by domain experts [START_REF] Flouvat | Improving pattern discovery relevancy by deriving constraints from expert models[END_REF].

In the case of DOTA2 where each match is played in a single map containing well-known point of interests (POI) such as corners, tower, bases, among others, it is intuitive to express expert knowledge as a graph of POI transitions. Actually, in MOBA games it is well established that a hero's movement and positioning throughout a match is a very good indicator of the experience and skill of the player that controls it [START_REF][END_REF]. We will refer to this as the mobility assumption.

The mobility assumption allows fixing allowed paths in the POI graph that represent skilled (expert) player usual transitions in the map. Obviously, the set of all allowed paths can be encoded as a Directed Graph which is not necessarily connected nor acyclic. Let us call this graph the Reference Behavioral Model.

Definition 5 (Reference Behavioral Model):

A reference model is a graph G = (V, E) with V a set of nodes (which represents POI) and E ⊆ V × V a set of edges (which represents allowed transitions between POI).

The reference model can be built manually by a game expert or automatically. In our case, we infer the reference model from a set of traces T m that are chosen w.r.t. the data analysis goals. For example, one may select all traces of a specific hero during a season, or instead all those from a particular professional player. Then, we choose a set of POI (9 zones in our simple example in Figure 3) denoted as V . For each player trace t ∈ T m , we compute the trajectory trajectory(t), i.e., the sequence of transitions between POIs (forbidding self loops). From the set of trajectories {trajectory(t), ∀t ∈ T m }, we compute the distribution of each direct POI transitions. For example, consider trajectory 5, 7, 5, 7, 5, 3, 5, 3, 5, 3, 2 , where transitions are distributed as follow: (5, 7) : 2, (7, 5) : 2, (3, 5) : 2, (5, 3) : 3 and (3, 2) : 1. Actually, these values are edge weights of the reference model G. Consequently, we can choose a cut off threshold to remove edges from the graph with low weights, e.g. consider a cut-off of 2, then we remove transition [START_REF][END_REF][START_REF]Dota2, wikipedia[END_REF]. This reference model corresponds to the graph represented with blue edges in Figure 3.

C. Measuring the deviation of a trajectory to the model

Given a Reference Model graph G = (V, E), each trace t to be analyzed is confronted to it. This is done using a function that takes t and G, and outputs a quantification of the outlierness of t, denoted as µ. Outlierness of a trace is measured by calculating the proportion of transitions in trajectory(t) that do not correspond to an edge in the Reference Model graph. We will use a |V | × |V | matrix representation of the Reference Model graph G denoted as M where M (i, j) = 0 if (v i , v j ) ∈ E and M (i, j) = 1 in the opposite case. A outlier scoring function for trace t, denoted by µ(t, M ) → [0, 1], returns 0 if the trajectory fully sticks to the Reference Model and 1 if it completely deviates from it.

Definition 6 (Outlier Score): Given a trace t such that |trajectory(t)| > 1, and a Reference Model matrix representation M , the outlier score is defined as: = 4/5 = 0.80. Thus, the second sequence is more anomalous than the first sequence. At this step, we can compute the values for the outlier score for each trajectory in Table IV.

µ(t, M ) = i=|trajectory(t)|-1 i=0 M (t i , t i+1 ) |trajectory(t)| -1 (1

D. Describing Deviant Behaviors with Discriminant Patterns

The outlier scoring measure allows splitting the original set of traces T into two transaction databases, containing positive and negative traces (non deviant and deviant, respectively). However, when defining these databases we will only consider the description axis of traces, i.e. global information (such as winning or losing) and purchased items during the match for each hero. These elements will allow us building explanations of non-deviant and deviant behavior as we explain next.

Definition 7 (Positive and Negative Traces): Consider an outlier scoring measure µ, a set of player traces T and a threshold θ ∈ [0, 1] called outlier threshold, the positive and negative transaction databases are given by:

D + = {description(t) | t ∈ T , µ(t, M ) ≤ θ} D -= {description(t) | t ∈ T , µ(t, M ) > θ}
Once the positive and negative transaction databases are built, we can mine frequent itemsets as defined in Section III. Notice that we are interested in itemsets that are actually patterns of trace descriptions (a subset of I) that frequently occurs in T . Finally, to discriminate if a pattern is a hypothesis of non-deviant or deviant behaviors we will use the normalized growth-rate φ introduced in Section III-B. IV. In the following, we use the notation d(t) = description(t), ∀t ∈ T . If we set θ = 0.5 we have two databases of traces D + = {d(t 1 ), d(t 2 ), d(t 3 )} and D -= {d(t 4 ), d(t 5 )}. Using min sup = 2, we have the frequent patterns X 1 = {buy X }, X 2 = {buy Z }, X 3 = {buy X , buy Y } with supp(X 1 ) = 4, supp(X 2 ) = 2, supp(X 3 ) = 2, resp. The normalized growth-rate for each pattern is:

Example. Let us consider traces in Table I and their trajectory representations in Table

φ({buy X }) = (3 -1)/(3 + 1) = 0.5 φ({buy Z }) = (0 -2)/(0 + 2) = -1 φ({buy X , buy Y }) = (2 -0)/(2 + 0) = 1
As we can see, itemset {buy X , buy Y } is a hypothesis of just positive or non-deviant traces. In other words, it is what we can consider a totally normal behavior. On the other hand, itemset {buy Z } describes only negative or deviant traces. We can consider it as a hypothesis of abnormal behaviors. Other examples are φ({ab A1 , ab B2 }) = (2 -0)/(2 -0) = 1 and φ({ab A1 , ab C2 }) = (0 -2)/(0 + 2) = -1. We can say that players who deviate from the model bought object Z, took ability A at level 1 and ability C at level 2. Other players took the ability B at level 2 and bought object Y . Algorithmic details. For mining frequent patterns, we use an efficient implementation of CHARM [START_REF] Zaki | Efficient algorithms for mining closed itemsets and their lattice structure[END_REF]. It extracts frequent closed itemsets. An itemset is closed if it has no superset with exactly the same support. Closed itemsets form a lossless condensed representation of frequent itemsets and that they maximize the growth-rate [START_REF] Plantevit | Condensed representation of sequential patterns according to frequency-based measures[END_REF]. For each pattern, we also compute a X 2 score (also maximized by closed itemsets) that allows one to measure how the distribution of the support of the itemset in the positive and negative bases is expected or not (introduced in [START_REF] Guns | Declarative pattern mining using constraint programming[END_REF]). Actually, in our experiments, we generally only consider the X 2 score as statistically sound (even when we use the term growth rate). This section reports an experimental study of the proposed approach. Firstly, we introduce the dataset used in our evaluation. Secondly, we show how different Reference Models can be built and to what extent. Thirdly, a quantitative study is presented that proves the feasibility and scalability of our approach. Finally, we provide a discussion on different scenarios supporting the discovery of interesting patterns and their application. All the experiments were carried out on an Intel Core i7 CPU 2.50 Ghz machine with 16 GB RAM. Code was written in JAVA using the CHARM implementation from the SPMF framework [START_REF] Fournier-Viger | SPMF: a java opensource pattern mining library[END_REF].

A. Dataset

Any action performed during a match is stored afterwards in a file (replay), allowing to re-watch the game at any time. We were kindly provided with a collection of 9.193 replays from the dotabank.com website. Different replay parsing tools are freely available. In our setting, we used Skadistats Clarity 2 parser2 .

Only traces from non-anonymous players were considered (unknown steam id). For this reason we obtain a bit less than 10 traces per game in average, for a total of 90, 366 traces. We have a total of 77, 112 different players and thus, a skewed distribution of heroes played and (playerID, hero) pairs (given in Figure 5 left and middle in the first row). These distributions shall influence the choice of scenarios for defining Reference Models. Heroes played the most (≥ 2, 000 times) are Mirana, Phantom Assassin, Invoker and Pudge. On the other hand, the most frequent (playerID, hero) pairs are: 135 times (XXXX30, Invoker), 56 times (XXXX45, Lycan), 55 times (XXXX45, Furion), 51 times (XXXX06, Techies) 3 . The hero with the highest number of traces is Invoker with 2, 090 in total, and 135 traces for a unique player. : this is why we choose to focus on these game traces in what follows.

B. Reference models

Because of the mobility assumption discussed in Section IV we will use positioning to determine our Reference Models.

The Web site [START_REF]Worlds 2015 viewership[END_REF] presents a study which aggregates the positions of 10, 000 matches of League Of Legends into a single map. Three phases (early, middle and late game) can be easily recognized in the aggregated game, where players occupy different regions of the map. This study also discusses on different roles for heroes occupying different regions of the map, namely carry and support in the bottom lane, mage in the center, tank/melee in the middle lane, and jungler on the whole map. We focus on the early phase of the game as positioning is crucial at this step.

We constructed several Reference Models that we present in Figure 4. For each, we consider 33 well known POI in DOTA2 (bases, shops, center of the map, towers, ...). Models are built for some of the most played heroes in our replay collection. For example, Invoker was played 2, 089 times. After computing the POI trajectories, we obtain the graph with edges having a minimum (resp. maximum) weight of 1 (resp. 50, 332) and an average of 731 for dire and 867 for radiant. We use these thresholds to drop non important edges in the graph and present the model for Invoker (radiant team) in Figure 4 (iv). Note that the size of each edge is proportional to the weight. We follow the same process to present models for Mirana 4 (i) and (ii), and Pudge 4 (iii). It can be observed that hero Mirana focuses its moves in the top and bottom lanes (depending of her team). Pudge (in the dire team) mainly plays in the mid lane. Finally, Invoker (radiant team) is a jungler thus more present in the top and bottom jungles.

C. Quantitative experiments

Here we provide evidences of the computational feasibility of our approach. For this matter, we build the largest collections of traces that we could extract from the initial dataset and that were coherent with our approach. Firstly, the Reference Model was built by using the traces of any player using hero Invoker. We will denominate this set of traces as T m where (|T m | = 2, 090). Secondly, the set of traces to be analyzed was built from a unique player, namely the most active player in the collection using hero Invoker. We will denote this set as T (|T | = 135). Finally, trace descriptions are built from a collection of 116 possible items to be purchased during a given match plus 68 different options for upgrade a hero's skills (build). Trajectories built from T contain between 16 and 1, 205 POI, with an average size of 476 POI per trajectory. The distribution of trajectory lengths is shown in Figure 5 (top right). To run the mining algorithm, we need to set several parameters: the minimum frequency σ (set to 1%), the graph weight cut off (set to the average of all weights in the graph) and the θ parameter that allows to split the transaction database into positive T + and negative T -examples. We report the number of transactions in both positive and negative databases, as well as the run time and number of patterns, for several values of θ. It follows that run times are very low, but the number of patterns can be sometimes too high to be analyzed by a Human. Our goal is to get few but accurate negative patterns: We choose θ = 0.008. Negative patterns, denoted by X -are those with a negative normalized discriminant measure. Figure 10 plots the resulting patterns, using a normalized X 2 measure: Interestingly most of the patterns cover normal behaviours while a small proportion has a measure below -0.5. Note that we only reported pattern mining run times. Parsing each replay and processing them into an appropriate format can take more than one second per file. This is however done a single time, and thus we do not take it into account when reporting run times.

With the replay collection we possess, our methodology has no computational issues. Publishers that own massive replay collections can use parallelized versions of pattern mining algorithms in presence of scalability issues [START_REF] Negrevergne | ParaMiner: a Generic Pattern Mining Algorithm for Multi-Core Architectures[END_REF], [START_REF] Moens | Frequent itemset mining for big data[END_REF].

D. Qualitative experiments

In DOTA2, each hero has a specific kind of game play. To win, one has to take choices, in a some order, which differs from one hero to another. Available objects for purchasing provide heroes with powers: some objects are better for some strategies than others. The same applies when choosing abilities. At each level of experience, a player has to choose between different upgrades for his hero. This choice influences the strategy of the player and efficiency of his hero. So called build orders are even shared and discussed on several community websites such as Dotabuff.com. Our purpose here is to provide patterns that inform the player about his choices and their capacity to discriminate the outcome of the game (first scenario) and his mobility behavior (second scenario). We consider the games traces of player XXXX30 using hero Invoker (the most prevalent in our replay collection). In 135 player traces, 69 games resulted in defeat and 66 in a victory, which can be considered as a balanced overall outcome. Each of the 135 traces is described by the objects purchased (I is the set of all available objects). This leads to a database of 135 transactions on which we apply the CHARM algorithm with a minimal frequency threshold of σ = 1%. 390 patterns are extracted in a negligible time. Figure 6 gives for each pattern its frequency in the whole database and growth-rate φ. Recall that the closer is the value of φ(X) to -1, the more discriminant for defeat is pattern X, and vice versa. We can observe patterns with extreme growth-rate values (1 and -1), that is, observed only in victorious or lost games. However, their frequency is very low, actually almost never observed. In contrast, the most balanced patterns appear more often (in 60% of the games). Note that this observation was made in a similar scenario studying balance issues in StarCraft 2 [START_REF] Bosc | A pattern mining approach to study strategy balance in rts games[END_REF]. Table V presents five patterns that appear only in lost games which we compare with a list provided by Dotabuff of the most popular objects purchased by any given hero during the last year 4 . While patterns found through our approach contain objects staff of wizardry,blade mail,healing salve for hero Invoker, these are not very popular in the list of Dotabuff. We can infer fromt his that these five patterns are indeed not very common, probably because of their associated low winning chances.

We conducted a second experiment by taking into account the upgrades chosen at each level by player XXXX30. Thus, I is only composed of pairs (hero level, ability level). Using the same parametrization than in the last experiment, we extracted 177 patterns from which we selected the pattern with the lowest growth-rate. which appears in only 4 traces. Again, we compare this pattern with the upgrade choices statistics collected by the Web site Dotabuff and shown in Figure 7. Each row denotes an upgrade of Invoker while columns denote the level of the hero. A cell thus counts the number of known matches in which a player chose to improve the correspondent upgrade a at the given level. Cells highlighted in green represent discovered patterns. They indicate that player XXXX30 sticks quite well to common behavior in levels 4,7,8,17 and to a lesser extent, level 10. However, it seems that considering upgrade choices and purchased items may be not enough. Indeed, a player may follow well known build orders, but position his hero wrongly on the map. Moreover, match outcomes depend not only on the choices of a single player but also, on the team's. MOBA games are based on team cooperation and positions are very important on the map. In the next scenario, we use a Reference Model that captures positioning as a way to improve the quality of patterns. 4 http://www.dotabuff.com/heroes/invoker/items?date=year

2) Scenario 2 : Patterns of traces that deviate/respect a reference model: In this scenario, we label each player trace with the help of the Reference Models illustrated in Figures 4. As we are studying games of the hero Invoker, we use its model for dire (resp. radiant) when labeling a trace played as dire (resp. radiant). Our goal is to describe sets of player traces that deviate the most from these models. The positive and negative transaction databases are build using θ = 0.008 (as explained in Section V.C.). Like in Scenario 1, we build trace descriptions in terms of (i) purchased objects, (ii) chosen upgrades. In both cases, we have |D -| = 27 and |D + | = 108 while the model was computed on a set of T m = 2, 090 traces. With these settings, and for the case (i) only 39 patterns have a negative growth rate. Support and growth rate for all patterns is plotted in Figure 10. Discriminant patterns for deviant behaviors are shown in Figure 8. Objects robe, sage mask, healing salve and staf f of wizardry are all rarely purchased items when using hero Invoker.

For case (ii), we extracted 91 patterns describing deviant behaviours. We illustrate some of them in Figure 9 which also depicts common upgrade statistics gathered by Dotabuff. In the figure we can observe that the player makes a mistake at level 9, by choosing the ability 3 instead of 2, again at level 12, by choosing upgrade 2 instead of 4, and again at level 14 and at level 16 where his chois is only shared by 4.4% of players. Thus, our method discriminates better the bad and infrequent moves.

VI. RELATED WORK

The analysis of behavioral video game data is not new. However, for a long time it seems to have only provided a test bed for artificial intelligence techniques. For example, the real-time strategy game StarCraft has attracted much attention for the design of intelligent agents and even serves as a test bed for AI to compete through tournaments [START_REF] Ontañón | A survey of real-time strategy game AI research and competition in starcraft[END_REF]. The problem of building an agent able to beat a Human is so hard that it is now an objective for both Facebook AI research and Google Deep Mind.

With the advent of massively multiplayer online-played games, the game industry got interested in analyzing these massive sets of historical data by means of visualization, machine learning and data mining techniques. This is one of the many facets of video game analytics aiming to enhance user experience and extending game lifetime [START_REF] Von | Machine learning and data mining in call of duty[END_REF]. There are several relevant tasks that demand massive data. Identifying imbalanced strategies in StarCraft 2 thanks to pattern mining was recently studied [START_REF] Bosc | A pattern mining approach to study strategy balance in rts games[END_REF]. It is also possible to predict who is playing thanks to keystrokes used by Starcraft 2 players [START_REF] Yan | Masters of control: Behavioral patterns of simultaneous unit group manipulation in starcraft 2[END_REF] and thus to recognize banned players with a new identity [START_REF] Cavadenti | When cyberathletes conceal their game: Clustering confusion matrices to identify avatar aliases[END_REF]. Without being exhaustive, we can also mention the tasks of detecting unexpected situations and bugs [START_REF] Von | Machine learning and data mining in call of duty[END_REF], cheaters [START_REF] Aurangzeb | Mining for gold farmers: Automatic detection of deviant players in mmogs[END_REF], improving match making systems [START_REF] Véron | Matchmaking in multi-player on-line games: Studying user traces to improve the user experience[END_REF], [START_REF] Buchan | A qualitative exploration of factors affecting group cohesion and team play in multiplayer online battle arenas (mobas)[END_REF], designing interactive player advice systems [START_REF] Luiz | Rtsmate: Towards an advice system for rts games[END_REF], understanding when to surrender in a MOBA [START_REF] Claypool | Surrender at 20? matchmaking in league of legends[END_REF], among others. Massive datasets can also be used in eSport analytics, e.g. [START_REF] Franc ¸ois Rioult | Mining Tracks of Competitive Video Games[END_REF], [START_REF] Mahlmann | Esports analytics through encounter detection[END_REF]. Our methodology is useful mainly for the task of understanding player behaviors, and addressed either to a player or to the game publisher. Several works considered the problem of player advising (recommendation) for MOBA and RTS games. Silva et al. presented an approach to help novice players of League of Legends [START_REF] Do | A tutor agent for moba games[END_REF]. The system tracks the player actions and gives tips in real-time, e.g. when the hero's health is too low, his positioning is wrong, etc. They use domain knowledge from expert players to build a decision tree that is used in realtime. Chunha et al. purposes an advisory system to help players in a RTS game [START_REF] Luiz | Rtsmate: Towards an advice system for rts games[END_REF]. They formalized expert guides and also used them for helping the player to master the game more rapidly. In both cases, the systems rely on expert knowledge a priori and manually designed, which can be a tedious task.

Our approach can use either an existing model or derive it automatically from selected game traces. It is however not designed to help the player in real time, but afterwards, when analyzing his games (or those of others).

Anomaly detection is a well-known task in data-mining (as surveyed in [START_REF] Chandola | Anomaly detection: A survey[END_REF]). The task consists in detecting objects which strongly differ from others w.r.t. an outlier measure. There are a lot of applications, e.g. fraud detection in many domains. Contextualized anomaly detection [START_REF] Angiulli | Detecting outlying properties of exceptional objects[END_REF] [30] [START_REF] Duan | Mining outlying aspects on numeric data[END_REF] still considers a set of objects in which outliers are searched for, but also in which context the objects are outliers: a normal object may be an outlier in some subspace of the data. Our approach differs as we are neither looking for outliers or contextualized outliers, but contextual information (or hypotheses) that mostly characterize objects that deviate from a norm.

VII. CONCLUSION

With the recent developments of eSports, the video game industry faces new challenges for developing games attractive for both professional and amateur players. Gamers are in need of data analytic tools that highlight their strengths and weaknesses and help them during a long learning process. For that matter, discriminant pattern mining techniques provide intelligible explanations for several kinds of targets. We developed in this article a global methodology that enable to output strategic patterns explaining victory and explaining deviations from a reference behaviour that can be customized for various scenarios. The choice of a reference model, but also the different features to be encoded in the itemsets and the target given for each trace (game outcome, reference model, ...) makes it indeed customizable. Our choices in these article were mainly motivated by the available of data. It remains thus to further develop this first attempt, and to achieve a deeper experimental validation with several heroes, players, description encodings, but also to involve Human players in the loop. Another issue concerns the lack of data: it is hard to find a sufficient number of replays involving the same players and player/hero pairs.

Figure 1 :

 1 Figure 1: MOBA map

Figure 3 :

 3 Figure 3: Simple expert model for DOTA2. Only edges with an important weight are displayed.

  ) where |.| counts the number of POI of the trajectory (its size) and |trajectory(t)| > 1 secure that the trajectory contains at least one transition. Example. Consider the model G = (V, E) given in Figure 3, and trajectories t 1 = 1, 4, 7, 5, 7, 5, 7 and t 2 = 1, 2, 3, 5, 6, 3 . We can calculate their outlier scores as µ(t 1 , M ) = 1+1+0+0+0+0 7-1 = 2/6 = 0.33 and µ(t 2 , M ) = 1+1+0+1+1 6-1

Figure 4 :

 4 Figure 4: Reference models for early game of: i) Mirana (radiant), (ii) Mirana (dire), (iii) Pudge (dire), (iv) Invoker (radiant)

Figure 5 :

 5 Figure 5: In the first row, several distributions on the DOTA2 dataset (traces by heroes, then by heroes/players, and sizes of behavior part). In the second row, we have several measures in terms of θ: time execution in milliseconds, number of patterns, and number of transactions.

1) Scenario 1 :

 1 Patterns that discriminate the game outcome: In this scenario, we label player traces with positive or negative classes depending on the outcome(t) function. If outcome(t) = {win} then class(t) = {+}, and if outcome(t) = {lost} then class(t) = {-}. We seek to answer our first problem: what are the choices (purchased objects and hero upgrade options), that discriminate a victory or a defeat?

1 FrequencyFigure 6 :

 16 Figure 6: Pattern frequencies and growth-rates (Scenario 1)

Figure 7 :Figure 8 :

 78 Figure 7: Comparing an itemset of skill choices with Dotabuff statistics (Scenario 1)

Figure 9 :FrequencyFigure 10 :

 910 Figure 9: Comparing an itemset of skill choices with Dotabuff statistics (Scenario 2)

  buy X ),(t2, -2077,-1550, move),(t3, -6922,-6185, ab A 1 ) ,(t4, -620,-5963, move),(t5, -6650,-6338, buy Y ), ... winner=No, length=60,... 3 (t1, -6928,-6436, buy X),(t2, -6050,-902, move),(t3, -4825,-6130, move) ,(t4, 10,5962, ab A 1 ),(t5, -4900,-6045, move), ... winner=Yes, length=54,... 4 (t1, -6806,-6334,buy X ),(t2, 25,100, move),(t3, 50,-160, ab A 1 ) ,(t4, -702,-5802, move),(t5, -7105,-6593, buy Z ), ... winner=No, length=35,... 5 (t1, -6896,-6450, move),(t2, -650,-6004, move),(t3, 4890,-5986, ab A 1 ) ,(t4, -598,-5785, move),(t5, -7445,-6985, ab B 2 ), ... winner=Yes, length=38,...

	pid	Traces	Global information
	1	(t1, -6973,-6428, buy X ),(t2, -6742,-5290, ab A 1 ),(t3, -6440,-750, move) ,(t4, -4801,5725, move) ,(t5, -938,563, move), ...	winner=Yes, length=42,...
	2	(t1, -6980,-6440,

Table I :

 I Simplified example of rough game traces

  choosing a, b and c can be interesting for a player as it discriminates victory and as it was played relatively often (f req D + ({a, b, c}) = 66.66%, f req D -({a, b, c}) = 20%). In this scenario, we are interested in itemsets with high support and growth-rate.

Figure 2: Early game positions in League of Legends.

Such positions totally differ in other contexts, see [3] pid Trajectory a Description Description Outlier Score 1 1, 4, 7, 5, 7, 5, 7 {buyX , buyY } {abA 1 , abB 2 } 0.33 2 1, 2, 3, 5, 3, 5, 3 {buyX , buyY } {abA 1 , abB 2 } 0.33 3 1, 5, 7, 5, 7, 5 {buyX } {abA 1 , abB 2 } 0.40 4 1, 2, 3, 5, 3, 6, 3 {buyX , buyZ } {abA 1 , abC 2 } 0.66 5 1, 2, 3, 5, 6, 3 {buyZ } {abA 1 , abC 2 } 0.80 Table IV: Contextualized trajectories: descriptions involves items bought (X, Y, Z) and abilities (A, B, C) taken at level 1 or 2.

Multi-labelled data can also be handled directly, however we omit this model in this article for sake of simplicity.

https://github.com/skadistats/clarity

In order to maintain players anonymity we obfuscate real game ID's maintaining just the last two digits. In this case, both codes finishing with

correspond to the same ID.

ACKNOWLEDGMENTS

This research has been partially funded by the French National Project FUI AAP 14 Tracaverre 2012-2016. The authors warmly thank Rob Jackson and the Dotabank website for providing us with a large collection of DOTA2 replays.


David Dureisseix

Béatrice Faverjon

Anthony Gravouil

A reduced order modeling for uncertainty propagation in the coupled biomechanical model of bone-implant healing process

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

A reduced order modeling for uncertainty propagation in the coupled biomechanical model of bone-implant healing process

David Dureisseix, Béatrice Faverjon, Anthony Gravouil Univ Lyon, INSA-Lyon, LaMCoS, CNRS UMR 5259, F-69621, Villeurbanne, France

Abstract

Uncertainty quantification is a useful approach for robust design and prediction in numerical simulation of engineering problems. Indeed, once a reliable model is available, it can be subjected to variability or lack of knowledge on one or several input parameters, considered as random variables. The model output is then also a random variable and the user is therefore interested in obtaining stochastic information on this model prediction.

Biomechanical problems are prone to such uncertainty, eventually with a large dispersion on the input parameters. The target problem is herein a transient chemical poromechanical coupled problem of parabolic non-linear convection-diffusion-reaction [START_REF] Ambard | A predictive mechano-biological model of the bone-implant healing[END_REF] serving to predict the bone healing around an implant. The goal is to provide a tool for implant design and a help to surgical decision. In this contribution focus is on the case where the deterministic model is considered as a black box: the stochastic analysis should therefore be non-intrusive. Amongst non-intrusive approaches, Monte Carlo simulations and polynomial chaos expansions with collocation [START_REF] Yang | Prediction of the intramembranous tissue formation during perisprosthetic healing with uncertainties. Part 2. Global clinical healing due to combination of random sources, to appear[END_REF] are reference approaches. The inputs are given with their cumulative density functions (cdf), and we wish to build the cdf of the output quantity of interest (QoI).

A reduced order model (ROM) can serve as reducing the cost of the overall analysis. Its efficiency is strongly related to the capability of the QoI to be represented in a smaller subspace. This ability can be improved for geometrical input parameters using a morphing approach. We therefore propose to couple ROM with geometric morphing and stochastic analysis, and assess the effectivity of the approach on the bone healing problem, both from an accuracy and efficiency points of view.


György Kurtág

Grégoire Tosser
email: gregoire.tosser@univ-evry.fr

Giacinto Nono

Jonathan Scelsi

Guus Harvey

Jay Alan Janssen

Richard Yim

Barrett

Signes et rides sont questions et réponses d'une même encre." Edmond Jabès. "La réponse est le malheur de la question." Maurice Blanchot.

Martijn Padding, Horatiu Radulescu, who have written for Uitti using this technique 1 .

1 From Uitti's own internet link : http://radiantslab.com/Uitti/twobows.html. About the two bows function : "The two bows can move independently in a vertical sense : the under bow playing vary close to the bridge while the upper bow is sul tasto. They can slide smoothly to the ordinary position and reverse the sense while moving horizontally. […] The two bows can produce independent articulations, accents, durations, legati etc. […] Due to the thickness and tension of the strings, not all theoretically imaginable 4 note combinations are practical.

An answer to Ives ?

Since the central issue in this piece does consist in a questioning process generating a dialogue, the title "answers", responds to the famous Unanswered Question, the orchestral piece composed by Charles Ives in 1908 1 .

From the general structure of Ives's work, Kurtág keeps the orchestration in groups, the spatial layout, and the natural alternation of question / answer whose substance is less obvious than it is in Ives's case : the patterns of question / answer share a number of features and do not make the job of telling them apart any the easier. The celesta, which turns up only for the three conclusive chords, seems to have no correspondent in Ives's score (Kurtág says that it might be dropped, as for the world premiere) ; this might be an extra component devised by Kurtág in order to answer the question in a final mannerthat is why the subtitle seems to intimate that precisely.

However we shall soon realize that ambivalence prevails in a supreme manner and that the dialectics of answer / question is an issue which transcends the problematic element represented by its oxymoronic title.

On the other hand, the dialogue, in the American composer's work, is completely unfolded between three protagonists : "[The strings] are to represent "The Silences of the Druids -Who Know, See and Hear nothing." The trumpet intones "The Perennial Question of Existence", and states it in the same tone of voice each time. But the hunt for "The Invisible Answer" undertaken by the flutes and other human beings, becomes gradually more active, faster and louder through an animando to a con fuoco", Ives writes in the foreword to the score. Kurtág's ploy is quite clearly not an attempt to comprehend the transcendentalist philosophical temper of Ives's piece : it tends to contemplate the musical expression for a suspended answerthe question may be both answered and unanswered. Let's also put into relief the fact that Kurtág's work is half the length of Ives's (four minutes against eight minutes), and that the tempo variations 1 IVES, Charles, The Unanswered Question, Southern Music Publishing Co. Inc., 246-5, 1953. Luigi Dallapiccola also wrote an answer to Ives (Three Questions with Two Answers, in 1962) : "The three questions are : "Who am I ? Who are you ? Who are we ?" uttered by "three thematic groups of three notes each". […] Of the two answers, the first is peaceful, optimistic and feminine (centred around a flute solo), while the second is harsh, pessimistic and masculine (based on a descending figuration of three notes at wide intervals). The third and final answer is lacking ; to be found only at the close of "Ulysses"." (Foreword to the score, Milan, Suvini Zerboni, S. 8155 Z., 1977). It seems obvious that the Italian composer relies upon lacks, absence, hesitation and the hesitancy and doubt aroused by the absence of the third answer ; not unlike Kurtág's work, Dallapiccola's piece remains open-ended, in the ever defeated expectancy of a conclusive answer. are much fewer and not as marked, which, yet another time, conveys the impression of a kind of slow-moving continuum.

In Ives's piece, the strings and the trumpet stick to largo molto sempre (about 50 on the metronome), while the tempo of the flutes shifts from adagio (bar 20) to con fuoco (53) via andante (26),allegretto (34),allegro (41),allegro molto (47),allegro (accelerando to presto), molto agitando (52-53). The Unanswered Question becomes more and more polyrhythmic, whereas, in Kurtág's work, the rhythmical superposition between the cello and the violins is only effective in the end, and the variations are minimal :

Larghissimo (ma sempre andante), for the cello (bar 1), Poco più lento, strascinato, ma sempre quasi andante, for the intervention of the violins (bar 9), Come prima, ma esitando poco a poco diminuendo al fine, for the cello's return (bar 15), Poco più andante, during the conclusive "tutti" (bar 22).

Further differences crop up between Ives's and Kurtág's pieces. I shall only mention the main ones. In Ives's piece, the strings weave the backcloth of the work, against which the question is stated by the trumpet ; the places where "the invisible answer" can be heard, played by the flutes, are less and less spaced out and more and more substantial. In Kurtág's piece, the cello is interrupted by the violins (poco più lento, strascinato, ma sempre quasi andante), but resumes (middle of page 5), uttering again the initial proposition-question, before conclusion (poco più andante), in a rhythmical superposition with the other participants in the exchange to which the celesta may be added (if it actually plays). This quick clausulaeffectively played by the three groups of instrumentsmight delineate the answer. The difficulty of the rhythmical décalage is less important in Kurtág's piece, as the whole work proceeds in long note values ; therefore, the effect is also toned down. The polyrhythmic perspective is nevertheless present ; besides, Ives's language can be divided in three distinctive parts :

 The strings : triads 1 , ppp.

1 For an analysis of the triads of the strings, see Betsy JOLAS. Molto espressivo. Textes rassemblés, présentés et annotés par Alban Ramaut. Paris : L'Harmattan, 1999. Coll. "L'Itinéraire". "Sur The Unanswered Question", p. 133-137 : "De simples accords parfaits à quatre parties ? Sans doute, mais tels que rarement on ne les entendit, tels certainement qu'aucun traité n'osa jamais les recommander, leurs quatre sons non plus chaudement rassemblés, mais projetés en hauteur le long de colonnes immenses. Longuement immobiles. Le temps d'oublier notre temps quotidien, de se désaccorder. Je commence à comprendre. J'AI OUBLIÉ CE QU'EST UN ACCORD PARFAIT." (p. 134).

 The trumpet : the rhythm is imperceptibly modified through a subtle interweaving of triplets and delayed beginnings. The nuance remains p or pp, and the last note of the melody may change (C or B).

 Finally, the flute quartet wants to achieve complete freedom in relation to the other instruments : the answer is varied, violent, at times fantastic or whimsical, jolly, harsh, in most diverse nuances and tempos. It is essentially different, as it has broken free from a set of constraints ; it asserts and denies itself both on the level of melody and of rhythm. How could we expect any adequation whatsoever between worlds which are supposed to have exchanges within the scope of an "existential" debate ?

Example 2a

An utterance of The Perennial Question to Existence

Example 2b

The Answer to the preceeding Question the answer clears out, runs away and ultimately edges away from any conclusive ending up 1 .

In a similar way, Kurtág's answer will not be satisfying : undermined by this constructive antithesis as it is, the answer can merely reach a certain degree of validity : it can by no means reach out to truth itself ; the radical and astounding antinomy inherent in its title is the hallmark of the concomitant prevalence of the answer and the non-answer. The dialogic form is doomed to hesitancy, vacillation, unending openendedness. Now, does an unanswered question retain its authenticity ? Must it renounce its status as a question or on the contrary does it take on a superior quality which establishes its critical and philosophical validity ?

Dialogue and non-dialogue

The title of this piece shows however that the dialogue actually operates since it literally expresses a link : "ligatura" and "message" imply the notion of contact, connection, exchange and produce an effect of near-redundancy, not unlike the great work in progress Signs, Games and Messages.

With respect to this piece, I will not dwell upon the rhythmic notation which distinguishes Kurtág's own way of writing and which, beyond the scope of measures, shapes the musical language in a fairly precise manner without hindering in any way the outstanding role of the instrumentalist. Because, let us face it, it is also upon duration, in its human, versatile, subjective, changeable forms that the whole of the soundadventure of music is played out and dependent. Conversely, silence plays as important and as emotionalizing a role. With Kurtág, the answer to the question does and does not occur : it seems to spring out from the intimate ties between the instrumentalists, in a flow of nearly complicit understanding. Whereas, in The Unanswered Question, opposition and conflict keep on recurring in sharp outlines, tautology stalks the Ligatura-Messagewhether it be simply bypassed or cleverly statedin view of the changing register of the string instruments (violins or cello).

As a result, the instruments answer each other within a single in camera, and the answer and question seem to melt into one homogeneous consistent discourse : one might describe it as one discursive entity an ever-renewed question / answer pattern. 1 The celesta may utter the answer, but it might be dropped… Yet it is actually upon hesitancy and doubt that the overall design of the piece is built : the wording nags, "bogged down" as it were in an awesome rhythmic regularity. The repetition of chords, whose construction offers striking similarities, paradoxically creates a sort of dissonant emptiness. Everything conspires to intimate malaise and drama, the tense quest of an answer. So, I can suggest that Kurtág made use of his outspoken reference to Ives as a means of disclosing his musical expression of dialogue, of a dialectics of question and answer. It so happens that Kurtág's piece can only emerge in the frame of reference of a virtually expected answer, in the statement of a question whose resolution is pending : the answer would in some way mean the death of the question and the concomitant demise of the musical piece.

A work of art must ever be in search of the "invisible answer", in quest of the truth which rules artistic creation. Ceaseless searching, lack of answer condition the existence of a work of art which lives and expands in the open-ended area (of meaning) discovered by the questioning process ; and this precedes the answer and ultimately the bestowal of meaning. The ruling principles of Kurtág's work might be labelled : link, homage, dialogue, memory, recall. The former are immediately perceptible in title and subtitle ; the latter crop up in the sound-world of a piece which connects both with Ives's problematics of "musical question" and with Frances-Marie [Uitti] whose technique influenced Kurtág's writing. All these items are thus present in Ligatura-Message either on the level of the conditions of its make-up or on the level of its metatextual links. In point of fact, the dialogue is portrayed within the piece where question, answer, silence, doubt, hesitancy are formulated ; but outside the piece, the link between the various instrumental exchanges also wants to be a "ligatura" between the composer and the instrumentalist. So the interpreter alone can weave the "ligature", the mere link into a truly meaningful message. The title straightaway enhances this genuine hyphenation which it behoves the interpreter to animate, to bring to life in the work of art. Valéry used to say that style is "a protracted vacillation between sound and meaning" : in view of this, is not Kurtág's op. 31/b, in some way, a lesson in style ?

Other Ligaturas in Kurtág's production

In this quick presentation, I have not the time to show the links between the Ligatura-Message and the other "Ligaturas" by Kurtág ; actually, the "ligature" is a musical notion and notation that can be often encountered in Kurtág's works ; here are just a few examples of pieces whose title and writing include the term :

 Ligature e versetti, for organ (1990).

 "Ligatura x" and "Ligatura y", from the 6 th volume of Játékok (1993) 1 .

 "Kalandozás a múltban", subtitled "Ligatura Ligetinek születésnapra szeretettel" ("Venturing into the past : a Ligature to Ligeti for his birthday, with love"), in the 7 th volume of Játékok (1997).

 "Ligatura y" also exists in two other versions : one for violin and viola (in Signs, Games and Messages, 1993) and one for string trio (idem, certainly revised in 1998).

 The "Ligatura-Hommage à Yehudi Menuhin" is a piece for two violins (Signs, Games and Messages, 1998). 1 Játékok, vol. 6, Budapest, EMB, Z. 14068, 1997, p. 40-41.

Example 3a

"Ligatura x", Játékok, vol. 6

  […] For the 4 note-chords, the overbow touches D & G, and the underbow A & C." Example 1 Ligatura-Message op. 31/b : the four pages of the score

Example 2c

The Silences of the Druids While Ives's orchestral heterogeneity enhances the various layers of sound, homogeneity prevails in Kurtág's work, where four or five instruments seem to seek a suitable way out. But, despite the lack of excess and hyperbole, the music of the Hungarian composer manages to articulate a malaise through a static stance. Another remarkable fact : the cello and the violins speak the same language, which consists of semitones and fifths ; this paradoxical yet fundamental duality is to be found at every juncture in Kurtág's works. However this is probably the moment when it achieves a greater accretion of meaning since it fits in so perfectly with the aporetic quality of the original question to which there is no such thing as a final answer. Thus, phrases such as tension / release, resolution / non-resolution find a meaning within the chords of Kurtág, that are, most of the time, built up with fifths (i. e. a consonant or neutral element) and semitones (i. e. a dissonant tense element) 1 . Let's repeat that the great difference with Ives lies in the fact that the American composer provides every item in his expression (strings, trumpet, flutes) with a tempo and a musical language of its own. We might well be dealing with a question to which there is no thoroughly suitable answer ; there is no real answer because, from an ironic and multiple viewpoint, 1 The initial chrods of the Ligatura-Message may be built according to the cycle used by Stephen Blum to analyse some Kafka-Fragmente op. 24 (please see his contribution, "Kurtág's Articulation of Kafka's Rhythms"). See also the alternation between the "darkness" of the flats and the "brightness" of the sharps.

Example 3b

"Ligatura y", Játékok, vol. 6

In conclusion, I would say that the open-endedness of the answered unanswered question may be the space of the kurtágian fragment. I am particularly eager to show that Kurtág, in his latest works, celebrates slowness while he does not radically alter his style in relation to his fragmentist productions. The components are reduced to a bare minimum and the development takes place within a single fragment. The key word, in this respect, is amplification within concentration. In the piece I have studied at some length, this amplification is central to the process of production : it is not mosaic-related but it operates from a comprehensive view to the gradual focusing on essential details.

The rhythm of fragmentation seems to be a clue to, and a feature of the existence of a questioning process. The "unanswered question" seems to provide the composer with a pattern, a horizon of expectation into which unexpected elements are inserted ;

ultimately, this appears to correspond to Roman Jakobson's definition of the stylistic feature as "defeated expectancy" : this lays bare, at the core of Kurtág's creative process, the preoccupation with, the search for and the invention of style. Is the Ligatura-Message to Frances-Marie an answer to the "perennial" unanswered question of music ? Samuel Beckett's Comment dire (or What is the word) has no question mark ; Kurtág's answer (if there is one) will certainly not end with a period.