C Gicquel
email: celine.gicquel@ecp.fr

M Minoux

Y Dallery

On the discrete lot-sizing and scheduling problem with sequence-dependent changeover times

Keywords: Lot-sizing, Sequence-dependent setup costs, Setup times, Mixed-integer programming

We consider the discrete lot-sizing and scheduling problem with sequence-dependent changeover costs and times and propose to solve it as a mixed-integer program using a commercial solver. Our approach is based on the extension of an existing tight formulation for the case without changeover times. Computational results conrm the benets of the proposed solution procedure.

Introduction

A wide variety of models for production planning and inventory management has been investigated in operations research. Among them, capacitated lotsizing models aim at determining the optimal timing and level of production complying with given capacity restrictions and such that demand for all products is satised without backlogging. Recent overviews on the lot-sizing literature can be found among others in [START_REF] Drexl | Lot sizing and scheduling -Survey and extensions[END_REF] and [START_REF] Jans | Meta-heuristics for dynamic lot sizing: a review and comparison of solution approaches[END_REF].

In the present paper, the discrete lot-sizing and scheduling problem (DLSP) is considered. The DLSP relies on several basic assumptions (see e.g. [START_REF] Fleischmann | The discrete lot sizing and scheduling problem[END_REF]) : -Demand for products is deterministic and timevarying.

-The production plan is established for a nite time horizon subdivided in several discrete periods.

-At most one item can be produced per period ("small bucket" model) and the facility processes either one product at full capacity or is completely idle ("all-or-nothing assumption"). -Costs to be minimized are the inventory holding costs and the changeover costs.

Here the single level single machine variant of this problem is studied: all items to be produced are end items and share the same constrained resource. In the DLSP, it is assumed that there is a changeover between two production runs for different items, resulting in a changeover cost and/or a changeover time. Changeover costs and times can depend either on the next item only (sequenceindependent case) or on the sequence of items (sequence-dependent case). Signicant changeover times which consume scarce production capacity tend to further complicate the problem. We consider here the most dicult variant: the DLSP with sequence-dependent changeover costs and times (denoted DLSPSD in the sequel).

The DLSP has received much attention in the literature. Complexity results for this problem can be found in [START_REF] Salomon | Some extensions of the discrete lotsizing and scheduling problem[END_REF]. They show that the single machine multi-product case without setup times is NP-hard and that the problem of nding a feasible solution in the presence of sequence-independent setup times is NP-complete. We deal here with the extension of this problem to the case of sequencedependent changeover costs and times. The DL-SPSD under study in the present paper is thus NPhard.

We now discuss into more detail specic contributions on the DLSPSD. [START_REF] Salomon | Solving the discrete lotsizing and scheduling problem with sequence dependent set-up costs and setup times using the travelling salesman problem with time windows[END_REF] reformulate the problem as a travelling salesman problem with time windows and use a dynamic programming-based algorithm to solve it. [START_REF] Jordan | Discrete lotsizing and scheduling by batch sequencing[END_REF] show the equivalence between the DLSPSD and the batch sequencing problem (BSP) and use a specic branch and bound type algorithm for solving the BSP to optimality. In both papers, the mixed-integer programming formulation proposed for the problem is weak and does not provide lower bounds good enough to solve the problem using a commercial solver (see results in section 3.2). However, as pointed out by [START_REF] Pochet | Production planning by mixed integer programming[END_REF], there is now a good knowledge about the "right" way to formulate many simple production planning submodels as mixed-integer programs and, thanks to it, many practical production planning problems can be (approximately) solved using commercial solvers. To the best of our knowledge, these results

have not yet been exploited to solve the DLSPSD. In the present paper, we attempt to close this gap by proposing a new tight formulation for this specic variant of the problem.

The purpose of this paper is thus to introduce a strengthened formulation for the DLSP with sequence-dependent changeover costs and times. This formulation is an extension of the formulation proposed by [START_REF] Wolsey | Solving multi-item lot-sizing problems with an MIP solver using classication and reformulation[END_REF] for the DLSP with sequencedependent changeover costs and zero changeover times. Thanks to this strengthened formulation, the lower bounds provided by the linear relaxation of the problem are signicantly better, enabling a branch and bound type procedure to solve the problem more eciently.

The paper is organized as follows. In section 2, we present the proposed tight formulation for the DLSPSD. In section 3, we discuss the results of some computational experiments carried out to evaluate it.

A tight formulation for the DLSPSD

We present a tight formulation for the DLSP with sequence-dependent changeover costs and times. This formulation is an extension of the formulation proposed by [START_REF] Wolsey | Solving multi-item lot-sizing problems with an MIP solver using classication and reformulation[END_REF] for the DLSP with sequencedependent changeover costs and zero changeover times. In the sequel, we denote it the DSLPSD2 formulation whereas we denote DLSPSD1 the formulation proposed by [START_REF] Salomon | Solving the discrete lotsizing and scheduling problem with sequence dependent set-up costs and setup times using the travelling salesman problem with time windows[END_REF].

Basic formulation

We wish to optimize the production schedule for a set of N items over an horizon featuring T planning periods. A period is indexed by t = 1, ..., T , an item by i = 0, .., N . We agree to use item i = 0 to represent idle periods. We use the following notation:

d it : demand (in units) for item i in period t.

-P it : production capacity (in units per period) for item i in period t.

h i : holding costs per unit and period for item i.

c ij : changeover costs from item i to item j.

-T ij : changeover time from item i to item j. T ij is assumed to be an integer number of planning periods. Decision variables are dened as follows:

-I it : inventory level corresponding to item i at the end of period t.

y it : setup variables. y it equals 1 if the resource is setup for production of item i in period t, and 0 otherwise.

-w ijt : changeover cost variables. If T ij > 0, w ijt equals 1 during the rst period of a changeover from item i to item j, and 0 otherwise. If T ij = 0, w ijt equals 1 in the rst period of production of j, and 0 otherwise. -v t : changeover time variables. v t equals 1 during each period in which a changeover between two items occurs, and 0 otherwise.

In the mixed-integer formulation proposed in table 1, the objective (3) minimizes the sum of inventory holding costs and changeover costs. Note that, in the DLSPSD2 formulation, variables w iit are introduced: w iit = 1 means that the resource is setup for item i both in period t -1 and in period t, i.e. that a production run for item i takes place over periods t -1 and t.

Constraints (4) express the inventory balance. Together with constraints (8), they ensure that demand for each item is fullled without backlogging.

Equalities ( 5) and ( 6) link the setup variables with the changeover cost variables. ( 5) guarantee that item i can be produced in period t -1 if and only if a changeover from i to another item j (possibly j = i) takes place at the beginning of period t. Similarly, [START_REF] Nemhauser | Integer and Combinatorial Optimization[END_REF] guarantee that item j can be produced in period t if and only if a changeover from another item i (possibly i = j) to item j begins early enough (i.e. in period t -T ij ) to be nished at the beginning of period t. [START_REF] Pochet | Production planning by mixed integer programming[END_REF] ensure that in each period, the resource either produces a single product at full capacity, or is idle (i.e y 0t = 1), or is in transition between two items (i.e. v t = 1).

The binary character of the setup variables is represented by [START_REF] Salomon | Solving the discrete lotsizing and scheduling problem with sequence dependent set-up costs and setup times using the travelling salesman problem with time windows[END_REF]. ( 10) and ( 11) state the nonnegativity of the changeover variables: observe, as pointed out by [START_REF] Belvaux | Modelling practical lot-sizing problems as mixed-integer programs[END_REF], that thanks to constraints ( 5)-( 7) and ( 9), there is no need to dene variables w ijt and v t as binary variables.

Valid inequalities

As shown in [START_REF] Wolsey | Solving multi-item lot-sizing problems with an MIP solver using classication and reformulation[END_REF] for the case without changeover times, the DLSPSD2 formulation can be further strengthened through a family of valid inequalities adapted from the ones developed by [START_REF] Van Eijl | On the discrete lot-sizing and scheduling problem with Wagner-Whitin costs[END_REF]. We investigate here an extension of this idea to the case of positive changeover times and propose a family of valid inequalities for the problem (3)- [START_REF] Wolsey | Solving multi-item lot-sizing problems with an MIP solver using classication and reformulation[END_REF].

This can be done using the assumption of Wagner-Whitin costs, constant capacity and no backlogging. In this case, demands and production capacity can be normalized without loss of generality: d it ∈ {0, 1} and P it = 1. We rst introduce some additional notation: -D i,t,τ : cumulated demand for item i in the interval {t, ..., τ }. Demand on item i is binary so that D i,t,τ is equal to the number of positive demand periods for i in {t, ..., τ }.

-S i,q : q th positive demand period for item i. Note that S i,Di,1,t+q denotes the q th period with positive demand for item i after period t. We also introduce the start-up variables z it dened as follows: z it equals 1 if the production of a new lot of item i starts at the beginning of period t, 0 otherwise. These start-up variables are linked to the changeover variables by the equations:

z jt = i:i =j w ij,t-T ij ∀j = 1...N, ∀t = 1...T (1)
Equalities [START_REF] Belvaux | Modelling practical lot-sizing problems as mixed-integer programs[END_REF] state that the production of a new lot of item j begins in period t if and only if a changeover from another item i = j starts "early enough" (i.e. in period t -T ij ) to be nished at the beginning of period t.

With this notation, we have:

Proposition 1. The following inequations [START_REF] Drexl | Lot sizing and scheduling -Survey and extensions[END_REF] are valid inequalities for the DLSP with sequencedependent changeover costs and times:

I it ≥ p q=1 1 -y i,t+q - S i,D i,1,t +q τ =t+q+1 z iτ (2) ∀i = 1...N, ∀t = 1...T, ∀p ∈ {0...D i,t+1,T }
Proof. A sketch of proof is as follows. First note that y i,t+q + S i,D i,1,t +q τ =t+q+1 z iτ = 0 if and only if the resource is not setup for item i in period t+q and no startup for i takes place between the period t+q +1 and the period where the q th demand after period t occurs, i.e. if and only if no production of item i is possible in the interval {t + q, ..., S i,D i,1,t +q }. In this case, the quantity needed to satisfy the q th demand after period t should be in stock at the end of period t. Thus we see that constraints (2) force an increase of the stock of item i at the end of period t by one for each index q for which no production occurs in the interval {t + q, ..., S i,Di,1,t+q }. A detailed proof of the validity of (2) can easily be derived from the above (see also [START_REF] Van Eijl | On the discrete lot-sizing and scheduling problem with Wagner-Whitin costs[END_REF]).

In the computational experiments to be presented in section 3, we use a standard cutting-plane generation method (see e.g. [START_REF] Nemhauser | Integer and Combinatorial Optimization[END_REF]) to strengthen the DSLPSD2 formulation by adding violated valid inequalities [START_REF] Drexl | Lot sizing and scheduling -Survey and extensions[END_REF]. The resulting improved formulation is denoted DLSPSD2*.

Remark

It is interesting to keep in mind that equalities ( 5)-( 6) can be interpreted as ow conservation constraints in a network.

More precisely, we consider a graph G = (V, A). A node v ∈ V corresponds to a item-period pair (i, t). There is an oriented arc a ∈ A from node v 1 to node v 2 if and only if v 1 = (i, t) and v 2 = (j, t+T ij +1). The setup variable y it corresponds to the ow through node (i, t) and the changeover variable w ij,t+1 corresponds to the ow between node (i, t) and node (j, t + T ij + 1). With this interpretation, a production sequence on the resource corresponds to a ow of a single unit through the network, starting from a node (i, 0) and arriving in a node (j, T ). Thus equalities ( 5) and ( 6) can be seen as ow conservation constraints, stating that the ow through a node is equal to the sum of the ows on the arcs directed away from it or to the sum of the ows on the arcs directed toward it.

Due to the presence of positive changeover times, the structure of the graph G used here is seen to be dierent from the one used in [START_REF] Belvaux | Modelling practical lot-sizing problems as mixed-integer programs[END_REF]. Namely, when there are no changeover times, all arcs in graph G link pairs of nodes related to successive planning periods, which is not the case anymore with positive changeover times.

Computational results

In this section, we discuss the results of some computational experiments carried out to evaluate the DLSPSD2* formulation proposed in section 2.

Problem instance generation

We created several sets of randomly generated instances following the procedure described in [START_REF] Salomon | Solving the discrete lotsizing and scheduling problem with sequence dependent set-up costs and setup times using the travelling salesman problem with time windows[END_REF] and [START_REF] Jordan | Discrete lotsizing and scheduling by batch sequencing[END_REF]. The reader is referred to these references for more details. The generated instances dier with respect to the following characteristics: -Problem dimension: The problem dimension is represented by the number of products N and the number of periods T. We use 7 dierent item-period combinations, namely (N, T ) = {(5,20), (10,40), (5,60), (10,60), (15,60), (10,90), (15,90)}, leading to 7 instance sets denoted sets A to G.

-Production capacity utilization: Production capacity utilization ρ is dened as the ratio between the total cumulated demand and the total cumulated available capacity. Because changeover times are nonzero, we experimented dierent medium values for ρ: ρ was varied between 0.5 and 0.75, in steps of 0.05. For each possible combination of problem dimension and production capacity utilization, 5 problems were generated, resulting in 7 × 6 × 5 = 210 instances. All tests were run on a Pentium 4 (2.8 Ghz) with 505 Mb of RAM, running under Windows XP. We used a standard MIP software (CPLEX 8.1.0) with the solver default settings to solve the problem, using either the DLSPSD1 formulation presented in [START_REF] Salomon | Solving the discrete lotsizing and scheduling problem with sequence dependent set-up costs and setup times using the travelling salesman problem with time windows[END_REF] or the DSLPSD2 and DL-SPSD2* formulations presented in section 2.

Comparison of DSLPSD1, DL-SPSD2 and DLSPSD2* formulations

We rst carried out some computational experiments in order to evaluate the reformulation proposed in section 2.1 and the family of valid inequalities derived in section 2.2. The comparison has been limited to the smallest instances (sets A and B) since computation time limits are exceeded for set B instances with the DLSPSD1 formulation.

Table 2 shows the results obtained with the DSLPSD1, DLSPSD2 and DLSPSD2* formulations for the sets A and B instances. For each formulation, we provide: -Variables and Constraints: the average number of variables and constraints.

-#VI : for the DLSPSD2* formulation, the average number of valid inequalities of type (2) added by the cutting-plane generation procedure.

-#Opt: the number of instances out of the corresponding 30 instances that could be solved to optimality within 20 minutes of computation.

-Gap 0 : the integrality gap, i.e. the relative difference between the lower bound provided by the linear relaxation of the problem and the value of an optimal solution. For the DLSPSD2* formulation, we consider the lower bound obtained after the cutting-plane generation procedure has stopped.

-#Nodes: the number of nodes of the search tree explored before a guaranteed optimal solution is found or the computation time limit of 20 minutes is reached.

-CP U IP : the computation time in seconds required to nd a guaranteed optimal solution. If one could not be found, we use the computation time limit of 1200 seconds.

-Gap: the gap obtained after 20 minutes of computation between the best integer solution and the best lower bound found. For performance measures Gap 0 , Nodes, CP U IP and Gap, we provide the average value (on the rst line) and the minimum and maximum values (in brackets on the second line) for the considered set of randomly generated instances.

Table 2 shows that the results obtained with the DLSPSD2* formulation are much better than the ones obtained with the DLSPSD1 formulation. Namely, computation times are signicantly reduced and more instances can be solved to optimality within the time limit while using the DLSPSD2* formulation.

This can be explained by the combination of two advantages: 1. The lower bounds provided by the linear relaxation of the DLSPSD2* formulation are much better than the ones obtained with the DLSPSD1 formulation. This formulation improvement is achieved to a large extent thanks to the use of a small number of valid inequalities (2). This can be seen e.g. for set A instances for which the integrality gap is reduced in average from 84% with the DLSPSD1 formulation to 59% with the basic DL-SPSD2 formulation and 4% with the strengthened DLSPSD2* formulation. 2. The MIP size (number of variables and constraints) is signicantly reduced with the DL-SPSD2* formulation. As a consequence, the time spent at each node of the branch and bound tree to solve the linear relaxation is shorter. This size reduction is explained by the fact that using the DL-SPSD2* formulation, there is no need to introduce explicit changeover time variables v ijt for each possible transition between pairs of items (i, j). Moreover, the set of equalities ( 5)-( 6) are sucient to ensure that positive changeover times between production runs for dierent items are respected. As a consequence, the numerous inequalities needed in the DLSPSD1 formulation to link changeover time variables to setup and changeover cost variables can be eliminated from the formulation.

Thus, thanks to tighter lower bounds and a reduced MIP size, the eciency of the branch and bound procedure embedded in CPLEX solver is signicantly improved while using the DLSPSD2* formulation.

Results with the MIP formulation DLSPSD2*

In order to further validate our approach, we carried out additional computational experiments. More precisely, we considered instances similar to the ones studied in [START_REF] Jordan | Discrete lotsizing and scheduling by batch sequencing[END_REF] and [START_REF] Salomon | Solving the discrete lotsizing and scheduling problem with sequence dependent set-up costs and setup times using the travelling salesman problem with time windows[END_REF], i.e. instances for which (N, T ) = {(5, 60), (10, 60)} (sets C-D). We also used 3 additional sets of larger instances for which (N, T ) = {(15, 60), (10, 90), (15, 90)} (sets E-G). Table 3 displays the detailed results obtained with the DLSPSD2* formulation. We observe that: -For medium size instances (sets C-D), 98% of the generated instances could be solved to optimality within 20 minutes of computation.

-For large size instances (sets E-G), 42% of the generated instances could be solved to optimality within the computation time limits. Moreover the average remaining gap obtained after 20 minutes of computation between the best integer solution and the best lower bound found is small (3.6% on average).

Thus, even if the proposed approach was implemented on a computer with more computing power, these results suggest the potential of the MIP modelling approach to solve instances larger than the ones considered in [START_REF] Jordan | Discrete lotsizing and scheduling by batch sequencing[END_REF] and [START_REF] Salomon | Solving the discrete lotsizing and scheduling problem with sequence dependent set-up costs and setup times using the travelling salesman problem with time windows[END_REF].


Fabien Teytaud
email: teytaud@lisic.univ-littoral.fr

Julien Dehos

On the tactical and strategic behaviour of MCTS when biasing random simulations

Over the last few years, many new algorithms have been proposed to solve combinatorial problems. In this field, Monte-Carlo Tree Search (MCTS) is a generic method which performs really well on several applications; for instance, it has been used with notable results in the game of Go. To find the most promising decision, MCTS builds a search tree where the new nodes are selected by sampling the search space randomly (i.e., by Monte-Carlo simulations). However, efficient Monte-Carlo policies are generally difficult to learn. Even if an improved Monte-Carlo policy performs adequately in some games, it can become useless or harmful in other games depending on how the algorithm takes into account the tactical and the strategic elements of the game.

) two connection games (Hex and Havannah). We aim to understand how the benefit is related (a) to the number of random simulations and (b) to the various game rules (within them, tactical and strategic elements of the game). Our results indicate that improved Monte-Carlo policies, such as PoolRave or Last-Good-Reply, work better for games with a strong tactical element for small numbers of random simulations, whereas more general policies seem to be more suited for games with a strong strategic element for higher numbers of random simulations.

Introduction

Monte-Carlo Tree Search (MCTS) algorithms have had a huge impact on Artificial Intelligence [KS06, Cou07, CSB + 06]. They are now generally used for decision-making problems such as games [GS07, Lor08, Caz09, AHH10, TT09, Stu15, HS14] and planning problems [START_REF] Kocsis | Bandit based Monte-Carlo planning[END_REF][START_REF] Nakhost | Monte-Carlo exploration for deterministic planning[END_REF]. One of the most interesting advantages of the MCTS algorithms is generality. Indeed, since they use Monte-Carlo simulations, they do not require an evaluation function (see Section 3). This makes them well-suited to applications for which expert knowledge is difficult to obtain [START_REF] Finnsson | Generalized monte-carlo tree search extensions for general game playing[END_REF][START_REF] Waledzik | An automatically generated evaluation function in general game playing[END_REF]. A second advantage is that MCTS algorithms are anytime, meaning they can be stopped at any moment and return the best decision found so far [START_REF] Kocsis | Bandit based Monte-Carlo planning[END_REF]. However, they can be costly for some applications. Furthermore, increasing the number of simulations (i.e., giving more time to compute the search) does not guarantee to obtain better results [BCC + 10].

The principle of MCTS is to build a subtree of possible future states of a problem, and to perform many random simulations, called "playouts", in order to evaluate these states. Numerous improvements have been proposed. Well-known examples involve biasing the decisions made to traverse the subtree; for instance, by using the Rapid Action Value Estimate (RAVE) [START_REF] Gelly | Combining online and offline knowledge in UCT[END_REF] or adding expert knowledge [CFH + 10, CHTT09]. Improvements on the Monte-Carlo policy (used for performing playouts) are often more complicated. Indeed, a great deal of studies have been performed with a general success, in trying to learn such a policy. However, the difficulty is that improving the Monte-Carlo policy does not guarantee that the general behaviour of the resulting MCTS will be better. In this article, we aim at understanding why and when a random simulation biasing technique works. To this end, we study two known Monte-Carlo policy improvements (PoolRave and Last-Good-Reply) using two games (Hex and Havannah). Whereas these games have many similarities (they both belong to the family of connection games), they are still differently suited to the Monte-Carlo policy improvements. Therefore, we perform a large number of experiments and analyze a variety of algorithmic parameters and game rules to explain the gain (or loss) that the improvements of the Monte-Carlo policy can bring to MCTS.

The article is organised as follows. Section 2 presents the two application games used in this study (Hex and Havannah). Section 3 presents the MCTS algorithm and three of its well-known improvements (RAVE, PoolRave, Last-Good-Reply). Section 4 contains experiments and results of MCTS on the two application games. In Section 5, we modify one of the applications in order to study the tactical and strategic behaviour of the Monte-Carlo learnings. Section 6 provides our conclusions and points to a future research direction.

Games of Hex and Havannah

Below we briefly describe the two application games used (Sections 2.1 and 2.2). In Section 2.3 we distinguish the tactical and strategic elements in these games.

Hex

The game of Hex is a 2-player board game. It has been created independently by Piet Hein and John Nash during the 1940s. It is played on a hexagonal grid, traditionally on a 11x11 or 14x14 rhombus. Both players put alternately a stone in an empty location on the board. Players must form a chain of stones of their colour between the two board sides of their colour (see Fig. 1). It is proved that there is no possible draw, thus one player must win [START_REF] Berman | Hex must have a winner: An inductive proof[END_REF][START_REF] Gale | The game of Hex and the Brouwer Fixed-Point theorem[END_REF]. Moreover, for this game we know that the first player must have a winning strategy. A way to prove this is to use a strategy stealing argument: the game is finite with perfect information, and draws are not possible, so one of the two players must have a winning strategy. It is important to add that having a stone on the board cannot be a drawback. Then, if the second player has a winning strategy, the first player can play a random move and steal the strategy of the second player. This ensures a first player win.

Many studies have been performed using artificial intelligence for the game of Hex. Currently, the best algorithms for this game combine a Monte-Carlo Tree Search algorithm and a solver [START_REF] Broderick Arneson | Computational Intelligence and AI in Games[END_REF][START_REF] Broderick Arneson | MoHex wins Hex tournament[END_REF]. Because Hex is played and studied by many people, expert knowledge exists and can been use: for instance, with patterns or opening books [START_REF] Maarup | Hex everything you always wanted to know about hex but were afraid to ask[END_REF]. All this is beyond the scope of this article. Here, we are only interested in the Monte-Carlo Tree Search itself, and in particular in the possible learning of the Monte-Carlo part.

Havannah

The game of Havannah is a 2-player board game created by Christian Freeling [START_REF] Schmittberger | New Rules for Classic Games[END_REF]. It is played on an hexagonal board of hexagonal cells. There are 6 corners and 6 edges, but an important point is that corner stones do not belong to edges. Both players play alternately a stone in an empty location on the board. If there is no more empty location and if no player wins then it is a draw. In order to win, a player has to realise one of these three shapes (see Fig. 2).

• A ring, which is a loop around one or more cells (empty or not, occupied by black or white stones).

• A bridge, which is a continuous string of stones connecting two corners.

• A fork, which is a continuous string of stones connecting three edges (edges exclude corners).

Havannah is known to be a difficult game for artificial intelligence, especially because there is no intuitive evaluation function and because of the large state space. Previous studies on this game include using Monte-Carlo Tree Search algorithms [TT09, Lor10, Ewa12].

Tactical and strategic elements in games

As far as we know, the notions of tactic and strategy first appeared in a military context. In this context, a strategy corresponds to the definition of a global plan (or objectives) that will lead to the victory. A tactic corresponds to the different decisions and threats used to gain this plan (or these objectives).

The notions of tactic and strategy also appear in games and have a similar definition. They are notably important for a human player to improve his or her playing. In games, we often talk about long-term plan (strategy) and short-term decisions (tactics). For instance, in Chess, a strategic plan could be to have a better pawn structure in the middle-game or in the end-game. Tactics are short-term decisions in order to achieve this previous plan (for instance, by threatening a piece of higher value).

In this paper, we focus on these notions in the game of Havannah: expert players state that rings correspond to tactical aspects (it is really rare to win with a ring, but rings can be used as local threats) whereas forks are generally considered as the strategic aspect (experts tend to build a global winning plan thanks to a fork).

Monte-Carlo Tree Search based methods

In this section we give a general outline of MCTS in 3.1. Then in 3.2 to 3.4 we briefly discuss three policy improvements, viz. Rapid Action Value Estimate (RAVE), PoolRave, and Last-Good-Reply.

s 0 s 0 s 0 s 0 s 1 s 1 s 1 s 1 s 2 s 2 s 2 s 3
Figure 3: The MCTS algorithm iteratively builds a subtree of the possible next states (circles) of the current problem. This figure illustrates one iteration of the algorithm. Starting from the root node s 0 (current state of the problem), a node s 1 is selected and a new node s 2 is created. A random simulation is computed (until a final state s 3 is reached) and the subtree is updated. From the current state s 0 of a problem, the MCTS algorithm computes the best possible following state to choose. To estimate this best choice, the algorithm iteratively constructs a subtree of possible futures of the problem (i.e., successive possible states, starting from s 0 ), using random simulations. Each iteration of the construction of the subtree is done in four steps, namely: selection, expansion, simulation and backpropagation (see Fig. 3 from [BPW + 12]). The four steps are given in pseudo code in Algorithm 1.

Monte-Carlo Tree Search

The selection step consists in choosing the first node found with untried child actions in the subtree. In the most common implementation of MCTS, called Upper Confidence Tree (UCT), the subtree is traversed, from the root node to a leaf node, using a bandit formula:

s 1 ← arg max j∈Cs 1 rj + C ln(n s1 ) n j ,
where C s1 is the set of child nodes of the node s 1 , rj is the average reward for the node j (the ratio of the number of wins over the number of simulations), n j is the number of simulations for the node j, and n s1 is the number of simulations for the node s 1 (n s1 = j n j ). C is called the exploration parameter and is used to tune the trade-off between exploitation and exploration. Once a leaf node s 1 is selected (i.e., a node of which all possible decisions have not been considered, in child nodes), the next step (expansion) consists in creating a new child node s 2 corresponding to a possible decision of s 1 which has not been considered yet.

The next step (simulation) consists in performing a random game (i.e., each player plays randomly until a final state s 3 is reached), leading to a reward r (win, loss or possibly draw).

Finally (backpropagation), r is used to update the reward in the newly created node and in all the nodes which have been encountered during the selection (see Algorithm 1):

rs4 ← rs4 × (n s4 -1) + r n s4 ,
where s 4 is the node to update, n s4 is the number of simulations for s 4 and rs4 is the average reward for s 4 .

Algorithm return best child of s 0

Rapid Action Value Estimate

The Rapid Action Value Estimate (RAVE) improvement [START_REF] Gelly | Combining online and offline knowledge in UCT[END_REF] is based on the idea of permutation of moves. If a move is good in a certain situation, then it may be good in another one. Thus, to make a decision in the subtree, a RAVE score is added to the bandit formula defined in Section 3.1. For this improvement, it is necessary to keep more information for each node in the subtree. Let us define m = f → s, meaning the move m played in situation f leads to situation s. For each node it is necessary to store the following four numbers.

• The number of wins by playing m in f (already needed for the bandit formula).

• The number of losses by playing m in f (already needed for the bandit formula).

• The number of wins when m is played after the situation f (but not necessarily in f ), called RAVE wins.

• The number of losses when m is played after the situation f (but not necessarily in f ), called RAVE losses.

The numbers of RAVE wins/losses for a move m are large compared to their classic numbers of wins/losses. The variance for estimating the move m will then be lower, but the bias will be higher (as this is an approximation: the move is not played in f ). The idea is to use especially the RAVE score when the number of simulations is small. Its influence progressively decreases as the number of simulations increases. In order to select a move in the subtree, the bandit formula is replaced by:

s 1 ← arg max j∈Cs 1 (1 -β) rj + β r RAV E s1,j + C ln(n s1 ) n j ,
where β is a parameter which tends to 0 as the number of simulations increases. According to [START_REF] Gelly | Combining online and offline knowledge in UCT[END_REF], we can

use β = R R+3nj
where R is a parameter to tune (see Fig. 4).

PoolRave

The PoolRave enhancement [START_REF] Rimmel | Biasing Monte-Carlo simulations through rave values[END_REF] is based on the RAVE improvement. The idea is the same as the RAVE idea, except that instead of using the RAVE values to bias the selection step (tree policy), it is used to bias the simulation step (Monte-Carlo policy). It can easily be combined with the RAVE improvement.

To compute a simulation step for a node n, with the PoolRave improvement, a pool of possible moves is built first, using the RAVE scores of n: for each possible move m of the node n, m is added to the pool if its RAVE score is meaningful (i.e., the number of RAVE simulations of m is greater than a threshold); then the pool is sorted according to the RAVE score and only the N best moves of the pool are kept. Thus, the pool contains the N moves of n which seem to be the best moves according to RAVE (i.e., moves that have the best ratios of RAVE wins over RAVE losses). Once the pool is built, the simulation step consists in playing moves chosen preferably in the pool: a move is chosen in the pool with a probability p, otherwise (with probability 1 -p) a random move is played as in the classic MCTS algorithm. The size of the pool (N ) and the probability of playing a PoolRave move (p) are parameters to be tuned.

Last-Good-Reply

The Last-Good-Reply improvement [START_REF] Baier | The power of forgetting: Improving the last-good-reply policy in Monte-Carlo Go[END_REF] is similar to a plain PoolRave: the goal is to try to have a kind of learning in the playouts. Here, the RAVE moves are not used, but instead, the principle is to learn how to reply to a previous move. During the simulation, each reply to a move for a player is kept in memory. The reply is considered as a success if the simulation is a win. The Last-Good-Reply improvement can be improved with the addition of forgetting: all stored replies made by a losing simulation are deleted. This modification is called the Last-Good-Reply Forgetting -1 (LGRF-1, see Fig. 5).

There exist other versions of the Last-Good-Reply improvement, namely LGRF-2, LGR-1 and LGR-2. LGRF-2 is the same as LGRF-1 excepted that it considers the last two previous moves. LGR-1 and LGR-2 correspond to LGRF-1 and LGRF-2 with no forgetting. In this study, we only use LGRF-1 in our experiments because it works better for our player. This result is similar to the results found in [START_REF] Stankiewicz | Monte-Carlo Tree Search enhancements for Havannah[END_REF].

Comparison of MCTS-based methods

As seen in the previous section, RAVE improves the efficiency of MCTS by introducing some bias in the selection step. PoolRave and LGRF-1 extend this idea by introducing some bias in the simulation step, i.e., the Monte-Carlo part. In this section, we introduce a protocol (4.1), and we evaluate the efficiency of PoolRave and LGRF-1 for the application games, Hex and Havannah (4.2 and 4.3).

Protocol

To evaluate the efficiency of PoolRave/LGRF-1, we compare two algorithms (MCTS+RAVE+PoolRave and MCTS+RAVE+LGRF-1) to a baseline. The baseline is a MCTS player with the RAVE improvement. We have chosen this baseline (and not just a vanilla MCTS) because MCTS+RAVE is now considered as the standard algorithm, particularly for the game of Hex and for the game of Havannah. Thus the difference between the baseline and the improved algorithms is only the Monte-Carlo policy. In order to have a low standard deviation, we run many games (600 games at least for each experiment) and compute the win rate

Hex

We have applied the previous protocol to the game of Hex and obtained the results depicted in Table 1. With the various parameter values we have tested, the probability that PoolRave wins against the baseline stands between 41% and 49%, i.e., PoolRave performs worse than the baseline. For LGRF-1, the win rate stands between 51% and 54%, i.e., LGRF-1 performs slightly better than the baseline. This indicates that, for a game such as Hex, biasing the Monte-Carlo policy step tends to be difficult.

Havannah

The results for the game of Havannah are depicted in Table 2. With a small number of random simulations (1, 000 playouts), biasing the simulation step is very interesting: PoolRave wins 59% to 69% of the games against the baseline, and LGRF-1 about 58%. However, with a higher number of random simulations (10, 000 playouts), biasing is not as interesting: PoolRave's win rate drops below 41% and LGRF-1's win rate below 49%. In fact, the number of playouts has a huge importance on the efficiency of the improvement, as shown in Fig. 6. We may notice that the advantage of the PoolRave enhancement decreases as the number of simulations increases. It even becomes negative above roughly 1, 500 simulations, which is quite small.

Influence of game rules

Both Hex and Havannah belong to the family of connection games. They are quite related, and generally, a good human player at one of these games is also good at the other one. In this section, we try to understand why an improvement such as PoolRave works on Havannah but not on Hex. In 5.1 we discuss winning shapes that win effectively. In 5.2 we modify the rules of the game of Havannah. In 5.3 we perform new experiments for studying the behaviour of PoolRave/LGRF-1 on the modified games. The game of Havannah is interesting because it has both tactical and strategic elements. Therefore, as described in 5.4, modyfing the Havannah rules brings an interesting range of new games (some of them are even close to the game of Hex). Indeed, in the game of Havannah, the tactical short-term threats (rings) allow a win but forks are considered by experts as a more strategic long-term win.

Winning shapes that win effectively

As seen previously, to win a game of Havannah, a player has to realise a winning shape: ring, fork or bridge. In the previous section, we show that PoolRave plays better than the baseline when the number of playouts is small but not when the number of playouts is high (see Fig. 6).

To develop this analysis, we detail which winning shape the winner realised effectively (see Fig. 7). When the number of playouts is small, both PoolRave and the baseline mostly win by realising rings. This can be explained by the fact that, when the number of playouts is small, it is difficult for MCTS-based algorithms to detect that a ring is about to be realised. Since a ring can be realised with a few moves, such algorithms tend to play these moves.

When the number of playouts is high, PoolRave and the baseline win most of the time by realising forks. Indeed, the algorithms have now more "time" to evaluate moves. Thus, they can detect that the opponent player is about to realise a ring and they can evaluate more accurately the benefit of forks. • forks are the most interesting strategies (long-term victories), and

• rings are interesting to do tactical threats (short-term profits). This may also explain why the algorithms with a biased playout policy, such as PoolRave, become worse than the baseline when the number of simulations is large. Since these algorithms tend to make tactical threads, with a small number of playouts some of these threads are successful (they are not detected by the baseline). With a large number of playouts, the baseline can easily detect the threads so the biased playouts are not beneficial anymore. However, the biased algorithms still try to make tactical threads so they dedicate less playouts to elaborate a strategy than the baseline, hence the worse results.

Combining the winning shapes

Below, we design seven new games in order to find a relation between the winning shapes of Havannah and the benefits of an improvement of the Monte-Carlo policy. Indeed, we can easily change the rules by deleting the possibility of winning with one (or two) of the shapes. Thus, we have defined the following games:

• RBF (Ring, Bridge and Fork), which corresponds to the game of Havannah: a player has to realise a ring, a bridge or a fork in order to win,

• R, which corresponds to the game of Havannah without bridge and fork: a player has to realise a ring in order to win,

• B: a player has to realise a bridge,

• F: a player has to realise a fork,

• RF: a player has to realise a ring or a fork,

• RB: a player has to realise a ring or a bridge, and • BF: a player has to realise a bridge or a fork.

All other rules remain the same.

Experiments and results

We performed a set of experiments by using all these "new games" in order to evaluate the benefits of two Monte-Carlo policy improvements (PoolRave and LGRF-1). The goal is to see whether we can find some similarities or logic among these games. Since the benefits of Monte-Carlo policy improvements really depend on the number of playouts, we run experiments with both a small and a large number of playouts (see Fig. 8).

With 1, 000 playouts (see Fig. 8, top), the PoolRave player is better than the baseline on the games RBF and RF (PoolRave 0.5 win rate > 65%). Indeed, PoolRave plays short-term tactics (rings) and the baseline does not have sufficient time to detect them since it also investigates long-term strategies (forks). On strategy-oriented games such as F and BF, the benefits of PoolRave are smaller (win rate about 60%). Here, it turns out that there is no short-term tactics to find, but a biased Monte-Carlo policy makes the algorithm find a quite good strategy sooner. On purely tactical games such as R (and maybe RB and B), it is not easy to find a long-term strategy, which makes both players look for short-term tactics in such a way that no one has a real advantage (most win rates between 45% and 55%).

With 10, 000 playouts (see Fig. 8, bottom), PoolRave plays worse than the baseline but this depends on the game. On RBF and RF (both tactical and strategic games), PoolRave still spends time to evaluate tactical threats (rings) but the baseline has now sufficient playouts to detect them. Since the baseline is more strategy-oriented (which is most promising for such Havannah-like games), biasing the Monte-Carlo policy brings no benefit (PoolRave 0.5 win rate about 40%). On strategy-oriented games such as F and BF, PoolRave does not lose time to evaluate useless short-term tactic (ring), therefore it is almost as good as the baseline. On tactical games (R, RB and B), PoolRave is really inefficient (on R, PoolRave 0.5 win rate < 25% and draw rate = 25%) because it favours exploitation over exploration, which is not interesting for such short-term games.

We may notice that LGRF-1 is more robust to the various games and to the number of playouts, thanks to its forgetting trend. Thus, its gain with 1, 000 playouts is smaller but its loss with 10, 000 playouts is also smaller. However, like PoolRave, LGRF-1 is inefficient on R (with 1, 000 playouts: win rate ≈ 40%; with 10, 000 playouts: win rate ≈ 45% and draw rate ≈ 30%) since the baseline performs quite well on this new game, for which tactical goals are essential.

Discussion

Our results show that improving the Monte-Carlo policy can yield benefits for small numbers of playouts; this is consistent with previous results obtained for Havannah [START_REF] Stankiewicz | Monte-Carlo Tree Search enhancements for Havannah[END_REF] and for Go [START_REF] Baier | The power of forgetting: Improving the last-good-reply policy in Monte-Carlo Go[END_REF]. However, our results also show that improving the Monte-Carlo policy is beneficial only if the game can be won with both a short-term tactic and a long-term strategy. Indeed, when the number of playouts is large, the tactical threads favoured by biased Monte-Carlo policies are not beneficial anymore since they can easily be detected. Moreover, if the game has only strategic elements (or only tactical elements), there is no choice to make between a tactical or a strategic move, which reduces the possible benefit of the biased Monte-Carlo policies.

This seems to confirm our insight that the biased Monte-Carlo policies do not perform very well in Hex because there are no obvious tactical short-term goals, but only long-term wins, involving longer (global) chains in complex configurations. In Havannah, the rings tend to involve smaller, simpler (local) chains which correspond to tactical threats, and those are more likely to be picked up correctly by the biased versions of MCTS.

Finally, we may notice that it is difficult to classify a game as "tactical" or "strategic" (or both), since these notions are more appropriate to characterise a player. The games RBF and RF can be classified as tactical and strategic since a player can effectively make tactical or strategic moves. With the games F and BF, there are no obvious tactical moves leading to a short-term win, so these games can be classified as strategic. However, the games R, RB and B are more difficult to classify because rings and bridges, which were previously seen as tactical threads, are now the only possible winning shapes; so, they can be considered here as "short-term strategies". This may also explain the great variability of the results for these games, in our experiments.

Conclusion

In this article, we studied the impact of biasing the Monte-Carlo policy of the Monte-Carlo Tree Search. To this end, we compared an MCTS algorithm with an unbiased Monte-Carlo policy and an MCTS algorithm with a biased Monte-Carlo policy. We used the classic RAVE improvement (biased tree policy) for all algorithms. For the MCTS algorithm with a biased Monte-Carlo policy, we applied two biasing techniques: PoolRave and LGRF-1.

We did experiments with these algorithms on two connection games, the game of Hex and the game of Havannah. First, we noticed that the algorithms with a biased Monte-Carlo policy (especially the PoolRave improvement) are more efficient on Havannah than on Hex. Subsequently, we studied for Havannah, how the benefits of the biased algorithms are related to the number of random simulations (playouts).

Then, we compared the ability of the algorithms to achieve short-term tactical goals and long-term strategic goals, by modifying the game of Havannah. We found that, when the number of playouts is small, the biased algorithms are beneficial and generally win by realising a ring, which corresponds to a short-term tactic. However, when the number of playouts is high, they become harmful and the most interesting shape is a fork, corresponding to a long-term strategy. Indeed, the (unbiased) opponent has then sufficient playouts to detect short-term tactics. So, dedicating playouts to find tactics is not only useless but also reduces the number of playouts to find interesting strategies.

It is really hard to make general conclusions, with experiments based on only two games. Still, we hope that our study will form a basis for new insights into MCTS and its enhancements. For example, since all the improvements presented in this article have been experimented in the game of Go, it would be interesting to do an analogous study in order to understand why one improvement is better than another one for this game.

Further work is needed to investigate the claim stated in the paper, viz. that improving the MC policy can yield benefits for a small number of playouts. In particular further work is needed to investigate whether biasing the Monte-Carlo policy increases the exploitation of tactical moves, which is beneficial when the (unbiased) opponent does not have sufficient playouts to detect them. We remark that with a higher number of playouts, such moves are easy to detect, so it is more fruitful to explore the area for strategic moves.

It would also be interesting to study the "decisive moves" improvement proposed in [START_REF] Teytaud | On the huge benefit of decisive moves in monte-carlo tree search algorithms[END_REF]. There it was shown that the improvement would detect the biggest tactical threats, making biased policies more effective.

As a second future work, it would be interesting to compare the biased algorithms mentioned above with non MCTS-based algorithms, or expert human players to avoid the possible negative effects of self-playing.

Figure 1 :

 1 Figure 1: Winning Hex: white player wins (left); black player wins (right).

Figure 2 :

 2 Figure 2: The three winning shapes of Havannah (for the white player): ring (left), bridge (middle) and fork (right).

Figure 4 :

 4 Figure 4: The RAVE improvement consists in biasing the selection step of the MCTS algorithm by adding a RAVE score in the bandit formula. The RAVE score of a move is the win ratio of the move played in other simulations of the subtree. For example, selecting the move c 3 using RAVE (top left circle), is biased with the win ratio of c 3 in the other branches of the subtree (diamonds).

Figure 5 :

 5 Figure 5: The LGRF-1 improvement (simulation step biasing). For black replies: during a first playout, replies C to the move B, E to the move D and G to the move F are learned. During the next simulation, the replies C to B and E to D are played. These two replies are deleted because the simulation is a loss, then, only the reply G is kept. During the third simulation new replies are learned and added to the reply G. Learning is the same for white replies.

Figure 6 :

 6 Figure 6: Havannah: PoolRave vs Baseline using different number of playouts. Results with nb games = 2000, board size = 8, R = 90, C = 0.4 , pool proba = 0.1, pool sim = 10 and pool size = 10. With a small number of playouts, PoolRave is beneficial, but for 1, 500 playouts or more it becomes harmful.

  fork Baseline wins with bridge Baseline wins with ring PoolRave wins with fork PoolRave wins with bridge PoolRave wins with ring

Figure 7 :

 7 Figure 7: Havannah: PoolRave vs Baseline. Results with nb games = 2, 000, board size = 8, R = 90, C = 0.4, pool proba = 0.1, pool sim = 10 and pool size = 10. With only few playouts, both the baseline and PoolRave win with ring, which is far from a real game. When the number of playouts increases, wins are mainly forks.

Figure 8 :

 8 Figure 8: PoolRave/LGRF-1 vs Baseline on various Havannah-based games. Results with board size = 8, R = 90, C = 0.4, pool proba ∈ {0.1, 0.5, 0.9}, pool sim = 10 and pool size = 10. Top: nb playouts = 1, 000 and nb games = 2, 000. Bottom: nb playouts = 10, 000 and nb games = 600. The colors indicate the type of the games: tactical (red), strategic (green), tactical and strategic (yellow).

Table 1 :

 1 Hex: PoolRave/LGRF-1 vs Baseline. Results with board size = 11, R = 90 and C = 0.4. player playouts pool proba pool sim pool size win rate std dev nb games

			0.1	10	30	48.25%	±1.11
			0.1	5	30	46.85%	±1.11
		1,000	0.5 0.5	10 5	30 30	46.85% 43.9%	±1.11 ±1.10	2,000
	PoolRave		0.9	10	30	46.7%	±1.11
			0.9	5	30	48.85%	±1.11
			0.1	10	30	44.2%	±1.11
		10,000	0.5	10	30	41.95%	±1.10	600
			0.9	10	30	43.95%	±1.10
	LGRF-1	1,000 10,000	--	--	--	51.9% 53.33%	±1.11 ±2.03	2,000 600
	Table 2: Havannah: PoolRave/LGRF-1 vs Baseline. Results with board size = 8, R = 90 and C = 0.4.
	player	playouts pool proba pool sim pool size win rate std dev nb games
			0.1	10	30	69.15%	±1.03
			0.1	5	30	69.3%	±1.03
		1,000	0.5 0.5	10 5	30 30	68.95% 68.6%	±1.03 ±1.03	2,000
	PoolRave		0.9	10	30	59.75%	±1.09
			0.9	5	30	59.7%	±1.09
			0.1	10	10	40.66%	±2.00
		10,000	0.5	10	10	37.5%	±1.97	600
			0.9	10	10	36.66%	±1.96
	LGRF-1	1,000 10,000	--	--	--	57.95% 48.83%	±1.11 ±2.03	2,000 600

of the PoolRave/LGRF-1 player. Since playing the first move can be an advantage, we run half the games with PoolRave/LGRF-1 as the first player and the other games with PoolRave/LGRF-1 as the second player.