Rebecca Milley
email: rkmilley@mathstat.dal.ca

Gabriel Renault
email: gabriel.renault@labri.fr

DEAD ENDS IN MIS ÈRE PLAY: THE MIS ÈRE MONOID OF CANONICAL NUMBERS

Keywords: Combinatorial game, Partizan, Misère, Monoids, Dead-ending

We find the misère monoids of normal-play canonical-form integer and non-integer numbers. These come as consequences of more general results for the universe of dead-ending games. Left and right ends have previously been defined as games in which Left or Right, respectively, have no moves; here we define a dead left (right) end to be a left (right) end whose options are all left (right) ends, and we define a dead-ending game to be one in which all end followers are dead. We find the monoids and partial orders of dead ends, integers, and all numbers, and construct an infinite family of games that are equivalent to zero in the dead-ending universe.

Introduction

In many combinatorial games (two-player games of perfect information and no chance), players take turns placing pieces on a board according to some set of rules. Usually these rules imply that the board spaces available to a player on his or her turn are a subset of those available on the previous turn; games such as domineering, col, snort, hex, and nogo, among many others, fit this description. What sorts of properties do these placement games have over other games? What can be said about their game trees? In 1 arXiv:1212.6435v2 [math.CO] 16 Apr 2013 contrast to a game like maze or konane, placement games have the property that a player cannot 'open up' moves for him or herself, or for the opponent; in particular, if a player has no available moves at some position of the game then they will have no moves in any follower1 of that position. This particular property, which we call dead-ending, is the focus of the present paper.

A left end is a game position with no options for the player we call Left, and a right end is a position with no options for the player Right. A game with no options for either player (called the zero game) is both a left end and a right end. We can thus define dead-ending games as follows.

Definition 1. A left (right) end is a dead end if every follower is also a left (right) end. A game G is called dead-ending if every end follower of G is a dead end. The set of all dead-ending games is denoted E.

In addition to the games listed above, many well-studied positions from normal-play game theory have the dead-ending property: integers are dead ends, and non-integer numbers, all-small games, and all hackenbush positions are dead-ending. The set of all dead-ending games is thus a meaningful (and large) universe to consider. Restricted universes are of particular interest to those studying misère games (where the last player to move loses), since the restrictions may reintroduce some of the algebraic structure that is lost in general misère play. The dead-ending universe is a natural extension of the dicot2 universe, which has been the focus of recent research in misère game theory (see [START_REF] Allen | An investigation of misère partizan games[END_REF], [START_REF] Allen | Peeking at partizan misère quotients[END_REF], and [START_REF] Mckay | Misère-play hackenbush sprigs[END_REF], for example).

In this paper we establish some basic results for dead-ending games and demonstrate that several significant subuniverses (ends, integers, and noninteger numbers) have many of the 'nice' algebraic properties that are missing from general misère play. More specifically, we find the misère monoids of these sets of games, and determine the associated partial orders. The concept of a misère monoid, and other prerequisite material, is discussed in Section 1.1.

General misère background

By convention, the players Left and Right are female and male, respectively. Under normal play, the first player unable to move in a game loses; the less-studied and less-structured ending condition known as misère play declares that the first player unable to move is the winner. Games or positions are defined in terms of their options: In both play conventions, the outcome classes next (N ), previous (P), left (L), and right (R) are partially ordered as shown in Figure 1, with Left preferring moves toward the top and Right preferring moves toward the bottom. We use N -, P -, L -, and R -to denote the outcome classes under misère play. We also use the outcome functions o -(G) and o + (G) to distinguish between the misère and normal outcomes, respectively. Many definitions from normal-play game theory3 are used without modification for misère games, including birthday, disjunctive sum, equality, and inequality. Thus, for misère games,

G = {G L | G R },
G = H if o -(G + X) = o -(H + X) for all games X, G ≥ H if o -(G + X) ≥ o -(H + X) for all games X.
In normal-play, the negative of a game is defined recursively as -G = {-G R |-G L }, and is so-called because G + (-G) = 0 for all games G. Under general misère play, however, this property holds only if G is the zero game [START_REF] Mesdal | Simplification of partizan games in misère play[END_REF]. To avoid confusion and inappropriate cancellation, we write G instead of -G and refer to this game as the conjugate of G.

In normal-play games, there is an easy test for equality: G = 0 if and only if o + (G) = P, and so G = H if and only if o + (G -H) = P. In misère-play, no such test exists. Equality of misère games is difficult to prove and is, moreover, relatively rare: for example, besides {• | •} itself, there are no games equal to the zero game under misère play [START_REF] Mesdal | Simplification of partizan games in misère play[END_REF]. As with normalplay, we can reduce a misère game to a unique canonical form by eliminating dominated options and bypassing reversible ones [START_REF] Siegel | Misère canonical forms of partizan games[END_REF], but instances of domination (inequality) and reversibility are much less common under misère play. Plambeck (see [START_REF] Plambeck | Taming the wild in impartial combinatorial games[END_REF] and [START_REF] Plambeck | Misère quotients for impartial games[END_REF], for example) introduced a partial solution to these challenges: modify the definitions of equality and inequality by restricting the game universe. Specifically, given a set of games U , misère equivalence (modulo U ) is defined by

G ≡ H (mod U ) if o -(G + X) = o -(H + X) for all games X ∈ U, while misère inequality (modulo U ) is defined by G ≧ H (mod U ) if o -(G + X) ≥ o -(H + X) for all games X ∈ U.
We use the words equivalent and indistinguishable interchangeably, and if G ≡ H (mod U ) then G and H are said to be distinguishable. If G ≧ H and G ≦ H then G and H are incomparable, and we write G||H. In this paper we use the symbol to indicate strict modular inequality. The set U is often called the universe.

Given a universe U , we can determine the equivalence classes under ≡ (mod U ) and form the quotient semi-group U / ≡. This quotient, together with the tetra-partition of elements into the sets P -, N -, R -, and L -, is called the misère monoid of the set U , denoted M U . It is usually desirable to have the set of games U closed under disjunctive sum; when a set of games is not already thus closed, we consider its closure or set of all sums of those games.

Plambeck and Siegel [START_REF] Plambeck | Misère quotients for impartial games[END_REF] used the monoid approach with much success in analyzing impartial misère games. Allen [START_REF] Allen | An investigation of misère partizan games[END_REF][START_REF] Allen | Peeking at partizan misère quotients[END_REF] extended the idea to partizan game theory, investigating monoids within the dicot universe. Most recently, McKay, Milley, and Nowakowski [START_REF] Mckay | Misère-play hackenbush sprigs[END_REF] determined the monoid for a subset of the dicot universe corresponding to instances of hackenbush, and Milley, Nowakowski, and Ottaway [START_REF] Milley | The misère monoid of onehanded alternating games[END_REF] found the monoid for ends in the universe of alternating (or 'consecutive-move-ban') games. In this paper we make a significant contribution to the literature by determining the misère monoid of all normal-play canonical-form numbers. We find this to be the same as the monoid of the closure of dead ends.

In Section 2 we establish some basic properties of the dead-ending universe. In Section 3 we analyze ends in the dead-ending universe, which includes all integers in normal-play canonical form. In Section 4 we extend this analysis to non-integer numbers and find that the monoid of all numbers is equivalent to the monoid of integers. We also determine the partial orders of these subuniverses (modulo the subuniverse as well as modulo E), and establish invertibility of the elements (modulo E). Finally, in Section 5 we discuss other dead-ending games, in the context of equivalency to zero modulo the dead-ending universe.

Preliminary results

We begin with some immediate consequences of the definition of deadending. Lemmas 1 and 2 show that the universe E of dead-ending games is 'closed' in two important respects: it is closed under followers and closed under disjucntive sum. Lemma 1. If G is dead-ending then every follower of G is dead-ending.

Proof. If H is a follower of G, then every follower of H is also a follower of G; thus if G satisfies the definition of dead-ending, then so does H. Lemma 2. If G and H are dead-ending then G + H is dead-ending.

Proof. Any follower of G + H is of the form G ′ + H ′ where G ′ and H ′ are (not necessarily proper) followers of G and H, respectively. If G ′ + H ′ is a left end, then both G ′ and H ′ are left ends, which must be dead, since G and H are dead-ending. Thus, any right options G ′ R and H ′ R are left ends, and so all options

G ′ R + H ′ and G ′ + H ′ R of G ′ + H ′ are left ends. A symmetric argument holds if G ′ + H ′ is a right end, and so G + H is dead-ending.
Under misère play, Left trivially wins any left end playing first. In general, Left may or may not win a left end playing second; for example, the game {• | 1} is a left end in N -. If a (non-zero) left end is dead, however, then it is a win for Left playing first or second.

Lemma 3. If G = 0 is a dead left end then G ∈ L -, and if G = 0 is a dead right end then G ∈ R -. Proof. A left end is always in L -or N -.
If G is a dead left end then any right option G R is also a left end, so Right has no good first move. Similarly, a dead right end is in R -.

The following lemma, which describes a sufficiency condition for invertibility, applies generally to any misère universe. In the present paper we apply it to various subsets of dead-ending games.

Lemma 4. Let U be any game universe closed under conjugation, and let S ⊆ U be a set of games closed under followers. If

G + G + X ∈ L -∪ N - for every game G ∈ S and every left end X ∈ U , then G + G ≡ 0 (mod U ) for every G ∈ S.
Proof. Let S be a set of games with the given conditions. Since U is closed under conjugation, by symmetry we also have G + G + X ∈ R -∪ N -for every G ∈ S and every right end X ∈ U.

Let G be any game in S and assume inductively that H + H ≡ 0 (mod U ) for every follower H of G. Let K be any game in U , and suppose Left wins K. We must show that Left can win

G + G + K. Left should follow her usual strategy in K; if Right plays in G or G to, say, G R + G + K ′ , with K ′ ∈ L -∪ P -,

then Left copies his move and wins as the second player on

G R + G L + K ′ = G R + G R + K ′ ≡ 0 + K ′ , by induction. Otherwise, once
Left runs out of moves in K, say at a left end K ′′ , she wins playing next on G + G + K ′′ by assumption.

The main argument above begins with the phrase 'suppose Left wins K'. This appears to be ambiguous, or incomplete; does Left win K playing first or playing second? The implied assumption with such a statement is that the argument to follow holds for both cases.

In subsequent sections we refer to the two game functions below, which are well-defined for our purposes -namely, for numbers and ends. In general, left-and right-length are well-defined if G has a non-alternating path to zero for Left or Right, respectively, and if the shortest of such paths is never dominated by another option. The latter condition ensures l(G) = l(G ′ ) when G ≡ G ′ . As suggested above, both of these conditions are met if G is a (normal-play) canonical-form number or if G is an end in E. If l(G) and l(H) are both well-defined then l(G + H) is defined and l(G + H) = l(G) + l(H). Similarly, when right-length is defined for G and H, we have r(G + H) = r(G) + r(H).

Integers and other dead ends

Let n denote the game {n -

1 | •}, where 0 = 0 = {• | •}.
That is, n is the position with the same game tree as the integer n in normal-play canonical form. In this paper the term 'integer' will always refer to such a position. Note that we should distinguish between the game n and the number n, since, among other shortcomings, n > n -1 in general misère play. One property that does hold in both normal and misère play is that the disjunctive sum of positive integers n and m is the integer n + m, although this is not generally true (in misère games) if one of n or m is negative and the other positive. In this section we prove that the restricted universe of integers under misère play has much of the structure enjoyed by normal-play integers. An integer is an example of a dead end: if n > 0 then Right has no move in n and no move in any follower of n. Similarly, if n < 0 then n is a dead left end. Thus, the following results for ends in the dead-ending universe are true for all integers, modulo E.

Our first result shows that when all games in a sum are dead ends, the outcome is completely determined by the left-and right-lengths of the games.

Lemma 5. If G is a dead right end and H is a dead left end, then o -(G + H) =      N -if l(G) = r(H), L -if l(G) < r(H), R -if l(G) > r(H).
Proof. Each player has no choice but to play in their own game, and so the winner will be the player who can run out of moves first.

We use Lemma 5 to prove the following theorem, which demonstrates the invertibility of all ends in E. In particular, this shows that every integer has an additive inverse modulo E.

Theorem 6. If G is a dead end then G + G ≡ 0 (mod E).
Proof. Assume without loss of generality that G = 0 is a dead right end. Since every follower of a dead end is also a dead end, Lemma 4 applies, with S the set of all dead left and right ends. It therefore suffices to show

G + G + X ∈ L -∪ N -for any left end X in E. We have l(G) = r(G) and r(X) ≥ 0, so l(G) ≤ r(G) + r(X) = r(G + X), which gives G + G + X ∈ L -∪ N -by Lemma 5. Corollary 7. If n is an integer then n + n ≡ 0 (mod E).
Note that equivalency in E implies equivalency in all subuniverses of E; thus in the universe of integers alone, every game has an inverse.

Lemma 5 shows that when playing a sum of dead ends, both players aim to exhaust their own options as quickly as possible. This suggests that options with longer paths to zero will be dominated by shorter paths; in particular, we have that integers are totally ordered among dead ends, as established in Theorem 8 below. Note that this ordering only holds in the subuniverse of the closure4 of dead ends, and not in the whole universe E. In fact, we see immediately in Theorem 9 that distinct integers are pairwise incomparable modulo E, just as they are in the general misère universe.

In the following arguments we frequently use the fact that, when H ∈ U has an additive inverse modulo U , G H (mod U ) if and only if G + H 0. Proof. By Corollary 7, it suffices to show n + m 0 (equivalently, k 0 for any negative integer k), modulo the closure of dead ends. Let X be any game in the closure of dead ends; then X = Y + Z where Y is a dead right end and Z is a dead left end. Suppose Left wins X playing first; then by Lemma 5, l(Y ) ≤ r(Z). We need to show Left wins k + X, so that o

-(k + X) ≥ o -(X). Since k is a negative integer, r(k) is defined and r(k) = -k > 0. Thus l(Y ) ≤ r(Z) < r(Z) + r(k) = r(Z + k), which gives k + Y + Z = k + X ∈ L -∪ N -, by Lemma 5 .
In general, G ≥ H under misère play implies G ≥ H under normal play [START_REF] Siegel | Misère canonical forms of partizan games[END_REF]; Theorem 8 shows this is not always the case for misère inequality modulo a restricted universe.

Theorem 9. If n = m ∈ Z then n||m (mod E). Proof. Assume n > m. Then we have n ≧ m (mod E), because n +m ∈ R - while m + m ≡ 0 ∈ N -. It remains to show n ≦ m.
Define a family of games λ k by

λ 1 = {0 | -1}, λ k = {0 | λ k-1 }.
Note that n + λ n ∈ L -, since Left wins playing first or second by ignoring λ n and forcing Right to play there, bringing the game to -1 with either Left or Right to play next.

If n > m ≥ 0 then m + λ n is in P -or R -: Left loses as soon as she plays in λ n , and so plays only in m, but (moving first) she will run out of moves in m before λ n is brought to -1. Thus n ≦ m in this case, since Left can win n + λ n but not m + λ n .

If m < 0 then let k = -m -1 and take X = k + λ n+k . As above, n + k + λ n+k ∈ L -. However, m + k + λ n+k ≡ -1 + λ n+k ∈ N -since each player can move to a position from which the opponent is forced to move to zero. In this situation we see Left prefers n over m, so again n ≦ m.

Theorem 9 tells us that, modulo E, the games {0, 1 | •} and {0 | •} are distinguishable, as the option to 0 does not in general dominate the option to 1. Thus, in the dead-ending universe, there exist ends that are not integers. However, if we restrict ourselves to the subuniverse of dead ends, then the ordering given in Theorem 8 implies that every end reduces to an integer. This fact is presented in the following lemma.

Lemma 10. If G is a dead end then G ≡ n, modulo the closure of dead ends, where n = l(G) if G is a right end and n = -r(G) if G is a left end.
Proof. Let G be a dead right end (the argument for left ends is symmetric). Assume by induction that every option G L i of G (necessarily a dead right end) is equivalent to the integer l(G L i ). Modulo dead ends, by Theorem 8, these left options are totally ordered; thus

G = {G L 1 | •} for G L 1 with smallest left-length. Then G is the canonical form of the integer l(G L 1 ) + 1 = l(G).
Lemma 10 shows that the closure of dead ends has precisely the same monoid as the set of canonical-form integers. The game of domineering on 1 × n and n × 1 strips is an instance of these universes. The results of this section allow us to completely describe the monoid, which we present in Theorem 11. By N we mean the set of natural numbers, including zero.

Theorem 11. Under the mapping n → α n , the misère monoid of the set of normal-play canonical-form integers is

M Z = 1, α, α -1 | α • α -1 = 1 ∼ = (Z, +),
with outcome partition

N -= {0}, L -= {α -n | n ∈ N}, R -= {α n | n ∈ N},

and total ordering

α n α m ⇔ n < m.

Numbers

The monoid of

Q 2 .
We say that a game a is a non-integer number in a universe U if it is equivalent, modulo U , to the normal-play canonical form of a (non-integer) dyadic rational:

a = m 2 j = m -1 2 j m + 1 2 j ,
with j > 0 and m odd. The set of all integer and non-integer (combinatorial game) numbers is thus the set of dyadic rationals, which we denote by Q 2 .

As we did for integers in the previous section, we now determine the outcome of a general sum of dyadic rationals and thereby describe the misère monoid of the closure of numbers. Note that the sum of two non-integer numbers (even if both are positive) is not necessarily another number. For example, in general misère play,

1 + 1/2 = {1/2, 1 | 2} = 3/2 implies that 1/2 + 1/2 = {1/2 | 1 + 1/2} = 1.
We will see that, unlike integers, the set of dyadic rationals is not closed under disjunctive sum even when restricted to the dead-ending universe; however, closure does occur when we restrict to numbers alone.

Lemma 14 below -analogous to Lemma 5 of the previous sectionshows that the outcome of a sum of numbers is determined by the left-and right-lengths of the individual numbers. To prove this, we require Lemma 13, which establishes a relationship between the left-or right-lengths of numbers and their options; and to prove Lemma 13, we need the following proposition.

Proposition 12. If a ∈ Q 2 \ Z then at least one of a RL and a LR exists, and either a L = a RL or a R = a LR .

Proof. Let a = m/2 j with j > 0 and m odd. If m ≡ 1 (mod 4) then

a L = m -1 2 j , a R = m + 1 2 j = m+1 2 2 j-1 = m-1 2 2 j-1 m+3 4 2 j-1 ,
so a L = a RL . Otherwise, m ≡ 3 (mod 4) and then

a L = m -1 2 j = m-1 2 2 j-1 = m-3 2 2 j-1 m+1 2 2 j-1 , a R = m + 1 2 j , so a R = a LR .
Note that if a > 0 is a dyadic rational then l(a) = 1 + l(a L ), and if a < 0 is a dyadic rational then r(a) = 1 + r(a R ). We also have the following inequalities for left-lengths of right options and right-lengths of left options, when a is a non-integer dyadic rational.

Lemma 13. If a ∈ Q 2 \ Z is positive then l(a R ) ≤ l(a); if a is negative then r(a L ) ≤ r(a).
Proof. Assume a > 0 (the argument for a < 0 is symmetric). Since a is in canonical form, both a L and a R are positive numbers. If a L = a RL then l(a R ) = 1 + l(a RL ) = 1 + l(a L ) = l(a). Otherwise a R = a LR , by Proposition 12; then a L is not an integer because a LR exists, so by induction we obtain

l(a R ) = l(a LR ) ≤ l(a L ) = l(a) -1 < l(a).
We can now determine the outcome of a general sum of numbers, both integer and non-integer. Lemma 14. If {a i } 1≤i≤n and {b i } 1≤i≤m are sets of positive and negative numbers, respectively, with

k = n i=1 l(a i ) -m i=1 r(b i ), then o - n i=1 a i + m i=1 b i =    L -if k < 0 N -if k = 0 R -if k > 0. Proof. Let G = n i=1 a i + m i=1 b i .
All followers of G are also of this form, so assume the result holds for every proper follower of G. Suppose k < 0. If n = 0 then Left will run out of moves first because Left cannot move last in any negative number. So assume n > 0. Left moving first can move in an a i to reduce k by one (since l(a i L ) = l(a i ) -1), which is a left-win position by induction. If Right moves first in an a i then k does not increase, since l(a i R ) ≤ l(a i ) by Lemma 13, so the position is a left-win by induction; if Right moves first in a b i then k does increase by one, but Left can respond in an a i (since n > 0) to bring k down again, leaving another left-win position, by induction. Thus G ∈ L -if k < 0.

The argument for k > 0 is symmetric. If k = 0 then either G = 0 is trivially next-win, or both n and m are at least 1 and both players have a good first move to change k in their favour.

Lemma 14 shows that in general misère play, the outcome of a sum of numbers is completely determined by the left-lengths and right-lengths of the positive and negative components, respectively. From this we can conclude that, modulo the closure of canonical-form numbers, a positive number a is equivalent to every other number with left-length l(a). In particular, every positive number a is equivalent to the integer l(a). This is Corollary 15 below; together with Theorem 18, it will allow us to describe the monoid of canonical-form numbers.

Corollary 15. If a is a number, then

a ≡ l(a) if a ≥ 0, -r(a) if a < 0.
As an example, the dyadic rational 1/2 is equivalent to l(1/2) = 1, and -3/4 ≡ -r(-3/4) = -2, modulo Q 2 . Note that these equivalencies do not hold in the larger universe of E; indeed, as we see in section 4.2, if a = b are numbers then a ≡ b (mod E).

We see then that the closure of numbers is isomorphic to the closure of just integers; when restricted to numbers alone, every non-integer is equivalent to an integer. Thus the misère monoid of numbers, given below, is the same monoid presented in Theorem 11. The partial order of the set of numbers, modulo E, is described in Section 4.2.

Theorem 16. Under the mapping a → α n , where n = l(G) if a ≥ 0 and n = -r(G) if a < 0, the misère monoid of the set of canonical-form dyadic rationals is

M Q 2 = 1, α, α -1 | α • α -1 = 1 ∼ = (Z, +),
with outcome partition

N -= {0}, L -= {α -n | n ∈ N}, R -= {α n | n ∈ N}.
As with integers, some of the structure found in the number universe is also present in the larger universe E. We end this subsection with a proof that all numbers -not just integers -are invertible in the universe of deadending games. We require the following lemma, an extension of Lemma 14. Lemma 17. If {a i } 1≤i≤n and {b i } 1≤i≤m are sets of positive and negative numbers, respectively, and

n i=1 l(a i ) -m i=1 r(b i ) < 0, then o - n i=1 a i + m i=1 b i + X = L -,
for any left end X ∈ E.

Proof. The argument from Theorem 14 works again, since if Right uses his turn to play in X then Left responds with a move in a 1 to decrease k by 1, which is a win for Left by induction.

Theorem 18. If a ∈ Q 2 then a + a ≡ 0 (mod E).

Proof. Without loss of generality we can assume a is positive. Since every follower of a number is also a number, we can use Lemma 4. That is, it suffices to show a + a + X ∈ L -∪ N -for any left end X ∈ E. If X = 0 this is true by Lemma 14. If X = 0 then we claim a + a + X ∈ L -; assume this holds for all followers of a. Left can win playing first on a + a + X by moving to a L , since l(a L )r(a) = l(a L )l(a) < 0 implies a L + a + X ∈ L -by Lemma 17. If Right plays first in X then again Left wins by moving a to a L ; if Right plays first in a then Left copies in a and wins on a L + a L + X ∈ L - by induction.

Theorem 18 shows that in dead-ending games like domineering, hackenbush, etc., any position corresponding to a normal-play canonical-form number has an additive inverse under misère play. So, for example, the positions in Figure 2 would cancel each other in a game of misère hackenbush.

The partial order of numbers inside E.

In section 3 we found that all integers were incomparable in the deadending universe. We will see now that non-integer numbers are a bit more cooperative; although not totally ordered, we do have a nice characterization of the partial order of numbers in the universe E. First note that any two distinct numbers are distinguishable modulo E; this is an immediate corollary of the following theorem of [START_REF] Dorbec | Dicots, and a taxonomic ranking for misère games[END_REF], which extends a result of [START_REF] Siegel | Misère canonical forms of partizan games[END_REF] referenced earlier. Theorem 19 says that if a ≧ b (mod E) then a ≥ b as real numbers (or as normal-play games). The converse is clearly not true for integers, by Theorem 9; it is also not true for non-integers, since 1/2 -1/2 ∈ N - while 3/4 -1/2 ∈ R -(which the reader can verify), so that 1/2 ≦ 3/4 (mod E). Theorem 23 shows that the additional stipulation l(a) ≤ l(b) is sufficient for a ≧ b (mod E). To prove this result we need the following lemmas. As before, non-bolded symbols represent actual numbers, so that 'a < b' indicates inequality of a and b as rational numbers (or as normal-play games), and a L means the rational number corresponding to the left-option of the game a in canonical form. Recall that if x = {x L |x R } is in (normalplay) canonical form then x is the simplest number (i.e., the number with smallest birthday) such that x L < x < x R . Thus, if x L < x, y < x R and x = y then x is nn y. Proof. We have a L < b < a < a R , so a must be simpler than b. Thus b L ≥ a L , since otherwise b L < a L < b < b R would imply that b is simpler than a L , which is simpler than a.

Theorem 19. [4] If G ≧ H (mod E) then G ≥ H in normal play.
Now, if b L = a L then l(a L ) = l(b L ) = l(b) -1 < l(b), and if b L > a L then by induction a L < b L < b < a gives l(a L ) < l(b L ) = l(b) -1 < l(b).
Lemma 21 is used to prove Lemma 22 below, which is needed for the proof of Theorem 23. Note that in the following two arguments we frequently use the fact that, if a ≧ b (mod E), then Left wins on the position a + b + X whenever she wins X ∈ E. Proof. Note that b ∈ Z since there are no integers between a L and a if a is in canonical form. We must show that Left wins a + b + X whenever she wins X ∈ E.

RL + b R + X ′ = b L + b L + X ′ ≡ X ′ (mod E); if the latter then Left moves to b R + b L L + X ′ = b R + b LR + X ′ = b R + b R + X ′ ≡ X ′ .
In either case Left wins as the previous player on X ′ ∈ L -∪ P -.

When Left runs out of moves in X, she moves to a L + b + X. By Lemma 21 we know l(a L ) < l(b), and this gives a L + b + X ∈ L -by Lemma 17.

L < b ≤ a L and l(b L ) = l(b) -1 ≥ l(a) -1 = l(a L ) implies a L b L (mod E).
If Right plays to a R + b + X ′ (assuming this move exists -that is, assuming a ∈ Z) then Left's response is a

RL + b + X ′ , if a RL > b, or a R + b R + X ′ if a RL ≤ b. In the first case Left wins by induction because a RL > b and l(a RL ) = l(a R ) -1 ≤ l(a) -1 < l(b) implies a RL b (mod E).
In the latter case, note firstly that in fact a RL = b, since we have already seen that as games they have different left-lengths. Then we see a RL < b < a < a R < a RR , which shows a R must be simpler than b. This gives b R ≤ a R , as otherwise b

L < b < a < a R < b R would imply that b is simpler than a R . If b R = a R then b R = a R ,
and if b R < a R then we can apply Lemma 22 to conclude that a R b R (mod E). In either case, Left wins a R +b R +X ′ , with X ′ ∈ L -∪P -, as the second player.

Finally, if Left runs out of moves in X then she moves to a L + b + X ′′ where X ′′ is a dead left end; then Left wins by Lemma 17 because l(a L ) < l(a) ≤ l(b) = r(b).

Zeros in the dead-ending universe

We have found that integer and non-integer numbers, as well as all ends, satisfy G + G ≡ 0 (mod E). It is not the case that every game in E has an additive inverse; for example, * + * ≡ 0 (mod E), although the equivalence does hold in the dicot universe D ⊂ E. Likewise, many familiar 'all-small' games from normal-play, which have inverses in the dicot universe 5 , are not invertible here.

The following lemma describes an infinite family of games that are not invertible in the universe of dead-ending games. Proof. Let X = {n 1 , . . . , n k | •} ∈ R -. Note that G = G. We describe a winning strategy for Left playing second in the game G+G+X = G+G+X. Right has no first move in X, so Right's move is of the form G + n i + X. Left can respond by moving X to n i , leaving G + 0. Now Right plays in G to a nonpositive integer, which as a right end must be in L -or N -.

We conclude with an infinite family of games that are equivalent to zero in the dead-ending universe, which are not all of the form G + G for some G. These games are illustrated in Figure 3.

Theorem 27. If G is a dead-ending game such that every G L is a left end with an option to zero and every G R is a right end with an option to zero, then G ≡ 0 (mod E).

Proof. Let X be any game in E and suppose Left wins X. Then Left wins G + X by following her strategy in X. If Right plays in G then he moves to G R + X ′ from a position G + X ′ with X ′ ∈ L -∪ P -; Left can respond to 0 + X ′ and win as the second player. If both players ignore G then eventually Left runs out of moves in X and plays to G L + X ′′ , where X ′′ is a left end. But G L is also a left end, so the sum is a left-win by Lemma 3.

R R G

j i 1 1 L L G G G

Future directions

From this first initial investigation, the universe of dead-ending games appears to be filled with potential for successful misère analysis. It includes as subuniverses many of the games that have already excited interest among combinatorial game theorists; we hope some of the techniques of the present paper can be fruitfully applied to these subuniverses.

A natural extension of this work would include analysis of specific games, such as nogo, col, snort, etc., in the context of the dead-ending universe. It would also be interesting to consider other properties, besides dead-ending, of the 'placement games' described in our opening paragraph.

  where G L is the set of positions G L to which Left can move in one turn, and similarly for G R . The simplest game is the zero game, 0 = {• | •}, where the dot indicates an empty set of options.

Figure 1 :

 1 Figure 1: The partial order of outcome classes.

Definition 2 .

 2 The left-length of a game G, denoted l(G), is the minimum number of consecutive left moves required for Left to reach zero in G. The right-length r(G) of G is the minimum number of consecutive right moves required for Right to reach zero in G.

Theorem 8 .

 8 If n < m ∈ Z then n m modulo the closure of dead ends.

Figure 2 :

 2 Figure 2: Normal-play canonical forms of 1/2 (left) and -1/2 (right) in hackenbush.

Corollary 20 .

 20 If a, b ∈ Q 2 and a = b then a ≡ b (mod E).

Lemma 21 .

 21 If a and b are positive numbers such that a L < b < a, then l(a L ) < l(b).

Lemma 22 .

 22 If a and b are positive numbers such that a L < b < a, then a b (mod E).

Case 1 :

 1 b R = a. Left can win a + b + X by playing her winning strategy on X. If Right moves in a + b to a R + b + X ′ , then Left responds to a R + b R + X ′ = a R + a + X ′ , which she wins by induction since a RL ≤ a L (see Proposition 12) gives a RL < a < a R . If Right moves to a + b R + X ′ = b R + b R + X ′ , with X ′ ∈ L -∪ P -(since Left is playing her winning strategy in X), then Left's response depends on whether b RL = b L or b LR = b R : if the former, Left moves to b

Case 2 :

 2 b R = a.Note that b R cannot be greater than a, since a L < b < a < a R implies a is simpler than b, while b L < b < a < b R would imply that b is simpler than a. So b R < a, and together with aL < b < b R this gives a L < b R < a, which shows a b R (mod E) by induction. Similarly b RL ≤ b L < b < b R implies b R b (mod E), byCase 1. Then by transitivity we have a b (mod E). With Lemma 22 we can now prove Theorem 23 below. The symmetric result for negative numbers also holds. Theorem 23. If a and b are positive numbers such that a > b and l(a) ≤ l(b), then a b (mod E). Proof. By Corollary 20 we have a ≡ b (mod E), and so it suffices to show a ≧ b (mod E). Again we have b ∈ Z. Since a > b, if b > a L then Lemma 22 gives a b (mod E) as required. So assume b ≤ a L . Again let X ∈ E be a game which Left wins playing first; we must show Left wins a+b+X playing first. Left should follow her winning strategy from X. If Right plays to a+b L +X ′ , where X ′ ∈ L -∪P -, then Left responds with a L +b L +X ′ , which she wins by induction: b

Corollary 24 .

 24 For positive numbers a, b ∈ Q 2 , a b (mod E) if and only if a > b and l(a) ≤ l(b).Proof. We need only prove the converse of Theorem 23. Suppose a > b and l(a) > l(b); then by[START_REF] Dorbec | Dicots, and a taxonomic ranking for misère games[END_REF] it cannot be that a ≦ b (mod E), so we need only show a ≧ b (mod E). We have b + b ∈ N -, while a + b ∈ R -, since in isolation the latter sum is equivalent to the positive integer l(a)l(b), by Theorem 16. Thus a ≧ b (mod E).To completely describe the partial order of numbers within E, it remains to consider the comparability of a and b when a ≥ 0 and b < 0 (or, symmetrically, when a > 0 and b ≤ 0). As before we cannot have a ≦ b (mod E), and the same argument as above (b + b ∈ N -and a + b ∈ R -) shows a ≧ b (mod E) . The results of this section are summarized below.Theorem 25. The partial order of Q 2 , modulo E, is given bya ≡ b (mod E) if a = b; a b (mod E) if 0 < a < band l(a) ≤ l(b), or b < a < 0 and r(b) ≤ r(a); a||b (mod E) otherwise.

Lemma 26 .

 26 If G = {n 1 , . . . , n k | n 1 , . . . , n k } with each n i ∈ N, then G + G ≡ 0 (mod E).

Figure 3 :

 3 Figure 3: An infinite family of games equivalent to zero modulo E (i ≥ 1, j ≥ 1).

By follower we mean any position that can be reached from a given game position, by alternating or non-alternating play, including the original position itself.

In a dicot game (called all-small in normal play), the position and every follower satisfies the property that either both players have a move or the game is over. These games are trivially dead-ending, as no follower can be a non-zero end.

A complete overview of normal-play game theory can be found in[START_REF] Albert | Lessons in Play[END_REF].

Since the sum of a dead left end and a dead right end may not be a dead end (or any end at all), the set of dead ends is not closed under disjunctive sum; thus the universe we consider is the closure of dead ends, as defined in Section 1.1.

The games ↑= {0 | * }, ↓= { * | 0}, and all other day-2 misère dicots with the exception of * 2 = {0, * | 0, * }, are shown to be invertible modulo D in the first author's thesis (in progress), using Lemma 4.

Acknowledgments

The authors greatly appreciate the comments and suggestions provided by Paul Dorbec, Neil McKay, Richard Nowakowski, Aaron Siegel, and Éric Sopena.


Ion Candel

Bertrand Reeb

David Lemon

Cornel Ioana

Electricité de France's study of the acoustic scintillation flow meter results in expanding its range and sensitivity

Introduction

Electricité de France's "Direction Technique Générale" (DTG) branch launched a three-year PhD thesis in order to study the Acoustic Scintillation Flow Meter (ASFM) developed by ASL AQFlow. The study was done in a partnership between EDF DTG (owner of one ASFM system since 2006), Hydro Québec (owner of two ASFM systems) and the manufacturer ASL AQFLow. The partnership aimed at sharing information about the mode of operation and components of the ASFM, as well as sharing the results of the research and development and on-site testing, in order to review the concept of the ASFM and, if feasible, to extend its application beyond its present range. Scientific support was provided by Gipsa-lab, a research laboratory within the Polytechnic Institute of Grenoble (INPG), a major player in the international signal processing community, and the R&D division of EDF located in Chatou, Greater Paris area. In the first two years of the PhD study five major measurement campaigns were performed in France and abroad. In addition, a reduced scale test facility was set up at Gipsa-lab. The main tasks for the PhD candidate were: to review the operational limits for the ASFM, to investigate the impact of various interferences on the discharge measurement, to get a better understanding of the velocity computation algorithm, to develop a method to filter out the scintillation frame vibrations, and to improve the algorithm, if feasible. It is expected that this study may provide the basis for the next generation of acoustic scintillation flow meters.

Background

For EDF's hydraulic power division, turbine flow metering represents a high stake issue as it involves a significant amount of knowhow, work force and physical resources. It was for this reason that in recent years EDF's DTG acquired an ASFM in order to exploit its advantages over the current meters (CM) and other flow metering methods, especially at low head hydro power plants (HPPs). Several situations encountered during on-site tests revealed that unusual flow conditions might arise, which are outside of the present ASFM guaranteed specifications and require further research. Therefore, in 2011, a three-year PhD study was launched, aiming at a better understanding of the ASFM's mode of operation and, if feasible, finding methods to extend the ASFM's capabilities beyond its present range of flow velocities between 0.6 and 6 meters/second. The study was to focus mostly on the signals acquired from the ASFM surface unit and their interaction with the turbulent flow environment. Throughout the study, several on-site tests at EDF's HPPs and under controlled laboratory conditions provided the data set needed for achieving this objective.

First steps

One of the first challenges was to develop an in house acquisition system that would be capable of recording the data from the ASFM. Since the ASFM sequence at one measurement level can take up to 33 seconds, it was necessary to find a multi-channel data acquisition system that would have several important characteristics:

-A high sampling frequency: at least three times the maximum frequency of the signals; -a high transfer rate; -a sufficient resolution so that the sampling noise would be negligible; -a readable file format for the recorded data.

For typical acquisition systems, the above mention characteristics tend to contradict each other: most high sampling frequency devices have a low resolution in order to obtain a high transfer rate. It soon became evident that an off-the-shelf solution would not be available. The quest for a suitable acquisition system found that a joint PCacquisition board would be more suitable for the study rather than any conventional heavy chassis devices. A four-channel 50 MHz bandwidth acquisition board with a 12 bit resolution was chosen. The acquisition board is controlled by a graphic interface on a PC (Figure 1). The initial software of the board was modified in order to better suit the acquisition process.

Fig. 1. Data acquisition system schematics

The onsite acquisition process will benefit also from the ultra high portability of the system.

Replicating the existing signal processing technique

In parallel with the development of the acquisition system, an important stage was to get a full insight into what the ASFM hardware is made up of (electronic design, main blocks and their mode of operation). Constant dialog with the ASFM's manufacturer, ASL AQFlow, allowed for a rapid development of a software replica of the algorithms embedded in the ASFM. The replication of the flow velocity estimation algorithm embedded in the ASFM was carried out in several stages. First, the hardware structure of the ASFM was studied in order to identify the system's components: transducer types, transmission and timing blocks, power sources and the ASFM management unit. An in-depth analysis of individual components was made in order to understand the topology and function of each circuit. Based on the documentation provided by ASL AQFLow, tests points for the transmitted signals were identified. The received scintillation pulses and the calculated envelopes were ready to be recorded. Using the layout presented in Figure 1, the emitted and received scintillation pulses were recorded. The bandwidth of the acoustic transducers was calculated.

Second, a special envelope detection was developed in order to compute the time series: having the entire scintillation sequence recorded, each pulse was passed through an envelope detection routine, prior to maxima extraction. A comparison with the original ASFM time series showed that both time series matched.

However, there is a difference between the two algorithms: the ASFM performs all the calculations in real time and the maxima extraction is done digitally, while the rest of the operations take place in the analog form. Recording the scintillation data means that the time series are not computed instantaneously, but after a certain amount of time. This amount of time can be significantly shortened to near-real time by using fast implementation of the algorithms. Saving the data means that very large databases of signals can be gathered and new ideas can be tested on the computer prior to performing on-site tests.

Additional on-site tests have allowed the development of a new signal processing technique based on spectral analysis, using the scintillation pulses from the ASFM. The resulting time series are, within the guaranteed range, similar to the ones from the existing ASFM algorithm. Starting from the raw data recorded, each individual scintillation pulse was isolated and time series were computed via the standard ASFM algorithm. The resulting time series were compared with the ones issued by the ASFM and the signals matched. Obtaining relevant time series is critical for the flow velocity estimation.

However, in cases of unusual or unfavorable conditions, the re-computed time series are more suitable than the existing ASFM ones for velocity calculation. The modified method extracts more turbulence information by "boosting" the information content relative to the turbulent phenomena. The recomputed time series are based on a spectral approach and it is focused on the signal's features where the turbulence has the maximum intensity. A spectral analysis can also provide information about the content of the acoustic signal during propagation through the turbulent flow.

Low flow velocities and low turbulence

An initial demand for the PhD study was to investigate ways to improve the ASFM's results for HPPs with no thrash racks installed. As illustrated in [START_REF] Lemon | Improvements to the Accuracy of Discharge Measurements by Acoustic Scintillation Resulting from Revisions to Data Processing Procedures[END_REF], [START_REF] Reeb | Investigation of the Performance of Acoustic Scintillation Flow Meter when Turbulence Levels are Low[END_REF] and [START_REF] Lemon | Comparison of Turbine Discharge Measured by Current Meters and Acoustic Scintillation Flow Meter at Laforge-2 Power Plant[END_REF], the low levels of turbulence issue had been investigated before and the robustness and stability of the results were clearly affected.

EDF's R&D department has facilitated a scintillation test under controlled conditions. This test was carried in an 80-meter long channel that allowed control of the flow velocity and had a very low level of turbulence. The flow velocity, however, was outside the guaranteed ASFM range.

Additional turbulence was created using a cable and chain curtain. The elements were 8 centimeters apart in order to simulate a real trash rack of a real EDF's HPP. This created an opportunity to see also the effects of a lateral flow on the scintillation signals.

The first task consisted of fabricating a support frame for the scintillation transducers. The support section was constructed from aluminum-profiled beams. These profiled beams allowed rigid and fast construction and the structure could easily be adjusted vertically and horizontally.

Scintillation transducers were mounted on aluminum sheets attached to the profiled aluminum beam frame (Figure 2). In order to avoid unwanted interference caused by the flow around the aluminum sheets, the edges of each sheet had an arched profile with the arc's angle under 30°, obtaining a hydrodynamic shape illustrated in Figure 3.

The profiling of the aluminum sheets also helped the entire structure to adhere to the channel's walls so that no water flow would occur between the walls of the channel and the metal structure. A silicone layer sealed the interface between the aluminum sheets and the channel walls. Three scintillation levels (three pairs of transducers) were installed with a vertical gap of 30 cm between levels, starting from a height of 30 cm from the channel floor. No protuberance that generated interference existed because all fixation devices were hidden within the aluminum sheets. The transducers were aligned in order to ensure close to ideal measurement conditions.

In order to create different types of turbulence, a cable curtain was placed upstream of the scintillation frame: ten steel cables fixed on a horizontal bar and placed on the top side of the channel (Figure 4). The cables were maintained straight using a heavy steel flat bar which rested on the bottom of the channel. The cables coupling allowed their removal in order to create combinations of turbulent flows.

Fig. 4. Cable curtain upstream of the scintillation frame.

In addition to cables, chains also provided extra turbulence. Chains were successfully used for the scintillation tests at one of Hydro Québec's HPP to increase the level of turbulence [START_REF] Reeb | Investigation of the Performance of Acoustic Scintillation Flow Meter when Turbulence Levels are Low[END_REF]. A combination between chains and cables completed the range of possible turbulence profiles.

The reference flow measurements were carried out using an acoustic Doppler probe (situated on a moving platform on top of the channel) as illustrated in Figure 5. The Doppler probe was submerged under water to provide the horizontal velocity profile for all scintillation levels. The horizontal flow velocity profiles for the three scintillation levels are illustrated in Figure 6: The first tests aimed at studying the behavior of the system without any turbulence caused artificially (with only the low levels of turbulence that was embedded in the flow). Two ASFM runs were made and the results are presented in Figure 7.

It can be seen that the low levels of turbulence, as well as the reduced flow velocity, affected the precision of the ASFM. The Quality Index of the measurements was below 0.5 as anticipated. However, if the same results are processed using the new algorithm, the results improve dramatically, as illustrated in Figure 8.

The low levels of turbulence mean that there is a weak footprint on the amplitudes of signals and the velocity information is not visible. However, the velocity information exists and it can be calculated with accuracy by applying the new signal processing algorithm.

Fig. 8. Flow velocity profiles (blue and red traces) calculated using the new algorithm compared with the Doppler reference (green trace). (natural turbulence)

Given the controlled flow conditions at our disposal, it was necessary to find out how the different types of turbulence created can affect the results of the scintillation measurements (the ASFM and the new technique). Different configurations were considered: placing one cable at a time on the cable curtain in order to quantify the effect of each cable on the results, creating a lateral flow by placing the flat steel bar in diagonal position. A chain + cables curtain was constructed and submerged in water in order to generate a higher level of turbulence.

In the case of turbulence generated by individual chains, the results have shown that the levels of generated turbulence were not enough to produce an improvement in the existing ASFM velocity estimation. However, the results were improved using the algorithm based on the new technique, as illustrated in figures 10, 11, 12 and 13. All the cables were removed in order to study how a single cable and its position can affect the results. Cables no. 1, 6, 7, 8, 9 and 10 were individually placed on the curtain and scintillation signals were recorded. The results (ASFM and new technique) are presented in figures 9 and 10: Figure 9 shows that there turbulence introduced by the cables manifests itself differently on the velocities. Turbulence introduced by cables 1 and 9 (placed at the extremities of the curtain) provides less bias than the cables placed in the middle of the curtain. In addition to that, the low flow velocity, outside of the specification range, does not allow for accurate velocity estimation.

However, using the new technique, the results are closer to the Doppler reference, as illustrated in Figure 10. The velocity points in figure 10 corresponding to all the 10 cables have a reduced scattering compared to the points in Figure 9. The offset between the reference (light green trace) and the scintillation results is significantly lower than in the previous figure.

In the case of a complete curtain (all the cables attached), several configurations were tested: cable curtain, chain curtain, chain curtain + flat steel bar and chain + cable curtain + flat steel bar. The results are presented in Figures 11 and12 Again, Figure 11 shows that the values are scattered around the Doppler reference, with a very high offset between them. Figure 12 shows that the new technique has managed to reduce the scattering of the velocity values and brought them into the reference velocity range. Thus the new technique "filters" the unwanted effects of turbulence and "amplifies" the signatures of turbulence across each acoustic path.

Plotting the error between the Doppler reference and scintillation results for all tests (Figure 13), it can be seen that the new technique provides more stable values than the ASFM. However, we must keep in mind that such flow velocity was below ASFM specifications.

Conclusions

The PhD study confirmed that within the guaranteed range the existing ASFM provides excellent turbine flow measurement results and thus can successfully compete with older techniques. As shown in this paper, when special situations outside of the ASFM range of flows and velocities arise, for which the existing algorithm was not designed, modified version of the ASFM's signal processing algorithm can allow the ASFM to produce accurate results.

An experiment under laboratory controlled flow conditions was carried out in order to compare the results from the two algorithms. The results show that a low level of turbulence, combined with a low flow velocity, both outside the ASFM guaranteed range, can still provide sufficient information for the new processing technique to compute accurate flow velocities with acceptable systematic error and repeatability. While this new processing method has been tested successfully in several power plants, where the hydraulic conditions were favorable, further testing is planned in plants with unfavorable intake conditions in order to continue the validation of the new technique.

Fig. 2 .Fig. 3 .

 23 Fig. 2. Scintillation transducers and frame layout inside the test channel.

Fig. 5 .

 5 Fig. 5. Acoustic Doppler probe.

Fig. 6 .

 6 Fig. 6. Horizontal profiles provided from the Doppler probe. For each level, the mean velocity values were: -Level 1 (bottom) : 49.2 cm/s; -Level 2 (middle): 50.4 cm/s; -Level 3 (top) : 52.3 cm/s

Fig. 7 .

 7 Fig. 7. Flow velocity profiles (blue and red traces) compared with the Doppler reference (green trace).(natural turbulence)

Fig. 9 .

 9 Fig. 9. Velocity profiles calculated by the ASFM compared to the Doppler probe results.

Fig. 10 .

 10 Fig. 10. Velocity profiles calculated using the new technique compared to the Doppler probe results.

  .

  Fig. 11. ASFM velocity profiles for different types of turbulence compared to Doppler results.

  Fig. 12. Velocity profiles calculated using the new technique.


Francesco Bellotti

Riccardo Berta

Alessandro De Gloria
email: alessandro.degloria@unige.itott@itd.cnr.itsarnab@cad.coventry.ac.uk

Michela Ott

Sylvester Arnab

Sara De Freitas
email: sfreitas@cad.coventry.ac.ukkristian.kiili@tut.fi

Kristian Kiili

Designing Serious Games for education: from Pedagogical principles to Game Mechanisms

Keywords: Serious games, Pedagogical strategies, Game design, Game-based learning, Technology Enhanced learning, virtual worlds, user profiling

SGs represent an important opportunity for improving education thanks to their ability to compel players and to present realistic simulations of real-life situations. The scientific community is aware that we are just at the beginning of a proper use of gaming technologies for education and training and, in particular, there is a need for scientific and engineering methods for building games not only as more realistic simulations of the physical world, but as means that provide effective learning experiences. This requires an ever closer cooperation among the various actors involved in the overall SG life-chain, putting pedagogy in a central role, given the educational target of the SGs. This paper addresses the till-now inadequate integration of educational and game design principles and proposes techniques, methods and mechanisms that allow designers with different background to dialogue among each other and to define games that are able to integrateby designentertainment and educational features. In particular, the paper follows a design path that starts from the definition of reference frameworks and then analyses the typical categories of design patterns, before focusing on the user-interaction modalitiesseen from a pedagogical point of viewgiven their relevance for the end-users. In the end, we discuss the sandbox serious game model, that looks suited to implement -by designjoint pedagogical and entertainment features. We believe that the indications provided in this paper can be useful for researchers and stakeholders to understand the typical issues in SG design and to get inspiration about possible solutions that take into account the need to implement tools that are effective both as an entertainment medium and as an education tool.

Introduction

Digital games are widely regarded as high potential educational tools able to provide students with new augmented learning opportunities. According to [START_REF] Kirriemuir | Literature review in games and learning[END_REF] digital games employed in education can be broadly subdivided in two categories: 1) mainstream games, i.e., games that are created solely for fun and 2) learning games, i.e., games that are expressly designed with explicit educational purposes. Games in this last category are also referred to as Educational Games and, with a slightly different "nuance", Serious Games (SGs) [START_REF] Breuer | Why so serious? On the relation of serious games and learning[END_REF][START_REF] Derryberry | Serious games: online games for learning[END_REF]. Also mainstream games can be used for education. In this case, the educational value and effectiveness is directly related to the pedagogical choices made by those, typically teachers, who are in charge of carrying out the educational intervention [START_REF] Bottino | The impact of mind game playing on children's reasoning abilities: reflections from an experience[END_REF]. [START_REF] Van Eck | Digital game-based learning: It's not just the digital natives who are restless[END_REF] argues that integrating Commercial Off -The Shelf (COTS) games in the learning process is promising for education, because of its cost-effectiveness and scalability in use. The paper provides many examples of COTS games already being used in the classroom, including Civilization (history), Age of Empires II (history), CSI (forensics and criminal justice), The Sims 2 (making complex social relationships), Rollercoaster Tycoon (Engineering and Business Management), and SimCity4 (Civil Engineering and Government). For some of them there is a clear match between their explicit content and the classroom content. For others, the match is implicit. In any case, it is important that teachers augment the game with contextualized instructional activities, inserting the game experience in a sound overall educational framework [START_REF] Van Eck | Digital game-based learning: It's not just the digital natives who are restless[END_REF]. The focus of this paper, instead, is on games -in particular SGs -ad-hoc designed for educational purposes. The potential of SGs is relevant, because a large and growing population is familiar with playing games, that can present users with realistic and compelling challenges, highly stimulating their information processing capabilities and capturing their concentration span for long duration. "In games, the learning is not only relevant but applied and practiced within that context (Situated cognition)" [START_REF] Van Eck | Digital game-based learning: It's not just the digital natives who are restless[END_REF]). Menn, (1993) claims that engagement in the job, even if only as a simulation, significantly increases students' knowledge retention. The SGs' educational potential and actual effectiveness may vary appreciably as a consequence of the pedagogical choices made a priori by the game designer [START_REF] Squire | Game-Based Learning: Present and Future State of the Field, An x-Learn Perspective Paper[END_REF]. Thus, a proper design is key to meet the end-user and stakeholder requirements, that are twofold, on the entertainment and education sides. Some authors argue that several games have "per se" the capacity to elicit and trigger some kind of learning, for instance SGs in the field of reasoning and problem solving skills [START_REF] Garris | Games, motivation, and learning: A research and practice model[END_REF]. However, it is undeniable that a fine-tuned pedagogy plays a major role in sustaining learning effectiveness. As Quinn (2005) has argued, educational games need to be designed properly to find a balance between gameplay and learning objectives. One of the biggest problems of educational games to date is the inadequate integration of educational and game design principles (e.g. Kiili, 2005;2007) and this is also due to the fact that digital game designers and educational experts do not usually share a common vocabulary. This paper stems from the authors' collaboration in the GaLA NoE (Game and Learning Alliance Network of Excellence1 ), in particular in the Technical Committee devoted to Pedagogy. The aim is to analyze and critically discuss the various steps of a pedagogy-driven game design that is rooted in pedagogical principles and is able to go down up to the game mechanisms. The following sections of the paper explore: "reference frameworks" underpinning and informing SG design (section 2); "game design patterns", intended as means to facilitate the design and development of high quality educational games by providing a shared vocabulary for both instructional and game designers (section 3); user interaction aspects of games which can benefit from the joint effort of pedagogy and game design experts (section 4). As an application case study, section 5 focuses on a particular class of SGs, namely the Sand-Box Serious Games, that, from our experience, look particularly interesting for implementing effective SGs. Section 6 draws the conclusions and proposes indications for future research.

"Reference frameworks" for SGs design

Given the instructional goal, SG research should be strongly grounded in proper educational foundations. "To be effective, serious games must incorporate sound cognitive, learning, and pedagogical principles into their design and structure" [START_REF] Greitzer | Cognitive science implications for enhancing training effectiveness in a serious gaming context[END_REF]. In this regard, it is important to stress that, while serious games are frequently seen as "de facto" instructional, the combination of entertainment and knowledge acquisition is far from being immediate. Games are easily "per se" motivating. However, the next step towards instructional effectiveness is more difficult to accomplish. Most new generation SGs and Virtual Environments (VEs) adopt a discovery and inquiry-based learning strategy: they are open environments where students should learn basically by exploring contents and solving problems. This approach, however, is problematic. Although unguided or minimally guided instructional approaches are popular and intuitively appealing, there is evidence from empirical studies that minimally guided instruction is less effective and efficient than instructional approaches that rely on a strong guidance of the student. The advantage of guidance begins to recede only when learners have sufficient knowledge to provide "internal" guidance [START_REF] Kirschner | Why minimal guidance during instruction does not .work: An analysis of the failure of constructivist, discovery, problem-based, experiential, and inquirybased teaching[END_REF]. The cognitive load theory (CLT) (Sweller, 2008) stresses "instruction [is] based on the facts, laws, principles, and theories that make up a discipline's content" [START_REF] Kirschner | Why minimal guidance during instruction does not .work: An analysis of the failure of constructivist, discovery, problem-based, experiential, and inquirybased teaching[END_REF].

Learning is a complex activity that needs several gradual steps, that have to be supported by various tools (e.g., paper and digital, reading and writing, etc.) and generally have to be guided, possibly by an adult person, in order to be useful for the learner and not cause a waste of time/energies or even acquisition of misconceptions or of incomplete/disorganized knowledge. The presence of a reliable adult teacher/educator can help the student to get the meaning of what he is doing, in particular in the first steps. What computer systems (including games) can do is to support teachers -for instance by building an information rich and stimulating environment, providing a wealth of data obtained by tracing the user and making comparisons, favoring personalization and feedback, supporting peer cooperation and dialogue with non-peers. Games can add by themselves a plot and mechanisms that keep the flow [START_REF] Csikszentmihalyi | Flow: The Psychology of Optimal Experience[END_REF] and continuously spur the player to improve. Awareness of these considerations is limited in the scientific community. And we believe that the proposed perspective provides a major direction to improve current design and consequently favor a real and useful uptake of SGs as an educational tool, not as a technology pull or a simple pedagogical fashion. One of the keywords of current SGs and VEs is "experience", according to [START_REF] Kolb | Experiential Learning as the Science of Learning and Development[END_REF] definition of learning as "the process whereby knowledge is created through the transformation of experience". In Kolb's experiential model of learning, individuals are encouraged to reflect on the actions and consequences, so to foster understanding and reapplying this understanding to future actions. Kolb defines four possible learning styles: (i) Divergent (feel and watch), (ii) Assimilative (watch and think), (iii) Convergent (do and think) and (iv) Accommodative (do and feel). These Kolb's styles are possibly interrelated depending on individual preferences, and may result in four different outcomes: Concrete Experience (feel), Reflective Observation (watch), Abstract Conceptualization (think) and Active Experimentation (do). A similar cataloguing of learning styles has been proposed by [START_REF] Fleming | Not Another Inventory, Rather a Catalyst for Reflection[END_REF], that developed a theory -VARK -that categorizes learners: Visual learners (with a preference for tools such as pictures, concept maps), Aural learners (listening and discussion), Reading/Writingpreference learners( textual stimulus), and Kinesthetic or Tactile learners (movement and hands-on practice). Kolb's experiential learning model has been recently revisited in order to include new generation VEs and SGs. To conceptually support issues of game design using pedagogically driven approaches, the Four Dimensional Framework (4DF) [START_REF] De Freitas | How can exploratory learning with games and simulations within the curriculum be most effectively evaluated?[END_REF] and the SG Exploratory Learning Model (ELM) [START_REF] De Freitas | The use of exploratory learning for supporting immersive learning in virtual environments[END_REF] have been proposed. These models open the capability for learning through the experience of exploring SG/VE spaces. 4DF suggests to inform game design by referring to four dimensions, such as: learner profiling (e.g. ICT skills, gaming experience), selection of pedagogies used (e.g. associative, cognitive or situative), used representation (e.g. level of fidelity, interactivity and immersion) and context within which learning takes place (e.g. disciplinary context, place of learning). By following the four dimensions model, game developers should be able to design SGs by taking into account the learning characteristics of learners and the different pedagogical and contextual constraints so to enact effective absorption, promote reflection on knowledge and transfer these learning variables into realworld scenarios. Similarly, the ELM model extends from Kolb's experiential learning model to include the typical and popular characteristics of VEs and SGs, such as the 3D world settings and the social interactive learning aspects. In ELM, learning sequences and experiences are so to say "choreographed", to support peer interactions and exchanges. This is made possible also thanks to the strong support of the user's kinesthetic experience. For instance, [START_REF] Arnab | Tactile interaction in an ancient world on a web browser[END_REF] explored the use of tactile interactions in a game-based learning environment implemented atop of a multimodal browser-based platform aimed at promoting "hands-on" engagement with a topic -the cultural heritage, in the implemented case. The models put an emphasis on sequencing learning experiences, meta-reflection, peer assessment and group work, that are interesting and innovative aspects of SGs. However, it is important to stress that this must not hinder the importance of student guidance [START_REF] Olimpo | Pedagogical plans as communication oriented objects[END_REF]) and of the curriculum. This does not intend to neglect the fun aspect, but to stress the educational effectiveness of a game for its users. In this sense, it is important to highlight that SGs, rather than an "all comprehensive" teaching tool, look particularly suited as an instrument for motivating beginners to new topics and as a practicing tool to apply and test knowledge acquisition [START_REF] Bellotti | Designing effective serious games: opportunities and challenges for research[END_REF]. This consideration should help designers to optimize the efforts and the expected results.

"Game design patterns" as a shared vocabulary and common viewpoint for SG designers

After adoption of a reference framework for design, a subsequent step is given by the necessity for designers to share a vocabulary for design analysis, documentation and communication. This need is stringent in SG design, because of the apparent difficulties in mastering a complex relational web including education, psychology, technology, art, business, and creativity. Practical design tools are necessary in order to effectively implement educational aspects in the designs.

A major conceptual tool, in this direction, is the definition of pedagogically informed game design patterns. Only seldom, in fact, do game designers and educational/instructional designers share a common vocabulary, which hinders collaborative design endeavors. A solution can come from the well-known design patterns, collections of reusable solutions to solve recurring problems [START_REF] Alexander | A Pattern Language: Towns, Buildings, Construction[END_REF]. It is important to note that the term design pattern is concerned with content, in our case, rather than with programming, as in [START_REF] Gamma | Design patterns: elements of reusable objectoriented software[END_REF].

Porting the design pattern concept into the educational games' field, [START_REF] Kiili | Educational Games: Design, Learning, and Applications[END_REF] has identified a number of patterns, for which he proposed 6 categories. In the following we briefly sketch how these categories address crucial educational aspects that game designers should take into account when designing educational games.



Integration patterns describe solutions that harmoniously integrate game elements and learning objectives in pedagogically meaningful ways. The integration of learning objectives and gameplay creates the foundation of a game and usually arouses constraints that affect the whole design.



Cognition patterns describe solutions that trigger reflective and metacognitive processes in players and stimulate players to process relevant content experienced through gameplay. [START_REF] Ketamo | Conceptual change takes time: Game based learning cannot be only supplementary amusement[END_REF] emphasize the meaning of cognitive feedback in educational games. The aim of cognitive feedback is to grasp player's attention, focus it on essential learning content and stimulate player to reflect on his or her experiences and tested solutions in order to further develop his mental models, validation of hypothesis and formation of new playing strategies. The results have indicated that the sooner the player notices the cognitive feedback and grasps it meaning, the more effectively can he play the game.  Presentation patterns aim to ensure that the player's processing of the content is effective. Learners are challenged to extract relevant information from a game world, select corresponding parts of information and integrate all such elements in a coherent representation. This is demanding, because the game world may change while playing, important information may be presented only a while, and thus it needs to be kept active in working memory in order to allow integration of information. This may impose an excessively high cognitive load and hinder learning. Thus, game designers should consider the cognitive price of every element and that visual effects should be used to highlight the crucial elements. It is not enough that players can cope with challenges, but they need to process game content so to learn. Test results have indicated that players' perception patterns tend to vary a lot and players miss relevant information during playing.



Social interaction and teaching patterns are interwoven into cognition patterns. They describe solutions that facilitate learning or teaching (trigger reflective and metacognitive processes) through social activities and socially constructed game elements. This pattern category is not restricted to direct game activities, but can also include patterns that guide debriefing sessions, for example. In particular, teaching patterns describe solutions that facilitate teacher's work by providing observation, assessment and participation possibilities. Games could be armed with effective tools that provide diagnostics and summarizations of learners' gaming behavior. Such tools could help teachers to concentrate on learners' most crucial problems and master relatively large learner groups with numerous variances in skills. Pedagogical support to teachers may be one of the key points for spreading SGs.



Finally, engagement patterns provide a means of wrapping the whole gaming experience into a meaningful and motivating package. They describe solutions that motivate players to perform better in a game, facilitate learning and increase playing time.

In general, SGs design patterns draw from the well established knowledge of game design patterns [START_REF] Bjork | Patterns in Game Design[END_REF], and add a second foundation beside entertainment: pedagogy. In our experience, pedagogically-informed game patterns represent a key practical tool to support the necessary collaboration among experts -mainly computer programming, pedagogy and the specific target domainin all the choices to be done when designing a SG. In the next section we focus in particular on presentation patterns, given their importance from the point of view of the end-user.

Focus on presentation and user interaction

As seen in the previous sections, there is a wide consensus that pedagogical choices made a priori and embedded in the pedagogical design of games may contribute to enhance learning effectiveness [START_REF] Kiili | Foundation for problem-based gaming[END_REF]. Such pedagogical choices may affect, to a different extent, different aspects and parts of a game. The first basic choice concerns the definition of the target users and the elicitation of their needs. Consequently, the content to insert in the game is to be decided. Besides guaranteeing the correctness and suitability for the target age and for the intended learning purposes, a number of other pedagogical aspects are to be considered, in particular the flow/harmonization of the content presentation, also considering the need to graduate the levels of difficulty. In this section we shortly focus on design items and choices related to the content presentation, given their relevance for the final product.



Interface -Interface appeal is key because games, by definition, have to be engaging to play, and also because a nice graphic aspect can attract demographics that are traditionally averse to instructional activities. This is often neglected when designing SGs, for which designers tend to think of their users as a captive audience. But this assumption strongly limits the potential of the final SG. In interface design, however, beside the pure graphical attractiveness, there are also other aspects that should be designed considering also the pedagogical point of view. These include the identification of relevant/irrelevant functionalities/modules -to be appropriately displayed in place and time according to their salience -and the appropriate use of audio to substantiate and foster comprehension and learning. Fig. 1 shows two different interfaces chosen for the same simple casual game (Hanoi Towers), from which it appears the difference in overall clearness and potential ability to help focus on relevant elements of the game.



Method/level of interaction -The interaction modalities for game have to be decided coherently with the application's educational strategy (e.g., a question-answering or an inquiry/exploratory strategy), which in turn is to be determined by the game's inspiring pedagogical principles. As a consequence, also the level of interaction should be different. For instance, "Question & Answer" environments typically require a paced and homogeneous user-computer interaction, while open environments, like simulations or adventure games, where inquiry or discovery learning strategies are adopted, are per se fully interactive and, at a further level, additional interaction (e.g. request of specific hints/explanations) should happen mainly "on demand", when the need emerges.



Feedback and reward -The type of feedback provided by the system as a consequence of user actions (from simple yes/no answers to full re-explanation and adapted, customized feedback to the user's responses) is a key point for all types of digital educational products [START_REF] Timmers | Attention paid to feedback provided by a computer-based assessment for learning on information literacy[END_REF]. Fig. 2 shows the contextualized feedback of a classic battleship puzzle game, Hexip, where instead of showing the solution or simply highlighting the user mistakes, the system shows the right way to follow, suggesting reflections and specific considerations on the actual game situation.

Fig.2. Screenshot showing contextualized feedback

The reward provided to the user in case of positive achievements is an important design element, since it could offer a strong performance motivation. It has to be perceived as a reward for the work done, but should also be effective for stimulating further gaming and learning. In general, feedback should be strictly linked with the needs of the target end-users and coherent with the overall learning objectives and adopted educational strategy.



Type of evaluation of performance and level of metacognitive support provided -The capacity of the digital tool to provide users with a proper evaluation of their performance is a key aspect to support and enhance the SG effectiveness and impact. The need for precise pedagogical assessment is necessary in both the typical evaluation methods: summative (final assessment of the overall performance) and formative (in itinere, aimed at supporting reflection on and adjustment of learning behavior). This is expected to guarantee that users are fully aware of their successes/failures, so that they are in a better position to improve their performance. Embedding formative and/or summative evaluation elements in the game has different pedagogical implications closely related to the level of performance awareness which, in turn, has clear implications on metacognition and metacognitive aspects of learning behavior [START_REF] Abbott | Literature Review: Deep learning with technology in 14-to 19-year-old learners[END_REF][START_REF] Roll | Designing for metacognition-applying cognitive tutor principles to the tutoring of help seeking[END_REF]. Also, inserting assessment in games should not obstacle the overall flow and should be smoothly embedded into the actual game mechanisms. This is not easy, and the literature presents some good practice cases, mot a coherent theory or model (e.g., [START_REF] Swarz | CancerSpace: A simulation-based game for improving cancer-screening rates[END_REF][START_REF] Zielke | Serious games for immersive cultural training: creating a living world[END_REF].

From theory to practice: the SandBox SG model

The virtual world (VW) in which a game is set can provide itself an important value for instruction. Actually, several effective SandBox Serious Games (SBSG)they also have a counterpart in successful entertainment games, such as Grand Theft Auto and Oblivion [START_REF] Squire | Open-Ended Video Games: A Model for Developing Learning for the Interactive Age[END_REF] -have an organization that tends to support players in building a suited knowledge structure for the addressed topic(s) [START_REF] Qin | Learning blood management in orthopedic surgery through gameplay[END_REF]. In rough terms, the model consists of: (1) a spatial organization -the VW -where knowledge is distributed (e.g., [START_REF] Sliney | JDoc: A serious game for medical learning[END_REF] and that induces spatial information processing and provides landmarks to support orientation [START_REF] Slater | Visual realism enhances realistic response in an immersive virtual environment[END_REF]; (2) contextualized tasks, that are spread and contextualized in the VW . Tasks embody units of knowledge that can be discovered by the player. The Task Based Learning (TBL) theory (W illis, 1996) stresses the importance of concrete, focused activities to construct knowledge and develop skills. A player explores the environment accomplishing missions involving a sequence of small tasks, each of which has a specific, limited instructional target. Pedagogical usefulness of this approach has been argued in [START_REF] Frazer | Is less actually more? The usefulness of educational minigames[END_REF], presenting the MyLA (My Learning Assistant) experience, highlighting the importance of stimulating learners through questions and timely, accurate, context-sensitive, answers. The missions' complexity, given by the difficulty of the tasks and of the environment to be explored, can grow up gradually towards ever more complex objectives, Tasks may be instances of templates (e.g. various sorts of minigames with different contents), with the advantage that interaction modalities can be re-employed by the player in several contexts, keeping the cognitive load low, which is good for the Cognitive Load Theory (CLT). Moreover, development of tasks can be efficiently supported by an authoring toolkit, allowing teachers, and even students, to develop/customize content [START_REF] Bellotti | Designing effective serious games: opportunities and challenges for research[END_REF]. Availability of a large database of semantically annotated tasks leads to the possibility of a dynamic scheduling of tasks. Bellotti et al., (2009a) present an Experience Engine (EE), that exploits computational intelligence to schedule tasks matching the needs estimated by profiling the user performance and with the aim of keeping the learners in the proper Zone of Proximal Development (ZPD) [START_REF] Vygotsky | Play and its role in the mental development of the child[END_REF] and enforcing a teacher-defined pedagogical strategy. This system, again, is able to provide a level of guidance that should help the learner to make the most of his exploration without getting lost in a potentially wide knowledge space. In the proposed approach, a game does not need a detailed story specification. There is a highlevel challenge (e.g., a treasure hunt), that spurs players to competition/cooperation through explorations of a VW. This simple narrative structure would cause a minor cognitive load to the player, leaving more space for knowledge acquisition. Tasks may be of different type, also supporting different learning styles (e.g., the Kolb's and VARK styles, in Bellotti et al., 2009a), that could be stressed in the gameplay either to improve the learner's skills or to make the learning easier by exploiting his most favorite skills -depending on the teacher strategy. In fact, the methodology allows the teacher to specify the requirements for a runtime scheduling policy that maximizes learning objectives. The policy is learnt by the EE, which is the responsible for the final scheduling of the task. The policy allows the teacher to define several educational targets, among which the expected difficulty curve and tasks' overall learning style distribution (Bellotti et al., 2009b).The SBSG-EE model has been implemented in SGs for the cultural heritage and maritime education domains, but it is clearly domain-independent (Bellotti et al., 2009a).

Conclusions and future work

SGs represent an important opportunity for improving education, also in a life-long learning perspective, thanks to their ability to compel players and present realistic simulations. Beside this, there is the awareness that we are just at the beginning of a proper use of gaming technologies for education and training [START_REF] Johnson | Lessons learned from games for education[END_REF] and there is a need for scientific methods for building games as means that provide effective learning experiences [START_REF] Greitzer | Cognitive science implications for enhancing training effectiveness in a serious gaming context[END_REF]. This requires a closer cooperation among the various actors involved in the overall SG lifechain (students, teachers, educators, developers, companies, etc.). This paper addresses the till-now inadequate integration of educational and game design principles and proposes methods and mechanisms that allow designers with different background to dialogue among each other and to define games that are able to integrateby designentertainment and educational features. We believe that the indications provided in this paper can be useful for researchers and stakeholders to understand the typical issues in SG design and get inspiration about SGs that are effective both as entertainment media and as education tools. The next steps of our research work concerns an improvement of the presented models/techniques (i.e., reference frameworks, design patterns, interaction modalities and sandbox serious game model). In the same time, these or similar techniques may be assessed and enhanced also by other experts and researchers, in order to achieve the long-term aim of defining proper rules and models for an effective design of SGs.

Fig. 1

 1 Fig. 1 Different interfaces for the same game (Hanoi Towers)

EU Network funded Under FP7