請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/80805完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 薛智文(Chih-Wen Hsueh) | |
| dc.contributor.author | Hsin-I Lin | en |
| dc.contributor.author | 林欣儀 | zh_TW |
| dc.date.accessioned | 2022-11-24T03:17:13Z | - |
| dc.date.available | 2022-02-16 | |
| dc.date.available | 2022-11-24T03:17:13Z | - |
| dc.date.copyright | 2022-02-16 | |
| dc.date.issued | 2022 | |
| dc.date.submitted | 2022-02-11 | |
| dc.identifier.citation | [1] 徐讚昇, 許舜欽, 陳志昌, 蔣益庭, 陳柏年, 劉雲青, 張紘睿, 蔡數真, 林庭羽, and 范綱宇. 電腦對局導論. 國立臺灣大學出版中心, 2017. [2] 謝曜安. 電腦暗棋之設計及實作. 臺灣師範大學資訊工程研究所學位論文, pages 1–52, 2007. [3] 謝政孝. 暗棋中棋種間食物鏈關係之探討與實作. 臺灣師範大學資訊工程研究所學位論文, pages 1–43, 2010. [4] A. M. AGENT. Emanuel Oster. PhD thesis, Maastricht University, 2015. [5] L. V. Allis, M. van der Meulen, and H. J. Van Den Herik. Proof-number search. Artificial Intelligence, 66(1):91–124, 1994. [6] B. W. Ballard. The*-minimax search procedure for trees containing chance nodes. Artificial Intelligence, 21(3):327–350, 1983. [7] H. J. Berliner. Backgammon computer program beats world champion. Artificial Intelligence, 14(2):205–220, 1980. [8] C. B. Browne, E. Powley, D. Whitehouse, S. M. Lucas, P. I. Cowling, P. Rohlfshagen, S. Tavener, D. Perez, S. Samothrakis, and S. Colton. A survey of monte carlo tree search methods. IEEE Transactions on Computational Intelligence and AI in games, 4(1):1–43, 2012. [9] M. Buro. The othello match of the year: Takeshi murakami vs. logistello. ICGA Journal, 20(3):189–193, 1997. [10] B.-N. Chen, B.-J. Shen, and T.-s. Hsu. Chinese dark chess. Icga Journal, 33(2):93–106, 2010. [11] R. Coulom. Efficient selectivity and backup operators in monte-carlo tree search. In International conference on computers and games, pages 72–83. Springer, 2006. [12] D. E. Knuth and R. W. Moore. An analysis of alpha-beta pruning. Artificial intelligence, 6(4):293–326, 1975. [13] J. Pearl. Scout: A simple game-searching algorithm with proven optimal properties. In AAAI, pages 143–145, 1980. [14] A. Reinefeld, J. Schaeffer, and T. A. Marsland. Information acquisition in minimal window search. In IJCAI, volume 85, pages 1040–1043, 1985. [15] A. L. Samuel. Some studies in machine learning using the game of checkers. IBM Journal of research and development, 3(3):210–229, 1959. [16] J. Schaeffer, R. Lake, P. Lu, and M. Bryant. Chinook the world man-machine checkers champion. Ai Magazine, 17(1):21–21, 1996. [17] C. E. Shannon. Xxii. programming a computer for playing chess. The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science, 41(314):256–275, 1950. [18] D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. Van Den Driessche, J. Schrittwieser, I. Antonoglou, V. Panneershelvam, M. Lanctot, et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484–489, 2016. [19] D. Silver, J. Schrittwieser, K. Simonyan, I. Antonoglou, A. Huang, A. Guez, T. Hubert, L. Baker, M. Lai, A. Bolton, et al. Mastering the game of go without human knowledge. nature, 550(7676):354–359, 2017. [20] S.-J. Yen, C.-W. Chou, J.-C. Chen, I.-C. Wu, and K.-Y. Kao. Design and implementation of chinese dark chess programs. IEEE Transactions on Computational Intelligence and AI in Games, 7(1):66–74, 2014. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/80805 | - |
| dc.description.abstract | 在過去幾十年裡，人工智慧在對局領域取得了長足的進步。其中帶有隨機因素的對局遊戲也成為一個重要的子領域。而暗棋可以翻棋子的獨特玩法所產生的機率行為，對於電腦來說是設計時的一大挑戰。本篇論文將進行電腦暗棋程式的相關研究，並且對暗棋中的機率型節點的搜尋提供一些改進的策略。我們將基於alpha-beta搜尋實作暗棋程式，並根據棋種之間的競爭關係設計審局函數。在搜尋機率型節點時，我們採用star搜尋演算法進行剪枝，最後發現star2搜尋演算法在預先探測時，若搭配好的排序可以大幅降低搜尋時間、減少搜尋節點，並且擁有較好的戰績。 | zh_TW |
| dc.description.provenance | Made available in DSpace on 2022-11-24T03:17:13Z (GMT). No. of bitstreams: 1 U0001-0702202210351200.pdf: 737289 bytes, checksum: 277cefc6a7a0116ddb7b2eddbbf49d0a (MD5) Previous issue date: 2022 | en |
| dc.description.tableofcontents | Contents 誌謝 iii 摘要 v Abstract vii 1 Introduction 1 2 Chinese Dark Chess 3 2.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.2 Rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.3 Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.3.1 State-Space Complexity . . . . . . . . . . . . . . . . . . . . . . 4 2.3.2 Game-Tree Complexity . . . . . . . . . . . . . . . . . . . . . . . 5 2.3.3 Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 3 Problem Statement and Related Works 7 3.1 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 3.2 Related Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 4 Methodology 9 4.1 Evaluation Function Design . . . . . . . . . . . . . . . . . . . . . . . . 9 4.2 Alpha-Beta Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 4.3 Iterative Deepening . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 4.4 Move Ordering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 4.5 Endgames Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 4.6 Transposition Table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 4.7 Quiescent Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 4.8 Star Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 4.8.1 Star0 search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 4.8.2 Star1 search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 4.8.3 Star2 search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 5 Experiments 31 5.1 Experimental Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 5.1.1 Experiment settings . . . . . . . . . . . . . . . . . . . . . . . . . 31 5.1.2 Evaluation function verification . . . . . . . . . . . . . . . . . . 31 5.1.3 Baseline agent . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 5.1.4 Chance nodes searching . . . . . . . . . . . . . . . . . . . . . . 32 5.2 Benchmark . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 6 Results 35 6.1 Improvement of evaluation function . . . . . . . . . . . . . . . . . . . . 35 6.2 Baseline agent adjustment . . . . . . . . . . . . . . . . . . . . . . . . . 39 6.3 Experiments related to chance nodes . . . . . . . . . . . . . . . . . . . . 41 7 Discussion 51 8 Conclusion and Future Works 53 8.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 8.2 Future Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 Bibliography 55 List of Figures 4.1 Min-Max Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 4.2 Alpah-beta search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 6.1 The difference between the score and the score with one less piece. . . . . 35 6.2 Example board 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 6.3 Example board 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 6.4 Example board 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 6.5 The statistic of all combinations of chess pieces on the board . . . . . . . 38 6.6 Experiment board . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 List of Tables 2.1 The pieces in Chinese Dark Chess . . . . . . . . . . . . . . . . . . . . . 4 3.1 The score of pieces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 4.1 The relationship between the types . . . . . . . . . . . . . . . . . . . . . 10 4.2 The initial score of the pieces . . . . . . . . . . . . . . . . . . . . . . . . 10 4.3 An exception in the evaluation function . . . . . . . . . . . . . . . . . . 11 4.4 The initial score of the pieces . . . . . . . . . . . . . . . . . . . . . . . . 15 5.1 Static scoring values . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 6.1 The score of Figure 6.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 6.2 The score of Figure 6.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 6.3 The score of Figure 6.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 6.4 The effect of move ordering . . . . . . . . . . . . . . . . . . . . . . . . 39 6.5 The effect of move ordering without escape priority . . . . . . . . . . . . 40 6.6 The effect of the transposition table . . . . . . . . . . . . . . . . . . . . 40 6.7 The hit rate of the transposition table . . . . . . . . . . . . . . . . . . . . 40 6.8 Compare different improvement methods . . . . . . . . . . . . . . . . . 41 6.9 The average of total nodes searching for positions with 8 dark pieces . . . 42 6.10 Average search time for position with 8 dark pieces . . . . . . . . . . . . 42 6.11 The average of total nodes searching for positions with 16 dark pieces . . 43 6.12 Average search time for position with 16 dark pieces . . . . . . . . . . . 44 6.13 The average of total nodes searching for positions with 24 dark pieces . . 44 6.14 Average search time for position with 24 dark pieces . . . . . . . . . . . 44 6.15 Compare the average numbers of total nodes in all methods . . . . . . . . 45 6.16 The results of the agents competition . . . . . . . . . . . . . . . . . . . . 47 6.17 The score of the agents competition . . . . . . . . . . . . . . . . . . . . 48 6.18 Standard deviation of the games . . . . . . . . . . . . . . . . . . . . . . 49 6.19 Probability distribution (1/2) . . . . . . . . . . . . . . . . . . . . . . . . 49 6.20 Probability distribution (2/2) . . . . . . . . . . . . . . . . . . . . . . . . 49 | |
| dc.language.iso | en | |
| dc.subject | 電腦暗棋 | zh_TW |
| dc.subject | 機率型遊戲 | zh_TW |
| dc.subject | 機率型節點搜尋 | zh_TW |
| dc.subject | alpha-beta剪枝 | zh_TW |
| dc.subject | 電腦對局 | zh_TW |
| dc.subject | computer games | en |
| dc.subject | chance node search | en |
| dc.subject | stochastic games | en |
| dc.subject | alpha-beta pruning | en |
| dc.subject | computer Chinese Dark Chess | en |
| dc.title | 電腦暗棋機率型節點搜尋及相關問題之研究 | zh_TW |
| dc.title | Chance Node Searching and Related Problems in Computer Chinese Dark Chess | en |
| dc.date.schoolyear | 110-1 | |
| dc.description.degree | 碩士 | |
| dc.contributor.coadvisor | 徐讚昇(Tsan-Sheng Hsu) | |
| dc.contributor.oralexamcommittee | 顏士淨(Shou-Zen Fan),(Li-Jen Lee) | |
| dc.subject.keyword | 電腦對局,電腦暗棋,alpha-beta剪枝,機率型節點搜尋,機率型遊戲, | zh_TW |
| dc.subject.keyword | computer games,computer Chinese Dark Chess,alpha-beta pruning,chance node search,stochastic games, | en |
| dc.relation.page | 57 | |
| dc.identifier.doi | 10.6342/NTU202200317 | |
| dc.rights.note | 同意授權(限校園內公開) | |
| dc.date.accepted | 2022-02-12 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
| 顯示於系所單位： | 資訊工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| U0001-0702202210351200.pdf 授權僅限NTU校內IP使用（校園外請利用VPN校外連線服務） | 720.01 kB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。