跳到主要內容

臺灣博碩士論文加值系統

(44.200.171.156) 您好!臺灣時間:2023/03/22 03:18
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:陳秉均
研究生(外文):CHEN, PING-CHUN
論文名稱:基於遊戲樹搜尋與神經網路設計電腦暗棋程式之研究
論文名稱(外文):The Design of a Chinese Dark Chess Program Based on Game Tree Search and Neural Network
指導教授:黃國展黃國展引用關係
指導教授(外文):HUANG, KUO-CHAN
口試委員:黃國展陳志昌陳隆彬姜自強
口試委員(外文):HUANG, KUO-CHANCHEN, JR-CHANGCHEN, LUNG-PINCHIANG, TZU-CHIANG
口試日期:2022-07-20
學位類別:碩士
校院名稱:國立臺中教育大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2022
畢業學年度:110
語文別:英文
論文頁數:40
中文關鍵詞:AlphaZero暗棋殘局庫蒙地卡羅樹搜尋法阿爾法與貝塔剪枝搜尋法神經網路
外文關鍵詞:AlphaZeroChinese dark chessendgame databaseMonte Carlo tree searchalpha-beta pruningneural network
相關次數:
  • 被引用被引用:0
  • 點閱點閱:81
  • 評分評分:
  • 下載下載:10
  • 收藏至我的研究室書目清單書目收藏:0
電腦對局(如西洋棋、象棋、圍棋等)在人工智慧的研究上具有長遠的歷史與重大意
義,暗棋也是其中一個典型的例子,並且是國內外電腦對局競賽中的常見項目。除
此之外,暗棋還具有前述西洋棋、象棋、圍棋等棋類對局所沒有的隨機性,使其遊
戲樹搜尋的複雜度及對局程式開發的難度大幅增加。本篇論文呈現我們開發一個
電腦暗棋程式,並持續改良以增進棋力的過程與相關探討。我們的電腦暗棋程式曾
分別在電腦奧林匹亞競賽 2020 與 2022 年,以及台灣電腦對局學會 2022 年競賽的
暗棋項目中獲得過第三名的成績。我們的程式首先實作了電腦對局領域中目前最
常被使用的最佳實務技術,包括阿爾法與貝塔剪枝遊戲樹搜尋法、蒙地卡羅樹搜尋
法、審局函數、同型表、殘局庫、平行處理等。以此為基礎,我們接著嘗試引進
AlphaZero 的強化學習技術來進一步提升程式的棋力。實際對局的結果顯示基於
AlphaZero 的程式相比於只使用蒙地卡羅樹搜尋法的版本的確能有效進一步提升
勝率。除此之外,我們亦將神經網路技術與殘局庫的概念結合,訓練出一個可以替
代傳統殘局庫的神經網路模型,在擁有高準確度的同時,只需相對更小的空間需求。
我們論文中所提出的這兩個方法除了可以獨自運用之外,亦能彼此整合成一個更
為強化的方法,實驗結果顯示能夠達到更高的勝率。
The study of computer programs playing strategy board games, such as chess, Chinese
chess, and Go, has a long history and great impact on the research of artificial intelligence.
Chinese dark chess is also a popular game in various competitions, featuring its stochastic
property which greatly increases the complexity of game tree search and thus the
difficulty in developing good playing programs. This thesis presents our work on
developing and continuously improving a competition program for Chinese dark chess,
which won the third place in Computer Olympiad 2020, 2022 and TCGA 2022. Our
program first implemented existing best practice in the area of computer game programs,
including alpha-beta pruning search, Monte Carlo tree search, evaluation function,
transposition table, endgame database, and parallel processing. To further improve the
program’sstrength, we then tried to apply AlphaZero to Chinese dark chess. Experimental
results show that the program based on AlphaZero could achieve better performance, in
terms of win rate, than the original program simply adopting MCTS. In addition, we
trained a neural network model to replace the traditional endgame database, providing
highly accurate evaluation capability and requiring much less storage space. Moreover,
experimental results also show that the two proposed approaches can be integrated to
achieve even better performance than adopted separately.
誌謝 I
Abstract II
摘要 III
Table of Contents IV
List of Figures V
List of Tables VI
Chapter1. Introduction 1
Chapter2. Background and Related Work 4
2-1. Chinese Dark Chess 4
2-2. Minimax Search with Alpha-Beta Pruning 5
2-3. Monte Carlo Tree Search 6
2-4. AlphaGo 8
2-5. Endgame Database 8
Chapter3. AlphaZero Applied to Chinese Dark Chess 11
3-1. Implicit Minimax Backups 12
3-2. Progressive Bias 12
3-3. Early Playout Termination 13
3-4. Quality-Based Rewards 13
3-5. Parallelization 13
3-6. AlphaZero for Chinese Dark Chess 16
Chapter4. Neural Network Emulating Endgame Database 21
Chapter5. Program Implementation 25
5-1. Lookup Table for Evaluation Function 25
5-2. Transposition Table 27
5-3. Parallel Alpha-Beta Search 28
5-4. Chance Nodes 29
Chapter6. Performance Evaluation 31
Chapter7. Conclusion and Future Work 35
References 37
[1]J. McCarthy, “Chess as the Drosophila of AI”, Computers, Chess, and Cognition, pp. 227-237, 1990.
[2]B. N. Chen, B. J. Shen, T. S. Hsu, “Chinese Dark Chess”, ICGA Journal, vol. 33, no. 2, pp. 93-106, 2010.
[3]Taiwan Computer Game Association, http://tcga.ndhu.edu.tw/ (accessed 2022/7/14).
[4]Taiwanese Association for Artificial Intelligence, https://www.taai.org.tw/ (accessed 2022/7/14).
[5]International Computer Games Association, https://icga.org/ (accessed 2022/7/14).
[6]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.
[7]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.
[8]D. Silver et al. “A General Reinforcement Learning Algorithm That Masters Chess, Shogi, and Go through Self-Play”, Science, vol. 362, no. 6419, pp. 1140-1144, 2018.
[9]L. S. Shapley, “Stochastic Games”, Proceedings of the National Academy of Sciences, vol. 39, no. 10, pp. 1095-1100, 1953.
[10]M. Świechowski, T. Tajmajer, “A Practical Solution to Handling Randomness and Imperfect Information in Monte Carlo Tree Search” Proceedings of 2021 IEEE Conference on Computer Science and Intelligence Systems (FedCSIS), pp. 101-110, 2021.
[11]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.
[12]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 2022/7/14).
[13]G. Tan, et al, “Winning Rate Prediction Model Based on Monte Carlo Tree Search for Computer Dou Dizhu”, IEEE Transactions on Games, vol. 13, iss. 2, pp. 123-137, 2019.
[14]N. Jouandeau, T. Cazenave, “Small and large MCTS playouts applied to Chinese Dark Chess stochastic game”, Proceedings of Workshop on Computer Games, Springer, p. 78-89, 2014.
[15]H. Baier, M.H.M. Winands, “MCTS-Minimax Hybrids with State Evaluations”, Journal of Artificial Intelligence Research, vol. 62, pp. 193-231, 2018.
[16]H. Baier, P.D. Drake, “The Power of Forgetting: Improving the Last-Good-Reply Policy in Monte Carlo Go”, IEEE Transactions on Computational Intelligence and AI in Games, vol. 2, iss.4, pp. 303-309, 2010.
[17]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.
[18]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.
[19]J. C. Chen, T. Y. Lin, S. C. Hsu, T. S. Hsu, “Design and Implementation of Computer Chinese Dark Chess Endgame Database”, Proceedings of Workshop on TCGA Computer Game, Hualien, Taiwan, 2012.
[20]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.
[21]K. Thompson, “Retrograde Analysis of Certain Endgames”, ICCA Journal, vol. 9, no. 3, pp. 131-139, 1986.
[22]D. Silver, J. Schrittwieser, K. Simonyan et al, “Mastering the Game of Go without Human Knowledge”, Nature, vol. 550, pp. 354-359, October 2017.
[23]M. Lanctot, et al, “Monte Carlo Tree Search with Heuristic Evaluations Using Implicit Minimax Backups”, Proceedings of 2014 IEEE Conference on Computational Intelligence and Games, pp. 1-8, 2014.
[24]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.
[25]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.
[26]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.
[27]E. Steinmetz, M. Gini, Maria, “More Trees or Larger Trees: Parallelizing Monte Carlo Tree Search”, IEEE Transactions on Games, vol. 13, iss. 3, pp. 315-320, 2020.
[28]M. Enzenberger and M. Müller, “A Lock-Free Multithreaded Monte-Carlo Tree Search Algorithm,” Proceedings of 12th Int. Conf. Adv. Comput. Games, pp. 14–20, 2009.
[29]H. Fang, T. Hsu, S. Hsu, “Construction of Chinese Chess Endgame Databases by Retrograde Analysis”, Proceedings of International Conference on Computers and Games, pp. 96-114, Berlin, Heidelberg, 2000.
[30]J. C. Chen, T. Y. Lin, B. N. Chen, ”Equivalence Classes in Chinese Dark Chess Endgames”, IEEE Transactions on Computational Intelligence and AI in Games, vol. 7, iss. 2, pp. 109-122, 2014.
[31]J. C. Chen, G. Y. Fan, H. J. Chang, “Compressing Chinese Dark Chess Endgame Databases by Deep Learning”, IEEE Transactions on Games, vol. 10, iss. 4, pp. 413-422, 2018.
[32]R. D. Greenblatt, D. E. Eastlake III, S. D. Crocker, “The Greenblatt Chess Program”, Proceedings of the November 14-16, 1967, fall joint computer conference, pp. 801-810, 1967.
[33]A. L. Zobrist, “A New Hashing Method with Application for Game Playing”, ICGA Journal, vol. 13, no. 2, pp. 69-73, 1990.
[34]R. A. Finkel, J. P. Fishburn, “Parallelism in Alpha-Beta Search”, Artificial Intelligence, vol. 19, iss. 1, pp. 89-106, 1982.
[35]B. N. Chen, T. Hsu, “Automatic Generation of Opening Books for Dark Chess”, Proceedings of International Conference on Computers and Games, pp. 221-232, 2013.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊