圍棋博弈與算法研究摘要下完一局棋應有無數種供選擇的方案，加上每個棋手的興趣愛好、棋風、當時的心情、狀態的差異，我們稱它為“千古無同局”，從古至今沒有一個人下棋的手法是一模一樣的，在此我們對其進行討論并分析。文中首先討論了圍棋的起源，比如最早的圍棋程序是由 AZobrist作為他模式識別專業博士論文的一部分提出的，之后JonRyder將Zobrist的程序進行了深入的研究，并得出了自己的見解。然后將定式問題對象化，將對于每一個定式的出現方式，進行統一的處理，展示出棋盤坐標系統及其映射的一種實現方案。 接著分析次序問題，因為棋局中整個布局過程往往是在多個定式之間交錯進行的，因此可以建立容易進行檢索及匹配操作的行棋步驟表，得出行棋步驟表字符串化的一種實現方式。從效果上來講，棋子的影響模型當然是越精確越好，因此建立精細計算的影響模型，從力學模型、度量公式和棋子雙方勢力范圍分別對其進行分析，了解到利用每個點計算得到的四個方向的力及合力的大小和方向， 我們可以粗略的表示雙方的勢力范圍，力量對比，棋勢強弱等信息。因為計算各點的影響值所需的時間成為搜索總用時的最主要影響因素， 要想實現計算時間可以接受的完全搜索，必須采用更簡潔的影響模型，因此建立快速計算時使用的影響模型，得出了影響值與空點級別的關系。最后建立了棋盤模型，設計方形棋盤使三線圍成的邊部與四線圍成的中腹具有相同的地位或最小的差異， 利用數學知識中的三線點與四線點目效率相近的原則，得出了圍棋棋盤選擇19/19的網點是最佳的。關鍵字：行棋步驟表 定式問題對象化 精細計算的影響模型 棋盤模型#一、問題重述圍棋是中華民族遠古的祖先們流傳下來的一項寶貴文化遺產。縱向看，這項國寶歷經了從春秋戰國到唐宋元明清幾千年的歷史，有盛有衰，有褒有貶，源遠流長。橫向看，當中國的文化往外輻射傳播時，作為有悠久歷史的“琴、棋、書、畫”也隨之傳向了海外。在藝術領域中，與它的姊妹藝術“琴、書、畫”相比，棋文化受關注的程度要少很多，鄭重其事作研究探討的文獻、文章所見也不多。時至今日，恰如許多中國文化的其他方面一樣，知其然而不知其所以然。因為下完一局棋應有無數種供選擇的方案 （這是一個天文數字 ）,加上每個棋手的興趣愛好、棋風、當時的心情、狀態的差異 ,我們稱之為“千古無同局”文中主要討論什么是圍棋算法？如何進行面向對象的改造，建立對象模型？請收集材料建立其相應的匹配算法。二、問題分析圍棋是一項智力性很強的智力性活動，它的起源說法很多，比如最早的圍棋程序是由A.Zob門琳為他模式識別專業博士論文的一部分提出的，之后JonRyder將Zobrist的程序進行了深入的研究，得出了自己的見解。然后將整個定式問題看作一個對象 ,定義為CGoFormulary類，對于每一個定式的8種出現方式,我們進行統一的處理，展示出了棋盤坐標系統及其映射的一種實現方案。圍棋定式的展開次序具有很大的不確定性 ,所以整個布局過程往往是在多個定式之間交錯進行的，因此建立易于進行檢索及匹配操作的行棋步驟表，然后得出行棋步驟表字符串化的一種實現方式。接著建立精細計算的影響模型，從力學模型、度量公式和棋子雙方勢力范圍求得結果，同時建立快速計算時使用的影響模型，得出影響值與空點級別的關系。最后建立了棋盤模型，設計方形棋盤使三線圍成的邊部與四線圍成的中具有相同的地位或最小的差異，應用搜集到的材料和所學的數學知識，解決其問題。三、模型假設假設一：假設下棋時不受外界的影響。假設二：假設有足夠多的黑白子圍棋。假設三：假設下棋的兩人能力一樣。

假設四：假設棋盤足夠大能夠容納足夠多的棋子四、符號說明符號符號說明總控制力平衡度黑子的扳位白子的扳位空交叉點遍歷棋子FB占有強度SFB形勢評估函數卜了某子之后形勢改變的度量x,y默認坐標系x,,y,符號符號說明總控制力平衡度黑子的扳位白子的扳位空交叉點遍歷棋子FB占有強度SFB形勢評估函數卜了某子之后形勢改變的度量x,y默認坐標系x,,y,各定式區坐標系五、模型的建立與求解布局研究人類棋手在選擇布局走法時，通常會使用定式，定式是經過幾千年經驗積累所得出的合理布局走法，精通定式變化是人類棋手棋力進階的必由之路 ，事實上在圍棋程序領域,引入了定式庫的程序也會在布局階段具有明顯優勢。因此，如何識別并選擇定式，是布局階段的核心問題。圍棋起源階段最早的圍棋程序是由A.Zobrist作為他模式識別專業博士論文的一部分提出的。Zobrist引入了影響函數的方法將棋盤分為黑方和白方地域。Zobrist的影響函數計算棋盤上每一個交叉點的數值，黑子取值+50,白子取值-50而空白點為0;正數效果的點要給其鄰接點加+1,同樣負數效果的點給鄰點加-1,這樣的算法遞歸執行4次，將棋盤最終數值化，如圖：32 42 4 81 2 6 102 4 832 42 4 81 2 6 102 4 82 421.根據Zobrist影響模型，一個黑子對其周圍輻射的影響6 4 210 8 4 262 10 6 2 110 8 4 26 4 22 2一個黑子對其周圍輻射的影響而JonRyder的程序是Zobrist研究的深入，這也是他的博士論文內容。像Zobrist一樣，Ryder也使用了一個影響函數，用來將每個棋子對其周圍產也是黑方取正數，白方取負數，某點影響的取值由其鄰點的影響傳播累加形成。Ryder的影響函數較Zobrist的簡單，傳播系數是固定的。1313601313生的影響進行量化。他的影響函數與 也是黑方取正數，白方取負數，某點影響的取值由其鄰點的影響傳播累加形成。Ryder的影響函數較Zobrist的簡單，傳播系數是固定的。1313601313.根據 Ryder影響模型，一個黑子對其周圍輻射的影響Ryder定義了兩個術語：聯絡和強關聯。某點對于某方聯絡 ,對于有子點而言，是指該點上是該方的非死子；對于空白點而言，是指該點至少有一個該方鄰子且沒有對方鄰子。完全聯絡的一個延伸定義為半聯絡，指一個空白點至少有兩個某方鄰子及至少一個對方鄰子，有三種情況被認為是強關聯的。某點由某方子占據或與某方子連接，某點與某方子對角線連接且共有至少一個空白點，尖以及某兩子之間只間隔一個空白點，棋塊就是由一組聯絡或半聯絡的點組成的。影響函數與聯絡度相結合來確定棋勢。對于一組聯絡的點，如果其影響函數的值不小于程序預定義的一個閾值，則組成棋勢。5.1.2定式問題對象化基本目標：將整個定式問題看作一個對象，并定義為CGoFormulary類，很顯然，該類必然應具備的功能是：給定一個局血，根據定式知識，返回下一步應手，這一功能可以定義為CGoFormulary類的一個方法CGoFormulary::GetNextStep()。對稱問題：圍棋棋盤具有多種對稱屬性，首先，在以天元為原點的坐標系統中四個象限之間具有對稱關系；其次,每一象限內部還都具有以經過天元的對角線為對稱軸的對稱關系，如圖所示，同一個定式，可以有8種出現形式：圖3.象棋的8種形式可見，我們需要把棋盤劃分為4個定式區，每個定式區還包含一個定式向哪個方向展開的特征，這一特征可能有兩種狀態：順時針或者逆時針。對于每一個定式的8種出現方式，我們進行統一的處理，所以，坐標映蔚是必然需要的。例如將左上角順時針作為定式的默認方式，我們就需要在其他各種方式與默認方式之間建立一對轉換方法，這一對方法可以定義為：CGoFormulary::MapToDefault()、CGoFormulary::MapToFactual()下圖展示了棋盤坐標系統及其映射的一種實現方案 ：：

012340123456789101112131415T61718圖4.棋盤坐標系統及其映射棋盤默認為以左上角為原點，19*19的坐標系統,而各個定式區又分別屬于以各自擁有的角為原點，10*10的子坐標系統。而從各定式區坐標系（x，,y，）到默認坐標系（x,y）的轉換關系為：第一象限 x，=x y第一象限 x，=x y，=y如圖中a點第二象限x，=18-y y，=x如圖中B點第三象限x，=y y，=18—x如圖中C點第四象限 x第四象限 x，=18-xy，=18-y 如圖中D點而各定式區內逆時針（x，，y，）與順時針（x，y）的轉換關系為：x，=y，y，=x5.1.4次序問題圍棋定式的展開次序具有很大的小確定性，首先，因為在某一定式區內的定式步驟尚未完畢之前，雙方可能暫時中斷而轉戰至另一定式區，所以整個布局過程往往是在多個定式之間交錯進行的。其次，被中斷的定式區在棋局的后續發展中也可能出現三種不同的情況 ：其一是回到該定式區時行棋次序與離開時一致，則定式繼續；其二是次序顛倒而導致定式終止;其三是次序顛倒后仍然符合定式步驟，這種定式屬于含有脫先變化的特殊定由于各定式往往交錯進行，所以，各定式區都必須維護一個行棋步驟表來記錄本區內的定式進行過程，可以定義為：Areali].StepsI]0由于定式可能處于中斷、終止或脫先等多種狀態 ，所以各定式區還需要增設一個屬性來標記自身的狀態，可以定義為：ArealiI.State。由于各定式區處于何種狀態，取決于區內的行棋步驟是否符合定式，因此，我們需要一個方法來進行判斷，這一方法可以定義為：CGoFormulary::IsFormulary()該方法進行判斷的依據只能是定式區行棋步驟表 Area【1.Steps因此，行棋步驟表所采用的數據結構應該是易于進行檢索及匹配操作的。顯然 ，字符串是最佳選擇，下圖給出了行棋步驟表字符串化的一種實現方式上圖顯示了在第2定式區順時針展開的一個含有脫先手的定式，如果將每手棋用相對于定式區子坐標系的兩個字母表示，則：TOC\o"1-5"\h\z1=DD 6=BD 11=XX2=CF 7=BE 12=JC3=FC 8=BC 13=EC

4=CC9=CE14=FB4=CC9=CE14=FB5=CD10=EB 15=GC其中，第11手黑棋脫先，無法用定式區子坐標系表示，而對于脫先手，由于其必然在其他定式區有表示并有記錄，所以可以一律記作XX由此，圖中定式即可用一個字符串表示為:DDCFFCCCCDBDBEBCCEEBXXJCECFBGC。定式問題對象化建立一個可供程序檢索及匹配的定式庫，該庫應該記錄各種定式及其各類變化。定式庫應該指出每種定式變化對于先手方或者后手方的有利或不利程度。 定式庫應該指出每種定式變化所依賴的局面條件。庫結構定式庫通常應用于教學演示日的，通常表現為森林結構：圖6.森林結構圖圖6.森林結構圖森林結構的特點是冗余數據少，非常適合整體或部分加載到內存然后使用遍歷算法訪問，但不適合快速匹配。如果將森林中每一條從根到葉子的路徑都抽取出來組成一個列表，則該列表雖然含有大量冗余數據（根及枝條多次重復儲存）,但非常適合于快速檢索匹配：

圖7圖7.快速檢索匹配圖優先級問題在同一局而下，往往具有多種定式可供選擇，而這些定式之間很難判定優劣，通常只是因對手而異：對手的棋力及棋風決定著選用某一定式所能達到的最終效果。顯然，最恰當的做法是主動適應對手。特別地，當對手本身也是程序時，由于可以進行大量的自動對局來積累經驗，所以對定式設定優先級，并針過實際對局結果修正該優先級，就可能大大提高對特定程序對手的對抗能力。因此，在定式庫設計及定式匹配算法設計中引入自適應的優先級設置，是當然之選。精細計算的影響模型從效果上來講，棋子的影響模型當然是越精確越好。需要以此為基礎建立分塊模型，用來作為戰斗單位的是棋塊而不是單獨的棋子。棋局中計算實地外勢，或者簡單計算棋塊的活力，強弱都會與棋子的影響模型有關。步著手時都要計算上百次或更多,義與計算簡便之間找到平衡點。而另一方面，由于影響模型在計算評估函數時要用到，評估函數在計算每一所以影響模型又不能過于復雜，必須在精確定步著手時都要計算上百次或更多,義與計算簡便之間找到平衡點。力學模型棋盤上的每一個棋子，都向周圍四個方向發出影響。通過這種影響實現對空點的占領和棋子之間的相互作用，這種影響可以被視為一種控制力沿四個方向大小相等，而黑白棋子產生的控制力符號相反。控制力產生后，沿它的方向向前傳播，其傳播方式遵守如下定律：遞減定律：控制力遇到一個點后，力的大小被減弱，符號方向不變的繼續向前傳播。如果遇到空點，減弱后的控制力變為原來的一個常數倍，該常數被稱為傳播率；如果遇到有子點，沿原方向的控制力消失。折射定律：控制力遇到一個點后，產生與控制力方向相垂直的兩個新的控制力，這兩個力符號與原控制力相同，方向相反，大小相等，為原控制力的一個常數倍，該常數被稱為折射率。反射定律：控制力到達棋盤邊緣后，會被反射回來，該反射力與原控制力方向相反，符號相同，大小為原控制力的一個常數倍該常數被稱為反射率。每一個點都受到四個方向的控制力的作用，任一方向的控制力的大小是這個點所受這個方向所有控制力的代數和。由于這種疊加類似于力的疊加原理，所以這種模型被稱為“力學模型”。在實際計算時，我們取：任意棋子產生的初始控制力的大小為 32；黑子的影響為正、白子的影響為負；傳播率為1/2;折射率為1/4；反射率為1;初始控制力的大小取為2的幕，而傳播率取為1/2,折射率取為1/4,就使各級影響值均為整數，避免了小數運算。圍棋程序因要計算很多問題，宜盡量節省計算時間，因此此處只用整數運算。度量公式在得到任一棋盤狀態下各空點影響的分布圖后，可以由這些影響值經過計算得到一些棋盤狀況的深層信息，一些常用的度量公式如下：設一個點受到的四個控制力大小為：向上F0;向右F1;向下F2;向左F3。總力：A=F0F1F2F3 (1)表示一個點受到某一方影響的度量。A>0受黑的影響強一些。

A<0受白的影響強一些。A=0受雙方的影響基本平衡。模：F),F),F02F12F22F32(2)表示一個空點受到棋子影響的強度。F很大，表示這一點受子的影響已經很強，常常是官子價值較小的位置。F很小，表示這一點受子的影響還很弱，常常是大場。平衡度：B=12 2F0-F2F1-F32FB=12 2F0-F2F1-F32FF1+F3—F0-F2F0+F1+F2+F3表示在一個點上四個方向的力互相平衡的程度，變化范圍 0~1。B很大，表示在某方的控制范圍內。B很小，表示在雙方控制范圍的交界線上。占有強度：FB=FB (4)表示一點作為某方實空的現實程度。FB很大，已是某方的實空了，這樣的位置雙方一般是不下子的。FB很小，有幾種情況：F很小，表示這一點是大場； F很大，B很小，表示這一點是雙方的分界線。形勢評估函數：SFB=￡F(sign(A,F*B)十￡g(color,狀態) (5)空點 有子點其中，F函數的作用是對FB值進行圓滑處理，尤其對于FB值很大的點,當FB值超過一定數值，該點已經被某方占有了，FB值再大已失去其數值意義,應當進行規格化。g函數的作用是對盤面上的死子進行處理， g函數的一個例子如下:(6)1

gx,p=(6)-1g函數還可以更加細化的處理處于安全，死亡之間的狀態。SFBa0,表示盤面黑棋優勢；SFB<=0,表示盤面白棋優勢。一手棋的價值：△SFB=下子之后的SFB—下子之前的SFB(7)表示下了某子之后形勢改變的度量，也就是這一手的價值。在無急場的情況下，選擇價值大的點落子。5.3.3判定雙方勢力范圍對每一空點，它受到的總控制力A=F0+F1+F2+F3,當A大于某一數值n時，將其規格化為n(T)。當A>0時受黑的影響強一些，該點能否被黑方所控制，能否算作黑方實地，按照以下規則判定：.如果該點所受四個方向的力均大于1,則該點為黑方勢力范圍；.如果該點所受四個方向的力均大于0,且A大于10,則該點為黑方勢力范圍；.如果該點的A值大于規格化最大值n的2/3,則該點為黑方勢力范圍；.如果該點為黑方勢力范圍，且所受四個方向的力均大于 1,其中3個方向的力大于2,則該點為黑方實地；.如果該點為黑方勢力范圍，且所受四個方向的力均大1,A值大于34則該點為黑方實地。對于白方的勢力范圍與實地有類似的判斷規則。利用力學模型，建立多層塊結構，以FB的值為基礎，根據FB值的范圍，建立起多級的塊，過程如下：.每個棋子建立一個零層(最底層塊)；.如果相鄰，兩個零層塊屬于同一個一層塊；.如果兩個i層塊之間可以找到這樣一個路徑相通：路徑上的任一點的FB值大于某一與i相關的設定值(在實現時根據經驗選取)，則兩個i層塊同屬于一個i+1層塊；.如果i+1層塊只有一個則結束，否則重復3o利用這個力學模型，分析一些簡單的常用走法，利用每個點計算得到的四個方向的力及合力的大小和方向，可以粗略的表示雙方的勢力范圍，力量對比，棋勢強弱等信息。棋子產生的影響用控制力的形式來表示，多個棋子的作用被看作是單個棋子作用的簡單疊加，當棋子有一定的距離時，這種疊加是有道理的。但是當棋子相近或相連時，單純的疊加已經不能近似實際情況。5.3.4快速計算時使用的影響模型在搜索棋塊的死活狀態時，需要確定一些與眼位有關的空點處于哪方的控制之下，此時，計算各點的影響值所需的時間成為搜索總用時的最主要影響因素，要想實現計算時間可以接受的完全搜索，必須采用更簡潔的影響模型。應用于快速計算的影響模型，首先按照空點對棋子的位置關系定義了以下的級別劃分：鄰位A的級別為1;關位B的級別為2;斜鄰位C的級別為1.5;小飛位D的級別為2.5o若雙方棋子相連，F是黑子的扳位，對于黑子級別為2;E是白子的扳位，對于白子級別為2。某色棋子對某空點的影響僅決定于離該點最近（即具最小級別數）的該色棋子，影響值如下表所示：表1.影響值與空點級別的關系空點級別11.522.5黑子影響6532白子影響-6-5-3-2黑白影響可以互消，所有點計算完畢，再根據以下規則進行圓滑處理某點影響值的代數和為1或-1,則取為0;與0或負影響相鄰的點，其影響值不得超過3；與1或2相鄰的點，其影響值不得超過5;負值（白子影響）有類似的規則。在實際計算時，遍歷所有的空交叉點（個數為m）而不是像前面的影響模型計算時遍歷棋子（個數為n）。如果遍歷棋子，一個棋子影響的空點有4+4+4+8=20個，需計算nx20次，每次都要判斷該棋子對此空點的影響值是否最大；而遍歷空點則只需計算mwx（x<20）次，從空點出發由近及遠，遇到第一個棋子（黑白各一次）就可以停止計算。5.4棋盤模型的建立為了對圍棋問題建立數學模型，需首先對圍棋棋子價值有個數學描述，為此我們給出如下定義：對于一塊成活型棋塊，用它的棋子數去除這些棋子所包含的目數，得到的商值稱為此棋塊的目效率，記為PE。可以看出，目效率表示單位棋子所占的目數，即表示此棋塊平均占有目數的能力下面利用此概念對圍棋棋盤問題建立模型。圍棋的棋盤由古時的每邊11道增至現在的每邊19道，其間歷經數千年。這種進化的過程也顯示著人們的認識逐漸接近真理。 古人在不貼子的情形下仍可公平對弈,說明先下的一方占的便宜不會太大可以推測，圍棋內部一定存在兩種抗衡的力量，使先手即使先落子也無法取得多少優勢。一般的棋類（如象棋），往往有攻有守，攻守之間有一種平衡，而且隨時可以轉換，因此，先手一方即使先進行攻擊也未必得勝。由此可以說，一般棋類之所以變化無窮，根本原因在其包含了攻與守這既對立又統一的兩個方面。它們在勝負的天平上地位相同，相互抑制，一切取勝的走法或定式不過是圍繞著攻與守， 以攻為守，或以守為攻來進行罷了。圍棋亦如此，但圍棋的攻守（攻為欲殺死對方，守為不被對方殺死）卻顯然不同于其它棋類，由于弈棋雙方輪換落子，因此，單純為殺死對方而進行攻擊要比防守來得困難。就是說，圍棋里的攻與守無法取得相同的地位，因此，絕不能把圍棋也認為是攻與守的對立統一體。但圍棋那樣富于變化從根本上講，其內部一定存在著兩種力量的抗衡。這兩種力量既可以對抗，又可隨時轉換。象棋的兩個對立面之所以是攻與守，無非是緣于其取勝規則為吃掉對方的將（帥），不進攻當然不行。因此，在確定圍棋中對抗的兩種力量時必須意識到：這兩種力量抗爭的最終目的與圍棋的目的應是統一的，即多占地盤。首先，我們把圍棋棋盤按區域特點籠統地分為邊部和中腹。從做活和占地兩個角度看，邊部因空間受阻而易受攻擊，但可利用邊部成目快的特點迅速做活，有根據地后再圖發展，中腹則由于四方皆可發展，不容易受到攻擊，做活便退居其次，而先去搶占空間。由此可見，邊部和中腹將成為圍棋中的兩種對抗的勢力，除此之外，還應保證兩種勢力所具有的價值相同，從而使二者能夠真正地進行抗衡，這是必要的，否則，無論偏重哪一方，圍棋都會成為單一凈奪邊部或中腹的乏味游戲,而且使先手棋獲益頗大。前面在討論三線的作用時，曾經指出三線控制邊部的優勢。顯然，控制中腹的重任無疑落到了緊鄰的四線上。這樣，問題最終可化為：怎樣設計方形棋盤（即每邊選取多少道）使三線圍成的邊部與四線圍成的中腹具有相同的地位或最小的差異？圖9.方形棋盤每邊19道時的情形三線點、四線點設置如圖9（此時棋盤每邊道數為19）,設三線點、四線點組成的棋塊的目效率分別為PE3,PE,。根據三線與四線目效率相近的原則，我們提出本節的數學問題：方形圍棋棋盤每邊設置多少道數,將使E=PE4-PE3的絕對值最小？5.4.1模型的求解假設棋盤每邊為x道，x為自然數。為了實用的需要，圍棋棋盤不宜太大，也不宜太小，設11Wx^23。參照圖9（此時x=19）,由于對x的限制，三線圍成的邊及四線圍成的中腹已成為實空，對方無法在其中做活這樣。所有三線圍成的目數為：8x-16其目效率為：四線圍成中腹的目數為:PE38x-164x—20四線圍成中腹的目數為:PE38x-164x—20(8)2，,一，、-(x—8)其目效率為:PE_Zz814-4x-28兩目效率之差為:Ex=PE4-PE3Ex=PE4-PE3(x-8f4x-288x-164x-20(10)對于PE3,如果把x看做連續變量，可以看出它是關于x的單調下降函數，因為這是PE3可改寫成:PE38x-16PE38x-168x-5 24c62

4x-20 4x-5x-5(11)同理，對PE4有:2 2x-8x-7-2x-7 1pe42 2x-8x-7-2x-7 1pe4= = 4x-7 4x-7x-714 21+ 4x-7(12)將PE4關于x求導得:TOC\o"1-5"\h\z1 1PE4x=4-K (13)由x-7>1,從而(PE4x>0,即PE4關于x單調上升，這將導致E(x)也關于x單調上升，因而，對于方程E(x)=PE4-PE3=0,若有解，其解也只能有一個，又由于；E18=-0.1888,E19=0.092 (14)故由連續函數介值定理，E(x)=0的解在開區間(18,19)中，顯然其解非整數，而我們尋求的是使|E(x)最小的整數解，由E(x)的單調性及同19卜忙(18),即知x=19將使E(x|最小。因此，我們用三線點與四線點目效率相近的原則證明了圍棋棋盤選擇 19M19的網點是最佳的。六、模型的評價與推廣圍棋在生活中隨處可見，平時的家庭生活又或者國際比賽中，它經常被廣泛的應用于各種比賽。我們也可以根據建立的圍棋模型，結合生活中的實際情況，學習相應的數學知識與技能。優點：本文建立的模型能夠與實際精密聯系，結合實際情況對問題進行了求解，使得模型具有很好的通用性和推廣性。本文模型的計算采用了專業的數學軟件，可信度較高。本文應用了正確的數據處理方法，很好的解決了小數取整的問題。缺點：本文沒有很好的把握重心，讓人感覺文章有點散。本文在模型建立的過程中引入的變量較多，不利于編程處理。七、參考文獻.馬凈，經久不衰的魅力，文化藝術出版社，1989年.姜啟源，數學模型，高等教育出版社，北京，1987年.杜維新，圍棋布局基礎，《成都棋苑》編輯委員會，1985年.吳清源，圍棋高級死活，1991.曹文君，知識庫系統原理及其應用，1995.程慧霞，用C+碇造專家系統，1995八、附錄附錄一：/*************************************************/TOC\o"1-5"\h\z//文件名：Go.h //////用途：圍棋 程序對弈類庫頭文件。////版本：V0.1 ////版權:伍白楊 ////日期：2014年11月 ///*************************************************/#pragmaonce#defineHUMAN0#defineCOMPUTER#defineCLOSEDdefineBLACK0defineWHITE1defineBLANK2defineFRAME3defineUP0defineDOWN1defineLEFT2defineRIGHT3defineLTOP4defineRTOP5#defineLBOT6#defineRBOT7#definePROLOG0#defineMIDRUN1#defineFINALE2template<classT>classCGoNodepublic;CGoNode();CGoNode<Tvalue,CGoNode*next=NULL>;tTvALUE;CGoNode*pNext;};classCGoStringpublic;CGoString(intnintc);~CGoString();intnColor;intnDots;intnPeps;intnEyes;CGoNode<int>*pDotHead;CGoNode<int>*pPepHead;voidTakePep(intn);voidLosePep(intn);voidLink(CGoString*str);};classCGoLonk{public;CGoLink();~CGoLink();intnType;CGoString*pBegin;CGoString*pEnd;intnBegin;intnEnd;}classCGoDragon{public;CGoDragon();'CGoDragon();intnFields;intnViablility;CGoString*pBase;CGoNode<CGoString*>*pStringHead;CGoNode<CGoLink*>*pLinkHead;CGoNode<int>*pFieldHead;intLiveExam();intExpand();intDefend();};classCGoFormularypublic;CGoFormulary();'CGoFormulary();_ConnectionPtrpConnect;_RecordsetPtrpRecordest;intnStste[4];CStringsSteps[4];CStringMapToFormulary(intn,intarea);intMapToStep(CStrings,intarea);CStringSyometrical(CStrings);intIsFormulary(CStrings);CStringGetNextStep(CStrings,CStringterm);voidUpdateState(intn;intcolor);intChoseStep(intcolor,intarea);};classCGoPoint{public;CGoPoint();CGoString*pString;intnForce[2];intnHolder;};classCGo{public;CGo();~CGo();CGoPointDots[361];intnSteps;intStepList[1000];intnFields[2];intnSeesawPoint;intnStage;CGoFormulary*pForm;voidReset();intCheck(intn,intdir);voidUpdateForce(intn,intc,intkill=0);intKillString(intn);intCanGo(intn);intTryGo(intn);voidGo(intn);voidReGo();intComputerChoice();voidEstimateFields();};#include"stdafx.h"#include"Sieger.h"#include"GoDlg.h"#include"Go.h"staticUINTWM_COMPUTER_DONE=RegisterWindowMessage("User");HANDLEhComputerInvolve;HANDLEhComputerDo;CGo*pBoard;UINTComputerThink(LPVOIDparam){while(WaitForSingleObject(hComputerInvolve,0)==WAIT_OBJECT_0){WaitForSingleObject(hComputerDo,INFINITE);if(WaitForSingleObject(hComputerInvovle,0)!=WAIT_OBJECT_0)return0;intn=pBoard->ComputerChoice();ResetEvent(hComputerDo);::PostMessage((HWND)param,WM_COMPUTER_DONE,n,0);}return0;}IMPLEMENT_DYNAMIC(CGoDlg,CDialog)BEGIN_MESSAGE_MAP(CGoDlg,CDialog)ON_WM_PAINT()ON_WM_LBUTTONDOWN()ON_BN_CLICKED(IDC_BUTTON_Black,OnBnClickedButtonBlack)ON_BN_CLICKED(IDC_BUTTON_White,OnBnClickedButtonWhite)ON_BN_CLICKED(IDC_Start,OnBnClickeedStaet)ON_BN_CLICKED(IDC_ReStart,OnBnClickedRestart)ON_BN_CLICKED(IDC_BUTTON_UNDO,OnBnClickedButtonUndo)ON_BN_CLICKED(IDC_BUTTON_SAVE,OnBnClickedButtonSave)ON_BN_CLICKED(IDC_BITTON_LOAD,OnBnClickedButtonLoad)ON_REGISTERED_MESSAGE(WM_COMPUTER_DONE,OnComputerDone)ON_BN_CLICKED(IDC_BUTTON_FORCE,OnBnClickedButtonForce)END_MESSAGE_MAP()BOOLCGoDlg::OnInitDialog(){CDialog::OnInialog();m_pBlackBrush=newCBrush;m_pWhiteBrush=newCBrush;m_pBlackBrus->CreateSolidBrush(0);m_pWhiteBrush->CreatesolidBrush(0xffffff);m_nRoles[BLACK]=HUMAN;m_nRoles[WHITE]=HUMAN;m_nStart=0;m_nState=0;m_LoadFile="";m_Button_Blick.SetWindowText(_T("人"));m_Button_White.SetWindowText(_T("人"));m_Button_Start.SetWindowText(_T("開始"));m_Button_Force.SetWindowText(_t("形式(關)"));hComputerInvolve=CreateEvent(NULL,TRUE,FALSE,NULL);hComputerDo=CreateEvent(NULL,TRUE,FALSE,NULL);EesetEvent(hComputerInvolve);ResetEvent(hComputerDo);retureTRUE;}voidCGoDLG::DoDataExchange(CGataExchange*pDX){CDialog::DoDataExchange(pDX);DDX_Control(pDX,IDC_BUTTON_Black,m_Button_Black);DDX_Control(pDX,IDC_BUTTON_White,m_Button_White);DDX_Control(pDX,IDC_Start,m_Button_Start);DDX_Control(pDX,IDC_ReStart,m_Button_ReStart);DDX_Control(pDX,IDC_BUTTON_UNDO,m_Button_Undo);DDX_Control(pDX,IDC_BUTTON_SAVE,m_Button_Save);DDX_Control(pDX,IDC_BUTTON_LOAD,m_Button_Load);DDX_Control(pDX,IDC_BUTTON_FORCE,m_Button_Force);}CGoDlg::'CGoDlg(){deletem_pBlackBrush;deletem_pWhiteBrush;CloseHandle(hComputerInvolve);CloseHandle(hComputerDo);}intCGoDlg::GetTurn(){if(!m_nStart)rturnCLOSED;inti=Board.nSteps%2;if(m_nRoles[i])returnCOMPUTER;elsereturnHUMAN;}voidCGoDlg::OnPaint(){CPaintDCdc(this);CDCMemDC;MemDC.CreateCompatibleDC(NULL);MemBitmap.CreateCompatibleBitmap(&dc,400,400);MemDC.SelectObject(&MemBitmap);MemDC.FillSolidRect(0,0,400,400,0xff9999);CRectrect(19,19,382,382);MemDC.FrameRect(&rect,m_pBlackBrush);for(inti=1;i<20;i++){MemDC.MoveTo(20,I*20);MemDC.LineTo(380,i*20);MemDC.MoveTo(i*20,20);MemDC.LineTo(i*20,380);}MemDC.SelectObject(m_pBlackBrush);for(i=0;i<9;i++){MemDC.Ellipse(i%3*120+77,i/3*120+77,i%3*120+83,i/3*120+83);}for(i=0;i<361;i++){if(Board.Dots[i].pString){if(Board.Dots[i].pString->nColor==BLACK)MemDC.SelectObject(m_pBlackBrush);elseMemDC.SelectObject(m_pWhiteBrush);MemDC.Ellipse(i%19*20+10,i/19*20+10,i%19*20+30,i/19*20+30);}elseif(m_nState){if(Board.Dots[i].nHolder==BLACK){MemDC.SelectObject(m_pBlackBrush);MemDC,Ellipse(i%19*20+15,i/19*20+15,i%19*20+25,i/19*20+25);}elseif(Board.Dots[i].nHolder==WHITE)MemDC.SelectObject(m_pWhiteBrush);MemDC.Ellipse(i%19*20+15,i/19*20+15,i%19*20+25,i/19*20+25);}}}if(Board.nSteps){intn=Board.nSteps-1;i=Board.StepList[n];if(n%2)MemDC.SelectObject(m_pBlackBrush);elseMemDC.SelectObject(m_pWhiteBrush);MemDC.Ellipse(i%19*20+15,i/19*20+15,i%19*20+25,i/19*20+25);}dc.BitBlt(0,0,400,400,&MemDC,0,0,SRCCOPY);MemBitmap.DeleteObject();MemDC.DeleteDC();}voidCGoDlg::OnLButtonDown(UINTNflags,CPointpoint){if(GetTurn()!=HUMAN)return;if((point.x<10)||()point.x>=390)||(point.y<10)||(point.y>=390))return;intx=(point.x-20)/20;inty=(point.y-20)/20;if((point.x>20)&&(point.x%20>10))x++;if((point.y>20)&&(point.y%20>10))y++;intn=y*19+x;if(!Board.CanGo(n))return;Board.Go(n);Inva;idate(FALSE);if(GetTurn()==COMPUTER)SetEvent(hComputerDO);elseResetEvent(hComputerDO);CDialog::OnLButtonDown(nFlags,point);}voidCGoDlg::OnBnClickedButtonBlanck(){if(m_nRoles[BLACK]==HUMAN){m_Button_Black.SetWindowText(_T("機"));m_nRoles[BLACK]=COMPUTER;}else{m_Button_Black.SetWindowText(_T("人"));m_nRoles[BLACK]=HUMAN;}Invalidate(FALSE);}voidCGoDlg::OnBnClickedButtonWhite(){if(m_nRoles[WHITE]==HUMAN)m_Button_White.SetWindowText(_T("機"));m_nRoles[WHITE]=COMPUTER;}else{m_Button_White.SetWindowText(_T("人"));m_nRoles[WHITE]=HUMAN;}Invalidate(FALSE);}voidCGoDlg::OnBnClickedStart(){m_nStart=1-m_nStart;if(m_nStart){m_Button_Start.SetWindowText(_T("暫停"));m_Button_Black.EnableWindow(FALSE);m_Button_White.EnableWindow(FALSE);m_Button_ReStart.EnableWindow(FALSE);m_Button_Undo.EnableWindow(FALSE);m_Button_Force.EnableWindow(FALSE);m_Button_Save.EnableWindow(FALSE);m_Button_Load.EnableWindow(FALSE);if(m_nRoles[BLACK]||m_nRoles[WHITE]){PbOARD=&Board;SetEvent(hComputerInvolve);HWNDhWnd=GetSafaeHwnd();AfxBeginThread(ComputerThink,hWnd);if(GetTurn()==COMPUTER)SetEvent(hComputerDo);elseResetEvent(hComputerDo);}}else{pBoard=NULL;m_Button_Start.SetWindowText(_T("開始"));m_Button_Black.EnableWindow(TRUE);m_Button_White.EnableWindow(TRUE);m_Button_ReStart.EnableWindow(TRUE);m_Button_Undo.EnableWindow(TRUE);m_Button_Force.EnableWindow(TRUE);m_Button_Save.EnableWindow(TRUE);m_Button_Load.EnableWindow(TRUE);ResetEvent(hComputerInvolve);SetEvent(hComputerDo);}Invalidate(FALSE);}voidCGoDlg::OnBnClickedRestart(){Board.Reset();Invalidate(FALSE);voidCGoDlg::OnBnClickedButtonUndo(){intn=Board.nSteps-2;Boerd.Reset();for(inti=0;i<n;i++){Board.Go(Board.StepList[i]);}Invalidate(FALSE);}voidCGoDlg::OnBnClickedButtonForce(){m_nState=1-m_nState;if(m_nState)m_Button_Force.SetWindowText(_T("形式(開)"));elsem_Button_Force.SetWindowText(_T("形式(關)"));Invalidate(FALSE);}voidCGoDlg::OnBnClickedButtonSave(){CStringoutfile;CFileDialog*pFileDlg=newCFileDialog(FALSE,"go",m_LoadFile,OFN_OVREWRITEPROMPT,"Go",Files|*.go||",this|);INT_PTRnResp=pFileDlg->DoModal();if(nResp==IDOK)outfile=pFileDlg->GetPathName();else{deletepFileDlg;return;}deletepFileDlg;CFile*pOoutFile=newCFile();if(!pOutFile->Open(outfile,CFile::modeCreate,CFile::modeWnite)){AfxMessageBox("文件無法打開")；deletepOutFile;return;}pOutFile->SetLength(0);pOutFile->SeekToBegin();charch[2];for(inti=0;i<Board.nSteps;i++){ch[0]=Board.StepList[i]%19+'A';ch[1]=Board.StepList[i]/19+'A';pOutFile->Write(ch.2);}pOutFile->Close();deletepOutFile;}voidCGoDlg::OnBnClickedButtonLoad(){CFileDialog*pFileDlg=newCFileDialog(TRUE,"go",NULL,OFN_HIDERE