F Tarpin-Bernard

I Marfisi-Schottman

H Habieb-Mammar

AnAmeter: The First Steps to Evaluating Adaptation

Keywords: adaptation degree, evaluating adaptation, adaptivity, adaptability, characterization, quantification

Computer systems now need to be adaptable in order to meet the needs of ever widening populations using a large variety of interactive services and various computer devices in different technical and social environments. This paper presents the online AnAmeter framework that helps characterize the different types of adaptations a system features by helping the evaluator fill in a simple form. The provided information is then processed to obtain a quantitative evaluation of three parameters called global, semi-global and local adaptation degrees. By characterizing and quantifying adaptation, AnAmeter provides the first steps towards the evaluation of the quality of a system's adaptation. AnAmeter is an open tool available as freeware on the web and has been applied to a selection of well known systems.

Introduction

More and more developers are now being asked to design interactive systems which are compatible with a large diversity of users accessing various functionalities and information using a range of different computing platforms. People using computer systems are of various ages and have all different kinds of interests and background knowledge. In addition to traditional desktops, the variety of computing platforms includes mobile telephones, personal digital assistants (PDAs), pocket PCs, wearable and immersive environments and many more. In this context, novel user interface metaphors and interaction styles are emerging.

Faced with this huge set of propositions, it is very difficult to characterize to what DRAFT: TARPIN-BERNARD F., MARFISI-SCHOTTMAN I., HABIEB-MAMMAR H. , ANAMETER: THE FIRST STEPS TO EVALUATING ADAPTATION ,SIXTH WORKSHOP ON USER-CENTRED DESIGN AND EVALUATION OF ADAPTIVE SYSTEMS, UMAP09 USER MODELING, ADAPTATION, AND PERSONALIZATION, TRENTO, ITALY, PP. [START_REF] Picard | Affective Computing[END_REF][START_REF] Coutaz | PAC: an object oriented model for implementing user interfaces[END_REF][13][14][15][16][17][18][19][20]2009 extent a specific application is adaptable. Likewise, it is difficult to explicit the new adaptation features that should be implemented in this system in order to increase its adaptation degree. For these reasons, it is necessary to characterize all the different kinds of adaptations that can possibly exist and define a proper way of quantifying the degrees of these adaptations. In order to accomplish a good evaluation framework, a subjective measure of the user's satisfaction with the adaptation could be added (see Fig. 1). These indicators could be used either for identifying strengths and weaknesses of a system, or for objectively comparing several systems. In this paper, we present a first proposal, AnAmeter, for characterizing and quantifying the adaptation of a system. This tool is largely based on our analysis of the multiple facets of adaptation we will develop in the first section. Then, we present the core of AnAmeter: a grid that helps characterize the adaptations by crossing the adaptation factors and the aspects of adaptation. Based on this grid, we build a quantification technique that provides a measure of the adaptation degree. Finally, the interest, limits and potential extensions of AnAmeter are discussed.

The multiple Facets of adaptation

Many studies have tried to build a taxonomy of adaptive interfaces [START_REF] Brusilovsky | User Modeling and User-Adapted Interaction[END_REF][START_REF] Jameson | Adaptive interfaces and agents[END_REF][START_REF] Calvary | A unifying reference framework for multi-target user interfaces[END_REF]. Based on these works and on a first design space provided by Vanderdonckt & al. [4], we consider that the most important questions to characterize adaptation are:  Who initiates the adaptation?  What are the factors to which the system can adapt?  What aspects of the system are adaptable?

In the next part, we will look at each of these questions in detail and elaborate a list of possible answers.

Who initiates the adaptation?

After using Dieterich's [START_REF] Dieterich | Approaches to Adaptivity in User Interface Technology: Survey and Taxonomy[END_REF] definition of adaptation, Kobsa & al. [START_REF] Kobsa | Personalized Hypermedia Presentation Techniques for Improving Online Customer Relationships[END_REF] identified two possible sources responsible of initiating the adaptation: -The system its-self. In this case the adaptation is automatically initiated and the system is called adaptive. -The user. In this case the adaptation is requested by the user and the system is called adaptable. Usually, the need for adaptation is associated to the notion of context. In the human computer interface (HCI) field, a context is generally described according to three dimensions along which adaptability can be analyzed [START_REF] Calvary | A unifying reference framework for multi-target user interfaces[END_REF]: the user, the platform and the environment. However, a specific user placed in the same environment using the same interaction platform could require some adaptation relevant to his/her activity. That is why, considering our goal, which is to find a way of characterizing and quantifying adaptability and adaptivity, we define four sets of factors of adaptation: user, interaction platform, environment and the activity.

In the next part, we will itemize these four factors of adaptation into sub-factors. The lists of sub-factors are not meant to be exhaustive, but as we will see later, they will help evaluate the levels of adaptation provided by a system. This classification work was done thanks to a detailed reviews of the state of the art and "context of use" definitions provide by standards like IEC CDV TR 61997 [START_REF] Iec Cdv Tr | Guidelines for the user interfaces in multimedia equipment for general purpose use[END_REF] and ISO 9241-11 [START_REF] Iso | Ergonomic requirements for office work with visual display terminals[END_REF]. We also analyzed more than 50 systems found in articles or available in public distribution (complete list on http://liesp.insalyon.fr/AnAmeter/References.php).

User

A User model usually refers to various user characteristics [START_REF] De Bra | AHA! The Adaptive Hypermedia Architecture[END_REF][START_REF] Habieb-Mammar | CUMAPH: Cognitive User Modeling for Adaptive Presentation of Hyper-documents: An experimental study[END_REF]. The user model contains characteristics of a particular user (also called stereotype). We can group these characteristics into four sub-factors: Knowledge and level of experience: The knowledge of an individual user refers to the user's theoretical understanding of the subjects treated in the system. The level of experience refers to the skills acquired to use the system itself. Certain educational systems adapt the content of the lessons to the student's knowledge. Other systems give more helping tips to users that are not familiar with the system. Socio-demographic characteristics and user role: Socio-demographic characteristics such as age, gender, weight, height, wage, profession, hobbies, cultural preferences… are becoming important factors of adaptation for all kinds of systems. When a user asks his GPS for tourist activities in a given area for example, the system will filter the information showing only the attractions compatible with the user's interests and his propensity to spend. In certain cases it is also worthwhile to consider the user's role. For example, a tutoring system can be presented in different ways to a student or to a teacher.

Cognitive abilities and emotional state: The cognitive abilities represent the ease with which the user deals with different modes of perceiving, memorizing, learning, judging etc. Introduced by Picard, R.W. "affective computing" [START_REF] Coutaz | PAC: an object oriented model for implementing user interfaces[END_REF], the emotional state (happy, sad, worried, frustrated, panicked, confident…) is also a very important characteristic to take into account when adapting a system.

Perceptual and motor abilities: These characteristics are useful to enable the systems to be used with disabilities (vision, manipulation, etc.). These disabilities can range from slight myopia or color blindness to total deathless and paralysis.

Interaction platform

The interaction platform describes the physical characteristics of the devices. The major characteristics that a system may take into account are the following:

Computing power and autonomy: Systems often need to be adapted to the platform's processing power and the memory capacity. For some portable devices it is also worthwhile to adapt to the battery level by shutting of certain services for example.

Input/Output device: Some systems are available on a wide variety of platforms. Certain web browsers, for instance, adapt to the different screen sizes and input devices such as mice, keyboards and pens when used on desktops, laptops, or telephones.

Software environment: Computer systems are almost always used alongside other systems on the same platform. These systems can adapt to cohabitate, synchronize and even cooperate with each other. The msn window, for example, can be configured to stay on top of other windows allowing msn to cohabitate with the other applications running at the same time.

Connectivity: More and more systems are now using network connections. The connectivity factor is therefore very important. Systems can adapt to cope with the lake of connection or slow connectivity but we may also want them to adapt to the type of network.

Environment

The third factor is the environment, a term used to cover the physical, social and organizational elements that are outside of the interactive system (platform & user).

Human environment: In some cases, systems can adapt to the other people who are interacting with the user (directly or thru the system). This kind of adaptation can be used for multi-user applications or for applications that detect humans present in the same physical area as the user and who are susceptible of communicating. A camera that automatically widens the view when a second person enters the room is an example of adaptation to the human environment.

Machine environment: This type of environment is defined by any reachable material such as webcams, printers, screens that could be connected on the fly to the main system, but which are not mandatory for the interactive system. Ambient characteristics: It is very common to find systems that adapt their interface colors when night falls (e.g. GPS map systems) but the luminance is not the only aspect of ambient conditions that deserves attention. Systems can also adapt to the temperature, the level of noise and the movements of the device. Spacio-temporal characteristics: Many GPS navigation systems propose potential interesting tourist areas by using geographic latitude and longitude measures. Localisation can also be expressed semantically if the system identifies a specific area such as a room or on a larger scale, the system can adapt to the country, the city or the time zone in which it is.

Activity

The fourth factor is the activity itself. At a micro level, it includes task characteristics and at a macro level it includes the general activity and the user's goal.

Task characteristics: For this sub-factor, the task is considered on its own. The frequency, complexity, dangerousness and confidentiality character of the task can be taken into account to adapt the system. In certain systems, icons and fast links can be added to enable easy access to frequent tasks. Extra warning messages, restoration points and password checking can be used for complex, dangerous or confidential tasks.

Task flow: Here, the task is considered as a part of a tasks flow. The tasks done before, the tasks that will be done after and the tasks done at the same time linked by dependencies can lead to different adaptations of the system. For example, if the user usually does task B after task A, the system might set a quick or automatic launch to task B each time task A is done.

User's goal: The tasks are considered as a whole forming an activity. For each activity, the user can have a different set of goals. For example, when a user is working on Photoshop®, he might be editing the photos, looking at a slide show, sorting the photos or even selecting the best photos to be printed. In all of these cases the goal is determined by the response to the question "Why is the user using the system and what does the user actually want to achieve?".

General activity: If we adopt a more global vision, the general nature of the activity weighs heavily in the successful adaptation of the system. Someone wanting to have fun, for example, will not have the same way of using a system as someone who wants to learn or work. Another dimension that deserves attention is whether the activity is engaged in, on a voluntary basis or out of obligation.

What aspects of the system are Adaptable?

Many aspects of applications can be adapted. We characterize these aspects mainly using the common approach of HCI engineering, PAC (presentation, abstract, control), used by Coutaz [START_REF] Coutaz | PAC: an object oriented model for implementing user interfaces[END_REF]. This model has the advantage of clearly separating the functional aspect of the system called "abstraction" from the interface components called "presentation". The "control" is in charge of linking these two worlds and thus externalizing the means and rules of communication.

In the next section, we clarify these aspects by using an example of a GPS system.

Abstraction

In this part we will be talking about the adaptation of the abstraction, in other words, of the information and the data proposed by the system and the way the different services behave.

Data & information: Adapting this aspect means changing the information and the data used by the system. Let us use our example to illustrate this type of adaptation: a GPS system in a car will give different information when asked for the hotels in the surrounding area. The hotels proposed will depend on the localization of the car.

Service behavior: The services proposed by a system need to adapt to certain circumstances. A company time-table planner for example will authorize the boss to take holidays whenever he wants but will send an approval email and mark the holidays as "to be confirmed" for any other employee.

Control

In this part we will describe the different adaptations that can be applied to the control of a system. The control module is in charge of giving access to the services and data available in the system by interacting in different ways with the user.

Filtering services and data: For various reasons, adaptation might mean limiting the number of services offered or providing only a partial access to a complex service. On our GPS system, for instance, the services to find a tourist attraction are only available when the system is set on "vacation" mode.

Technical choice of interaction: Systems can choose to accept input via many physical devices or by voice or movement recognition. The output can be delivered on screens or loudspeakers. Let us illustrate this type of aspect with our GPS system again: When the car is running, the information on the screen is read out loud by a voice synthesizer.

Presentation

In this part we will discuss the different ways the presentation of a system can be adapted.

Spacio-temporal organization: The elements of information can be arranged in a variety of ways. For example, the GPS system will present the descriptions of the hotels in a specific order by calculating the distance to the hotel or by taking into account the level of comfort wanted.

Presentation aspects: Finally, we get to the outermost layer of the surface, which includes elements such as colors, shapes, as well as the interactive elements such as buttons, boxes, menus... For example, our GPS system will change the colors and the brightness of the screen when night falls. The volume and the type of the voice used can also be adapted for different needs.

Characterizing and Quantifying Tool

As we have mentioned in the introduction, the AnAmeter tool characterizes the adaptation and measures the quantity of this adaptation. It is important to keep in mind that is does not yet measure the satisfaction of the user or the efficiency of the adaptation. In order to build a system widely accepted as a standard evaluating tool it is necessary to provide an open system that has a strong basis to support an iterative and participative building approach. We therefore present AnAmeter as a starting point for developing such a quality scale.

Characterizing adaptation

Using the classification presented in the previous section, we can build a first characterizing grid by crossing the adaptable aspects versus the factors of adaptation. This grid can be used to break down types of adaptability as well as the types of adaptivity (Fig. 2). Each factor (respectively aspect) is divided into sub-factors (respectively sub-aspects). The sub-factors and sub-aspects are also broken down into elements. For ease of presentation, we have not drawn these last subdivisions but each cell of the main grid contains a smaller grid composed of these elements which refer to the finest grain of description. Each lower level cell corresponds to the question "Does this aspect adapt to this factor?" If this is the case then the cell should be checked. For example, the system tested in Fig. 3 adapts the "size of the text" and the "type and color of the background" to the users "myopia". Some of these questions might not make very much sense in certain situations or for a specific type of system. This is why we add a N/A (non-applicable) option. The N/A box can be checked if the adaptation does not seem logical or if it is not a desirable adaptation for the system. For example, an evaluating system such as the BULATS test (http://www.bulats.org/), meant to be used in a closed environment without access to internet or other software systems does not really need to be adaptable to the connectivity of the platform. The cells corresponding to adaptations to connectivity are therefore considered N/A. AnAmeter will take this into account when calculating the mean adaptation degree by ignoring these cells.

The complete evaluation requires filling out the grid and therefore answering a long list of questions. In order to ease the work of the evaluator and speed up the process, we have built an online tool for handling the grid that only requires the evaluator to check boxes. The tool is available online at http://liesp.insalyon.fr/AnAmeter. For the first evaluations we carried out on four well known systems, filling out the grid took about 60min. Fig. 2 : Characterization grid v1.0. with an example of the main grid and a smaller grid containing aspect and factor elements. To fully test a system, 2 grids like this have to be filled in, one for the system's adaptability degree and one for the system's adaptivity degree.

Quantifying adaptation

Now that we have built a grid to characterize the adaptability and the adaptivity of a system, we want to quantify these adaptations.

Once each cell of the smaller grid relevant to sub-aspect B and sub-factor C is filled in, an adaptation degree A B/C ranging from 0 to 3 is automatically calculated according to the number and distribution of the boxes checked using the rules detailed in Table 1.

For example, Fig. 2 shows the small grid of the sub-aspect "presentation aspects" and the sub-factor "perceptual/motor abilities". Once the evaluator clicks on the OK button, the adaptation degree A presentation aspects / perceptual, motor abilities will be automatically calculated according to the number and position of the ticks entered in the grid.

Table 1 : Scoring process for the adaptation degree.

Degree Meaning Reading in the grid Example

A B/C = 0

The system does not have this type of adaptation. No checked boxes.

A B/C = 1 One aspect is adapted to one factor. One checked box.

A B/C = 2
One aspect is adapted to several factors or several aspects are adapted to one factor.

Checked boxes only on one row or only on one column.

A B/C = 3 More than two aspects adapt to more then two factors.

Checked boxes on at least two rows and two columns.

When all the cells in the main grid relevant to the aspect B and the factor C are filled in with a score of 0, 1, 2 or 3, a local adaptation degree, LA B/C is determined by calculating the average of these scores. The N/A cells will not be considered in the calculations. The results is then converted into a percentage as shown in equation n°1 (100% corresponds to a score of 3 in all the cells). One all the local adaptation degrees A B/j relevant to an aspect B are calculated, the semi-global aspect adaptation degree AA B can be found with equation n°2. In the same way, equation n°3 is used to determine the semi-global factor adaptation degree FA c relevant to the factor C.

n LA AA j B B / j {factors} (2) n LA FA C i C / i {aspects} (3)
Finally, the global adaptation degree, GA, is determined by taking the average of the semi-global adaptation degrees -either of all the aspects or of all the factors -as shown in equation n°4.

n FA n AA GA j i j {factors} i {aspects} (4)
To enable easy understanding of these adaptation degrees, we then identify the aspects and the factors by using the first letter of their name. Also, the adaptation degree relevant to adaptivity (self-adaptive) will be marked with an apostrophe (LA' C/A , GA'…). AnAmeter provides an overall score for the adaptation degree of the system yet also provides sub-scores (local and semi-global). This is very useful for systems that are specialized in a certain type of adaptation.

Discussion

Our proposal for characterizing adaptation is to use a scoring matrix in order to quantify local, semi-global and global adaptation degrees a system. The advantages of this tool are:

1) Its simplicity. The user fills out the grid by answering simple Boolean questions of the following type: does a precise aspect of the system adapt to a precise factor? Clear examples with references are available for each type of adaptation. The resulting grid and charts are automatically generated.

2) Its precision. The tool provides precise local evaluations. This is very useful for specialized systems that concentrate on one aspect of adaptation. AnAmeter also allows for the possibility of evaluating the system from two fundamental different points of view: adaptability (user-initiated adaptation) or adaptivity (automatic system-initiated adaptation).

3) Its ease for comparing adaptive systems. The final result grid can be compared to any other result grid. In addition, AnAmeter has already been used to evaluate the adaptation degrees of four well-known systems. These evaluations available on the web platform can therefore be used as a basis for further comparisons. 4) Its extensibility and flexibility. Our idea was to offer a robust basis for the community to build on. The architecture of our tool makes it easy to extend by adding other elements or refine it by dividing the sub-categories or extending the measuring scale to 0-5 or 0-10. 5) Its accessibility. AnAmeter is freely accessible on the web along with a selection of completely tested systems and more than 300 examples of adaptation types (http://liesp.insa-lyon.fr/AnAmeter). This makes it possible for the same system to be tested by several evaluators who could then combine their results to obtain a mean value for the adaptation degree.

Although AnAmeter has many advantages, the fact that the approach tries to be as complete as possible extends the time required to evaluate a system to approximately one hour. Indeed this first version of the grid contains 22 aspect elements and 59 factor elements which adds up to more than a 1000 Boolean questions to answer for a highly adaptive or adaptable system. Of course, for most of the systems, entire sections of the grid will be left out or marked as non-applicable, greatly reducing the amount a work. By creating an online tool that enables easy manipulation of the grid and calculates the adaptation degree automatically, we have lightened the task but it is still represents quite an investment of time and effort. We hope it will be possible to improve the grid with the scores and the comments of people who use it.

Future work

We believe that building an evaluating tool, widely accepted by the community can only be done in a cooperative way with the help of the members of this community. AnAmeter was created to serve as a basis for building on and this is why we created an open, extensible and flexible online framework.

In the near future, we plane on adding a subjective measure of the user's satisfaction of the adaptation to establish a global evaluation mark as seen in the first section (see Fig. 1) In order to do this, AnAmeter can be reconfigured so that, instead of indicating if the adaptation is available or not by checking the boxes, the evaluator will enter a measurement of his or her satisfaction.

Another Idea is to ask people with different user profiles to test the same system in order to see if the results coincide or not. This will allow us to measure the reliability of AnAmeter.

If the system is fully developed, the designer might also want to ask a user to evaluate the system with AnAmeter to see if he is aware of all the adaptable (userinitiated) options and if the adaptive dimensions (automatic system-initiated) have been noticed. The next step is to test the AnAmeter tool for ease of use by asking other people to use it to evaluate systems on their own and send us feedback. Now that AnAmeter is available on the web is should be easy to launch an evaluation campaign. A simple questionnaire could be added to know if the evaluators found the system clear and easy to use.

Conclusion

In this paper, we present AnAmeter, a tool to characterize the multiple facets of adaptability and a quantification technique to measure the adaptability degree of an interactive system. We discuss the multiple facets of adaptation, primarily the aspects and factors of adaptation that serve as parameters. Then, we suggest the use of a scoring matrix to evaluate local, semi-global and global adaptation of an interactive system. We provide a first version of the scoring technique and simple formulas for calculating these adaptation degrees. The AnAmeter tool is presented as a starting point for the community to cooperatively build a widely accepted framework for evaluating any kind of adaptable or adaptive systems.

Figure 1 :

 1 Figure 1: The three steps to evaluating a systems adaptation

2 . 2

 22 What are the factors to which the system can adapt?

  to B and C m N/A cells relevant to B and C(1)

Fig. 3 :

 3 Fig. 3 : Example of local, semi-global and global adaptation degrees.

Fig. 3

 3 Fig. 3 illustrates these equations: Local adaptation of the control to the activity: LA C/A = 33.33 % Adaptation of the presentation aspect: AAp = 20.83 % Adaptation to the platform factor: FAp = 27.78 % Global adaptation of the system: GA = 19.79 %


Nazim Fatès
email: nazim.fates@loria.fr

Does Life resist desynchronisation?

Introduction

Undoubtedly, Conway's Game of Life -or simply Life -is one of the most amazing inventions in the field of cellular automata. Forty years after its discovery, the model still fascinates researchers as if it were an inexhaustible source of puzzles. One of the most intriguing questions is to determine what makes this rule so particular among the quasi-infinite set of rules one can search. According to W. Poundstone, "Conway wanted to create a game that would be as unpredictable as possible, yet with the simplest possible rules" [START_REF] Poundstone | The Recursive Universe[END_REF]. Still, what kind of intuition struck Conway when he designed the model? Was it mere chance or is a method for designing a simple rule which yet leads to a surprising behaviour? Is the Life rule somewhat related to real life, and if it so, can we discover models of equal richness by observing natural phenomena?

Our long-term objective is to analyse how the properties of the Life rule are related to the properties of natural systems. In other words, we ask whether Conway's Life resists structural perturbations, where structural means that the perturbations modify the interactions of the components interaction instead of modifying their states. In this paper, our aim is to examine whether the Life rule verifies an important property of living organisms: their robustness to desynchronisation, i.e., their ability to keep a constant behaviour when the updating of their components is modified. We thus study the behaviour of an asynchronous version of Life on a regular and an irregular topology.

To date, these issues haven't received much attention. One reason to explain this lack of interest is that Conway's model is generally considered as a simple metaphor without any serious connection to real life. It is thought of as an example which illustrates how basic local rules can produce a complex and unpredictable behaviour. However, even if the model is metaphor, we want to know if asynchronism allows us to discover novel interesting properties. The next section introduces some bibliographical landmarks to see how this issue has been tackled so far.

A brief History of the Problem

The idea to test how Life resists noise dates from as early as 1978 with paper by Schulman and Seiden [START_REF] Schulman | Statistical mechanics of a dynamical system based on conway's game of life[END_REF]. They examined how the introduction of a stochastic element in the local evolution rule would perturb the long term evolution of the system. They replaced the deterministic transitions p k,swhich are equal to 0 or 1 if a cell in state k with s lives neighbours dies or leaves -by p k,s (T ) which are the probabilities to be in state 1 at the next iteration. They take p k,s (T ) = (p k,s + d.T )/(1 + T ) , where d is the current density and T is the stochastic parameter, named "temperature" by analogy with the physical parameter. Interestingly, this parameter is chosen such as not to influence the evolution towards increasing or decreasing the density. The main drawback with this approach is that the definition of the probabilities of transition p k,s is not local: the density should first be computed using the state of the whole grid before the transitions are determined. Nevertheless, the authors analyse the perturbed model with first order and improved mean-field analysis. Their findings can be summarised by saying that: (a) the mean-field analysis fails to predict the evolution of the classical deterministic Life but succeeds with high-temperature models ; (b) more surprisingly, the analysis shows that a phase transition exists which separates two regimes: depending on the value of T , the system is either attracted to the null density or to an attractor of density d * = 0.37. However, a deeper analysis of this phase transition remains yet to be achieved.

Adachi et al. also proposed a modified version of Life. Their model takes into account a "temperature" as a stochastic parameter and uses continuous values for the cells' state [START_REF] Adachi | The Game of Life at finite temperature[END_REF]. The authors show that there are some stable patterns, such as gliders, which resist a finite amount of noise.

Tackling the question of how Life is affected by asynchronous updating, Bersini and Detours [START_REF] Bersini | Asynchrony induces stability in cellular automata based models[END_REF] proposed a qualitative study of the model under fully asynchronous updating, i.e., when the updating is sequential and cells are chosen randomly and uniformly without any memory (see [START_REF] Fatès | Fully asynchronous behavior of double-quiescent elementary cellular automata[END_REF] for a classification of rules with this updating scheme). The authors observed that Life's behaviour was qualitatively altered by the change of updating. They deduced that asynchrony had a stabilising effect since they could observe the emergence of "labyrinth" patterns that would eventually allow the system to reach a fixed point. However, no systematic study of the phenomenon was conducted, in particular the authors did not examine how this stabilising effect scales with the size of the grid.

The first quantitative study of the change of behaviour was conducted by Blok and Bergersen [START_REF] Blok | Effect of boundary conditions on scaling in the "game of Life[END_REF]. They examined Life with the α-asynchronous updating, i.e., when each cell has a probability α to be updated at each time step. They identified a continuous change of behaviour of the model depending on α. More precisely, they found that Life displays a second-order phase transition which belongs to the directed percolation universality class (see below). In this paper, we will proceed to similar experiments but with a different protocol.

Finally, let us mention the stochastic variant of Life which was introduced by Monetti and Albano: they modified the local rule by adding probabilities p s and p b for survival and birth, respectively [START_REF] Monetti | Critical edge between frozen extinction and chaotic life[END_REF]. This change produces a firstorder irreversible phase transition between an "extinct" state where no cell is alive and a "live" state where some structures persist. An improved mean-field analysis was developed to support the experimental observations [START_REF] Monetti | First-order irreversible phase transitions in a nonequilibrium system: Mean-field analysis and simulation results[END_REF].

We now present formally our model, where, in a first step, the perturbations apply only to the updating procedure (and not to the transition rule). Our starting point is thus similar to the study by Blok and Bergersen, we then extended our scope of analysis to a greater range of conditions.

Asynchronous Life

Let us consider the square grid L = {1, . . . , L} × {1, . . . , L} with periodic boundary conditions (the space is a torus). The state of a cell c ∈ L at time t is denoted by σ t c ∈ {0, 1}. Each cell c ∈ L is associated with its neighbourhood N (c) ⊂ L. We use the 8-nearest neighbours topology:

N (c) = {c ′ ∈ L, |c ′ x -c x | = 1 or |c ′ y -c y | = 1}
. The local rule is the function which gives the next state of a cell according to the state of its neighbours. In the case of Life and its variants, it is defined as an outer-totalistic function, i.e., the application of the local rule on a cell c is a function of only two variables: σ t c and s = c ′ ∈N (c) σ t c ′ . A general expression of the local transition rule of Life is stated with two threshold rules:

• birth rule: a cell in state in state 0 becomes a 1 iff s ∈ [B l , B h ];

• survival rule: a cell in state in state 0 remains a 1 iff s ∈ [S l , S h ];

where the thresholds B l , B h , S l , S h are non-zero integers. The original Life is defined with the thresholds B l = 3, B h = 3, S l = 2 and S h = 3.

Classically, the model isdefined with a synchronous updating, i.e., all cells are updated at each time step. In this paper, we will also consider the asynchronous updating, i.e., only a fraction of cells are updated at each time step. There are various ways of considering asynchronous updating in cellular automata. Here, we will consider two simple schemes:

(a) the α-synchronous updating [START_REF] Fatès | An experimental study of robustness to asynchronism for elementary cellular automata[END_REF]: at each time step, each cell will be updated with probability α or left unchanged with probability 1-α. (b) the fully asynchronous updating [START_REF] Fatès | Fully asynchronous behavior of double-quiescent elementary cellular automata[END_REF]: at each time step, one cell is chosen uniformly at random and updated, the other cells are left unchanged.

The probability α is called the synchrony rate. When α = 1 we have the classical synchronous updating, the system is deterministic. For α < 1, the system becomes stochastic. In order to compare the different simulations, we use the rescaled time τ defined as τ = t/α for the α-asynchronous updating and τ = t • n for the fully-asynchronous updating. Intuitively, for α → 0, the α-synchronous updating and the fully-asynchronous updating become equivalent under the time rescaling. Indeed, the probability that two neighbouring cells are simultaneously updated becomes negligible, which allow the two processes to be mapped one onto the other given the appropriate transformation. However, note that this is valid only for a bounded rescaled simulation time ; if we consider infinite-time evolutions of the system, the equivalence may not hold any more. Formally, we model the asynchronism by specifying the set of cells which are updated at each time t. This is done by using a function ∆ : N → P(L). For a fixed updating scheme ∆, the global transition function F ∆ : {0, 1} L → {0, 1} L associates a configuration σ t c to its successor σ t+1 c according to:

∀t ∈ N, ∀c ∈ L, σ t+1 c = f (σ t c , s) if c ∈ ∆(t) σ t c otherwise where s = c ′ ∈N (c) σ t c ′ ,
and f (q, s) is the local transition function defined with:

f (0, s) = 1 if s = 3 0 otherwise and f (1, s) = 1 if s ∈ [2, 3] 0 otherwise .
Using this formalism, we reformulate our objective as an analysis of the behaviour of global transition rule F ∆ depends on the updating scheme ∆. The word "behaviour" has yet to be defined more precisely ; in this article we will mainly use two functions for quantifying changes of behaviour:

• the density d(x) , i.e., the ratio of 1s in a configuration x.

• the activity χ(x), i.e., the ratio of unstable cells in a configuration x.

These two parameters are only rough projections of the state of the system and clearly, they capture only a small part of what one generally expects by saying "behaviour". However, we will see that they give enough information to observe interesting phenomena, especially when qualitative changes of the behaviour of the system need to be detected.

Assessing Life's Robustness to Desynchronisation

We now turn our attention to the evaluation of the robustness of the Life rule. We proceed in three steps: (1) an informal observation of the changes induced by asynchrony, (2) a quantification of these changes, (3) an analysis of the phase transition with the tools from statistical physics.

First Experiment

Figure 1 shows Life's steady state typical configurations for three different updating schemes. It illustrates the influence of the updating on the behaviour of the system: we see that for the asynchronous updating, a new type of pattern has emerged. We call these patterns labyrinths ; their presence on the grid depends on the synchrony rate α: for α > 0.9, no labyrinth pattern appears, for α < 0.9, the lower the synchrony rate, the denser the labyrinth patterns. How can we explain this modification?

We repeated the previous experiment by decreasing α by steps of 5% and we observed that the labyrinth shapes progressively appears when α < 0.9. For α < 0.8, the system rapidly reaches a steady state where the density becomes stable. As α decreases, blank spaces in the steady state disappear in favour of the labyrinth shapes; for α < 0.5, these shapes almost cover the whole grid (see Fig. 1).

A Quantification of the Changes

How does this steady state vary as a function of the synchrony rate? A possible method for quantifying the variation is to measure the average activity of the steady-state. Figure 2 shows the steady state activity χ ∞ as a function of α.

The values are obtained by running a system for a transient of 1000 steps and then averaging the activity of the system for another 1000 steps. It confirms that a qualitative change of behaviour occurs for α ∼ 0.9. As noted by Blok and Bergersen, there also exists a "jump" near α = 1. This discontinuity is the consequence of a modification of behaviour which occurs as soon as a small amount of noise is introduced: some patterns with a short cycle stability (e.g., the blinkers) are destroyed by the asynchronous updating. Noteworthy is the analogy with similar phenomena observed in 1D Elementary Cellular Automata (ECA), see [START_REF] Fatès | An experimental study of robustness to asynchronism for elementary cellular automata[END_REF]. Although for Life, the jump is relatively small (of the order of 0.01), it can be much larger in the case of other cellular automata [START_REF] Fatès | Perturbing the topology of the game of life increases its robustness to asynchrony[END_REF].

If it is easy to explain the change of behaviour near α = 1, the modification which occurs near α = 0.9 is rather puzzling at first sight. What kind of transformation the system undergoes at this critical value?

A Second-order Phase Transition

The first quantitative study of the abrupt change of behaviour in the asynchronous Game of Life is due to Blok and Bergersen [START_REF] Blok | Synchronous versus asynchronous updating in the "game of life[END_REF]. The authors showed that the phenomenon was a second-order phase transition: the macroscopic functions that describe the global behaviour as a function of α are continuous but their derivative are discontinuous at the critical point α c ∼ 0.9. The critical threshold α c separates two well-distinguished macroscopic behaviours called phases. The first phase (α > α c ) is the frozen phase, in which the systems evolves with low-density patterns and quickly stabilises to a fixed point. The second phase (α < α c ) is the labyrinth phase, it is characterised by a steady state with higher density and the absence of a stabilisation on a fixed point (at least for large grid sizes, e.g., for L > 20).

Note that this description is ideal in the sense that it only applies to infinite systems. As simulation imposes to deal with finite systems, how do we then know that we are in presence of a phase transition? This problem is delicate and there exist a great range of methods to answer it. In general, the system is observed near the critical threshold and we measure how a macroscopic description, the order parameter, varies as a function of the lattice size L. Ideally, one should observe that the effect of the lattice size become less and less important, i.e., the order parameter tends to converge to an asymptotic value with regard to the lattice size.

Concomitantly, we should also observe that the order parameter obeys power laws as it gets closer to the threshold. The origin of these power laws comes from the divergence of the system's spatial length scale at the critical point: the system becomes self-similar and its structure follows a fractal pattern. A major discovery in statistical physics is that the power laws that describe the system are not arbitrary: it was observed that very different systems are described by power laws with the same critical exponents. The set of systems which exhibit the same critical exponents is called a universality class. The identification of a universality class is thus a trusted method to show that a brutal change of behaviour is a phase transition (and thus not a mere continuous change in the system's behaviour).

By measuring the value of the steady state activity χ ∞ as a function of the synchrony rate α, Blok and Bergersen demonstrated that asynchronous Life's phase transition belonged to the universality class of directed percolation (see [START_REF] Hinrichsen | Nonequilibrium critical phenomena and phase transitions into absorbing states[END_REF] for a detailed description). Their protocol consisted in measuring a single critical exponent, i.e., they showed that near criticality, the system obeys:

χ ∞ (α) ∼ (α -α c )
β with β being predicted by the directed percolation theory. Although this allowed them to locate the critical threshold at α c = 0.9083, it is well-known in the literature that this method alone does not give precise results [START_REF] Hinrichsen | Nonequilibrium critical phenomena and phase transitions into absorbing states[END_REF]. Indeed, the closer we get to the critical threshold, the longer we need to wait for the system to stabilise to a steady state. This phenomenon, known as the critical slowing down, is difficult to counterbalance. It often introduces systematic biases in the measures, which can not be "seen" by merely computing the uncertainties in the statistical data. In order to avoid the biases of this method, we follow another protocol which was for instance used by Grassberger for linear stochastic cellular automata [START_REF] Grassberger | Synchronization of coupled systems with spatiotemporal chaos[END_REF].

The protocol consists of an interactive process: (a) we fix α and start with a random configuration, (b) we monitor the evolution of the order parameter for a long simulation time until we observe a sub-critical or super-critical behaviour ; (c) we repeat the experiment with a value closer to the critical point until we are not able to observe the difference between sub-and supercritical behaviour.

As we expect the evolution of the order parameter to be a power law near criticality, its evolution should thus appear as straight line on a log-log plot. The value of threshold is not known advance, the values we test are thus either sub-critical or super-critical. The critical threshold is approximated by observing the changes of convexity in the plots displayed in log-log scale: a plot with a positive or negative curvature corresponds to a super-critical or a sub-critical behaviour, respectively. We tested both the density and the activity as an order parameter and observed that the activity gave much better results. Figure 3 displays different evolutions of the steady state activity χ for different synchrony rates. We find that for α = 0.912, the curve bends downwards, which indicates an subcritical regime ("frozen phase"); while for α = 0.910, the curve bends upward, which indicates a super-critical regime ("labyrinth phase"). We thus locate the phase transition at the point α c = 0.911 ± 10 -3 . Note that this value, although close to value given by Blok and Bergersen is not in agreement with their uncertainty range. As said before, we believe that the small discrepancy comes from the biases which exist in the method they have used. Other experiments are now needed in order to settle this value with greater precision. This could be done for example by measuring the dynamical exponents, starting from an initial condition close to the absorbing phase. In any case, for the critical synchrony rate α c ∼ 0.911, we observe a good agreement between the measured slope and the expected value δ = 0.451 which corresponds to the directed percolation critical exponent.

Influence of the Initial Condition on the Asymptotic Behaviour

So far we used only uniform random initial conditions, i.e., configurations where each cell had a probability d ini = 1/2 to be in state 1. For the great majority of dynamical systems, the choice of the initial condition generally has an effect in the outcome of a trajectory. What about the asynchronous Life? For α < α c , do we always observe the labyrinth phase regardless of the initial condition? To deal with this question, we first observe the system behaviour from an experimental point of view. Part of this behaviour is then explained using a mean-field analysis and another part is explained with a close-up on how the labyrinth phase develops from specific parts of the lattice.

Experimental Approach

Bagnoli et al. were among the first authors to examine in details the importance of the initial condition in the evolution of the Game of Life [START_REF] Bagnoli | Some facts of life[END_REF]. For the classical synchronous updating, they detected two sharp transitions in the asymptotic density d ∞ as a function of the initial density d ini . Fig. 4 shows d ∞ = f (d ini ) for the synchronous and asynchronous case (α = 0.5). The asymptotic density is approximated by taking a 100 × 100 grid and measuring the average density during 1000 steps after a transient time of 5000 steps.

The curve obtained for the synchronous case α = 1 displays two sharp transitions. The first one is for a small d ini : there exists a threshold which separates the initial conditions which lead to the "extinct" state (d = 0) from the initial conditions which lead to the "frozen" state (d > 0). Above this threshold, we observe a saturation phenomenon which indicates that the initial density might not have a great importance in the evolution of the system. A symmetrical situation is observed for d ini > 0.8 where the system is again lead to the "extinct" state. Now, if we have a look at the asynchronous updating for α = 0.5, we notice that: (a) the sharp transition for low d ini is still present, which shows that the labyrinth phase is not always attained, even for α < α c , (b) the sharp transition for high d ini has disappeared. How can we explain these two phenomena?

Mean-field Analysis

Since the evolution of many cellular automata is difficult or impossible to predict analytically, one might need some approximations to make such a mathematical analysis possible. One of the simplest approximations is the mean-field method, which consists in neglecting all spatial correlations. The mean-field analysis is equivalent to considering an infinite system were the cells would be redistributed randomly at each time step.

Let us assume that the density is d at time t and let us calculate the density d ′ at time t + 1. Since the updating is asynchronous only a fraction α of the cells will be updated. In this subset of updated cells, a cell in state 0 will transform into a 1 (proba. p 01 ) if and only if it has 3 neighbours (among 8) in state 1. Similarly, a cell that in state 1 will turn into a 0 (probability p 10 ) if and only if it has not 2 or 3 neighbours. Consequently, we obtain the following set of equations:

d ′ = d + α[(1 -d).p 01 -d.p 10 ]
We have 6 ] This results in:

p 01 = C 3 8 d 3 (1 -d) 5 and p 10 = 1 -[C 3 8 d 3 (1 -d) 5 + C 2 8 d 2 (1 -d)
d ′ = d + α d [84 d 2 (1 -d) + 56 d 3 (1 -d) 5 -1]
We can remark that the solutions points of this equation (d' = d) are the same in the synchronous or asynchronous regime. This implies that the meanfield analysis does not give us any information on how the system is affected by the asynchronous updating! Intuitively, we can observe that if the system is at equilibrium, no matter how many cells are updated since the density of the set of updated cells will not vary. From the mean-field viewpoint, the synchrony rate α acts only as a dilution factor and this why we need to study experimentally the effect of α. For α=1, we obtain the well-known mean-field analysis with two solutions: d -= 0.19 is a unstable point while d * = 0.37 is a stable one. In the limit α → 0, we simply obtain the identity function; intermediate values result in a "hybrid" function between these two extremal cases. Obviously, the decrease in the synchrony rate mainly affects the evolution of initial configurations with high densities. This observation explains the difference in behaviour between low and high values of α: for a small α, only a small fraction of the cells are updated, the density progressively decreases until it reaches the first stable point. By contrast, when α is large, the density goes in one step below the stability limit d * and the system is attracted to the frozen state d = 0. Now that we have explained what happens for high densities, let us turn our attention to the other side of the curve. Is there a phase transition for small values of d ini ? Recall that a necessary condition for having phase transitions is to observe a threshold whose position is independent of the grid size. The observations confirm the existence of a strong increase of the asymptotic density d ∞ as a function of d ini . However, there is here no clear "signature" of the presence of phase transition as we see no infinite slope appearing for a given threshold value of d ini . Instead, as the size increases, the slope of the curve also increases but threshold simultaneously seems to be "translated" to the left. Moreover, starting from low-d ini initial conditions, it is possible to observe that the labyrinth phase develops from very specific parts of the lattice that we call germs, by analogy with crystallography where the germs refers to the elements which can initiate a crystal growth. In order to support our claim that there is no phase transition here, let us analyse how the labyrinth phase develops onto the grid. In a previous paper, we showed that it was possible to predict the shape of the curve d ∞ = f (d ini ) by studying how the germs developed on an empty grid [START_REF] Fatès | Perturbing the topology of the game of life increases its robustness to asynchrony[END_REF]. We considered all 3×3 germs and examined what was the probability of seeing each germ expand and fill the whole grid, i.e., be the source of the labyrinth phase. The probability of seeing the labyrinth phase was then obtained by grouping the germs according to their number of 1s, and by relating this number to their probability of presence on the grid as a function of the initial density d ini .

A Close-up on Small Initial Densities

We now propose a slightly different method, which is less demanding in simulation time. Instead of studying the 2 3 * 3 = 512 germs one by one, we will simply set the initial density d ini and then initialise a 3 × 3 block of cells with the central cell set in state 1 and the 8 neighbouring cells initialised randomly with initial density d ini . All the other cells of the grid are left in state 0. We then let the system until it either stabilises on a fixed point or it reaches the labyrinth phase. To decide if the labyrinth phase is reached, we use the following criterion: the activity should be higher than the threshold value 0.1. We verified experimentally that this criterion was fulfilled when the labyrinth phase appeared on the grid. The ratio of labyrinth phases attained over the number of samples gives us P germ (d ini ). From this (local) probability, we derive the global probability P LP to observe the emergence of the labyrinth phase as a function of the initial density d ini . To calculate P LP , we assume total decorrelation between the 3×3 patterns. The emergence of the labyrinth phase is then obtained if at least one of the germs is the source of the labyrinth phase. As there are d ini • L 2 such germs in average, an approximation of the probability of emergence of the labyrinth phase P LP is given by: . Figure 8 displays P LP = f (d ini ) for the fully asynchronous updating scheme and for different lattice sizes. We see that the shape of the curves obtained are similar to the curves of Fig. 6. The curves can be divided into three parts a slow increase for small d ini , followed by a sharp increase for a small range of d ini and then a saturation for higher values of d ini . As the steady state density reached for α = 0.5 is close to 0.38, we observe a qualitative agreement between the plots of Fig. 6 and those of Fig. 8. This agreement pleads in favour of the non-existence of a phase transition: indeed, if the germ hypothesis is correct, as soon as we have d ini > 0, the probability that the labyrinth phase appears and from a germ which "invades" the whole lattice is non-zero, and this probability increases (non-linearly) as a function of the lattice size. These observations can be extended to any α < α c : the probability to observe the labyrinth phase tends to 1 as the grid size tends to infinity. In short, for α < α c , there exists no phase transition with regard to the variation of d ini . We leave the question open for α > α c , in particular for the synchronous case α = 1 (the question was raised by Bagnoli et al. [START_REF] Bagnoli | Some facts of life[END_REF]).

P LP (d ini ) = 1 -[ 1 -P germ (d ini ) ] diniL 2

Extensions of the Asynchronous Game

Our examination so far was limited to a Life rule with a desychronised updating but with a regular topology and with its classical definition. In this section, we examine how the behaviour of the asynchronous Life model is affected either by a change of topology or by a change in the thresholds which define the local rule.

How important is a regular topology?

In a similar way that perfect synchrony is not a realistic assumption, it is also possible to question if a perfectly connected grid where each cell has exactly the same number of neighbours is "realistic" (see [START_REF] Fatès | Critical phenomena in cellular automata: perturbing the update, the transitions, the topology[END_REF] for a short survey related to this question). In a previous paper, we tackled the question and examined if Life's phase transition was still present if we removed links randomly between a cell and its neighbours. We observed that this operation had a surprising effect: the location of the critical threshold α c was lowered as the rate of missing links ǫ -was increased. Simultaneously, the phase transition became less and less visible and for ǫ ∼ 10%, the phase transition was no longer observable [START_REF] Fatès | Perturbing the topology of the game of life increases its robustness to asynchrony[END_REF].

Following the same protocol as described in Sec. 4.3, we performed simulations to test how the phase transition was modified for the missing links perturbation. We verified than the directed percolation was conserved, at least for ǫ -< 6%. For this range of perturbation, the critical threshold α c decreases linearly with ǫ -. For a greater amount of perturbations (ǫ -> 6%), we face a "blurring effect", i.e., the phase transition becomes more and more difficult to observe and the critical threshold is hardly located. Similar phenomena were recently observed on a stochastic version of the Greenberg-Hasting cellular automaton [START_REF] Fatès | Robustness of the critical behaviour in a discrete stochastic reaction-diffusion medium[END_REF]. It is an open question to explain how this loss of precision results from the lattice perturbations.

We observed that the phase transition was also perturbed when links were randomly added in a local way, i.e., when some neighbours are counted twice. Similarly, Huang et al. observed that rewiring the links randomly in the lattice (a link has a given probability to be rewired to a cell chosen uniformly in the lattice) produces the same type of phase transition as the asynchronous updating [START_REF] Huang | Networkinduced nonequilibrium phase transition in the "game of life[END_REF]. It is an interesting problem to determine how the non-local topological perturbations and the asynchronous updating combine.

How "Frequent" is the Sensibility to Desynchronisation?

It is now time to go back to our initial question: what is there so special about the Life rule? We saw that it displayed a great sensitivity to its updating scheme and that the evolution of the synchronous and asynchronous systems strongly depended on the initial density. Can this be considered as a "signature" of a complex behaviour? If this is the case, then we would have a novel method to search the infinite space of CA rules for Life-like behaviour. We leave the question open to stimulate further research, but before coming to the conclusion of this paper, let us indicate a few facts. The Kaleidoscope of Life rule, which was identified by Adachi et al. as being a Turing-universal rule [START_REF] Adachi | Kaleidoscope of life: A 24-neighbourhood outer-totalistic cellular automaton[END_REF] also has a second-order phase transition which is produced by asynchronous updating. The critical threshold appears at α c ∼ 0.89 and separates an "extinct" phase were patterns tend to disappear and an "active-sparse" phase with more or less regularly dispersed live sites (see Fig. 9). For this rule, the presence of a phase transition induced by asynchronism raises a challenging question: is it a mere coincidence or is there some possibility of establishing an "equivalence" of behaviour between the two models? (Also note the proximity of the two thresholds.)

To have a larger panel of rules, we briefly explored the larger space of Lifelike rules, where the thresholds are varied. Let us denote by L abcd the CA rule defined with birth thresholds B l = a and B h = b and survival thresholds S l = c and S l = d. We found out numerous rules which display asynchronyinduced phase transitions. We indicate for instance the rules: L 1756 , L 3643 , L 3312 , L 3636 , L 3666 , etc. although there seems to be some "regions" in the rule space where phase transitions are more densely found, we have no clue yet whether there exists a common property shared by these rules. different snapshots which display the qualitative changes of behaviour when varying the synchrony rate α. We observe that various type of transitions are seen. For L 1756 , we even observe two phase transitions: from a "sparse" phase to a "dense-labyrinth" phase and then to an "order-striped" phase. Interested readers may consult the paper by Regnault et al. [START_REF] Regnault | On the analysis of simple "2d" stochastic cellular automata[END_REF] for similar observations and the study by de la Torre and Mártin [START_REF] De La Torre | A survey of cellular automata like the "game of life[END_REF] for other Extended-Life behaviour in the synchronous case.

Discussion & Openings

We studied an asynchronous version of Conway's Game of Life where the cells were updated with partial of full asynchronism. We showed that the variation of the synchrony rate α and initial density d ini leads to the evolution of the system into qualitatively different steady states, the phases, which we identified as the extinct, the frozen and the labyrinth phases. There exists a critical synchrony rate α c , which separates the frozen phase (α > α c ) from the labyrinth phase (α < α c ). This change of behaviour was identified as belonging to the directed percolation universality class, a sign which indicates that the behaviour near the critical point is difficult to predict analytically. Using numerical simulations, the critical threshold α c was estimated to α c = 0.911. We also analysed the dependence of Life on the initial condition and showed that the initial density d ini was a key factor for predicting the evolution of the system. Here also, for a given lattice size, there exists an abrupt change which depends on the value of d ini : for α < α c , the emergence of the labyrinth phase is a random process which depends on a complex mechanism that is only partially understood. We proposed to analyse this mechanism by focusing on the "germs", i.e., small "islands" of cells in state 1 in a "sea" of cells in state 0. The analysis allowed us to understand qualitatively how the labyrinth phase emerges from the germs, but the quantitative predictions have still to be improved. At any rate, these results suggest -by contrast with asynchronythat the abrupt change of behaviour for d ini is not a phase transition, i.e., there exists no critical initial density that would separate the labyrinth phase from the frozen phase. Finally, we examined how these observations could be generalised to other systems close to the asynchronous Life. As a first step, we indicated that perturbing the topology affected the phase transition by shifting the value of the critical threshold and by making it more difficult to observe (the "blurring effect"). We also provided a list of a few other rules similar to Life where asynchrony also induced phase transitions.

In short, examining the robustness of Life to desynchronisation led us to discover many non-linearities in its behaviour depending on the degree of synchrony and on the initial condition. The mystery of Life is still out there and it is an open question to determine if similar rules can be found in the infinite space of CA rules.

  synch. upd. α = 0.5 fully-asynch. upd.

Fig. 1 .

 1 Fig. 1. Snapshots of configurations obtained with 3 updating schemes: synchronous (left), α-asynchropnous (middle), fully asynchronous (right). Configurations are taken at time τ = 100 (top) and τ = 200 (bottom).

Fig. 2 .

 2 Fig. 2. Steady state activity χ∞ as a function of the synchrony rate α. Grid size is 100 × 100. Averages obtained with 12 samples.

Fig. 3 .

 3 Fig. 3. Evolution of the activity χ as a function of time ; grid size is 800 × 800, averages are taken with 50 samples. the straight line has slope -δ = -0.451.

Fig. 4 .

 4 Fig. 4. Asymptotic density as a function of initial density ; grid size is 100 × 100.

Fig. 5 .

 5 Fig. 5. Mean-field analysis : d ′ = f (d) for different values of α.

Figure 5

 5 Figure5displays the curve d'= f (d) for different values of α. For α=1, we obtain the well-known mean-field analysis with two solutions: d -= 0.19 is a unstable point while d * = 0.37 is a stable one. In the limit α → 0, we simply obtain the identity function; intermediate values result in a "hybrid" function between these two extremal cases. Obviously, the decrease in the synchrony rate mainly affects the evolution of initial configurations with high densities. This observation explains the difference in behaviour between low and high values of α: for a small α, only a small fraction of the cells are updated, the density progressively decreases until it reaches the first stable point. By contrast, when α is large, the density goes in one step below the stability limit d * and the system is attracted to the frozen state d = 0. Now that we have explained what happens for high densities, let us turn our attention to the other side of the curve. Is there a phase transition for small values of d ini ? Recall that a necessary condition for having phase transitions is to observe a threshold whose position is independent of the grid size.

Figure 6

 6 Figure 6 displays the scaling behaviour of d ∞ = f (d ini ) for different grid sizes and for α = 0.5. The estimation of d ∞ is obtained by averaging 200 samples for which we let the system evolve during 1000 time steps as a transient time and then take the average value of the density for another 1000 steps. The curves obtained for the fully-asynchronous updating are similar, although the density saturates at d max = 0.43 instead of d max = 0.38.The observations confirm the existence of a strong increase of the asymptotic density d ∞ as a function of d ini . However, there is here no clear "signature" of the presence of phase transition as we see no infinite slope appearing for a given threshold value of d ini . Instead, as the size increases, the slope of the curve also increases but threshold simultaneously seems to be "translated" to the left. Moreover, starting from low-d ini initial conditions, it is possible to observe that the labyrinth phase develops from very specific parts of the lattice that we call germs, by analogy with crystallography where the germs refers to the elements which can initiate a crystal growth. In order to support our claim that there is no phase transition here, let us analyse how the labyrinth phase develops onto the grid.

Fig. 6 .

 6 Fig. 6. d∞ = f (dini), close up for small initial densities with α = 0.5. Averages obtained with 200 samples.

5. 4 250 Fig. 7 .

 42507 Fig. 7. Colonisation of the grid by a germ. The grid size is 50×50, the synchrony rate is α = 0.5, the random configurationw was obtained wityh initial density dini = 0.10.

Fig. 8 .

 8 Fig.8. Estimated probability PLP to observe the labyrinth phase as a function of the initial density dini using the "germ" approximation for α = 0.5 (see text).

Fig. 9 .

 9 Fig. 9. Three snapshots from the evolution of Kaleidoscope Life : (top) α = 0.90 critical synchrony rate ; (bottom) α = 0.50 super-critical rate

Fig. 10 .

 10 Fig. 10. Snapshots from the steady-state of Extended Life rules.


I Marfisi-Schottman

A Sghaier

S George

F Tarpin-Bernard

P Prévôt

Towards Industrialized Conception and Production of Serious Games

Keywords: Author environment, conception methods, evaluation, scenario modeling, Serious Games

Serious Games (SGs) have experienced a tremendous outburst these last years. Video game companies have been producing fun, user-friendly SGs, but their educational value has yet to be proven. Meanwhile, cognition research scientist have been developing SGs in such a way as to guarantee an educational gain, but the fun and attractive characteristics featured often would not meet the public's expectations. The ideal SG must combine these two aspects while still being economically viable. In this article, we propose a production chain model to efficiently conceive and produce SGs that are certified for their educational gain and fun qualities. Each step of this chain will be described along with the human actors, the tools and the documents that intervene.

I. INTRODUCTION

HESE past decades, computer games and web applications have become more and more familiar to people, whatever their age, gender or social environment. By taking advantage of this trend, the educational system has evolved to create an innovative generation of learning technology: Serious Games (SGs) [START_REF] Mizuko | Living and Learning with New Media: Summary of Findings from the Digital Youth Project[END_REF]. An American study [START_REF] Prensky | Digital Natives, Digital Immigrants[END_REF] revealed that, on average, students graduating with a bachelor's degree have spent only 5,000 h reading for over 10,000 h playing video games and 20,000 h watching TV! Games have always been used to develop intelligence and build knowledge. Why would they not systematically be used for learning even with adults [START_REF] Crawford | The Art of Computer Game Design[END_REF]? Games have the power to immerge learners into a world where they have to invest themselves intellectually and mentally to progress, face challenges or accomplish quests. The objective of a SG is to teach; the game dimension only serves to enhance the effectiveness by catalyzing the learner's attention. SGs add a new dimension to teaching by combining the two fundamental pillars of education: action and emotion. In traditional learning, only the parts of the brain dedicated to problem resolution, vision and speech are used, whereas SGs also stimulate the emotional, and sometimes, physical zones as well. SGs have two other undeniable advantages: the power to adapt to the learner and unlimited patience. The scenario, the level of difficulty, the speed of progression, and the nature of the internal elements of the game… everything can be adapted to the knowledge and preferences of the learners, or to their handicaps.

Riding the wave of user-friendly, intuitive home and portable consoles such as the Nintendo Wii [4] and DS [5], a wide range of commercial SGs have been developed. These SGs, developed as mini reflex games [START_REF]Ninja Reflex[END_REF] or logical enigmas [START_REF]Touch-Generation[END_REF] are supposed to train reflexes and develop memory and logic faculties. Even though their fun qualities are widely recognized, their educational value has yet to be proven. Meanwhile, cognition research scientists have been developing their SGs in such a way as to guarantee an educational gain. However, the fun, attractive characteristics they feature are often hampered by old-fashioned graphics and monotonous interactions. How can we bring together the best of these two worlds to design SGs that are certified for their educational gain and fun qualities? In addition, to have commercially viable SGs, their conception and production needs to be rapid and efficient. This is all the more important knowing that the market span of SGs, due to their specific educational goals, are often very limited, thereby reducing the potential profits as compared to video games.

II. MAIN ISSUE

SG production is a long process involving multiple actors. No specific protocol has yet been developed resulting in the use of methods designed for video games (on the one hand) or educational systems (on the other hand), that are then patched up in an effort to adapt them to the needs of SGs. The production starts by a conception phase during which domain experts, pedagogical experts and cognitive experts build a mock-up model of the future SG. The mock-up model is then transferred to the production team (programmers, graphic designers, actors, sound managers…) that build the first version of the SG called a prototype. This step is very time-consuming, all the more so as it is impossible to invest in mass production the way big video companies do. The prototype is then tested on a representative test group. This phase can go on for months or even years. The collected feedback triggers an important amount of recoding work to correct the errors and, sometimes, even the conception of the scenario needs to be rethought. In this last case, the SG will have to be resubmitted to the conception team and the production team.

For all these reasons, and based on our conception and production experience with a dozen SGs [8], we can say that the whole process lasts about three years (to obtain approximately 10h of learning) and the total cost comes out to approximately 15,000€ per hour of SG. These figures were also confirmed by several video companies .To minimize the constraints related to money and time, we must come up with a rapid and efficient production chain for SG conception and production.

The SG scientific community is probably now in a position to meet this challenge. Over these past fifteen years, researchers have acquired enough experience in the production of SGs to share their techniques and pursue new ambitions [START_REF] Akkouche | Conception et génération de jeux d'entreprise[END_REF] [START_REF] Babari | Approche générique pour la conception et l'ingénierie de jeux d'entreprise multimédias coopératifs -Cas du jeu de la maintenance multimédia[END_REF]. SGs are becoming more and more popular due to the fact that they apply to new domains and therefore captivate the interest of a number of scientific and professional communities. It is the ideal moment to propose efficient and effective production methods for future SGs. It would also be wise to collaborate with video game companies and, in general, with all industrial companies that are used to dealing with time and money constraints.

To efficiently produce SGs that are certified for their educational value and fun qualities, we propose, in this article, a production chain model. In the next section, each step of this chain will be described along with the human actors, the tools and the documents that intervene.

III. PRODUCTION CHAIN

A. Global view

To show all the different factors involved, we decided to apply the 5M classification, often used in industrial engineering: Method, Milieu, Manpower, Machine and Material [START_REF] Isaksson | The measurment system resource as support for sustainable change[END_REF]:  Method: overall organization of the different production steps also including the flow of material input and output and the intervention of human actors.  Milieu: all the elements of the external environment that intervene on the production of the SG such as domain experts (professors, doctors, engineers…), freelance subcontractors (graphic designers, actors, sound managers…) or the learners and the tutors (tests and feedback).  Manpower: the team of human actors that is employed to work on the production chain. To facilitate comprehension, these actors will be described by their function (pedagogical expert, programmer…) although these various roles may in fact be detained by a single person.  Machine: set of tools that will assist the human actors to produce the SG.  Material: documents, mock-up models, executable files, data bases and all other artifacts that will be used as material to manufacture the final SG. Fig. 1 illustrates the different steps of the SG production chain by using the previous classification. The next section describes the different steps in chronological order.

B. General description of the production chain

The production process starts with the client's request for a SG that meets his specific needs (Fig. 1, phase 1). The project manager is in charge of making sure the different steps of production are followed and done according to the cost and time constraints set by the client. The next phase is the conception of a mock-up model of the SG and its pedagogical quality control (Fig. 1, phase 2 and 3). As these two phases are the center of our research, will be described them in detail in section IV.

The mock-up model is then passed on to the production team (Fig. 1, phase 4) composed of programmers and freelance specialists such as graphic designers, actors, film directors, sound managers; etc. All the members of this team collaborate together thanks to a global planning tool that helps them synchronize their work, communicate and share documents. After this phase, the SG prototype is then validated by a coherence control and debugging phase (Fig. 1, phase 5).

The prototype is now ready to be trialed on a representative test group (Fig. 1, phase 6).. This phase is certainly very time and money consuming but it is still essential. We can nonetheless make it much more efficient by using a testing platform that can automatically collect the tracking data of the tests and analyze them with Data mining techniques. After having spotted any existing problems, the pedagogical expert must resolve them by notifying the responsible members of the production team.

Once the SG has gone through all the preceding steps, it can be certified for its pedagogical value and fun qualities. The person in charge of the SG sessions (tutor or student) can then create accounts, plan and set up group playing sessions and perhaps even personalize certain parameters if the SG design allows it (Fig. 1,phase 7). If problems are encountered by the tutors or learners, they must be able to contact the production or conception team. Most SGs are designed to be online applications so they will support maintenance setups. It is also possible to equip the SG with a hidden tracking system to extract quality indicators, allowing the SG to be improved with time.

IV. CONCEPTION AND PEDAGOGICAL QUALITY CONTROL

A. Extracting the domain-specific knowledge

The first step of the conception phase consists in extracting the domain-specific knowledge that is to be learned by the students. To do this, the cognitive expert works with domain experts to extract and formalize the most important knowledge and techniques in a given domain. The experts are often provided by the client.

B. Creating the scenario, the learner's profile and the toolbar

Once the pieces of knowledge specific to the domain are clearly specified, the pedagogical expert assembles them in such a way as to identify the principal ones, define the pedagogical objectives of the SG and conceive a scenario that will allow learners to acquire them. This is where the SG research knot lies. Cognitive scientists have been working on didactic methods of teaching for years. They have managed to characterize different "learning moments" that make up the learning scenario [START_REF] Chevallard | Analysis of teaching practices in anthropological didactics theory[END_REF] but it seems impossible to extract the essence of a "good" learning scenario. By collecting scenarios from SGs and courses that have proven to be effective, we hope to identify some successful "learning moment patterns" or at least identify best practice rules for building learning scenarios.

In addition to this issue, another challenge is raised by SGs: introducing fun into the learning scenario. Inspired by research on video gaming, film scripting and the art of storytelling, we have characterized a number of "entertaining moments" in the same way we identified "learning moments". The global SG scenario is then defined as the combination of an entertaining scenario and a learning scenario one on top of the other. As shown in fig. 2, the global SG scenario is then broken down into modules. The three different scenarios involved will be written with the help of a scenario editing tool. If the SG supports adaptation, the expert will also have to specify the different paths that can be taken and the determining criteria. The experience we have acquired in our research laboratory (a dozen SGs designed, tested and currently used in classrooms to train future engineers) leads us to identify several different types of scenarios (board, adventure, investigation game…). Our objective is to collect frequent SG types that could be used as a base to build on. For each module of the scenario, the expert then has to specify the sequence of activities the learner will have to follow.

Simple activity editors could be set up with editing interfaces, allowing pedagogical experts to create their own activities with a generic model. A number of micro-activity editors have already been put together for puzzles, crosswords, voting systems, brainstorming sequences, etc. These micro-activity editors are currently being collected and normalized so they can be integrated into any SG. Any activity, whether it be a micro-activity, an activity or a module (sequence of activities), is described by a metadata file that explains its use characteristics. Each activity can then be linked to several activity editors. The editors will be chosen in accordance with the pedagogical experts' experience with programming and the degree of adaptation they need. Let us illustrate this concept with a crossword puzzle: non-programmer pedagogical experts will choose a crossword editor with a simple editing interface that allows them to change the background color and the vocabulary used for the crossword whereas, if needed, computer scientists will choose a crossword editor that gives them access to the source code and thereby enables them to change all the elements of the cross word activity (presentation aspects, scoring techniques, words used, images…). The activity editors are therefore also tagged with metadata that specify the activities they can be applied to, the level of adaptation they offer and the minimum programming knowledge required for using them.

The different activity editors are placed in a library and accessed though a service oriented architecture (SOA) [START_REF] Bell | Service-Oriented Modelling: service analysis, Design, and Architechture[END_REF]. As Daniel Schneider concludes in his article [START_REF] Schneider | Conception and implementation of rich pedagogical scenarios through collaborative portal sites[END_REF], this is indeed the ideal method to access editors of different grain (applying to micro-activities, activities, modules…) that cannot be hierarchically classified.

The pedagogical expert then has to define the learner's profile by indicating the different pedagogical objectives to achieve and the mechanism for calculating the scores of each activity. He can also add extra indicators to measure the learner's behavior (paths followed, speed of action, number of times he clicked on a particular button…).

To finalize the conception, the expert has to edit the toolbar with the different tools accessible to the learner all through the game (help module, access to the history of game, pedagogic tools…).

C. Editing the storyboard and specifying the virtual world and characters

The scenario is then structured in acts and scenes and enhanced with elements that make the SG fun (story, characters, intrigue, quest…). We propose to use theatre vocabulary to distinguish these activity sequences.  Act: The SG is usually split into acts of approximately the same size (as concerns time and information). Each act is dedicated to one pedagogical objective.  Scene: Subdivisions of an act in which there are no modification of characters or environment. A scene usually corresponds to a game interaction. The scenario is therefore structured into logical sequences of activities that will be executed in order by the learner. Fig. 3 shows an example of an XML Act file. A raw XML description file of this type is not very easy to handle for a pedagogical expert. Our objective is therefore to provide an editing tool with a visual interface adapted to SGs. The interoperability will be insured by the use of existing specifications such as IMS-LD [START_REF] Koper | Learning Design: A Handbook on Modelling and Delivering, Networked Education and Training[END_REF] and editors like Reload [START_REF] Reload | Reusable Learning Objects Authoring and Delivering[END_REF] or MOT+ [START_REF] Paquette | Learning Design based on Graphical Knowledge-Modelling[END_REF]. Once the scenario has undergone all these modifications, it is called a storyboard. The artistic director then has to describe all the visual, sound and other presentation aspects. The ideal solution would be to use a communication charter to maximize the chances of having clear, precise specifications for the various specialists (graphic designers, actors, film directors, sound managers…) As a result of this conception phase, the mock-up model of the SG, composed of the storyboard and the different specifications of the gaming aspects, contains all the necessary information to start production.

D. Pedagogical quality control

To minimize the testing phases, we intend to set up a preevaluation of the SG before it is actually produced. A first set of tests can be run on the storyboard graph to make sure there are no dead-end paths and that all paths insure that the learners acquire the main pedagogical objectives. For a more thorough testing, we can model virtual players that will act in accordance to their level of knowledge and their specific behavioral profile (curious, prudent, hasty, confident…) [18][19]. For the time being, this method exists only for board game type SGs that have a very formalized and simple structure, but it should be applicable to other types. The objective of these simulations is to statistically evaluate the SG in terms of pedagogical gain. With this system, we hope to be more efficient then when testing is only done on real people at the end of the production, which usually results in going through the production chain again.

V. CONCLUSION AND PERSPECTIVES

In this article, we propose a production chain model to efficiently conceive and produce SGs that are certified for their educational value and fun qualities. We propose various tools to help the human actors do their tasks in a rapid and efficient way. The idea of activity editors that will allow activities to be generically created is also brought up. For each step of the SG production chain, we have presented the different tools that presently exist. We now have to determine to what extent they may be used and modified to answer our particular needs. We will also have to determine a format for the different material and artifacts (documents, data base, XML…) used by these tools so that they can be integrated into the global interoperable structure.

Fig. 1

 1 Fig. 1 Global vision of the SG production chain.

Fig. 2

 2 Fig. 2 Learning and entertaining scenario

Fig. 3

 3 Fig. 3 Example of an XML storyboard file