25 Study on Effectiveness of Monte Calro Tree Search for Single-Player Games

Size: px

Start display at page:

Download "25 Study on Effectiveness of Monte Calro Tree Search for Single-Player Games"

きみかずなつ
5 years ago
Views:

1 25 Study on Effectiveness of Monte Calro Tree Search for Single-Player Games

2 ,,, i

3 Abstract Study on Effectiveness of Monte Calro Tree Search for Single-Player Games Norimasa NASU Currently, Monte-carlo tree search has been actively studied for two-person games. Monte-carlo tree search took much attention after the first application to the igo player. However, there are few studies on monte-carlo tree search applied to one-person games. For some one-player games we cannot perform complete-search due to their very broad search space. An efficient search algorithm is needed to solve those problems with broach search space. In this study, we apply the monte-carlo tree search to one player games and verified the effectiveness. We use two problems for experiments: the knapsack problem and generation of Sudoku problems. The performance of monte-carlo tree search is compared with that of the genetic algorithm. The experiment results show the following facts. Firstly, the monte-carlo tree search gives a rather good solution immediately after the start. Secondly, the accuracy of the solution is hard to rise. Thirdly, the reason is that many playouts are done on a node that does not give an optimal solution. key words Monte-carlo tree search, Genetic algorithm, Sudoku, Knapsack problem ii

4 SAT iii

5 iv

6 SAT n = n = n = v

7 6.4 n = n = vi

8 MCT GA vii

9 1 1.1 [2] [14] [11] [14] 1

10 [11] ( ) [13] Samegame Schadd Takes [7] [8]

11 2 2.1 [10]

2.2 2.1 2.2 2.1 1 SAT 2.2.1 Cell-Unique x x a 1 x a Line-Unique Block-Unique a x 1 x a k-naked k x 1, x 2,..., x k k a 1, a 2,.

12 SAT Cell-Unique x x a 1 x a Line-Unique Block-Unique a x 1 x a k-naked k x 1, x 2,..., x k k a 1, a 2,..., a k x 1, x 2,..., x k a 1, a 2,..., a k k-hidden k a 1, a 2,..., a k x 1, x 2,..., x k k x 1, x 2,..., x k a 1, a 2,..., a k 4

13 2.2 solve(board) { cnf <- CNFOfBaseRule cnf <- append(cnf, tocnf(board)) if (satisfiable(cnf)) { answer = findanswer(cnf) cnf2 <- append(cnf, negate(answer)) if (satisfiable(cnf2)) { return multiple else { return unique else { return noanswer 2.3 SAT SAT SAT CNF CNF [5] 2.1 CNF SAT CNF CNF CNF [5] extended encoding 1 1 CNF SAT CNF no_answer CNF 1 CNF CNF SAT multiple unique 5

14 2.3 makeboard() { loop until board $n$ { board <- sethint(board) if(solve(board) ){ board <- board else if(solve(board) ){ return board; sethint 1 1 solve SAT solve 6

15 2.3 multiple no_answer unique 7

16 3 [3] [6] m n i C i j w j v j 1 1 m = 2 C 0 = 10, C 1 = 15 3 k i C i k 0 = {0, 1, 4 k 1 = {2, 3, 5, j w j v j

17 4 4.1 [2]

18 4.2 MCT(root) { loop until { leaf <- select_downwards(root) leaf.n <- leaf.n + 1 if (expand_cond(leaf)) { leaf <- expand(leaf).first_child board = playout(leaf.board) update_upwards(leaf, getvalue(board)) return select_best_child(root) select_downwards 2. expand_cond expand 3. playout 4. evaluate update_upwards 4.1 select_downwards expand_cond expand playout evaluate update_upwards 10

19 4.3 UCT [4] UCT UCB1 Upper Confidence Bound [1] Multi-armed bandit problem [12] X j j n j j n c ucb j = X j + c 2 log n n j (4.1) UCB1 4.1 UCB1 UCB1 UCB select_downwards expand_cond expand playout evaluate update_upwards UCB

20 4.3 playout(board) { loop until board.hint == $n$ { hint <- selecthint(board) board <- addhint(board, hint) if (solve(board ) == noanswer) { board <- deletecand(board, hint) else { board <- board return board 4.2 n selecthint solve deletecand addhint 1 n solve playout solve SAT n n n c v v = n 3 c (4.2) 12

21 4.4 playout(items, knapsack) { loop (infinity) { items <- getitemlist(items) if (items == empty) { break loop item <- selectitem(items ) knapsack_id <- selectknapsack(knapsack) knapsack <- additem(knapsack, knapsack_id, item) return bag.value UCB1 getitemlist) 1 (selectitem) (selectknapsack) (additem) 13

22 4.4 14

23 5 [9] evaluate 2. generate_next 3. 15

24 5.1 Genetic_Algorithm(first) { now <- first loop until { evaluate(now) next = generate_next(now) now <- next return max(now) 5.1 generate_next(population) { next <- null loop until next parent1, parent2 <- select_parent(popuration) if( ){ child1, child2 <- crossover(parent1, parent2) if( ){ child1, child2 <- mutation(child1, child2) next.add(child1, child2) else { next.add(parent1, parent2) return next select_parent 2 2 crossover mutation 2 16

25 evaluate 5.2 select_parent crossover mutation [9] i f i N i p i p i = f i N j=1 f j (5.1) N j=1 f j f i

26 [9] m 0 m 1 0 m n n n m 0 m 1 18

27 m , 2,

28 [ ]

29 , n n c 0 n 21

5.3 5.10 1 5.11 2 5.12 3 1 c 2 n c 5.8 5.9 7 5.12 1 1 1 5.

30 c 2 n c m 0 m [ ]

31 % 1 23

32 6 4 5 OS ubuntu CPU Intel Core 3.30GHz 8GB Java b03 MCT GA n = 17, 18, 19, 20 C

33 n MCT GA n = % 30% n =

34 n = 18 n = 19, 20 n = n = n m 3 C C 0 = 4n, C 1 = 5n, C 2 = 6n j j n 10 n n 5 2n 26

35 n MCT GA (-14) 2649(0) (-17) 6323(-10) (-131) 13029(-74) (-749) 17328(-169) (-905) 23511(-247) (-1585) 28575(-1159) C % 30% 1 n 50, 100, 150, 200, 250, (=10 ) n 6.2 n 200, 250,

36 n = n =

37 n = MCT GA n ( ) MCT GA (MCT ) (-27) (-251) (-501) (-172) (-1500) (-1824) 6.2 n 29

38 n UCB1 UCB1 30

39 7 2 UCB1 31

41 [1] P. Auer, N. Cesa-Bianchi, and P. Fischer: Finite-time Analysis of the Multiarmed Bandit Problem. Machine Learning, Vol. 47, No. 2 3, pp , [2] C. Browne, E. Powley, D. Whitehouse, S. Lucas, P. I. Cowling, P. Rohlfshagen, S. Tavener, D. Perez, S. Samothrakis, S. Colton: A Survey of Monte Carlo Tree Search Methods. IEEE Transactions on computional intelligence and AI in games, Vol. 4, No. 1, [3] H. Kellerer, U. Pferschy and D. Pisinger, Knapsack Problems, Springer, Berlin, [4] L. Kocsis, C. Szepesvári: Bandit Based Monte-Carlo Planning, 17th European Conference on Machine Learning (ECML 2006), Lecture Notes in Computer Science 4212, pp (2006). [5] I. Lynce, J. Ouaknine: Sudoku as a SAT problem. In Proceedings of 9th International Symposium on Artificial Intelligence and Mathematics, [6] S. Martello, P. Toth: Knapsack problems : algorithms and computer implementations, Wiley, Chichester, pp , [7] M. P. D. Schadd, M. H. M. Winands, M. J. W. Tak, J. W. H. M. Uiterwijk: Singleplayer Monte-Carlo tree search for SameGame. Journal Knowledge-Based Systems, Vol. 34, pp. 3 11, Elsevier, [8] F. W. Takes and W. A. Kosters: Solving SameGame and its Chessboard Variant. In Proceedings of the 21st Benelux Conference on Artificial Intelligence (BNAIC), pp , [9] : 1,, [10] :, pp ,, Vol.53, No.2, 33

42 563,, [11],,, :, pp ,, Vol.53, No.11, [12], : k-armed., AL,, Vol. 2008, No. 49, pp.65 70, [13], :., Vol MPS-86, No. 31, pp. 1 4, [14] :,, Vol. 49, No. 6, pp ,

23 Study on Generation of Sudoku Problems with Fewer Clues

23 Study on Generation of Sudoku Problems with Fewer Clues 1120254 2012 3 1 9 9 21 18 i Abstract Study on Generation of Sudoku Problems with Fewer Clues Norimasa NASU Sudoku is puzzle a kind of pencil