請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/1360完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 薛智文 | |
| dc.contributor.author | Hung-Cheng Lin | en |
| dc.contributor.author | 林弘承 | zh_TW |
| dc.date.accessioned | 2021-05-12T09:37:10Z | - |
| dc.date.available | 2019-02-12 | |
| dc.date.available | 2021-05-12T09:37:10Z | - |
| dc.date.copyright | 2019-02-12 | |
| dc.date.issued | 2018 | |
| dc.date.submitted | 2019-01-30 | |
| dc.identifier.citation | [1] Erik CD van der Werf, H Jaap Van Den Herik, and Jos WHM Uiterwijk. Solving go on small boards. Icga Journal, 26(2):92–107, 2003.
[2] Erik CD van der Werf and Mark HM Winands. Solving go for rectangular boards. Icga Journal, 32(2):77–88, 2009. [3] Cheng-Wei Chou, Ping-Chiang Chou, Hassen Doghmen, hang-Shing Lee, TsanCheng Su, Fabien Teytaud, Olivier Teytaud, Hui-Ming Wang, Mei-Hui Wang, LiWen Wu, et al. Towards a solution of 7x7 go with meta-mcts. In Advances in Computer Games, pages 84–95. Springer, 2011. [4] Erik CD van der Werf, Jos WHM Uiterwijk, and H Jaap van den Herik. Solving ponnuki-go on small boards. 2002. [5] Chia-Chuan Chang, Ting-Han Wei, and I-Chen Wu. Job-level computing with boinc support. In Technologies and Applications of Artificial Intelligence (TAAI), 2016 Conference on, pages 200–206. IEEE, 2016. [6] John Tromp and Gunnar Farnebäck. Combinatorics of go. In International Conference on Computers and Games, pages 84–99. Springer, 2006. [7] Ken Thompson. Retrograde analysis of certain endgames. ICCA journal, 9(3):131–139, 1986. [8] Haw-ren Fang, Tsan-sheng Hsu, and Shun-chin Hsu. Construction of chinese chess endgame databases by retrograde analysis. In International Conference on Computers and Games, pages 96–114. Springer, 2000. [9] Hiroyuki Iida, Jin Yoshimura, Kazuro Morita, and Jos WHM Uiterwijk. Retrograde analysis of the kgk endgame in shogi: Its implications for ancient heian shogi. In International Conference on Computers and Games, pages 318–335. Springer, 1998. [10] John W Romein and Henri E Bal. Solving awari with parallel retrograde analysis. Computer, 36(10):26–33, 2003. [11] Bruno Bouzy. Go patterns generated by retrograde analysis. Evaluation, 1(3):9. [12] Ping-hsun Wu, Ping-Yi Liu, and Tsan-sheng Hsu. An external-memory retrograde analysis algorithm. In International Conference on Computers and Games, pages 145–160. Springer, 2004. [13] ⽇本棋院. 囲碁パズル「黒貓のヨンロ」 . Retrieved Apr 16, 2018, from the World Wide Web: https://www.nihonkiin.or.jp/teach/app/yonro/index.html/, 2011. [14] Ko at sensei’s library. Retrieved Mar 30, 2018, from the World Wide Web: https://senseis.xmp.net/?Ko, 2017. [15] Scoring at sensei’s library. Retrieved Mar 30, 2018, from the World Wide Web: https://senseis.xmp.net/?Scoring, 2017. [16] Seki at sensei’s library. Retrieved Mar 30, 2018, from the World Wide Web: https://senseis.xmp.net/?Seki, 2017. [17] David B Benson. Life in the game of go. Information Sciences, 10(1):17–29, 1976. [18] Louis Victor Allis et al. Searching for solutions in games and artificial intelligence. Rijksuniversiteit Limburg, 1994. [19] Peter Deutsch and Jean-Loup Gailly. Zlib compressed data format specification version 3.3. Technical report, 1996. [20] zlib. Retrieved May 11, 2018, from the World Wide Web: http://www.zlib.net/, 2018. [21] zlib 1.2.11 manual. Retrieved May 31, 2018, from the World Wide Web: https://www.zlib.net/manual.html, 2017. [22] Henri Bal and Victor Allis. Parallel retrograde analysis on a distributed system. In Supercomputing, 1995. Proceedings of the IEEE/ACM SC95 Conference, pages 73–73. IEEE, 1995 | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/handle/123456789/1360 | - |
| dc.description.abstract | 之前的研究已有弱解的小盤面圍棋解法,在此基礎上,我們希望能找到小盤面圍棋的強解,做為更深入的分析。我們應用圍棋的特性來壓縮狀態的儲存空間,並用回溯分析以找出所有可能狀態的最佳解,也設計出一個儲存於硬碟的資料庫以供後續存取。為了儲存及更新大量的狀態,使用壓縮後並儲存分割的資料區塊於記憶體而非硬碟,在需要使用的時候再解壓,可達到速度和記憶體用量的平衡。此方法亦可應用於巨量資料的處理。此外,我們由結果觀察並證明正確一路圍棋的最佳簡單著手規則。 | zh_TW |
| dc.description.abstract | Previously studies have weakly solved the problem of playing small-board-sized Go, but this study determines a strongly-solved solution and a database to access afterward. State reduction is applied by the features of Go; and then retrograde analysis is used to find the optimal answer of every possible state of small-board-sized Go. Dealing with large state information, an in-memory method is used to search the states for small-board-sized Go. Saving separated compressed data in the memory, instead of on a disk, and decompressing this data on demand, to balance performance and memory usage, in order to solve the problem efficiently. This method can also be applied to large scale data processing. A method is also determined that obtains the optimal result for boards with a single row. | en |
| dc.description.provenance | Made available in DSpace on 2021-05-12T09:37:10Z (GMT). No. of bitstreams: 1 ntu-107-R05922061-1.pdf: 1211924 bytes, checksum: 0fe5263d758a7e42c51df6f1c5795db6 (MD5) Previous issue date: 2018 | en |
| dc.description.tableofcontents | Acknowledgements iii
摘要 v Abstract vii 1 Motivation 1 2 Related Work 3 2.1 Previous Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.2 Retrograde Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.3 4 × 4 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 3 Problem Definition 7 3.1 The Rules of Go . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 3.1.1 Basic Rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 3.1.2 Rules of Ko . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.1.3 Scoring Rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3.2 Seki . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.3 The Rules that are used for this study . . . . . . . . . . . . . . . . . . . . 10 3.4 Goal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 4 Method 13 4.1 Encoding of States . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 4.2 Legal States and Reduction . . . . . . . . . . . . . . . . . . . . . . . . . 15 4.2.1 Terminal States . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 4.2.2 State Reduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 4.2.3 Sort Order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 4.3 Search Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 4.3.1 Preprocessing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 4.3.2 Algorithm to Search the Game Result . . . . . . . . . . . . . . . 19 4.3.3 Algorithm to Find the Score . . . . . . . . . . . . . . . . . . . . 21 4.3.4 Data Structure used to save the Search Result . . . . . . . . . . . 21 4.3.5 Validation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4.3.6 Misc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.4 In-Memory Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.5 Memory Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 4.6 Performance Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 5 Result 29 5.1 Configuration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 5.2 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 5.3 Performance Considerations . . . . . . . . . . . . . . . . . . . . . . . . 30 5.3.1 Memory Block Size and Memory Chunk Size . . . . . . . . . . . 30 5.3.2 Sort Order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 5.3.3 Number of Edges . . . . . . . . . . . . . . . . . . . . . . . . . . 33 5.3.4 Search Depth . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 5.3.5 Data Saving Method . . . . . . . . . . . . . . . . . . . . . . . . 36 5.4 Variation: Circular Board . . . . . . . . . . . . . . . . . . . . . . . . . . 37 5.5 Properties of Go . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 5.5.1 Seki . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 5.5.2 Strongly Connected Component . . . . . . . . . . . . . . . . . . 38 5.6 Strategy for 1 × n Go . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 5.6.1 Step(s) = 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 5.6.2 Step(s) = 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 5.6.3 Step(s) = 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 5.6.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 6 Conclusion and Future Work 53 6.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 6.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 6.2.1 Rule-Based 2 × N Go . . . . . . . . . . . . . . . . . . . . . . . 54 6.2.2 Other Sorting Criteria . . . . . . . . . . . . . . . . . . . . . . . 54 References 55 | |
| dc.language.iso | en | |
| dc.subject | 記憶體內運算 | zh_TW |
| dc.subject | 小盤面圍棋 | zh_TW |
| dc.subject | 狀態空間搜尋 | zh_TW |
| dc.subject | 回溯分析 | zh_TW |
| dc.subject | State Space Search | en |
| dc.subject | In- Memory Computing | en |
| dc.subject | Retrograde Analysis | en |
| dc.subject | Small-board-Go | en |
| dc.title | 有效使用記憶體的小盤面圍棋求解演算法及實作 | zh_TW |
| dc.title | Memory efficient algorithms and implementations for solving small-board-sized Go | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 107-1 | |
| dc.description.degree | 碩士 | |
| dc.contributor.coadvisor | 徐讚昇 | |
| dc.contributor.oralexamcommittee | 王大為,蔣益庭 | |
| dc.subject.keyword | 小盤面圍棋,狀態空間搜尋,回溯分析,記憶體內運算, | zh_TW |
| dc.subject.keyword | Small-board-Go,State Space Search,Retrograde Analysis,In- Memory Computing, | en |
| dc.relation.page | 57 | |
| dc.identifier.doi | 10.6342/NTU201802448 | |
| dc.rights.note | 同意授權(全球公開) | |
| dc.date.accepted | 2019-01-31 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
| 顯示於系所單位： | 資訊工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-107-1.pdf | 1.18 MB | Adobe PDF | 檢視/開啟 |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。