P Audouard

G Chaslot

J.-B Hoock

J Perez

A Rimmel

O Teytaud

Grid coevolution for adaptive simulations; application to the building of opening books in the game of Go

This paper presents a successful application of parallel (grid) coevolution applied to the building of an opening book (OB) in 9x9 Go. Known sayings around the game of Go are refound by the algorithm, and the resulting program was also able to credibly comment openings in professional games of 9x9 Go. Interestingly, beyond the application to the game of Go, our algorithm can be seen as a "meta"-level for the UCT-algorithm: "UCT applied to UCT" (instead of "UCT applied to a random player" as usual), in order to build an OB. It is generic and could be applied as well for analyzing a given situation of a Markov Decision Process.

Introduction

The game of go is an ancient Asian game with the nice property that it is much harder for computers than chess and therefore still unsolved -whereas nowadays computers play handicap games in chess against top-level humans (the handicap is here for helping the human!), the top human Go players still win very easily handicap games against humans (with the handicap for helping the computer!). However, the handicap has strongly reduced. In 1998, a 6D human player could win with 29 handicap stones [START_REF] Müller | Computer go[END_REF] against a top program, Many Faces of Go, whereas in 2008, MoGo (running on the supercomputer Huygens) could win with 9 handicap stones against a top-level human player, Kim Myungwan (8 th Dan pro and winner of the US Open 2008); the human also said that MoGo could probably win also with only 8 handicap stones and was roughly 2nd or 3rd Dan. The most important tool for this strong improvement is Monte-Carlo Tree Search [START_REF] Péret | On-line search for solving markov decision processes via heuristic sampling[END_REF][START_REF] Coulom | Efficient selectivity and backup operators in monte-carlo tree search[END_REF][START_REF] Kocsis | Bandit-based monte-carlo planning[END_REF][START_REF] Chaslot | Progressive strategies for monte-carlo tree search[END_REF][START_REF] Gelly | Combining online and offline knowledge in uct[END_REF].

Complexity of OB in Go. Handcrafting OB in Go is quite hard because the usual knowledge is not encoded as a mapping situation → answer but much more as a set of local rules (termed Joseki), to be applied only after consideration of the global situation of the board. Also, a well known proverb in Go says "Learn joseki, loose two stones" (LJLTS): when a player learns these rules, he becomes weaker in a first time. The simple explanation to this fact is that local context in Go must always be related to the global situation of the board; so, blindly applying newly learned opening sequences leads to inevitable mistakes concerning the global context of the game known as "errors in the direction of play". Indeed, choosing between several opening sequences depending on the global context is one of the hardest skill to acquire in the game of go, because the amount of experience required to handle the emptiness of the beginning of the game is huge.

For games in which standard game algorithms (using variants of minimax) work, building automatically an OB is more or less difficult, but usually it works [START_REF] Buro | Toward opening book learning[END_REF], possibly with complicated tricks for removing bad moves [START_REF] Donninger | Innovative opening-book handling[END_REF]. In the case of 9x9 Go, efficient computer players are very recent and there's no positive result on 9x9 Go OB. Also, as these recent (and strong) players are mainly best-first search, i.e. focus on a small number of moves and not on all moves, it is not clear that they can be used for building OB -OB imply some diversity. We will here show that this approach works; this result, besides its positive effectiveness, is also interesting for understanding how best-first search algorithms can be efficient for games in spite of the fact that they only study a little set of moves (without efficient expert pruning).

Best first research in games. A main element in games is the branching factor. More than the incredible number of legal situations [START_REF] Tromp | Combinatorics of go[END_REF], the trouble in Go is that pruning rules are quite inefficient and therefore the "practical" branching factor is not so far from the "theoretical" branching factor. This is in particular true for building OB; requesting suggestions from professional players is quite difficult when the number of possible situations is huge as in the case of Go. How do we handle this problem ? A naive approach would require 1 request for the first move, 81 for the second move, and so on. How to reduce this combinatorial explosion ? As well as MCTS is efficient in front of the combinatorial explosion of Go, we show here that a meta-level of MCTS (MCTS on top of MCTS, see below) is efficient in front of the combinatorial explosion of OB. As the detailed presentation of MCTS is beyond the scope of this paper, we here refer the reader to [START_REF] Coulom | Efficient selectivity and backup operators in monte-carlo tree search[END_REF][START_REF] Kocsis | Bandit-based monte-carlo planning[END_REF][START_REF] Chaslot | Progressive strategies for monte-carlo tree search[END_REF][START_REF] Gelly | Combining online and offline knowledge in uct[END_REF] for more information around MCTS, and here we insist only on the fact that MCTS is a coevolution 1 .

MCTS leads to a "best-first" approach 2 in the sense that when we build a tree of future situations, a move is further analyzed as long as it is the move with best success rate in the simulations. Is this reasonable for OB ? The experimental answer given by this paper is positive, and we justify it as follows: (i) assume that for a fixed height d (i.e. there are d moves at most before the end), the estimate of the winning probability of winning converges to 0 or 1, depending on whether this situation is winning or not; (ii) then for a situation with height d + 1, the move with best success rate will not stay the move with best success rate if it is not a winning move, and this will ensure diversification. Of course, this is quite "sequential": no alternate move is explored if the first explored move is still at a high success rate in spite of the fact that it is not the best move. But MCTS has shown that with a strong enough computational power, this approach is in fact very reliable and better than classical approaches; we here show that it is also reliable in the difficult framework of OB in spite of the intuitive diversity requirement.

All our experiments are based on MoGo, the first program which (i) won a game against a pro player in 9x9 Go (Comp.-Go Olympiads, Amsterdam 2007), (ii) won a game against a pro player without blitz in 9x9 Go (IAGO challenge, Paris, 2008), (iii) won a game against a pro player in 19x19 Go with handicap 9 (US Go Congress, Portland, 2008). The OB built as explained below was used in the Hakone 2008 computer-Go Cup, won by MoGo. All Go figures use the PSGO package. Comments which require a high-level in 9x9 Go are given by Pierre Audouard (P.A.). P.A. is teaching Go since 1992; he was 17 th in the World Amateur Go Championship (Tokyo 2008). He has a special interest in 9x9 Go and won the 1st international disabled Go tournament of 9x9 Go (Seoul, 2008). Section 2 presents the methods investigated in this paper and shows experiments in an artificial setup. Section 3 shows real-size experiments. The conclusion will emphasize some generality of the result.

Methods and preliminary results on fast time settings

The goal is the incremental building of a set of games (an OB), supposed to be used by a (human or computer) player as follows: If the current situation is in the set of games, choose the most frequent move in won games. We choose the most simulated move in won games, instead of the move with highest success ratethere are far less erroneous moves with the most simulated move in won games. This is consistent with the MCTS literature (see e.g. [START_REF] Wang | Modifications of UCT and sequence-like simulations for Monte-Carlo Go[END_REF]). We use self-play as a basic tool for building OB, as in [START_REF] Nagashima | Self-playing-based opening book tuning[END_REF] (for computer-Shogi). Precisely, while looking for a methodology for building an OB with coevolution, we understood that MCTS is precisely a tool for building OB, usually applied to a naive random player and with small time settings, and that what we need is essentially MCTS with however (i) very different time settings (ii) a good computer player; in this paper, the good player is itself the original MCTS. Our non-evolutionary methods for building OB are as follows. Expert OB: A handcrafted set of games played by top level players and optimized manually (even pro games can be optimized offline by experts). 4H-OB: A version of MoGo spending 4H studying each move plays against a MoGo spending 1s per move. After 4 moves, the MoGo playing 1s per move resigns. These two MoGos use no OB and are not adaptive (no learning). The 4H-OB was rejected as weaker than the expert OB.

Coevolution has already been used for building partial strategies in Chinese chess [START_REF] Ong | Discovering chinese chess strategies through coevolutionary approaches[END_REF] and also in the game of Go [START_REF] Drake | Coevolving partial strategies for the game of go[END_REF], but with less impressive results -our coevolution will therefore be exactly MCTS. MCTS is usually not presented as a coevolution, and we designed our coevolutionary algorithm (CA) for OB without conceiving it initially as a MCTS; but MCTS consists in evolving a white strategy and a black strategy in a given situation, by mutating the policy in the currently studied variation. Our CA is "MCTS applied to MoGo-black and MoGo-white", as well as MoGo is "MCTS applied to a naive random black player and a naive random white player" (not "very" naive; see [START_REF] Wang | Modifications of UCT and sequence-like simulations for Monte-Carlo Go[END_REF] for details). Our co-evolutionary techniques for building OB are as follows, starting from a part of the handcrafted OB (the complete version was not available at that time). Mutate bad moves (MBM, Algo. 1): MoGo plays against itself (each player has 6h per side on a quad-core, roughly equivalent to 24h per side as the speed-up of MCTS for 4 cores is very good). The two MoGo use the OB and choose the move with highest success rate if at least one move with success rate > 50 % is available. Otherwise, the standard MoGo algorithm is used. Mutate very bad moves (MVBM): Mogo plays against itself (each player has 6h per side). The two mogo use the OB and choose the move with highest success rate if at least one move with success rate > 10 % is available. Otherwise, the standard MoGo algorithm is used. MVBM was introduced because, with MBM, there were too many cases in which black did not follow any OB at all because the success rate of black was lower than 50 %. Both algorithms are a coevolution, in which an individual is a game (the games won by black (resp. white) are the black (resp. white) population; each won (resp. lost) game is a good (resp. bad) partial strategy), and as in the Parisian approach [START_REF] Collet | Polar ifs + parisian gp = efficient inverse ifs problem solving[END_REF], the solution (the OB) is made of all the population. This algorithm is used on a grid (www.grid5000.fr, a great grid provided freely for scientific experimentation). This introduces some constraints: λ is not known in advance and not constant (λ depends on the number of available CPUs, and jobs might be preempted). In order to have preliminary results, we first run MBM on a simplified setting (see section 2.1). We see first that the depth-first approach works fine, what is a great success as building OB in Go is quite difficult; these results, quite good for white, are based on MBM. We will see however that this approach is not satisfactory for black and therefore derived the MVBM approach.

Why we should mutate very bad moves only

We here experiment the MBM approach, on a simplified case of 10 seconds per move, 8-cores machine; in this easier framework we could generate 3496 games. The results follow:

Conditions

Before learning After learning Against handcrafted OB Success rate (white) 51.5 % ± 1.8 % 64.3 % ± 1.9 % 64.1 % ± 1.8 % Success rate (black) 48.5 % ± 1.8 % 48.0 % ± 1.9 % 46.1 % ± 1.8 %

The first column sums to 100 % as it is the success rate of white (resp. black) in the case of no learning. The second column shows the results for white (resp. black) after learning against a non-learning version: the sum is higher than one as Fig. 1. Left: success rate as black against the non-learning version. Right: success rate as white against the non-learning version. For both figures, the abscissa is the time index (number of test games played); the plot is made on a moving average on 100 games.

follows against the version without OB, more than if we use the handcrafted OB (Figure 2, left). We can also check the results in self-play: is one of the player winning more and more often, converging to a resolution towards 100 % of won, i.e. a complete solving of the game ? We plot the results in figure 2 (right). Highlevel Go-players usually consider that with Komi 7.5, white has the advantage. Fig. 2. Success rate of the self-learning version against itself, as white. This is consistent with usual knowledge about 9x9 Go with Komi 7.5 for strong players: the white player has the advantage.

This is supported by the final result (Figure 2). Comment from P.A.: It is known that with Komi 7.5 white should have the advantage on average, if the level is sufficiently high -this is therefore consistent.

Below, we: present some general statistics on the optimization run and the resulting OB (section 3.1); check some known points in Go (section 3.2); present links between variations (i.e. sequences) studied by MoGo and professional games (section 3.3).

Statistics on the final population of our grid-coevolution

We checked that all answers to all moves cited as classical in 9x9 Go in http: //senseis.xmp.net/?9x9Openings have their answer in the OB. Therefore, if a (black or white) player plays his first move in this library of moves, then an opponent playing with the OB has an automatic answer. Also, on average, the number of moves played by MoGo inside his OB against GnuGo 3.6 and Fuego 0.2.2 is 3.28 and 4.64 moves respectively.

Comments by P.A. on the OB built by MVBM

We consider here some well known elements, proposed for test by P.A.: Mane Go, i.e. a strategy known very efficient for white after an initial move of black different from E5; Kosumi, i.e. a class of moves for which some elements are known. Mane Go, for the white player, consists in replying symmetrically to the black moves, for white, when black does not start with E5. With this simple strategy for white, black has to break the symmetry (by playing in the center E5) and is in a more difficult situation. P.A. tested Mane Go as follows. First move black F6: MoGo as white answers D4; then we test black D6 and MoGo as white replies symmetrically, i.e. F4. First move black F5: MoGo as white answers D5; then we test black E7 and MoGo as white replies symmetrically, i.e. E3. Kosumi consists in playing two stones (of the same color), in diagonal. This might be a good idea in a game, but usually not in the beginning. Here are the statistics in the final population. Many cases of Kosumi appeared just a few times and then disappeared; the only one which appeared significantly is a Kosumi between the first and third move for black: E5 G5 F4. F4 and G5 are in Kosumi. However, this Kosumi is somewhat rare and is not chosen by MoGo when it uses the usage rule of the move used in most won games -it just appears in the exploration. However, this shows that our MVBM approach can spend time on weak moves. Comment from P.A.: The absence of Kosumi for white before the seventh move is a good feature. Kosumi might happen later in the game. On the other hand, the choice E5 / G5 / F4 often studied by MoGo (though not selected at the end) for black is not a good one. We can also check the currently analyzed openings: the last games are based on E5 / G5 / G4 / C5 or E5 / G5 / G4 / C6. This is a quite classical beginning. Also, P.A. could check that MVBM never plays as black E5/C5/E3/G5/E7 (a classical sequence of MoGo when openings are removed), which was quite bad.

Comments by MoGo on professional games, and their evaluation by a Go-expert

Due to length constraints, this section, which can only be evaluated by 9x9-Go experts, is reported to a technical report and we only summarize here the analysis of some professional games provided by P.A. MVBM does not like the variation E5/G5/G4/C4 found in several professional games; in the population, after E5/G5/G4/C4, Black wins with probability 67.9% (whereas C5 instead of C4 is fine). According to the population, E5/G5/G4/C4/F5 is strong for black. This is consistent with pro games, as the 5 professional games with this sequence were all won by black. Also, the only game played in which black answered F4 was lost by black; this move was not considered at all by MVBM. Only one game was played with H5 (E5/G5/G4/C4/H5); according to MoGo, this sequence is very good for black; however, black lost that game. Interestingly, MVBM has simulated also the next moves until the 20 th move; MVBM considers that black made a mistake later in the game and should have won with a different move (winning with probability 100% according to MVBM). Comment by P.A.: MVBM is right when he says that C4 is not the best choice after E5/G5/G4 and that C5 should be chosen. Also, MVBM is right when he says that black made a mistake later in the game lost after the good initial sequence E5/G5/G4/C4/H5but the mistake is later than the move pointed out by MVBM. On the other hand, the move proposed by MVBM is quite strong and really leads to a good position for black. Also, MVBM does not like the sequence E5/G5/F3; according to MVBM, White can then win with probability 75% by playing C6, or possibly C4 (70%), G3 (70%); D3 is possible also (50%) and all other moves are considered as weak by MVBM. A professional game features this sequence E5/G5/F3 with a win for black, and this is in accordance with MVBM as white then played C5, one of the bad moves according to MVBM. Comment by P.A.: In spite of the fact that MVBM's prediction is in accordance with the result of the game, C5 a good move after E5/G5/F3. Other moves proposed by MoGo are also interesting and it's difficult to choose between them. C4/C6 are more complicated than C5, and G3 is a contact move, it might be dangerous -however, in 9x9, such an early contact move can be considered. Finally, MVBM analyzed E5/G5/G4/C5. A professional player played F4 in this situation, and MVBM explored this solution with the same preferred answer after E5/G5/G4/C5/F4 as the one played in this professional game; however, MoGo considers that F4 should be replaced by E3 with success rate 59 % instead of F4. Comment by P.A.: E3 is not a good idea. This is not a good reason for the result of the considered professional game.

Conclusion

We used a CA for generating OB for the game of Go. There's no big efficient OB available. First, the positive results follow. First, effectiveness. The resulting OB is satisfactory and consistent with results of professional games. It leads to quite good results in the sense that the program is much stronger with the OB than without. It is also satisfactory, in most cases, from the point of view of an expert human player: some known rules have been found independently by the algorithm (Kosumi, Mane Go, comments on professional games). Second, grid-compliance. Thanks to preemptable jobs (the algorithm is completely fault tolerant), the use of the grid was not too much a trouble for other users. It was also possible to have simultaneously a small number of non-preemptable jobs and plenty of preemptable jobs, so that the grid is used adaptively. A much bigger run is under progress on grid5000, and thanks to preemptable jobs has little impact on the grid. Third, parallelization. The speed-up is seemingly good, as (i) there's very little redundancies between individuals in the population (ii) the individuals are different just a very few moves after the initial sequence which is not randomly mutated. This is consistent with [START_REF] Teytaud | Lower bounds for evolution strategies using vcdimensio n[END_REF] which has shown that evolution strategies have a very good speed-up when the problem has a huge dimensionality: the domain here is huge [START_REF] Tromp | Combinatorics of go[END_REF]. Fourth, user-friendly aspect.

It is easy to monitor the optimization, as at any fixed time step we can see which sequence is currently analyzed by the algorithm. Fifth, generality. We applied our algorithm to the empty Goban (initial situation), but it could be applied easily to a given situation (Tsumego analysis). Also, it can be used for analyzing a particular situation for any Markov Decision Process. After all, MVBM is an adaptive Monte-Carlo algorithm: it is based on an initial strategy, and incrementally improves this strategy, based on simulations -it is like a Monte-Carlo algorithm used for plotting a Value-At-Risk, but used adaptively. Applications in finance or power plant management is straightforward. Some less positive points are as follows: First, one of the solution proposed by the algorithm is weak according to P.A., namely E5/G5/G4/C5/E3. By the way, the solution was later replaced (in the current run), but there was no indicator, at that time, of the fact that E3 was a bad solution. We have an algorithm which is therefore consistent, but we can't guess a priori that a solution is still unstable. Also, E5/G5/F4 was not in the final result, but a long exploration has been made on this move, whereas it is, according to P.A., a poor solution that could be removed by expert knowledge around "Kosumi". Second, no free lunch:

the OB generated by a poor random player (MoGo with small time settings) is useless for a better MoGo (with longer time settings). This is consistent with [START_REF] Donninger | Innovative opening-book handling[END_REF]: the presence of erroneous moves is a major trouble when building OB.

This looks obvious in our case as we have "real" games as initial points for our coevolution instead of random games, and "real" moves instead of naive random moves, but MCTS also is definitely a coevolution between variations as well.

MCTS has often been emphasized as a compromise between exploration and exploitation, but many practitioners have seen that in the case of deterministic games, the exploration constant, when optimized, is zero or indistinguishable from zero, leading to a best-first approach.

Acknowledgements. We are very grateful to B. Bouzy, T. Cazenave, A. Cohen, R.

Coulom, C. Fiter, S. Gelly, B. Helmstetter, R. Munos, Z. Yu, the computer-go mailing list, the KGS community, the Cgos server, the IAGO challenge, the Recitsproque company, the French Federation of Go, and Grid5000.

Algorithm 1

The "mutate bad move" (MBM) algorithm. λ is the number of machines available. The random choice is performed by MoGo with long time settings (except in section 2): therefore, it is quite expensive. Readers familiar with UCT/MCTS might point out that there is no exploration term in the version of MCTS presented here; however, this is the case in many successful MCTS implementations, and other implementations often have a very small constant which is equivalent, in fact, to 0. MBM did a good job on average. The third column shows that the learning has provided better results than the handcrafted OB. However, we see no progress for black. This can be explained as follows: as long as black has not found a move with success rate > 50%, he always mutates. Therefore, white improves his results by choosing moves with higher success rates, but not black. This is why in next sections, we will use the "mutate very bad moves" approachasymptotically it is probably equivalent, but non-asymptotically it's better to use an approach in which 40% of success rate is better than 30 % of success rate instead of repetedly mutating in order to find at least 50 %.

Learn Joseki, loose two stones (LJLTS)

These results above look quite promising, but we then tested what happens if we use this learnt OB in a stronger version of MoGo (i.e. with bigger time settings), using 60s per move instead of 10s (still on 8-cores machines).

Validation of the OB for a stronger version of MoGo. Success rate of the handcrafted OB against no OB for 60 s per move: 50 % as black, 63 % as white. Clearly the handcrafted OB still works for this stronger MoGo. Success rate of the learnt OB (learnt as above, with 10s per move games) against handcrafted OB: 30.6 % as black, 40.7 % as white. The learnt OB, learnt for 10s per move, is definitely not sufficiently strong for 60s per move. These numbers show that a weak player can't estimate efficiently an opening sequence, whenever this weak player performs hundreds of games -the opening sequence might be good for this weak-player, but this opening sequence will become a handicap when the player will become stronger.

Robustness of the handcrafted OB. We then switched to 300s per move, still on 8-cores machines, to see if the handcrafted OB was still efficient. Success rate of the handcrafted OB against no OB: 49.6 % as black, 57.0 % as white. We then considered an optimized handcrafted OB, still for 300s per move, and reached 49.7% as black, 62.9 % as white. This shows the LJLTS: if you learn Joseki (handcrafted opening moves) which are too difficult for you (if MoGo has only 10s per move), they are not efficient (you'd better use your own learnt opening moves). But if you become stronger (MoGo with 60s/move or 300s/move), you can trust the Joseki (the handcrafted rules).

3 Real-size experiments on MVBM for 9x9 Go, Komi 7.5 In this section we present the results of the real-size experiments on MVBM. Each game is played with 6h per side on a quad-core. 3000 games are played, i.e. the final population has 3000 individuals. MVBM is "Parisian": all the population is the solution. Also, there's no removal: the population is incrementally increasing, and no individual is never eliminated (it might just become negligible). The handcrafted OB used in this section is an improved version of the one used in the previous section. We first show that the learning version becomes stronger and stronger, in front of the non-learning version. Results are presented in figure 1. The good point is that on average on the learning we have a success rate as


Chang-Shing Lee

Mei-Hui Wang

Guillaume Chaslot

Jean-Baptiste Hoock

Arpad Rimmel

Olivier Teytaud
email: olivier.teytaud@inria.fr

Shang-Rong Tsai

Shun-Chin Hsu

Tzung-Pei Hong

The Computational Intelligence of MoGo Revealed in Taiwan's Computer Go Tournaments

Keywords: Computational Intelligence, Computer Go, Game, MoGo, Monte-Carlo Tree Search

In order to promote computer Go and stimulate further development and research in the field, the event activities, "Computational Intelligence Forum" and "World 9×9 Computer Go Championship," were held in Taiwan. This study focuses on the invited games played in the tournament, "Taiwanese Go players versus the computer program MoGo," held at National University of Tainan (NUTN). Several Taiwanese Go players, including one 9-Dan professional Go player and eight amateur Go players, were invited by NUTN to play against MoGo from August 26 to October 4, 2008. The MoGo program combines All Moves As First (AMAF)/Rapid Action Value Estimation (RAVE) values, online "UCT-like" values, offline values extracted from databases, and expert rules. Additionally, four properties of MoGo are analyzed including:

(1) the weakness in corners, (2) the scaling over time, (3) the behavior in handicap games, and (4) the main strength of MoGo in contact fights. The results reveal that MoGo can reach the level of 3 Dan with, (1) good skills for fights, (2) weaknesses in corners, in particular for "semeai" situations, and (3) weaknesses in favorable situations such as handicap games. It is hoped that the advances in artificial intelligence and computational power will enable considerable progress in the field of computer Go, with the aim of achieving the same levels as computer chess or Chinese chess in the future.

I. Introduction

Games provide competitive dynamic environments that are ideal for testing computational intelligence theories, architectures, and algorithms [START_REF] Lucas | Evolutionary computation and games[END_REF]. Many studies have identified the developments, challenges, and opportunities for applying computational intelligence methods to games [START_REF] Lucas | Evolutionary computation and games[END_REF] [START_REF] Lucas | Computational intelligence and games: challenges and opportunities[END_REF]. Additionally, Go remains an excellent challenge for computer science research; however, Monte Carlo methods have very recently shown significant promise, especially for small versions of the game such as 9 × 9 games. Therefore, the Upper-Confidence Tree (UCT) Monte Carlo has considerable potential for application to other games such as Hex, Amazons, and even Shogi [START_REF] Lucas | Computational intelligence and games: challenges and opportunities[END_REF] [START_REF] Schaeffer | Games, computers, and artificial intelligence[END_REF]. Schaeffer and Herik [START_REF] Schaeffer | Chips challenging champions: games, computer and artificial intelligence[END_REF] [START_REF] Schaeffer | Games, computers, and artificial intelligence[END_REF] noted that work on computer games has resulted in advances in numerous computing areas. Many ideas that developed through game-tree search have been applied to other algorithms. For example, the UCT Monte Carlo algorithm may have important applications to control Non-player Characters (NPCs) in video games such as Quake [START_REF] Lucas | Evolutionary computation and games[END_REF] [START_REF] Lucas | Computational intelligence and games: challenges and opportunities[END_REF].

Moreover, many studies have applied artificial intelligence (AI) and evolutionary computation to games.

For instance, Chellapilla and Fogel [START_REF] Chellapilla | Evolving neural networks to play checkers without expert knowledge[END_REF] [START_REF] Chellapilla | Evolving an expert checkers playing program without using human expertise[END_REF] developed an expert program that plays checkers without using human expertise or expert knowledge. Messerschmidt and Engelbrecht [START_REF] Messerschmidt | Learning to play games using a PSO-based competitive learning approach[END_REF] developed a competitive learning approach to playing games. Werf et al. [START_REF] Van Der Werf | Solving Go on small boards[END_REF] presented a search-based approach for playing Go on small boards. Bouzy and Cazenave [START_REF] Bouzy | Computer Go: an AI-oriented survey[END_REF] presented an AI-oriented survey of computer Go. Togelius et al. [START_REF] Togelius | Computational intelligence in racing games[END_REF] applied computational intelligence to racing games. Chen [START_REF] Chen | Maximizing the chance of winning in searching Go game trees[END_REF] proposed a strategy that maximizes the chance of winning when searching Go game trees. Cutumisu et al. [START_REF] Cutumisu | ScriptEase: a generative/adaptive programming paradigm for game scripting[END_REF] advocated the development of adaptive programming as an alternative to current constructive programming techniques, as well as the application of adaptive programming to many domains. Carbonaro et al. [START_REF] Carbonaro | Interactive story authoring: a viable form of creative expression for the classroom[END_REF] proposed an interactive story authoring technology that offers students an opportunity to successfully construct interactive game stories.

Zahavi et al. [START_REF] Zahavi | Duality in permutation state spaces and the dual search algorithm[END_REF] proposed a new dual search algorithm to improve the chance of reaching a goal fast, meaning that the algorithm does not necessarily visit all states on a solution path.

In chess, humans now need a handicap (in favor of the human) to have a chance of winning against top-level programs. In Go, humans are still heavily favored to win. For example, in 1998 Muller won despite 29 handicap stones against "Many Faces Of Go" [START_REF] Müller | Computer Go[END_REF]. Computer Go has, however, made considerable progress in recent years. Programs are currently competitive at the professional level in 9 × 9 Go, and MoGo has won with an advantage of "only" 9 handicap stones against top-level human players in 19 × 19 Go; additionally, CrazyStone won with handicaps of 8 and 7 stones against Kaori Aoba, a Japanese 4 th Dan Pro (4P). To strengthen computer Go programs and advocate research, development and application of computer games' related fields, Chang Jung Christian University (CJCU), National University of Tainan (NUTN), and the Taiwanese Association for Artificial Intelligence (TAAI) hosted the "2008 Computational Intelligence Forum and World 9×9 Computer Go Championship." This event, held in Taiwan, was to fulfill the purpose of "Enjoying learning through playing computer Go." Event activities were the "Computational Intelligence Forum" and "World 9 × 9 Computer Go Championship." The championship was divided into two sections. Section A, which comprised computer program competitions, was won by MoGo which was undefeated. Section B was human versus computer competitions.

The recent rapid improvements to computer Go are mainly due to the development and application of the Monte Carlo Tree Search (MCTS) algorithm. The MCTS algorithm and associated algorithms have been applied to computer Go. On the other hand, they have also been applied to several other games, such as Settlers of Catan [START_REF] Chaslot | Monte-Carlo tree search: a new framework for game AI[END_REF] and Texas Hold'em poker [START_REF] Maîtrepierre | Adaptive play in texas hold'em poker[END_REF], which show that when the branching factor after obvious pruning remains too large, or when no good handcrafted evaluation function exists, algorithms based on the "bandit principle" (compromises between exploration and exploitation) are efficient.

Real-time strategy games, which are games with incomplete information, have also been tested [START_REF] Chung | Monte Carlo planning in RTS games[END_REF].

Algorithms using the bandit principle have also been applied to, say, clinical trials with the MCTS algorithm [START_REF] Audibert | Tuning bandit algorithms in stochastic environments[END_REF], non-linear robust optimization using UCT [START_REF] Auger | Continuous lunches are free and the design of optimal optimization algorithms[END_REF], news selection with a technique based on mixing bandit and change-point detection, which was ranked first in the Nips/Pascal "Online Trading of Exploration and Exploitation Challenge 2006" [START_REF] Hartland | Multi-armed bandit, dynamic environments and meta-bandits[END_REF], and optimal sailing using simulations and a tree developed at the point of interest [START_REF] Peret | On-line search for solving markov decision processes via heuristic sampling[END_REF]. The new algorithms are remarkably scalable and have considerable

II. Recent Advances in Computer Go

Minimax and alpha-beta searches are the most common techniques used in computer games. In Go, these algorithms use patterns and/or expert rules to prune search trees. However, they cannot compete with humans in 9 × 9 or 19 × 19 Go games. One reason for this is that there is no good function to evaluate a position in Go. The MCTS algorithm has been designed to improve the performance of computer Go programs. This section introduces all the improvement features adopted by MoGo. It is divided into two subsections to briefly examine the MCTS approach. Why Monte Carlo evaluation is successful in Go is described in subsection A. The MCTS algorithm is then presented in detail in subsection B, in which Monte Carlo evaluation is adaptively biased by statistics from previous simulations. Additionally, the various formulas used in choosing compromises between exploration and exploitation, i.e., choosing which sequences should be studied carefully, are also described in subsection B.

A. Monte Carlo evaluation

Brugmann proposed an original evaluation function based on Monte Carlo exploration [START_REF] Brügmann | Monte Carlo Go[END_REF]. For a given situation s, the evaluation value is the probability of winning when a game is completed by an ad hoc random player p playing both black and white. This evaluation function depends on situation s, random player p, and the number n of simulations. Although this evaluation function proposed by Brugmann is quite generic, it has the following drawbacks:

-The evaluation function relies on a random player p. Designing such a random player is a "dark art" [START_REF] Wang | Modifications of UCT and sequence-like simulations for Monte-Carlo Go[END_REF]. That is, one can improve the performance of p as a standalone Go player and still have a weak evaluation function built on top of it. State-of-the-art Monte Carlo simulators have been designed by trial and error using the complete algorithm (i.e., random player p is relevant when the complete algorithm makes decisions with the evaluation function. Designing a good Monte Carlo simulator therefore involves experiments that last for several months;

-

The evaluation function may be very weak when robust evaluation functions exist (e.g., in chess); -The evaluation function can be very computationally expensive when games are very long.

For Go, only the first drawback is relevant, which may explain the success of the Monte Carlo evaluation.

The All-Moves-As-First (AMAF) value of a move improves Monte Carlo evaluation. This value is a good heuristic for identifying good moves [19][21]. In the MCTS setting, AMAF values are usually called Rapid Action Value Estimation (RAVE) values. The AMAF value of move m for player q (white or black) in situation s with random player p after n simulations is w/N, where (1) N is the number of games in n simulations, in which move m is played by player q before possibly being played by the opponent later in the game; and (2) w is the number of won games in n simulations, in which move m is played by player q before possibly being played by the opponent. The important point here is that move m is not necessarily the first move in situation s. This study considers AMAF values in all simulations, including move m played by the player whose turn is to play in situation s. These AMAF values are poor quality as the order of moves is not preserved: an AMAF simulation is not necessarily consistent with Go rules, as a permutation of a consistent game is in many cases inconsistent. For each real simulation, this study has a significant amount of AMAF values-one for each move by the same player in a simulation.

B. Combining Monte Carlo evaluation and a tree search

The Monte Carlo evaluation function evaluates a position in random games played starting from this position. Thus, Monte Carlo evaluation can be used as an evaluation function in an alpha-beta engine.

However, a recent and considerable improvement is the incremental construction of a tree on top of the Monte Carlo evaluation function. In each iteration, one simulation is launched from the current situation; however, the initial part of the simulation is in the tree (Fig. A3 of Appendix), which grows by adding the first situation of the simulation not yet in the tree. Outside the tree, the simulation uses the default random policy, whereas in the tree, simulation is based on moves that maximize a score combining two criteria: (

Exploration criterion: moves that have not been simulated often should be simulated frequently; and (2)

Exploitation criterion: moves that lead to high probabilities of winning should be simulated often. This implies that (1) Hashtable should be used to retain in memory many situations and statistics for these situations; these statistics can be used to adaptively change simulations using a compromise between exploration and exploitation; [START_REF] Lucas | Computational intelligence and games: challenges and opportunities[END_REF] The quantitative formulas should be defined to specify these biases.

Therefore, the resulting algorithm is called the MCTS algorithm [START_REF] Coulom | Efficient selectivity and backup operators in Monte-Carlo tree search[END_REF][23] whose pseudo-code is shown in Algorithm 1. Additionally, the MCTS algorithm depends on the Monte Carlo player (see Algorithm 2) and quantitative formulas (see Algorithm 3) that introduce bias into random choices.

Algorithm 1: Pseudo-code of a MCTS algorithm applied to a two-player game (typically Go or chess). T is a tree of positions, with each node equipped with statistics (number of wins and losses in simulations starting at this node). Concerning the decision line at the very end of the pseudo-code, the most simulated decision is known as the most reliable criterion; other solutions such as taking the decision with the highest ratio "number of wins divided by the number of simulations" are insufficiently robust, due to the possible small number of simulations. Here the reward at the end of each simulation is binary (win or loss) and deterministic (the reward only depends on the moves and not on random play), but arbitrary distributions of rewards can be used. Initialize T to a single node, representing the current state. while Time left > 0 do -Simulate one game until a position L is out of T (thanks to bandit algorithms, see Algorithm 3).

-Simulate one game from position L until the game is over (thanks to the random player, see Algorithm 2). -Growth of the tree: add L in T.

-Update statistics in the entire tree: In UCT, we have to store in each node how many simulations and how many winning simulations have been performed from this node. In other forms of tree search, some more information is necessary; for example, the Bandit Algorithm for Smooth Trees (BAST) algorithm [START_REF] Coquelin | Bandit algorithms for tree search[END_REF] needs more general information on the size of the tree, and "AMAF-variants" of MCTS (discussed later and presented in [START_REF] Gelly | Combining online and offline knowledge in UCT[END_REF]) need some more subtle statistics on past simulations. End while Return the move which has been simulated most often from the root Various formulas exist for choosing compromises between exploration and exploitation. This work defines the (1) Upper Confidence Bound (UCB) formula, (2) AMAF values (or RAVE values), [START_REF] Chellapilla | Evolving neural networks to play checkers without expert knowledge[END_REF] Heuristic values, and (4) Progressive unpruning (or Progressive widening), as follows.

1) UCB formula

The most classical formula for choosing compromises between exploration and exploitation is the UCB formula [36][37]. This formula provides a score for each possible move; the move with the highest score is simulated. The score of a move m is the sum of the frequency of simulations won among all simulations starting with move m and a confidence term

+ + = (1)
where c is an ad hoc constant, sims(s, m) is the number of simulations starting at s with first move m, and sims(s) is the total number of simulations starting at s. This work then simulates the move with a maximal score (see Algorithm 3). Some variants of UCB, e.g., UCB-tuned [START_REF] Audibert | Use of variance estimation in the multi-armed bandit problem[END_REF], have been proposed and scholars have believed that the UCB formula is key to a successful MCTS. However, in most cases (as in the case of MoGo, as RAVE values are used), using c=0, which is surprising, is the best choice, at least when frequency is regularized by, for example, (number of wins + K1) / (number of simulations + K2) for some ad hoc constants, K1 > 0 and K2 > 0, where K1 and K2 are absolute, and do not depend on the node. No optimized programs exist in which c>0 provides significant improvements. We believe c>0 is only suitable for preliminary implementations without RAVE values, without progressive widening, without heuristic values learned from datasets, and without tuning constants. Moreover, in some cases discussed in personal communications, the authors of effective programs with c>0 have admitted that the advantage of c>0 was unclear. On the other hand, the fact that the constant c is zero has been debated on mailing lists, but never stated clearly is studies. In fact, many studies still claim that UCT is used in MCTS, whereas in MoGo, a modified UCT, namely, c=0, is used. UCB has however been quite useful for understanding the algorithm.

We could see that the exploration constant c>0 was useful in early versions of MoGo whereas it became useless when heuristics were added. By empirically tuning the constant c to 0, we made tree search in computer Go essentially a best-first search (see however the discussion of optimism in front of uncertainty in Section III.B).

When UCB is used, MCTS is called an Upper-Confidence Tree (UCT) [START_REF] Kocsis | Bandit-based Monte-Carlo planning[END_REF]. Interestingly, some significant improvements in chess have been achieved with "forced moves" [START_REF] Anantharaman | Singular extensions: adding selectivity to brute-force searching[END_REF]. Forced moves are moves that are almost mandatory for a player. A combination is a sequence of such moves when an opponent can only play forced moves. Via forced moves, one can increase analysis depth. In chess, according to some scholars, this technique is efficient and programs with forced moves can announce checkmate and victory far in advance. In computer Go, forced moves are a difficult concept. Cazenave [START_REF] Cazenave | Metaprogramming forced moves[END_REF] produced notable results using forced moves; however, forced moves are only forced in the sense that they are necessary for some particular goal, not for complete victory. In Go, strong players never try to keep some group alive. If the opponent can use many stones to kill one group, letting the opponent reach his target is fine, as during that time, influence is extended to another part of the goban, increasing the amount of territory won. Via the MCTS approach, very deep sequences can be produced, allowing computer Go to reach the same complexity as computer chess despite a lack of forced moves.

2) AMAF values

The bandit algorithm, which is based on AMAF, was developed by [START_REF] Gelly | Combining online and offline knowledge in UCT[END_REF]. Generally, the first statistic, AMAF, is created by permutations of moves in simulations. If a move is often in a winning simulation, it will be considered a possible move. Therefore, the proportion of won simulations in simulations containing move X is a criterion for analyzing move X, as well as the proportion of won simulations in simulations with X as a starting move. The second statistic is clearly better asymptotically than the first one because it is based on real simulated games; however, the AMAF statistic is relatively much faster. It is much faster because for each simulation, many AMAF simulations (namely, all simulations obtained from the real simulation by permutation of one move with the first move 1 ) exist; that is, all simulations obtained from a real simulation after exchanging the first move with another move of the same player later in the simulation. The score for one move m is then a weighted average of the ratio of won simulations (estimated in simulations starting with move m) and the ratio of won AMAF simulations (i.e., simulations in which move m occurs for the same player before occuring for the other player). The score for one move m is formally defined as Eq. ( 2):

Score(move m, situation s) = α×ratio of won simulations + (1-α)× ratio of won AMAF simulations [START_REF] Lucas | Computational intelligence and games: challenges and opportunities[END_REF] where weight α increases toward 1 as the number of simulations starting at s with move m moves toward infinity and is small for a small number of simulations. The move chosen for simulations is the move with the maximum score (see Algorithm 3).

3) Heuristic values

Adding a term based on the patterns and rules to the scores computed above was proposed by [START_REF] Bouzy | Bayesian generation and integration of knearest-neighbor patterns for 19 × 19 Go[END_REF][29] [START_REF] Chatriot | Including expert knowledge in bandit-based Monte-Carlo planning with application to Computer Go[END_REF]. Typically, a value is proportional to the frequency of a move m in a pattern p according to a database, plus a coefficient tuned empirically for moves matching some expert rules. The main rules in MoGo are such classical rules as (1) avoidance of big self-atari, (2) avoidance of empty triangles, (

territory lines, (4) walls, and (5) connect. Other rules implemented in MoGo can be found in [START_REF] Chatriot | Including expert knowledge in bandit-based Monte-Carlo planning with application to Computer Go[END_REF]. The website (http://senseis.xmp.net) provides the Go definitions required for implementing these rules.

4) Progressive unpruning

Progressive widening [START_REF] Coulom | Computing elo ratings of move patterns in the game of Go[END_REF] and progressive unpruning [START_REF] Chaslot | Progressive strategies for Monte-Carlo tree search[END_REF] improve Algorithm 3, which considers only the K(n) "best" moves according to some heuristic at the n-th simulation in a given node, for some 1 Only moves of the same color are permuted. See [START_REF] Gelly | Combining online and offline knowledge in UCT[END_REF] for a detailed description of the AMAF method in a Monte-Carlo Tree Search (MCTS).

non-decreasing mapping K(n). The decision to be simulated is that with a maximum score among K(n) moves. However, when AMAF values are implemented, this improvement to Algorithm 3 is minor.

III. The Mechanism of MoGo

This section presents the Monte Carlo player used in MoGo in subsection A, and the formulas for biasing the Monte Carlo simulator, i.e., the bandit formula, also known as the compromise between exploration and exploitation, in subsection B. Subsection C discusses the parallelization of MoGo.

A. The Monte Carlo player

The Monte Carlo player is defined in Algorithm 2. An atari occurs when a string representing a group of stones can be captured in one move. Some Go knowledge, such as 3 × 3 hand-crafted patterns, has been added to play meaningful games [START_REF] Wang | Modifications of UCT and sequence-like simulations for Monte-Carlo Go[END_REF].

Algorithm 2: Algorithm for choosing a move in Monte Carlo simulations for the game of Go. Some details have been omitted for clarity; see [START_REF] Chatriot | Including expert knowledge in bandit-based Monte-Carlo planning with application to Computer Go[END_REF] for details (in particular the "Nakade" modification

B. Compromise between exploration and exploitation in MoGo

Combining various scores is classical in computer Go. Some studies have combined offline learning with statistics obtained from professional games and online learning with bandit choosing moves [START_REF] Bouzy | Bayesian generation and integration of knearest-neighbor patterns for 19 × 19 Go[END_REF] [START_REF] Coulom | Computing elo ratings of move patterns in the game of Go[END_REF].

Gelly and Silver, who combined online learning with bandit choice and "transient" learning using AMAF values [START_REF] Gelly | Combining online and offline knowledge in UCT[END_REF], experimented with the use of off-line learning, i.e., a heuristic value. However, offline learning using Reinforcement Learning and Computer Go (RLGo) was later removed from MoGo as improvement was minor and even negative after tuning. In the current version of MoGo, improvements have been achieved by combining the following: The compromise between these values is as follows:

for a small number of simulations, off-line knowledge is extremely important; -for a high number of simulations, transient learning RAVE values becomes essential; -after additional simulations, the "standard" statistics, ratio of won simulations, become the most important term.

Algorithm 3 presents the detailed pseudo-code for the compromise between exploration and exploitation in MoGo. Notably, α+ β+ γ >1, but converges to 1 (equivalent to 1/log(number of simulations of this move)) as the number of simulations goes to infinity. Therefore, values of α+ β+ γ >1 can be used for moves that are moderately explored-this ensures diversity and it is the only part of MoGo which has such a diversity criterion, i.e. it is the only part which is not a completely best-first approach. This is a form of optimism in front of uncertainty for the values of unvisited nodes.

Algorithm 3: Algorithm for choosing a move in the tree, for a two-player game with binary reward (extensions to arbitrary distributions are straightforward). sims(s, m) (resp. wins(s, m)) is the number of simulations (resp. won simulations) in which move m has been chosen in situation s. The total number of simulations at situation s is sims(s) = sims(s, m 1 ) + sims(s, m 2 ) + … + sims(s, m n ) where m i 's are the possible moves. The prefix "amaf" holds for statistics on AMAF-simulations instead of standard simulations (see section II.B.2). For each simulation with moves m 1 , m 2 , …, m k , we consider the corresponding AMAF-simulations: in the i-th AMAF-simulation associated to this simulation, m 1 is replaced by m i (for i odd, as both stones must be of the same color). Function decision = Bandit(situation s in the tree). For m in the set of possible decisions do p1(m, s) = wins(s, m) / sims(s, m) p2(m, s) = amaf-wins(s, m) / amaf-sims(s, m) p3(m, s) = heuristic value of m in situation s.

Score(m,s) = α×p1(m, s) + β× p2(m, s) + γ×p3(m, s), where -α goes to 1 as sims(s, m) goes to infinity (and α negligible for sims(s,m) small) :

-β is negligible for sims(s,m) small, and then increases, and later (for sims(s,m) large) goes to 0;

-γ starts at a value >1 and then decreases to 0 as sims(s, m) goes to infinity; Decision = argmax d Score(s, m) End for

C. Parallelization in MoGo

Parallelization of MoGo is described in detail in [START_REF] Gelly | The parallelization of Monte-Carlo planning[END_REF]. Essentially, two types of parallelization exist.

-Multicore parallelization for shared memory, which exists in most MCTS implementations.

Basically, this parallelization runs simulations independently on each core of a machine, and each core updates the same tree T.

-Message-passing parallelization without shared memory. This parallelization has one MCTS working independently on each computation node. At a frequency of 3Hz, all computation nodes merge their trees as follows:

(1) all nodes of all the trees with > 5% of the total number of simulations at a depth < 10 are shared (only those nodes);

(2) for each shared node, all statistics for win/loss/AMAF-win/AMAF-loss are averaged among all computation nodes.

Message-passing parallelization is presented in the Appendix (Fig. A3).

IV. Game Results of MoGo Playing Against Human Players in Taiwan

This study constructed a platform for the GO games held at NUTN, Taiwan, from August 26 to October

A. Comments on the 9× 9 games

Games Nos. 15 and 16 were very interesting 9 × 9 games. In these two games, MoGo played against Zhou (the 9P Go player). Figures 1 and2 show the boards for these two 9 × 9 games, respectively.

According to the comments of Tsai and Zhou, game No. 15, shown in Fig. 1, was worth studying because MoGo had a chance to win. However, MoGo was tricked by Zhou with White 20 and lost the game. Zhou analyzed that if time per side was extended, then MoGo would have taken the advantage. Figure 3 indicates that the probability of playing a good move (E9) instead of one of the two bad moves exceeded 50% after 5 minutes × computation cores, which quickly reached parallelization. The probability of playing D8, E2 or E9 depends on computational effort. Bad moves D8 and E2 are likely to be played when MoGo has little time, and the probability of playing E9 increases as computational effort increases. The 9 × 9 Go game is the first field to which MCTS methods have been applied. However, game results for MoGo in Taiwan

were not good against top-level human players; MoGo lost most of its 9 × 9 games-two games against Zhou and three games against Luoh. Additionally, the first game against Zhou was difficult. The professional player predicted during the game that MoGo was likely to win prior to its big mistake (see Fig. 1). Nonetheless, MoGo won one of two games against 6D Tsai. Figures 4 and5 show the outcomes of games Nos. 3 and No. 4, respectively. Figure 6 shows the outcome of game No. 10. Result:

The 9× 9 game was played against Zhou (9P). MoGo was black and lost the game. The komi was 6.5, whereas MoGo had hard-coded the first moves for komi 7.5.

Comments by Tsai: MoGo was black. A good move was 20 for White (Zhou). Black answered with 21 E2, whereas E9 would have resulted in a win for black.

Comments from Luoh: MoGo could have played C3 as a reply to D2. A posteriori analysis by MoGo of the situation after move 20:

(1) MoGo inferred that it was likely to win with move E9 (65% probability of winning, estimated after a few seconds). (2) MoGo did not see clearly that E2 was a bad move (MoGo computed the probability of winning for a moment and generated an estimation of roughly 50%). ( 3) MoGo was likely to play good move E9, but could also play moves D8 (a loosing move) or E2. The probability of a good move increases as computational effort increases (Fig. 3). In many cases, MoGo simulated the 50% bad move for a long time, and did not explore the good moves sufficiently such that it converged to 65%. However, if MoGo is forced to spend 50% of its time on each move, it will choose the good move. By forcing MoGo to consider both moves is not a solution for the general case because deciding which moves should be considered is difficult.

Result:

The 9× 9 game was played against Zhou (9P).

MoGo was white and lost the game. The komi was 6.5, whereas MoGo had hard-coded the first moves for komi 7.5.

Comments by Tsai: White (MoGo) played a bad move, move 16 (C5).

A posteriori analysis by MoGo of the situation before move 16 (C5): With limited time per move, MoGo was likely to play bad move C5 with 50% probability of winning, and played G6 based on the other 50% probability. Interestingly, MoGo, when playing C5, was aware that this move did not lead to a good situation. However, it did not find a move with a relatively better probability of winning. Some methods, such as "distributing computational power over several moves" (e.g., parallelization in which the first move is fixed and different for each node) when the situation seems very good may be a good idea; however, this idea has not been implemented. Moreover, Kim stated that MoGo would likely win with only 8 handicap stones. Although humans also improve over time, the game results (Table V) show that the human improvement is not as significant as that for computers. However, humans can spend a long time on particular moves, whereas the MCTS Interestingly, the same situation occurs in games in which MoGo has an advantage (see comments for the first 9 × 9 game lost against Zhou, shown in Fig. 1). This is illustrated by the successes of MoGo in non-handicapped games (Figs. [START_REF] Chen | Maximizing the chance of winning in searching Go game trees[END_REF][START_REF] Anantharaman | Singular extensions: adding selectivity to brute-force searching[END_REF][START_REF] Müller | Computer Go[END_REF], and by statistics given in Section IV.C.

Result: Game against Tsai (6D), with 5 handicap stones. MoGo was Black and lost the game.

Comments by Tsai: In this game, Black (MoGo) made a mistake on the right upper corner so that Black lost the game. After playing with Black for some games, Tsai thought that Black had made such a mistake many times. This was not a good move. A useful solution for MoGo in handicapped games is to avoid corner trouble. The first moves can be hard coded to ensure nothing occurs in corners. Figure 12(a) presents defensive moves for black in corners when the handicap is seven stones. Thus, black plays defensive moves to ensure that two corners will remain black, and does not try to protect the other two corners. This solution, however, is ad hoc and based on human expertise. Of course, a solution based on deep improvements in the MCTS would be more elegant. Cases of poor behavior by MoGo in corners often involve "semeai," which are very common in corners. However, such a "semeai" can be simulated in an artificial situation, shown in Fig. 12(b). Figure • Likelihood = (3/4) 2A /2 if A<0.

The level of MoGo can then be determined by maximizing overall likelihood, i.e., the product of all likelihoods. Confidence intervals can be given that consider values with likelihoods that are at least half of maximum likelihood. The result is shown below.

(1) The level of MoGo in all games was slightly less than 2D (1.6D) and it differs depending on the machine used by MoGo:

-Games played by the R900 machine (16 cores; 3GHz): 2.5D (confidence interval, 1.7-3.3), -Games played by the Huygens cluster: 1.7D (confidence interval, 0.8-2.7).

This is quite surprising at first view, as the Huygens cluster is a powerful machine and its acceleration is very good. The Huygens machine was used in games against Zhou and 6D players, who had a large number of handicap stones; thus, the Huygens machine performed poorly. This can be contrasted with the fact that the R900 machine was tested against 1-4D players. This introduces a bias that exceeds computational power. In particular, strong players always defeat MoGo in corners regardless of the handicap; this cannot be solved by increasing computational power.

(2) The level of MoGo in games with at most 4 handicap stones (MCTS algorithms do not handle handicaps properly) was 5D (5.3D; confidence interval, 3.8-7.8). This is surely too high as an estimate.

The game MoGo won against a 4D player involved large fights, a situation that favored MoGo.

Additionally, MoGo may have lost in other situations-changing just one game has a significant impact on the estimate as the number of games was small.

We conclude that the level of MoGo is estimated at 2-3D. Additionally, MoGo has (1) good fighting skills, (2) weaknesses in corners (especially in semeai situations) and (3) weaknesses in favorable situations such as in handicapped games.

V. Discussion and Conclusion

In this study, the advances in computational intelligence of MoGo are revealed from Taiwan's computer Go tournaments. in contact fights; this finding is not based on statistics, but rather the unanimity among human players. This set of games is the largest set of games MoGo has played against human players with levels validated by the Go federation. Confidence intervals were used in this study: confidence intervals are built with a likelihood ratio of 0.5. Finally, according to the comments made by the Go players against MoGo in Taiwan's computer Go Tournaments, MoGo is roughly 1P professional and 2-3D amateur for 9 × 9 and 19 × 19 games on the Taiwanese scale, respectively. However, it is hoped and expected that thanks to future advances in artificial intelligence and computational power, the field of computer Go will progress in the future. Possibly, trying to combine the expert knowledge such as ontology [32][33] with the MCTS [34][35] is a way to improve the performance of MoGo.

7. When a game is nearly over, if a Go player recognizes that MoGo is protecting its territory, MoGo likely wins. Conversely, if a Go player is aware that MoGo is playing abnormally, such as when it makes poor moves, the Go player likely wins. 8. Generally, MoGo is weak at the start of a game, and becomes stronger as the game progresses. 9. MoGo may not fully understand the problems in a ko fight. A ko fight may have some complicated math problems. Each computation node builds his own tree in memory, and 3 times per second all nodes "share" their tree with other nodes: all statistics are averaged, and thereafter all nodes have the same tree in memory, for the upper part (nodes with low number of simulations, i.e. less than 5% of the number of simulations of the root, or too deep in the tree, i.e. depth more than 10, are not shared).

computational power in the 19 ×

 19 [START_REF] Brügmann | Monte Carlo Go[END_REF] Go game, as they can use supercomputers. This study focuses on the invited games played in the tournament, "Taiwanese Go players versus the computer program, MoGo," held at NUTN, Taiwan. Several Taiwanese Go players, including one 9P Go player and eight amateur players, ranging from 1 Dan (1D) to 6D, were invited by NUTN to play against MoGo from August 26 to October 4, 2008. In particular, Jun-Xun Zhou, a 9P Go player, played 9 × 9 and 19 × 19 games against MoGo running on a supercomputer with 800 CPUs, through the Kiseido Go Server (KGS) on September 27, 2008. Zhou, the strongest Go player in Taiwan, won the 2007 World LG Cup. MoGo lost three games to Zhou, including two 9 × 9 games and one 19 × 19 game with 7 handicap stones. MoGo had a very favorable situation in the first 9 × 9 game, but made a significant mistake and lost. The invited eight amateur Go players included a retired professor of NUTN (C. W. Dong, 70 years old, 5D), a Chief Information Officer (CIO) of a software company (C. S. Chang, 50 years old, 6D), the Chief Referee of this championship (S. R. Tsai, 55 years old, 6D), two teachers of Tainan's Go Association (B. S. Luoh, 45 years old, 6D; and W. T. Yu, 50 years old, 3D), and three child members of Tainan's Go Association (Y. S. Huang, 12 years old, 4D; Y. X. Wang, 11 years old, 3D; and S. Y. Tang, 10 years old, 2D). Tournament results indicate that MoGo was roughly 2-3D for 19 × 19 games and roughly 1P professional for 9 × 9 games on the Taiwanese scale. The remainder of this study is organized as follows. Section II briefly describes recent advances in computer Go. The mechanism of MoGo is presented in Section III. The game results of MoGo playing against humans in Taiwan are presented in Section IV. Discussions and conclusions are given in Section V. Finally, comments and properties of MoGo in the Taiwanese tournament are presented in the Appendix.

-

  on-line learning, i.e., statistics such as those in a UCT, but with c = 0 (Section II.B.1); -transient learning, i.e., AMAF values (Section II.B.2); -off-line knowledge, i.e., expert rules and statistics in a database (Section II.B.3); -progressive unpruning (small improvement).

Fig. 1 Fig. 3 1 )

 131 Fig. 1 Game No. 15. Fig. 2 Game No. 16.

Fig. 8

 8 Game No. 21. Result: Game against Yu (3D), without handicap stones. MoGo was White and won the game. Fig. 9 Game No. 18. Result: Game against Huang (4D), without handicap stones. MoGo was Black and won the game. MoGo successfully attacked the white Q4 group and therefore managed to win the game. Fig. 10 Game No. 22. Result: Game against Wang (3D), without handicap stones. MoGo was Black. Fig. 11 Game No. 23.

  12 (b) is an extreme case of a very simple situation in which MoGo poorly evaluates the situation. As white, MoGo played a move that captured three stones in the upper part of Fig.12(b), whereas it should have played in the very large "semeai" in the lower part which decides the winner. The "semeai" situation is very simple for humans, but involves much more different reasoning than other Go situations. That is, one must count "liberties" (free locations around groups)-this is obvious for a Go player but not for a Monte Carlo algorithm. The MoGo is not equipped with such intelligence, and is not encoded in any computer (this study tested without success several available programs). (a) (b) Fig. 12 (a) Defensive moves for black in the corners with 7 handicap stones. (b) Artificial "semeai" situation: here the random player cannot play the right sequence and therefore estimates the probability of winning the semeai at 50% independently of the first moves. 4) Strength of MoGo in contact fights Notably, MCTS algorithms are very effective in local fights (see Figs. 13-15). Result: Game against Tsai (6D), with 5 handicap stones. MoGo was Black and won the game. Comments by Tsai: Originally, White (Tsai) should have had a great chance to win in the middle of the game. When White played 142 to attempt to break into Black's territory, Black played 143 and 145 to cut White's stones. Meanwhile, White made another mistake. That is, White played a bad move at 146. If White had played 146 at G8 instead of H7, White would have successfully intruded into Black's territory to get more than 10 points. From the board of this game, Tsai said that MoGo had a good performance on the contact fight. In spite of the fact that Black (MoGo) also lost some points at the corners in this game, White ended up losing the game because of this vital mistake. Another key point of this game was the ko fight at 156 and 157. From the result of ko fight, Black also performed ko fight well in this game. Fig. 13 Game No. 13.

4

 4 Fig.A3One step of sharing in the MPI-parallelization of MoGo. Each computation node builds his own tree in memory, and 3 times per second all nodes "share" their tree with other nodes: all statistics are averaged, and thereafter all nodes have the same tree in memory, for the upper part (nodes with low number of simulations, i.e. less than 5% of the number of simulations of the root, or too deep in the tree, i.e. depth more than 10, are not shared).

  4, 2008 (http://go.nutn.edu.tw/). TableIlists the profiles of all Go players who competed against MoGo. NCF). The MoGo program was allowed to use at most 25 of the 104 nodes of the supercomputer, i.e., 800 cores at 4.7GHz, with a floating point processing power of 15 Teraflop (>1000 times that of Deep Blue). The game was played over the KGS Go server platform when MoGo was run on the Huygens cluster with different numbers of cores. Go teacher and 6D amateur, and Tsai, the chief referee of the tournament and a 6D amateur, were invited to comment on game results. Their comments on the 9 × 9 and 19 × 19 games are provided in the next two subsections, respectively.

	Table II lists the Chinese rule adopted and related game parameters. During the tournament, MoGo ran on a Dell PowerEdge R900 machine with 16 cores and supercomputer "Huygens," which was provided by Dutch research organizations, Stichting Academisch Rekencentrum Amsterdam (SARA) and National Title Name Age Sex Dan grade Mr. Jun-Xun Zhou 28 Male 9P Professional Mr. Biing-Shiun Luoh 45 Male 6D Amateur Prof. Shang-Rong Tsai 55 Male 6D Amateur Mr. Cheng-Shu Chang 50 Male 6D Amateur Prof. Cheng-Wen Dong 70 Male 5D Amateur Child Yu-Shu Huang 12 Female 4D Amateur Child Yu-Xin Wang 11 Male 3D Amateur Mr. Wen-Tong Yu 50 Male 3D Amateur Child Sheng-Yu Tang 10 Male 2D Amateur Computer Facilities (Table I. Profiles of all the Go players competing with MoGo. Table II. Parameters of the game. Game Board Komi Time per side (min) 9× 9 7.5 unless otherwise stated (some games with Komi 6.5) 30 19× 19 7.5 45

Tables III and IV list the information related to the 9 × 9 and 19 × 19 game results MoGo played against nine Taiwanese Go players, respectively. All Smart Go Format (SGF) files of the game records (Tables

III and IV

) are available on the website, (http://go.nutn.edu.tw/eng/result_eng.htm). In Tables

III and IV

, the first column shows the game number and the second column lists MoGo performance. Performance is represented by XD+ or XDwith X = L -H, where L is the rank of a player and H is the handicap level.

When MoGo won, its performance was XD+; otherwise, its performance was XD-. The level Xkyu corresponds to -(X-1) Dan. As the Dan number increases, player proficiency increases. The 9P player Zhou (9D on the pro scale) is assumed equivalent to a 10D player (10D on the amateur scale). Luoh, a

Table III .

 III Related information about results of the 9× 9 games that MoGo played against humans in the tournament.

	No Performance Date 1 9 × 9 5D+ 08/26/2008 9 × 9 Setup 3 9 × 9 6D+ 08/26/2008 9 × 9 4 9 × 9 6D-08/26/2008 9 × 9 10 9 × 9 6D-09/25/2008 9 × 9 11 9 × 9 6D-09/25/2008 9 × 9 15 9 × 9 10D-09/27/2008 9 × 9 16 9 × 9 10D-09/27/2008 9 × 9 24 9 × 9 2D+ 10/04/2008 9 × 9	Environment Huygens with 150CPUs MoGo Dong White Black Huygens with 150CPUs Tsai MoGo B+Resign Result W+0.5 Huygens with 150CPUs MoGo Luoh B+Resign Huygens with 320CPUs Luoh MoGo W+Resign Huygens with 320CPUs MoGo Luoh B+Resign Huygens with 800CPUs Zhou MoGo W+Resign Huygens with 800CPUs MoGo Zhou B+Resign R900 machine Tang MoGo B+0.5

Table IV .

 IV Related information about results of the 19× 19 games that MoGo played against humans in the tournament.

	23 3D+	10/04/2008 19 × 19	R900 machine	Wang	MoGo B+2.5
	No Performance Date 2 1kyu+ 08/26/2008 19 × 19 H5 Huygens with 150CPUs Dong Setup Environment White 5 2 kyu+ 09/24/2008 19 × 19 H6 R900 machine Dong 6 1D+ 09/24/2008 19 × 19 H4 R900 machine Dong 7 1D+ 09/25/2008 19 × 19 H4 R900 machine Dong 8 1D+ 09/25/2008 19 × 19 H4 R900 machine Dong 9 1D+ 09/25/2008 19 × 19 H4 R900 machine Dong 12 2D-09/25/2008 19 × 19 H4 Huygens with 320CPUs Luoh 13 1D+ 09/27/2008 19 × 19 H5 Huygens with 480CPUs Tsai 14 1D+ 09/27/2008 19 × 19 H5 Huygens with 480CPUs Chang 17 3D-09/27/2008 19 × 19 H7 Huygens with 800CPUs Zhou 18 3D+ 10/02/2008 19 × 19 R900 machine MoGo Yu Black MoGo B+0.5 Result MoGo B+Resign MoGo B+Resign MoGo B+Resign MoGo B+Resign MoGo B+0.5 MoGo W+Resign MoGo B+1.5 MoGo B+1.5 MoGo W+Resign W+11.5 19 2D+ 10/02/2008 19 × 19 H4 R900 machine Luoh MoGo B+7.5 20 1D-10/03/2008 19 × 19 H5 R900 machine Tsai MoGo W+Resign 21 1D-10/03/2008 19 × 19 H5 R900 machine Tsai MoGo W+Resign 22 4D+ 10/04/2008 19 × 19 R900 machine Huang MoGo B+0.5

  The MoGo program combines AMAF/RAVE values, online values, offline values extracted from databases, and expert rules. These techniques have three-level learning, including offline learning from a dataset, online learning with the MCTS, and transient learning with AMAF/RAVE values. In the game results in the tournament it appears that MCTS does not properly handle semeai situations. That is, the counter example-the very simple semeai for which MoGo cannot find a good answer-is a very clear example of the weakness of MCTS in Go. This is an important open problem, which is now being addressed and paid considerable attention. Additionally, the difference in levels depending on whether one considers handicapped games or non-handicapped games is highly significant -almost all games with a low handicap generate better results than almost all handicapped games.From the game results, it is known that the level of MoGo was poorly estimated for 9 × 9 games; that is, changing the outcome of just one game strongly changes the overall outcome. The situation is slightly better for 19 × 19 games, including handicapped games, but still very imprecise for 19 × 19 games without handicaps, as changing the outcome of just one game markedly changes the estimated level. Despite these limitations due to a finite set of games, the following conclusions are held. (1) MoGo is weak in semeai situations. This is validated by human players and a very clear artificial semeai not solved by MoGo, which can be solved by a Go beginner. (2) MoGo is the strongest in games without handicaps. (3) MoGo is strong

Acknowledgements

The authors would like to thank the National Science Council of Taiwan for financially supporting this research under the grant NSC97-2221-E-024-011-MY2 and the Pascal Network of Excellence for its support. Additionally, the authors would like to thank the support of Professor Hsiu-Shuang Huang (President of National University of Tainan, Taiwan), the Computer Center of National University of Tainan, especially Mr. Yuan-Liang Wang & Miss Meng-Chun Wang, and the Tainan Go Association, especially Mr. Biing-Shiun Luoh. Finally, the authors would also like to thank the anonymous referees and Professor Simon Lucas for their constructive and valuable comments.

programs typically spend the same amount of time on each move. Criteria for determining when to increase the time spent on a move are needed. Result: Game against Zhou (9P), with 7 handicap stones. MoGo was Black and lost the game.

Comments by Tsai: This game was a bad game which MoGo played in this championship. White (Zhou) profited from the four corners which meant that MoGo might not be good at processing the corners in the game. So, White quickly won the game after Black (MoGo) lost points at the four corners. Fig. 7 Game No. 17.

3) MoGo in handicapped games

MoGo, like other MCTS algorithms, is based on best-first searching. Hence, at the start of games with high handicaps, MoGo only studies a few moves and keeps simulating each move to ensure they keep the probability of winning high. As all moves have a high probability of winning at the start of a game, based on underlying assumption of equal strength between two players (an essential assumption in MCTS algorithms), MoGo keeps simulating only initial moves. Consequently, MoGo plays its first moves almost randomly. This is in contrast with the case of an equilibrated situation without a handicap, in which MoGo will spend considerable time on various moves until it finds a move with a high probability of winning.

Result: Game against Luoh (6D), with 4 handicap stones. MoGo was Black and lost the game.

Comments by Tsai: Black (MoGo) played well in the beginning of the game, but made big mistakes at the end of the game. The key point of this game was at the fight located at the left side. Most of the time, Black played reasonable moves, but critical mistakes, such as Black 68, caused Black to lose the game. Anyway, Black had a good performance in this game. Fig. 14 Game No. 12.

Result: Game against Luoh (6D), with 4 handicap stones. MoGo was Black and won the game.

Comments by Luoh: Black (MoGo) played the locally optimal move when White (Luoh) played 25, which caused White to play in a difficult situation later. Therefore, Black won the game. From the result of this game, Luoh said that Black could not only detect the locally optimal move but also had a strong center territory performance. But, Black performed poorly in managing the edges and corners of the board (this point is further developed in section IV.B.1). Fig. 15 Game No. [START_REF] Brügmann | Monte Carlo Go[END_REF].

C. Numerical analysis of performance

A classical formula for likelihood used in the Internet Go Server (IGS) rating system (http://www.pandanet.co.jp/English/ratingsystem/) estimates the level of players by likelihood maximization, which is based on the following formulas. The probability of losing against the L Dan player with a handicap of H stones, if one's level is B, is estimated by evaluating the following:

• Effective advantage of opponent A = L-H-B; He has published more than 300 research papers in international/national journals and conferences and has planned more than fifty information systems. He is also the board member of more than ten journals and the program committee member of more than sixty conferences. His current research interests include parallel processing, machine learning, data mining, soft computing, management information systems, and www applications.

Dr. Hong is a member of the Association for Computing Machinery, the IEEE, the Chinese Fuzzy Systems Association, the Taiwanese Association for Artificial Intelligence, and the Institute of Information and Computing Machinery.

Appendix. Comments of Games for MoGo in Taiwan

In this appendix, some comments made by five Go players against MoGo in Taiwan's Computer Go Nonetheless, MoGo won all the games against 5D Dong shown in Fig. A1. Based on Go players' dan grade, the statistics in the game results are also presented in Fig. A2. Figure A2 shows that MoGo won most games when the Go players are ranked from 2D to 5D and the handicap has not changed the fact that the game results are much better for level lower than 5D. Thus, MoGo should be with the quite level of rank. 5. The ability of MoGo to fight and attack is acceptable; however, MoGo typically makes sacrificial plays. That is, MoGo typically loses more points than it gains after a fight or attack. 6. For 9× 9 games, MoGo has reached the level of professional and is a good tool for players practicing fight and attack strategies. 7. When MoGo cannot kill its opponent, it surrounds the territory and makes sacrificial moves to achieve its goal. In some cases, after a fight or attack, the points MoGo loses exceed those it gains. 8. The time to play for each side is key to MoGo victory. Compared with human Go players, MoGo needs more time to compensate for its weak rank. 3

Prof. Tsai (6D) 1. The ranking of MoGo is unstable; that is, MoGo in the best case is a 3D player, and in other cases a 1D player. Thus, the average rank of MoGo is roughly 2D. 2. The performance of MoGo was beyond the expectations of Tsai. He was also surprised that MoGo can respond to most reasonable moves. 3. MoGo has the ability to identify the weaknesses of its opponent and gain points. 4. In the latter half of a game, MoGo can surround a territory. 5. The number of poor moves by MoGo is significantly less than that by the computer Go program. 6. At the start of a game, MoGo often loses points fighting in corners.