Tristan Cazenave
email: cazenave@lamsade.dauphine.fr

Jean Méhat

Abdallah Saffidine
email: abdallah.saffidine@dauphine.fr

UCD : Upper Confidence bound for rooted Directed acyclic graphs

Keywords: Monte-Carlo Tree Search, UCT, Transpositions, DAG

teaching and research institutions in France or abroad, or from public or private research centers.

Introduction

Monte-Carlo Tree Search (MCTS) is a very successful algorithm for multiple complete information games such as Go [START_REF] Coulom | Efficient selectivity and back-up operators in monte-carlo tree search[END_REF][START_REF] Coulom | Computing Elo ratings of move patterns in the game of Go[END_REF][START_REF] Gelly | Achieving master level play in 9 x 9 computer go[END_REF][START_REF] Lee | Special issue on monte carlo techniques and computer go[END_REF][START_REF] Rimmel | Current frontiers in computer go[END_REF], Hex [START_REF] Cazenave | Utilisation de la recherche arborescente Monte-Carlo au Hex[END_REF][START_REF] Arneson | Monte carlo tree search in hex[END_REF], or Lines of Action [START_REF] Winands | Monte carlo tree search in lines of action[END_REF]. Monte-Carlo programs usually deal with transpositions the simple way: they do not modify the Upper Confidence bound for Trees (UCT) formula and develop a Direct Acyclic Graph (DAG) instead of a tree.

Transpositions are widely used in combination with the Alpha-Beta algorithm [START_REF] Breuker | Memory versus search in games[END_REF] and they are a crucial optimisation for games such as Chess. Transpositions are also used in combination with the MCTS algorithm but little work has been done to improve their use or even to show they are useful. The only works we are aware of are the paper by Childs et al. [START_REF] Childs | Transpositions and move groups in Monte Carlo Tree Search[END_REF] and the paper by Méhat and Cazenave [START_REF] Méhat | Combining UCT and nested Monte-Carlo search for single-player general game playing[END_REF].

Our main contribution consists in providing a parametric formula adapted from the UCT formula 2 so that some transpositions are taken into account. Our framework encompasses the work presented in [START_REF] Childs | Transpositions and move groups in Monte Carlo Tree Search[END_REF]. We show that the simple way is often surpassed by other parameter settings on an artificial one player game as well as on the two player games hex and go as well as several games from General Game Playing competitions. We do not have a definitive explanation on how parameters influence the playing strength yet. We show that storing aggregations of the payoffs on the edge rather than on the nodes is preferable from a conceptual point of view and our experiment show that it also often lead to better results.

The rest of this article is organised as follows. We first recall the most common way of handling transpositions in the MCTS context. We study the possible adaptation of the backpropagation mechanism to DAG game trees. We present a parametric framework to define an adapted score and an adapted exploration factor of a move in the game tree. We then show that our framework is general enough to encompass the existing tools for transpositions in MCTS. Finally, experimental results on an artificial single player game and on several two players games are presented.

Motivation

We will use the following notations for a given object x. If x is a node, then c(x) is the set of the edges going out of x, similarly if x is an edge and y is its destination, then c(x) = c(y) is the set of the edges going out y. We indulge in saying that c(x) is the set of children of x even when x is an edge. If x is an edge and y is its origin, then b(x) = c(y) is the set of edges going out of y. b(x) is the set of the "siblings" of x plus x. During the backpropagation step, payoffs are cumulatively attached to nodes or edges. We denote by µ(x) the mean of payoffs attached to x (be it an edge or a node), and by n(x) the number of payoffs attached to x. If x is an edge and y is its origin, we denote by p(x) the total number of payoffs the children of y have received: p(x) = e∈c(y) n(e) = e∈b(x) n(e). Let x be a node or an edge, between the apparition of x in the tree and the first apparition of a child of x, some payoffs (usually one) are attached to x, we denote the mean (resp. the number) of such payoffs by µ (x) (resp. n (x)). We denote by π(x) the best move in x according to a context dependant policy.

Before having a look at transpositions in the MCTS framework, we first use the notation to express a few remarks on the plain UCT algorithm (when there is no transpositions). The following equalities are either part of the definition of the UCT algorithm or can easily be deduced. The payoffs available at a node or an edge x are exactly those available at the children of x and those that were obtained before the creation of the first child: n(x) = n (x) + e∈c(x) n(e). The mean of a move is equal to the weighted mean of the means of the children moves and the payoffs carried before creation of the first child:

µ(x) = µ (x) × n (x) + e∈c(x) µ(e) × n(e) n + e∈c(x) n(e) (1)
The plain UCT value [START_REF] Kocsis | Bandit based monte-carlo planning[END_REF] with an exploration constant c giving the score of a node x is written

u(x) = µ(x) + c × log p(x) n(x) (2)
The plain UCT policy consists in selecting the move with the highest UCT formula: π(x) = max e∈c(x) u(e). When enough simulations are run at x, the mean of x and the mean of the best child of x are converging towards the same value [START_REF] Kocsis | Bandit based monte-carlo planning[END_REF]:

lim n(x)→∞ µ(x) = lim n(x)→∞ µ(π(x)) (3)
Introducing transpositions in MCTS is challenging for several reasons. First, equation 1 may not hold anymore since the children moves might be simulated through other paths. Second, UCT is based on the principle that the best moves will be chosen more than the other moves and consequently the mean of a node will converge towards the mean of its best child; having equation 1 holding is not sufficient as demonstrated by Figure 1 where equation 3 is not satisfied. Suppose we have a single-player graph of size 5 as depicted in Figure 1 (a), with two leaves such that the leaf on the left is deterministic (or has a very low variance) and the associated reward is 0.5, and the leaf on the right is non-deterministic with mean reward 0.8. The best policy from the root for a risk neutral agent is to select the right edge twice and arrive at the 0.8 leaf. We will show that using the UCT policy together with the update-all backpropagation mechanism and show that it does not to lead to selecting the correct action sequence. Assume that the algorithm started by selecting twice the 0.5 leaf and twice the 0.8 leaf but that the mean of the results for the 0.8 leaf is 0.4. We obtain the situation depicted in Figure 1 (a). As we can see from the root, the left edge has a higher mean and a higher exploration value that the right edge. As a result the UCT policy will select the left edge ending invariably in the 0.5 leaf. The update-all backpropagation will update the µ and n values of both edges from the root, but the left edge will keep a higher mean and a higher exploration value. Figure 1 (b) shows the situation after 100 more descents of the algorithm. The UCT policy and the update-all procedure are such that every descent ended selecting the left 0.5 leaf. As a consequence, if the mean of the first draws on the 0.8 leaf are lower than 0.5, the UCT policy together with the update-all procedure will no select the right action to start with, no matter the number of descents performed.

The most common way to deal with transpositions in the MCTS frame-work, beside ignoring them completely, is what will be referred to in this article as the simple way. Each position encountered during the descent corresponds to a unique node. The nodes are stored in hash-table with the key being the hash value of the corresponding position. Mean payoff and number of simulations that traversed a node during the descent are stored in that node. The plain UCT policy is used to select nodes.

The simple way shares more information than ignoring transpositions. Indeed, the score of every playout generated after a given position a is aggregated in the node representing a. On the other hand, when transpositions are not detected, playouts generated after a position a are divided among all nodes representing a in the tree depending on the moves at the beginning of the playouts.

It is desirable to maximise the usage of a given amount of information because it allows to make better informed decisions. In the MCTS context, information is in the form of playouts. If a playout is to be maximally used, it may be necessary to have its payoff available outside of the path it took in the game tree. For instance in Figure 2 the information provided by the playouts were only propagated on the edges of the path they took. There is not enough information directly available at a even though a sufficient number of playouts has been run to assert that b is a better position than c.

Nevertheless, it is not trivial to share the maximum amount of information. A simple idea is to keep the DAG structure of the underlying graph and to directly propagate the outcome of a playout on every possible ancestor path. It is not always a good idea to do so in a UCT setting, as demonstrated by the counter-example in Figure 1. We will further study this idea under the name update-all in Section 3.2.

Possible Adaptations of UCT to Transpositions

The first requirement of using transpositions is to keep the DAG structure of the partial game tree. The partial game tree is composed of nodes and edges, since we are not concerned with memory issues in this first approach, it is safe to assume that it is easy to access the outgoing edges as well as the in edges of given nodes. When a transposition occurs, the subtree of the involved node is not duplicated. Since we keep the game structure, each possible position corresponds to at most one node in the DAG and each node in the DAG corresponds to exactly one possible position in the game. We will indulge ourselves to identify a node and the corresponding position. We There is enough information in the game tree to know that position b is better than position c, but there is not enough local information at node a to make the right decision.

will also continue to call the graph made by the nodes and the moves game tree even though it is now a DAG.

Storing results in the edges rather than in the nodes

In order to descend the game tree, one has to select moves from the root position until reaching an end of the game-tree. The selection uses the results of the previous playouts which need to be attached to moves. A move corresponds exactly to an edge of the game tree, however it is also possible to attach the results to nodes of the game tree. When the game tree is a tree, there is a one to one correspondence between edges and nodes, save for the root node. To each node but the root, correspond a unique parent edge and each edge has of course a unique destination. It is therefore equivalent to attach information to an edge (a, b) or to the destination b of that edge. MCTS implementations seem to prefer attaching information to nodes rather than to edges for implementation simplicity reasons. When the game tree is a DAG, we do not have this one to one correspondence so there may be a difference between attaching information to nodes or to edges.

In the following we will assume that aggregations of the payoffs are attached to the edges of the DAG rather than to the nodes. The payoffs of a node a can still be accessed by aggregating the payoffs of the edges arriving in a. No edge arrives at the root node but the results at the root node are usually not needed. On the other hand, the payoffs of an edge cannot be easily obtained from the payoffs of its starting node and its ending node, therefore storing the results in the edges is more general than storing the results only in the nodes. 1Figure 3 (a) shows a toy game tree where a couple of playouts where performed and the results stored in the nodes. Figure 3 (b) show the same game tree with exactly the same playouts performed, but this time the results were stored on the edges. Almost all the data in Figure 3 (a) can be retrieved in Figure 3 (b). For instance, the data in the middle nodes in Figure 3 (a) is exactly the data in the incoming edges of the middle nodes in Figure 3 (b). Similarly, the data in the bottom left node in Figure 3

Backpropagation

After the tree was descended and a simulation lead to a payoff, information has to be propagated upwards. When the game tree is a plain tree, the propagation is straightforward. The traversed nodes are exactly the ancestors of the leaf node from which the simulation was performed. The edges to be updated are thus easily accessed and for each edge, one simulation is added to the counter and the total score is updated. Similarly, in the hash-table solution, the traversed edges are stored on a stack and they are updated the same way.

In the general DAG problem however, many distinct algorithms are possible. The ancestor edges are a superset of the traversed edges and it is not clear which need to be updated and if and how the aggregation should be adapted. We will be interested in three possible ways to deal with the update step: updating every ancestor edge, updating the descent path, updating the ancestor edges but modifying the aggregation of the edge not belonging to the descent path.

Updating every ancestor edge without modifying the aggregation is simple enough, provided one takes care that each edge is not updated more than once after each playout. We call this method update-all. Update-all might suffer from deficiencies in schemata like the counter-example presented in Figure 1. The problem in update-all made obvious by this counter-example is that the distribution of playouts in the different available branches does not correspond to a distribution as given by UCT: assumption 3 is not satisfied.

The other straightforward method is to update only the traversed edges, we call it update-descent. This method is very similar to the standard UCT algorithm implemented on a regular tree and it is used in the simple way. When such a backpropagation is selected, the selection mechanism can be adjusted so that transpositions are taken into account when evaluating a move. The possibilities for the selection mechanism are presented in the following section.

The backpropagation procedure advocated in [START_REF] Childs | Transpositions and move groups in Monte Carlo Tree Search[END_REF] for their selection procedure UCT3 is also noteworthy. The same behaviour could be obtained directly with the update-descent backpropagation (Section 3.3), but it is fast and can be generalised to our framework (Section 3.4)

Selection

The descent of the game tree can be described as follows. Start from the root node. When in a node a, select a move m available in a using a selection procedure. If m corresponds to an edge in the game tree, move along that edge to another node of the tree and repeat. If m does not correspond to an edge in the tree, consider the position b resulting from playing m in a. It is possible that b was already encountered and there is a node representing b in the tree, in this case, we have just discovered a transposition, build an edge from a to b, move along that edge and repeat the procedure from b. Otherwise construct a new node corresponding to b and create an edge between a and b, the descent is finished.

The selection process consists in selecting a move that maximises a given formula. State of the art implementations usually rely on complex formulae that embed heuristics or domain specific knowledge, but the baseline remains the UCT formula defined in equation 2. 2When the game tree is a DAG and we use the update-descent backpropagation method, the equation 1 does not hold anymore, so it is not absurd to look for another way of estimating the value of a move than the UCT value. Simply put, equation 1 says that all the needed information is available locally, however deep transpositions can provide useful information that would not be accessible locally.

For instance in the partial game tree in Figure 2, it is desirable to use the information provided by the transpositions in node b and c in order to make the right choice at node a. The local information in a is not enough to decide confidently between b and c, but if we have a look at the outgoing edges of b and c then we will have more information. This example could be adapted so that we would need to look arbitrarily deep to get enough information. We define a parametric adapted score to try to take advantage of the transpositions to gain further insight in the intrinsic value of the move. The adapted score is parameterized by a depth d and is written for an edge e µ d (e). µ d (e) uses the number of playouts, the mean payoff and the adapted score of the descendants up to depth d. The adapted score is given by the following recursive formula.

µ 0 (e) = µ(e) (4)
µ d (e) = f ∈c(e) µ d-1 (f ) × n(f ) f ∈c(e) n(f ) (5)
The UCT algorithm uses an exploration factor to balance concentration on promising moves and exploration of less known paths. The exploration factor of an edge tries to quantify the information directly available at it. It does not allow to acknowledge that transpositions occurring after the edge offer additional information to evaluate the quality of a move. So just as we did above with the adapted score, we define a parametric adapted exploration factor to replace the exploration factor. Specifically, for an edge e, we define a parametric move exploration that accounts for the adaptation of the number of payoffs available at edge e and is written n d (e) and a parametric origin exploration that accounts for the adaptation of the total number of payoffs at the origin of e and is written p d (e). The parameter d also refers to a depth. n d (e) and p d (e) are defined by the following formulae.

n 0 (e) = n(e) (6)
n d (e) = f ∈c(e) n d-1 (f ) (7)
p d (e) = f ∈b(e) n d (f ) (8)
In the MCTS algorithm, the tree is built progressively as the simulations are run. So any aggregation of edges built after edge e will lack the information available in µ (e) and n (e). This can lead to a leak of information that becomes more serious as the depth d grows. If we attach µ (e) and n (e) along µ(e) and n(e) to an edge it is possible to avoid the leak of information and to slightly adapt the above formulae to also take advantage of this information. Another advantage of the following formulation is that is avoids to treat separately edges without any child.

µ 0 (e) = µ(e) (9)
µ d (e) = µ (e) × n (e) + f ∈c(e) µ d-1 (f ) × n(f ) n (e) + f ∈c(e) n(f ) (10)
n 0 (e) = n(e) (11)
n d (e) = n (e) + f ∈c(e) n d-1 (f ) (12)
p d (e) = f ∈b(e) n d (f ) (13)
If the height of the partial game tree is bounded by h, then there is no difference between a depth d = h and a depth d = h + x for x ∈ N. 3 When d is chosen sufficiently big, we write d = ∞ to avoid the need to specify any bound. Since the underlying graph of the game tree is acyclic, if h is a bound on the height of an edge e then h -1 is a bound on the height of any child of e, therefore we can write the following equality which recalls equation 1.

µ ∞ (e) = µ (e) × n (e) + f ∈c(e) µ ∞ (f ) × n(f ) n (e) + f ∈c(e) n(f ) (14)
The formulae proposed do not ensure that any playout will not account for more than once in the values of n d (e) and p d (e). However a playout can only be counted multiple times if there are transpositions in the subtree starting after e. It is not clear to the authors how a transposition in the subtree of e should affect the confidence in the adapted score of e. Thus, it is not clear whether such playouts need to be accounted several times or just once. Admitting several accounts gives rise to a simpler formula and was chosen for this reason.

We can now adapt formula 2 to use the adapted score and the adapted exploration to give a value to a move. We define the adapted value of an edge e with parameters (d 1 , d 2 , d 3 ) ∈ N 3 and exploration constant c to be (e) . The notation (d 1 , d 2 , d 3 ) makes it easy to express a few remarks about the framework.

u d 1 ,d 2 ,d 3 (e) = µ d 1 (e) + c × log p d 2 (e) n d 3
• When no transpositions occur in the game, such as when the board state includes the move list, every parametrisation gives rise to exactly the same selection behaviour which is also that of the plain UCT algorithm.

• The parametrisation (0, 0, 0) is not the same as completely ignoring transpositions since each position in the game appears only once in the game tree when we use parametrisation (0, 0, 0).

• The simple way (see Section 2) can be obtained through the (1, 0, 1) parametrisation.

• The selection rules in [START_REF] Childs | Transpositions and move groups in Monte Carlo Tree Search[END_REF] can be obtained through our formalism: UCT1 corresponds to parametrisation (0, 0, 0), UCT2 is (1, 0, 0) and UCT3 is (∞, 0, 0).

• It is possible to adapt the UCT value in almost the same way when the results are stored in the nodes rather than in the edges but it would not be possible to have a parametrisation similar to any of d 1 , d 2 or d 3 equal to zero.

Efficient selection through incremental backpropagation

The definitions of µ d 1 , p d 2 , and n d 3 can be naturally transformed into recursive algorithms to compute the adapted value of an edge. In MCTS implementations, the descent part usually constitute a speed bottleneck. It is therefore a concern that using the plain recursive algorithm to compute the adapted mean could induce a high performance cost. Moreover, most of the values will not change from one iteration to the next and so they can be memoized.

To accelerate the descent procedure, we store in each edge e the current values for µ d 1 (e), n d 2 (e), and n d 3 (e) as long as n (e). n d 2 allows to compute easily p d 2 and is easier to update. Then we suggest a generalisation of the backpropagation rule used for the UCT3 selection procedure [START_REF] Childs | Transpositions and move groups in Monte Carlo Tree Search[END_REF] that we call update d 1 ,d 2 ,d 3 .

Consider the leaf node l from which the playout was performed. We call a d (x) the set of the ancestors of x at distance at most d from x. For instance, a 0 (x) = {x}, a 1 (x) = {y|x ∈ c(y)} ∪ {x} is the set of the parents of x plus x. Notice that for each edge e not situated on the traversed path and not belonging to a d 1 (l), the adapted mean value is not altered by the playout. Similarly, if e / ∈ a d 2 (l) then n d 2 (e) is not altered. Updating the n d 2 (resp. n d 3 ) value of the relevant nodes is straightforward. We simply need to add one to the n d 2 (resp. n d 3 ) value of each edge on the traversed path and each edge in a d 2 (l) (resp. a d 3 (l)).

Updating the µ d 1 value is a bit more involved. We call ∆µ d 1 (e) the variation of µ d 1 (e) induced by the playout. If e is not in a d 1 (l) nor in the traversed path, then ∆µ d 1 (e) = 0. ∆µ d 1 (l) can be directly computed from the payoff of the playout and the values stored at l. For each other edge e, we use the formula:

∆µ(e) = f ∈c(e) ∆µ(f ) × n(f ) n (e) + f ∈c(e) n(f ) (15)

Experimental results

In the following experimental results, transpositions were detected by structural comparison of the positions. We used a hash-table where each key k was associated to a list l of pair (position, data). The list l contains the list of every position encountered having key k. To look for a position in the table, we first compute a hash-key for it and then look for the exact position in the corresponding association list. This technique allows for a relatively high speed of execution provided there are few hash collisions. It is also lossless in that it allows a perfect distinction between every position. On the other hand, this method makes it necessary to store one position for each node in the tree which is very memory consumming. Given that we never had more than 100,000 nodes in a memory in these experiments, lack of memory was not a bottleneck and this method was acceptable for our purpose.

Tests on leftright

leftright is an artificial one player game already used in [START_REF] Cazenave | Nested monte-carlo search[END_REF] under the name "left move", at each step the player is asked to chose to move Left or to move Right; after a given number of steps the score of the player is the number of steps walked towards Left. A position is uniquely determined by the number of steps made towards Left and the total number of moves played so far, transitions are therefore very frequent. If there are h steps, the full game tree has only h×(h-1) 2 nodes when transpositions are recognised. Otherwise, the full game tree has 2 h nodes.

We used 300 moves long games for our tests. Each test was run 200 times and the standard error is never over 0.3% on the following scores.

The UCT algorithm performs well at leftright so the number of simulations had to be low enough to get any differentiating result. We decided to run 100 playouts per move. The plain UCT algorithm without detection of transpositions with an exploration constant of 0.3 performs 81.5%, that is in average 243.5 moves out of 300 were Left. We also tested the update-all backpropagation algorithm which scored 77.7%. We tested different values for all three parameters but the scores almost did not evolve with d 2 so for the sake of clarity we present results with d 2 set to 0 in Figure 4.

The best score was 99.8% with the parametrisation (∞, 0, 1) which basically means that in average less than one move was played to the Right in each game. Setting d 3 to 1 generally constituted a huge improvement. Raising d 1 was consistently improving the score obtained, eventually culminating with d 1 = ∞.

Tests on Hex

hex is a two-player zero sum game that cannot end in a draw. Every game will end after at most a certain number of moves and can be labelled as a win for Black or as a win for White. Rules and details about hex can be found in [START_REF] Browne | Hex Strategy: Making the Right Connections[END_REF]. Various board sizes are possible, sizes from 1 to 8 have been computer solved [START_REF] Henderson | Solving 8x8 Hex[END_REF]. Transpositions happen frequently in hex because a position is completely defined by the sets of moves each player played, the particular order that occurred before has no influence on the position. MCTS is quite successful in Hex [START_REF] Cazenave | Utilisation de la recherche arborescente Monte-Carlo au Hex[END_REF], hence Hex can serve as a good experimentation ground to test our parametric algorithms.

hex offers a strong advantage to the first player and it is common practice to balance a game with a compulsory mediocre first move. 4 We used a size 5 board with an initial stone on b2. Each test was a 400 games match between the parametrisation to be tested and a standard Artificial Intelligence (A.I.) In each test, the standard A.I. played Black on 200 games and White on the remaining 200 games. The reported score designates the average number of games won by a parametrisation. The standard error was never over 2.5%.

The standard A.I. used the plain UCT algorithm with an exploration constant of 0.3, it did not detect transpositions and it could perform 1000 playouts at each move. We also ran a similar 400 games match between the standard A.I. and an implementation of the update-all backpropagation algorithm with an exploration constant of 0.3 and 1000 playouts per move. The update-all algorithm scored 51.5% which means that it won 206 games out of 400. The parametrisation to be tested also used a 0.3 exploration constant and 1000 playouts at each move. The results are presented in Figure 5 for d 2 set to 0 and in Figure 6 for d 2 set to 1.

The best score was 63.5% with the parametrisation (0, 1, 2). It seems that setting d 1 as low as possible might improve the results, indeed with d 1 = 0 the scores were consistently over 53% while having d 1 = 1 led to having scores between 48% and 62%. Setting d 1 = 0 is only possible when the payoffs are stored per edge instead of per node as discussed in Section 3.1.

One can contrast the fact that the optimal value for d 1 in a one player game was ∞ and that it is 0 in the two-player game hex. One possible explanation for this behaviour would be that the higher d 1 is, the more information is taken into account, however in a two-player game, alternating 0 0 0 42.5% 52.0% 46.5% 1 0 0 40.5% 53.0% 48.0% 2 0 0 34.5% 37.0% 33.5% 0 0 1 47.5% 48.5% 53.0% 1 0 1 45.0% 48.0% 44.5% 2 0 1 36.0% 31.0% 31.0% 0 1 0 44.0% 53.0% 44.0% 1 1 0 45.5% 56.0% 51.0% 2 1 0 37.5% 33.0% 33.5% 0 1 1 40.5% 52.0% 49.0% 1 1 1 51.5% 48.5% 49.5% 2 1 1 39.0% 37.5% 31.5% turns introduces a bias leading to poor performance.

Tests on go

In order to test Upper Confidence bound for Direct acyclic graph (UCD) in another game we choose to make it play go. Size 9 × 9 and 19 × 19 are standard for go, but given the size of the parameter space and the large number of playouts per move needed so that many transpositions occur on bigger boards, we decided to run the experiments on size 6 × 6. The number of playouts is fixed to 10000 in order to have enough transpositions to detect a difference in strength. Each test consists in playing 200 games against UCT without transposition table.

Table 1 gives the results for various configurations of UCD against UCT without transposition table. The game is 6 × 6 go with a komi of 5.5. UCT without transposition table uses the best found constant c = 0.4. A first interesting result in this table is that the usual configuration of UCT with transposition table (d 1 = 1, d 2 = 0, d 3 = 1) only wins 48% of its game against UCT without transposition table. Another interesting result is that UCD with d 1 = 1, d 2 = 1 and d 3 = 0 wins 56% of its games against UCT without transposition table. Another possibility for UCD is to adapt the idea to the Rapid Action Value Estimation (RAVE) heuristic [START_REF] Gelly | Combining online and offline knowledge in UCT[END_REF]. In this case instead of using the All Moves as First (AMAF) values of the node, the program mixes the AMAF values of all its children. This way it also uses the playouts of its children that come from another node to compute the AMAF value.

Table 2 gives the results for various configurations of RAVE UCD against standard RAVE. We can observe that RAVE UCD is often worse than standard RAVE.

Tests on General Game Playing

Game program usually embed a important body of knowledge that is specific of the game they play. This knowledge is used by the designer beforehand and limit somewhat the generality of the program. While a program like Deep Blue is able to play well chess, it can not play a match of checkers, or even tictactoe: while an expert in its domain, the playing program is limited to one game in its abilities, and these are not easily extended to other domains or even to other games.

The Logic Group at the university of Stanford addresses this limitation with GGP. In a GGP match, the players receive the rules of the game they have to play in a specific language called Game Description Language from a Game Master. The players have a set time, usually between 30 seconds and 20 minutes, to analyse the game. After that analyse phase, every player repeatedly selects a move in a fixed time, usually between 10 seconds and 1 minute, and sends it to the Game Master that combines them in a joint move transmitted back to all the players.

The Logic Group organise an annual competition at the summer conference of the Association for the Advancement of Artificial Intelligence (AAAI) [START_REF] Genesereth | General game playing: Overview of the AAAI competition[END_REF].

As they do not know beforehand the games that will be played, General Game Player have to analyse the rules of the game to select a method that work well for the game at hand, or use only methods that work well for all the conceivable games. Ary, our General Game Playing program uses UCT to play general games. It won the 2009 and the 2010 GGP competitions.

Due to the interpretation of the game descriptions in GDL, current general game players are only able to perform a very limited number of playouts in the given reflexion time.

The tests consist in having a parameterized version of Ary playing games against Ary without transposition detection. Parameters for the depth of the calculation for the mean, the parent playouts and the child playouts were tested with values 0, 1 and 2. Games have been played with 10 seconds per move. The UCT constant c was fixed to 40 as games results vary between 0 and 100. Both players ran on the same machine, from a pool of 35 computers, each with 2 GB of memory and dual core processors of frequencies between 2 and 2.5 GHz.

We tested using the games breakthrough, knightthrough, pawn whopping, capture the king, crisscross, connect 4, merrills, othello, pentago, and quarto.

breakthrough is played on a chess board; each player has two rows of pawns, moving forward or diagonally and try to have one pawn breaking through adversary line to attain the opposite row of the board. knigththrough has the same structure, but all the pieces move forward like knights in chess. pawn whopping is a variant where the players have only pawns, disposed at the beginning and moving as in ordinary chess. capture the king is a simplified variation of chess where the goal is to be the first to capture the opponent king. crisscross is a simplified version of chinese checkers where the players must move their four pieces on the other side of a two cells wide cross inscribed in 6 square board. connect 4, merrills, othello, pentago and quarto are the usual games. The description of all these games can be found on http://euklid.inf.tu-dresden.de: 8180/ggpserver.

The tables containing the results are given at the end of the paper. We tested the values 0, 1 and 2 for d 1 , d 2 , and d 3 . Each percentage in the table is the result of at least 200 games.

For breakthrough the best combination is (2, 1, 1) which has an average score of 54.1%. For capture the king the best combination is (1, 0, 0) which has an average score of 56.5%. For connect 4 the best combination is (2, 1, 2) which has an average score of 70.9%. According to the table, the transposition table helps a lot at connect 4 since many values in the table are above 60%. The usual way of dealing with transpositions (1, 0, 1) gives 63.9%. For crisscross the best combination is (0, 2, 0) which has an average score of 62.0% whereas the usual combination (1, 0, 1) has an average score of 55.1%. For knightthrough the best combination is (2, 1, 1) which has an average score of 56.9% which is very close to the score of 56.6% of the usual combination. For merrills the best combination is (1, 2, 2) with a score of 55.8% which is better than the 48.9% of the usual combination. For othello the best combination is (1, 1, 1) with a score of 59.2% which is better than the 46.5% of the usual combination. For pawn whopping the best combination is again (1, 1, 1) with a score of 59.8% which is better than the 50.5% of the usual combination. For pentago the best combination is (0, 2, 1) with a score of 56.8% which is close to the 53.8% of the usual combination. For quarto the best combination is (0, 0, 0) with a score of 55.8% which is better than the 50.7% of the usual combination.

In all these games the best combination is different from the usual combination. In some games the results are quite close to the results without transposition table. However in some games such as connect 4 for example, the transposition table helps a lot and the best combination gives much better results than the usual combination.

Conclusion and Future Work

We have presented a parametric algorithm to deal with transpositions in MCTS. Different parameters did improve on usual MCTS algorithms for games such as leftright, hex or connect 4. In this paper we did not deal with the graph history interaction problem [START_REF] Kishimoto | A general solution to the graph history interaction problem[END_REF]. In some games the problem occurs and we might adapt the MCTS algorithm to deal with it.

We have defined a parameterized value for moves that integrates the information provided by some relevant transpositions. The distributions of the values for the available moves at some nodes do not necessarily correspond to a UCT distribution. An interesting continuation of our work would be to define an alternative parametric adapted score so that the arising distributions would still correspond to UCT distributions.

Another possibility to take into account the information provided by the transpositions is to treat them as contextual side information. This information can be integrated in the value using the RAVE formula [START_REF] Gelly | Combining online and offline knowledge in UCT[END_REF], or to use the episode context framework described in [START_REF] Rosin | Multi-armed bandits with episode context[END_REF].

Figure 1 :

 1 Figure1: Counter-example for the update-all backpropagation procedure. If the initial estimation of the edges is imperfect, the UCT policy combined with the update-all backpropagation procedure is likely to lead to errors.

Figure 2 :

 2 Figure2: There is enough information in the game tree to know that position b is better than position c, but there is not enough local information at node a to make the right decision.

Figure 3 :

 3 Figure 3: Example of the update-descent backpropagation results stored on nodes and on edges for a toy tree.

Figure 4 :

 4 Figure 4: leftright results.

d 1 d

 1 2 d 3 c = 0.2 c = 0.4 c = 0.6

Table 1 :

 1 Results of various configurations of UCD against UCT without transposition table at 6 × 6 go

Table 2 :

 2 Results of various configurations of RAVE UCD against standard RAVE at 6 × 6 go

	RAVE constant depth RAVE depth mean result
	0.0001	1	0 48.0%
	0.0002	1	0 52.0%
	0.0004	1	0 47.5%
	0.0008	1	0 45.5%
	0.0016	1	0 49.0%
	0.0032	1	0 47.5%
	0.0064	1	0 39.0%
	0.0001	1	1 32.0%
	0.0002	1	1 38.0%
	0.0004	1	1 36.0%
	0.0008	1	1 33.0%
	0.0016	1	1 31.5%
	0.0032	1	1 37.5%
	0.0064	1	1 30.5%

Table 3 :

 3 Results for the game of Breakthrough

Table 4 :

 4 Results for the game of Capture the king .6 49.2 46.3 46.3 47.6 52.4 47.7 49.4 1 56.5 50.0 44.9 48.8 51.4 49.4 49.2 50.2 56.1 2 42.3 46.1 48.4 51.4 48.2 47.6 44.9 50.8 47.8

		d 2 = 0			d 2 = 1			d 2 = 2
	d 1	d 3			d 3			d 3
	0	1	2	0	1	2	0	1	2
	0 54.1 49

Table 5 :

 5 Results for the game of Connect4

		d 2 = 0			d 2 = 1			d 2 = 2
	d 1	d 3			d 3			d 3
	0	1	2	0	1	2	0	1	2
	0 52.2 46.1 58.3 66.7 48.9 42.8 58.9 52.8 52.8
	1 69.4 63.9 50.6 61.7 67.8 53.3 66.1 60.6 54.4
	2 57.2 56.7 67.8 61.1 58.3 70.9 57.2 62.2 70.7

Table 6 :

 6 Results for the game of Crisscross

		d 2 = 0			d 2 = 1			d 2 = 2
	d 1	d 3			d 3			d 3
	0	1	2	0	1	2	0	1	2
	0 58.0 52.2 43.1 61.1 51.4 45.8 62.0 50.8 43.5
	1 56.5 55.1 49.6 57.4 58.8 55.0 57.4 56.9 50.0
	2 59.7 54.6 58.8 57.9 56.9 59.2 57.9 58.9 56.9

Table 7 :

 7 Results for the game of Knightthrough .6 48.8 56.4 53.3 50.0 49.5 49.0 49.3 1 48.6 56.6 39.4 52.6 53.3 53.1 45.7 51.5 54.8 2 50.5 49.1 48.1 52.6 56.9 43.5 52.6 52.6 52.6

		d 2 = 0			d 2 = 1			d 2 = 2
	d 1	d 3			d 3			d 3
	0	1	2	0	1	2	0	1	2
	0 41.2 55

Table 8 :

 8 Results for the game of Merrills

		d 2 = 0			d 2 = 1			d 2 = 2
	d 1	d 3			d 3			d 3
	0	1	2	0	1	2	0	1	2
	0 49.0 52.6 50.8 50.6 47.8 50.0 47.9 54.2 50.4
	1 55.7 48.9 50.2 46.4 50.0 52.5 47.0 48.3 55.8
	2 47.8 52.0 52.5 50.8 52.2 54.8 47.7 47.5 51.7

Table 9 :

 9 Results for the game of Othello-comp2007

		d 2 = 0			d 2 = 1			d 2 = 2
	d 1	d 3			d 3			d 3
	0	1	2	0	1	2	0	1	2
	0 54.1 50.0 52.9 49.3 46.1 46.4 45.7 50.2 51.1
	1 42.1 46.5 42.6 46.9 59.2 50.6 53.4 47.6 51.4
	2 44.2 52.9 46.4 54.1 47.0 51.6 43.8 49.8 53.2

Table 10 :

 10 Results for the game of Pawn whopping .7 51.0 51.2 52.1 50.6 53.8 48.2 49.8 1 52.0 50.5 50.8 50.8 59.8 52.6 42.8 57.4 51.9 2 50.0 49.0 49.1 46.8 52.1 52.8 47.5 49.0 58.6

		d 2 = 0			d 2 = 1			d 2 = 2
	d 1	d 3			d 3			d 3
	0	1	2	0	1	2	0	1	2
	0 48.0 53

Table 11 :

 11 Results for the game of Pentago 2008

		d 2 = 0			d 2 = 1			d 2 = 2
	d 1	d 3			d 3			d 3
	0	1	2	0	1	2	0	1	2
	0 55.8 53.4 56.0 55.3 51.5 45.5 52.8 56.8 46.2
	1 46.6 53.8 47.2 51.0 50.0 49.8 51.7 53.8 48.3
	2 49.6 52.1 52.4 48.3 52.6 53.0 48.9 53.3 53.5

Table 12 :

 12 Results for the game of Quarto

		d 2 = 0			d 2 = 1			d 2 = 2
	d 1	d 3			d 3			d 3
	0	1	2	0	1	2	0	1	2
	0 55.8 47.4 49.5 53.7 47.5 49.8 51.2 51.9 47.9
	1 50.2 50.7 50.2 49.1 52.1 49.8 48.6 48.9 48.6
	2 50.9 51.4 50.4 51.1 49.6 46.2 51.2 47.6 50.2

As an implementation note, it is possible to store the aggregations of the edges in the start node provided one associates the relevant move.

Although these heuristics tend to make the exploration term unnecessary.

For instance, if the game cannot last more than h moves or if one node is created after each playout and there will not be more than h playouts, then the height of the game tree is bounded by h.

Even more common is the swap rule or pie-rule.

Acknowledgements

We would like to thank the anonymous reviewers for their comments that helped improve this article.


Tristan Cazenave

Nicolas Jouandeau

Abdallah Sadine

Solving breakthrough

Introduction

In this paper, we address the use of parallelization to solve games. We use the game breakthrough [START_REF] Handscomb | 8 × 8 game design competition: The winning game: Breakthrough... and two other favorites[END_REF] as the testbed for our experiments with parallel solving algorithms. breakthrough, which has already been used as a testbed in other work [START_REF] Skowronski | Automated discovery of search-extension features[END_REF][START_REF] Finnsson | Game-tree properties and mcts performance[END_REF], is an interesting game which oers new challenges to the AI community. We therefore also try to improve on domain specic techniques for the game of breakthrough. To this eect, we present race patterns, a new kind of static patterns that allow to detect win several moves before the actual game ends. The use of race patterns has some links with the use of threats to solve go-moku [START_REF] Victor | Searching for Solutions in Games an Articial Intelligence[END_REF]. However the threats used in go-moku by Allis were designed to select a small number of moves to search, whereas the race patterns are designed to stop search early.

Research on parallel game tree search was initially mainly about the parallelization of the Alpha-Beta algorithm. A survey on the parallelization of Alpha-Beta can be found in Mark Brockington PhD thesis [START_REF] Brockington | Asynchronous Parallel Game-Tree Search[END_REF]. Other sources about the use of transposition tables in parallel game tree search and Alpha-Beta are Feldmann's paper [START_REF] Feldmann | Game tree search on a massively parallel system[END_REF] and Kishimoto's paper [START_REF] Kishimoto | Distributed game-tree search using transposition table driven work scheduling[END_REF].

More recently the work on the parallelization of game tree search algorithms has addressed the parallelization of Monte-Carlo Tree Search algorithms [57] Other related works deal with the parallelization of PDS [START_REF] Nagai | A new and/or tree search algorithm using proof number and disproof number[END_REF][START_REF] Kishimoto | Parallel and/or tree search based on proof and disproof numbers[END_REF] and of Depth First Proof Number search (DF-PN) [START_REF] Kaneko | Parallel depth rst proof number search[END_REF]. A technique to reduce the memory usage of DF-PN is the garbage collection of solved trees [START_REF] Nagai | Df-pn algorithm for searching AND/OR trees and its applications[END_REF]. Previous attempts at parallelizing the Proof Number Search (PNS) algorithm used randomization [START_REF] Saito | Randomized parallel proof-number search[END_REF] or a specialized algorithm called at the leaves of the main search tree [START_REF] Wu | Job-level proof-number search for Connect6[END_REF].

Proof-Number search and parallel algorithms were also already successfully used in solving Checkers [START_REF] Schaeer | Solving checkers[END_REF][START_REF] Schaeer | Checkers is solved[END_REF].

In this paper we focus on the parallelization of the PN 2 algorithm. The PN 2 algorithm has enabled to solve complex games such as fanorona [START_REF] Maarten | Best Play in Fanorona leads to Draw[END_REF]. Our goal is to solve such games faster with a similar but parallel algorithm.

The second section is about PNS, Job-Level Proof Number Search (JLPNS) and our algorithm Parallel PN 2 (PPN 2 ). The third section deals with race patterns at breakthrough and the fourth section details experimental results. In this section we start presenting PNS. Then we recall the parallelization of PNS with Job-Level parallelization. The last section presents our Parallel PN 2 algorithm.

Proof Number Search

PNS was proposed by V. Allis [START_REF] Victor | Proof-Number Search[END_REF]. The goal of the algorithm is to solve sequential perfect information games. Starting from the root position, it develops a tree in a best rst manner. PNS uses the concept of eort numbers to compare leaves. Eort numbers are associated to nodes in the search tree and try to quantify the progress made towards some goal. Specically in PNS, two eort number are used: the proof number PN of a node n estimates the remaining eort to prove that n is winning for Max. Conversely, the disproof number DN, estimates the remaining eort to prove a win for Min. Originally, the PN (resp. the DN) of a node n was a lower bound on the number of node expansions needed below n to prove that n is a Max win (resp. loss). When the PN reaches 0 (resp. ∞), the DN reaches ∞ (resp. 0), and the node has been proved to be a Max win (resp. loss).

The PN and DN are recursively dened as shown in Table 1 where Win (resp. Lose) designate a terminal node corresponding to a position won by Max (resp. Min), Frontier designate a non-expanded non-terminal leaf node. Max (resp. Min ) designate an expanded internal node with Max (resp. Min) to play.

To select which node to expand next, Allis dened the set of most proving nodes [START_REF] Victor | Proof-Number Search[END_REF] and showed that it is possible to select one of them by the following descent procedure. Iterate until a Frontier node is reached: when at a Max node, select a child minimizing PN, when at a Min node, select a child minimizing DN.

Node type

PN DN Win 0 ∞ Lose ∞ 0 Frontier 1 1
Max In order to avoid having several clients trying to prove the same leaf, JLPNS uses a virtual-loss mechanism. 3 When a leaf is sent to a client, it is temporarily assumed to be proved a loss until the client returns a meaningful result.

min c∈chil(n) PN(c) c∈chil(n) DN(c) Min c∈chil(n) PN(c) min c∈chil(n) DN(c)
A disadvantage of the virtual-loss mechanism is that it is possible for a node to be considered losing for some time, but then to be updated to a non-solved state. Put another way, 0 and ∞ are no longer attractor values for the proof and disproof numbers.

An advantage of the approach taken by JLPNS, is that it allows an easy parallelization over a distributed system with a very small communication overhead.

Parallel PN 2

The principle of the PN 2 algorithm [START_REF] Victor | Searching for Solutions in Games an Articial Intelligence[END_REF][START_REF] Michel | Memory versus Search in Games[END_REF] is to develop another PN search at each leaf of the main PN search tree in order to have more informed proof and disproof numbers. For PPN 2 search, the PN search tree at the leaves is developed on a remote client.

A rst dierence with JLPNS is that the algorithm that is called at the leaves is also a Proof Number Search instead of a specialized solver as in JLPNS. As a result, partial results from the unnished remote search in one client can be sent back to the server to update the main PNS tree in order to inuence the next searches of the other clients.

Another dierence is that we do not use the virtual loss mechanism to avoid currently computed leaves but a ag on these leaves. First, in our technique, a node is never considered to be losing unless it has actually been proved to be losing, thus 0 and ∞ remain attractors. Then, note that the set of mostproving nodes usually contains several nodes, our technique ensures that we will pick tasks from the set of most-proving nodes of the current tree. Finally, the virtual-loss mechanism does not t well with the partial result update described described in the preceding paragraph.

On the other hand, our algorithm also has breakthrough specic knowledge: it uses the mobility heuristic and race patterns dened in Section 3.3.

Just as in PN 2 , the size of the remote tree can either be xed or a function of the size of the main search tree.

The main algorithm which is run on the server, is described in Algorithm 1. It consists in receiving results from the clients and updating the tree according to these results. A result can either be a partial result or a nal result. In both cases, we need to update the proof and disproof numbers of the concerned leaf with the result. We also update recursively its ancesters. When the result is nal, however, we expand the tree and need to nd a new not reserved leaf for the now idle client. Finding a not reserved leaf is done using a backtracking algorithm where the choice points are the nodes with several children minimizing the proof or disproof number. The remote algorithm which is run on the clients is described in Algorithm 2. It consists in developing a PNS tree until a given threshold and regularly sending partial results to the server. while the stop message is not received do receive a position, a player and a threshold N from the server while root is not proved and number of descents is less than N do if the number of descent is a multiple of a parameter p then send as partial results to the server the current PN and the DN of the root end if expand the tree using Proof Number Search end while send the denitive results to the server end while pawns situated on opposite borders as shown in Figure 1a. The pawns progress in opposite direction and the rst player to bring a pawn to the opposite last row wins the game. A pawn can always move diagonally forward possibly capturing an opponent pawn but can move forward one cell only if it is empty (Figure 1b). breakthrough was originally designed to be played on a 7 × 7 board but was adapted to participate in the 8 × 8 board game design competition which it won [START_REF] Handscomb | 8 × 8 game design competition: The winning game: Breakthrough... and two other favorites[END_REF].

Retrograde Analysis for Small Boards

The state space complexity of breakthrough on a board m × n with m ≥ 2 and n ≥ 4 can be upper bounded by the following formula 2 2m × 3 (n-2)m . This formula derives from the fact that each cell on the top row can only be empty or Black, each cell on the bottom row can only be empty or White, and all three possibilities are available for cells in the n -2 central rows. This upper bound is relatively accurate for board with small height, but it includes positions that cannot be reached from standard starting position as does not take into account the fact that each player has at most 2m pieces. As a result, it is rather loose for larger boards.

Jan Haugland used retrograde analysis to solve breakthrough on small boards. [START_REF] Brockington | Asynchronous Parallel Game-Tree Search[END_REF] The largest sizes solved by his program were 5 × 5 and 3 × 7, both turned to be a second player win.

To reduce the state space complexity and ease the retrograde analysis, Haugland avoided to store positions that could be won in one move. That is, positions with a pawn on the one before last row were not stored. It allows to reduce the state space complexity to 2 4m × 3 (n-4)m . The reduction factor is r = 3 2 2m which is r = 58 when m = 5.

Race patterns

After a couple of games played, human players start to get a sense of tactics in breakthrough. It allows the experimented player to spot a winning path sometimes as early as 15 plies before the actual game end. A game of breakthrough proceeds as follows, in the opening, the players strive to control the center or to obtain a strong outpost on the opponent's side without exchanging many pieces. Then, the players perform waiting moves until one of them enters a zugzwang position and need to weaken his or her structure. The opponent will now try to take advantage of the breach, usually the attack involves sacricing one or two pawns to force the opponent's defense to collapse. Thus, at this point both players could break through if the opponent passed, and the paths of both are usually disjoint, therefore it is necessary to count the number of moves needed by both players and the quickest to arrive wins (Figure 3a is an example of such a situation).

As we can see, detecting an early win involves looking separately at the possible winning paths of both players and deciding which is the shortest. Formalizing this technique can improve the playing level of an articial player or the performance of a solver.

Dening race patterns

We dene race patterns that allow to spot such winning paths. To be able to deal softly with the left and right sides of the board, we will consider a generalization of breakthrough with walls. 5 Walls are static cells which cannot be traversed nor occupied by any player.

In the following, we assume that we are looking for a winning path for player White. Formally, a pattern for player White is a two dimensional matrix in which each element is of one of the following type {occupied, free, passive, crossable, don't care }. The representation and the relationship between these types is presented in Figure 2. A cell of type passive should not contain a Black pawn to begin with, but it will not be necessary for any white pawn to cross it. On the other hand it should be allowed to bring a White pawn on a cell of type crossable, so it cannot be a wall but it could already hold a White or a Black pawn.

Occupied Free

Passive Crossable Dont't care To verify whether a pattern is matched on a given board, we rst extend the board borders with walls and then check for each possible pattern location that every cell are compatible as dened by Table 2. For instance, if the attacking player is White, then a White pawn will match any cell type in the pattern. Put another way, if the pattern cell corresponding to a Black pawn is not Crossable or Don't Care, then the pattern does not match.

Occupied Free Passive Crossable Don't Care

White Pawn Empty cell Black Pawn Wall

Table 2: Checking race patterns for White.

The order of a race pattern is dened as the maximal number of pass moves Black is allowed to do before White wins in the restricted position designated by the race patterns.

We compute for each player the lowest-order matching race pattern and if they only intersect on don't care cells, we know the outcome of the game. For instance in Figure 3a, we can see that White has two-move second player win pattern (Figure 3b) and that Black has a three-move rst player win pattern (Figure 3c). Given that player Black does not have a one-move nor a two-move race pattern, we conclude that the position is a White win. It is thus possible to statically solve this position four moves before the actual game end. In general, this technique allows to solve positions 2 × n moves before the actual game end only if we have access to every n-move race pattern. However, a position cannot be solved this way if its solution tree involves a zugzwang.

In our experiments, we used 26 handwritten patterns of order up to 2. The biggest patterns we used were 4 × 3 such as the one presented in Figure 3b. We do not have yet a tool for automatic correctness checking, therefore we had to limit the number of patterns used to keep condence in their correctness. [START_REF] Brockington | Asynchronous Parallel Game-Tree Search[END_REF] Experimental Results

Experiments are done on a simple network of Linux computers connected with Gigabyte switches. The network area includes 17 computers with 3.2 GHz Intel i5 quad core CPU with 4 GB of RAM. The master is run alone on one of these computers. The maximum number of clients is set to 16 × 4.

In the following experiments, we report the total time needed to solve the starting position of a breakthrough game of various sizes. We also report the number of nodes expanded and touched that were needed in Algorithm 1.

A node is expanded when all of its children have been added to the tree. In our server-side implementation, one node is expanded per iteration. The number of nodes expanded is proportional to the memory needed to store the PN tree on the server side. It also corresponds to the total number of tasks that have been sent to the clients. For a touched node, we only store the proof and disproof numbers as given by a client search. On the other hand, an expanded node also needs to store a pointer to every child. As a result touched nodes take much less memory than expanded nodes. We bounded to 1k or 100k the number of descents in one search in the clients, so memory resources in the clients were never a problem in these experiments.

Scalability

Table 3 gives the time needed in sec., the number of expanded and touched nodes saved on the server side to solve the 4 × 5 game with the PPN 2 algorithm with 1k descents in the clients. Solving 4 × 5 with 64 clients with 100k descents in each remote search takes 577 seconds, while with 10k descents in each remote search, it takes 216 seconds. Therefore, increasing the number of descents in the remote search does not necessarily improve the solving time. On the other hand, performing 100 descents in each remote search made it necessary to go over 1m descents in the main search which is very memory consuming. We can see from Table 3, that the number of expanded nodes on the server increases as the number of clients rises. Put another way, running many clients in parallel makes it harder to avoid unnecessary work. This is an expected behavior in a parallel algorithm. Nevertheless, the time needed to solve the position also decreases steadily as the number of clients rises. The speedup factor with 8 and 64 clients compared to 1 single client are respectively 4 and 18. We can conclude that although the algorithm is not perfectly parallelizable, the scaling factor is satisfactory. As we can see, sending partial results makes it possible to direct better the search but also increases the communication overhead. It is therefore needed to nd a balance between spending too much time in communications and not taking advantage of the information available. In this setting, sending partial results every 100 descents in the client seems the best compromise. Using partial informations, solving time is less dependent to the search size.

Partial Results Updates

Patterns

Table 5 gives the time in sec. and the number of expanded nodes needed to solve dierent games with the PPN 2 algorithm with partial results, xed search size and some patterns. The patterns we used allowed to statically solve a position up to 4 moves before the game end, 26 patterns were hand-written for this purpose. Checking whether a pattern can be matched on a given position is done in the most naive way and implementing more ecient pattern matching techniques is left as future work.

Using race patterns, the solving time is divided by 5.96 for the 4 × 5 board with 1k search, and by 9.85 for the 5 × 5 board. It takes 927 sec. to solve the 5 × 5 board with 1k search in the clients. Without patterns, 5 × 5 board with 1k search fails with 1 million nodes saved and goes beyond the server allowable memory with 2 million nodes.

Combining PPN 2 and race patterns allows us to solve the 6×5 board in 25,638 sec. (i.e. 7 hours 7 minutes 18 sec.) with 10k search and in 47,134 sec. (i.e. 13 hours 5 minutes 34 sec.) with 100k search.

As we can see, using race patterns makes it unnecessary to examine many positions in the main search. Race patterns also allow for a time reduction of one order of magnitude on boards of small sizes and probably more on larger boards.

Board size Search size Patterns Time Expanded In this paper, we have dened race patterns and used them to ease the solving of breakthrough positions. Indeed, in our experiments, using race patterns usually allows to examine about two orders of magnitude fewer positions. We have also shown how to successfully parallelize the PN 2 algorithm. The PPN 2 algorithm associated to race patterns has enabled to solve 6×5 breakthrough: the game is a second player win. We have found that on the smaller 4 × 5 board the speedup due to parallelization is important until at least 64 clients.

In future work, we will try to solve breakthrough for larger sizes. The race patterns used in this work had been devised by hand but it is impractical if we need many more patterns to statically solve positions earlier. We therefore need to devise an algorithm to generate and check for correctness race patterns automatically.

Zugzwang positions are still dicult to solve. Indeed, no winning race pattern will be found in a zugzwang position, so an extension of the concept of race patterns to be compatible with zugzwang positions or an orthogonal technique would be desirable.

We will also apply the Parallel PN 2 algorithm to other games. Moreover we will try to enhance the algorithm itself in order to have even greater speedups.

3 breakthrough and Race Patterns 3 . 1

 331 Rules of breakthrough breakthrough is race game invented in 2001 by Dan Troyka. The game is played on a rectangular board of size 8 × 8. Each player starts with two rows of Algorithm 2 Remote algorithm.

Fig. 1 :

 1 Fig. 1: Rules for the game breakthrough.

Fig. 2 :

 2 Fig. 2: Pattern representation. An arrow from a to b indicates that any cell satisfying a satises b.

  (a) Sample game with Black to play. White player can force a win. (b) Two-move second player win pattern. (c) Three-move rst player win pattern.

Fig. 3 :

 3 Fig. 3: Early win detection using race patterns. White can match pattern (b) and Black can match pattern (c).

Table 1

 1

	: Determination of eort numbers for PNS
	2.2 Job-Level Parallelization
	Job-Level Proof Number Search [21] has been used to solve connect6 positions.
	The principle is to have a main Proof Number Search tree, but instead of having
	simples leaves, a solver is called at each leaf in order to evaluate it.

Table 3 :

 3 Time needed, number of expanded and touched nodes for the PPN 2 with xed search size on 4 × 5 board with 1k descents at most in the remote search. Partial results were sent from a client every 100 descents.

	Clients Time Speed-up Expanded Touched
	1	3397s		107k	915k
	4	1559s	2.2	126k 1073k
	8	803s	4.2	130k 1106k
	16	472s	7.2	152k 1298k
	32	305s	11.1	196k 1651k
	64	186s	18.3	232k 1930k

Table 4

 4 gives the time needed in sec., the number of expanded and touched nodes saved in memory to solve the 4 × 5 game with the PPN 2 algorithm with partial results. The rst column gives the partial results frequency. Each solved position turned to be a second-player win.

	Partial Time Expanded Touched
	None 263s	324k 2645k
	500	233s	281k 2336k
	250	205s	253k 2105k
	100	186s	232k 1930k
	50	190s	233k 1944k
	25	201s	243k 2023k
	12	193s	223k 1855k

Table 4 :

 4 Time needed, number of expanded and touched nodes for PPN 2 algorithm with partial results and xed remote search size of 1k descents on 4 × 5 board, involving 64 clients.

Table 5 :

 5 Time needed and number of expanded nodes for the PPN 2 algorithm with partial results, xed remote search size and patterns with 64 clients.

		5 × 4	1k	No	2s	4132
		5 × 4	1k	Yes	1s	72
		4 × 5	1k	No	161s	241k
		4 × 5	1k	Yes	27s	4k
		5 × 5	1k	Yes	927s	78k
		5 × 5	100k	No	29,170s	208k
		5 × 5	100k	Yes	2959s	3k
		6 × 5	10k	Yes	25,638s	14k
		6 × 5	100k	Yes	47,134s	21k
	5	Discussion and Conclusion

The authors of JLPNS also try a virtual-win policy and a greedy mechanism which are conceptually similar to virtual-loss[START_REF] Wu | Job-level proof-number search for Connect6[END_REF].

Available on http://www.neutreeko.net/neutreeko.htm.

This generalization was used in the 2011 GGP competition.