引言
本為主要對我在開發(fā)JAVA黑白棋人機算法過程中所用的博弈思想、估值函數(shù)、搜索算法分3個方面進行了闡述，由于本人水平有限，如果大家希望了解更多有關(guān)黑白棋博弈策略以及人機算法的深入的理論研究，可以參看本文最后的參考文獻，或者搜索其他相關(guān)資料。
黑白棋，又叫反棋（Reversi）、奧賽羅棋（Othello）、蘋果棋或翻轉(zhuǎn)棋。黑白棋在西方和日本很流行。游戲通過相互翻轉(zhuǎn)對方的棋子，最后以棋盤上誰的棋子多來判斷勝負。它的游戲規(guī)則簡單，因此上手很容易，但是它的變化又非常復(fù)雜。有一種說法是：只需要幾分鐘學(xué)會它，卻需要一生的時間去精通它。（本段摘自百度百科）
正文
一、黑白棋人機博弈思想
1.棋局階段應(yīng)合理劃分（一般分為三個階段），開局應(yīng)盡量用優(yōu)秀的定式
之所以要使用開局定式，個人的觀點為：即使最頂級的機器能夠從第一步一直搜索到最后一步，也必然不能斷定誰最終會贏，要不然這個游戲就沒有存在的價值了。
基于上面的觀點，必然走到某一種局面的時候，才可以斷定輸贏，當然這個輸贏不是絕對的，更不是最終意義上的輸贏，因為對方有可能不按最優(yōu)路線行棋。于是我們便需要利用優(yōu)秀的開局為自己爭取盡可能大的優(yōu)勢，迫使對方失誤或者為自己爭取勝利的保障。
2.穩(wěn)定子具有絕對優(yōu)勢
所謂穩(wěn)定子，就是指再后續(xù)的行棋過程中始終不會被翻轉(zhuǎn)的棋子。最明顯的穩(wěn)定子就是角位置的棋子，同時當角位置被占取之后，角周圍的棋子，尤其是兩條邊上的，也會較容易成為穩(wěn)定子。棋局終了時棋盤上的所有子都可以看做是穩(wěn)定子。
當然，穩(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.奇偶性理論
所謂奇偶性，就是指如果在對弈過程中沒有任何一方停步，那么當黑棋下完后，棋盤總會有奇數(shù)個空位，而當白棋下完后，棋盤總會有偶數(shù)個空位。
我們可以推斷，如果沒有任何一方停步，那么白棋會走完最后一步棋并應(yīng)該略微占優(yōu)一定的優(yōu)勢。但如果有一方停步時，這個奇偶性就會顛倒過來，當再有一方停步的時候，奇偶性就又會恢復(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è)當前無法判斷輸贏，對棋局的評估值計算后為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)自己一定會輸。當然，我們期望的過程是這樣的：不能確定輸贏，取最優(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)值取負，這樣在運算時只需要各個值取相反數(shù)，就成為了對方在行棋時對我方收益而言的一張權(quán)值表，這樣便只需要做一張權(quán)值表就可以了。
②對于各個位置權(quán)值的確定是要綜合各種情況并不斷試驗的，但同時也要符合一些基本的邏輯。比如我們設(shè)角位的權(quán)值為a（a>0，對己方有利），星位的權(quán)值為b（b<0，對己方不利），那么應(yīng)該有a+b>-b，因為如果a+b<-b，那么我們可以將其變形成-a-b>b，也就是說對方同時占角位和星位為我們帶來的收益要大于我們只占一個星位而來帶來的收益（這里的收益都是負值），也就是說，電腦寧肯讓對方占一個角位和一個星位，自己也不會去只占那個星位而不占角位，這顯然在大部分情況下是不符合邏輯的。
結(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é)果的情況的考慮
當機器可以搜到最終結(jié)果時，我們就不宜再用權(quán)值表等統(tǒng)計權(quán)值的方法來衡量棋局的優(yōu)劣，因為最終子數(shù)多者一定獲勝，但依棋局的估值函數(shù)，算出的權(quán)值卻不一定時較大者。
因此，當可以搜索到最終結(jié)果時，我們便需要對估值函數(shù)的返回值做修改：
①如果我們選擇的是取值為[-1,1]的實數(shù)概率的估值函數(shù)，那么當確定自己獲勝的時候就可以返回1，失敗時返回-1，平局時返回0。當然，更為方便的方法就是直接返回己方與對方的棋子數(shù)之差，同時，出于對規(guī)則的考慮，我們也要這么做，因為現(xiàn)行的規(guī)定是：雙方分先下偶數(shù)局數(shù)的棋(如4局)，勝1分，負0分，和0.5分，分數(shù)多的取勝，假如分數(shù)一樣，就以棋子數(shù)目來計算勝負。于是，確定為贏時，我們贏得棋子越多越好，而確定會輸?shù)臅r候，輸?shù)迷缴僭胶谩?/span>
②如果我們選擇的是取值為[-INF,INF]的整數(shù)化概率的評估函數(shù)，那么當確定自己獲勝時返回INF+己方與對方棋子之差，確定自己失敗時則返回-INF+己方與對方棋子之差，平局時返回0。
6.估值函數(shù)的實現(xiàn)（也即對各項影響棋局因素的權(quán)值進行合并）
當可以搜索到最終結(jié)果的情況我們已經(jīng)在前面討論過了，因而在這里我就主要闡述一下對在搜索過程中無法得到最終結(jié)果時估值函數(shù)的實現(xiàn)的一些看法。
我們不妨設(shè)各項因素的權(quán)值分別為a1，a2……an，如果采用的是實數(shù)概率值的估值函數(shù)，那么一般同時滿足-1<an<1。
在合并的時候，按是否線性合并可以分為下面兩種合并方式：
①非線性合并
若執(zhí)行非線性合并，其優(yōu)點在于最后的估值會更加精準，畢竟大多數(shù)涉及概率的函數(shù)都是非線性的，但缺點在于非線性合并的函數(shù)形式是比較難確定的。同時，因為涉及到整數(shù)進行非線性運算的精度的問題，如果采用整數(shù)化概率值的估值函數(shù)，是不宜使用非線性合并的。
②線性合并
線性合并的優(yōu)點在于函數(shù)形式是確定的，我們后續(xù)的工作就是確定出各項的前導(dǎo)系數(shù)就可以了。
我們設(shè)線性合并公式中各項的前導(dǎo)系數(shù)分別為p1，p2，……，pn，那么最終的估值就是value=p1*a1+p2*a2+……+pn*an，并且如果選擇的是實數(shù)概率的估值函數(shù)，那么一般還會滿足p1+p2+……+pn=1。
出于容易實現(xiàn)這一角度的考慮，我還是選用了線性合并，由于我只考慮了每個位置的權(quán)值和邊緣子的數(shù)量，如果兩個因素的權(quán)值分別為a1、a2，那么我的程序的估值函數(shù)的形式就是value=p1*a1+p2*a2。
在選擇了線性合并之后，那么最大的難題就在于確定p1與p2的值。在猜測兩個參數(shù)的值時，我遵循了兩條原則：①衡量各項估值之間的大小差異，做到盡量平衡，但又有所側(cè)重；②選取盡量小的整數(shù)作為pn的值，這樣需要測試的情況的種數(shù)也會減少很多。
通過這樣的猜測和測試，最終v4.7采用的p1與p2的值分別為3和7。
三、黑白棋博弈樹搜索算法及其實現(xiàn)
1.Min-Max搜索
在機器與人對弈的過程中，機器事先并不知道人的水平如何，因而機器只能假設(shè)人走的每一步都會為自己帶來最小的收益，而機器走的每一步都要為自己爭取最大的收益，這就是極大極小原理。
如果我們把機器和人接連走的每一步畫成樹狀結(jié)構(gòu)的話（也即博弈樹，見上圖），對于每一個節(jié)點，其子節(jié)點是下一步所有可能走的位置（有可能是對方走，也有可能是自己走），對于葉子節(jié)點我們運用一次估值函數(shù)得到葉子的權(quán)值，之后便一直向上反推，直到得到根節(jié)點的權(quán)值。我們把每一次機器要走的節(jié)點叫做Max節(jié)點，因為這個節(jié)點的值是其子節(jié)點所有值中的最大值，而把每一人要走的節(jié)點叫做Min節(jié)點，因為這個節(jié)點的值是其子節(jié)點所有值中的最小值。這樣得到的根結(jié)點的值，就是機器走這一步的期望的最大收益。
基于這樣的算法，我們進行迭代深搜是可以實現(xiàn)的。深搜函數(shù)的返回值對于Max節(jié)點而言就是所有子節(jié)點的最大值，而對于Min節(jié)點而言就是所有子節(jié)點的最小值。
同時，在深搜過程中，我們要不斷更新、記錄棋盤的狀態(tài)，但對于黑白棋而言，比較棘手的一個問題就是自己每下一步，不僅會改變己方棋子的分布，同時還會改變對方棋子的分布，這樣對于將下過一個棋子的棋盤還原成沒下之前的棋盤是十分困難的，因而我們不能采用傳統(tǒng)的深搜函數(shù)的形式（對訪問位置做標記，深搜并得到返回值，抹去對訪問位置的標記），于是我們在迭代的時候就要不斷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)有的時間，當節(jié)點多時就少搜幾步，而當節(jié)點少時就多搜幾步。具體實現(xiàn)的方法就是取一個變量branches記錄當前節(jié)點還可以向下搜索的總節(jié)點數(shù)，而對當前節(jié)點的子節(jié)點進行深搜時，傳遞過去的參變量就變成了branches除以當前節(jié)點擁有的子節(jié)點的數(shù)量，當branches為0或者雙方都無子可下時，就要調(diào)用估值函數(shù)了。
2.α-β搜索
前面已經(jīng)說過了，α-β搜索實際上就是運用α-β剪枝優(yōu)化后的Min-Max搜索，其基本的極大極小的思想是不變的。
我們首先引入兩個變量α、β，表示當前節(jié)點在前面的深搜過程中，依據(jù)子節(jié)點的返回值來估計出的當前節(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的值了，我們當然沒必要多搜索F和G了。
上面不去搜索F和G的過程就是剪枝的過程，確切來說是α剪枝的過程。下面就給出α剪枝和β剪枝的定義：
①如果當前節(jié)點是Min節(jié)點，當前節(jié)點的父節(jié)點是Max節(jié)點，那么當當前節(jié)點的一個子節(jié)點的值小于當前節(jié)點的α值時，那么當前節(jié)點的其余子節(jié)點就不用搜索了，這個過程稱為α剪枝過程。
②如果當前節(jié)點是Max節(jié)點，當前節(jié)點的父節(jié)點是Min節(jié)點，那么當當前節(jié)點的一個子節(jié)點的值大于當前節(jié)點的β值時，那么當前節(jié)點的其余子節(jié)點就不用搜索了，這個過程稱為β剪枝過程。
通過上面的實例，我們也觀察到，當前節(jié)點α、β的值是不斷依據(jù)子節(jié)點的返回值進行更新的，并作為深搜函數(shù)的參數(shù)進行下一個子節(jié)點的深搜。其中根節(jié)點的α、β的值分別初始化為-INF、INF。
一般來說，當前節(jié)點是Min節(jié)點時，如果子節(jié)點的返回值小于當前節(jié)點的β值，那么β值就會更新成為返回值，當返回值同時小于或者等于當前節(jié)點的α值時，如果同時當前節(jié)點的父節(jié)點是Max節(jié)點，就會產(chǎn)生剪枝的過程。
同樣的，當前節(jié)點是Max節(jié)點時，如果子節(jié)點的返回值大于當前節(jié)點的α值，那么α值就會更新成為返回值，當返回值同時大于或者等于當前節(jié)點的β值時，如果同時當前節(jié)點的父節(jié)點是Min節(jié)點，就會產(chǎn)生剪枝的過程。
我們發(fā)現(xiàn)上面討論的兩種情況都是當前節(jié)點與父節(jié)點不是同類節(jié)點的情況，那么如果當前節(jié)點和父節(jié)點是同類節(jié)點呢（也即發(fā)生了停步的情況）？這時就沒辦法進行剪枝了。
通過上面的討論，我們注意到，在深搜的過程中，我們同時要用一個參數(shù)來傳遞父親節(jié)點的類型，如果父親節(jié)點和當前節(jié)點是同類節(jié)點時，即便滿足了一部分的剪枝條件，也是不能進行剪枝的。
后記
黑白棋的人機算法是博大精深的，一直到v4.7這個版本我才只是剛剛研究到最基本的對Min-Max搜索的優(yōu)化，還有更多的諸如歷史表和置換表以及啟發(fā)式搜索等優(yōu)化方法還有待進一步學(xué)習(xí)。
通過這次黑白棋項目的實踐，我由衷的感覺到了算法的重要性，以后還要在ACM競賽的準備中不斷學(xué)習(xí)更多的算法并應(yīng)用到軟件開發(fā)中來。機器的優(yōu)勢在于快速而精準的暴力，而算法的作用就在于使其在有效實時間和空間內(nèi)，盡可能地多得發(fā)揮它的優(yōu)勢。
參考文獻
[1] 柏愛俊.幾種智能算法在黑白棋程序中的應(yīng)用.
[2] 黑白棋對弈策略指南-玄黃整理版
[3] 黑白文檔
P.S. 黑白棋游戲的jar文件我掛在了另一篇博客《JAVA黑白棋之學(xué)習(xí)感悟》的下面，大家
可以下載下來玩一玩哈。如果有什么意見或者建議，還望各位不吝賜教哈O(∩_∩)O~
聯(lián)系客服
