博弈圍棋社成員結(jié)構(gòu)

培訓(xùn)部

組織結(jié)構(gòu)

社長副社長秘書部宣傳部組織部外聯(lián)部本社團(tuán)在東莞城市學(xué)院開展社團(tuán)活動(dòng)。各由社長、副社長/理事、秘書部、培訓(xùn)部、組織部、宣傳部、外聯(lián)部組成。社長

社團(tuán)的總負(fù)責(zé)人，負(fù)責(zé)社團(tuán)活動(dòng)大綱制定，社團(tuán)總體規(guī)劃等。全面負(fù)責(zé)社團(tuán)的各項(xiàng)事務(wù)，召開、主持社團(tuán)部門大會(huì)等會(huì)議；享有會(huì)議最終決議權(quán)；協(xié)調(diào)部門間的關(guān)系。代表社團(tuán)簽署相關(guān)重要文件，代表社團(tuán)參加各種活動(dòng)。副社長

協(xié)助社長處理日常事務(wù)；配合社長的總體工作。協(xié)助社長主持社團(tuán)工作和社團(tuán)會(huì)議、召集社團(tuán)全體成員開會(huì)。對(duì)各部門工作進(jìn)行監(jiān)督和指導(dǎo)，了解各部門成員的意見和建議，及時(shí)解決問題。社長不在時(shí)，代理社長處理社團(tuán)工作。秘書部

負(fù)責(zé)整理、保管社團(tuán)的各種資料、檔案；負(fù)責(zé)擬寫各種統(tǒng)計(jì)報(bào)告、總結(jié)、通知、新聞稿等文書；主要負(fù)責(zé)社團(tuán)內(nèi)的財(cái)務(wù)的支出和收入，并做好財(cái)務(wù)的收支情況登記；安排通知協(xié)會(huì)各種會(huì)議和重要活動(dòng)，做好活動(dòng)考勤登記及會(huì)議記錄。宣傳部

負(fù)責(zé)社團(tuán)及各部門的宣傳工作，提高社團(tuán)的知名度。工作內(nèi)容包括海報(bào)的設(shè)計(jì)、書寫和張貼工作以及制作PPT、視頻等；負(fù)責(zé)活動(dòng)的會(huì)場(chǎng)設(shè)計(jì)及布置等工作；保管宣傳物品。組織部

負(fù)責(zé)本社團(tuán)組織工作，做好活動(dòng)策劃和活動(dòng)總結(jié)。組織和策劃內(nèi)部活動(dòng)，活躍社團(tuán)內(nèi)部氣氛，增進(jìn)協(xié)會(huì)內(nèi)部成員的交流與溝通；組織實(shí)施各類棋類比賽，籌備活動(dòng)場(chǎng)地及活動(dòng)所需物品。培訓(xùn)部

制定比賽流程，比賽規(guī)則，負(fù)責(zé)棋藝教學(xué)，棋隊(duì)管理，棋譜記錄和裁判工作。教授社員棋藝知識(shí)，培養(yǎng)棋手積極參加各類棋藝比賽，負(fù)責(zé)社團(tuán)日常活動(dòng)的棋類保管。外聯(lián)部

負(fù)責(zé)本社團(tuán)對(duì)外聯(lián)絡(luò)交流工作，聯(lián)系校內(nèi)各個(gè)組織和校外各大院校進(jìn)行學(xué)術(shù)交流等對(duì)外交流。組織對(duì)外合作活動(dòng)以及對(duì)外校進(jìn)行棋藝交流，為本社團(tuán)開展的各種活動(dòng)拉贊助，活動(dòng)的接待工作。

擴(kuò)展閱讀：計(jì)算機(jī)博弈之黑白棋

JAVA黑白棋之算法淺析

一、黑白棋人機(jī)博弈思想

1.棋局階段應(yīng)合理劃分（一般分為三個(gè)階段），開局應(yīng)盡量用優(yōu)秀的定式之所以要使用開局定式，個(gè)人的觀點(diǎn)為：即使最頂級(jí)的機(jī)器能夠從第一步一直搜索到最后一步，也必然不能斷定誰最終會(huì)贏，要不然這個(gè)游戲就沒有存在的價(jià)值了。

基于上面的觀點(diǎn)，必然走到某一種局面的時(shí)候，才可以斷定輸贏，當(dāng)然這個(gè)輸贏不是絕對(duì)的，更不是最終意義上的輸贏，因?yàn)閷?duì)方有可能不按最優(yōu)路線行棋。于是我們便需要利用優(yōu)秀的開局為自己爭取盡可能大的優(yōu)勢(shì)，迫使對(duì)方失誤或者為自己爭取勝利的保障。

2.穩(wěn)定子具有絕對(duì)優(yōu)勢(shì)所謂穩(wěn)定子，就是指再后續(xù)的行棋過程中始終不會(huì)被翻轉(zhuǎn)的棋子。最明顯的穩(wěn)定子就是角位置的棋子，同時(shí)當(dāng)角位置被占取之后，角周圍的棋子，尤其是兩條邊上的，也會(huì)較容易成為穩(wěn)定子。棋局終了時(shí)棋盤上的所有子都可以看做是穩(wěn)定子。

當(dāng)然，穩(wěn)定子有絕對(duì)的優(yōu)勢(shì)，并不意味著我們見角就奪，比如斯通納陷阱就是一個(gè)很好的例子。

3.內(nèi)部子具有相對(duì)的優(yōu)勢(shì)

所謂內(nèi)部子，就是被一方的棋子圍困在內(nèi)部的另一方的棋子。

內(nèi)部子的優(yōu)勢(shì)主要體現(xiàn)在：①內(nèi)部子是半穩(wěn)定子或者穩(wěn)定子，不易被對(duì)方吃掉；②擁有較多的內(nèi)部子，可以提高己方的行動(dòng)力（可下子位置的數(shù)量），限制對(duì)方的行動(dòng)力，從而更容易設(shè)置陷阱，迫使對(duì)方走出很差的棋步，進(jìn)而使自己占有一定的優(yōu)勢(shì)。

4.邊緣子具有相對(duì)的劣勢(shì)所謂邊緣子，可以看作是除去邊角之外的周圍有空位的棋子，或者可以理解為包圍內(nèi)部子且與內(nèi)部子異色的周圍有空位的棋子。

邊緣子實(shí)際上是相對(duì)于內(nèi)部子而言的，因?yàn)檫吘壸拥牧觿?shì)也恰好是與內(nèi)部子相對(duì)的：①邊緣子在現(xiàn)有棋局下多數(shù)是不穩(wěn)定的，但在后續(xù)行棋過程中可能成為對(duì)方或者己方的穩(wěn)定子；②為對(duì)方制造陷阱提供了更多的機(jī)會(huì)。

5.奇偶性理論所謂奇偶性，就是指如果在對(duì)弈過程中沒有任何一方停步，那么當(dāng)黑棋下完后，棋盤總會(huì)有奇數(shù)個(gè)空位，而當(dāng)白棋下完后，棋盤總會(huì)有偶數(shù)個(gè)空位。

我們可以推斷，如果沒有任何一方停步，那么白棋會(huì)走完最后一步棋并應(yīng)該略微占優(yōu)一定的優(yōu)勢(shì)。但如果有一方停步時(shí)，這個(gè)奇偶性就會(huì)顛倒過來，當(dāng)再有一方停步的時(shí)候，奇偶性就又會(huì)恢復(fù)正常。

因此，黑棋總是希望構(gòu)造強(qiáng)制性的奇數(shù)次停步。同時(shí)，黑棋想要獲得奇偶性的優(yōu)勢(shì)的另外一個(gè)可行的辦法就是：建立一種這樣的局面，使得每次黑棋下完之后棋盤上有且僅有奇數(shù)個(gè)擁有奇數(shù)個(gè)空位的空白區(qū)域，并且這些區(qū)域是白棋無法進(jìn)入的，或者一旦白棋進(jìn)入，黑棋就會(huì)擁有絕對(duì)的優(yōu)勢(shì)。

二、機(jī)器容易實(shí)現(xiàn)的評(píng)判棋局優(yōu)劣的因素，以及估值函數(shù)的實(shí)現(xiàn)

既然要評(píng)判棋局的優(yōu)劣，那么就必然要想破譯密碼那樣把棋盤上所有棋子的分布轉(zhuǎn)化成一個(gè)數(shù)值，以數(shù)值的大小來衡量己方的收益情況，而轉(zhuǎn)化的方式就是估值函數(shù)。

一般估值的形式有以下兩種：

①采用概率的思想，數(shù)值的取值范圍為[0,1]，確定為勝局時(shí)值為1，敗局時(shí)值為0，平局時(shí)值為0.5。假設(shè)當(dāng)前無法判斷輸贏，對(duì)棋局的評(píng)估值計(jì)算后為a，那么綜合值就是0.5+a。也可優(yōu)化一下，把取值區(qū)間看做[-1,1]，這樣確定勝局時(shí)值為1，敗局時(shí)值為-1，平局時(shí)值為0。

②將概率思想中的實(shí)數(shù)整數(shù)化，即對(duì)概率值乘以INF，這樣取值區(qū)間就變成了[-INF,INF]。

估值函數(shù)這個(gè)模塊是整個(gè)程序中最核心的一個(gè)模塊，之所以這樣說，是因?yàn)闊o論怎樣優(yōu)化搜索過程，在現(xiàn)有的條件下搜索層數(shù)也是有限的，如果這個(gè)模塊沒有做好，很容易出現(xiàn)這樣的過程：不能確定輸贏，取最優(yōu)-->……-->不能確定輸贏，取最優(yōu)-->發(fā)現(xiàn)自己一定會(huì)輸。當(dāng)然，我們期望的過程是這樣的：不能確定輸贏，取最優(yōu)-->……-->不能確定輸贏，取最優(yōu)-->發(fā)現(xiàn)自己一定會(huì)贏。

想要盡可能出現(xiàn)我們期望的過程，那么一般便有三種措施：一是選用優(yōu)秀的開局定式，二是提高估值函數(shù)模塊的性能，三是通過對(duì)搜索算法的優(yōu)化來加深搜索層數(shù)。

對(duì)于選用優(yōu)秀的開局定式，是受到百度百科上對(duì)一款外國棋力頂尖的黑白棋軟件的簡介的啟發(fā)，但對(duì)于如何存儲(chǔ)和實(shí)現(xiàn)開局定式，我還只是處于萌芽階段，在此就不妄加分析了。對(duì)于對(duì)搜索算法的優(yōu)化，我會(huì)放在下一個(gè)版塊來闡述一些我的學(xué)習(xí)的心得。

下面就主要闡述一下我對(duì)如何讓機(jī)器對(duì)人考慮機(jī)博弈思想并實(shí)現(xiàn)對(duì)棋局進(jìn)行評(píng)估的一些看法，也即對(duì)提高估值函數(shù)這個(gè)模塊的性能的一些看法。

1.對(duì)穩(wěn)定子的考慮

對(duì)穩(wěn)定子的考慮在理論上是很有意義的，因?yàn)樽罱K棋局比的實(shí)際上還是穩(wěn)定子的數(shù)量，但對(duì)穩(wěn)定子進(jìn)行判斷這個(gè)過程是不容易實(shí)現(xiàn)的，而且我在一個(gè)論壇上也看到有個(gè)帖子說，在高強(qiáng)度的對(duì)局中，一般都要四五十步之后才會(huì)出現(xiàn)穩(wěn)定子，而這時(shí)搜索函數(shù)已經(jīng)可以搜索到底了�；�于這一點(diǎn)，對(duì)穩(wěn)定子判斷的意義也就體現(xiàn)在40-60步中還不能確定誰輸誰贏的情況。

考慮到這些，我決定放棄對(duì)穩(wěn)定子的判斷而轉(zhuǎn)化成兩個(gè)部分，一個(gè)是對(duì)邊角位置利用權(quán)值表去判斷己方的收益，另一個(gè)就是對(duì)中間部分的位置，轉(zhuǎn)化成對(duì)內(nèi)部子與邊緣子的考慮，因?yàn)閮?nèi)部子、邊緣子與穩(wěn)定子之間是有一定的聯(lián)系的。

2.對(duì)邊角位置的考慮

說起權(quán)值表，我們肯定很容易想到角位權(quán)值大，而C位（與角相鄰的邊上的位置）和星位（與叫相鄰的除去C位之后剩下的那個(gè)位置）的權(quán)值小。但對(duì)權(quán)值表的設(shè)定過程中，還要注意一些細(xì)節(jié)：

①為了方便計(jì)算，不妨把對(duì)己方有力的位置的權(quán)值取正，對(duì)己方不利的位置的權(quán)值取負(fù)，這樣在運(yùn)算時(shí)只需要各個(gè)值取相反數(shù)，就成為了對(duì)方在行棋時(shí)對(duì)我方收益而言的一張權(quán)值表，這樣便只需要做一張權(quán)值表就可以了。

②對(duì)于各個(gè)位置權(quán)值的確定是要綜合各種情況并不斷試驗(yàn)的，但同時(shí)也要符合一些基本的邏輯。比如我們?cè)O(shè)角位的權(quán)值為a（a>0，對(duì)己方有利），星位的權(quán)值為b（b-b，因?yàn)槿绻鸻+bb，也就是說對(duì)方同時(shí)占角位和星位為我們帶來的收益要大于我們只占一個(gè)星位而來帶來的收益（這里的收益都是負(fù)值），也就是說，電腦寧肯讓對(duì)方占一個(gè)角位和一個(gè)星位，自己也不會(huì)去只占那個(gè)星位而不占角位，這顯然在大部分情況下是不符合邏輯的。

結(jié)合我個(gè)人針對(duì)自己的程序研發(fā)的權(quán)值表以及一張外國人研發(fā)的權(quán)值表，對(duì)其中有些值進(jìn)行了修改，生成了一張新的權(quán)值表，也就是在v4.7中使用的權(quán)值表。權(quán)值表如下：

{100,-5,10,5,5,10,-5,100},{-5,-45,1,1,1,1,-45,-5},{10,1,3,2,2,3,1,10},{5,1,2,1,1,2,1,5},{5,1,2,1,1,2,1,5},{10,1,3,2,2,3,1,10},{-5,-45,1,1,1,1,-45,-5},{100,-5,10,5,5,10,-5,100}3.對(duì)內(nèi)部子和邊緣子的考慮

由于內(nèi)部子和邊緣子是相對(duì)的，在對(duì)程序要求不是很高的情況下，我們可以只研究其中一方。同時(shí)，結(jié)合實(shí)戰(zhàn)經(jīng)驗(yàn)，邊緣子數(shù)量對(duì)棋局的影響程度要高于內(nèi)部子，因而我們不妨抓住主要矛盾去研究邊緣子的多少。

在對(duì)邊緣子的研究過程中，我又研發(fā)了另一種間接統(tǒng)計(jì)邊緣子的方式，即統(tǒng)計(jì)一個(gè)邊緣子周邊的空格數(shù)，然后取相反數(shù)（邊緣子越多，一定程度上對(duì)己方越不利）作為這個(gè)邊緣子的權(quán)值。之所以這么做，是希望能夠融合對(duì)行動(dòng)力（可落子位置的總數(shù)）的考慮，因?yàn)檫吘壸又車�空位的�?shù)量一定程度上體現(xiàn)了對(duì)方行動(dòng)力的大小。但后來在實(shí)際應(yīng)用過程中，這種想法并沒有達(dá)到我預(yù)想的效果，可能是因?yàn)閷?duì)不同的情況，二者之間的線性關(guān)系并不明顯，于是我便轉(zhuǎn)而只單純地去考慮邊緣子的數(shù)量。

4.對(duì)奇偶性理論的考慮因?yàn)閷?duì)于這個(gè)部分，代碼實(shí)現(xiàn)起來比較困難，所以我并沒有把這個(gè)部分的理論應(yīng)用到我的程序之中。但就百度百科上的資料顯示，國外一個(gè)十分強(qiáng)大的黑白棋軟件是把棋手行棋是否具有奇偶性也納入了考慮范圍之內(nèi)的。

5.對(duì)可以搜到最終結(jié)果的情況的考慮當(dāng)機(jī)器可以搜到最終結(jié)果時(shí)，我們就不宜再用權(quán)值表等統(tǒng)計(jì)權(quán)值的方法來衡量棋局的優(yōu)劣，因?yàn)樽罱K子數(shù)多者一定獲勝，但依棋局的估值函數(shù)，算出的權(quán)值卻不一定時(shí)較大者。

因此，當(dāng)可以搜索到最終結(jié)果時(shí)，我們便需要對(duì)估值函數(shù)的返回值做修改：①如果我們選擇的是取值為[-1,1]的實(shí)數(shù)概率的估值函數(shù)，那么當(dāng)確定自己獲勝的時(shí)候就可以返回1，失敗時(shí)返回-1，平局時(shí)返回0。當(dāng)然，更為方便的方法就是直接返回己方與對(duì)方的棋子數(shù)之差，同時(shí)，出于對(duì)規(guī)則的考慮，我們也要這么做，因?yàn)楝F(xiàn)行的規(guī)定是：雙方分先下偶數(shù)局?jǐn)?shù)的棋(如4局)，勝1分，負(fù)0分，和0.5分，分?jǐn)?shù)多的取勝，假如分?jǐn)?shù)一樣，就以棋子數(shù)目來計(jì)算勝負(fù)。于是，確定為贏時(shí)，我們贏得棋子越多越好，而確定會(huì)輸?shù)臅r(shí)候，輸?shù)迷缴僭胶谩?/p>

②如果我們選擇的是取值為[-INF,INF]的整數(shù)化概率的評(píng)估函數(shù)，那么當(dāng)確定自己獲勝時(shí)返回INF+己方與對(duì)方棋子之差，確定自己失敗時(shí)則返回-INF+己方與對(duì)方棋子之差，平局時(shí)返回0。

6.估值函數(shù)的實(shí)現(xiàn)（也即對(duì)各項(xiàng)影響棋局因素的權(quán)值進(jìn)行合并）當(dāng)可以搜索到最終結(jié)果的情況我們已經(jīng)在前面討論過了，因而在這里我就主要闡述一下對(duì)在搜索過程中無法得到最終結(jié)果時(shí)估值函數(shù)的實(shí)現(xiàn)的一些看法。

我們不妨設(shè)各項(xiàng)因素的權(quán)值分別為a1，a2……an，如果采用的是實(shí)數(shù)概率值的估值函數(shù)，那么一般同時(shí)滿足-1Max節(jié)點(diǎn)，因?yàn)檫@個(gè)節(jié)點(diǎn)的值是其子節(jié)點(diǎn)所有值中的最大值，而把每一人要走的節(jié)點(diǎn)叫做Min節(jié)點(diǎn)，因?yàn)檫@個(gè)節(jié)點(diǎn)的值是其子節(jié)點(diǎn)所有值中的最小值。這樣得到的根結(jié)點(diǎn)的值，就是機(jī)器走這一步的期望的最大收益。

基于這樣的算法，我們進(jìn)行迭代深搜是可以實(shí)現(xiàn)的。深搜函數(shù)的返回值對(duì)于Max節(jié)點(diǎn)而言就是所有子節(jié)點(diǎn)的最大值，而對(duì)于Min節(jié)點(diǎn)而言就是所有子節(jié)點(diǎn)的最小值。

同時(shí)，在深搜過程中，我們要不斷更新、記錄棋盤的狀態(tài)，但對(duì)于黑白棋而言，比較棘手的一個(gè)問題就是自己每下一步，不僅會(huì)改變己方棋子的分布，同時(shí)還會(huì)改變對(duì)方棋子的分布，這樣對(duì)于將下過一個(gè)棋子的棋盤還原成沒下之前的棋盤是十分困難的，因而我們不能采用傳統(tǒng)的深搜函數(shù)的形式（對(duì)訪問位置做標(biāo)記，深搜并得到返回值，抹去對(duì)訪問位置的標(biāo)記），于是我們?cè)诘�代的時(shí)候就要不斷new一個(gè)數(shù)組來存儲(chǔ)變化之后的棋盤，并作為深搜函數(shù)的參數(shù)，傳遞給下一個(gè)節(jié)點(diǎn)。

由于深搜節(jié)點(diǎn)的數(shù)量是指數(shù)級(jí)增長的，如果我們不對(duì)深搜層數(shù)進(jìn)行一定的限制，那么程序的運(yùn)行時(shí)間將是一個(gè)很龐大的數(shù)字。對(duì)于未加優(yōu)化的的搜索，如果限定30s之內(nèi)要行棋的話，最壞情況也只能搜索5層左右，因而我們必然要對(duì)Min-Max搜索算法進(jìn)行優(yōu)化，來提升程序的棋力，一種有效的方法就是對(duì)Min-Max進(jìn)行α-β剪枝優(yōu)化，也就是接下來要討論的α-β搜索。

現(xiàn)在先拋開優(yōu)化搜索算法的問題，我們?cè)谑褂肕in-Max搜索算法編出的程序時(shí)，會(huì)發(fā)現(xiàn)往往最后結(jié)局電腦往往會(huì)很快就能走出一步棋，原因在于到了后期，博弈樹每層的節(jié)點(diǎn)數(shù)很變得很少，而這時(shí)機(jī)器完全有時(shí)間做出更深層次的搜索，因而我們可以采用用限定搜索節(jié)點(diǎn)的方式來取代限定搜索層數(shù)的方式進(jìn)行深搜，這樣我們就可以充分利用現(xiàn)有的時(shí)間，當(dāng)節(jié)點(diǎn)多時(shí)就少搜幾步，而當(dāng)節(jié)點(diǎn)少時(shí)就多搜幾步。具體實(shí)現(xiàn)的方法就是取一個(gè)變量branches記錄當(dāng)前節(jié)點(diǎn)還可以向下搜索的總節(jié)點(diǎn)數(shù)，而對(duì)當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)進(jìn)行深搜時(shí)，傳遞過去的參變量就變成了branches除以當(dāng)前節(jié)點(diǎn)擁有的子節(jié)點(diǎn)的數(shù)量，當(dāng)branches為0或者雙方都無子可下時(shí)，就要調(diào)用估值函數(shù)了。

2.α-β搜索

前面已經(jīng)說過了，α-β搜索實(shí)際上就是運(yùn)用α-β剪枝優(yōu)化后的Min-Max搜索，其基本的極大極小的思想是不變的。

我們首先引入兩個(gè)變量α、β，表示當(dāng)前節(jié)點(diǎn)在前面的深搜過程中，依據(jù)子節(jié)點(diǎn)的返回值來估計(jì)出的當(dāng)前節(jié)

點(diǎn)最后的結(jié)果的下限和上限。

以下圖為例，我們來討論一下α-β搜索剪枝的原理：

首先，我們初始化A點(diǎn)的下限為-INF，上限為INF，要知道A點(diǎn)的值就要搜索B點(diǎn)，搜索B點(diǎn)后得知B的值為6，那么我們就可以更新A點(diǎn)的下限為6，因?yàn)锳點(diǎn)是Max節(jié)點(diǎn)，也即A點(diǎn)的α值為6。這時(shí)我們繼續(xù)搜索C點(diǎn)，我們將A點(diǎn)的下限6和上限INF同時(shí)作為參數(shù)傳給子節(jié)點(diǎn)C，顯然C的值至少要在6和INF之間A才有可能更新成C的值。要知道C點(diǎn)的值我們就要繼續(xù)搜索E點(diǎn)，同樣把下限6和上限INF傳遞給點(diǎn)E，顯然E要在6和INF之間，C點(diǎn)的值才有可能在6和INF之間，那么A點(diǎn)才有可能更新成C點(diǎn)的值。而搜索E點(diǎn)時(shí)我們發(fā)現(xiàn)E點(diǎn)值為-2，不在6和INF之間，這時(shí)我們還有必要搜索F和G點(diǎn)嗎？顯然沒有必要，因?yàn)榉凑鼳是不會(huì)更新成C的值了，我們當(dāng)然沒必要多搜索F和G了。

上面不去搜索F和G的過程就是剪枝的過程，確切來說是α剪枝的過程。下面就給出α剪枝和β剪枝的定義：

①如果當(dāng)前節(jié)點(diǎn)是Min節(jié)點(diǎn)，當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)是Max節(jié)點(diǎn)，那么當(dāng)當(dāng)前節(jié)點(diǎn)的一個(gè)子節(jié)點(diǎn)的值小于當(dāng)前節(jié)點(diǎn)的α值時(shí)，那么當(dāng)前節(jié)點(diǎn)的其余子節(jié)點(diǎn)就不用搜索了，這個(gè)過程稱為α剪枝過程。

②如果當(dāng)前節(jié)點(diǎn)是Max節(jié)點(diǎn)，當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)是Min節(jié)點(diǎn)，那么當(dāng)當(dāng)前節(jié)點(diǎn)的一個(gè)子節(jié)點(diǎn)的值大于當(dāng)前節(jié)點(diǎn)的β值時(shí)，那么當(dāng)前節(jié)點(diǎn)的其余子節(jié)點(diǎn)就不用搜索了，這個(gè)過程稱為β剪枝過程。

通過上面的實(shí)例，我們也觀察到，當(dāng)前節(jié)點(diǎn)α、β的值是不斷依據(jù)子節(jié)點(diǎn)的返回值進(jìn)行更新的，并作為深搜函數(shù)的參數(shù)進(jìn)行下一個(gè)子節(jié)點(diǎn)的深搜。其中根節(jié)點(diǎn)的α、β的值分別初始化為-INF、INF。

一般來說，當(dāng)前節(jié)點(diǎn)是Min節(jié)點(diǎn)時(shí)，如果子節(jié)點(diǎn)的返回值小于當(dāng)前節(jié)點(diǎn)的β值，那么β值就會(huì)更新成為返回值，當(dāng)返回值同時(shí)小于或者等于當(dāng)前節(jié)點(diǎn)的α值時(shí)，如果同時(shí)當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)是Max節(jié)點(diǎn)，就會(huì)產(chǎn)生剪枝的過程。

同樣的，當(dāng)前節(jié)點(diǎn)是Max節(jié)點(diǎn)時(shí)，如果子節(jié)點(diǎn)的返回值大于當(dāng)前節(jié)點(diǎn)的α值，那么α值就會(huì)更新成為返回值，當(dāng)返回值同時(shí)大于或者等于當(dāng)前節(jié)點(diǎn)的β值時(shí)，如果同時(shí)當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)是Min節(jié)點(diǎn)，就會(huì)產(chǎn)生剪枝的過程。

我們發(fā)現(xiàn)上面討論的兩種情況都是當(dāng)前節(jié)點(diǎn)與父節(jié)點(diǎn)不是同類節(jié)點(diǎn)的情況，那么如果當(dāng)前節(jié)點(diǎn)和父節(jié)點(diǎn)是同類節(jié)點(diǎn)呢（也即發(fā)生了停步的情況）？這時(shí)就沒辦法進(jìn)行剪枝了。

通過上面的討論，我們注意到，在深搜的過程中，我們同時(shí)要用一個(gè)參數(shù)來傳遞父親節(jié)點(diǎn)的類型，如果父親節(jié)點(diǎn)和當(dāng)前節(jié)點(diǎn)是同類節(jié)點(diǎn)時(shí)，即便滿足了一部分的剪枝條件，也是不能進(jìn)行剪枝的。

后記

黑白棋的人機(jī)算法是博大精深的，一直到v4.7這個(gè)版本我才只是剛剛研究到最基本的對(duì)Min-Max搜索的優(yōu)化，還有更多的諸如歷史表和置換表以及啟發(fā)式搜索等優(yōu)化方法還有待進(jìn)一步學(xué)習(xí)。

通過這次黑白棋項(xiàng)目的實(shí)踐，我由衷的感覺到了算法的重要性，以后還要在ACM競(jìng)賽的準(zhǔn)備中不斷學(xué)習(xí)更多的算法并應(yīng)用到軟件開發(fā)中來。機(jī)器的優(yōu)勢(shì)在于快速而精準(zhǔn)的暴力，而算法的作用就在于使其在有效實(shí)時(shí)間和空間內(nèi)，盡可能地多得發(fā)揮它的優(yōu)勢(shì)。

友情提示：本文中關(guān)于《博弈圍棋社成員結(jié)構(gòu)》給出的范例僅供您參考拓展思維使用，博弈圍棋社成員結(jié)構(gòu)：該篇文章建議您自主創(chuàng)作。

來源：網(wǎng)絡(luò)整理 免責(zé)聲明：本文僅限學(xué)習(xí)分享，如產(chǎn)生版權(quán)問題，請(qǐng)聯(lián)系我們及時(shí)刪除。

《博弈圍棋社成員結(jié)構(gòu)》由互聯(lián)網(wǎng)用戶整理提供,轉(zhuǎn)載分享請(qǐng)保留原作者信息,謝謝!
鏈接地址：http://www.hmlawpc.com/gongwen/624912.html

• 上一篇：校學(xué)生會(huì)期末工作感想
• 下一篇：青志部手拉手