Jean-Pierre Dussault

Jean-François Landry

Philippe Mahey

Computational pool: an OR-optimization point of view

Keywords: Pool, Billiards, Snooker, Game, Simulation, Planning, Strategy, Optimization, Artificial Intelligence

Computational and robotic pool has received increasing interest in the past few years. The challenges are important. In this survey, we focus on the computational aspect, but nevertheless acknowledge that the robotic aspect is both very important and very difficult.

Computationally, one may roughly split the tasks into three main aspects: simulation of the physics, execution of the shots and planning of sequences of shots. We will discuss those aspects from an OR-optimization point of view. The planning aspect retains also the interest of the artificial intelligence community, and links between both approaches will be revealed.

We will present the state of the art in this young research area, as well as the obstacles that remain before a computer-robotic system actually challenges a human champion.

Introduction

The interest in computational pool is motivated by a variety of factors. The mechanics of pool has long served as a focus of interest for physicists, an interest which has extended naturally to the realm of computer simulation. Realistic and efficient simulators have led to the proliferation of computer pool games. These games include significant computer graphics components, often including human avatar competitors with unique personalities, as well as an element of artificial intelligence to simulate strategic play. There are numerous one-person games available, of various physical realism.

Though in the context of this chapter the primary objective is the creation of a computer pool player, we wish to extend our research beyond the scope of billiards. We hope that by researching the best way of making a perfect player we can develop new AI approaches, and possibly contribute to other problems of that nature.

There have been three instances of pool Olympiads where rival computational pool player competed. The competitions attracted participants from the artificial intelligence community, a pool player representing a challenge for the agent approach. Yet, only 8-ball tournaments were held, and the champions used a Monte Carlo search tree strategy [START_REF] Greenspan | UofA wins the pool tournament[END_REF][START_REF] Greenspan | PickPocket wins pool tournament[END_REF][START_REF] Smith | PickPocket: A computer billiards shark[END_REF][START_REF] Archibald | Analysis of a winning computational billiards player[END_REF]. In this chapter, we develop a complementary approach based on OR techniques, simulation, dynamic programming, numerical optimization.

Although the problem we wish to solve is deterministic in nature, subject to the laws of physics, it is so easily influenced by many small factors that it can actually be seen as stochastic. This makes it very hard to create a perfect player, because even if he never misses, the outcome of the game is never pre-defined.

In this chapter we will explore the technical challenges of computational pool from an OR point of view. Section 1 describes the elements of the cue sports from a human perspective, including some discussion of the aspects of advanced human play. Section 2 introduces the several OR aspects to be detailed later on.

Section 3 presents the requirements to produce a simulation model. Section 4 addresses the optimization of a billiards player. This is work in progress.

Future trends are discussed in section 5.

The Cue Sports

There are many varieties of cue sport, and many different terminologies and rules that vary with geographical location. For example, the most popular North American pool game is 8-ball, in which there are seven "low" (solid) balls (1-7), seven "high" (striped) balls [START_REF] Gaspard | Théorie mathématique des effets du jeu de billard[END_REF][START_REF] Fray | [END_REF][START_REF] Greenspan | UofA wins the pool tournament[END_REF][START_REF] Greenspan | PickPocket wins pool tournament[END_REF][START_REF] Johnson | The NLopt nonlinear-optimization package[END_REF][START_REF] Jones | Lipschitzian optimization without the lipschitz constant[END_REF][START_REF] Landry | AI optimization of a billiard player[END_REF] and the 8-ball. The objective is to be the first to sink all balls in one group, and then the 8-ball. Alternately, snooker is likely the most popular cue sport in England, which is played on a larger table and consists of 15 red balls, and 6 of various colors. The balls are smaller than their North American counterparts, and the objective is to accumulate points by alternately sinking a red and then a colored ball, each having a certain value. In France, a game called carom is played, where only 3 balls are used on a pocket-less table, and the player must attempt to contact both object balls with the cue ball. In the three cushions ("trois bandes" in french) version of carom, the cue ball is required to rebound off of three rails before kissing the object ball.

Pool terminology

The basic elements common to all of these games are as follows. For a much more complete glossary of cue sport terms, see the Wikipedia page [START_REF]Glossary of cue sports terms[END_REF] from which we extract the terms relevant to our computational pool study.

• Cue: Also cue stick. A stick, usually around 55-60" in length with a tip made of a material such as leather on the end and sometimes with a joint in the middle, which is used to propel billiard balls.

• Cue Ball: Also cueball. The ball in nearly any cue sport, typically white in color, that a player strikes with a cue stick. Sometimes referred to as the "white ball", "whitey" or "the rock".

• Object Ball: Depending on context:

1. Any ball that may be legally struck by the cue ball (i.e., any ball-on);

2. Any ball other than the cue ball.

• Table : The flat playing surface. The table size varies, depending on the game played, but is always rectangular, being twice as long as is is wide. In most games, the table has a pocket in each of the four corners, and one at the centers of each length.

1. Bed: The table is covered in a textured felt (or baize) material, usually of green color, to add a frictional damping effect to the shots.

Rail:

A rubberized edge running along the inner boundary of the table, to accommodate rebounds following the collision of a ball (cushions in British English). State: the position of all balls at rest on the table, ready for the next shot.

Table

• Shot: The use of the cue to perform or attempt to perform a particular motion of balls on the table, such as to pocket (pot) an object ball, to achieve a successful carom (cannon), or to play a safety. Different classes of shot type include:

-Direct Shot: A shot where the cue ball hits an object ball, which then reaches a pocket.

-Kick Shot: A shot in which the cue ball is driven to one or more rails before reaching its intended target-usually an object ball. Often shortened to 'kick'.

-Bank Shot: Shot in which an object ball is driven to one or more rails prior to being pocketed (or in some contexts, prior to reaching its intended target; not necessarily a pocket). Sometimes "bank" is conflated to refer to kick shots as well, and in the UK it is often called a double.

-Combination Shot: Also combination, combo. Any shot in which the cue ball contacts an object ball, which in turn hits one or more additional object balls (which in turn may hit yet further object balls) to send the last-hit object ball to an intended place, usually a pocket. In the UK this is often referred to as a plant.

-Safety shot:

1. An intentional defensive shot, the most common goal of which is to leave the opponent either no plausible shot at all, or at least a difficult one. 2. A shot that is called aloud as part of a game's rules; once invoked, a safety usually allows the player to pocket his or her own object ball without having to shoot again, for strategic purposes. In games such as seven-ball, in which any shot that does not result in a pocketed ball is a foul under some rules, a called safety allows the player to miss without a foul resulting. A well-played safety may result in a snooker (no direct shot available).

• Spin: Rotational motion applied to a ball, especially to the cue ball by the tip of the cue, although if the cue ball is itself rotating it will impart (opposite) spin (in a lesser amount) to a contacted object ball. Types of spin include follow or top spin, bottom or back spin (also known as draw or screw), and left and right side spin, all with widely differing and vital effects. Collectively they are often referred to in American English as "English".

Specificity of game variants

To excel in any pool variant, one has to thoroughly understand the physics, accurately control the cue ball, and plan several shots in advance. However, each variant has its specificity, and the relative weight of those game aspects slightly differs from one variant to another. We examine here four among the most popular games and their specifics.

Games using numbered balls

On the American continent, most pool tables use numbered balls [START_REF]Canal + multimédia[END_REF][START_REF] Fastfiz | [END_REF][START_REF]Glossary of cue sports terms[END_REF][START_REF] Alciatore | The Illustrated Principles of Pool and Billiards[END_REF][START_REF] David | Pool and billiards physics resources[END_REF][START_REF] Archibald | Analysis of a winning computational billiards player[END_REF][START_REF] Archibald | Success, strategy and skill : an experimental study[END_REF][START_REF] Archibald | Modelling billiards games[END_REF][START_REF] Gaspard | Théorie mathématique des effets du jeu de billard[END_REF][START_REF] Fray | [END_REF][START_REF] Greenspan | UofA wins the pool tournament[END_REF][START_REF] Greenspan | PickPocket wins pool tournament[END_REF][START_REF] Johnson | The NLopt nonlinear-optimization package[END_REF][START_REF] Jones | Lipschitzian optimization without the lipschitz constant[END_REF][START_REF] Landry | AI optimization of a billiard player[END_REF] in a variety of games.

The "official" tables measure 4.5 ′ × 9 ′ , but smaller models (4 ′ × 8 ′ or even 3.5 ′ × 7 ′ ) are quite common. Hereafter, we briefly discuss three popular game variants using such equipment.

Eight ball This is by far the most popular game played on the American continent. However, some of its popularity stems from its use in bars, on coin operated tables, and the rules of the game reflect this situation. It is the variant where chance plays a major role, and this for three main reasons:

• no call is made on the break shot, so any ball pocketed by luck on the break is valid;

• on a foul play, pocketed balls remain in the pockets;

• both players do not play on the same set of balls.

Although not the primary variant in high level human competitions, this has been the variant in the first three computational pool tournaments.

Planning is limited to eight shots before the win. On the other hand, the presence of opponent's balls may complicate the plan.

Nine ball This variant is played with nine balls, and the specifics include the obligation to hit the lowest numbered ball on the table. Thus, planning is somewhat simpler here since the order in which the player attempts the balls is fixed.

Straight pool This is played on similar tables as eight balls pool, but here, any ball has to be called including on the break shot, and balls sunk on a foul are pulled out the pocket and re-spotted on the table. Champions achieve runs of several hundreds consecutive successful shots. It is clear that this variant requires both clever planning, and extreme accuracy. High risk shots involving several rebounds on the rails or with other balls are rare, the players often preferring to resort to defensive shots than to risk giving hand to the opponent with an easy table.

Snooker

Snooker is the most popular variant in UK. It is played on a large (6 ′ × 12 ′ ) table using 15 red balls and six colored balls in addition to the cue ball. The large dimension of the table and the use of slightly smaller balls call for high accuracy. Here again difficult bank, kick or combination shots are often avoided by the frequent use of defensive shots. The name snooker itself refers to the situation where a player has no legal direct shot available.

Carambol

Carom is played on a pocket-less table using only three balls, slightly larger than numbered balls though. The game consists in having the cue ball hit the other two balls. In high level competitions, the three cushions variant is often prefered, in which the cue ball has to rebound on three cushions before hitting the second of the other two balls. Obviously, this three cushions variant is extremely demanding in geometrical skills, and the sole difficulty of a single shot almost precludes any form of planning.

In opposition to most pocket billiards variants, the physics model of the collision with the rail is of primary importance here, as is the accurate control of the cue ball. On the other hand, the strategic planning aspect is way less important.

Overview of computational pool

In this section, we present the three basic building blocks used in a computational billiards player. As we discussed in section 1.2, different variants of the game require different balance and specificity in the building blocks.

Physics simulation

The simulator is required for two aspects in computational pool.

• The first one is to act as a common table and referee in order for the (computer) players to compete. In an ideal world, the simulated game would be indistinguishable from its counterpart as played on a real table. This involves meticulous modeling of the impacts between the cue, the balls, the rails and (whenever balls jump) the table. Moreover, the rolling motion of the balls on the cloth must be addressed faithfully.

• The second aspect is a tool on which the AI players rely in order to predict the outcome of a given shot. Here, speed-accuracy trade-offs are expected.

Yet, in the first three editions of the computer pool tournaments, the same simulator was used for both uses, some random noise being added on the shots played on the "common table ". As the situation evolves, it is likely that referee simulators will get more and more complex and faithful, yielding high computational costs perhaps no more compatible with the requirements of computational players under limited resources. Ultimately, the games will be played on a real table by robots, and the simulators used by the players will be integral part of the player's strategy.

Control of the cue ball

When observing a champion at some variant of pocket billiards, two aspects are striking: the guy has mostly easy looking shots to play, but whenever he faces a difficult shot, he nevertheless sinks the ball. The first aspect is less spectacular, but is a consequence of his accurate repositioning after the impact on the object ball.

Strategic planning

Another aspect is that the champion takes enlightened decisions with respect to the order in which he will sink the balls. In computational pool, this aspect is addressed using some dynamic model of the game aspect. Among the most evident strategic decisions is the choice to do a so called defensive shot. Instead of aiming to sink some object ball, the player strives to leave the cue ball in such a position that his opponent is left with a very difficult situation.

Modeling billiards physics

In this section we first summarize the mathematical models that have been developed over the years, going back to Coriolis in 1835. Next we discuss two computer implementations.

Mathematical models

All variants of billiards and pool games involve a cue, hard spheres, a bed which is a flat surface covered with a cloth, and rail cushions. Spheres slide and roll on the bed, impact on each other as well as on the rails, and the cue gives the initial impact to the cue ball. Thus, we need to model

• cue-cueball impacts;

• moving balls; mostly, sliding and rolling on the bed, but sometimes "jumping" off the bed for some tiny amount of time, and even sometimes jumping off the table;

• collisions between moving hard spheres, mostly elastic collisions between rigid bodies;

• collisions between hard spheres and cushions on the rails, partly inelastic collisions between a rigid body and a not so rigid one (the rail).

All of this is quite delicate to accurately simulate, but since the moving bodies are identical spheres, and the bed is planar, the physics equations are rather simple.

The interest in the mathematics of billiards goes back to at least Coriolis [START_REF] Gaspard | Théorie mathématique des effets du jeu de billard[END_REF], and has attracted recent interest as well. In particular, David G. Alciatore (Dr Dave), in addition to his book [START_REF] Alciatore | The Illustrated Principles of Pool and Billiards[END_REF], maintains a web site [START_REF] David | Pool and billiards physics resources[END_REF] where he posts more mathematically oriented developments including fine tuning of physical models required to accurately predict experiments he conducts using high speed video cameras.

Rolling motion-2D simplifications

An important observation yields computationally tractable prediction for balls motion on the table. The trajectory of the balls is described by a piecewise quadratic parametric equation. This allows to simplify the collision detection to simultaneous quadratic equations, for which closed form formulae are available. [START_REF] Leckie | Pool physics simulation by event prediction 1: Motion transitions[END_REF][START_REF] Leckie | Pool physics simulation by event prediction 2: Collisions[END_REF][START_REF] Sénéchal | Mouvement d'une boule de billard entre les collisions[END_REF]. Moreover, extension to 3D simulation still may be described by piecewise parametric quadratic equations. Therefore, in principles, it is possible to implement a discrete event simulator without using numerical integration. Moreover, since the underlying parametric equations are simple piecewise quadratic, an improved implementation will provide sensitivities and derivatives, most useful for the optimization aspects to be discussed in section 4.3.1.

Ball-ball collisions

Ball-ball collisions are almost rigid bodies perfectly frictionless elastic collisions. The behavior of the object ball and cue ball after the collision are described by the so-called 30 • and 90 • rules. Actually, slight non-elasticity, small friction, speed, spin all slightly modify the rules. In [START_REF] David | Pool and billiards physics resources[END_REF], one can find numerous technical notes providing fine points of billiards physics.

Ball-rail collisions

Those collisions are much more complicated. In most pocket billiards variant, though, kick or bank shots are not that frequent, so a simple approach is justified. In three cushions, as the name of the game suggests, those collisions are of prime importance. Larger balls used in carom variants and high energy ball-rail collisions imply the cushion undergo important deformations, no more faithfully computed using simple geometric models alone. For instance, in [START_REF]Canal + multimédia[END_REF][START_REF] Fray | [END_REF], a one person carom game, shots were performed and captured with a camera, and in the actual game, interpolation is used to simulate the player's shots.

Existing physically documented simulators

While there are many one-person pool playing games, there are few efforts disclosing the actual equations or physical models underlying their simulator; we describe hereafter two softwares available under open source licenses.

PoolFiz -FastFiz

The first three instances of the pool Olympiads used the PoolFiz simulator [START_REF] Leckie | Pool physics simulation by event prediction 1: Motion transitions[END_REF][START_REF] Leckie | Pool physics simulation by event prediction 2: Collisions[END_REF][START_REF] Leckie | An event-based pool physics simulator. 11 th Advances in Computer Games[END_REF], lately replaced by the re-implementation FastFiz [START_REF] Fastfiz | [END_REF]. This simulator implements the simplified 2D rolling equations; the present implementation neglects any spin in the e 3 axis. The simulator was made available through a common interface to the competitors, which used it to compute their shots. When used as the referee table, some random noise was added to the shot parameters.

In the simulator, the following parameters describe a shot:

• a and b representing the side-spin and top-spin with respect to the cue ball center;

• θ the elevation of the queue stick;

• φ the orientation of the queue stick on the table;

• v, the initial speed given to the cue ball.

Billiards

The billiards-techne project [START_REF] Papavasiliou | Billiards[END_REF] adopts a different approach, namely it uses the ODE open source dynamics engine. As such, physical objects (cue, balls, table bed, table rails) are described using the ODE interface, and simulated as accurately as ODE allows. No advantage is taken from the simplified nature of perfect spheres rolling on a planar surface. While still in progress, the physics has 3D realism, and care has been taken to validate the results with high speed cameras observations to accurately model the cueball deflection when using English, an aspect absent from PoolFiz. The approach using ODE has some drawback, though: the simulator cannot produce noiseless results since it relies on .

Simulators comparison

We illustrate in Figure 1 the differences in repositioning possibilities of the two simulators.

Probably neither is realistic enough to predict reposition on a real table and further validation is certainly required. Important differences come from the fact that PoolFiz does not take side spin into account on ball-rail collisions, which explains the large area unattainable. Billiards, as compared to PoolFiz, results in less influence of speed on the cue ball deflection after impact with the object ball.

Modeling billiards players

As discussed above, some kind of simulation of the physics is required for the computational player to be able to predict the outcome of a given shot. In this section, we assume such a simulation model is available in the form of a black box. The more accurate the simulator, the more accurate predictions and planning of the AI player. In the first Olympiads, all the players shared the same simulator, which also acted as table referee. When playing on a robot, or when using a highly accurate simulator, it is expected that different players will use different simulators for their planning. Two aspects mainly require our attention. A sequence of shots has to be established, and thereafter, their execution has to be computed. By a shot, we mean a somewhat generalized shot including repositioning of the cueball. In the following subsections, we first address the planification of the sequence of shots as modeled by a dynamic programming (DP) formulation. We also discuss some solution strategies for this admittedly abstract DP formulation. Actual shots required by the dynamic programming planner are then computed using a local optimization model. We cannot avoid the tentation to report on our preliminary experience with respect to the local optimization.

Before going on further, we must warn that the following modeling assumes the 8-ball game setting. As the model is rather abstract, we expect no fundamental problem to extend it to other pool variants, but of course several minute details will have to be adjusted for other forms of the game.

A dynamic programming formulation

Modeling billiard games is a difficult task and very few known frameworks fit correctly the specific characteristics of these games which are : continuous state and control spaces, actions taken at discrete unknown instants, a specific turn-taking game rule which allows a player to play several times as long as he keeps the hand, stochastic perturbations of moves. C. Archibald et al. [START_REF] Archibald | Modelling billiards games[END_REF] have proposed a stochastic game framework valid for finite or repetitive versions of the billiard games and they studied the existence of Nash equilibria associated with stationary Markov strategies. We will first focus on the stochastic control problem mixing discrete and continuous aspects before introducing the game theoretic ingredients in the model.

Stochastic dynamic programming has been introduced to model dynamic discrete processes where random events occur after decisions are applied at each stage of the process. The state space X specifies the position of each ball on the table. It is here continuous but may be discretized to locate balls on the table. The control space U corresponds to the value of the cue parameters which are adjusted at the beginning of the shot. Each transition is the result of a nonlinear constrained optimization problem which represents the dynamic trajectory of the balls on the table under random perturbations. As seen below, one tries here to minimize the distance of the cue ball to a specified location while maximizing the probability to sink the object ball. The overall objective function is to maximize the reward of the player which is positive when the object ball is sunk in the pocket. The way to model that situation is to add a Boolean variable y t at each stage which is one when the object ball is sunk. Observe that, when y t = 0, the hand is lost and the opponent will inherit the current table. Thus, in difficult situations, a defensive step will try to minimize the opponent's reward. Note also that, as long as expectations are used in the stochastic case, a value function can be estimated by backward calculations, starting at an ideal state to pocket the last ball.

Let π = (u 0 , . . . , u T -1 ) be a feasible policy (series of actions for the states (s 1 , . . . , s T )), P [s ′ | s, u] the probability of going from state s to state s ′ while taking action u, R(s) the reward for reaching state s. The stochastic program can be stated in the following way (using here a finite length game) :

Maximize γP [y T = 1 |(u 1 , . . . , u T -1 ; ω 1 , . . . , ω T -1 )] + t E[R t (s t , y t , ω t )] (s t+1 , y t+1 ) = argmin s(τ )∈X,ut∈U E[F (s t , u t , s(τ ), st , ω t )] (1) s t ∈ X, y t ∈ {0, 1}
where ω t ∈ Ω t is a random variable with normal distribution and γ is an harmonization factor. The transition step associated with the internal minimization sub-problem will be detailed below. It relies on a target position for the cue ball corresponding to state st . The trajectory is represented by s(τ ) where τ ∈ [0, τ f ] is the continuous time of the motion of the balls, s t = s(0), s t+1 = s(τ f ).

Let now V π (s) be the optimal expectation of the final reward when applying the subpolicy (u t , . . . , u T -1 ) from state s t until the final state.

The equation:

V π (s) = R(s) + γ s ′ P (s ′ |s, π(s))V π (s ′ )
will be at its optimum if it satisfies the condition:

V * (s) = R(s) + max π(s) γ s ′ P (s ′ |s, π(s))V * (s ′ )
.

Thus, the sub-policy π * = {u * t , u * t+1 ..., u * T -1 } will be optimal for this problem. For billiards, as stated in [START_REF] Archibald | Modelling billiards games[END_REF], we are faced with a continuous-state and continuous-action domain, which makes things a bit more complicated.

We find ourselves evaluating an integral instead of a sum:

V (s) = R(s) + max π γ s ′ P (s ′ |s, π(s))V (s ′ )ds ′
The optimal strategy of discrete dynamic programs is commonly solved by performing backward computations from the final state back to the current state. We will discuss that strategy below, after saying a few words about the underlying game theoretic issues.

Game issues

Let us consider first the simpler situation of a finite game (like the 8-ball). It is not easy to analyze the general strategy which interprets a defensive shot as the one which will leave a difficult table to the adversary, thus expecting to take back the hand later to finish the game. This means indeed that the final profit associated with P [y T = 1] is still valid. Nevertheless, we should here pull from a possible table at stage t to an unknown table at t + q where q is the number of estimated shots left to the opponent. We refer to Archibald et al [START_REF] Archibald | Success, strategy and skill : an experimental study[END_REF] for an interesting A.I. point of view of the strategic issues.

Solution strategies for the DP model

The general problem of finding V π (s) for a deterministic problem may be quite complex by itself, and often becomes intractable as soon as more variables come into play. It is even worst for a problem with a continuous state and action space. However, in our case, we can benefit from the knowledge we have of the game we are solving and extract important information to narrow our search to a limited number of action-state space combinations. Assumption 1 : y t = 1, t = 1, . . . , T Assumption 1 corresponds to the so-called win-off-the-break winning sequence. The optimal value is hence the expected sum of remaining rewards to get through the game. The way to cope with the fact that the success of the game is now deterministic is to add a technical reward to an easier shot, or, equivalently, to a better position for the cue ball on a given table. Assumption 2 : The cue and object balls are the only balls expected to move.

With assumption 2, we get a direct estimate of the future positions of all future object balls. The player strategy corresponds to the Optimistic Planner described in [START_REF] Archibald | Success, strategy and skill : an experimental study[END_REF]. Observation : Later, we will naturally relax Assumption 2 to authorize collisions with other balls (and with the rails). Then, a new question will arise : should we consider only side collisions due to the trajectory of the cue and object balls, or should we include different shots aiming at repositioning the cue ball so that a collision happens with another ball (or a cluster of dangerously close balls) ? That latter situation is now under study. The skill model to compute the optimal trajectory of the balls will here be much more intricate as it will involve elastic collisions and singularities (see [START_REF] Miller | Optimal control problems in hybrid systems with active singularities[END_REF]).

Back to the stochastic dynamic program, assuming Assumptions 1 and 2, we will now proceed backward to estimate the optimal value of a given table. We may start with the last table which can be modeled as the current table where we want to sink, not the current object ball, but the the one which should be sunk at the last shot. To compute all V π (s T -1 ), we must compute the pocket angle for each remaining balls and then perform an inverse step to position the cue ball in all feasible states at t = T -1. The optimization black box will be very useful as it already works with an estimate st of the desired repositioning state. Observation : The curse of dimensionality will probably make these computations cumbersome and time-consuming if T is large, but we can begin testing increasingly complex situations setting T = 2, 3, . . . which can be easily adapted from the general case.

Optimization approach

We describe briefly here the minimization sub-problem associated with the transition step at stage t as defined in model [START_REF]Canal + multimédia[END_REF].

Supposing we are using the black box simulator described earlier, with the action variable u t being the finite-dimensional vector of the five parameters a, b, θ, φ and v. The trajectories s(τ ) of the balls moving on the table at a given shot depend thus on the initial state s(0) = s t and on u t , the latter being perturbed by the random variable ω t .

To compute an optimal action u t , we minimize a least-square function associated with the desired reposition st of the cue ball on the table, and with the desired sinking of the object ball. The objective function can thus be modeled in the following way :

F (s(τ ), u t , ω t ) = s(τ f ) -st 2 subject to s(τ ) = ψ(s t , u t , ω t ) y = 1 if s obj (τ ) = p for τ ∈ [0, τ f ]
where ψ is the dynamic transition function associated with the simulator, s obj is the component of s associated with the object ball and p is the component of st associated with the pocket. The solution of the minimization sub-problem will then give s t+1 = s(τ f ) with the corresponding value of y updating y t+1 . In the stochastic case, the function is replaced by an expectation value computed from the known distribution of the noise on the action variables.

The detailed formulation of the minimization problem and its resolution by an adaptation of Powell's derivative-free Quasi-Newton method (see [START_REF] James | The BOBYQA algorithm for bound constrained optimization without derivatives[END_REF]) can be found in [START_REF] Landry | AI optimization of a billiard player[END_REF].

Value of Billiards

In a general matter, the difficulty of executing a shot on a billiard table is defined by two aspects; the distance between the cue-ball, object ball and pocket, as well as the angle at Figure 2: Shot difficulty. The distance of the cue ball to the object ball, of the object ball to the pocket, the cut angle and the angle with the pocket all influence the difficulty of a shot, proportional to the admissible error with respect to the "perfect" shot that will sink the object ball right in the center of the pocket. which the cue-ball will hit the object ball. Of course, other factors also come into play like other balls partially blocking the path, or the closeness of the cue-ball to the rails. However, we can still get a pretty good estimate of a shot difficulty by using the first two aspects described. A real and precise difficulty coefficient is almost impossible to compute since it will not only rely on the percentage of success of the computed shot, but also on the impact of this shot for the cue-ball repositioning.

As shown in Figure 2, both the angle and distance factor result in a calculable angle θ for the shot difficulty. A shot aimed at the center of this angle should normally result in the best success percentage for this shot.

Once we have computed this coefficient, we can use it to evaluate any given table state, simply by taking the maximum value of all the available shots for a given cue ball position. If we now divide our billiard table into a 50x100 grid, we can take the value of max n i=0 θ i at each of these points and come up with the best repositioning targets for the next shots by removing each time the ball we would be aiming for (since we assume it will be pocketed).

However, this first and seemingly logic evaluation of a billiard table state is not necessarily applicable to all variants of the game, and does not for the moment take into account defensive shots. It does however give a good estimation of a table state value.

Results

To show the efficiency of the optimization model discussed in this paper, we ran some tests on randomly generated table states and computed possible shots using local and global optimization libraries. We show here only two of the best performers we tested for the sake of brevity. Both approaches were implemented using the NLopt library ( [START_REF] Johnson | The NLopt nonlinear-optimization package[END_REF]). BOBYQA, a local optimization method by Powells [START_REF] James | The BOBYQA algorithm for bound constrained optimization without derivatives[END_REF] was tested with five different starting points, distributed over the possible shot parameters. DIRECT-L, a global optimization method by [START_REF] Jones | Lipschitzian optimization without the lipschitz constant[END_REF], was tested with only one starting point.

Close to 20,000 various shots were computed using both libraries, to insure a proper sample size. Each of these shots represents a combination of an object-ball, an aimed pocket, a cue-ball and a repositioning target. As can be seen below, types of shots included direct, kick, bank and combine shots.

Table 1: Results of 19930 different shots computed with the local optimization method BOBYQA and global optimization method DIRECT-L. Average times(seconds) are displayed for all shots, as well as for successful shots. The average distance (meters) is the distance from the repositioning target.

The local optimization method, even though launched five times with various starting points, gets a slightly lower success percentage for bank and combine shots. The DIRECT-L, however, being a more global approach, achieves better results but at a higher cost in calls to the simulator. What these results actually show us is that we can obtain satisfying results to compute single shots with very few calculations. The trade-off between the solution's quality and the computation time needs to be carefully studied to achieve the best compromise, but this will also vary with respect to the variant of game played. It should also be noted that in the case a solution is not found for a given shot, it is usually because it is not possible because of other balls or rails restricting the queue motion. Thus a global method may be able to find a solution by doing a spectacular shot, but one that is not very reliable when played on a stochastic system. Further testing is needed to adapt the search criteria to the type of game played, and the level of noise present in the simulator.

Perspective

We proposed a description of a new application field, computational billiard. The field is really emerging, and much is to be expected in some near future. However, the ultimate goal to have a computer robot challenge human champions appears quite remote. We did not discuss the robotic aspect of this challenge, but it should be clear that good progress has been made on the computational aspect, and that much remains to be done in this, once again, new field.

From an OR specific point of view, we have described a stochastic dynamic programming framework to model an optimal strategy of a generic billiard player in the presence of noise. The key contribution is an improved estimation of the table value at some stage that takes in consideration the expectation of the difficulty to complete a sequence of winning shots and not only the current one. The present modeling is coherent with the conclusions of Archibald et al [START_REF] Archibald | Success, strategy and skill : an experimental study[END_REF] who state that 'strategic skill' is decisive whenever 'the execution skill' is imperfect.

On the other hand, we have presented an improved player simulator based on an accurate optimization tool to drive the cue ball trajectory towards the desired spot with the 'best' table value. Numerical simulations on repeated launching of 8-ball games were performed with relative success, including indirect shots like bank and combine shots, confirming the robustness of our player.

Current work aims at improving the player skill to cope with more realistic situations including the precise modeling of elastic collisions with banks and the breaking of clusters of balls.

Finally, the introduction of defensive strategies to take in consideration the game theoretical aspects will be the direction of further studies. It is indeed evident that the development of future competitions between virtual players controlling robots acting on a real table will progressively increase the level of noise effects, thus turning more crucial the improvement of the 'strategic skill' of the players.

Figure 1 :

 1 Figure 1: Reachable regions. For a simple shot in the upper right corner, we observe the reachable regions for Billiards (left) and PoolFiz (right).

Acknowledgments

We are grateful to François Gaumond and Benoit Hamelin for their careful reading of the manuscript and useful comments and François Gaumond's work on the Billiards-PoolFiz interface.


Ph Brax

The Cosmological Constant Problem

Observational evidence seems to indicate that the expansion of the universe is currently accelerating. Such an acceleration strongly suggests that the content of the universe is dominated by a non-clustered form of matter, the so-called dark energy. The cosmological constant, introduced by Einstein to reconcile General Relativity with a closed and static Universe, is the most likely candidate for dark energy although other options such as a weakly interacting field, also known as quintessence, have been proposed. The fact that the dark energy density is some one hundred and twenty orders of magnitude lower than the energy scales present in the early universe constitutes the cosmological constant problem. We review various aspects of the cosmological constant problem and some interesting scenarios using supersymmetry or extra-dimensions attempting to solve one of the most puzzling issues in physics.

The Cosmological Constant

It is now common knowledge that the Universe is expanding. More puzzling is the recent evidence that this expansion is accelerating. Not only distant galaxies are receding away from us, they do so in an accelerating fashion. The quest for an explanation of the acceleration of the Universe is still in its infancy. Many scenarios have been proposed. No complete understanding has been reached yet. The purpose of this introductory review is to present parts of the observational evidence and some of the theoretical models which have been proposed. More details and a comprehensive list of references can be found in the reviews [START_REF] Binetruy | Cosmological Constant vs. Quintessence[END_REF][START_REF] Carroll | Why is the Universe Accelerating?[END_REF][START_REF] Carroll | The Cosmological Constant[END_REF][START_REF] Padmanabhan | Cosmological Constant-the Weight of the Vacuum[END_REF][START_REF] Peebles | The Cosmological Constant and Dark Energy[END_REF]. The figures have been taken from the research articles [START_REF] Knop | the Supernova Cosmology Project[END_REF][START_REF] Spergel | [END_REF]8,9].

The dynamics of the Universe are described by the general theory of relativity. In general relativity, matter and geometry are intrinsically entangled. Space-time is curved by matter as well-known from black-hole physics where the gravitational effects are so strong that even light cannot escape to infinity. The Einstein equations relate on the one hand geometry, in the form of the Ricci tensor R µν , the metric tensor g µν and the curvature R, and matter represented by the energy-momemtum tensor

T µν R µν - 1 2 g µν R = -8πG N T µν (1)
where G N is Newton's constant of gravitation. The Ricci tensor measures the curvature of space-time while the energy-momentum tensor embodies the effects of pressure and energy. These equations relate tensors, here four by four matrices, leading to highly non-linear equations. All gravitational phenomena are governed by Einstein equations. In particular we will be interested in cosmological features occurring on time-scales of the order of the age of the Universe and on distance scales as large as the size of the Universe. Even on such extraordinary scales, general relativity is thought to apply and govern all cosmological phenomena. When trying to analyse the cosmology of galaxies and galaxy clusters, it is convenient to model the behaviour of matter with only two quantities: energy density and pressure. This is enough to characterise dust-like matter as well as radiation, two of the key components of our Universe. For ordinary matter and radiation, the energy momentum tensor is diagonal and determined by the energy density ρ measured in units of energy per unit volume and p the pressure. All energy scales will be measured in units where h = c = 1. This implies that length scales can be converted into inverse energy scales, therefore energy densities will be expressed in electron-Volt to the fourth power.

In 1917, Einstein applied his equations to cosmology. Lacking the observational evidence on the recession of galaxies (discovered by E. Hubble in 1929), Einstein assumed that the Universe was closed and static. A closed universe is such that space is spherical, i.e. spatially finite with no boundary. A static Universe is such that its shape is time-independent. Unfortunately these two hypotheses are incompatible with Einstein's equations. In order to accommodate a closed and static Universe, Einstein modified his equations by introducing a new term: the cosmological constant Λ

R µν - 1 2 g µν R = -8πG N T µν + Λg µν (2)
The positive cosmological constant Λ introduces a repulsive effect which compensates the gravitational pull. A closed and static Universe is a solution of the modified Einstein equations with a radius 3 Λ . The cosmological constant Λ has dimension two in energy unit. It can be interpreted as another source of matter with a diagonal energy momentum-tensor (as for dust-like matter and radiation). The pressure due to a cosmological constant is the opposite of the energy density corresponding to a so-called equation of state w = -1. The equation of state in statistical mechanics is the relation between pressure and energy density. In cosmology it is common practise to call the equation of state the proportionality coefficient relating pressure and density. The repulsive nature of the cosmological constant is due to a negative pressure. We will encounter other types of matter with the same kind of repulsiveness when discussing scalar fields.

After the discovery of the galaxy recession, the necessity of the cosmological constant became doubtful. Indeed Friedmann and then independently Lemaitre showed that the Hubble flow of galaxies could be explained within general relativity without the need for a cosmological constant. Until recently the cosmological constant was deemed unphysical as can be read in the highly influential textbook on the classical theory of fields by Landau and Lifschitz.

Since the early eighties, the inflationary paradigm has reinstated the cosmological constant at the forefront of current research. Indeed the standard cosmological model relying on the homogeneity, i.e. the Copernican principle that no particular place in the Universe plays a special role, and the isotropy of the Universe , i.e. on large scales there is no preferred direction, suffers from many problems, among others the horizon problem. As the velocity of light is finite, how come that regions of space which were not in causal contact in the past look so similar now? In particular how come that the temperature of the cosmic microwave background, the remnant radiation from the very early Universe is so isotropic? This can be explained using inflation, a period of exponentially fast expansion in the early Universe. When inflating, regions in causal contact are blown up so fast as to become acausal.

So what is the connection between inflation and the cosmological constant? Inflation can be understood as driven by a constant energy density acting as a cosmological constant. This can be easily grasped by looking at one of the most important equations of cosmology: the Friedmann equation

H 2 = 8πG N ρ 3 + Λ 3 - k a 2 (3)
Here a is the cosmic scale factor measuring the size of the Universe and H = ȧ a is the Hubble rate corresponding to the ratio between the speed of receding galaxies and their distance. In a closed and static Universe the Hubble rate vanishes H = 0, a compensation due to the curvature term k = 1 and the cosmological constant Λ. In a flat Universe k = 0 with no cosmological constant Λ = 0, the Hubble rate is non-vanishing due to the presence of matter ρ. In a flat Universe dominated by a constant cosmological constant Λ the Hubble rate is constant. This is the de Sitter model leading to an exponential increase of the scale factor a. Primordial inflation in the early Universe is thought to occur due to a large energy density mimicking the presence of a cosmological constant. This is enough to create an enormous blowing up of distance scales. The end of inflation is due to the sudden transfer of the inflationary energy density to ordinary particles. The origin of this energy density is often modelled by a scalar field. This idea also reappears in models of quintessence as we will discuss shortly.

After inflation the Universe is radiation dominated and then matter dominated. In the matter dominated era, structures such as galaxies are formed due to the collapse of matter density fluctuations seeded by quantum fluctuations in the early universe. Well-known physics such as particle and nuclear physics constrain the evolution of the Universe since nucleosynthesis (when elements such as helium were created). In particular, it is observationally clear that a cosmological constant, if present, must be negligible from nucleosynthesis till the very recent past measured in redshift denoted by z and defined by a = a0 1+z where a 0 is the scale factor of the Universe now, i.e. from a red-shift of a few thousand to one. The red-shit z is observationally accessible from the displacement of the light spectra coming from distant objects compared to the light spectra measured on earth. In terms of age, a red-shift of unity corresponds to events occurring roughly at a third of the age of the Universe. In the recent past from a red-shift of order unity, it seems that the cosmological constant plays a significant role in the dynamics of the Universe.

Observations and the Cosmological Constant

In cosmology, empirical results have a different status from ordinary laboratory experiments. Indeed we have access to a single Universe and one cannot tamper with the fate of the Universe by changing parameters as one would do in a laboratory experiment. Moreover, observations of distant phenomena are plagued with uncertainty, known as systematics, due to our incomplete understanding of features such as the intergalactic medium. Another important source of uncertainty springs from the difficulty of measuring distances. All these issues are highly relevant when interpreting one of the major sources of information on the cosmological constant: the Hubble diagram as deduced from the explosion of type Ia supernovae. These supernovae are believed to result from the explosion of white dwarfs accreting neighbouring stars whose mass go above a threshold known as the Chandrasekar limit. Recently type Ia supernovae have been used as standard candles, i.e. they are assumed to be all of the same type from low red-shift to z ∼ 1. This hypothesis is borne out by their supposed common origin. The intrinsic luminosity of type Ia supernovae is considered to be constant with M ∼ -19.5, as bright as the whole galaxy they inhabit. Distances are measured by astronomers using the magnitude difference m -M where m is the apparent magnitude and M the absolute magnitude of an object. This difference is nothing but the logarithm of the luminosity distance obtained by using the inverse square decrease of the measured flux of light received on earth compared to the intrinsic luminosity of a distant object. The apparent magnitude of type Ia supernovae can be inferred as a function of the red-shift z. The luminosity distance depends on the geometry of the Universe. At small red-shift, the luminosity distance is proportional to the red-shift of an object. For more distant objects, this linear relation is distorted when the Universe accelerates. Hence, the measurement of the luminosity distance gives a direct clue about the acceleration of the Universe. The quadratic correction the linear relationship between the red-shift and the luminosity distance depends on the acceleration parameter q 0 now. A non-vanishing and negative q 0 indicates that not only the Universe is expanding but the expansion itself is accelerating. It seems that, as seen in figure 1, this is the case. Possible sources of uncertainty could be an intrinsic difference between supernovae at different red-shifts and extinction of the light received on earth due to the intergalactic dust.

The acceleration parameter is crucially related to the matter content of the universe q 0 = Ωm 2 -Ω Λ where Ω m is the matter fraction and Ω Λ is the cosmological constant fraction. The energy fraction Ω i is the ratio of the energy density of a species i to the critical density of the Universe ρ c . The critical energy density of the Universe is the energy density which would lead to the present Hubble rate, i.e. would explain the recession of galaxies, in a flat Universe with no cosmological constant or dark energy. It has been measured to be ρ c ≈ 10 -48 GeV 4 . Measurements of q 0 give access to one relation between the cosmological constant and matter fractions. Another constraint is provided by the cosmic microwave background.

The temperature anisotropies in the cosmic microwave background allows one to constrain the cosmological fractions. These anisotropies are one of the benchmarks of modern cosmology. Their origin gives us a hint about the nature of the early universe. The cosmic microwave background was discovered in 1965 by Penzias and Wilson. It corresponds to a bath of radiation at the very low temperature of 2.7 K. It appears to be completely isotropic, i.e. photons arising from all directions in the sky have the same temperature. It is only in 1992 that the satellite COBE measured fluctuations in temperature of the order of 10 -5 . Such small fluctuations are not uniformly distributed on the sky, they can be decomposed into the spherical harmonics -like the eigenstates of the hydrogen atom. The origin of these fluctuations is thought to be due to quantum fluctuations in the early universe. These quantum fluctuations result in radiation energy density fluctuations. When matter and radiation decouple around z = 1300, at the last scattering surface, the photons are then nearly free. These photons, red-shifted by the expansion of the Universe, are the ones composing the cosmic microwave radiation. Small fluctuations in the radiation energy density at the last scattering surface appear to us as small temperature fluctuations. These fluctuations are are random variables which are easier to characterise using their power spectrum C l depending only on the multipole number l. The statistical average is taken over the possible realisations of the random processes creating the primordial fluctuations. Of course we have only one realization (our Universe) so observationally one has to resort to the ergodic hypothesis according to which the statistical average and the spatial average over the sky are equal.

The latest results on the C l spectrum have been obtained by the WMAP experiment. In particular a structure of acoustic peaks is clearly observed. These peaks correspond to the wave patterns of the temperature fluctuations across the sky. Small l is equivalent to large structures whereas large l probes small structures. One prominent feature of the C l spectrum is the existence of a large first peak whose location is related to the total matter content of the universe

Ω 0 = Ω m + Ω Λ by l peak ∼ 220 Ω -1/2 0 .
The measurement of the first peak location confirms that our Universe is nearly flat Ω 0 ∼ 1 leading to a curvature k = 0. Combining this result with the supernova measurements one obtains that the matter content of the Universe is such that

Ω m ≈ 0.3, Ω Λ ≈ 0.7 (4)
It is conspicuous that this result is also corroborated by a third type of observation determining the matter density Ω m alone. There are many different ways of estimating the matter density of the Universe, some of them like gravitational lensing use the property that light rays are bent by masses in general relativity. They all converge to a value of 0.1 ≤ Ω m ≤ 0.4. This is enough to ensure that matter is not enough to guarantee the flatness of space-time. Another kind of matter, very different from the type of baryonic matter forming galaxies, is needed. It has been coined dark energy in contrast with cold dark matter which is responsible for the gravitational collapse leading to the formation of galaxies. Either in the form of a cosmological constant or some other type of candidates such as quintessence, dark energy represents 70% of the energy balance of the Universe.

One would like to characterise the dark energy component of the Universe. A very useful feature is the equation of state w defined as the ratio between pressure and energy p = wρ. The Universe comprises different types of matter of very different equations of state. Radiation has w = 1 3 while Cold Dark Matter (CDM) and ordinary dust like matter are pressure-less w = 0. A cosmological constant is such that w = -1. Observation indicates that the equation of state of dark energy should be less than -0.8, see figure 3. Exotic types of matter with a negative equation of state are favoured. In particular, as seen in figure 4, the cosmological constant is one of these possibilities. It even seems that equations of state w < -1 are not experimentally excluded. This would violate the energy conditions of general relativity. In particular, energy densities would not be automatically positive. This can be realized using a ghost (or phantom) scalar field with a negative kinetic energy. This type of field would be rolling towards the maxima of its potential where the equation of state would be w = -1. However, the excitations of the phantom field would have a negative mass jeopardizing the stability of space-time. Empty space-time could decay into ordinary particles and phantoms. Hence such models lead to very serious problems which make them highly contrived. In the following we will examine alternatives to a pure cosmological constant with an equation state 0 > w > -1

3 Particle Physics and the Cosmological Constant

The cosmological constant problem springs from the blatant mismatch between the typical energy scales of particle physics, and therefore of all the physical phenomena taking place in the early Universe, and the energy scale Ω Λ ρ c . It is ρ c ≈ 10 -48 GeV 4 , i.e. an energy scale of order 10 -3 eV. Recall that the mass of the electron is m e ≈ 0.5 MeV while the mass of the proton and the neutron is close to m p ≈ 1 GeV. Already the critical energy density of the Universe is twelve orders of magnitude lower than the typical scale of nuclear physics Ω Λ ρ c << m 4 p ≈ 1GeV 4 . To have a better understanding of the chasm that separates the observed cosmological constant and particle physics scales, a few notions of high energy physics must be recalled.

Particle physics has fulfilled an impressive unification programme. By looking at shorter and shorter distance scales, the laws of physics simplify drastically reaching a climax with the electro-weak unification as predicted by the Weinberg-Salam model and tested to high precision at accelerators such as LEP at CERN in Geneva. Going up in energy, the electron-volt is the atomic physics scale, while the proton mass m p ≈ 1 GeV is the nuclear physics scale. Above the mass of the W and Z bosons of order 90 GeV, the weak force responsible for radioactivity and electromagnetism become a single electro-weak force. The scale of 100 GeV is the current energy barrier beyond which particle physics models have not been tested experimentally. The new LHC (Large Hadron Collider) accelerator at CERN which is due to operate before the end of the decade will go beyond that threshold and probe the Higgs physics. The Higgs particle is essential to the theoretical architecture of the electro-weak theory. Its detection would be a major achievement of the unification programme. Above the TeV scale (1000 GeV), particle physicists are prone to speculation. A host of models have been proposed ranging from supersymmetry to extra dimensions. We will come back to these models later. Eventually the final energy frontier is set by the gravitational Planck energy

m Pl = hc 8πG N (5)
which is m Pl ≈ 2.4 10 18 GeV. This is the scale above which gravity is not negligible anymore at the subatomic level. Strong gravitational effects are expected which may distort our vision of space-time. This might be the beginning of the string theory realm where particles would be best described by small open and closed strings. The cosmological constant scale 10 -12 GeV is thirty orders of magnitude lower that the Planck scale. Particle physics has a strong impact on the cosmological constant. First of all one must realize that the cosmological constant is nothing but the vacuum energy. Vacuum energy is a well-known concept in quantum mechanics. Consider the harmonic oscillator with its eigen-energies E n = (n + 1 2 )hω. The expectation value of the energy operator in the vacuum is hω 2 . It is not zero as one may have expected classically. In particle physics, particles are described by quantum fields corresponding to an infinite collection of harmonic oscillators. The vacuum energy associated to a particle is therefore an infinite sum n=∞ n=0 hω 2 = ∞. This infinite contribution is at the heart of renormalisation theory. In flat space-time where one neglects the influence of gravity, as it is the case in accelerator experiments, it makes sense to subtract an infinite contribution to the vacuum energy leaving a finite renormalised energy density. This is not physical in curved space-time where the energy density of the vacuum influences the geometry of space-time. In field theory the contribution to the vacuum energy is regularised, the infinite contribution is not physical and turns out to be ρ vacuum ∝ M 4 where the possible particle masses cannot exceed a certain energy scale M . Such an energy scale is called a cut-off. It represents the maximal energy scale for which a given particle physics model is adequate. For the electro-weak theory M ≈ 100 GeV while models beyond the electroweak theory may be valid up to m Pl . Hence quantum fluctuations lead to a non-vanishing vacuum energy contributing to the cosmological constant.

Quantum effects up to the Planck scale give a contribution of order m 4 Pl to the cosmological constant. Assuming that the Universe has a bare cosmological constant Λ 0 , the observed dark energy is then Λ 0 + m 4 Pl ≈ 10 -48 GeV. This requires to adjust Λ 0 to 120 orders of magnitude. No physical justification to such a fine-tuning is known. Even if one could accommodate such an enormous cancellation, contributions to the vacuum energy from the electro-weak phase transition would give a contribution of order M 4 W to the vacuum energy. Of course nobody knows how to cancel such disparate contributions to the dark energy. In conclusion, the vacuum energy of particle physics gives large contributions to the dark energy. All these contributions have to cancel each other somehow. In the following we will present partial attempts to tackle these issues.

Supersymmetry and the Cosmological Constant

One can separate the cosmological constant problem into two issues. The first one consists in understanding how the cosmological constant could be zero. The second one is concerned with generating a small vacuum energy away from the vanishing cosmological constant. In this section we will examine the possible vanishing of the cosmological constant. The following section, on quintessence, will be devoted to generating a small vacuum energy. Exactly vanishing entities in physics are generally associated with symmetries. For instance, the gauge invariance A µ → A µ + ∂ µ λ of QED (Quantum Electro-Dynamics) leads to the vanishing of the mass of the photon. This springs from the impossibility of writing a quadratic and Lorentz invariant term A µ A µ in the Lagrangian of QED. Such a term would violate gauge invariance. Could it be that the cosmological constant vanishes for symmetry reason? This would be the case in a supersymmetric world.

Particles are classified according to their statistics, integer spin particles are Bosons obeying the Bose-Einstein statistics while half-integer spin particles are Fermions obeying the Fermi-Dirac statistics. Photons are Bosons while electrons are Fermions. Usual symmetries of nature such as Lorentz symmetry do not mix Bosons and Fermions, they preserve the statistics of each particle. In 1971 while trying to introduce Fermions in string theory, P. Ramond invented an unusual symmetry exchanging Bosons and Fermions: supersymmetry. Supersymmetry is a framework within which most models of particle physics can be embedded. There is for instance a supersymmetric electro-weak theory extending the electro-weak theory. How does one construct such theories? First of all supersymmetry associates to each particle another particle called a superpartner. Electrons are spin 1 2 particles whose superpartners are the selectrons, spin 0 particles. Photons with spin 1 are associated to photini of spin 1 2 . Earlier attempts trying to identify the photino with the electron failed (they have a different charge). The supersymmetric electro-weak theory has twice as many particles as the electro-weak theory.

Another conspicuous feature of supersymmetry is its link to the Poincaré group. The Poincaré group comprises the Lorentz group, i.e. rotations and Lorentz boosts, and the translation group. When transforming a particle into its superpartner and then back into the original particle, the particle is translated in space-time. This fundamental property of supersymmetry is at the origin of its special link with the vacuum energy of the Universe. Indeed denoting the generators of supersymmetry by Q, they satisfy Q Q + QQ = 2E in the rest frame of a massive particle of energy E. This is the mathematical formulation of the fact that squaring a supersymmetry transformation amounts to a translation. Taking the expectation value of the left hand side in a given normalised state of the theory |φ > gives |Q|φ > | 2 +| Q|φ > | 2 = 2E from which we deduce that E ≥ 0 the energy is always positive in a supersymmetric theory. Moreover the supersymmetric vacuum |0 > such that Q|0 >= Q|0 >= 0 has vanishing energy E vacuum = 0 Hence the vacuum energy of a supersymmetric theory is protected and vanishes. Such an astonishing result would provide a solution to the cosmological constant problem but for a hitch: the Universe is not supersymmetric. Indeed the superpartners have never been observed. If they exist at all, the most likely explanation for their non-observation would be a large mass splitting within supersymmetric multiplets. This requires to break supersymmetry.

The role of supersymmetry in alleviating the cosmological constant problem requires to incorporate gravity in the supersymmetry framework. This is realized within supergravity where ordinary particles are complemented with the gravitational multiplet. It comprises the graviton and its superpartner the gravitino. The graviton is the particle mediating gravity, in the same vein as photons mediate electromagnetism. It is a spin 2 particle, its superpartner the gravitino is a spin 3 2 particle. Gravity being of infinite range, the graviton and the gravitino are massless particles. This is true as long as supersymmetry is not broken. In the most common supersymmetry breaking scheme, the socalled gravity mediated breaking, the gravitino becomes massive in manner akin to the way the W boson becomes massive in the electro-weak theory, it is the super-Higgs mechanism. As a result, the superpartners become heavier than the particles of the electro-weak theory. The mass splitting is of the order of the gravitino mass and is expected, if supersymmetry is ever to be detected, to be of order 100 GeV. A larger mass splitting would rule out supersymetry as a viable candidate of physics beyond the electro-weak theory.

In supergravity the vacuum energy is not guaranteed to vanish. Moreover as soon as supersymmetry is broken, the vacuum energy picks up a value of order ρ vacuum = m 2 3/2 m 2 Pl ≈ 10 40 GeV 4 where m 3/2 is the gravitino mass. Notice that this is a lot less than m 4 Pl but still much too high to provide a plausible explanation for the tiny value of the observed cosmological constant. So despite all its promises supersymmmetry alone is not enough to provide a mechanism explaining either the vanishing of the cosmological constant or its extremely small value.

Quintessence

Judging on the difficulty of obtaining a proper explanation for the almost zero value of the cosmological constant, one may attempt to treat the cosmological constant in a two-pronged approach. First postulate that some unknown mechanism is at play and leads to a vanishing cosmological constant. Then adjust the small amount of dark energy using four dimensional field theory. Of course this approach anticipates an eventual breakthrough which would explain the first step. The small vacuum energy can be modelled using scalar fields with simple potentials. This bears the name of quintessence.

Let us list some of the requirements that one may impose on quintessence models. First of all they must reproduce the vacuum energy now. In doing so, one would prefer not to fine-tune energy scales to values way below particle physics scales. Similarly if the energy of the scalar field were to dominate earlier, i.e. during nucleosynthesis, the model would lead to such a change in the Hubble rate that the delicate balance necessary to produce all the elements would be dramatically modified. In practice the scalar field energy cannot start dominating much before z = 1. Such a coincidence problem, i.e. why the vacuum energy dominates nearly now and not in the past or even in the future is one of the unsolved puzzles of quintessence models. One would also like to obtain models such that the dynamics of the scalar field now does not depend too much on the initial conditions set in the early universe. Indeed having to set the values of field during the early Universe would be seen as an unexplainable finetuning. An explanation could be provided by the anthropic principle claiming that initial conditions must be set so that our Universe is the way it is in order to accommodate the existence of life on earth.

The dynamics of a scalar field mimics a perfect fluid with a pressure identified with the difference between the kinetic energy and the potential energy V (φ). The energy density is the sum of the kinetic energy and the potential energy. Quintessence relies on the possible existence of runaway potentials, i.e. decreasing potentials vanishing at infinity. Just like on a ski slope, the field φ rolls down the potential. For properly chosen potentials the value of the field and its kinetic energy can be arranged in such a way that the energy density is 70% of the critical energy density of the universe now. There seems to be an infinite choice of rolling potentials leading to this property. In fact, one may restrict this infinity by requiring the existence of an attractor, i.e. a long time solution of the scalar field equations of motions attracting all possible solutions. Of course the advantage of attractors is to get rid of the dependence on initial conditions. The scalar fields eventually follows the attractor, independently of the initial conditions. Attractors do exist as long as the potential decreases steeply enough. We will discuss two explicit families of potentials: exponential potentials and inverse power law potentials. Choosing the potential to be

V (φ) = V 0 e -λ φ
m Pl , the field rolls down mimicking a fluid of constant equation of state ω φ = λ 2 3 -1. Hence it leads to an equation of state close to -1 for small λ. Moreover, in the presence of dust-like matter, one can show that the scalar field eventually dominates provided its equation of state is negative. In that case it is also a late time attractor. Hence for small λ the exponential model provides an interesting quintessence model. Now it does not alleviate the coincidence problem. One must tune the value of the field now so that it is marginally dominant, in other words our Universe would not have reached the late time attractor and would be trawling in a transient state.

To remedy this problem one may invoke models where the attractor exists in the past. Consider the potential V (φ) = M 4+α φ α where α is positive . As long as the scalar field is subdominant one can find an attractor where the scalar field energy density decreases slower than the matter density, implying that the scalar field density overcomes the matter density eventually. This happens as soon as φ reaches a value of order m Pl . After that the scalar field rolls slowly φ ≈ m Pl . This allows to reformulate the coincidence problem: the scalar field dominates in the recent past provided V (m Pl ) is of the order of the critical density now. This necessitates to adjust the value of M . For instance if α = 6, this leads to M ∼ 10 6 GeV, a scale which is compatible with high energy physics. Of course, the value of the energy scale M has to be fine-tuned. This is a pity as no clear explanation for both the value of the parameter α and the energy scale M can be provided.

These models suffer from a serious problem, the value of the field is so large that it is difficult to justify a theory involving a single scalar field. One may invoke supergravity whose description up to the Planck scale is more justified. In that case, the supergravity equivalent of the inverse power law potential

is modified V (φ) = M 4+α φ α e φ 2 m 2
Pl . This potential leads to no modification in the Figure 5: The energy densities of matter (middle curve), radiation (top curve) and quintessence (bottom curves for the inverse power model and its supergravity version) as a function of the red-shift. It illustrates the coincidence problem: why do the energy densities turn out to be so close now and in the recent past? (taken from [9])

Figure 6: The evolution of the equation of state for the inverse power law potential and the supergravity corrected power law potential. The equation of state is closer to -1 now for the supergravity modified potential. Notice the frequent variations of the equation of state (taken from [9]).

early Universe. As soon as the scalar density dominates, the potential becomes larger than the inverse power law case, hence an equation of state closer to -1 is obtained. This type of potential can be used phenomenologically as a benchmark for testing the observability of quintessence models. Another remarkable feature of quintessence is the extreme lightness of the quintessence field with a mass of the order of the Hubble rate now H 0 ∼ 10 -43 GeV For all practical purpose, the quintessence field can be considered to be massless leading to strong deviations from general relativity. The only possible wayout is to impose that the quintessence field is almost decoupled from known particles. This puts severe constraints and jeopadises the naturality of possible models. Similarly there is no symmetry preventing a direct coupling between the quintessence field and the kinetic terms of the photon field in QED. This leads to large variations of the fine structure constant, in contradiction with known bounds.

Other types of potentials have been presented in the last few years. As long as a comprehensive theory describing the dynamics and the origin of the quintessence scalar field is not obtained, all quintessence models only give a partial understanding of the value of the vacuum energy now.

Extra-Dimensions and the Cosmological Constant

So after all it seems that a satisfactory explanation for the cosmological constant problem may be out of reach. This is backed up by a no-go theorem proven by S. Weinberg and stating that the vanishing of the vacuum energy cannot be solved with field theories involving a finite number of scalar fields. Of course such theorems can always be circumvented by applying methods not covered by their premises. A possible explanation may come from the putative existence of extra-dimensions. The first model with one extra-dimension was proposed in the 1920s by Kaluza and Klein in an attempt to unify gravity and electromagnetism. Since then the number of extra-dimensions has been gradually increasing. In particular, string theory predicts that the highest number of dimensions is 11. This is obtained from the existence of an unique supergravity in 11 dimensions accommodating no particle of spin higher than 2. By compactifying one of these dimensions on a small circle, one obtains the 10 dimensional string theories. In string theory, there exists extended objects called p-branes of dimension p + 1. They represent higher dimensional object generalizing point particles p = 0 and strings p = 1. In particular, one popular model consists in imagining that the known particles, the strong, weak and electromagnetic forces reside on a 3-brane. Only gravity is allowed to propagate outside the brane, in the bulk. The simplest configuration is 11 dimensional with two boundary branes, p = 9, separated by a finite interval. One of the boundaries carries the electro-weak and strong interactions. By compactifying 6 of the 7 extra-dimensions on a manifold called a Calabi-Yau manifold, one gets a five-dimensional model where the extra-dimension is an interval. Compactification is a process whereby some space dimensions are curled up and of small size. To a good approximation, space-time appears to have fewer dimensions, e.g. one can go from 11 to 5 dimensions by curling up 6 dimensions. A Calabi-Yau manifold is a 6-dimensional space with vanishing Ricci tensor. This situation has been drastically simplified by Randall and Sundrum where the bulk interval carries a negative cosmological constant and the two boundary branes have opposite tensions related to the square root of the bulk cosmological constant. The tension of a brane is similar to the tension of a soap bubble preventing its collapse under gravity.

The equations of general relativity in five dimensions have solutions where the brane configuration presents flat boundaries, i.e. the metric on the boundaries is invariant under the Poincaré group. This invariance guarantees the vanishing of cosmological constant in four dimensions as seen by an observer on the boundary branes. So this would provide an extra-dimensional explanation to the vanishing of the cosmological constant. Is it devoid of any fine-tuning?

Of course the answer is no. If one modifies the delicate balance between the boundary tension and the bulk cosmological constant, one finds that an observer on the brane would identify two situations. If the brane tensions are increased, adding some energy to the system, the effective cosmological constant is positive. The acceleration of the Universe appears to be due to the increase of the energy on the branes. If one decreases the tensions, the effective cosmological constant would be negative. Of course one could fine-tune the small increase of the brane tensions. This would just be a rephrasing of the four dimensional cosmological constant problem. In the same fashion, one may incorporate more degrees of freedom in the bulk. A likely candidate is a bulk scalar field. In that case, one obtains exponential potentials of the quintessence type with a low value of the coupling constant λ. Unfortunately these models do not allay the cosmological fine-tuning problem as the value of the scalar field now has to be adjusted. Nevertheless, higher dimensional models provide an interesting framework wherein one may either reformulate or even propose new mechanisms whose four dimensional justification would have been debatable. This is the case of self-tuning of the cosmological constant which is a very stimulating possibility. The idea can be formulated in very simple terms. The cosmological constant or the vacuum energy is a source of curvature for the four dimensional dynamics. Could it be that the same vacuum energy on our Universe seen as a 3-brane in a multi-dimensional Universe would curve the extra-dimensions while preserving the flatness of our Universe? As a result, any modification to the vacuum energy, for instance from phase transitions, would not affect the four dimensional dynamics at all. It would simply modify the geometry of unobservable dimensions.

An explicit model can be easily constructed. Consider a free scalar field living in the bulk and coupled exponentially to a four-dimensional brane. The induced geometry on the brane is flat, i.e. the Hubble rate vanishes while the bulk metric is curved with an amount depending onthe brane tension. The metric in the bulk develops a singularity at finite distance where the curvature of five dimensional space-time blows up. The existence of this singularity is a nuisance which may jeopardize the model altogether. In particular, shielding the singularity requires to include a brane at the singularity whose tension has to be fine-tuned to match the tension of the observable brane. The absence of fine-tuning on the observable brane has been replaced by a worse sin: one must fine-tune tensions on branes situated at different points along the fifth dimension.

After all, it may happen that gravity itself needs to be altered. One may modify gravity in five dimensions in order to smooth out the singularity. This is achieved by adding a so-called Gauss-Bonnet term in the Lagrangian of gravity. Such a correction to gravity is suggested by string theory. It arises as soon as quantum corrections to gravity are taken into account. It also turns out that Lovelock theorem guarantees that it is the only possible modification of gravity which preserves the fact that the Einstein equations are second order differential equations. Now the metric in the bulk is non-singular. The price to pay is the need to fine-tune parameters once again. Hence it seems that requiring that no singularity occurs in the bulk is connected to fine-tuning of some parameters, while the absence of fine-tuning is linked to the presence of a singularity in the bulk.

Could it be that supersymmetry in five dimensions solve the cosmological constant problem? It is indeed the case that five dimensional supergravity leads to a vanishing effective cosmological constant on the brane. The only snag is that the necessary step of supersymmetry breaking reintroduces a fine-tuning of the non-zero vacuum energy.

More generally, can one envisage to obtain de Sitter space with a small cosmological constant from the compactification of a higher dimensional supergravity theory? It turns that the Gibbons-Maldacena-Nunez theorem implies that this cannot happen if one compactifies on a static manifold with no boundary. As soon as one allows compactifications on time-dependent spaces, one may obtain de Sitter space. This is only the tip of a very active branch of high energy physics where one tries to generate de Sitter space. This is a subject still in its infancy which may provide some insight into the cosmological constant problem.

Conclusion

We have presented a few aspects of the cosmological constant puzzle. The fact that no physical mechanism providing even a qualitative understanding has been discovered, despite the efforts of numerous physicists, may call for a complete reappraisal. It could be that drastic measures such as modifications of gravity may be necessary. At present, all these models are at best contrived. A more surprising outcome, which may be hinted by observations, is that the acceleration of the Universe could be due to a cosmological constant. In this introductory review we have presented some promising mechanisms, within high energy physics, using either supersymmetry or extra-dimensions.

Figure 1 :

 1 Figure 1: The Hubble diagram giving the effective magnitude of type Ia supernovae up to a red-shift of 1. The blown up region indicates three possible scenarios for Ω m and Ω Λ . The fit with the continuous line corresponds to a spatially flat Universe with Ω Λ = 0.75 (taken from [6]).

Figure 2 :

 2 Figure 2: The WMAP result for the C l 's as defined in the text. Notice the location of the first peak which indicates that the Universe is spatially flat (taken from [7]).

Figure 3 :

 3 Figure 3: The contour plot for Ω m and Ω Λ . The flat Universe k = 0 constraint is indicated as a straight line and the oblong ellipses emanate from the supernovae results (taken from [6]).

Figure 4 :

 4 Figure4: The combined constraints from structure formation, the cosmic microwave background and the supernovae measurements on the equation of state w and Ω m . Notice that the contours are centered around w = -1, a cosmological constant. Values of w < -1 would violate the energy conditions and would certainly require some new physical insight (taken from[8])

brax@spht.saclay.cea.fr