臺灣博碩士論文加值系統

蒙地卡羅樹搜尋演算法是近年來在電腦對局領域中最熱門的演算法，應用在電腦圍棋領域中更是卓有成效，使電腦圍棋程式的棋力有著飛躍性的成長。這個演算法也被應用在其他的遊戲上，甚至被用來解決能源管理等真實世界的問題。本論文就幾個層面對此演算法進行了應用與擴展。首先，本論文試圖將此原本用在完全資訊型遊戲的演算法應用於不完全資訊型遊戲，也就是在華人文化圈相當盛行的暗棋，並取得了卓越的成果。其次，本論文試圖利用蒙地卡羅樹搜尋演算法的架構，建構出一套自我學習的機制，在缺乏領域知識的遊戲NoGo上，僅需使用相當少的知識，便能夠透過自我學習的方式極大地提升程式的棋力。最後，本論文針對蒙地卡羅樹搜尋演算法本身在不同分支間資訊共享不便的缺陷，提出一套即時學習的機制，使電腦圍棋程式的棋力有所成長。

Monte Carlo Tree Search (MCTS) is the most popular algorithm in computer games field in recent years. This algorithm is very efficient for computer Go and improves the strength of computer Go program amazingly. This algorithm is also used to other games, even the problem of real world, for example, power management. MCTS is applied and ameliorated in several directions in this article. First, this article tries to use MCTS to Dark Chess, an imperfect information game, and very popular in Chinese culture. Second, this article tries to use the framework of MCTS to build a self-learning method. The self-learning method could greatly improve the strength of program in the game of NoGo, by counterbalancing the lack of domain knowledge by self-learning. Finally, this article focuses on a specific weakness of MCTS. MCTS does not share information between different branches. This article proposes an online learning method to ameliorate it.

摘要 i
Abstract iii
誌謝 v
Contents vii
List of Figures ix
List of Tables x
1. Introduction 1
2. Monte Carlo Tree Search 5
2.1 Monte Carlo Method 5
2.2 Upper Confidence Bound 6
2.3 Upper Confidence Bound for Tree Search 6
2.4 Rapid Action Value Estimation 7
2.5 Prior Knowledge 8
2.6 Simulation Strategy 8
3. MCTS for Dark Chess 9
3.1 Introduction 9
3.2 Dark Chess 10
3.3 Game Tree Search in Dark Chess 12
3.3.1 Expectiminimax Game Tree 12
3.3.2 Heuristics for Flipping Actions 13
3.3.3 Move efficiency 14
3.4 Nondeterministic Monte Carlo Tree Search 15
3.4.1 Structure of NMCTS 16
3.4.2 Selection and Expansion 17
3.5 Simulation 19
3.5.1 Capture First 19
3.5.2 Capture Stronger Piece First 19
3.5.3 Capture and Escape Stronger Piece First 20
3.6 Backpropagation 20
3.7 Experimental Results 21
3.7.1 MCTS Parameters 21
3.7.2 Backpropagation Heuristics 22
3.7.3 Simulation Heuristics 22
3.7.4 Scalability 23
3.7.5 Tournament Results 24
3.7.6 Diablo versus ABS-Based Programs 24
3.7.7 Diablo versus Humans 25
3.8 Conclusion 26
4. Self-Learning in NoGo 29
4.1 Introduction 29
4.1.1 MM 30
4.1.2 SB 31
4.1.3 NoGo 33
4.2 Main method 34
4.3 Preliminary Result 36
4.4 Experiment Results 37
4.5 Conclusion &; Discussion 39
5. Online Learning in Go 41
5.1 Introduction 41
5.2 Related Work 42
5.2.1 The Game of Go 42
5.2.2 LGRF 42
5.3 Global Corresponding Move Bias 43
5.4 Experiment Results 45
5.4.1 Inner Data 45
5.4.2 Scalability 46
5.4.3 Threshold Value 46
5.5 Conclusion &; Discussion 46
6. Conclusion &; Future Work 47
6.1 Conclusion 47
6.2 Future Work 47
APPENDIX A – RESULTS OF INTERNATIONAL TOURNAMENT 53

[1] B. Bruegmann. Monte carlo go. 1993.
[2] B. E. Childs , J. H. Brodeur and L. Kocsis "Transpositions and move groups in Monte Carlo tree search", Proc. IEEE Symp. Comput. Intell. Games, pp.389 -395 2008
[3] Berliner, H. J.: Chess as Problem Solving: The Development of a Tactics Analyzer. Ph.D. Thesis, Carnegie-Mellon University, Pittsburgh, (1974)
[4] Borsboom, J., Saito, J., Chaslot, G., and Uiterwijk, J., A comparison of Monte-Carlo methods for Phantom Go, Proc. 19th Belgian–Dutch Conference on Artificial Intelligence (BNAIC), Utrecht, The Netherlands, 2007.
[5] Bouzy, B. and Helmstetter, B. (2003). “Monte-Carlo Go Developments” , in H. J. van den Herik, H. Iida and E. A. Heinz (eds.), Proceedings of the 10th Advances in Computer Games Conference (ACG-10) (Kluwer Academic), pp. 159–174.
[6] Bouzy, Bruno and Cazenave, Tristan (2001). Computer Go: An AI oriented survey, Artificial Intelligence 132, pp. 39-103.
[7] Browne, C., Powley, E., Whitehouse, D., Lucas, S., Cowling, P., Rohlfshagen, P., Tavener, S., Perez, D., Samothrakis, S., and Colton, S., A survey of Monte Carlo Tree Search, IEEE Transactions on Computational Intelligence and AI in Games, vol. 4, no. 1, 2012.
[8] C.-W. Chou , O. Teytaud and S.-J. Yen "Revisiting Monte-Carlo tree search on a normal form game: NoGo", Proc. Appl. Evol. Comput., pp.73 -82 2011
[9] Chaslot, G.M.J.-B., Winands, M.H.M., Uiterwijk, J.W.H.M., van den Herik, H.J., and Bouzy, B., Progressive strategies for Monte-Carlo Tree Search, New Mathematics and Natural Computation, vol.4, no. 3, pp. 343–357, 2008.
[10] Chen, B.-N., Shen, B.-J., and Hsu, T.-s., Chinese Dark Chess, ICGA Journal. vol. 33, No.2, pp. 93–106, 2010.
[11] Chen, J.-C., Lin, T.-Y., Hsu, S.-C., and Hsu, T.-s., Design and Implementation of Computer Chinese Dark Chess Endgame Database, Proceeding of TCGA Workshop 2012, pp. 5-9, Hualien, Taiwan, 2012. (in Chinese)
[12] Chou, C.-W., Yen, S.-J., and Wu, I-C., TAAI 2011 Computer Go Tournaments, ICGA Journal, vol. 34, no. 4, pp. 251-252, 2011.
[13] Ciancarini, P. and Favini, G.P., Monte Carlo tree search in Kriegspiel, Artificial Intelligence, vol. 174, pp. 670-684, 2010.
[14] D. MacKay. Introduction to Monte Carlo methods. In M. Jordan, editor, Learning in graphical models. MIT Press, 1998.
[15] D. Silver and G. Tesauro "Monte-Carlo simulation balancing", Proc. 26th Annu. Int. Conf. Mach. Learn., pp.945 -952 2009
[16] D.E. Knuth and R.W. Moore, “An Analysis of Alpha-Beta Pruning,” Artificial Intelligence, Vol. 6, 1975, Page 293--326.
[17] Enzenberger, M., Müller, M., Arneson, B., and Segal, R., Fuego - An Open-Source Framework for Board Games and Go Engine Based on Monte Carlo Tree Search, IEEE Transactions on Computational Intelligence and AI in Games, vol. 2, no. 4, pp. 259-270, 2010.
[18] Gamelet.com, Inc., Unique Chinese Dark Chess , http://tw.gamelet.com/game.do?code=darkchess

[19] Gelly, S. and Silver, D. (2011) Monte-Carlo tree search and rapid action value estimation in computer Go. Artificial Intelligence. Vol. 175, Issue 11, July 2011, pp. 1856-1875.

[20] Gelly, S. and Silver, D., Monte-Carlo tree search and rapid action value estimation in computer Go, Artificial Intelligence, vol. 175, no. 11, pp. 1856-1875, 2011.

[21] Gelly, S., Wang, Y., Munos, R., and Teytaud, O., Modification of UCT with patterns in Monte-Carlo Go, Technical Report 6062, INRIA, 2006.
[22] Guy, V.B., Kurt, D., and Jan, R., Monte-Carlo tree search in poker using expected reward distributions, Advances in Machine Learning, First Asian Conference on Machine Learning, ACML 2009, pp. 367–381.
[23] H. Baier and P. D. Drake "The power of forgetting: Improving the last-good-reply policy in Monte Carlo Go", IEEE Trans. Comput. Intell. AI Games, vol. 2, no. 4, pp.303 -309 2010.
[24] H.J. Berliner. “Computer Backgammon,” Scientific American, Vol. 242, No. 6, 1980, pages 64--72.
[25] J. P. A. M. Nijssen "Playing Othello using Monte Carlo", Strategies, pp.1 -9 2007
[26] Kloetzer, J., Iida, H., and Bouzy, B., The Monte-Carlo Approach in Amazons, Proceedings of the Computer Games Workshop 2007 (CGW 2007), Amsterdam, The Netherlands, 2007, pp. 185–192.
[27] L. Kocsis , C. Szepesvári and J. Willemson Improved Monte-Carlo search,, 2006
[28] L. Kocsis and C. Szepesvari. “Bandit based monte-carlo planning.” In 15th European Conference on Machine Learning (ECML), pages 282–293, 2006.
[29] Lai, S.-C., Research and Implementation of Computer Dark Chess Program with Heuristics, National Dong Hwa University, Matser thesis, 2008. (in Chinese)
[30] Lishout, F. Van, Chaslot, G., and Uiterwijk, J.W.H.M., Monte-Carlo Tree Search in Backgammon, Proceedings of the Computer Games Workshop 2007 (CGW 2007), Amsterdam, The Netherlands, 2007, pp. 175-184.
[31] Lou, W.-C., Artificial Intelligence Improvement of Chinese Dark Chess, National Taiwan Normal University, Master thesis, 2011. (in Chinese)
[32] Martin Müller. Computer Go. Artificial Intelligence, 134:145-179, 2002.
[33] P. Hingston and M. Masek "Experiments with Monte Carlo Othello", Proc. IEEE Congr. Evol. Comput., pp.4059 -4064 2007
[34] P.W. Prey, “Machine Problem Solving, Part 1: Trial-and-Error Search, a Mechanical Plan to Save the Missionaries,” BYTE, Sep., 1980, pages 102--112.
[35] P.W. Prey, “Machine Problem Solving, Part 2: Directed Search Using Cryptarithmetic,” BYTE, Oct., 1980, pages 266--326.
[36] R. Coulom and K. Chen, “CRAZY STONE Wins 9x9 Go Tournament”, ICGA Journal, vol. 29, no. 2, pp. 96-97
[37] R. Coulom "Computing Elo ratings of move patterns in the game of Go", Int. Comput. Games Assoc. J., vol. 30, no. 4, pp.198 -208 2007
[38] Rémi Coulom, Efficient selectivity and backup operators in Monte-Carlo tree search, Proceedings of the 5th international conference on Computers and games, p.72-83, May 29-31, 2006, Turin, Italy

[39] Russell, S. and Norvig, P., Artificial Intelligence: A Modern Approach 2/e, Prentice Hall, 2003.
[40] S. Gelly and D. Silver "Combining online and offline knowledge in UCT", Proc. 24th Annu. Int. Conf. Mach. Learn., pp.273 -280 2007
[41] S. Gelly and Y. Wang, MOGO Wins 19×19 Go Tournament, ICGA Journal, vol. 30, no. 2, pp. 111-112
[42] S.-C. Huang , R. Coulom and S.-S. Lin "Monte-Carlo simulation balancing in practice", Proc. Comput. Games, pp.81 -92 2010
[43] Samuel, “Some studies of machine learning using the game of checkers,” IBM Journal of Research and Development, Vol. 3, No. 3, pages 210--229, 1959.
[44] Shieh, Y.-A., The Design and Implementation of Computer Dark Chess, National Taiwan Normal University, Master thesis, 2008. (in Chinese)
[45] Shih, H.-C. and Lin, S.-S., The Design and Implementation of Computer Dark Chess, Proceeding of TCGA workshop 2012, pp. 29-36, Hualien, Taiwan, 2012. (in Chinese)
[46] Shi-Jim Yen, Cheng-Wei Chou, Shun-Chin Hsu, Jr-Chang Chen and Tai-Ning Yang, "Improvement of MCTS in Computer Go," the 14th Game Programming Workshop (GPW-09), November 13-15, 2009, Hakone Seminar House, Kanagawa, Japan: GPW-2010 Proceeding pp. 91-94.
[47] T. Kozelek Methods of MCTS and the game Arimaa, 2009
[48] Van den Broeck, G., Driessens, K., and Ramon, J., Monte-Carlo Tree Search in Poker using Expected Reward Distributions, Adv. Mach. Learn., LNCS 5828, no. 1, 2009, pp. 367–381.
[49] Y. Sato , D. Takahashi and R. Grimbergen "A Shogi program based on Monte-Carlo tree search", Int. Comput. Games Assoc. J., vol. 33, no. 2, pp.80 -92 2010
[50] Yang, J.-K., Su, T.-C., and Wu, I-C., TCGA 2012 Computer Game Tournament Report, submitted to ICGA Journal, 2013.
[51] Yen, S.J., Chen, J.C., Yang, T.N., Hsu, S.C., Computer Chinese Chess. ICGA Journal, vol. 27, no. 1, pp. 3-18, ISSN 1389-6911, March 2004.
[52] Yen, S.-J., Chiu, S.-Y., and Wu, I-C., Modark Wins Chinese Dark Chess Tournament, ICGA Journal, vol. 33, no. 4, pp. 230–231, 2010.
[53] Yen, S.-J., Su, T.-C., and Wu, I-C., The TCGA 2011 Computer-Games Tournament, ICGA Journal, vol. 34, no. 2, pp. 108–110, 2011.
[54] Yi-Shan Lin, I-Chen Wu, and Shi-Jim Yen, "TAAI 2011 Computer-Game Tournaments," ICGA Journal, vol. 34, no. 4, pp. 248-250.