有效使用記憶體的小盤面圍棋求解演算法及實作

Memory efficient algorithms and implementations for solving small-board-sized Go

林弘承(Hung-Cheng Lin)

指導教授 ： 薛智文

共同指導教授 ： 徐讚昇

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2018年)

https://doi.org/10.6342/NTU201802448

摘要

之前的研究已有弱解的小盤面圍棋解法,在此基礎上,我們希望能找到小盤面圍棋的強解,做為更深入的分析。我們應用圍棋的特性來壓縮狀態的儲存空間,並用回溯分析以找出所有可能狀態的最佳解,也設計出一個儲存於硬碟的資料庫以供後續存取。為了儲存及更新大量的狀態,使用壓縮後並儲存分割的資料區塊於記憶體而非硬碟,在需要使用的時候再解壓,可達到速度和記憶體用量的平衡。此方法亦可應用於巨量資料的處理。此外,我們由結果觀察並證明正確一路圍棋的最佳簡單著手規則。

關鍵字

小盤面圍棋 ； 狀態空間搜尋 ； 回溯分析 ； 記憶體內運算

並列摘要

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.

並列關鍵字

Small-board-Go ； State Space Search ； Retrograde Analysis ； In- Memory Computing

參考文獻

[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.