[優(yōu)秀畢業(yè)設(shè)計(jì)精品] 圍棋對(duì)弈系統(tǒng)中勝負(fù)判斷與局面分析功能的設(shè)計(jì)與實(shí)現(xiàn)

1、<p>　　本科畢業(yè)論文（設(shè)計(jì)）</p><p>　　題目：圍棋對(duì)弈系統(tǒng)中勝負(fù)判斷與</p><p>　　局面分析功能的設(shè)計(jì)與實(shí)現(xiàn)</p><p>　　2006年6月18日</p><p>　　畢業(yè)論文（設(shè)計(jì)）評(píng)語及成績</p><p>　院（系）數(shù)學(xué)與計(jì)算機(jī)學(xué)院</p><p>　專

2、 業(yè)計(jì)算機(jī)科學(xué)與技術(shù)</p><p>　年 級(jí)級(jí)</p><p>　姓 名學(xué) 號(hào)</p><p>　指導(dǎo)教師職 稱工程師</p><p><b>　　目　　錄</b></p><p><b>　　摘　要1</b></p><p>　

3、　Abstract2</p><p><b>　　前　言3</b></p><p><b>　　第一章　緒論4</b></p><p>　　1.1　圍棋概述4</p><p>　　1.1.1　圍棋簡介4</p><p>　　1.1.2　相關(guān)圍棋術(shù)語4</p&

4、gt;<p>　　1.2　計(jì)算機(jī)圍棋6</p><p>　　1.2.1　計(jì)算機(jī)與圍棋6</p><p>　　1.2.2　圍棋編程的挑戰(zhàn)7</p><p>　　1.3　圍棋對(duì)弈系統(tǒng)開發(fā)的意義9</p><p>　　第二章　圍棋對(duì)弈系統(tǒng)的開發(fā)環(huán)境及使用工具11</p><p>　　2.1　開發(fā)環(huán)境的

5、選擇及使用工具11</p><p>　　2.2　系統(tǒng)開發(fā)工具與編程方法11</p><p>　　2.3　Source Insight3.5輔助工具12</p><p>　　2.4　Visual SourceSafe 6.0版本與配置管理工具13</p><p>　　第三章　勝負(fù)判斷功能的設(shè)計(jì)與實(shí)現(xiàn)14</p><

6、p>　　3.1　圍棋計(jì)算勝負(fù)的方法與規(guī)則14</p><p>　　3.1.1　圍棋計(jì)算勝負(fù)的方法14</p><p>　　3.1.2　圍棋計(jì)算勝負(fù)的規(guī)則16</p><p>　　3.2　圍棋勝負(fù)判斷的實(shí)現(xiàn)18</p><p>　　3.3　繼續(xù)以前對(duì)局的設(shè)計(jì)與實(shí)現(xiàn)21</p><p>　　第四章　局面分析

7、功能的設(shè)計(jì)與實(shí)現(xiàn)23</p><p>　　4.1　圍棋局面分析的影響模型23</p><p>　　4.1.1　影響模型概念23</p><p>　　4.1.2　典型影響模型舉例24</p><p>　　4.2　圍棋局面分析的常用算法26</p><p>　　4.3　圍棋局面分析功能的實(shí)現(xiàn)27</p&g

8、t;<p>　　4.3.1　影響模型27</p><p>　　4.3.2　力學(xué)模型28</p><p>　　4.3.3　棋盤分塊設(shè)計(jì)29</p><p>　　4.3.4　度量公式30</p><p>　　4.3.5　判定雙方的勢(shì)力范圍30</p><p>　　第五章　圍棋對(duì)弈系統(tǒng)功能的運(yùn)行實(shí)例

9、33</p><p>　　5.1　判斷勝負(fù)功能運(yùn)行實(shí)例33</p><p>　　5.2　局面分析功能運(yùn)行實(shí)例34</p><p>　　5.3　結(jié)論與展望36</p><p><b>　　注　　釋37</b></p><p><b>　　附　　錄39</b></

10、p><p><b>　　后　　記51</b></p><p><b>　　摘 要</b></p><p>　　計(jì)算機(jī)圍棋是計(jì)算機(jī)博弈研究的一個(gè)重要分支，是當(dāng)前人工智能研究的熱點(diǎn)之一，一直以來吸引著大量的研究人員，產(chǎn)生了較大的社會(huì)影響和學(xué)術(shù)影響。由于圍棋變化復(fù)雜、棋理深?yuàn)W，是一種高智能的活動(dòng)，因而圍棋的計(jì)算機(jī)博弈設(shè)計(jì)難度

11、較大，同時(shí)計(jì)算機(jī)圍棋熱點(diǎn)問題的研究為人工智能帶來了嶄新的方法和理論。計(jì)算機(jī)圍棋的研究和實(shí)現(xiàn)需要多門學(xué)科的知識(shí)交叉，至少會(huì)涉及到圍棋、計(jì)算機(jī)、數(shù)學(xué)、生物、邏輯學(xué)、軍事學(xué)、教育、心理學(xué)乃至哲學(xué)等領(lǐng)域，因此其發(fā)展具有重要的研究價(jià)值和應(yīng)用價(jià)值。</p><p>　　論文主要介紹了圍棋對(duì)弈系統(tǒng)中勝負(fù)判斷與局面分析功能子系統(tǒng)具有的功能，論述了子系統(tǒng)的開發(fā)和實(shí)現(xiàn)的過程，同時(shí)對(duì)圍棋勝負(fù)判斷的主要規(guī)則、計(jì)算機(jī)圍棋中計(jì)算勢(shì)的幾個(gè)經(jīng)典

12、模型以及計(jì)算機(jī)圍棋發(fā)展的現(xiàn)狀進(jìn)行了闡述。通過Visual Basic 6.0可視化開發(fā)工具實(shí)現(xiàn)了圍棋對(duì)弈系統(tǒng)，該系統(tǒng)具有新局、繼續(xù)以前局、存當(dāng)前局、設(shè)置、回手、復(fù)盤、判斷勝負(fù)、顯示勢(shì)力、顯示定式等功能，能夠輔助圍棋愛好者進(jìn)行“人-人”圍棋對(duì)弈。</p><p>　　圍棋勝負(fù)判斷與局面分析功能子系統(tǒng)，是圍棋對(duì)弈系統(tǒng)的一個(gè)重要組成部分，并為“人―人”圍棋對(duì)弈系統(tǒng)向“人―機(jī)”圍棋對(duì)弈系統(tǒng)發(fā)展打下基礎(chǔ)。在實(shí)現(xiàn)過程中，通過

13、建立棋局的記錄來判斷棋盤上每一點(diǎn)的歸屬，從而確定雙方地域，故能夠?qū)μ岬羲雷雍蟮慕K局棋盤進(jìn)行判斷勝負(fù)；通過建立棋子的影響模型、力學(xué)模型以及度量公式，將棋子向棋盤其它部分輻射的影響量化，從而判斷對(duì)弈雙方的影響地域。</p><p>　　關(guān)鍵詞：計(jì)算機(jī)圍棋；勝負(fù)判斷；影響模型；勢(shì)</p><p><b>　　Abstract</b></p><p>

14、　　Computer Go is an important branch of Computer Game research, and it is also an hotspot of Artificial Intelligence. Computer Go has been attracting lots of researchers and has brought remarkable social and scientific i

15、nfluence in the meantime. On one hand, because the moves in Go are not only manifold but also complicated, which makes it a more difficult work in Computer Go programming. On the other hand, it has brought Artificial Int

16、elligence many new methods and theories. At the same time, Com</p><p>　　The paper mainly introduces the background, functions to be completed and the development procedure of the system. It presents the rule

17、s of victory judgment, the classic influence model and the current situation. The Go Playing System is built by Visual Basic 6.0 and includes many functions such as new game, load game, storage game, settings, undo, redo

18、, victory judgment of the two sides, show influence and formulized series of moves. It can help Go enthusiasts to make competition of human-to-hu</p><p>　　Both of the victory judgment and situation analysis

19、subsystems are needed sections of human-to-human Go Playing System, and they will all be foundations of the human-to-machine Computer Go System in the future. In the process of implementation, the system can obtain the r

20、esult by building the record adscription of every point. The paper builds the influence model, mechanical model and measurable formula. It is constructed to quantify the influence that stones make and estimate the areas

21、of the t</p><p>　　Key words: Computer Go；victory judgment；influence model；force</p><p><b>　　前 言</b></p><p>　　圍棋是一項(xiàng)廣有裨益的智力競(jìng)技運(yùn)動(dòng)，它集休閑娛樂、陶冶性情、修心養(yǎng)性于一身，是中華文化的瑰寶，是人類智慧的最高象征之

22、一。圍棋經(jīng)歷了數(shù)千年，久盛不衰，且至今還在不斷發(fā)展?，F(xiàn)在的人工智能科學(xué)研究在它面前顯得很是稚嫩，因而值得將它作為重要的研究對(duì)象。在人工智能領(lǐng)域內(nèi)，博弈是很重要的一個(gè)研究分支。通過對(duì)博弈的研究，可以解決很多實(shí)際問題，使計(jì)算機(jī)智能向人類智能邁進(jìn)。計(jì)算機(jī)國際象棋和計(jì)算機(jī)圍棋一直是人工智能的熱門課題，而圍棋程序的編制被稱作人工智能的“試金石”，是人工智能技術(shù)的一大難題，它將會(huì)在今后相當(dāng)長的時(shí)期內(nèi)哺育著人工智能科學(xué)的成長。</p>

23、<p>　　本系統(tǒng)立足于“人―人”圍棋對(duì)弈系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)，具有圍棋記譜、打譜、對(duì)弈計(jì)時(shí)、查看定式、初步顯示局面形勢(shì)等功能，是一個(gè)適宜在計(jì)算機(jī)上對(duì)弈的“人―人”對(duì)弈系統(tǒng)，可作為實(shí)用的圍棋學(xué)習(xí)、研究和娛樂的良好的輔助工具。圍棋勝負(fù)判斷與局面分析功能子系統(tǒng)是圍棋對(duì)弈系統(tǒng)的重要組成部分，本文在此基礎(chǔ)上初步討論了“人―機(jī)”對(duì)弈的模式和方法，分析了“人―機(jī)”對(duì)弈系統(tǒng)所應(yīng)具有的功能。本系統(tǒng)的實(shí)現(xiàn)為進(jìn)一步研究圍棋的“人-機(jī)”對(duì)弈奠定了基礎(chǔ)。

24、</p><p>　　論文研究的主要內(nèi)容：</p><p>　　（1）設(shè)計(jì)與實(shí)現(xiàn)一定條件下的圍棋棋局最后勝負(fù)判斷功能子系統(tǒng)。</p><p>　　（2）探討“非中國圍棋規(guī)則中棋局最后勝負(fù)判斷”實(shí)現(xiàn)的途徑和方法。</p><p>　?。?）設(shè)計(jì)與實(shí)現(xiàn)局面分析功能子系統(tǒng)。</p><p>　?。?）探討“人―機(jī)”圍棋對(duì)弈系

25、統(tǒng)實(shí)現(xiàn)的途徑和方法。</p><p>　　圍棋勝負(fù)自動(dòng)判斷是一個(gè)實(shí)用的圍棋對(duì)弈系統(tǒng)所應(yīng)具有的功能。在現(xiàn)實(shí)的圍棋勝負(fù)判斷中，往往需要一個(gè)裁判員通過做棋來判斷棋局最終的勝負(fù)。如果有一個(gè)客觀、準(zhǔn)確的圍棋自動(dòng)判斷勝負(fù)系統(tǒng)，一方面可以省時(shí)省力，一方面可以做到客觀公正。但實(shí)現(xiàn)一個(gè)具有人（裁判員）一樣的判斷能力的勝負(fù)判斷系統(tǒng)，存在著許多困難和挑戰(zhàn)。本系統(tǒng)通過建立棋局的記錄來判斷棋盤上每一點(diǎn)的歸屬，從而確定棋局中雙方地域，故能夠

26、對(duì)提掉死子后的終局棋盤用中國規(guī)則判斷勝負(fù)，并由此討論如何實(shí)現(xiàn)用日本規(guī)則判斷勝負(fù)；通過建立棋子的影響模型、力學(xué)模型以及度量公式，將棋子向棋盤其它部分輻射的影響量化，從而判斷對(duì)弈雙方的影響領(lǐng)域，在此基礎(chǔ)上，探討如何實(shí)現(xiàn)“人―機(jī)”對(duì)弈中著法的選擇。但目前仍有許多問題有待于進(jìn)一步解決，例如影響函數(shù)的優(yōu)化，死子的提取等問題。 </p><p><b>　　第一章 緒論</b></p>

27、<p><b>　　1.1 圍棋概述</b></p><p>　　1.1.1 圍棋簡介</p><p>　　圍棋相傳為堯所創(chuàng)，有“堯造圍棋，以教子丹朱”的記載。班固在《漢書》中提到“縱橫一十九道，天元是為太極，太極生兩儀，為黑白子；兩儀生四象，為四個(gè)角”。又記載：“棋有白黑，陰陽分也，駢羅列布，效天文也?！盵A1]可知圍棋本是仿效天文而制，逐漸演變?yōu)椴┺挠?/p>

28、戲。</p><p>　　1.1.2 相關(guān)圍棋術(shù)語</p><p><b>　　1. 塊棋</b></p><p>　　同色的棋子在經(jīng)線或緯線上相鄰，稱為連接。如圖1-1，連接在一起的棋子組成了一塊棋，當(dāng)然單一的一顆棋子也可以稱一塊棋。塊棋的氣是組成它的所有棋子的氣總和；一般來說，有兩個(gè)及兩個(gè)以上真眼的塊棋是不能被提掉的，如圖中的eye點(diǎn)，因?yàn)?/p>

29、對(duì)方不可能同時(shí)落下兩顆棋子填眼，故圖1-1中的塊棋是活棋。 </p><p>　　圖1-1 已經(jīng)活的塊棋</p><p><b>　　2. 假眼</b></p><p>　　同顏色的幾個(gè)棋子圍住一個(gè)交叉點(diǎn)，該交叉點(diǎn)稱為“眼”。棋塊被圍，至少須有兩眼方能成活，而己方的這兩眼能使對(duì)方無法入內(nèi)打吃取子，稱為“真眼”。有時(shí)眼形不完備，有被下子投入提吃

30、的可能，稱為“假眼”。一個(gè)完整的眼，在角上必須有三子，在邊上必須有五子，在中腹至少占領(lǐng)周圍七子。如圖1-2，其中a為真眼，b為假眼。</p><p>　　圖1-2 真眼和假眼</p><p><b>　　3. 死活</b></p><p>　　死棋指棋盤上遲早要被對(duì)方吃掉的棋子。常見形式有：</p><p>　　（1）

31、沒有氣的棋子。</p><p>　　（2）有些棋子雖還有氣，但本身已無條件做成兩個(gè)眼，終將被對(duì)方吃掉。如圖1-3，黑棋三例均為死棋。</p><p><b>　　圖1-3 死棋</b></p><p>　　活棋指棋盤上對(duì)方無法吃掉的棋子。常見形式有：</p><p>　?。?）一塊棋至少有兩個(gè)對(duì)方禁著點(diǎn)。</p&

32、gt;<p>　　（2）一塊棋所圍的空點(diǎn)較多，已經(jīng)具備做成兩個(gè)眼的條件。如圖1-4，黑棋有a和b兩個(gè)白棋的禁著點(diǎn)，為活棋。[B1]</p><p><b>　　圖1-4 活棋</b></p><p><b>　　4. 分?jǐn)?lt;/b></p><p>　　也稱“斷”，指把對(duì)方的棋子分割成兩部分，是一種激烈的攻擊

33、手段。此后雙方將引起激烈戰(zhàn)斗，所以要在對(duì)方兩面薄弱的情況下選擇斷點(diǎn)。 </p><p><b>　　5. 聯(lián)絡(luò)</b></p><p>　　圍棋術(shù)語中兩棋子的連接僅指經(jīng)緯線上的連接，又稱并。但實(shí)際的連接中可以有許多方式，如并、尖、飛、大飛等，如圖1-5，1-6。如果兩塊棋沒有聯(lián)絡(luò)，則稱為斷開的。</p><p>　　圖1-5 并、關(guān)、二間關(guān)&

34、lt;/p><p>　　圖1-6 尖、飛、大飛</p><p><b>　　6. 棋塊</b></p><p>　　兩塊或多塊互相緊密聯(lián)絡(luò)的同色塊棋組成棋塊，由于互相之間有緊密的聯(lián)絡(luò)，它們可以被看作一塊棋。棋塊是對(duì)局中棋手分析棋局的一個(gè)較大的單位，其最重要的屬性是確定它是否是活的，或是否可以做出兩個(gè)眼，或可以與一個(gè)已有兩個(gè)眼的活棋塊聯(lián)絡(luò)。如圖1-

35、7中含三個(gè)棋塊。</p><p>　　圖1-7 棋塊</p><p><b>　　7. 棋勢(shì)</b></p><p>　　兩塊或多塊聯(lián)絡(luò)松散的同色塊棋組成棋勢(shì)，如圖1-7中三個(gè)棋塊（每個(gè)棋塊由多個(gè)塊棋組成）圍成了很大的地域，構(gòu)成棋勢(shì)。對(duì)于棋手而言，將棋勢(shì)轉(zhuǎn)化為實(shí)地是很重要的。而對(duì)方侵入這塊地域則稱為打入。</p><p

36、><b>　　8. 棋局</b></p><p>　　是所有那些必須記錄下來的信息。根據(jù)這些信息，比賽在按計(jì)劃暫停后能夠得以繼續(xù)進(jìn)行下去。顯然，這些信息包括了此時(shí)棋子在棋盤上的位置以及指出下一步該哪方走，有時(shí)甚至需要有對(duì)局時(shí)間等信息。</p><p><b>　　9. 數(shù)棋</b></p><p>　　當(dāng)對(duì)局結(jié)束后，

37、從棋盤上提掉死子，分別數(shù)出雙方的提子數(shù)和圍空數(shù)之和，多的一方為勝者。</p><p>　　1.2 計(jì)算機(jī)圍棋</p><p>　　1.2.1計(jì)算機(jī)與圍棋</p><p>　　計(jì)算機(jī)運(yùn)用于棋類方面幾乎與計(jì)算機(jī)誕生的歷史一樣長。這方面內(nèi)容主要屬于人工智能范疇。人工智能作為一門學(xué)科首先是在五十年代被建立起來的，隨即便運(yùn)用于博弈，同時(shí)博弈等方向的研究也極大地促進(jìn)了人工智能

38、的發(fā)展。</p><p>　　計(jì)算機(jī)圍棋發(fā)展至今的一些代表性程序?yàn)殛愔拘薪淌诘腍andTalk、陳克訓(xùn)教授的Go Intellect、Mark Boon的Goliath和許舜欽教授的學(xué)生們所制作的程序以及開放源代碼的GNUGO。還一些計(jì)算機(jī)圍棋軟件的界面還是基于DOS命令下的，以字符界面方式工作，通過命令提示符輸入坐標(biāo)及相應(yīng)得命令來下棋。計(jì)算機(jī)圍棋發(fā)展初期的八十年代，圍棋程序以大約每年兩級(jí)的速度在進(jìn)步，而到了九十

39、年代計(jì)算機(jī)圍棋已發(fā)展到某一程度，但仍以大約每年一級(jí)的速度在穩(wěn)定進(jìn)步中，由此看來，計(jì)算機(jī)圍棋目前仍在穩(wěn)定發(fā)展之中，另一方面，由各圍棋程序各有特色看來，計(jì)算機(jī)圍棋還有相當(dāng)大的發(fā)展空間。</p><p>　　就圍棋而言，人弈棋憑的主要是經(jīng)驗(yàn)，即“棋感”，精確計(jì)算為輔。人類的優(yōu)勢(shì)是模糊判斷、靈敏的直覺，高手往往會(huì)靈機(jī)一動(dòng)而弈出妙手。當(dāng)然事物有其兩面性，即人的直覺有時(shí)也會(huì)誤導(dǎo)形成錯(cuò)誤，棋手的心態(tài)也至關(guān)重要，即直覺是法寶，亦

40、是促成盲動(dòng)的敗因。</p><p>　　計(jì)算機(jī)的優(yōu)勢(shì)是計(jì)算速度快，不為情緒、直覺所惑，故地域廣狹之分能較為準(zhǔn)確，劣勢(shì)是不擅模糊判斷、只能根據(jù)少數(shù)經(jīng)驗(yàn)選點(diǎn)導(dǎo)致搜索量過大，且沒有棋感，不知道走哪一步較好、哪一步不好，只有逐點(diǎn)試，有時(shí)費(fèi)時(shí)甚巨（也未必有用），有時(shí)不夠準(zhǔn)確。</p><p>　　1.2.2 圍棋編程的挑戰(zhàn)</p><p>　　圍棋帶來的眾多挑戰(zhàn)中的一個(gè)方面便

41、是計(jì)算機(jī)程序的實(shí)現(xiàn)。福特蘭德說：“計(jì)算機(jī)圍棋程序已經(jīng)產(chǎn)生了許多改進(jìn)，但是沒有突破性的進(jìn)展?！?[B2]計(jì)算機(jī)圍棋程序不僅不能很快地計(jì)算出棋局變化的可能性，而且也不能準(zhǔn)確地進(jìn)行計(jì)算。但盡管如此，由于圍棋本身的高深和復(fù)雜促使程序設(shè)計(jì)師們?cè)谌斯ぶ悄茴I(lǐng)域不斷地推進(jìn)基礎(chǔ)性的工作，開發(fā)有關(guān)圍棋計(jì)算機(jī)程序的吸引力也在不斷增加。</p><p>　　1. 棋類算法及其在象棋與圍棋中的對(duì)比</p><p>

42、　　由于技術(shù)的進(jìn)步，計(jì)算機(jī)速度的提高、算法的不斷發(fā)展，目前電腦國際象棋的水平已極高，一九九七年，IBM的電腦“深藍(lán)”一舉戰(zhàn)勝卡斯帕羅夫，震驚世界。其實(shí)電腦國際象棋的水平早在七、八十年代已擠身世界高手之林，而中國象棋軟件也已幾乎具有大師水準(zhǔn)，非一般愛好者能望其項(xiàng)背。唯獨(dú)計(jì)算機(jī)圍棋舉步維艱，連業(yè)余下手都勝券難握，更莫論一等一的高手，究其原因不外是圍棋之博大精深、縱橫變換繁復(fù)，棋手多靠經(jīng)驗(yàn)下棋，計(jì)算機(jī)很難描述經(jīng)驗(yàn)，更難應(yīng)用經(jīng)驗(yàn)。</p&

43、gt;<p>　　圍棋和象棋一樣是博弈游戲，看似僅有黑白兩種棋子，簡單不過。實(shí)則比起兵種繁多的象棋卻復(fù)雜得多。</p><p>　　目前，棋類算法主要有兩大類：基于模式匹配和使用博弈樹。這在國際象棋中的運(yùn)用可以追溯到五、六十年代，且而十分成功。</p><p>　　電腦圍棋起源于六十年代。Zobrist和Ryder兩位博士在論文中均涉及了圍棋程序，前者的算法基于模式識(shí)別；而后

44、者的算法基于搜索，即使用博弈樹。這兩種在國際象棋中效果不錯(cuò)的算法在圍棋中的表現(xiàn)卻極差，竟然連僅有幾盤棋經(jīng)驗(yàn)的人都贏不了。</p><p>　　這里分析一下上述兩種算法。</p><p><b>　?。?）模式匹配</b></p><p>　　象棋中因?yàn)槠遄觽€(gè)數(shù)少、種類多，那么就較易分別與歸納（實(shí)際上也是困難的，但比圍棋容易實(shí)現(xiàn)得多）。而在圍棋中

45、，顯然將所有的模式都存儲(chǔ)起來是不可能的。那么只有模糊匹配。但這似乎也很難辦。圍棋中有“愚形”這個(gè)名詞，一般指的是效率差的形狀。那么怎樣是效率差呢？就是浪費(fèi)子力，在不必要的地方落子，哪怕只是一個(gè)子。而模糊的匹配在一子之差時(shí)究竟如何判斷？是好形還是愚形？這就陷入了矛盾的境地。況且，根據(jù)實(shí)際情況，還有“愚形之妙手”，實(shí)難判斷。</p><p><b>　?。?）搜索算法</b></p>

46、<p>　　搜索的代價(jià)是極大的，據(jù)估計(jì)，國際象棋搜索7個(gè)回合約有500億至600億種選擇（當(dāng)然是在博弈樹剪枝后），這個(gè)數(shù)字盡管也十分龐大，但以目前的技術(shù)水平還是可以承受的；然而在圍棋中，我們稍微計(jì)算一下便知道：假設(shè)每步大約有只有一百個(gè)可行點(diǎn)（已經(jīng)非常少了），那么14步（即7個(gè)回合）以內(nèi)的變化則約有1028種，當(dāng)然這只是保守的估計(jì)，已足以駭人了?？梢娫谌质褂盟阉魉惴ㄊ遣豢尚械摹Ｒ虼水?dāng)前的做法一般是在局部明確目標(biāo)（如做活、殺

47、棋、突圍、切斷等）的情況下，才使用博弈樹進(jìn)行搜索。</p><p>　　2. 為什么圍棋無法像國際象棋那樣編程</p><p>　　同國際象棋編程相比較，圍棋編程領(lǐng)域的發(fā)展尚處于初級(jí)階段。在國際象棋的編程研究領(lǐng)域中曾出現(xiàn)過像60年代和70 年代時(shí)投入了強(qiáng)大的研究力量的情形，在圍棋編程領(lǐng)域從來沒有過。在兩者之間有著本質(zhì)的區(qū)別，使得國際象棋受人青睞成為研究對(duì)象，同時(shí)，即使也有力量投入圍棋編程，

48、其結(jié)果也無法趕上國際象棋編程的進(jìn)步。這其中原因，一方面是由于圍棋本身的復(fù)雜性，另一方面是由于在國際象棋領(lǐng)域取得的編程技術(shù)無法恰當(dāng)?shù)剡\(yùn)用于圍棋領(lǐng)域。 </p><p>　　（1）圍棋棋子類型簡單，只有一種，但棋盤為19*19，且由于著手的相對(duì)自由，使得圍棋棋局的平均手?jǐn)?shù)大約為300步，每步棋著的選擇（分支因子）可高達(dá)平均200個(gè)。</p><p>　?。?）圍棋有兩種終局方式：認(rèn)輸和自然終局

49、，且需要雙方同時(shí)認(rèn)可，但往往初學(xué)者很難判斷是否已經(jīng)沒棋可下，所以他們的棋局往往比高手之間的要長，圍棋程序也會(huì)犯同樣的毛病。如果按照日本的數(shù)目法計(jì)算勝負(fù)，則多余的著手會(huì)因?yàn)樘钤诩悍降目绽锘蜃兂蓪?duì)方的提子而減少目數(shù)。</p><p>　?。?）圍棋的棋子威脅度與國際象棋不同，就國際象棋而言，棋子的威脅度僅是它所能走到的格子，而在圍棋中，棋子下后就不再移動(dòng)（僅當(dāng)提子時(shí)例外），但可以對(duì)棋盤上其他的棋子產(chǎn)生影響，如引征可以

50、改變某塊棋的征子關(guān)系。</p><p>　?。?）圍棋中，棋子的移動(dòng)對(duì)棋局的變化影響不顯著，從而需要大容量的記憶分析棋局。即使是一個(gè)初學(xué)者也可以看出60步以后的征子結(jié)果，這是一個(gè)很深但很窄的計(jì)算問題。但只有最后當(dāng)棋子被提掉的時(shí)候，棋盤的物理狀態(tài)才發(fā)生顯著的變化。</p><p><b>　　3. 圍棋的復(fù)雜性</b></p><p>　　圍棋的

51、復(fù)雜性具有以下的特點(diǎn)：變化的復(fù)雜性；計(jì)算的復(fù)雜性；勝負(fù)判斷的復(fù)雜性；打劫的復(fù)雜性；對(duì)弈時(shí)間長；頂尖高手失手率高；計(jì)算機(jī)程序的設(shè)計(jì)難度大；棋評(píng)的內(nèi)容復(fù)雜。圍棋全局與其死活問題其復(fù)雜性都大致可歸納為如下三點(diǎn)：</p><p><b>　?。?）模糊性</b></p><p>　　“圍棋”之名自是取自圍地之意，倘若是雙方落子一開始便是緊緊相貼的，那么可想而之行棋的速度（即占

52、領(lǐng)地盤的速度）是極慢的，故而布局、中盤以至大官子階段，雙方只是圍出一個(gè)大概的輪廓，甚而連輪廓都不明顯。黑白勢(shì)力難分，形狀多變。這對(duì)于計(jì)算機(jī)處理造成了極大的困難。</p><p><b>　?。?）反復(fù)性</b></p><p>　　象棋中棋子一旦被吃，則永遠(yuǎn)從棋盤上提去，而在圍棋棋盤上，被吃的地方仍可重新落子，甚至將對(duì)方反吃回來，這樣搜索的難度就大大增加，如“倒脫靴”

53、之形，送子后再吃子，一塊空可以幾易其主。所以“死子”不一定死，因此在計(jì)算機(jī)處理中不可以簡單確定一塊棋的死活和對(duì)周圍的影響。</p><p><b>　?。?）靈活性</b></p><p>　　象棋的靈活，至多體現(xiàn)在兌子上，所謂“寧棄一子，不失一先”，也僅是一子而已，若是兩子、三子呢？恐怕在雙方實(shí)力相當(dāng)?shù)那闆r下必?cái)o疑。而且在象棋算法中多有將各種棋子折合為一定的價(jià)值相

54、加的做法，如在國際象棋中以一個(gè)兵為單位，一個(gè)馬約可等于三個(gè)兵，一個(gè)車約可等于五個(gè)兵，再根據(jù)棋子所處位置加以一定的折算。</p><p>　　而圍棋的靈活遠(yuǎn)勝于此，有時(shí)棄去十來個(gè)子以取勢(shì)，棄去二、三十目的角地以轉(zhuǎn)換。而且，圍棋棋子的價(jià)值是難以估量的，其價(jià)值不完全在其本身，而常在于周圍，有些影響甚而可跨整個(gè)棋盤。</p><p>　　1.3 圍棋對(duì)弈系統(tǒng)開發(fā)的意義</p>&l

55、t;p>　　計(jì)算機(jī)圍棋的研究和實(shí)現(xiàn)需要多門學(xué)科的知識(shí)交叉，至少會(huì)涉及到圍棋、計(jì)算機(jī)、數(shù)學(xué)、生物乃至哲學(xué)等領(lǐng)域。從程序員角度狹義地看計(jì)算機(jī)圍棋，它是計(jì)算機(jī)技術(shù)在圍棋上的應(yīng)用，即編寫一個(gè)下圍棋的程序，使計(jì)算機(jī)智能足以在棋局中得到發(fā)揮。從大的方面看，研究計(jì)算機(jī)圍棋，也是探索機(jī)器智能、揭穿人類及其它生物智能秘密的一個(gè)重要途徑。</p><p>　　早在1962年，人們開始以圍棋為研究對(duì)象將電腦圍棋納入到研究工作中，

56、盡管直到1968年（Zobrist，1970）才出現(xiàn)了第一盤由程序下出的完整的棋。而隨著電腦圍棋賽事的舉辦和第一個(gè)商業(yè)程序的發(fā)行，在80年代也正式確定了電腦圍棋研究領(lǐng)域，并在90年代變得興旺起來。目前在電腦圍棋競(jìng)賽中比較活躍的頂尖程序有 Explorer，Go Intellect，Go4++，手談和The Many Faces of Go，水平大致是在4-8級(jí)之間。這些圍棋程序都使用了一定量的“知識(shí)”。由于建立在設(shè)計(jì)者下棋經(jīng)驗(yàn)的啟發(fā)之上

57、，每個(gè)程序都可被看作一種（可能是含糊的）圍棋理論的一次以經(jīng)驗(yàn)為依據(jù)的實(shí)驗(yàn)。圍棋理論成立的關(guān)鍵要靠數(shù)據(jù)結(jié)構(gòu)的選擇，因?yàn)樗鼈儧Q定了編碼不同類型知識(shí)的難易和應(yīng)用這些知識(shí)的計(jì)算開銷。隨著程序員同時(shí)在圍棋和電腦圍棋方面獲得技能，程序會(huì)有發(fā)展（例如，在過去的十五年中隨著 Fotland 的棋力從15級(jí)發(fā)展到2段，MFG也增長了棋力并且代碼長度增加到目前的4萬行）。值得注意的是，程序的性能由它最弱的部件決定，而向程序增加新知識(shí)的難易是提高程序性能的重

58、要部分。</p><p>　　由此可見，計(jì)算機(jī)圍棋領(lǐng)域在關(guān)于怎樣構(gòu)筑一個(gè)圍棋程序或者指配不同圍棋知識(shí)的優(yōu)先性（例如，Go4++注重聯(lián)接性而MFG注重死活）方面還沒有一致性。必須提到的一點(diǎn)是：關(guān)于人類是怎樣下圍棋的至今也沒有一致的說法，這是目前認(rèn)知科學(xué)研究的一個(gè)課題。這個(gè)領(lǐng)域的任何進(jìn)展都會(huì)對(duì)圍棋理論有個(gè)直接的促進(jìn)，并可能導(dǎo)致圍棋程序算法的改進(jìn)。</p><p>　　計(jì)算機(jī)圍棋的挑戰(zhàn)性在于要擴(kuò)

59、展當(dāng)前的圍棋理論或發(fā)展新理論——特別是與評(píng)估有關(guān)的，針對(duì)實(shí)時(shí)限制設(shè)計(jì)合適的數(shù)據(jù)結(jié)構(gòu)和算法，解決知識(shí)瓶頸。目前還沒有一個(gè)有力的程序使用學(xué)習(xí)技術(shù)，盡管有過幾次這樣的嘗試（如Pell，1991；Schraudolph, Dayan & Sejnowski，1994；Donnelly, Corr & Crookes，1994）。怎樣把學(xué)習(xí)能力賦予現(xiàn)有的程序（或者它們暗示的圍棋理論）是個(gè)等待解決的問題。</p>&l

60、t;p>　　本課題所建立的圍棋對(duì)弈系統(tǒng)是一個(gè)適宜在計(jì)算機(jī)上對(duì)弈的“人―人”對(duì)弈系統(tǒng)，能夠作為實(shí)用的學(xué)習(xí)和研究圍棋的輔助工具。它立足于“人―人”圍棋對(duì)弈系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)，該層次的系統(tǒng)可以輔助實(shí)現(xiàn)圍棋記譜、打譜、對(duì)弈計(jì)時(shí)、查看定式、初步顯示局面等管理功能，并在此基礎(chǔ)上探索“人―機(jī)”對(duì)弈的模式和方法，以讓計(jì)算機(jī)代替人進(jìn)行對(duì)弈思維活動(dòng)， 勝負(fù)判斷與局面分析功能子系統(tǒng)，是圍棋對(duì)弈系統(tǒng)的重要組成部分，為“人―人”圍棋對(duì)弈系統(tǒng)向“人―機(jī)”圍

61、棋對(duì)弈系統(tǒng)發(fā)展打下基礎(chǔ)。</p><p>　　圍棋對(duì)弈系統(tǒng)的開發(fā)環(huán)境及使用工具</p><p>　　2.1 開發(fā)環(huán)境的選擇及使用工具</p><p>　　開發(fā)與運(yùn)行環(huán)境：Windows XP操作系統(tǒng)</p><p>　　開發(fā)工具：Visual Basic 6.0</p><p>　　輔助工具：Source Insig

62、ht 3.5，Visual SourceSafe 6.0</p><p>　　2.2 系統(tǒng)開發(fā)工具與編程方法</p><p>　　1. Visual Basic可視化開發(fā)工具</p><p>　　VB系統(tǒng)提供豐富的數(shù)據(jù)類型、眾多的內(nèi)部函數(shù)、子程序、事件子程序和自定義函數(shù)等模塊，各個(gè)子程序模塊之間可以彼此獨(dú)立，可以相互聯(lián)系。在VB中可以應(yīng)用結(jié)構(gòu)化的程序設(shè)計(jì)方法，也可

63、以運(yùn)用基于對(duì)象和面向?qū)ο蟮募夹g(shù)。</p><p>　　Visual Basic允許程序員以單文檔界面（SDI）或多文檔界面（MDI）或資源管理器式界面來運(yùn)行環(huán)境的選項(xiàng)，也有允許同時(shí)將多個(gè)工程作為工程組加載到環(huán)境中的功能。在VB集成開發(fā)環(huán)境中，用戶可以設(shè)計(jì)界面、編寫代碼、調(diào)試程序，直至把應(yīng)用程序編譯成可執(zhí)行文件。</p><p>　　在VB應(yīng)用程序開發(fā)環(huán)境，常常把程序和數(shù)據(jù)封裝起來視為一個(gè)對(duì)

64、象工具，每個(gè)對(duì)象工具都是可視的。程序員在設(shè)計(jì)時(shí)只需要根據(jù)設(shè)計(jì)界面的要求利用現(xiàn)有的對(duì)象工具，直接在屏幕上設(shè)置不同的對(duì)象（如：窗口、菜單、按鈕或滾動(dòng)條等），并為每個(gè)對(duì)象設(shè)置屬性，以所見即所得的方式進(jìn)行程序設(shè)計(jì)。</p><p>　　2. 事件驅(qū)動(dòng)的編程機(jī)制</p><p>　　事件驅(qū)動(dòng)是增強(qiáng)程序圖形界面交互性的主要方法。事件驅(qū)動(dòng)是指利用用戶的動(dòng)作或行為控制程序運(yùn)行的流向。用戶的每一個(gè)動(dòng)作或操作

65、行為都可產(chǎn)生一系列消息，這些消息都可驅(qū)動(dòng)一段程序（即某事件代碼）的運(yùn)行。程序員只需編寫響應(yīng)用戶動(dòng)作的代碼，各個(gè)動(dòng)作之間不一定有聯(lián)系。這樣的方式下，具有代碼短、易編寫、易維護(hù)的優(yōu)點(diǎn)。</p><p>　　3. 結(jié)構(gòu)化的思想與原則</p><p>　　（1）自頂向下，逐步求精原則</p><p>　　進(jìn)行程序設(shè)計(jì)時(shí)，先把對(duì)問題的處理（即算法）粗分成幾個(gè)步驟，叫做模塊。然

66、后對(duì)每個(gè)模塊再細(xì)化為幾個(gè)小模塊，每個(gè)小模塊再細(xì)分為若干個(gè)更小的子模塊，直到每個(gè)小模塊能直接用語言來實(shí)現(xiàn)為止。這種過程是一種自頂向下，逐步求精的過程，會(huì)使程序結(jié)構(gòu)清晰，易保證程序的正確性，也便于修改和維護(hù)。</p><p><b>　?。?）模塊化思想</b></p><p>　　整個(gè)程序和功能模塊都由幾個(gè)功能相對(duì)獨(dú)立的子模塊組成，每個(gè)子模塊只有一個(gè)入口和出口與外界聯(lián)系

67、。這使程序結(jié)構(gòu)清楚，便于調(diào)試和修改。</p><p><b>　?。?）三種基本結(jié)構(gòu)</b></p><p>　　整個(gè)程序中的各級(jí)模塊僅由順序、選擇、循環(huán)三種基本控制結(jié)構(gòu)組成。這三種基本結(jié)構(gòu)也只有一個(gè)入口和一個(gè)出口。</p><p>　　2.3 Source Insight 3.5輔助工具</p><p>　　閱讀源代

68、碼是鉆研技術(shù)的最佳手段，在設(shè)計(jì)過程中，Gnu Go 提供了開放的源代碼庫，本文借鑒了其中的許多思想，它是一個(gè)使用C語言在UNIX下編寫的優(yōu)秀的圍棋人機(jī)對(duì)弈系統(tǒng)。如果缺乏良好的源代碼閱讀工具，會(huì)使閱讀源代碼尤其是個(gè)函數(shù)內(nèi)部的調(diào)用十分困難，在閱讀過程中，使用了一個(gè)優(yōu)秀的源代碼閱讀工具——Source Insight。</p><p>　　Source Insight是一個(gè)面向項(xiàng)目的程序編輯器和代碼瀏覽器，內(nèi)建C/C+

69、+、C#和Java程序語法分析。Source Insight能動(dòng)態(tài)地保持符號(hào)信息的自己的數(shù)據(jù)庫，并自動(dòng)地顯示有用的上下文信息。Source Insight還能夠顯示參考樹，類繼承圖表和調(diào)用樹。Source Insight的特點(diǎn)是快速源代碼導(dǎo)航，它能快速地訪問源代碼和代碼信息。當(dāng)編輯時(shí)，Source Insight解析源代碼并立刻提供給有用的信息和分析。這使得代碼的閱讀變得相對(duì)簡易。 </p><p>　　圖2-1

70、 工作窗口</p><p>　　使用Source Insight的具體用途主要有：上下文敏感的智能改名、符號(hào)自動(dòng)完成、快速訪問所有符號(hào)和文件、項(xiàng)目定位、團(tuán)隊(duì)編程支持、源代碼超鏈接到編譯器錯(cuò)誤的地方、快速項(xiàng)目范圍的搜索和替換、項(xiàng)目窗口帶有多個(gè)視圖、集成額外的編譯器和工具、剪貼窗口排序剪貼板和規(guī)范代碼、雙狀態(tài)行修改標(biāo)記和選擇行恢復(fù)、可擴(kuò)展的文檔類型和語言、崩潰恢復(fù)提供保護(hù)、穩(wěn)定的工作臺(tái)、可自定義的菜單和鍵盤、支持遠(yuǎn)

71、程終端服務(wù)會(huì)話等。 </p><p>　　2.4 Visual SourceSafe 6.0版本與配置管理工具</p><p>　　Visual SourceSafe （以下簡稱VSS）是一種源代碼控制系統(tǒng)，它提供了完善的版本和配置管理功能，以及安全保護(hù)和跟蹤檢查功能。VSS通過將有關(guān)項(xiàng)目文檔（包括文本文件、圖像文件、二進(jìn)制文件、聲音文件、視屏文件）存入數(shù)據(jù)庫進(jìn)行項(xiàng)目研發(fā)管理工作。用戶可

72、以根據(jù)需要隨時(shí)快速有效地共享文件。文件一旦被添加進(jìn)VSS，它的每次改動(dòng)都會(huì)被記錄下來，用戶可以恢復(fù)文件的早期版本，項(xiàng)目組的其他成員也可以看到有關(guān)文檔的最新版本，并對(duì)它們進(jìn)行修改，VSS也同樣會(huì)將新的改動(dòng)記錄下來。用VSS來組織管理項(xiàng)目,會(huì)使得項(xiàng)目組間的溝通與合作更簡易而且直觀。 </p><p>　　圖2-2 VSS服務(wù)器的配置</p><p>　　VSS的主要功能是對(duì)項(xiàng)目進(jìn)行版本控制

73、和源碼控制，它能夠詳細(xì)記錄一個(gè)源碼文件從創(chuàng)建到發(fā)布的所有修改和版本信息，而且還可以查看所有歷史記錄并對(duì)不同時(shí)間的源碼進(jìn)行比較分析，恢復(fù)代碼到某一時(shí)刻和版本狀態(tài)。VSS具有強(qiáng)大的用戶管理權(quán)限，可以對(duì)每個(gè)用戶設(shè)置R(Read)、C(Check Out)、A(Add)、D(Destroy)權(quán)限，非常適合團(tuán)隊(duì)開發(fā)。</p><p>　　由于是四人共同開發(fā)圍棋對(duì)弈系統(tǒng)，個(gè)人設(shè)計(jì)的任務(wù)不同，而且是同時(shí)進(jìn)行各自子系統(tǒng)的設(shè)計(jì)工作

74、，每個(gè)人每天都會(huì)在一定程度上修改自己的相應(yīng)子系統(tǒng)，為了方便文本數(shù)據(jù)的管理，設(shè)計(jì)時(shí)嘗試地使用了VSS代碼控制系統(tǒng)，以一臺(tái)機(jī)器為服務(wù)器，其余成員安裝VSS的客戶端軟件，并創(chuàng)建相應(yīng)的工作目錄，只要通過該客戶端軟件登錄到VSS服務(wù)器上，CheckOut當(dāng)前要進(jìn)行工作的項(xiàng)目或文件，復(fù)制到自己的工作目錄進(jìn)行修改，如有修改的在工作結(jié)束時(shí)將其CheckIn提交給VSS服務(wù)器進(jìn)行統(tǒng)一更新，同時(shí)存有修改的記錄?？梢猿废e(cuò)誤的修改，極大地方便了對(duì)系統(tǒng)的管理，

75、并節(jié)省了許多時(shí)間。</p><p>　　第三章 勝負(fù)判斷功能的設(shè)計(jì)與實(shí)現(xiàn)</p><p>　　3.1 圍棋計(jì)算勝負(fù)的方法與規(guī)則</p><p>　　3.1.1 圍棋計(jì)算勝負(fù)的方法</p><p>　　圍棋判斷對(duì)局雙方勝負(fù)結(jié)果的方法有數(shù)子法、計(jì)目法和計(jì)點(diǎn)法。它們的實(shí)質(zhì)都是對(duì)棋盤上已明確具體歸屬地域的計(jì)算。所謂地域，是棋盤上已明確歸屬的位點(diǎn)總

76、和，地域應(yīng)包括棋盤上已成活的所有棋塊以及雙活棋塊所共有的公氣。地域的歸屬由對(duì)局雙方用行棋的自然方式?jīng)Q定，地域的形成和歸屬在終局時(shí)由裁判仲裁，不由任何一方單方面決定。</p><p><b>　　1. 計(jì)目法</b></p><p>　　計(jì)目法，也稱比目法，是我國最早的判定勝負(fù)的方法。計(jì)目法計(jì)算的計(jì)量單位是目，目就是由活子所圍成的空點(diǎn)，一個(gè)空點(diǎn)就是一目，計(jì)目法是對(duì)所屬部

77、分位點(diǎn)的計(jì)算，用簡單的文字表述，就是計(jì)算比較雙方終局時(shí)所圍的地域目數(shù)，并以目數(shù)多少來判斷勝負(fù)結(jié)果。也可以認(rèn)為，目是對(duì)局雙方著子權(quán)的價(jià)值表示。計(jì)目就是計(jì)算雙方各喪失多少所有權(quán)或著子權(quán)，或者說，得到多少所有權(quán)或著子權(quán)。因此，計(jì)目法特點(diǎn)在強(qiáng)調(diào)棋子的圍地效能，沒有圍到空的棋子稱為單官。計(jì)目法由于只計(jì)算所圍的地域目數(shù)，收完單官與否并不影響勝負(fù)結(jié)果，因而規(guī)定棋局終局不收單官。所以是否收完所有單官，是數(shù)子法和計(jì)目法在終局時(shí)的主要區(qū)別。</p&g

78、t;<p>　　棋塊（棋形，棋串）是棋子的集合，棋塊成活的最低條件是不能被對(duì)方從棋盤上一手提取，非雙活棋塊成活的最低條件是至少具有2個(gè)真眼眼位。狹義的眼位具有排他性，即敵子可以在眼位內(nèi)存在，但不能在眼位內(nèi)存活。成活棋塊由構(gòu)成活形的棋子以及棋子所圍成的空組成，所謂空，由地域內(nèi)未經(jīng)著子的位點(diǎn)和對(duì)方已經(jīng)著子但不能存活的位點(diǎn)組成。空是廣義的眼位，因而空也具有排他性，如果敵子能在空內(nèi)存活，則空立即消失不存在，空內(nèi)未著子位點(diǎn)全部還原為

79、公共所有狀態(tài)，甚至還可能威脅到己方棋塊的生存。空的排他性明確表明了空的歸屬，同時(shí)原屬公共所有狀態(tài)的位點(diǎn)，也因?yàn)榕懦藢?duì)方的所有權(quán)（著子權(quán)），而由2目變?yōu)榱?目?？帐悄康募希苫钇鍓K一旦定型，其空目數(shù)保持基本不變，空的這一特性，是計(jì)目可以作為形勢(shì)判斷和勝負(fù)判斷的主要依據(jù)。由于對(duì)局雙方的著子權(quán)是對(duì)等相同的，是可以互相抵消的，而雙方的死子也是容易清點(diǎn)計(jì)算的，所以對(duì)全部歸屬位點(diǎn)的計(jì)算統(tǒng)計(jì)，可以簡化為比較雙方歸屬的空位點(diǎn)數(shù)量和死子數(shù)量之總和，并

80、以此判斷雙方的勝負(fù)。</p><p>　　計(jì)目法的一個(gè)缺陷之處，就是死子不能由提取來證明，尤其對(duì)于圍棋初學(xué)者，死活判斷不是那么準(zhǔn)確，多下一手就損失一目，若不下，又不放心。且如果雙方對(duì)死活產(chǎn)生歧義，還是不易解決。</p><p>　　圖3-1 計(jì)目法例1</p><p>　　如圖3-1，黑1是無意義的一手棋，如無黑1，是8個(gè)空點(diǎn)，即8目棋，下黑1后，現(xiàn)只有7目，即黑

81、1不但沒有增加空點(diǎn)，反而減少了自己的空。</p><p>　　圖 3-2 計(jì)目法例2</p><p>　　如圖3-2，黑1提兩個(gè)白子，在計(jì)目法是損手，角上黑棋由9目變成8目。</p><p><b>　　2. 數(shù)子法</b></p><p>　　數(shù)子法是根據(jù)棋局終局后對(duì)局雙方的棋子在棋盤上所歸屬位點(diǎn)的多少來判斷勝負(fù)結(jié)果

82、的。數(shù)子法是對(duì)所屬全部位點(diǎn)（地域）的計(jì)算，計(jì)量單位是子。前圖3-1中， 黑1雖是無用之著，但無損于角上空域。</p><p>　　數(shù)子法必須收完盤面上的所有單官，否則就無法知道雙方終局所得的子數(shù)，也就無法與歸本數(shù)相比較得出明確的勝負(fù)結(jié)果。</p><p>　　所謂歸本數(shù)，是指數(shù)子法的基礎(chǔ)勝負(fù)標(biāo)準(zhǔn)。因?yàn)闃?biāo)準(zhǔn)圍棋棋盤總計(jì)有361個(gè)交叉點(diǎn)，所以對(duì)局雙方每方應(yīng)得點(diǎn)數(shù)應(yīng)為總點(diǎn)數(shù)的一半，即180.5點(diǎn)

83、。多于此數(shù)者勝，少于此數(shù)者敗，等于此數(shù)者和。故數(shù)子法的一個(gè)明顯的優(yōu)越之處，就是不易引起糾紛，如果對(duì)局雙方對(duì)勝負(fù)結(jié)果有分歧有異議發(fā)生糾葛，那么化解爭(zhēng)端的最佳方案就是實(shí)戰(zhàn)解決，比任何理論道理都管用。前圖3-2中，黑地不會(huì)因提取而減少。</p><p><b>　　3. 計(jì)點(diǎn)法</b></p><p>　　從表面上看，計(jì)點(diǎn)法與數(shù)子法沒什么大的區(qū)別，也是以棋盤總點(diǎn)數(shù)361為準(zhǔn)

84、，誰超過半數(shù)誰就獲勝。一塊活棋中，棋子是1點(diǎn)，空也是1點(diǎn)。道理和數(shù)子法一樣，但是計(jì)點(diǎn)法要較數(shù)子法精密和復(fù)雜些，計(jì)算時(shí)不會(huì)破壞棋形，也容易查證。</p><p><b>　　4. 子數(shù)與目數(shù)</b></p><p>　　如前所述，我們可以導(dǎo)出數(shù)子法和計(jì)目法的關(guān)系式：</p><p>　　black+white+G=361</p>&

85、lt;p>　　其中：black=黑棋終局子數(shù)；white=白棋終局子數(shù)；G=無爭(zhēng)公共位點(diǎn)數(shù)=單官數(shù)+雙活公氣數(shù)；</p><p>　　從以上關(guān)系式可以發(fā)現(xiàn)：當(dāng)G=0時(shí)，即收完全部單官，數(shù)子法不變；如black或white﹥361/2時(shí)，為勝方，如black或white=361/2時(shí)，為平局。</p><p>　　把上面的關(guān)系式變換移位，得black+white=361-G我們可以發(fā)現(xiàn)

86、數(shù)子法不收單官，同樣可以計(jì)算勝負(fù)，不過基礎(chǔ)標(biāo)準(zhǔn)即歸本數(shù)發(fā)生了位移變小，但勝負(fù)結(jié)果不變。</p><p>　　3.1.2 圍棋計(jì)算勝負(fù)的規(guī)則</p><p>　　目前的圍棋規(guī)則有三種，即中國規(guī)則、日本規(guī)則和應(yīng)氏規(guī)則。</p><p>　　1. 中國規(guī)則計(jì)算勝負(fù)</p><p>　　中國規(guī)則又稱數(shù)子規(guī)則，子空皆地，主要在春蘭杯及中國國內(nèi)使用。它規(guī)

87、定“雙方下子完畢的棋局，計(jì)算勝負(fù)采用數(shù)子法。 先將雙方死子全部清理出盤外，然后對(duì)一方的活棋（包括活棋圍住的點(diǎn)）以子為單位進(jìn)行計(jì)數(shù)。 雙方活棋之間的空點(diǎn)各得一半，一個(gè)點(diǎn)即為一子。 勝負(fù)的基準(zhǔn)以棋局總點(diǎn)數(shù)的一半180又1/2點(diǎn)為歸本數(shù)。凡一方活棋與所屬空點(diǎn)的總和大于此數(shù)者為勝，小于此數(shù)者為負(fù)，等于此數(shù)者為和。 采用貼子方式的棋局，勝負(fù)標(biāo)準(zhǔn)另行規(guī)定?！盵B3]</p><p>　　關(guān)于貼子的規(guī)定：“ 為了抵消黑方先手的

88、效率，現(xiàn)行全國性正式比賽在終局計(jì)算勝負(fù)時(shí)，黑方需貼出三又四分之三子?！盵B4]因此，黑184又1/4，白176又3/4為雙方分別獲勝的基數(shù)。</p><p>　　對(duì)終局有以下規(guī)定： </p><p>　　“一、棋局下到雙方一致確認(rèn)著子完畢，為終局。</p><p>　　二、對(duì)局中，有一方中途認(rèn)輸，為終局?！盵B5]</p><p>　　關(guān)于終

89、局判斷的規(guī)定：</p><p>　　“一、除總則第七條的規(guī)定外，凡比賽一方棄權(quán)或因各種原因被裁判員判負(fù)、判和的對(duì)局， 也作終局處理。 </p><p>　　二、雙方確認(rèn)的終局，確認(rèn)的次序應(yīng)是，先由輪走方，后是對(duì)方以異色棋子一枚放于已方 棋盤右下角的線外。”[B6]</p><p>　　2. 日本規(guī)則計(jì)算勝負(fù)</p><p>　　日本規(guī)則又稱數(shù)

90、目規(guī)則，空才算地、死子加倍。日本規(guī)則使用較為廣泛，在除應(yīng)氏杯、春蘭杯外的所有國際比賽中，均使用該規(guī)則。日本、韓國的國內(nèi)比賽，也使用日本規(guī)則。但兩國在貼目等方面有微小差異。</p><p>　　在日本圍棋規(guī)則中，某一方的活棋所圍住的空點(diǎn)稱為“目”，目以外的空點(diǎn)稱為“單官”，有單官存在的活棋稱為“雙活棋”，雙活棋以外的活棋的目稱為“地”，地的一點(diǎn)即為“一目棋”。完全的并且獨(dú)立生存的活棋的目稱為地，而共有單官才得以生存

91、的雙活棋，因其本身不是獨(dú)立的活棋，所以其為主的目不是地。 [B7]</p><p>　　其中對(duì)勝負(fù)的規(guī)定有：</p><p>　　1．雙方達(dá)成終局協(xié)議后，相互把自己地中的對(duì)方死棋子取出，加算到提子中。</p><p>　　2．用提子互填對(duì)方的地，比較雙方地的目數(shù)，多的一方為勝。相同時(shí)稱之為“和棋”。3．一方對(duì)勝負(fù)有異議時(shí)，必須通過復(fù)盤再現(xiàn)等辦法，再次確認(rèn)勝負(fù)。<

92、;/p><p>　　4．雙方確認(rèn)勝負(fù)后，不能以任何理由來加以改變。[B8] </p><p>　　日韓圍棋規(guī)則都采用計(jì)目法。依日韓規(guī)則，雙活棋形一概不計(jì)目數(shù)并不合理。雙活是棋形成活的一種特殊形式，由棋局行棋過程自然形成，和普通兩眼成活棋形一樣，也不能從棋盤上被一手提取，從而滿足構(gòu)成活的要件，因此構(gòu)成帶眼雙活棋形的眼位理應(yīng)等同普通成活棋形。在眼位目數(shù)不等時(shí)，或一方有眼一方無眼的雙活棋形，如果按計(jì)

93、目法，形成眼位的空點(diǎn)數(shù)應(yīng)按成空目數(shù)計(jì)算，如果按數(shù)子法，則空點(diǎn)數(shù)應(yīng)按子數(shù)計(jì)算。</p><p>　　圖 3-3 雙活棋形</p><p>　　如果雙活棋形不計(jì)目數(shù)起源于要還“棋塊頭”的中國唐宋棋規(guī)的“填空法”，則屬于“填空法”內(nèi)在邏輯的必然結(jié)果。但現(xiàn)代計(jì)目法不用還“棋塊頭”，因而無論從法理上，還是用內(nèi)在的邏輯推理，都缺乏充分的必然依據(jù)。日本規(guī)則，吃掉的死子要拿起來，否則會(huì)不準(zhǔn),所以日本規(guī)則

94、更適合耍賴, 只要偷拿對(duì)方吃掉自己的幾個(gè)棋子,就可以很容易地扭轉(zhuǎn)局勢(shì)。</p><p>　?。? 應(yīng)氏規(guī)則計(jì)算勝負(fù)</p><p>　　應(yīng)氏規(guī)則僅在由應(yīng)氏杯中使用。其中關(guān)于勝負(fù)計(jì)算規(guī)定：“子空皆地 填滿計(jì)點(diǎn)”，</p><p>　　它創(chuàng)“子空皆地、空屬鄰界”為勝負(fù)準(zhǔn)則：凡“活子”及其“屬空”皆為“域點(diǎn)”。</p><p>　　同時(shí)創(chuàng)“填滿計(jì)點(diǎn)

95、、以子量地”為計(jì)算實(shí)務(wù)：原有鄰界一子未變，勝負(fù)點(diǎn)數(shù)即使是初學(xué)者也可一目了然。</p><p>　　關(guān)于填滿規(guī)定：四虛終局后，即須計(jì)點(diǎn)。余空稱“勝空”，余子稱“負(fù)子”。雙活中鄰界黑白兼有之“公空”，多于一空各填其半，少至一空不得填子。</p><p>　　關(guān)于計(jì)算規(guī)定：勝負(fù)點(diǎn)數(shù)之計(jì)算以“差值”為準(zhǔn)，公空無差值，勝空一點(diǎn)，負(fù)子、還子、罰子、每子三點(diǎn)。點(diǎn)多者勝，分“不計(jì)勝”、“計(jì)點(diǎn)勝”。[B9]

96、 </p><p>　　3.2 圍棋勝負(fù)判斷的實(shí)現(xiàn)</p><p>　　綜上分析，本系統(tǒng)在設(shè)計(jì)時(shí)對(duì)終局計(jì)算勝負(fù)采用了中國規(guī)則的數(shù)子法。</p><p>　　終局是指收官完了，該進(jìn)行勝負(fù)計(jì)算而言。因此，對(duì)弈雙方認(rèn)為棋局結(jié)束，點(diǎn)擊菜單欄“判斷勝負(fù)”時(shí)（如圖3-4），系統(tǒng)會(huì)提醒“是否已收完所有單官子”（如圖3-5）。</p><p>　　圖 3-

97、4 終局判斷勝負(fù)</p><p>　　圖3-5 提示是否收完單官</p><p>　　該對(duì)話框只是起到提示雙方收棋盤上的單官的作用。但系統(tǒng)設(shè)計(jì)中沒收單官也判斷勝負(fù)，只是會(huì)有出入。</p><p>　　雙方收官完畢后，要提掉死子，對(duì)話框如圖3-6所示。</p><p>　　圖3-6 提死子對(duì)話框</p><p>　

98、　圖3-7即為圖3-4的棋局提掉死子后的圖。</p><p>　　圖 3-7 死子提畢</p><p>　　提掉所有的死子后，系統(tǒng)數(shù)棋。實(shí)現(xiàn)流程圖如圖3-8所示。這里定義了Item的數(shù)據(jù)結(jié)構(gòu)，用于記錄每一枚棋子的顏色及搜索的狀態(tài)：</p><p>　　Public Type Items</p><p>　　Value As Integer

99、</p><p>　　Checked As Boolean</p><p><b>　　End Type</b></p><p>　　定義終局棋譜數(shù)組：Public m_GameOverMap(1 To 19, 1 To 19) As Items</p><p>　　終局的每一結(jié)點(diǎn)存儲(chǔ)為Item結(jié)構(gòu)

100、，記錄每一點(diǎn)的歸屬。</p><p>　　對(duì)待盤棋局（用m_Map（19，19）記錄）上每一點(diǎn)用循環(huán)掃描，記錄每一點(diǎn)是哪一方的領(lǐng)域。函數(shù)及子過程調(diào)用情況如下：</p><p>　　BeginVictory → CountGameOverMap（） → VerifyItemColor（row，column）→ ItemIsColor（row，column，color）</p>

101、;<p><b>　　“→”表示調(diào)用。 </b></p><p>　　圖 3-8 勝負(fù)判斷實(shí)現(xiàn)流程圖</p><p>　　其中，ItemIsColor（row，column，color）函數(shù)用于記錄（row，column）點(diǎn)是否屬于color色的地域。</p><p>　　VerifyItemColor（row，column）檢

102、測(cè)（row，column）點(diǎn)屬于哪一方。 </p><p>　　CountGameOverMap數(shù)終局棋盤子過程，并計(jì)入終局棋譜m_GameOverMap（19，19）。</p><p>　　BeginVictory對(duì) m_GameOverMap（19，19）的每個(gè)個(gè)交叉點(diǎn)進(jìn)行計(jì)算，黑地域計(jì)+1，白子計(jì)-1，并將黑地域填充黑子，白地域填白子，當(dāng)單官子為奇數(shù)時(shí)，若該黑落子總數(shù)+1，否則-1。

103、讓子棋的基本數(shù)的計(jì)算是：180又1/2+讓子數(shù)的一半=黑棋基本數(shù)，計(jì)算時(shí)，計(jì)（減讓子數(shù)/2）。黑先行貼還3又3/4子（-3.75）。計(jì)算畢，總數(shù)total若大于零，則黑勝，反之白勝，勝子數(shù)為｜total｜。圖3-9即為單擊“完畢”后的計(jì)算結(jié)果。具體代碼詳見附錄。</p><p>　　圖 3-9 判斷結(jié)果</p><p>　　在實(shí)際對(duì)弈中，終局后開始計(jì)算勝負(fù)，術(shù)語叫“做棋”。為實(shí)現(xiàn)此功能，

104、加入了“填入黑子”和“填入白子”按鈕，在棋盤的鼠標(biāo)按下事件Board_MouseDown中設(shè)置。見前圖3-9右側(cè)。</p><p>　　3.3 繼續(xù)以前對(duì)局的設(shè)計(jì)與實(shí)現(xiàn)</p><p>　　圍棋對(duì)弈時(shí)，有時(shí)是非連續(xù)時(shí)間的對(duì)局，因此需要保存正在對(duì)弈的棋局及相關(guān)數(shù)據(jù)，如對(duì)弈雙方所用時(shí)間，該哪一方落子，當(dāng)前步數(shù)以及打劫信息的記錄等。為此，在圍棋對(duì)弈系統(tǒng)中設(shè)計(jì)了“繼續(xù)以前對(duì)局”這一功能。<

105、/p><p>　　圖3-10 繼續(xù)以前對(duì)局</p><p>　　打開已保存的一盤棋，用VB中“Open”對(duì)話框控件打開文件，讀入相應(yīng)表示棋盤的狀態(tài)的數(shù)據(jù)，包括對(duì)弈雙方姓名、雙方用時(shí)、讓子棋數(shù)、手?jǐn)?shù)、該那一方落子、是否有打劫、打劫位置等信息，并把這些數(shù)據(jù)寫到記錄棋局的數(shù)組M_map(19,19)中，重新置棋盤信息，并根據(jù)這些數(shù)據(jù)畫棋盤，棋子，顯示相應(yīng)信息。如果打開的棋局格式與該格式不同則顯示“

106、格式不正確”。</p><p>　　圖3-11 打開以前的對(duì)局</p><p>　　第四章 局面分析功能的設(shè)計(jì)與實(shí)現(xiàn)</p><p>　　圍棋的最終目的是圍空，占領(lǐng)地盤，但是棋子的作用顯然不僅僅是圍得實(shí)空，每一枚棋子都有它的本身價(jià)值，這由棋盤上位點(diǎn)的本身價(jià)值決定，其價(jià)值實(shí)質(zhì)即由圍棋的本身對(duì)局形勢(shì)所決定。在最終確定雙方實(shí)地之前，如何標(biāo)識(shí)和衡量棋子在棋局中發(fā)揮的作用

107、，對(duì)局面進(jìn)行分析，這是圍棋對(duì)弈系統(tǒng)設(shè)計(jì)的一個(gè)重要內(nèi)容，目的是輔助下棋者判斷形勢(shì)，并為將來“人-機(jī)”對(duì)弈時(shí)，計(jì)算機(jī)判斷形勢(shì)打下基礎(chǔ)。</p><p>　　4.1 圍棋局面分析的影響模型</p><p>　　在對(duì)圍棋當(dāng)前局面進(jìn)行分析時(shí)，通常采用影響模型來解決這個(gè)問題，利用影響模型將棋子向棋盤其他部分輻射的影響量化。</p><p>　　4.1.1 影響模型概念<

108、/p><p>　　首先介紹圍棋中“外勢(shì)”的概念，外勢(shì)表征著棋子對(duì)外的影響。例如圖4-1中的黑子把白角包圍起來。白角形成了近10目的實(shí)空，而黑棋則對(duì)外方有著強(qiáng)大的影響，也就是有強(qiáng)大的外勢(shì)。</p><p><b>　　圖 4-1 外勢(shì)</b></p><p>　　在圍棋程序中，影響這個(gè)概念是泛指，不僅包括外勢(shì)。圖4-1中的白子雖因不能對(duì)中腹和兩邊發(fā)

109、出影響而無外勢(shì)，但這些白子仍有對(duì)角上空位的影響，其結(jié)果是把這些空位控制在白方而形成實(shí)空。</p><p>　　一個(gè)棋子的作用不僅僅體現(xiàn)在它的幾個(gè)鄰接點(diǎn)上，也不僅僅作用于其后的一兩步棋，它的作用可以波及到較遠(yuǎn)地域并且持續(xù)很長時(shí)間，尤其體現(xiàn)在開局階段和棋盤上比較廣闊的地方。勢(shì)是一種圍棋概念，它表明了每一方棋子對(duì)空點(diǎn)的最大可能的控制潛力。通過確保開局時(shí)子力投放不過于集中，棋手在后面的對(duì)局中將取得最大限度獲得領(lǐng)地的機(jī)會(huì)。