電腦圍棋中考慮使用損劫之打劫策略研究

林玉祥(Yu-Xiang Lin)

指導教授 ： 林順喜

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

摘要

在圍棋中，劫爭是個重要且有趣的問題，同時也是電腦圍棋程式提昇棋力的關鍵之一。劫爭與劫材的使用有密不可分的關係，也可以說，劫爭的複雜性與樂趣就建築在劫材的使用上。損劫是圍棋實戰中經常出現且被使用的一種劫材，由於損劫本身的性質，使得找劫材時的利益考量更複雜了許多。我們延續了先前師大資工所黃士傑的劫爭研究，納入使用損劫的考量，透過minimax搜尋原則以及打劫流程圖，找出打劫的策略。目標是當電腦圍棋程式遇上劫爭，可以迅速的計算出在這個局部能夠得到的利益，以及選擇正確的劫材來打劫。目前在損劫的損值相同時能夠迅速地獲得最佳解，而損值不同時，透過我們的方法來搜尋，平均能夠在七分鐘左右處理雙方各16個劫材的數量。另透過測試得知，使用經驗法則可以在平均誤差0.1目以內逼近最佳解所求之值。

關鍵字

電腦圍棋 ； 劫爭 ； 打劫 ； 劫材 ； 損劫 ； 最小最大搜尋法

並列摘要

Ko fight is not only an important and interest part in Go, but also one of the key issues in order to improve the level of Go program. There is a great relationship between Ko and Ko threat. In other words, the complexity and fun of Ko are usually based on finding Ko threat. Damage Ko is one kind of Ko threat that occurs and is used frequently. Because of the property of damage Ko, it’s getting more complex when we deal with the benefits of the Ko threats. Following the research of S. C. Huang in National Taiwan Normal University for Ko fight, we furthermore consider the usage of damage Ko and find out the strategies for Ko fight by showing the flow diagram of Ko fight and the principle of minimax search. Our prototype program can calculate the optimal benefit quite fast in some cases, and choose a correct Ko threat to against opponent when Ko fight happened. We can find the best solution when damage values of the Ko threats are the same. On the other hand, the number of Ko threat that we can process in 7 minutes by our search method is about 16 for each player when the damage values are different. The experimental results show that we can approximate the best solution by our heuristic method with an average error less than 0.1.

並列關鍵字

Computer Go ； Ko ； Ko Fight ； Ko Threat ； Damage Ko ； Minimax Search

參考文獻

[2] B. Bouzy, T. Cazenave, “Computer go: an ai-oriented survey,” Artificial Intelligence, Vol. 132 (1), pp. 39-103, 2001.

[6] J. Lehmann, “Computer go,” available at

[12] 林順喜、黃士傑、顏士淨，”電腦圍棋打劫的策略”，全國計算機會議(NCS2003), 逢甲大學，台灣，中華民國，OT_133，頁1754-1761, 2003。

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

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