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

培訓(xùn)部

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

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

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

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

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

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

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

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

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

擴展閱讀：計算機博弈之黑白棋

JAVA黑白棋之算法淺析

一、黑白棋人機博弈思想

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.對邊角位置的考慮

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

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

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

結(jié)合我個人針對自己的程序研發(fā)的權(quán)值表以及一張外國人研發(fā)的權(quá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.對內(nèi)部子和邊緣子的考慮

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

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

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

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

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

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

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

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

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

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

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

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

2.α-β搜索

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

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

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

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

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

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

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

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

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

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

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

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

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

后記

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

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

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

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

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

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