Tristan Cazenave
email: cazenave@ai.univ-paris8.fr

Nicolas Jouandeau

On the Parallelization of UCT

We present three parallel algorithms for UCT. For 9×9 Go, they all improve the results of the programs that use them against GNU GO 3.6. The simplest one, the single-run algorithm, uses very few communications and shows improvements comparable to the more complex ones. Further improvements may be possible sharing more information in the multiple-runs algorithm.

Introduction

Works on parallelization in games are mostly about the parallelization of the Alpha-Beta algorithm. We address here different approaches to the parallelization of the UCT algorithm.

Monte-Carlo Go has recently improved to compete with the best Go programs [START_REF] Coulom | Efficient selectivity and back-up operators in monte-carlo tree search[END_REF][START_REF] Gelly | Modification of UCT with patterns in Monte-Carlo go[END_REF][START_REF] Gelly | Exploration exploitation in go: UCT for Monte-Carlo go[END_REF][START_REF] Wang | Modifications of UCT and sequence-like simulations for Monte-Carlo go[END_REF]. We show that it can be further improved using parallelization.

Section 2 describes related work. Section 3 presents three parallel algorithms. Section 4 details experimental results. Section 5 concludes.

Related Works

In this section we expose related works on Monte-Carlo Go. We first explain basic Monte-Carlo Go as implemented in GOBBLE in 1993. Then we address the combination of search and Monte-Carlo Go, followed by the UCT algorithm.

Monte-Carlo Go

The first Monte-Carlo Go program is GOBBLE [START_REF] Bruegmann | Monte Carlo Go[END_REF]. It uses simulated annealing on a list of moves. The list is sorted by the mean score of the games where the move has been played. Moves in the list are switched with their neighbor with a probability dependent on the temperature. The moves are tried in the games in the order of the list. At the end, the temperature is set to zero for a small number of games. After all games have been played, the value of a move is the average score of the games it has been played in first. GOBBLE-like programs have a good global sense but lack of tactical knowledge. For example, they often play useless Ataris, or try to save captured strings.

Search and Monte-Carlo Go

A very effective way to combine search with Monte-Carlo Go has been found by Rémi Coulom with his program CRAZY STONE [START_REF] Coulom | Efficient selectivity and back-up operators in monte-carlo tree search[END_REF]. It consists in adding a leaf to the tree for each simulation. The choice of the move to develop in the tree depends on the comparison of the results of the previous simulations that went through this node, and of the results of the simulations that went through its sibling nodes.

UCT

The UCT algorithm has been devised recently [START_REF] Kocsis | Bandit based monte-carlo planning[END_REF], and it has been applied with success to Monte-Carlo Go in the program MOGO [START_REF] Gelly | Modification of UCT with patterns in Monte-Carlo go[END_REF][START_REF] Gelly | Exploration exploitation in go: UCT for Monte-Carlo go[END_REF][START_REF] Wang | Modifications of UCT and sequence-like simulations for Monte-Carlo go[END_REF] among others.

When choosing a move to explore, there is a balance between exploitation (exploring the best move so far), and exploration (exploring other moves to see if they can prove better). The UCT algorithm addresses the exploration/exploitation problem. UCT consists in exploring the move that maximizes µ i + C × log(t)/s. The mean result of the games that start with the c i move is µ i , the number of games played in the current node is t, and the number of games that start with move c i is s.

The C constant can be used to adjust the level of exploration of the algorithm. High values favor exploration and low values favor exploitation.

Parallelization

In this section, we present the parallel virtual machine that we have used to implement the parallel algorithms. Then we present in three separate subsections the three parallel algorithms.

The Parallel Virtual Machine

To improve search, we choose message passing as parallel programming model, which is implemented in the standard MPI, also supported by LAM/MPI [START_REF] Burns | LAM: An Open Cluster Environment for MPI[END_REF]. Our virtual parallel computer, constituted with classical personal computer, sets up a fully connected network of computers. Both communications are done only with the global communicator MPI COMM WORLD. Each hyper-threaded computer that allows to work on two threads at once, supports two nodes of our parallel computer. Each node runs one task with independent data. Tasks are created at the beginning of the program's execution, via the use of the master-slave model. All gtp read and write commands are realized from and to the master. Slaves satisfy computing requests. The maximum time taken by any slave task is specified during each computing request. Therefore, the communication time is added. According to time limits, the maximum time spent over all computing loops is defined by the sum of all slowest answers. We use a synchronous communication mode for data transmission, with time-constrained computing sequences. In the UCT context, as the algorithm is anytime, it is naturally well-adapted for synchronous programming.

MASTER PART: singleRunParallelUCTMove(goban[ ], color, ko, time)

1 best ← -1; 2 (wins[ ], games[ ]) ← initialParallelUCTMove(goban[ ],

Single-Run Parallelization

The single-run parallelization consists in running multiple UCT algorithms in parallel without communication between the processes. Each process has a different seed for the random-number generator, so they do not develop the same UCT tree. When the time is over, or when the maximum number of random games is reached, each slave sends back to the master the number of games and the number of wins for all the moves at the root node of the UCT tree. The master process then simply adds the number of games and the number of wins of the moves for all the slave processes.

The master part and the slave part of the single-run parallelization are given in algorithm 1.

Multiple-Runs Parallelization

On the contrary of the single-run parallelization algorithm, the multiple-runs parallelization algorithm shares information between the processes. It consists in updating the number of games and the number of wins for all the moves at the root of the shared UCT tree every fixed amount of time. The master process starts with sending the goban, the color to move, the ko intersection and the initial thinking time to the slaves, then all the slaves start computing their UCT trees, and after the initial thinking time is elapsed, they all send the number of wins and the number of games for the root moves to the master process. Then the master process adds all the results for all the moves at the root, and sends back the information to the slaves. The slaves then initiate a new UCT computation with the same shared root moves information. The communication from the slaves to the master, the update of the master root moves information, the update of the slaves root moves information and the slaves computations are then run until the overall thinking time is elapsed. It is important to notice that at line 5 of the multipleQuerySlaveLoop function, the newWins and newGames arrays contain the difference between the number of wins (resp. games) after the UCT search and the number of wins (resp. games) before the UCT search.

Another important detail of the algorithm is that in the slaves, the number of wins and the number of games of the root moves are divided by the number of slaves. During the experiments of the multiple-runs algorithm, we tried not to divide, and the results were worse than the non-parallel algorithm. Dividing by the number of slaves makes UCT develop its tree in the slaves in a similar way as it would without sharing information, however the average scores of the root moves are more accurate than without sharing information. The improvement comes from the improved average scores.

The master part and the slave part of the multiple-runs parallelization are given in algorithm 2.

At-the-leaves Parallelization

At-the-leaves parallelization consists in replacing the random game at a leaf of the UCT tree with multiple random games run in parallel on the slave processes. This type of parallelization costs much more in communication time than the two previous approaches since communications between the master and the slaves occur for each new leaf of the UCT tree.

In the at-the-leaves parallelization algorithm, the master is the only one to develop the UCT tree. For each new leaf of the UCT tree, it sends to the slaves the sequence that leads from the root of the tree to the leaf. Then each slave plays a pre-defined number of random games that start with the sequence, and returns the average score of these random games. The master collects all the averages of the slaves and computes the average of the averages. The master part and the slave part of the at-the-leaves parallelization are given in algorithm 3.

Experimental Results

Tests are run on a simple network of computers running LINUX 2.6.18. The network includes 100 Mb switches. The BogoMips rating of each node is approximately 6000.

In our experiments, UCT uses µ i + log (t) 10×s to explore moves. The random games are played using the same patterns as in MOGO [START_REF] Wang | Modifications of UCT and sequence-like simulations for Monte-Carlo go[END_REF] near the last move. If no pattern is matched near the last move, the selection of moves is the same as in CRAZY STONE [START_REF] Coulom | Efficient selectivity and back-up operators in monte-carlo tree search[END_REF].

Table 1 gives the results (% of wins) of 200 9×9 games (100 with black and 100 with white) for the single-run parallel program against GNU GO 3.6 default level. The parallel algorithm has been tested with either 3,000 simulations (random games) for each UCT search, or 10,000 simulations. The single-run parallelization improves the result bringing them from 27.5% for 1 CPU and 3,000 games to 53.0% for 16 CPUs and 3,000 games per CPU. Concerning the experiments with 10,000 games per CPU, the results increase from 45.0% for 1 CPU to 66.5% for 16 CPUs. For the single-run parallelization, the communication time is very small compared to the computation time. The single-run parallelization successfully improves the UCT algorithm. 2 gives the results of 200 9×9 games for the multiple-runs parallel program against GNU GO 3.6 default level. In these experiments, the multiple-runs algorithms updates the shared information every 250 simulations. The results are similar to the results of the single-run parallelization. They are slightly better with 10,000 simulations. 3 gives the results of 200 9×9 games for the at-the-leaves parallel program against GNU GO 3.6 default level. We can see an improvement when the number of CPUs increases from 1 to 8. However increasing the number to more than 8 does not improve much as can be seen from the second line of the table, where the slaves all play 8 games per leaf. Playing 8 games per leaf is equivalent to having 8 times more CPUs with one game per leaf.

Concerning the 10,000 simulations experiments, the percentage of wins also increases until 8 CPUs. Table 4 shows the communication overhead for the at-the-leaves parallel program. For one CPU, the slave process runs on the same machine as the master process, so the communication time is small and the time used to find the first move on an empty 9×9 goban can be used as a reference for a non-parallel program. We see in the next columns that the communication time progressively increases, doubling the thinking time for 8 CPUs. The communication time for the at-the-leaves parallel program is significantly higher than the two previous algorithms. Given that it gives similar improvements in level, it is preferable to use the single-run or multiple-runs algorithms. The at-the-leaves parallelization could be of interest to multiple CPUs machines with a shared memory where the communication costs are less of a problem.

Conclusion

We have presented three parallel algorithms that improve UCT search. They all give similar improvements. The single-run parallelization is the most simple one and also the one that uses the fewest communications between the processes.

The at-the-leaves parallelization currently costs too much communications, however it could still be interesting on a multiple CPUs machine.

We believe that the multiple-runs algorithm can be further improved to share more information and then may become the best algorithm.

  color, ko, time); 3 for j ← 0 to goban.size()

	4	best ← max(best, wins[j]/games[j]);
	5 return best;
	initialParallelUCTMove(goban[ ], color, ko, time)
	1 for i ← 0 to goban.size()
	2	wins[i] ← 0;
	3	games[i] ← 0;
	4 broadcast(goban[ ], color, ko, time);
	5 for i ← 0 to nbSlaves
	6	receiveUCTSequences(newW ins[ ], newGames[ ]);
	7	for j ← 0 to goban.size()
	8	wins[

j] ← wins[j] + newW ins[j]; 9 games[j] ← games[j] + newGames[j]; 10 return (wins[ ], games[ ]); SLAVE PART: singleRunParallelUCTMoveSlaveLoop() 1 while(true) 2 if(SingleQueryUCTSlaveLoop() == EN D GAM E) break; 3 return; SingleQueryUCTSlaveLoop() 1 if(receive(goban[ ], color, ko, time) == EN D GAM E) return EN D GAM E; 2 for i ← 0 to goban.size() 3 wins[i] ← 0; 4 games[i] ← 0; 5 (wins[ ], games[ ]) ← playUCTSequences(goban[ ], color, ko, time); 6 send(wins[ ], games[ ]); 7 return CON T IN U E; ALG. 1: Single-Run Parallel Algorithm.

Table 1 .

 1 Results of the single-run program against GNU GO 3.6.

	1 CPU 2 CPUs 4 CPUs 8 CPUs 16 CPUs
	3,000 simulations 27.5% 40.0% 48.0% 55.5% 53.0%
	10,000 simulations 45.0% 62.0% 61.5% 65.0% 66.5%

Table

Table 2 .

 2 Results of the multiple-runs program against GNU GO 3.6.

	1 CPU 2 CPUs 4 CPUs 8 CPUs 16 CPUs
	3,000 simulations 20.0% 32.0% 48.0% 53.5% 56.0%
	10,000 simulations 49.0% 58.5% 72.0% 72.0% 68.0%

Table

Table 3 .

 3 Results of the at-the-leaves parallel program against GNU GO 3.6.

		nbGamesAtLeaf 1 CPU 2 CPUs 4 CPUs 8 CPUs 16 CPUs
	3,000 simulations	1	21.0% 35.0% 42.0% 46.0% 45.0%
	3,000 simulations	8	54.5% 48.5% 49.5% 47.5% 51.0%
	10,000 simulations	1	47.0% 53.5% 53.5% 69.5% 62.0%

Table 4 .

 4 Times for the first move for the at-the-leaves parallel program. nbGamesAtLeaf 1 CPU 2 CPUs 4 CPUs 8 CPUs 10,000 simulations 1 6.21s. 10.85s. 11.56s. 13.07s.


Tristan Cazenave
email: cazenave@ai.univ-paris8.fr

Nicolas Jouandeau

A Parallel Monte-Carlo Tree Search Algorithm

Monte-Carlo tree search is a powerful paradigm for the game of Go. We present a parallel Master-Slave algorithm for Monte-Carlo tree search. We experimented the algorithm on a network of computers using various configurations: from 12,500 to 100,000 playouts, from 1 to 64 slaves, and from 1 to 16 computers. On our architecture we obtain a speedup of 14 for 16 slaves. With a single slave and five seconds per move our algorithm scores 40.5% against GNUGO, with sixteen slaves and five seconds per move it scores 70.5%. We also give the potential speedups of our algorithm for various playout times.

Introduction

. We address the parallelization of the UCT algorithm (Upper Confidence bounds applied to Trees). This work is an improvement over our previous work on the parallelization of UCT [3]. In our previous work we tested three different algorithms. The single-run algorithm uses very few communications, it consists in having each slave computing its own UCT tree independently of the others. When the thinking time is elapsed, it combines the results of the different slaves to choose its move. The multipleruns algorithm periodically updates the trees with the results of the other slaves. The at-the-leaves algorithm computes multiple playouts in parallel at each leaf of the UCT tree. In this paper we propose a different parallel algorithm that develops the UCT tree in the master part and performs the playouts in the slaves in parallel, it is close to the algorithm we presented orally at the Computer Games Workshop 2007 and that we used at the 2007 Computer Olympiad.

. We show that it can be further improved using parallelization.

Section 2 describes related work. Section 3 presents the parallel algorithm. Section 4 details experimental results. Section 5 concludes.

Related Works

In this section we expose related works on Monte-Carlo Go. We first explain basic Monte-Carlo Go as implemented in GOBBLE in 1993. Then we address the combination of search and Monte-Carlo Go, followed by the UCT algorithm.

Monte-Carlo Go

The first Monte-Carlo Go program is GOBBLE [START_REF] Bruegmann | Monte Carlo Go[END_REF]. It uses simulated annealing on a list of moves. The list is sorted by the mean score of the games where the move has been played. Moves in the list are switched with their neighbor with a probability dependent on the temperature. The moves are tried in the games in the order of the list. At the end, the temperature is set to zero for a small number of games. After all games have been played, the value of a move is the average score of the games it has been played in first. GOBBLE-like programs have a good global sense but lack of tactical knowledge. For example, they often play useless Ataris, or try to save captured strings.

Search and Monte-Carlo Go

A very effective way to combine search with Monte-Carlo Go has been found by Rémi Coulom with his program CRAZY STONE [START_REF] Coulom | Efficient selectivity and back-up operators in Monte-Carlo tree search[END_REF]. It consists in adding a leaf to the tree for each simulation. The choice of the move to develop in the tree depends on the comparison of the results of the previous simulations that went through this node, and of the results of the simulations that went through its sibling nodes.

UCT

The UCT algorithm has been devised recently [START_REF] Kocsis | Bandit based Monte-Carlo planning[END_REF], and it has been applied with success to Monte-Carlo Go in the program MOGO [START_REF] Gelly | Modification of UCT with patterns in Monte-Carlo Go[END_REF][START_REF] Gelly | Combining online and offline knowledge in UCT[END_REF] among others.

When choosing a move to explore, there is a balance between exploitation (exploring the best move so far), and exploration (exploring other moves to see if they can prove better). The UCT algorithm addresses the exploration/exploitation problem. UCT consists in exploring the move that maximizes µ i + C × log(games) childi→games . The mean result of the games that start with the c i move is µ i , the number of games played in the current node is games, and the number of games that start with move c i is child i → games.

The C constant can be used to adjust the level of exploration of the algorithm. High values favor exploration and low values favor exploitation.

Parallelization

In this section, we present the run-time environment used to execute processes on a cluster. Then we present and comment the master part of the parallel algorithm. Eventually, we present the slave part of the parallel algorithm.

The Parallel Run-Time Environment

To improve search, we choose message passing as parallel programming model, which is implemented in the standard MPI, also supported by Open MPI [START_REF] Gabriel | Open MPI: Goals, concept, and design of a next generation MPI implementation[END_REF]. Open MPI is designed to achieve high performance computing on heterogeneous clusters. Our cluster is constituted with classical personal computers and with a SMP head node that has four processors. The resulting cluster is a private network connected with TCP Gigabit network. Both communications are done only with the global communicator MPI COMM WORLD. Each hyper-threaded computer that allows to work on two threads at once, supports of one to four nodes of our parallel computer. Each node runs one task with independent data. Tasks are created at the beginning of the program's execution, via the use of the master-slave model. The SMP head node is always the master. All Go Text Protocol read and write commands are realized from and to the master. Slaves satisfy computing requests.

The Master Process

The master process is responsible for descending and updating the UCT tree. The slaves do the playouts that start with a sequence of moves sent by the master. The master starts sending the position to each slave. Then it develops the UCT tree once for each slave and sends them an initial sequence of moves. Then it starts its main loop (called MasterLoop) which repeatedly receive from a slave the result of the playout starting with the sent sequence, update the UCT tree with this result, create a new sequence descending the updated UCT tree, and sends this new sequence to the slave.

The master finishes the main loop when no more time is available or when the maximum number of playouts is reached. Before stopping, it receives the results from all the children that are still playing playouts until no more slave is active.

The master part of the parallel algorithm is given in algorithm 1.

The Slave Process

The slave process loops until the master stops it with an END GAME message, otherwise it receives the board, the color to play and the ko intersection and starts another loop in order to do playouts with this board configuration.

In this inner loop, it starts receiving a sequence of moves, then it plays this sequence of moves on the board, then completes a playout and sends the result of the playout to the master process.

The slave part of the parallel algorithm is given in algorithm 2.

Experimental Results

Tests are run on a simple network of computers running LINUX 2.6.18. The network includes 1 Gigabit switches, 16 computers with 1.86 GHz Intel dual core CPUs with 2 GB of RAM. The master process is run on the server which is a 3.20 GHz Intel Xeon with 4 GB of RAM.

In our experiments, UCT uses µ i + 0.3 × log(games)

childi→games to explore moves.

The random games are played using the same patterns as in MOGO [START_REF] Gelly | Modification of UCT with patterns in Monte-Carlo Go[END_REF] near the last move. If no pattern is matched near the last move, the selection of moves is the same as in CRAZY STONE [START_REF] Coulom | Efficient selectivity and back-up operators in Monte-Carlo tree search[END_REF].

Table 1 gives the results (% of wins) of 200 9×9 games (100 with black and 100 with white, with komi 7.5) against GNUGO 3.6 default level. The time limit is set to five seconds per move. The first program uses one slave, it scores 40.5 % against GNUGO. The second program uses sixteen it scores 70.5 % against GNUGO. Table 2 can be used to evaluate the benefits from parallelizing the UCT algorithm. For example, in order to see if parallelizing on 8 slaves is more interesting than parallelizing with 4 slaves, we can compare the results of 100,000 playouts with 8 slaves (70.0%) to the results of 50,000 playouts with 4 slaves (65.0%). In this case, parallelization is beneficial since it gains 5.0% of wins against GNUGO 3.6. We compare 8 slaves with 100,000 playouts with 4 slaves with 50,000 playouts since they have close execution times (see table 3).

To determine the gain we have parallelizing with 8 slaves over not parallelizing at all, we can compare the results of 12,500 playouts with 1 slave (47.5%) to the results of 100,000 playouts with 8 slaves (70.0%). In this case it is very beneficial.

Another interesting conclusion we can draw from the table is that the interest of parallelizing starts to decrease at 32 slaves. For example 100,000 playouts with 32 slaves wins 65.0% when 50,000 playouts with 16 slaves wins 65.5%. So going from 16 slaves to 32 slaves does not help much.

Therefore, our algorithm is very beneficial until 16 slaves, but it is much less beneficial to go from 16 slaves to 32 or 64 slaves. Table 3 gives the mean over 11 runs of the time taken to play the first move of a 9x9 game, for different numbers of total slaves, different numbers of slaves per computer, and different numbers of playouts. The values were computed on an homogeneous network of dual cores. The associated variances are very low.

We define the speedup for n slaves as the division of the time for playing the first move with one slave by the time for playing the first move with n slaves.

Table 4 gives the speedup for the different configurations and 100,000 playouts, calculated using table 3. Table 5 gives the corresponding speedups for 50,000 playouts. The speedups are almost linear until 8 slaves with one slave per computer. They start to decrease for 16 slaves (the speedup is then roughly 14), and stabilize near to 18 for more than 16 slaves. Another conclusion we can draw from these tables is that it does not make a large difference running one slave per computer, two slaves per computer or four slaves per computer (even if processors are only dual cores).

In order to test if the decrease in speedup comes from the client or from the server, we made multiple tests. The first one consists in not playing playouts in the slaves, and sending a random value instead of the result of the playout. It reduces the time processing of each slave to almost zero, and only measures the communication time between the master and the slaves, as well as the master processing time.

The results are given in table 6. We see that the time for random results converges to 3.9 seconds when running on 32 slaves, which is close to the time taken for the slaves playing real playouts with 32 or more slaves. Therefore the 3.9 seconds limit is due to the communications and to the master processing time and not to the time taken by the playouts. In order to test the master processing time, we removed the communication. We removed the send command in the master, and replaced the reception command with a random value. In this experiment the master is similar to the previous experiment, except that it does not perform any communication. Results are given in table 7. For 100,000 playouts the master processing time is 2.60 seconds, it accounts for 78% of the 3.3 seconds limit we have observed in the previous experiment.

Further speedups can be obtained by optimizing the master part, and from running the algorithm on a shared memory architecture to reduce significantly the communication time. Table 8 gives the time of the parallel algorithm for various numbers of slaves, with random slaves and various fixed playout times. In this experiment, a slave sends back a random evaluation when the fixed playout time is elapsed. The first column of the table gives the fixed playout time in milliseconds. The next columns gives the mean time for the first move of a 9x9 game, the numbers under parenthesis give the associated variance, each number corresponds to ten measures.

We see in table 8 that for slow playout times (greater than two milliseconds) the speedup is linear even with 32 slaves. For faster playout times the speedup degrades as the playouts get faster. For one millisecond and half a millisecond, it is linear until 16 slaves. The speedup is linear until 8 slaves for playout time as low as 0.125 milliseconds. For faster playout times it is linear until 4 slaves.

Slow playouts policies can be interesting in other domains than Go, for example in General Game Playing. Concerning Go, we made experiments with a fast playout policy, and we succeeded parallelizing it playing multiple playouts at each leaf. For 19x19 Go, playouts are slower than for 9x9 Go, therefore our algorithm should better apply to 19x19 Go. The last experiment tests the benefits of going from 8 slaves to 16 slaves assuming linear speedups. Results are given in table 9. There is a decrease in winning percentages as we increase the number of playouts. 8-slaves with 50,000 playouts against 16-slaves with 100,000 playouts 33.50% 8-slaves with 25,000 playouts against 16-slaves with 50,000 playouts 27.00% 8-slaves with 12,500 playouts against 16-slaves with 25,000 playouts 21.50%

Conclusion

We have presented a parallel Monte-Carlo tree search algorithm. Experimental results against GNUGO 3.6 show that the improvement in level is efficient until 16 slaves. Using 16 slaves, our algorithm is 14 times faster than the sequential algorithm. On a cluster of computers the speedup varies from 4 to at least 32 depending on the playout speed. Using 5 seconds per move the parallel program improves from 40.5% with one slave to 70.5% with 16 slaves against GNUGO 3.6.

Table 1 .

 1 Results against GNUGO for 5 seconds per move.

	1 slave 40.50%
	16 slaves 70.50%

Table 2

 2 gives the results (% of wins) of 200 9×9 games (100 with black and 100 with white, with komi 7.5) for different numbers of slaves and different numbers of playouts of the parallel program against GNUGO 3.6 default level.

Table 2 .

 2 Results of the program against GNUGO 3.6.

	1 slave 2 slaves 4 slaves 8 slaves 16 slaves 32 slaves 64 slaves
	100,000 playouts 70.0% 69.0% 73.5% 70.0% 71.5% 65.0% 58.0%
	50,000 playouts 63.5% 64.0% 65.0% 67.5% 65.5% 56.5% 51.5%
	25,000 playouts 47.0% 49.5% 54.0% 56.0% 53.5% 48.5% 42.0%
	12,500 playouts 47.5% 44.5% 44.0% 45.5% 45.0% 36.0% 32.0%

Table 3 .

 3 Time in sec. of the first move.

	1 slave 2 slaves 4 slaves 8 slaves 16 slaves 32 slaves 64 slaves
	1 slave per computer
	100,000 playouts 65.02 32.96 16.78	8.23	4.49	-	-
	50,000 playouts 32.45 17.05	8.56	4.08	2.19	-	-
	2 slaves per computer
	100,000 playouts -	35.29 17.83	9.17	4.61	3.77	-
	50,000 playouts -	16.45	9.23	4.61	2.25	1.74	-
	4 slaves per computer
	100,000 playouts -	-	20.48 13.13	5.47	3.77	3.61
	50,000 playouts -	-	10.33	6.13	2.82	1.83	1.75

Table 4 .

 4 Time-ratio of the first move for 100,000 playouts.

	1 slave 2 slaves 4 slaves 8 slaves 16 slaves 32 slaves 64 slaves
	1 slave per computer 1.00	1.97	3.87	7.90	14.48	-	-
	2 slaves per computer -	1.84	3.65	7.09	14.10	17.25	-
	4 slaves per computer -	-	3.17	4.95	11.89	17.25	18.01

Table 5 .

 5 Time-ratio of the first move for 50,000 playouts.

	1 slave 2 slaves 4 slaves 8 slaves 16 slaves 32 slaves 64 slaves
	1 slave per computer 1.00	1.90	3.79	7.95	14.82	-	-
	2 slaves per computer -	1.97	3.52	7.04	14.42	18.65	-
	4 slaves per computer -	-	3.14	5.29	11.51	17.73	18.54

Table 6 .

 6 Time in sec. of the first move with random slaves.

	1 slave 2 slaves 4 slaves 8 slaves 16 slaves 32 slaves
	1 slave per computer
	100,000 playouts 25.00 12.50	6.25	4.44	4.10	-
	2 slaves per computer
	100,000 playouts -	12.49	6.94	4.47	4.48	3.93
	4 slaves per computer
	100,000 playouts -	-	6.26	4.72	4.07	3.93

Table 7 .

 7 Time in sec. of the random master.

	100,000 playouts 2.60
	50,000 playouts 1.30

Table 8 .

 8 Time in msec. of the algorithm with random slaves and various playout times.

	time	1 slave	4 slaves	8 slaves	16 slaves	32 slaves
	10	1026.8 (6.606) 256.2 (0.103) 128.1 (0.016)	64.0 (0.030)	32.0 (0.020)
	2	224.9 (0.027)	56.3 (0.162)	28.1 (0.011)	14.0 (0.005)	7.0 (0.002)
	1	125.0 (0.081)	31.2 (0.006)	15.6 (0.001)	7.8 (0.006)	4.3 (0.035)
	0.5	75.0 (0.026)	18.8 (0.087)	9.4 (0.001)	4.8 (0.034)	4.0 (0.055)
	0.25	50.0 (0.005)	12.5 (0.024)	6.2 (0.001)	4.1 (0.019)	3.9 (0.049)
	0.125	37.5 (0.021)	9.4 (0.001)	4.7 (0.007)	4.1 (0.222)	3.9 (0.055)
	0.0625	25.0 (0.012)	6.6 (0.013)	4.4 (0.013)	4.0 (0.023)	3.8 (0.016)
	0.03125 25.0 (0.007)	6.3 (0.004)	4.5 (0.110)	4.2 (0.0025)	4.0 (0.054)
	0.01	25.0 (0.007)	6.3 (0.004)	4.5 (0.110)	4.5 (0.025)	4.0 (0.054)

Table 9 .

 9 Results of the 8-slaves program against 16-slaves program.


Tristan Cazenave

Nicolas Jouandeau

Parallel Nested Monte-Carlo Search

Keywords: Monte-Carlo, Search, Parallelization, Morpion Solitaire

We address the parallelization of a Monte-Carlo search algorithm. On a cluster of 64 cores we obtain a speedup of 56 for the parallelization of Morpion Solitaire. An algorithm that behaves better than a naive one on heterogeneous clusters is also detailed.

I. Introduction

M ONTE-CARLO methods can be used to search prob- lems that have a large state space and no good heuristics. Nested Monte-Carlo search [START_REF] Cazenave | Nested Monte-Carlo search[END_REF] improves Monte-Carlo search using a lower level Monte-Carlo Search to choose move at the upper level. For problems that do not have good heuristics to guide the search, the use of nested levels of Monte-Carlo search amplifies the results of the search and makes it better than a simple Monte-Carlo search. A similar algorithm has already been applied with success to Morpion Solitaire [START_REF] Cazenave | Reflexive monte-carlo search[END_REF]. We address the parallelization of the Nested Monte-Carlo Search algorithm on a cluster.

Section 2 describes related work, section 3 explains the sequential Nested Monte-Carlo Search algorithm, section 4 presents two parallel algorithms: the Round-Robin algorithm and the Last-Minute algorithm, section 5 details experimental results.

II. Related works

Parallel algorithms have been developed for many different metaheuristics [START_REF] Alba | Parallel Metaheuristics: A New Class of Algorithms[END_REF], [START_REF] Tantar | A comparative study of parallel metaheuristics for protein structure prediction on the computational grid[END_REF], [START_REF] Alba | Natureinspired distributed computing[END_REF].

Rollout algorithms were first proposed by Tesauro and Galperin for improving a Backgammon program [START_REF] Tesauro | On-line policy improvement using monte-carlo search[END_REF]. The idea of a rollout is to improve a heuristic playing games that follow the heuristic and using the result of these games to evaluate moves. Rollouts were applied to different optimization problems [START_REF] Bertsekas | Rollout algorithms for combinatorial optimization[END_REF], [START_REF] Bertsekas | Rollout algorithms for stochastic scheduling problems[END_REF], [START_REF] Mancini | New rollout algorithms for combinatorial optimization problems[END_REF], [START_REF] Secomandi | Analysis of a rollout approach to sequencing problems with stochastic routing applications[END_REF].

Nested rollouts were found effective for the game of Klondike solitaire [START_REF] Yan | Solitaire: Man versus machine[END_REF]. The base level uses a domain specific heuristic to guide the samples. Nested rollouts have also been used for Thoughtful Solitaire, a version of Klondike Solitaire in which the locations of all cards is known. In this case they were used with heuristics that change with the stage of the game [START_REF] Bjarnason | Searching solitaire in real time[END_REF].

Recently there has been interest in the parallelization of Monte-Carlo tree search, especially for the game of Go [START_REF] Cazenave | On the parallelization of UCT[END_REF], [START_REF] Gelly | The parallelization of montecarlo planning[END_REF], [START_REF] Cazenave | A parallel monte-carlo tree search algorithm[END_REF], [START_REF] Chaslot | Parallel monte-carlo tree search[END_REF], [START_REF] Kato | Parallel monte-carlo tree search with simulation servers[END_REF].

Morpion Solitaire is an NP-hard puzzle [START_REF] Demaine | Morpion solitaire[END_REF]. A move consists in adding a circle such that a line containing five LAMSADE, Université Paris-Dauphine Place Maréchal de Lattre de Tassigny, 75775 Paris Cedex 16, France email: cazenave@lamsade.dauphine.fr Université Paris 8, LIASD 2 rue de la liberté, 93526, Saint-Denis, France email: n@ai.univ-paris8.fr circles can be drawn. Lines can either be horizontal, vertical or diagonal. The starting position already contains circles disposed as in figure 1. In the disjoint version a circle cannot be a part of two lines that have the same direction. The best human score at Morpion Solitaire disjoint version is 68 moves [START_REF] Demaine | Morpion solitaire[END_REF]. The previous best computer score was 79 obtained with Simulated Annealing [START_REF] Hyyro | New heuristics for morpion solitaire[END_REF]. A reflexive Monte-Carlo algorithm was shown to be effective for Morpion Solitaire [START_REF] Cazenave | Reflexive monte-carlo search[END_REF]. Reflexive Monte-Carlo search is close in spirit to nested rollouts except that the base level plays random games and does not follow a heuristic.

Guerriero and Mancini have proposed two parallel strategies for rollout algorithms [START_REF] Guerriero | Parallelization strategies for rollout algorithms[END_REF]. They were tested on the Traveling Salesman Problem (TSP) and the Sequential Ordering Problem (SOP). With their speculative strategy they obtained a modest average speedup of 2.53 on 8 processors for SOP and TSP. They obtained speedup ranging from 3.89 to 6.64 on 8 processors depending on the size of the neighborhood for SOP.

In this paper we propose the parallelization of a nested rollout algorithm on a cluster.

III. The sequential algorithm

The basic sample function just plays a random game from a given position: int sample (position) 1 while not end of game 2 play random move 3 return score

The score is the score of the game in the terminal position. For example at Morpion Solitaire the goal is to play as many moves as possible, so the score is the number of moves played in the game. In other games where the algorithm is of interest, the score can be computed completely differently. The idea of the score function is that the algorithm tries to find the sequence of moves that maximizes it.

The

IV. Parallel algorithms

In order to parallelize nested rollouts we define four types of processes: the root process, the median node processes, the dispatcher process and the client processes. These processes work at different levels of nesting: the root process at the first level (the highest level of nesting), the median process at the second level and the client processes at the third level. The root process plays a game at the first level and calls the median processes to play games at the second level. The median processes ask the client processes to play games at the third level in parallel. The dispatcher process is used to tell median nodes which clients to use. The third communication (fig. 2(c)) occurs when a client of a median node has finished its search. It then sends back the result to the median node that has asked for this search. Once the median node has all its results, it can choose the best move, play it and continue its game going back to the second communication. When the game is over, it uses the fourth communication (fig. 2(d)) which consists in sending the result of the game to the root node.

A. The Round-Robin algorithm

(e) The root process plays a game until the end at the highest level. The number of median nodes is greater than the number of possible moves. Median nodes are mainly used to dispatch the computation at a lower level on the client nodes, they are not used for long computation. Starting from the current position of the game, the root process tries each possible move and sends the resulting position to a different median node. Then it waits for all answers from median nodes previously chosen. Once it has all answers, it can choose the move that has the highest score, play it and loop until the end of the game.

The pseudo code for the root process is : The code for the Round-Robin dispatcher is: A median process receives a position to play from the root process. At each step of a game, it tries all possible moves and asks the dispatcher which client to use to evaluate each move. It then waits for the client node from the dispatcher, and once it has received it, it sends to the client node the position to evaluate. After having sent all the positions (one for each possible move), it waits for all the corresponding answers from the clients. Each answer consists in a score. When it has received all the scores, it chooses the move that has the highest score and plays it. Then it loops until the end of the game. Eventually, it sends back the score of the game to the root process.

1
1 client = first
The code for a median process is: A client process waits for a position from a median node. When it receives the position, it plays a nested rollout at a predefined level, and sends back the resulting score to the median node. In the case of the Last-Minute algorithm it also warns the dispatcher that it is available, sending its own identifier.

1
The code for a client process is:

1

B. The Last-Minute algorithm

Figure 4 shows the difference between the Round-Robin algorithm and the Last-Minute algorithm. Instead of only sending back the result of a search to its median node (fig. 2(c)), a client also warns the dispatcher that it is free (fig. 4(c')). The dispatcher maintains a list of free clients and a list of jobs. Jobs are ordered by expected computation time. The expected computation time is estimated with the number of moves already played in a game. When a request is received by the dispatcher, either there are free clients and it sends back the first free client, or there are no free clients and the job is added to the list of jobs. When it is notified by a client that the client is free, either it sends this client to the median node of the longest expected job, (c') Fig. 4. Communication between processes during the Last-Minute algorithm or if there are no available jobs it adds it to the list of free clients. The other communications are similar to the Round-Robin algorithm.

Figure 5(e') shows that communications can occur in parallel.

The Last-Minute dispatcher waits for a node from any client. If it receives a client node, it means that this client node is waiting for a new job, therefore if there are pending jobs it sends the job with the smallest number of moves to this client. If there are no pending job, it simply adds the client to the list of free clients. If it receives a median node, it also receives the number of moves of the position to analyze. If there are no free clients, it adds the job to the list of pending jobs. If there is a free client it sends the free client to the median node and removes the client from the list of free clients.

The pseudo-code for the Last-Minute dispatcher: server connected with a Gigabit network. We used message passing with Open MPI [START_REF] Gabriel | Open MPI: Goals, concept, and design of a next generation MPI implementation[END_REF] as parallel programming model. Open MPI is designed to achieve high performance computing on heterogeneous clusters. All communications are done with the global communicator MPI COMM WORLD. Each node runs two client processes. Processes are created at the beginning of the execution, via the use of the master-slave model. The server runs the root process as well as all the median processes and the dispatcher. Most of the computation is performed by the clients. We run the 40 median processes on the server and the client nodes on the dual core PCs.

1 listFreeClients =
All experiments use Morpion Solitaire disjoint model. All the time results are a mean over multiple runs of each algorithm, except for results in parenthesis which were run only once. The standard deviation is given between parenthesis after the time results. The algorithms were tested on playing only the first move of a game, and on playing an entire game. All experiments consist in testing the algorithms at level 3 and 4 of nesting. Each rollout needs a time that is slightly different from others since random games inside each rollout can have different lengths. Times taken by two rollouts can be different. Standard deviations show these times variations.

The results for the sequential algorithm are given in table I. We can observe that level 4 takes approximately 207 times more time than level 3. One rollout takes approximately 9 times more time than the first move. III gives the times for playing a rollout with the Round-Robin algorithm at level 3 and 4. The speedup of the algorithm for 64 clients is 44.

Table IV gives the results of the Last-Minute algorithm for the first move at levels 3 and 4. Results are similar to the Round-Robin algorithm at level 3. The speedup for level 4 is 30 which is a little higher than the Round-Robin algorithm.

Table V gives the results of the Last-Minute algorithm for rollouts at levels 3 and 4. Results are slightly better than the Round-Robin algorithm. Running the algorithm at level 4 on our cluster, we have discovered two new sequences of 80 moves which is the current world record.

VI. Conclusion

We have presented two algorithms that parallelize Nested Monte-Carlo Search on a cluster. The speedup for 64 clients is approximately 56 for Morpion Solitaire which is a problem with a large state space and no good known heuristic. The Last-Minute algorithm is more adapted to heterogeneous clusters. The parallel algorithm run at level 4 has found sequences of length 80 which is the current world record at Morpion Solitaire disjoint version (see for example figure 1).

Fig. 1 .

 1 Fig. 1. A world record found by Parallel Nested Monte-Carlo Search at Morpion Solitaire disjoint version

Figure 2

 2 Figure2details the Round-Robin algorithm. There are four possible communications. The first one (fig.2(a)) consists in a message from the root node to a median node that asks the median node to perform a nested search at the lower level.During the second communication (fig.2(b)), the median node asks to the dispatcher which clients it should use, once it has received a client, it asks this client to perform a nested search at the lower level.

Fig. 2 .

 2 Fig. 2. Communication between processes during the Round-Robin algorithm

Fig. 3 .Figure 3

 33 Fig. 3. Parallel communications that can occur during the Round-Robin algorithm

while not end of game 2

 2 (position, move with best score) 10 return scoreThe Round-Robin dispatcher consists in choosing the next client in the list of clients for each request. It receives messages from median nodes that ask it on which client to send their computation. It simply sends back clients one after another, always in the same order.

Fig. 5 .

 5 Fig. 5. Parallel communications that can occur during the Last-Minute algorithm

  Our cluster is composed of 20 1.86 GHz dual core PCs, 12 2.33 GHz dual core PCs and one quad core

		all Clients
	2 jobs = empty list
	3 while true
	4	receive node from any node
	5	if node is a client node
	6	add node to listFreeClients
	7	if jobs is not empty
	8	find j in jobs with
		the smallest number of moves
	9	send j.sender to the node
	10	remove j from jobs
	11	remove node from listFreeClients
	12	else if node is a median node
	13	receive number of moves from node
	14	addNewJob = true
	15	if listFreeClients is empty
	16	add {node, number of moves} to jobs
	17	else
	18	client = first element of listFreeClients
	19	send client to node
	20	remove client from listFreeClients
		V. Experimental Results

TABLE I

 I Times for the sequential algorithm

  TableIIgives the times for playing the first move with the Round-Robin algorithm at level 3 and 4. The speedup of the algorithm for 64 clients is 56 (in fact it should be a little less since the time with one client is on a 1.86 GHz PC), if we use the ratio of the mean cluster frequency on

	clients	level 3		level 4
	64	10s	(1s)	33m11s (1m33s)
	32	20s	(2s)	1h04m44s (3m02s)
	16	37s	(5s)	(2h10m)
	8	01m11s	(8s)	-
	4	02m22s (11s)	-
	1	09m07s (28s) (29h56m14s)

TABLE III

 III Rollout times for the Round-Robin algorithm the single client frequency we obtain r = ((20 × 1.86 + 12 × 2.33)/32)/1.86 = 1.09. So the speedup should rather be closer to 56/1.09 = 51. The result for 32 clients is obtained using only 1.86 GHz PCs, and this time the speedup is 29.8. Concerning level 4 the speedup is 28.50 for 32 clients. Table

  Table VI compares the two algorithms with an heterogeneous repartition (where 16x4+16x2 means that there are 16 PCs with 4 clients and 16 PCs with 2 clients and where 8x4+8x2 means there are 8 PCs with 4 clients and 8 PCs

	clients	level 3		level 4
	64	09s	(2s)	27m20s (1m22s)
	32	19s	(1s)	59m44s (2m21s)
	16	37s	(4s)	(2h05m17s)
	8	01m12s	(5s)	-
	4	02m23s	(4s)	-
	1	09m30s (21s) (33h06m57s)

TABLE VI

 VI First move times on an heterogeneous cluster with 2 clients). At level 4 the Last-Minute algorithm (LM) has better results than the Round-Robin algorithm (RR).The Last-Minute algorithm gives better results than the Round-Robin algorithm in an heterogeneous environment. The speedup of the Last-Minute algorithm for rollouts of level 4 with 64 clients is approximately 56 which is quite good.