工作層級蒙地卡羅樹狀搜尋之研究

Abstract

近來蒙地卡羅樹狀搜尋(Monte Carlo Tree Search;簡稱MCTS)方法，已相當成功地應用於電腦圍棋程式;工作層級搜尋(Job-level Search)方法，最近也成功地應用於解六子棋開局問題。本論文的研究方向是將此兩項技術結合，成為工作層級MCTS(Job-level MCTS;簡稱JL-MCTS)，並將其應用於解7x7 Killall圍棋問題。 對於JL-MCTS，我們設計一些預先更新策略(Pre-update Policy)，分析對平行化的效率。而為了解7x7 Killall 圍棋，由於搜尋樹太龐大，我們利用資料庫解決記憶體使用問題，並改善資料庫存取效率與解決同步問題。另外，為了不浪費運算資源，我們使用Transposition Table，但因此產生了GHI問題(Graph History Interaction)，為了解決GHI問題，我們提出一新的GHI問題解決方法，來解出7x7 Killall圍棋的盤面。 最後我們解出一個僅有四子的7x7 Killall圍棋開局盤面，總共算了37,792,301個節點，若使用288核心，將耗時89天，這是目前可能解出之圍棋開局中，有最多空點的盤面。

Monte Carlo tree search has been successfully applied to the improvement of Go program strengths, and Job-level Search has been successfully applied to solving Connect6 openings. We combine the two techniques into Job-level Monte Carlo Tree Search(JL-MCTS) and use it to solve the game of 7x7 Killall-Go. Several pre-update policies were designed for our JL-MCTS. Experiments were performed to compare the parallelized efficiency of each policy. In order to solve 7x7 Killall-Go , for which the search tree memory requirements are huge, we provided a solution to store the search tree into a database, which solved the problem of access efficiency and synchronization. The GHI (Graph History Interaction) problem for Go was also an issue since transposition tables were used. For solving 7x7 Killall-Go correctly, we designed a new approach to solve the GHI problem. We have solved a 7x7 Killall-Go position with only four stones on the board, which is computed in parallel with 288 cores by 37,792,301 nodes and 89 days. This is one of the most difficult Killall-Go openings that have been solved to date because of its larger board size and the large amount of playable space involved.