<4D F736F F D204E FB971B8A3B3F2B4D1A5B4A754AABAB5A6B2A42E646F63>

Size: px

Start display at page:

Download "<4D F736F F D204E FB971B8A3B3F2B4D1A5B4A754AABAB5A6B2A42E646F63>"

坛戎
5 years ago
Views:

1 林順喜國立台灣師大資訊工程研究所電腦圍棋打劫的策略黃士傑國立台灣師大資訊工程研究所顏士淨國立東華大學資訊工程研究所摘要打劫在圍棋裏佔據了十分重要的位置, 然而目前的電腦圍棋程式大都不具備打劫的能力我們利用最大最小搜尋法的原則, 得出本劫最佳的打劫策略, 使得電腦圍棋程式在處理本劫時, 能在局部求得獲利最大或損失最小的下法我們定義了棋步劫爭與劫材的價值, 作為探討打劫策略的基礎我們也詳細探討了打劫過程中劫材的使用策略關鍵詞 : 電腦圍棋打劫劫材最大最小搜尋法一緒論圍棋誕生於中國的鬥智遊戲, 主要特色規則簡單, 但由於盤面廣大變化可說無窮無盡, 圍棋已被證明為 P-Space Hard 的問題 [9] 關於圍棋史料, 請參閱 [1][2] 電腦圍棋程式的歷史, 可追溯自 1960 年,D. Lefkovitz 設計出第一個電腦圍棋程式 [4] 八年後,Zobrist 設出第一個打敗人類 ( 圍棋初學者 ) 的電腦圍棋程式 [5] 1980 年代, 由於世界電腦圍棋比賽的推動, 以及商業化的結果, 電腦圍棋成為一個引人注目的研究領域, 使得每年電腦圍棋程式的棋力均有穩定的進步 1990 年代, 世界電腦圍棋比賽的平均參賽者已超過 40 個, 來自全世界不同的國家有關電腦圍棋的規則及相關資料, 可參考 [6][7][8] 打劫在圍棋中佔據了一個相當重要的地位, 在高手對局中, 打劫隨處可見, 甚至到了幾乎每局必有打劫的地步目前, 只有少數的圍棋程式 [10][11] 有處理簡單的打劫, 大多數在電腦圍棋世界比賽得名的程式, 都未處理打劫據我們所知, 目前對於打劫的研究, 著重於劫型棋型的探討 [3][12], 牽涉到組合對局理論 [13], 尚未有從策略面探討打劫的研究本論文探討電腦圍棋中的打劫問題, 針對的根據價值的計算與判斷而決定的打劫策略關於打劫相關知識, 請參閱 [14][15] 二打劫的規則與棋步的價值打劫或劫爭圍棋中同型反覆循環的情況打劫的英文 ko, 係從日語發音而來應氏規則 [17] 與日本圍棋規約 [18] 對打劫分別規定如下 : 應氏規則第五條 : 劫型中可互提之子稱為劫子連續反覆所爭之劫子稱為熱子凡提取熱子須間隔一實手或虛手, 則爭窮日本圍棋規則第六條 : 相互提掉對手的一個棋子的棋形稱之為打劫被提的一方, 必須至少隔一手才能提回來一棋步的價值即一棋步的大小, 可用來回比較法來計算 [16] 劫爭的價值可由計算棋步價值的觀念來計算我們只要分別計算黑棋勝劫與白棋勝劫的地域, 其差距便此劫爭的大小劫材的價值, 指一方若不理此劫材, 另一方再繼續下一棋步的價值換句話說, 劫材的價值就在當作劫材的那個局部, 連下兩手的價值三劫材的分類劫材 (ko threat) 在打劫時, 用來使對方應一手而達到隔一手目的之棋步本篇論文中, 我們特別加上一個額外條件, 劫材必須包含一個性質 : 對方應一手, 便完全不損失若劫材本身就帶有地域的價值, 則歸類到有價值的棋步圍棋對局中出現的劫材可說各式各樣, 有些能計算其價值, 有些卻難以計算, 例如以劫換劫 ( 方案之一按照劫爭辭典 [14] 第頁所提, 視為劫爭價值的三分之二 ) 在圍棋對局中, 有時會出現無限劫材的情況 ( 例如雙劫活 ), 在這個局部, 白棋就擁有無限的劫材解決白棋有無限劫材的方案之一, 在其他的劫爭開始前 1

2 解決劫爭, 就可拆掉白棋在這裏的劫庫下面我們探討一些特殊的劫材雙方只得其一的劫材雙方只得其一的劫材, 意即在一個局部中的劫材, 對雙方來說都劫材, 因此雙方只得其一的劫材, 有三種可能情況 : 一. 只對黑棋符合條件, 二. 只對白棋符合條件三. 對黑棋白棋都符合條件第一二種情況, 將此劫材分別算為黑白方的劫材, 而不成為另一方的劫材第三種情況, 則算為雙方的劫材, 並且由於先使用的一方可以一次全部下完, 因此全部只算成一個劫材劫材生出的劫材圍棋對局中, 常常出現所謂的劫材生劫材, 意即在一個棋局局部中, 使用一個劫材後, 又產生出新的劫材來劫材生劫材的特色前面的劫材用完才會產生後面的劫材, 先後順序固定的, 因此可以視為先後順序固定的一組劫材本身劫當劫爭與一棋塊的死活有關時, 能作活或突破包圍網的劫材, 便稱為本身劫劫材生劫材由於先後順序固定, 因此可以將衍生出來的劫材總數, 算入我方劫材總數中, 其大小便目前能用的劫材大小本身劫棋塊發生與死活有關的劫爭時, 必須優先使用, 因為將來發生其他劫爭時, 此劫爭的本身劫不一定能成為劫材四打劫的策略本劫解題方法據估記, 本劫在圍棋對局中的打劫, 佔了 90% 以上的比例本劫各種打劫中最單純最簡單, 也最重要的其他種類的劫爭, 都本劫的延伸與複雜版本本章中, 我們先展示我們對本劫的策略, 再於下節解釋與證明我們的策略根據我們預設我方為黑棋, 而此演算法當然也適用於白棋首先我們先定義解題過程中所用到的參數 : (1) 劫爭的價值以 k 表示 (2) 黑方劫材價值下限 ((Black Ko Threat Value Lower bound,bktvl) 與白方劫材價值下限 (White Ko ThreatValue Lower bound,wktvl), 劫材價值下限我們設定的一個下限值, 用來求出劫材價值大於或等於劫材價值下限的劫材個數, 這些價值大於或等於劫材價值下限的劫材, 就符合條件的劫材對黑方與白方所設的劫材價值下限不一定相同, 因為我們分別定義黑方劫材價值下限與白方劫材價值下限 (3) 黑方盤面上 m 個符合條件的劫材 b i 及其價值白方 n 個符合條件的劫材 w i b i BKTVL, 1 i m, w i WKTVL, 1 i n 符合條件的劫材, 即為決定開始打劫後, 所使用的劫材順序由於我們預設我方黑方, 因此當開始打劫後, 黑方便從 b 1 開始使用劫材得到黑白雙方各有 m 與 n 個符合條件的劫材後, 黑方 ( 我方 ) 的劫材依照下面的原則排列將 B 建構出來 : ( 甲 ) 所有雙方只得其一的劫材, 排在最前面若有多個,b 1 其中價值最小的 ( 乙 ) 接著後面排本身劫, 從價值小的排到價值大的若第一項中沒有劫材, 則 b 1 其中價值最小的 ( 丙 ) 接著後面排一般的劫材, 從價值小的排到價值大的若第一二項都沒有劫材, 則 b 1 其中價值最小的我們預設雙方都未使用損劫, 至於其他價值小於劫材價值下限的劫材, 其中價值最大的劫材其價值用 b u 表示 (4) 盤面上除了劫爭之外的有價值的棋步 :X=(x 1,x 2,x 3, ),x 1 x 2 x 3 >0, X even = x 2 +x 4 +x 6 +,X odd = x 3 +x 5 +x 7 + 有價值的棋步中,x 1 目前盤面上除了劫爭之外價值最大的棋步,x 2 x 1 被下了之後, 盤面上除了劫爭之外價值上最大的棋步, 以此類推有價值棋步的個數, 依程式的搜尋深度與判斷能力而定, 因此我們並不定義有價值的棋步共有幾個, 而保持開放的規格為了判斷式的簡潔, 我們將 x 2 之後的第偶數大的所有的有價值棋步的價值和定義成 X even,x 3 之後的第奇數大的所有的有價值棋步的價值和定義成為 X odd 由於劫爭需要隔一手才能提劫, 因此在電腦圍棋裏, 除了棋局開端先下的一方之外, 我方總需要對方上一步下在哪裏的資訊, 以判斷對方上一步造成我方的禁著若沒有上一步對方下在哪裏的資訊, 很可能對方剛提劫的劫爭目前盤面最大的棋, 我方程式據此就提劫而馬上被判輸因此, 對方上一步下在哪裏我方決定下一步時必備的輸入與已知條件下面我們利用本劫中白方在上一步下在哪裏的資訊, 也就黑棋在所會遇到的七種情況, 提出合理且最佳的下一步, 每一種情況代表白棋的一種下法, 在後面我們將證明其正確性在這七種情況中, 並不包含造劫者所會遇到的情況換言之, 我們的演算法並未處理造劫, 除了造劫之外, 2

3 在劫爭中會碰到的每一種情況我們都有考慮造劫未來的研究課題下面, 我們預設劫爭的第一步白方提劫 ( 或造劫 ), 並根據白方七種下法來決定黑方最佳的下一步 : 白方剛提劫 x 1 +X even 的設定, 依序檢查雙方的劫材數流程如下面的 pseudo code 所展示 : for (i=1;i k+x odd -(x 1 +X even );i++) { BKTVL=[2(k+X odd -X even )]-i; WKTVL=(2x 1 +1)+i; ( 求得黑方白方符合條件的劫材數分別為 m,n); If (m>n) break; } 檢查過程中只要符合 m>n, 跳出迴圈後下 b 1 若不符合, 則檢查劫材分布三 k+x odd? 不打劫, 下 x 1 白方使用劫材 w i 屬於哪一種劫材分布? 劫材分布三屬於哪一種劫材分布? 劫材分布二劫材分布一下 b 1 劫材分布一劫材分布二劫材分布三 (b 1 本身劫 ) (b 1 雙方只得其一的劫材 ) (b 1 <w 1 )? w i WKTVL 下 b 1 應劫消劫下 x 1 x 1 b u -x 1? 下 b u w i <WKTVL 消劫圖 4.1 第一種情況情況一. 白方提劫, 輪到我方 ( 黑方 ) 找劫材首先判斷本劫的打劫條件 : x 1 +X even k+x odd? 若符合, 就開始檢查雙方的劫材分布來決定下一步我們將劫材分布的情況分為三種, 在每種分布中, 先設定 BKTVL 與 WKTVL, 便可得到雙方符合條件的劫材數 m 與 n, 來判別屬於目前檢查的劫材分布, 若屬於目前檢查的劫材分布, 便依照前述的方法將 B 建構出來雙方的劫材分布可以分成下面的三種情況 : 劫材分布一. 我方一定能取得大於或等於 k+x odd -(x 1 +X even ) 的利益 BKTVL=2(k+X odd -X even ), WKTVL=2x 1 +1 若 m>n 就符合此種分布, 則黑方下 b 1 若不符合, 則檢查劫材分布二劫材分布二. 我方一定能取得大於或等於零的利益將 BKTVL 與 WKTVL 一個遞減一個遞增 max(x 1 +X even -(k+ X odd ),b u +X even -(k+x 1 +X odd )) k +x 1 +X odd -(w i +X even )? 應劫圖 4.2 第四種情況消劫劫材分布三. 我方一定遭受損失 BKTVL=k+x 1 +X odd -X even WKTVL=k +x 1 +X odd -X even +1 若 m n 就符合此種分布這時若 b 1 雙方只得其一的劫材或為本身劫, 則使用 b 1 則比較 b 1 和 w 1 的價值, 若 b 1 <w 1, 則下 b 1 若 b 1 w 1, 就比較 x 1 與 b u -x 1, 若前者不小於後者就下 x 1, 則下 b u 第一種情況, 輪到方找劫材的演算法過程, 可以用圖 4.1 的流程圖來表示 3

4 情況二. 白方回應我方的劫材白方回應我方的劫材時, 不論我方劫材較多或劫材較少, 我方都一律提劫, 因為我方找劫材即已預設白方會應劫情況三. 白方消劫白方消劫時, 若上一步我方使用劫材 b i, 則立即取得劫材的利益 b i, 則 x 1 情況四. 白方找劫材類似情況一, 檢查雙方的劫材分布來決定下一步 : 劫材分布一. 我方一定能取得大於或等於 k-x 1 -x 2 的利益, 若白方使用的劫材 w i WKTVL 就應劫, 則消劫劫材分布二. 我方一定能取得大於或等於零的利益, 若白方使用的劫材 w i WKTVL 就應劫, 則消劫劫材分布三. 我方一定遭受大於或等於零的損失, 若白方使用 w i <WKTVL 則消劫則比較 max(x 1 +X even -(k+x odd ),b u +X even - (k+x 1 +X odd )) 與 k+x 1 +X odd -(w i +X even ), 若前者較大, 則我方應劫若後者較大, 則選擇消劫第四種情況的演算法過程, 可以用圖 4.2 的流程圖來表示情況五. 白方下有價值的棋步黑消劫若白方提劫而未消劫, 則黑提劫情況六. 白方取得劫材利益這在黑方不理白方的劫材消劫之後, 所以黑方下 x 1 情況七. 白方下瞎劫單官或虛手黑消劫以下我們要由三個方面來證明上節所提出的打劫策略 : 本劫的打劫條件與劫材價值下限交換劫材與減少損失有價值棋步的循環 I. 本劫的打劫條件與劫材價值下限下面我們藉著流程圖展示本劫整個打劫的過程, 並觀察流程圖, 利用 Minimax 搜尋原則求出本劫的打劫條件與劫材價值下限假設白方剛提劫, 雙方都將劫材耗盡才放棄劫爭, 且雙方都未使用損劫, 整個流程便如圖 4.3(a) 所示圖 4.3(b) 與 4.3(c) 圖 4.3(a) 的最底層部分最後若黑方勝劫, 底層 4.3(b), 白方勝劫則 4.3(c) 流程圖中所用到的參數定義如下 : (1)k 為劫爭的價值 (2) 黑棋使用的劫材其價值依所下的順序為 b 1,b 2,b 3, ( 不一定按大小排列 ) (3) 白棋使用的劫材其價值依所下的順序為 w 1,w 2,w 3, ( 不一定按大小排列 ) (4) 盤面上劫爭之外的有價值的棋步 x 1,x 2,x 3,,x 1 x 2 x 3 (5) X even = x 2 +x 4 +x 6 +. (6) X odd = x 3 +x 5 +x 7 +. 流程圖第 ( 一 ) 部分 : 白棋提剛劫後, 黑方需檢查佔取 x 1 讓劫給白方為較有利的下法, 就檢查本劫的打劫條件黑方下 x 1 後, 白方消劫得 k, 黑方再下 x 2, 白方再下 x 3 等, 如流程圖所示, 進行下去黑白方的利益差為 x 1 +X even -(k+x odd ) 若利益差大於或等於零, 黑方下 x 1 有利或不損失的下法, 因此選擇 x 1 由此可知本劫的打劫條件為 x 1 +X even (k+x odd ) 若不符合本劫的打劫條件, 黑方將使用劫材 b 1, 進入流程圖第 ( 二 ) 部分流程圖第 ( 二 ) 部分 : 既然決定要打這個劫爭, 黑方就使用某一個劫材 b 1, 此時白方有兩種下法白方若消劫, 就進入流程圖第 ( 三 ) 部分, 若應劫則入流程圖第 ( 四 ) 部分流程圖第 ( 三 ) 部分 : 白方消劫, 黑方再花一步取得 b 1 的劫材利益, 接著雙方便依序下有價值的棋步, 因此黑白方的利益差為 b 1 +X even -(k+x 1 +X odd ) 流程圖第 ( 四 ) 部分 : 白方應劫, 黑方提劫後, 便進入流程圖第 ( 五 ) 部分流程圖第 ( 五 ) 部分 : 白方找某一劫材 w 1, 黑方同樣有兩種應法, 若應劫, 則一直循環下去, 若消劫, 則接下來類似流程圖第 ( 三 ) 部分, k+x 1 +X odd -(w 1 +X even ) 流程圖第 ( 六 ) 部分 ( 如圖 4.3(b)): 這最後黑方勝劫的情況黑方找劫材 b i, 若白方消劫, 接下來的進行, 黑白方的利益差黑白方利益為 b i +X even -(k+x 1 +X odd ) 若白方應劫, 因無劫材繼續爭劫, 只好下 x 1, 黑方消劫後, 雙方依序下有價值的棋步, 黑白方的利益差為 k+x odd -(x 1 +X even ) 流程圖第 ( 七 ) 部分 ( 如圖 4.3(c)): 這最後白方勝劫的情況, 同流程圖第 ( 六 ) 部分, 因為黑方無劫材繼續爭劫, 只好在 x 1 與不理白方的劫材兩者中作一選擇 4

5 ( 一 ) 白方剛提劫 ( 三 ) 本劫的打劫條件成立? 黑不打劫, 下 x1 MIN ( 二 ) 黑下 b 1 ( 四 ) 白應劫黑提劫黑取得 b 1 利益白下 x 3 MAX ( 五 ) 白下 w 1 白下 x 1 黑下 x 4 黑應劫黑消劫白提劫白取得 w 1 利益白下 x 3 黑下 b 2 黑下 x 1 x 1 +X even -(k+x odd ) MIN 白應劫白下 x 2 b 1 +X even -(k+x 1 +X odd ) 黑提劫黑下 x 3 MAX 白下 w 2 黑取得 b 1 利益黑應劫黑消劫白下 x 1 b 2 +X even -(k+x 1 +X odd ) 白提劫黑下 b 3.. 接 4.3(b) 或 (c) b 2 +X even -(k+x 1 +X odd ) 流程圖 4.3(a) 打劫的流程圖 5

6 MIN ( 六 ) 白應劫黑提劫白下 x 1 黑消劫白下 x 2 黑下 x 3 圖 4.3(b) 接續流程圖 4.3(a)- 黑方勝劫 ( 七 ) MAX 黑應劫白提劫黑下 x 1 白下 x 3 黑下 b i X odd -(x 1 +X even ) 白下 w i x 1 +X even -(k+x odd ) 黑取得 b i 利益白下 x 1 b i +X even -(k+x 1 +X odd ) 黑消劫白取得 w i 利益黑下 x 1 白下 x 2 k+x 1 +X odd -(w i +X even ) 圖 4.3(c) 接續流程圖 4.3(a)- 白方勝劫觀察整個打劫的流程圖, 可以發現幾點特性 : ( 甲 ) 往左邊展開部分, 雙方一直回應對方的劫材, 使整個流程圖的樹狀結構呈現傾斜 ( 乙 ) 整個打劫過程的黑白利益差只有四種可能結果 :(1) 當黑方找某一劫材 b i 下時 ( 如圖 4.3(b)), 若白方消劫, 進行下去黑白方利益差為 b i +X even -(k+x 1 +X odd ) (2) 反之, 此時若白方改佔 x 1 換取輸劫, 黑白方利益差為 k+x odd -(x 1 +X even )(3) 每當白方找某一劫材 w i 下時 ( 如圖 4.3(c)), 若白方消劫, 進行下去黑白方利益差為 k+x 1 +X odd -(w i +X even ) (4) 反之, 此時若黑方改佔 x 1 換取輸劫, 黑白方利益差為 x 1 +X even -(k+x odd ) ( 丙 ) 假設黑方的劫材比白方多, 且劫材價值都很大, 白方的劫材不但少且價值都很小也就說, 黑棋在這場劫爭佔有絕對的優勢, 可以勝劫那麼黑方所能獲得的最大利益多少呢? 流程圖 4.3(a) 每次方找劫材, 由於白方不理劫材的損失過於巨大, 因此會全數應劫, 流程便一直往左邊的分支走到最後流程圖 4.3(b), 白方的劫材用盡, 只好選擇下 x 1 也就說, 黑方在具有絕對優越的打劫條件下, 所能獲得的最大利益, 在圖 4.3(b) 的左分支, 黑白的利益差為 k+x odd -(x 1 +X even ) 這個結論便得出下面的定理 : 定理 4-1. 在本劫中, 若雙方都最佳進行, 且 k+x odd >x 1 +X even, 則勝劫的一方能從劫爭獲取的最大利益為 k+x odd -(x 1 +X even ) 証明 : 前面我們已經得到黑方從劫爭所能獲取的最大利益為 k+x odd -(x 1 +X even ) 同理, 流程圖 4.3(c) 中黑下 x 1 換取輸劫黑白利益差為 x 1 +X even -(k+x odd ), 即白方 ( 勝劫的一方 ) 與輸劫的一方的利益差為 k+x odd -(x 1 +X even ) 因此不論黑白雙方所能獲取的最大利益為 k+x odd -(x 1 +X even ) 此定理得証 ( 丁 ) 讓我們再次觀察黑方勝劫的情況, 依據上面的定理找出黑棋勝劫時的劫材分布, 來求出雙方的劫材價值下限目前的已知條件只有本劫的打劫條件, 即 k+x odd x 1 +X even, 因此圖 4.3(b) 黑方勝劫的流程圖中, 左分支的黑白利益差 k+x odd -(x 1 +X even ) 0 (1) 根據定理, 黑方所能獲取的最大利益為 k+x odd -(x 1 +X even ), 因此讓我們先考慮能得到最大利益的情況要獲取最大利益 k+x odd -(x 1 +X even ), 就要讓白方走到圖 4.3(b) 中的左分支, 根據 Minimax 搜尋的原則, 在黑下 b i 後白方選擇應劫或消劫當中, 必須選擇 MIN, 也就黑白利益差較小的一 6

7 邊換言之, 在右分支的利益差大於左分支的情況下, 白方若按最佳進行會選擇左分支, 如果一來我們就可以如願以償的獲取最大利益 k+x odd - (x 1 +X even ) 接著利用 Minimax 搜尋的原則接著往上層 bottom-up 計算, 每次黑方找劫材 b i, 都必須讓右分支的利益差大於或等於左分支 ( 取 MIN), 因此, 我們得到這種情況下黑方的劫材價值下限為 2(k+X odd -X even ) : b i +X even -(k+x 1 +X odd ) k+x odd -(x 1 +X even ) => b i 2(k + X odd - X even ) 接著求白方的劫材價值下限從 4.3(b) 用 Minimax 搜尋原則往上層 bottom-up 計算時, 由於白方每次找劫材黑方會選擇 MAX, 所以白方選擇的劫材 w i 只需要讓右分支的利益差小於左分支, 我方就必須選擇左邊才能獲取最大利益因此, 我們得到這種情況下白方的劫材價值下限為 2x 1 +1 : k+x 1 +X odd -(w i +X even ) k+x odd -(x 1 +X even )-1=> w i 2x 1 +1 (2) 其次, 我們考慮黑無法獲取最大利益 k+x odd -(x 1 +X even ), 卻能獲取介於 0 到 k+x odd - (x 1 +X even ) 某個數的利益的情況若黑方能獲取 k+x odd -(x 1 +X even )-1 的利益, 黑白雙方的劫材價值下限求法同 (1): b i +X even -(k+x 1 +X odd ) k+x odd -(x 1 +X even )-1= > b i [2(k+X odd -X even )]-1 k+x 1 +X odd -(w i +X even ) (k+x odd -(x 1 +X even )-1)-1=>w i (2x 1 +1)+1 比較前一種情況,b i 與 w i 範圍分別為前一個 b i 與 w i 減 1 與加 1 同理, 能獲取 k+x odd -(x 1 +X even )-2 利益的 b i 與 w i 範圍又此種情況的 b i 與 w i 減 1 與加 1 因此我們可以依序求得能獲取 k+x odd -(x 1 +X even ),k+x odd -(x 1 +X even )-1, k+x odd -(x 1 +X even )-2,,2,1,0, 利益的黑白雙方的劫材價值下限在解題方法的劫材分布二, 即用迴圈依序從獲取 k+x odd -(x 1 +X even ) 到 0 的劫材價值下限來判斷黑方所能獲取的最大利益為何 (3) 黑方無法獲取 0 目以上利益的情況, 就用獲取 0 利益黑白雙方的劫材價值下限判斷雙方劫材數時, 黑方劫材少於白方這就解題方法中的劫材分布三 II. 交換劫材與減少損失當雙方的劫材分布情況劫材分布三時, 表示黑方一定會遭受 1 目或 1 目以上的損失, 這時候就要想辦法將損失降到最低此時黑方若有價值大於 BKTVL 的劫材, 其價值又小於白於大於 WKTVL 的劫價, 便可以交換劫材舉例而言, 假設黑方雙方經過劫材價值下限的檢查後, 符合條件的劫材分別如下 : B=(25,30,40,60) W=(42,45,50,55,80) 黑方 B 中的最小的劫材價值為 25 目, 白方則為 42 目, 既然 25 比 42 小, 這時候交換就有利了, 並且白方非換不可, 因為若按照最佳下法, 白方不得不回應我方符合條件的劫材黑方用 25 目的劫材, 白方接著用 42 目的劫材, 接著黑方又發現 30 目的劫材小於白方 45 目的劫材, 於再度交換, 一直交換到黑方的符合條件的最小劫材價值大於白方的為止, 結果如下 : B=(60) ; W=(55,80) 考慮將來可能發生的另一場劫爭, 假設兩場劫爭的途中雙方的劫材都沒有增加,BKTVL 與 WKTVL 皆為 45, 結果在將來這場劫爭原本符合條件的劫材, 黑白雙方各有 1 個與 4 個, 相差 3 個劫材, 然而經過黑方在前一場劫爭交換劫材後, 雙方變成各有 1 個與 2 個, 變成相差 1 個劫材由此可知交換劫材的策略對黑方有好處的在交換完劫材, 就轉而選擇有價值棋步中最大的 x 1 或不符合條件的劫材中最大的 b u, 看哪一種下法損失比較小根據流程圖 4.3(a), 黑方選擇 x 1 與 b u, 白方消劫後的利益差分別為 x 1 +X even -(k+x odd ) 與 b u +X even -(k+x 1 +X odd ), 黑方的最佳選擇選擇利益差較大的一邊下另外在白方找劫材時, 如果白方下的劫材不符合條件的劫材, 則一種失誤, 黑方消劫即可如果符合條件的劫材, 我們可以比較此刻消劫後的利益差與黑方在選擇 x 1 與 b u 時較大的那一個利益差, 來選擇利益差較大的下法換句話說, 即比較 max(x 1 +X even -(k+x odd ), b u +X even -(k+x 1 +X odd )) 與 k + x 1 + X odd - (w i +X even ) III. 有價值棋步的循環打劫過程中, 有價值棋步的循環, 通常劫材少的一方佔取有價值棋步換劫時, 劫材多的一方仗著劫材多而搶佔有價值棋步, 等到劫材少的一方提劫後, 劫材多的一方再找劫材將劫提回來在我們的解題方法中, 倘若黑方劫材多, 黑方並沒有搶佔有價值棋步, 而選擇消劫, 在這裏有一個策略的分歧點, 關鍵的點有時候有價值的棋步會增加劫材, 也就所謂的製造劫材在圍棋對局中, 劫材少的 7

8 一方有時會藉著佔取有價值的棋步製造劫材最完美的情況, 程式有能力檢查白方下的有價值棋步會不會增加劫材, 若不會增加劫材, 則我方大可仗著劫材多而繼續搶佔有價值的棋步, 等白方提劫, 再找劫材即可然而判別有價值棋步被下了以後會不會增加劫材的搜尋深度通常很深, 複雜度很高, 因此我們的演算法選擇消劫倘若已經有判別有價值棋步會不會增加劫材的機制, 則在我方劫材多的情況下, 可以選擇搶佔大棋五結論與未來研究方向本論文中, 我們展開整個本劫打劫的流程, 利用 Minimax 搜尋的原則, 在預設擁有各種需要的盤面資訊下, 求出在目前盤面的情況下最佳的打劫策略, 巨觀的探討了本劫的打劫策略, 使電腦圍棋程式在處理本劫時, 能在局部求得獲利最大或損失最小的下法我們利用 Rule 判斷的方式決定下一步, 大大降低了搜尋所需的時間並且也詳細探討了劫材的使用策略, 將之納入我們的演算法中如果不納入損劫, 我們幾乎已經完全解決本劫的打劫問題, 接下來的首要課題便損劫的處理只要在打劫問題中考慮損劫, 整個問題便複雜許多如果按照圍棋對局常理, 損劫其他劫材都用完後才開始用, 並且從損失最小的用到損失最大的, 不過目前為止這並未被嚴謹的證明除了損劫之外, 未來的研究方向探討其他劫爭 ( 同時多個劫爭三劫寬氣劫二段劫與三段劫萬年劫等 ) 的策略, 並且可以回溯到打劫的上一層探討作劫, 所得的結果能為電腦圍棋程式在全局或局部搜尋時所利用圍棋中的擴大劫爭也一個有趣且值得討論的問題而種種基礎工作, 諸如判別劫爭的種類判別劫材與計算棋步的價值等, 不但電腦圍棋程式會不會打劫的主要關鍵, 也未來圍棋程式棋力能向上提升的重要基礎參考文獻 [4]D. Lefkovitz, A strategic pattern recognition program for the game of Go,University of Pennsylvania, the Moore school of Electrical Engineering, Wright Air Development Division, Technical note ,1-92, [5]Zobrist, A. L, A Model of Visual Organization for the Game of Go, Proc. AFIPS 1969 Spring Joint Computer Conf. 34 (Boston, Mass., May 14-16, 1969), AFIPS Press, Montvale, NJ, [6] 顏士淨, 電腦圍棋程式 Jimmy 5.0 之設計與製作, 國立台灣大學資訊工程研究所, 博士論文,1999. [7]S.C. Hsu, J.C. Yan, and H. Chang. Design and implementation of a computer Go program Archimage 1.1. Journal of Information Science and Engineering 10, pages , [8]Allis, V., Searching for solutions in games and artificial intelligence. phd thesis, University of Limburg, Maastricht, [9]Lichtenstein. D.and Sipser. M., GO is Polynomial-Space Hard, Journal ACM 27, 2 (April 1980), (Also: IEEE Symp. on Foundations of Computer Science, (1978), 48-54). [10]Mick Resis, uk/webgo/compgo.htm. [11] 陳志行, [12]Elwyn Berlekamp, and YoungHoan Kim. Where is the Thousand-Dollar ko?.games of No Chance, MSRI Publications Volume 29,1996. [13]John H. Conway. On Numbers and Games. Adademic Press, London/New York,1976. [14] 村島誼紀, 劫爭辭典, 理藝出版社,1997. [15] 林海峰, 打劫之魔力, 理藝出版社,1997. [16] 大竹英雄, 官子入門, 世界文物出版社. [17] 應昌期圍棋教育基金會, 計點制圍棋規則,1995 年版. [18] 日本棋院, 日本圍棋規則,1989. [1] 中國圍棋史話, article/china_go/china_go.htm [2] 日本近代圍棋通史, org/article/history/history.htm [3] 吳震坤, 電腦詰棋程式中處理劫爭問題之研究, 國立台灣大學資訊工程研究所, 碩士論文,

0 0 = 1 0 = 0 1 = = 1 1 = 0 0 = 1

0 0 = 1 0 = 0 1 = = 1 1 = 0 0 = 1 0 0 = 1 0 = 0 1 = 0 1 1 = 1 1 = 0 0 = 1 : = {0, 1} : 3 (,, ) = + (,, ) = + + (, ) = + (,,, ) = ( + )( + ) + ( + )( + ) + = + = = + + = + = ( + ) + = + ( + ) () = () ( + ) = + + = ( + )( + ) + = = + 0