跳到主要內容

臺灣博碩士論文加值系統

(44.220.44.148) 您好!臺灣時間:2024/06/14 12:10
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:張智淵
研究生(外文):CHANG, CHIH-YUAN
論文名稱:對手模型在電腦暗棋對局程式上效益之研究
論文名稱(外文):Evaluating the Effectiveness of Opponent Model in Chinese Dark Chess Program
指導教授:黃國展黃國展引用關係
指導教授(外文):HUANG, KUO-CHAN
口試委員:陳志昌陳隆彬姜自強黃國展
口試委員(外文):CHEN, JR-CHANGCHEN, HUNG-PINCHIANG, TZU-CHIANGHUANG, KUO-CHAN
口試日期:2021-07-12
學位類別:碩士
校院名稱:國立臺中教育大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2021
畢業學年度:109
語文別:中文
論文頁數:53
中文關鍵詞:暗棋最小最大樹搜尋法阿爾發-貝塔剪枝法對手模型
外文關鍵詞:Chinese dark chessminimax game tree searchalpha-beta pruningopponent model
相關次數:
  • 被引用被引用:0
  • 點閱點閱:97
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
電腦對局是人工智慧領域非常重要的一門學問,其中雙人對局遊戲的研究中也已經有很長的一段時間。一般而言,電腦程式通常是以遊戲樹搜尋的概念來處理雙人對局,從最早的最小最大樹搜尋法到阿爾發-貝塔剪枝法,再到蒙地卡羅樹搜尋法。我們在本篇論文中探討如何將對手模型運用在採最小最大樹搜尋法的暗棋程式上。在之前的研究中,對手模型曾被引入遊戲Bao的電腦程式,然而和Bao不同的是暗棋多了翻棋的隨機因素,所以探討對手模型在暗棋中的效益是值得進行的研究。我們的對手模型研究大致可以分為兩個部分,在第一部分中我們將先前文獻中的對手模型搜尋法導入暗棋程式中,並得到了正面的結果。對手模型確實能增加暗棋程式的勝率,但是由於暗棋中含有隨機的特性,因此若等到所有蓋著的棋子都翻開後再導入對手模型會得到更佳的結果。在第二部分的研究中,我們提出了一個新的對手模型建立及運用方法。我們利用對手模型的資訊在進行最小最大樹搜尋時加上分枝限縮的作法。和原本的對手模型運用方式相比,分枝限縮有效地減少了搜尋所需時間,所節省下來的時間可被用來增加搜尋深度以提升程式的棋力。實驗結果顯示我們的新方法對於增強暗棋程式是有效的,並且在實際的對戰中有擊敗文獻上原本對手模型搜尋法的潛能。
Computer programs for playing conventional board games are a very important research topic in the field of artificial intelligence. Generally speaking, the programs usually deal with two-player games based on the concept of game tree search, from earlier minimax search to alpha-beta pruning search, and now to Monte Carlo tree search. In this thesis, we study how to effectively build an opponent model and apply it to the minimax game tree search for playing Chinese dark chess. In previous studies, an opponent-model search method has been introduced into the game Bao. However, compared with Bao, Chinese dark chess has a stochastic nature. Therefore, it is worthwhile to conduct opponent model related research works on Chinese dark chess to evaluate its potential benefits. Our research work can be divided into two parts. In the first part, we apply the opponent-model search method to Chinese dark chess. The outcome is positive. The opponent model can indeed improve the performance for our program, but due to the game's stochastic nature, it is better to adopt the opponent-model search after all pieces are revealed. In the second part, we propose a new branch reduction method for minimax tree search based on opponent model. Compared to the previous opponent-model search, the proposed method features low search overhead and feasible opponent model construction process. The experimental results show that our new method can improve the program's playing strength significantly and has potential to outperform the opponent-model search in terms of win rate.
Abstract I
Table of Contents III
List of Figures IV
List of Tables V
Chapter1. Introduction 1
Chapter2. Background and Related Work 6
Chapter3. Game Tree Search based on Opponent Model 12
3-1. Minimax Search and Alpha-Beta Pruning 12
3-2. Evaluation Function 18
3.3 Other strength improvement strategies 23
3-4. Emulating opponent’s minimax search 26
3-5. Branch reduction based on opponent model 28
Chapter4. Experimental Evaluation 30
4-1. Evaluation Functions in the Experiments 30
4-2. Evaluation of Opponent Model Search in Chinese Dark Chess 30
4-2-1. Experiment Setup 30
4-2-2. Experiment I 31
4-2-3. Experiment II 33
4-2-4. Experiment III 35
4-3. Evaluation of the Branch Reduction Method Based on Opponent Model 36
4-3-1. Experiment Setups 36
4-3-2. Experiment on exploring top 10 branches 37
4-3-3. Experiment on exploring top 5 branches 37
4-3-4. Experiment on exploring top 3 branches 38
4-4. Branch Reduction Performed after Revealing All Pieces 39
Chapter5. Conclusions and Future Work 42
References 44


[1]https://en.wikipedia.org/wiki/Category:Traditional_board_games (Accessed 2021/7/12)
[2]P. Muens, “Game AIs with Minimax and Monte Carlo Tree Search”, Towards Data Science, https://towardsdatascience.com/game-ais-with-minimax-and-monte-carlo-tree-search-af2a177361b0 (accessed 2019/12/28)
[3]H. J. V. D. Herik, “Computer Chess: From Idea to DeepMind”, ICGA Journal, Vol. 40, No. 3, pp. 160-176, 2018.
[4]D. Silver, A. Huang, C. J. Maddison et al., “Mastering the Game of Go with Deep Neural Networks and Tree Search”, Nature, Vol. 529, pp. 484-489, January 2016.
[5]D. Silver, J. Schrittwieser, K. Simonyan et al., “Mastering the Game of Go without Human Knowledge”, Nature, Vol. 550, pp. 354-359, October 2017.
[6]B. N. Chen, B. J. Shen, T. S. Hsu, “Chinese Dark Chess”, ICGA Journal, Vol. 33, No. 2, pp. 93-106, 2010.
[7]L. S. Shapley, Stochastic games. Proceedings of the national academy of sciences, 39(10), pp. 1095-1100, 1953.
[8]H. H. L. M. Donkers, H. J. van den Herik, J. W. H. M. Uiterwijk, “Selecting Evaluation Functions in Opponent-Model Search”, Theoretical Computer Science, Vol. 349, Iss. 2, pp. 245-267, December 2005.
[9]N. Mizukami, Y. Tsuruoka, “Building a Computer Mahjong Player Based on Monte Carlo Simulation and Opponent Models”, Proceedings of IEEE Conference on Computational Intelligence and Games, 31 Aug.-2 Sept. 2015, Tainan, Taiwan
[10]E. A. Heinz, “Extended Futility Pruning”, Scalable Search in Computer Chess -- Algorithmic Enhancements and Experiments at High Search Depths, pp. 41-51, 2000.
[11]I. Althöfer, S. Heuser, “Randomised Evaluation in Single-Agent Search”, ICGA Journal, Vol. 28, No. 1, pp. 21-31, 2005.
[12]C. B. Browne, E. Powley, D. Whitehouse et al., “A Survey of Monte Carlo Tree Search Methods”, IEEE Transactions on Computational Intelligence and AI in Games, Vol. 4, Iss.1, pp. 1-43, March 2012.
[13]L. Kocsis, C. Szepesvári, “Bandit Based Monte-Carlo Planning”, Proceedings of European Conference on Machine Learning, pp. 282-293, 2006
[14]A. Sadybakasov, Combining Monte-Carlo Tree Search with State-of-the-Art Search Algorithm in Chess, Master Thesis, TU Darmstadt, Knowledge Engineering Group, 2016.
[15]M. Lanctot, M. H. M. Winands, T. Pepels, N. R. Sturtevant, “Monte Carlo Tree Search with Heuristic Evaluations Using Implicit Minimax Backups”, Proceedings of 2014 IEEE Conference on Computational Intelligence and Games, pp. 26-29, Aug. 2014.
[16]H. Baier, M. H. M. Winands, “MCTS-Minimax Hybrids with State Evaluations”, Journal of Artificial Intelligence Research, Vol. 62, pp. 193-231, 2018.
[17]H. Baier, M. H. M. Winands, “MCTS-Minimax Hybrids”, IEEE Transactions on Computational Intelligence and AI in Games, Vol. 7, Iss. 2, pp. 167-179, June 2015.
[18]H. Baier, M. H. M. Winands, “Monte-Carlo Tree Search and Minimax Hybrids”, Proceedings of IEEE Conference on Computational Intelligence in Games, pp. 11-13 Aug. 2013, Niagara Falls, ON, Canada.
[19]H. Baier, M. H. M. Winands, “Monte-Carlo Tree Search and Minimax Hybrids with Heuristic Evaluation Functions”, Proceedings of Workshop on Computer Games, pp. 45-63, 2014.
[20]H. Baier, “A Rollout-Based Search Algorithm Unifying MCTS and Alpha-Beta”, Proceedings of International Workshop on General Intelligence in Game-Playing Agents, pp. 57-70, 2016
[21]https://en.wikipedia.org/wiki/Solved_game (Accessed 2021/7/12)
[22]D. Carmel, S. Markovitch, Learning models of opponent’s strategies in game playing, in: Proc. AAAI Fall Symp. on Games: Planning and Learning, Raleigh, NC, pp. 140–147, 1993.
[23]H. Iida, J.W.H.M. Uiterwijk, H.J. van den Herik, Opponent-Model search, Technical Report CS 93-03, Universiteit Maastricht, Maastricht, The Netherlands, 1993.
[24]D. Carmel, S. Markovitch, Pruning algorithms for multi-model adversary search, Artificial Intelligence 99 (2), pp. 325–355, 1998.
[25]H.H.L.M. Donkers, J.W.H.M. Uiterwijk, H.J. van den Herik, Admissibility in Opponent-Model search, Inform. Sci. 154 (3–4), pp. 195–202, 2003.
[26]H.H.L.M. Donkers, J.W.H.M. Uiterwijk, H.J. van den Herik, Probabilistic Opponent-Model search, Inform. Sci. 135, pp. 123–149, 2001.
[27]H.H.L.M. Donkers, Nosce Hostem: searching with opponent models, Ph.D. Thesis, Universiteit Maastricht, Maastricht, The Netherlands, 2003.
[28]Marc Ponsen, Geert Gerritsen, Guillaume Chaslot, ”Integrating Opponent Models with Monte-Carlo Tree Search in Poker”, AAAIWS'10-03: Proceedings of the 3rd AAAI Conference on Interactive Decision Theory and Game Theory, 2010.
[29]A. Davidson, “Opponent modeling and search in poker: Learning and acting in a hostile and un-certain environment”, Master’s thesis, University of Alberta, 2002.
[30]A. Van Der Kleij, “Monte Carlo tree search and opponent modeling through player clustering in no-limit Texas hold’em poker,” Master’s thesis, University of Groningen, 2010.
[31]C. H. Hsueh, I. C. Wu, W. J. Tseng, S. J. Yen, J. C. Chen, “An Analysis for Strength Improvement of an MCTS-based Program Playing Chinese Dark Chess”, Theoretical Computer Science, Vol. 644, pp. 63-75, September 2016.
[32]S. J. Yen, C. W. Chou, J. C. Chen, I. C. Wu, K. Y. Kao, “The Art of the Chinese Dark Chess Program DIABLE”, R. S. Chang, L. Jain, S. L. Peng (eds), Advances in Intelligent Systems and Applications -Volume 1, Smart Innovation, Systems and Technologies, Vol. 20. Springer, Berlin, Heidelberg, 2013.
[33]S. J. Yen, C. W. Chou, J. C. Chen, I. C. Wu, K. Y. Kao, “Design and Implementation of Chinese Dark Chess Programs”, IEEE Transactions on Computational Intelligence and AI in Games, Vol. 7, Iss. 1, pp. 66-74, March 2015.
[34]T. Pepels, M.J. Tak, M. Lanctot, M.H.M. Winands, “Quality-Based Rewards for Monte Carlo Tree Search Simulations”, Proceedings of the 21st European Conf. on Artificial Intelligence, Prague, Czech Republic, 2014.
[35]G. M. J. B. Chaslot, M. H. M. Winands, H. J. V. D. Herik, J. W. H. M. Uiterwijk, B. Bouzy, “Progressive Strategies for Monte-Carlo Tree Search”, New Mathematics and Natural Computation, Vol. 4, No. 3, pp. 343-357, 2008.
[36]H. J. Chang, J. C. Chen, G. Y. Fan, C. W. Hsueh, T. S. Hsu, “Using Chinese Dark Chess Endgame Databases to Validate and Fine-Tune Game Evaluation Functions”, ICGA Journal, Vol. 40, No. 2, pp. 45-60, 2018.
[37]H. J. Chang, J. C. Chen, C. W. Hsueh, T. S. Hsu, “Analysis and Efficient Solutions for 2×4 Chinese Dark Chess”, ICGA Journal, Vol. 40, No. 2, pp. 61-76, 2018.
[38]H. J. Chang, C. W. Hsueh, T. S. Hsu, “Convergence and Correctness Analysis of Monte-Carlo Tree Search Algorithms: A Case Study of 2 by 4 Chinese Dark Chess”, Proceedings of 2015 IEEE Conference on Computational Intelligence and Games, 31 Aug.-2 Sept. 2015, Tainan, Taiwan.
[39]https://web.ntpu.edu.tw/~jcchen/clients/ver3/chinesedarkchess_Rule.txt(Accessed 2021/7/12)

電子全文 電子全文(網際網路公開日期:20260816)
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top