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

A Study of Optimal Strategies for Ko Fight of Computer Go

詹傑淳(Chieh-Chun Chan)

指導教授 ： 林順喜

國立臺灣師範大學/理學院/資訊工程研究所/碩士(2010年)

摘要

打劫問題在圍棋裏佔據了一個十分重要的位置。在過去圍棋的打劫問題研究上，由於雙方各種走法的組合過於繁複，因此並未能考慮到所有可能獲得更大利益的情況。本論文重新的探討在本劫的條件下圍棋的打劫策略。首先，我們在打劫過程中將所有可能發生的情況都納入考慮，來確保不會有可能獲得更大利益的情況被忽略，利用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.

並列關鍵字

Computer Go ； Ko ； Ko Fight ； Ko Threat ； Real Ko ； Damage Ko ； MiniMax Search

參考文獻

[2].S. Russell, P. Norving, Artificial Intelligence: A Modern Approach, 2/E, PEARSON, 2003.

[5].林玉祥，“電腦圍棋中考慮使用損劫之打劫策略研究＂，國立台灣師範大學資訊工程研究所，碩士論文，2007。

[9].黃士傑，“電腦圍棋打劫的策略＂，國立台灣師範大學資訊工程研究所，碩士論文，2003。

[1].L. V. Allis, “Searching for solutions in games and artificial intelligence, ＂Ph.D Dissertation Vrije, Universitat Amsterdam, Maastricht, 1994.

[3].日本圍棋規則，http://go.yenching.edu.hk/japrule.htm。