圍棋博弈與算法研究

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

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

012340123456789101112131415T61718圖4.棋盤坐標(biāo)系統(tǒng)及其映射棋盤默認(rèn)為以左上角為原點，19*19的坐標(biāo)系統(tǒng),而各個定式區(qū)又分別屬于以各自擁有的角為原點，10*10的子坐標(biāo)系統(tǒng)。而從各定式區(qū)坐標(biāo)系（x，,y，）到默認(rèn)坐標(biāo)系（x,y）的轉(zhuǎn)換關(guān)系為：第一象限 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點而各定式區(qū)內(nèi)逆時針（x，，y，）與順時針（x，y）的轉(zhuǎn)換關(guān)系為：x，=y，y，=x5.1.4次序問題圍棋定式的展開次序具有很大的小確定性，首先，因為在某一定式區(qū)內(nèi)的定式步驟尚未完畢之前，雙方可能暫時中斷而轉(zhuǎn)戰(zhàn)至另一定式區(qū)，所以整個布局過程往往是在多個定式之間交錯進行的。其次，被中斷的定式區(qū)在棋局的后續(xù)發(fā)展中也可能出現(xiàn)三種不同的情況 ：其一是回到該定式區(qū)時行棋次序與離開時一致，則定式繼續(xù)；其二是次序顛倒而導(dǎo)致定式終止;其三是次序顛倒后仍然符合定式步驟，這種定式屬于含有脫先變化的特殊定由于各定式往往交錯進行，所以，各定式區(qū)都必須維護一個行棋步驟表來記錄本區(qū)內(nèi)的定式進行過程，可以定義為：Areali].StepsI]0由于定式可能處于中斷、終止或脫先等多種狀態(tài) ，所以各定式區(qū)還需要增設(shè)一個屬性來標(biāo)記自身的狀態(tài)，可以定義為：ArealiI.State。由于各定式區(qū)處于何種狀態(tài)，取決于區(qū)內(nèi)的行棋步驟是否符合定式，因此，我們需要一個方法來進行判斷，這一方法可以定義為：CGoFormulary::IsFormulary()該方法進行判斷的依據(jù)只能是定式區(qū)行棋步驟表 Area【1.Steps因此，行棋步驟表所采用的數(shù)據(jù)結(jié)構(gòu)應(yīng)該是易于進行檢索及匹配操作的。顯然 ，字符串是最佳選擇，下圖給出了行棋步驟表字符串化的一種實現(xiàn)方式上圖顯示了在第2定式區(qū)順時針展開的一個含有脫先手的定式，如果將每手棋用相對于定式區(qū)子坐標(biāo)系的兩個字母表示，則：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手黑棋脫先，無法用定式區(qū)子坐標(biāo)系表示，而對于脫先手，由于其必然在其他定式區(qū)有表示并有記錄，所以可以一律記作XX由此，圖中定式即可用一個字符串表示為:DDCFFCCCCDBDBEBCCEEBXXJCECFBGC。定式問題對象化建立一個可供程序檢索及匹配的定式庫，該庫應(yīng)該記錄各種定式及其各類變化。定式庫應(yīng)該指出每種定式變化對于先手方或者后手方的有利或不利程度。 定式庫應(yīng)該指出每種定式變化所依賴的局面條件。庫結(jié)構(gòu)定式庫通常應(yīng)用于教學(xué)演示日的，通常表現(xiàn)為森林結(jié)構(gòu)：圖6.森林結(jié)構(gòu)圖圖6.森林結(jié)構(gòu)圖森林結(jié)構(gòu)的特點是冗余數(shù)據(jù)少，非常適合整體或部分加載到內(nèi)存然后使用遍歷算法訪問，但不適合快速匹配。如果將森林中每一條從根到葉子的路徑都抽取出來組成一個列表，則該列表雖然含有大量冗余數(shù)據(jù)（根及枝條多次重復(fù)儲存）,但非常適合于快速檢索匹配：

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

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

gx,p=(6)-1g函數(shù)還可以更加細(xì)化的處理處于安全，死亡之間的狀態(tài)。SFBa0,表示盤面黑棋優(yōu)勢；SFB<=0,表示盤面白棋優(yōu)勢。一手棋的價值：△SFB=下子之后的SFB—下子之前的SFB(7)表示下了某子之后形勢改變的度量，也就是這一手的價值。在無急場的情況下，選擇價值大的點落子。5.3.3判定雙方勢力范圍對每一空點，它受到的總控制力A=F0+F1+F2+F3,當(dāng)A大于某一數(shù)值n時，將其規(guī)格化為n(T)。當(dāng)A>0時受黑的影響強一些，該點能否被黑方所控制，能否算作黑方實地，按照以下規(guī)則判定：.如果該點所受四個方向的力均大于1,則該點為黑方勢力范圍；.如果該點所受四個方向的力均大于0,且A大于10,則該點為黑方勢力范圍；.如果該點的A值大于規(guī)格化最大值n的2/3,則該點為黑方勢力范圍；.如果該點為黑方勢力范圍，且所受四個方向的力均大于 1,其中3個方向的力大于2,則該點為黑方實地；.如果該點為黑方勢力范圍，且所受四個方向的力均大1,A值大于34則該點為黑方實地。對于白方的勢力范圍與實地有類似的判斷規(guī)則。利用力學(xué)模型，建立多層塊結(jié)構(gòu)，以FB的值為基礎(chǔ)，根據(jù)FB值的范圍，建立起多級的塊，過程如下：.每個棋子建立一個零層(最底層塊)；.如果相鄰，兩個零層塊屬于同一個一層塊；.如果兩個i層塊之間可以找到這樣一個路徑相通：路徑上的任一點的FB值大于某一與i相關(guān)的設(shè)定值(在實現(xiàn)時根據(jù)經(jīng)驗選取)，則兩個i層塊同屬于一個i+1層塊；.如果i+1層塊只有一個則結(jié)束，否則重復(fù)3o利用這個力學(xué)模型，分析一些簡單的常用走法，利用每個點計算得到的四個方向的力及合力的大小和方向，可以粗略的表示雙方的勢力范圍，力量對比，棋勢強弱等信息。棋子產(chǎn)生的影響用控制力的形式來表示，多個棋子的作用被看作是單個棋子作用的簡單疊加，當(dāng)棋子有一定的距離時，這種疊加是有道理的。但是當(dāng)棋子相近或相連時，單純的疊加已經(jīng)不能近似實際情況。5.3.4快速計算時使用的影響模型在搜索棋塊的死活狀態(tài)時，需要確定一些與眼位有關(guān)的空點處于哪方的控制之下，此時，計算各點的影響值所需的時間成為搜索總用時的最主要影響因素，要想實現(xiàn)計算時間可以接受的完全搜索，必須采用更簡潔的影響模型。應(yīng)用于快速計算的影響模型，首先按照空點對棋子的位置關(guān)系定義了以下的級別劃分：鄰位A的級別為1;關(guān)位B的級別為2;斜鄰位C的級別為1.5;小飛位D的級別為2.5o若雙方棋子相連，F(xiàn)是黑子的扳位，對于黑子級別為2;E是白子的扳位，對于白子級別為2。某色棋子對某空點的影響僅決定于離該點最近（即具最小級別數(shù)）的該色棋子，影響值如下表所示：表1.影響值與空點級別的關(guān)系空點級別11.522.5黑子影響6532白子影響-6-5-3-2黑白影響可以互消，所有點計算完畢，再根據(jù)以下規(guī)則進行圓滑處理某點影響值的代數(shù)和為1或-1,則取為0;與0或負(fù)影響相鄰的點，其影響值不得超過3；與1或2相鄰的點，其影響值不得超過5;負(fù)值（白子影響）有類似的規(guī)則。在實際計算時，遍歷所有的空交叉點（個數(shù)為m）而不是像前面的影響模型計算時遍歷棋子（個數(shù)為n）。如果遍歷棋子，一個棋子影響的空點有4+4+4+8=20個，需計算nx20次，每次都要判斷該棋子對此空點的影響值是否最大；而遍歷空點則只需計算mwx（x<20）次，從空點出發(fā)由近及遠(yuǎn)，遇到第一個棋子（黑白各一次）就可以停止計算。5.4棋盤模型的建立為了對圍棋問題建立數(shù)學(xué)模型，需首先對圍棋棋子價值有個數(shù)學(xué)描述，為此我們給出如下定義：對于一塊成活型棋塊，用它的棋子數(shù)去除這些棋子所包含的目數(shù)，得到的商值稱為此棋塊的目效率，記為PE?？梢钥闯?，目效率表示單位棋子所占的目數(shù)，即表示此棋塊平均占有目數(shù)的能力下面利用此概念對圍棋棋盤問題建立模型。圍棋的棋盤由古時的每邊11道增至現(xiàn)在的每邊19道，其間歷經(jīng)數(shù)千年。這種進化的過程也顯示著人們的認(rèn)識逐漸接近真理。 古人在不貼子的情形下仍可公平對弈,說明先下的一方占的便宜不會太大可以推測，圍棋內(nèi)部一定存在兩種抗衡的力量，使先手即使先落子也無法取得多少優(yōu)勢。一般的棋類（如象棋），往往有攻有守，攻守之間有一種平衡，而且隨時可以轉(zhuǎn)換，因此，先手一方即使先進行攻擊也未必得勝。由此可以說，一般棋類之所以變化無窮，根本原因在其包含了攻與守這既對立又統(tǒng)一的兩個方面。它們在勝負(fù)的天平上地位相同，相互抑制，一切取勝的走法或定式不過是圍繞著攻與守， 以攻為守，或以守為攻來進行罷了。圍棋亦如此，但圍棋的攻守（攻為欲殺死對方，守為不被對方殺死）卻顯然不同于其它棋類，由于弈棋雙方輪換落子，因此，單純?yōu)闅⑺缹Ψ蕉M行攻擊要比防守來得困難。就是說，圍棋里的攻與守?zé)o法取得相同的地位，因此，絕不能把圍棋也認(rèn)為是攻與守的對立統(tǒng)一體。但圍棋那樣富于變化從根本上講，其內(nèi)部一定存在著兩種力量的抗衡。這兩種力量既可以對抗，又可隨時轉(zhuǎn)換。象棋的兩個對立面之所以是攻與守，無非是緣于其取勝規(guī)則為吃掉對方的將（帥），不進攻當(dāng)然不行。因此，在確定圍棋中對抗的兩種力量時必須意識到：這兩種力量抗?fàn)幍淖罱K目的與圍棋的目的應(yīng)是統(tǒng)一的，即多占地盤。首先，我們把圍棋棋盤按區(qū)域特點籠統(tǒng)地分為邊部和中腹。從做活和占地兩個角度看，邊部因空間受阻而易受攻擊，但可利用邊部成目快的特點迅速做活，有根據(jù)地后再圖發(fā)展，中腹則由于四方皆可發(fā)展，不容易受到攻擊，做活便退居其次，而先去搶占空間。由此可見，邊部和中腹將成為圍棋中的兩種對抗的勢力，除此之外，還應(yīng)保證兩種勢力所具有的價值相同，從而使二者能夠真正地進行抗衡，這是必要的，否則，無論偏重哪一方，圍棋都會成為單一凈奪邊部或中腹的乏味游戲,而且使先手棋獲益頗大。前面在討論三線的作用時，曾經(jīng)指出三線控制邊部的優(yōu)勢。顯然，控制中腹的重任無疑落到了緊鄰的四線上。這樣，問題最終可化為：怎樣設(shè)計方形棋盤（即每邊選取多少道）使三線圍成的邊部與四線圍成的中腹具有相同的地位或最小的差異？圖9.方形棋盤每邊19道時的情形三線點、四線點設(shè)置如圖9（此時棋盤每邊道數(shù)為19）,設(shè)三線點、四線點組成的棋塊的目效率分別為PE3,PE,。根據(jù)三線與四線目效率相近的原則，我們提出本節(jié)的數(shù)學(xué)問題：方形圍棋棋盤每邊設(shè)置多少道數(shù),將使E=PE4-PE3的絕對值最??？5.4.1模型的求解假設(shè)棋盤每邊為x道，x為自然數(shù)。為了實用的需要，圍棋棋盤不宜太大，也不宜太小，設(shè)11Wx^23。參照圖9（此時x=19）,由于對x的限制，三線圍成的邊及四線圍成的中腹已成為實空，對方無法在其中做活這樣。所有三線圍成的目數(shù)為：8x-16其目效率為：四線圍成中腹的目數(shù)為:PE38x-164x—20四線圍成中腹的目數(shù)為: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ù)變量，可以看出它是關(guān)于x的單調(diào)下降函數(shù)，因為這是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關(guān)于x求導(dǎo)得:TOC\o"1-5"\h\z1 1PE4x=4-K (13)由x-7>1,從而(PE4x>0,即PE4關(guān)于x單調(diào)上升，這將導(dǎo)致E(x)也關(guān)于x單調(diào)上升，因而，對于方程E(x)=PE4-PE3=0,若有解，其解也只能有一個，又由于；E18=-0.1888,E19=0.092 (14)故由連續(xù)函數(shù)介值定理，E(x)=0的解在開區(qū)間(18,19)中，顯然其解非整數(shù)，而我們尋求的是使|E(x)最小的整數(shù)解，由E(x)的單調(diào)性及同19卜忙(18),即知x=19將使E(x|最小。因此，我們用三線點與四線點目效率相近的原則證明了圍棋棋盤選擇 19M19的網(wǎng)點是最佳的。六、模型的評價與推廣圍棋在生活中隨處可見，平時的家庭生活又或者國際比賽中，它經(jīng)常被廣泛的應(yīng)用于各種比賽。我們也可以根據(jù)建立的圍棋模型，結(jié)合生活中的實際情況，學(xué)習(xí)相應(yīng)的數(shù)學(xué)知識與技能。優(yōu)點：本文建立的模型能夠與實際精密聯(lián)系，結(jié)合實際情況對問題進行了求解，使得模型具有很好的通用性和推廣性。本文模型的計算采用了專業(yè)的數(shù)學(xué)軟件，可信度較高。本文應(yīng)用了正確的數(shù)據(jù)處理方法，很好的解決了小數(shù)取整的問題。缺點：本文沒有很好的把握重心，讓人感覺文章有點散。本文在模型建立的過程中引入的變量較多，不利于編程處理。七、參考文獻(xiàn).馬凈，經(jīng)久不衰的魅力，文化藝術(shù)出版社，1989年.姜啟源，數(shù)學(xué)模型，高等教育出版社，北京，1987年.杜維新，圍棋布局基礎(chǔ)，《成都棋苑》編輯委員會，1985年.吳清源，圍棋高級死活，1991.曹文君，知識庫系統(tǒng)原理及其應(yīng)用，1995.程慧霞，用C+碇造專家系統(tǒng)，1995八、附錄附錄一：/*************************************************/TOC\o"1-5"\h\z//文件名：Go.h //////用途：圍棋 程序?qū)念悗祛^文件。////版本：V0.1 ////版權(quán):伍白楊 ////日期：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("形式(關(guān))"));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("形式(關(guān))"));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