電腦圍棋打劫的最佳策略之研究

Abstract

打劫問題在圍棋裏佔據了一個十分重要的位置。在過去圍棋的打劫問題研究上，由於雙方各種走法的組合過於繁複，因此並未能考慮到所有可能獲得更大利益的情況。本論文重新的探討在本劫的條件下圍棋的打劫策略。首先，我們在打劫過程中將所有可能發生的情況都納入考慮，來確保不會有可能獲得更大利益的情況被忽略，利用MiniMax的搜尋原則建構出打劫的流程圖。接下來利用bottom up的方法來比較雙方的利益差，將不可能走到的分支砍掉，來找到正確決策的判斷式，因此我們可以得到在不同劫爭價值、有價值棋步、雙方劫材下最佳的決策。

Ko fight plays a very important role in Go. How to get the best profit for all possible situations has not been shown in the past study of ko fight problem, because it has a huge number of possible outcomes. In this thesis, we reconsider the optimal strategies over all the possible situations, which could be happened during the process of the ko fight. We build a flow chart of ko fight for each situation by MiniMax search tree. By comparing the difference of the profits between two subtrees, we then prune the worse branches of the game tree in a bottom-up fashion. Finally, we find the correct decision formulas for all possible situation. Therefore, we can find the best strategy in a ko fight with the consideration of ko threats and valuable moves.