請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/84876完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 薛智文(Chih-Wen Hsueh) | |
| dc.contributor.author | Chia-Ming Hsu | en |
| dc.contributor.author | 許嘉銘 | zh_TW |
| dc.date.accessioned | 2023-03-19T22:30:20Z | - |
| dc.date.copyright | 2022-08-30 | |
| dc.date.issued | 2022 | |
| dc.date.submitted | 2022-08-26 | |
| dc.identifier.citation | 11th computer olympiad. https://icga.org/icga/news/Olympiad/Olympiad2006/. Accessed June 8, 2022. Aga rules. https://www.usgo.org/aga-concise-rules-go. Accessed April 29, 2022. Asian tv cup. https://www.nihonkiin.or.jp/match/tv-asia/archive.html. Accessed April 29, 2022. British go journal - number 174. https://www.britgo.org/files/2016/deepmind/BGJ174-AlphaGo.pdf. Accessed June 8, 2022. Chinese rules. http://home.snafu.de/jasiek/c2002.pdf. Accessed April 29, 2022. The future of go summit, match one: Ke jie vs alphago. https://www.youtube.com/watch?v=Z-HL5nppBnM. Accessed June 8, 2022. The future of go summit, match three: Ke jie vs alphago. https://www.youtube.com/watch?v=ru0E7N0-kFE. Accessed June 8, 2022. The future of go summit, match two: Ke jie vs alphago. https://www.youtube.com/watch?v=1U1p4Mwis60. Accessed June 8, 2022. Google deepmind challenge match - full games with commentary. https://www.youtube.com/playlist?list=PLqYmG7hTraZAZG14YEL8iFDjShWQsWrNR. Accessed June 8, 2022. Ing cup. http://www.ycqweiqi.com/Index.aspx. Accessed April 29, 2022. Ing rules. https://www.usgo.org/sites/default/files/pdf/IngRules2006.pdf. Accessed April 29, 2022. Ing rules. https://go.org.nz/index.php/about-go/new-zealand-rules-of-go. Accessed April 29, 2022. International computer game association. https://icga.org/. Accessed April 29, 2022. Japanese rules. http://www.cs.cmu.edu/~wjh/go/rules/Japanese.html. Accessed April 29, 2022. Katago. https://katagotraining.org/. Accessed June 8, 2022. Katago opening books. https://katagobooks.org/. Accessed June 8, 2022. Korean rules. http://home.snafu.de/jasiek/k2016.html. Accessed April 29, 2022. Lg cup. http://baduk.lg.co.kr/eng/. Accessed April 29, 2022. Lomonosov tablebases website. https://tb7.chessok.com/. Accessed April , 2022. 福井正明. 囲碁特訓五 × 五 ― 五道盤上達法. 碁スーパーブックス２. 日本棋院, 2000. 福井正明. 五路盤問題集: 画期的囲碁上達法. 囲碁文庫. 日本棋院, 2002. 林弘承. 有效使用記憶體的小盤面圍棋求解演算法及實作. 2018. V. Arlazarov and A. Futer. Computer analysis of a rook endgame. In Computer Chess Compendium, pages 330–336. Springer, 1988. H. Bal and V. Allis. Parallel retrograde analysis on a distributed system. In Supercomputing’95: Proceedings of the 1995 ACM/IEEE Conference on Supercomputing, pages 73–73. IEEE, 1995. B. Bouzy. Go patterns generated by retrograde analysis. Evaluation, 1(3):9, 2001. C.-W. Chou, P.-C. Chou, H. Doghmen, C.-S. Lee, T.-C. Su, F. Teytaud, O. Teytaud, H.-M. Wang, M.-H. Wang, L.-W. Wu, et al. Towards a solution of 7x7 go with meta-mcts. In Advances in Computer Games, pages 84–95. Springer, 2011. R. Gasser. Solving nine men’s morris. Computational Intelligence, 12(1):24–41, 1996. T. N. Ki-in. 黑猫的四路围棋. T. R. Lincke and A. Marzetta. Large endgame databases with limited memory space. ICGA Journal, 23(3):131–138, 2000. R. Raman, V. Raman, and S. R. Satti. Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets. ACM Transactions on Algorithms (TALG), 3(4):43–es, 2007. J. W. Romein and H. E. Bal. Awari is solved. ICGA Journal, 25(3):162–165, 2002. J. W. Romein and H. E. Bal. Solving awari with parallel retrograde analysis. Computer, 36(10):26–33, 2003. J. Schaeffer, Y. Björnsson, N. Burch, R. Lake, P. Lu, and S. Sutphen. Building the checkers 10-piece endgame databases. In Advances in Computer Games, pages 193–210. Springer, 2004. J. Schaeffer, N. Burch, Y. Bjornsson, A. Kishimoto, M. Muller, R. Lake, P. Lu, and S. Sutphen. Checkers is solved. science, 317(5844):1518–1522, 2007. M. Sharir. A strong-connectivity algorithm and its applications in data flow analysis. Computers & Mathematics with Applications, 7(1):67–72, 1981. T. Ströhlein. Untersuchungen über kombinatorische Spiele. PhD thesis, Technische Hochschule München, 1970. R. Tarjan. Depth-first search and linear graph algorithms. SIAM journal on computing, 1(2):146–160, 1972. K. Thompson. Retrograde analysis of certain endgames. J. Int. Comput. Games Assoc., 9(3):131–139, 1986. K. Thompson. 6-piece endgames. ICGA Journal, 19(4):215–226, 1996. E. C. van der Werf, H. J. Van Den Herik, and J. W. Uiterwijk. Solving go on small boards. ICGA Journal, 26(2):92–107, 2003. C. Wirth and J. Nievergelt. Exhaustive and heuristic retrograde analysis of the kppkp endgame. ICGA Journal, 22(2):67–80, 1999. P.-h. Wu, P.-Y. Liu, and T.-s. Hsu. An external-memory retrograde analysis algorithm. In International Conference on Computers and Games, pages 145–160. Springer, 2004. B. Yang, L. Wang, H. Lu, and Y. Yang. Learning the game of go by scalable network without prior knowledge of komi. IEEE Transactions on Games, 12(2):187–198, 2020. V. Zakharov and V. Makhnychev. Creating tables of chess 7-piece endgames on the lomonosov supercomputer. Superkomp＇yutery, 15:34–37, 2013. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/84876 | - |
| dc.description.abstract | 圍棋在古代就被發明出來，是一個歷史悠久的遊戲，世代相傳。到了現在，雖然規則與以往不同，但在很多國家也都一直是個熱門的遊戲，圍棋的規則簡單明瞭，但玩法變化多端，因此圍棋被認為是世界上最受歡迎且有趣的棋類遊戲之一。本論文在建構4路圍棋的殘局知識庫，提供了一個圍棋殘局知識庫的建立流程。我們使用AGA圍棋計分規則，實作包含完全禁止迴圈和只禁止長度為二的劫爭迴圈在內的兩種棋規，並透過殘局知識庫觀察和探討禁止迴圈和不同圍棋規則對於圍棋決策的影響。最後建立2路、3路和5路的圍棋殘局知識庫，觀察不同棋盤大小的圍棋的解和迴圈的關聯。 | zh_TW |
| dc.description.abstract | Go was invented in ancient times. It is a game with a long history and has been passed down through generations. Now, although the rules are different from the past, Go has always been a popular game in many countries. The rules of Go are simple and clear, but there are many ways to play it. So Go is considered one of the most popular and interesting board games in the world. In this thesis, we propose a process to build the 4x4 Go endgame databases. We use the AGA scoring rules and try different rules, including no cycle is allowed and only allows length-2 cycles formed by ko. We analyze the impact of prohibiting cycles on the endgame databases we build. Finally, we build the endgames for 2x2 Go, 3x3 Go, and 5x5 Go and observe the relationship between the board size and cycle dealing rules. | en |
| dc.description.provenance | Made available in DSpace on 2023-03-19T22:30:20Z (GMT). No. of bitstreams: 1 U0001-2608202214162300.pdf: 3368538 bytes, checksum: 2d8506471b617a36dc8d8bfc90f643c6 (MD5) Previous issue date: 2022 | en |
| dc.description.tableofcontents | 口試委員會審定書 iii 誌謝 v 摘要 vii Abstract ix 1 Introduction 1 2 Related Works 3 2.1 Endgame Databases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.2 Go Endgame and Go in Small Board . . . . . . . . . . . . . . . . . . . . 4 3 Go 7 3.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 3.2 Rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 3.2.1 Board . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 3.2.2 Stone . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.2.3 Intersection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.2.4 String . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3.2.5 Liberty . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3.2.6 Capture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.2.7 No Suicide Rule . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.2.8 Ko . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.2.9 Seki . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.2.10 Eye . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.2.11 Dead and Alive . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.2.12 Score . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.2.13 Komi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.2.14 Comparison of Rules . . . . . . . . . . . . . . . . . . . . . . . . 15 3.3 Stable Terminal Position (STP) . . . . . . . . . . . . . . . . . . . . . . . 15 3.4 Rules used in this study . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 4 Methodology 19 4.1 State . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 4.2 Computing Board Index . . . . . . . . . . . . . . . . . . . . . . . . . . 20 4.2.1 Board Serial . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 4.2.2 Board Status . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 4.2.3 Board Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 4.2.4 Illegal Board Index . . . . . . . . . . . . . . . . . . . . . . . . . 22 4.3 Stable States . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4.3.1 Board Score . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4.4 Child . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.5 Retrograde Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.6 Cycle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 4.6.1 In-Cycle and Out-Cycle . . . . . . . . . . . . . . . . . . . . . . 37 4.6.2 Strongly Connected Component (SCC) . . . . . . . . . . . . . . 39 4.6.3 Retrograde Analysis Without Cycles . . . . . . . . . . . . . . . . 40 4.7 DTM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 4.7.1 Stable States . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 4.7.2 Retrograde Analysis . . . . . . . . . . . . . . . . . . . . . . . . 45 5 Experiments 49 5.1 Experiment Settings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 5.2 Results for 4x4 Go Endgame . . . . . . . . . . . . . . . . . . . . . . . . 49 5.2.1 Legal States . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 5.2.2 Initialization of State Values . . . . . . . . . . . . . . . . . . . . 51 5.2.3 Children of States . . . . . . . . . . . . . . . . . . . . . . . . . . 53 5.2.4 Endgames with Different Rules . . . . . . . . . . . . . . . . . . 53 5.3 DTM for 4x4 Go . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 5.4 Verification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 6 Discussion 67 6.1 Initial State . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 6.2 Score . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 6.2.1 States not in the SCC . . . . . . . . . . . . . . . . . . . . . . . . 70 6.2.2 States in the SCC . . . . . . . . . . . . . . . . . . . . . . . . . . 72 6.2.3 Endgame Types . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 6.3 Cycle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 7 Results on other small-board-sized Go 79 7.1 Results for 2x2 Go and 3x3 Go Endgame . . . . . . . . . . . . . . . . . 79 7.2 Results for 5x5 Go Endgame . . . . . . . . . . . . . . . . . . . . . . . . 96 7.3 Cycles in Small board . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 8 Conclusion and Future Works 111 8.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 8.2 Future Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 Bibliography 115 Problems 119 .1 4x4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 .1.1 Problem 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 .1.2 Problem 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 .1.3 Problem 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 .1.4 Problem 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 .1.5 Problem 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 .2 5x5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 .2.1 Problem 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 .2.2 Problem 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 .2.3 Problem 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 .2.4 Problem 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 | |
| dc.language.iso | en | |
| dc.subject | 回溯分析 | zh_TW |
| dc.subject | 圍棋循環 | zh_TW |
| dc.subject | 殘局知識庫 | zh_TW |
| dc.subject | 強連通元件 | zh_TW |
| dc.subject | 圍棋 | zh_TW |
| dc.subject | retrograde analysis | en |
| dc.subject | Go | en |
| dc.subject | cycles in Go | en |
| dc.subject | endgame database | en |
| dc.subject | strongly connected component | en |
| dc.title | 使用不同迴圈規則小棋盤圍棋殘局庫的建構及觀察 | zh_TW |
| dc.title | Small-board-sized Go endgames for different cycle-breaking rules: Constructions and Observations | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 110-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.coadvisor | 徐讚昇(Tsan-Sheng Hsu) | |
| dc.contributor.oralexamcommittee | 陳志昌(Jr-Chang Chen),顏士淨(Shi-Jim Yen) | |
| dc.subject.keyword | 圍棋,圍棋循環,殘局知識庫,強連通元件,回溯分析, | zh_TW |
| dc.subject.keyword | Go,cycles in Go,endgame database,strongly connected component,retrograde analysis, | en |
| dc.relation.page | 139 | |
| dc.identifier.doi | 10.6342/NTU202202858 | |
| dc.rights.note | 同意授權(限校園內公開) | |
| dc.date.accepted | 2022-08-29 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
| dc.date.embargo-lift | 2022-08-30 | - |
| 顯示於系所單位： | 資訊工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| U0001-2608202214162300.pdf 授權僅限NTU校內IP使用（校園外請利用VPN校外連線服務） | 3.29 MB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。