請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/1360
標題: | 有效使用記憶體的小盤面圍棋求解演算法及實作 Memory efficient algorithms and implementations for solving small-board-sized Go |
作者: | Hung-Cheng Lin 林弘承 |
指導教授: | 薛智文 |
關鍵字: | 小盤面圍棋,狀態空間搜尋,回溯分析,記憶體內運算, Small-board-Go,State Space Search,Retrograde Analysis,In- Memory Computing, |
出版年 : | 2018 |
學位: | 碩士 |
摘要: | 之前的研究已有弱解的小盤面圍棋解法,在此基礎上,我們希望能找到小盤面圍棋的強解,做為更深入的分析。我們應用圍棋的特性來壓縮狀態的儲存空間,並用回溯分析以找出所有可能狀態的最佳解,也設計出一個儲存於硬碟的資料庫以供後續存取。為了儲存及更新大量的狀態,使用壓縮後並儲存分割的資料區塊於記憶體而非硬碟,在需要使用的時候再解壓,可達到速度和記憶體用量的平衡。此方法亦可應用於巨量資料的處理。此外,我們由結果觀察並證明正確一路圍棋的最佳簡單著手規則。 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. |
URI: | http://tdr.lib.ntu.edu.tw/handle/123456789/1360 |
DOI: | 10.6342/NTU201802448 |
全文授權: | 同意授權(全球公開) |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-107-1.pdf | 1.18 MB | Adobe PDF | 檢視/開啟 |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。