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

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.