【導(dǎo)讀】亞馬遜棋是歐洲國家的一種棋種，是1988. 年阿根廷的WalterZamkauskas發(fā)明的，名的八皇后問題貌似神合。的研究相對還很少。機(jī)器博弈通俗來說就是讓機(jī)器下棋，之所。是現(xiàn)代智能化研究水平的集中體現(xiàn)。能的較量，更是計(jì)算機(jī)智能軟件的較量。自從計(jì)算機(jī)誕生以來，眾多著名學(xué)者都曾經(jīng)涉足。這一領(lǐng)域的研究工作。計(jì)算機(jī)之父馮·諾依曼就提。出了極大極小定理用于解決博弈問題。創(chuàng)始人香儂教授，又給出了極大極小算法。弈水平迅速上升。其中心任務(wù)是研究如何使計(jì)算。機(jī)器博弈屬于博弈論研究的范。目前，研究最多的是棋類的機(jī)器博。博弈論，又稱對策論，是使。決策的均衡問題。博弈論的早期思想源于。按照參與人行動的次序可以把博弈論分為。按照參與人之間的利益關(guān)系可以把博弈論。亞馬遜、蘇拉卡爾塔是完全信息動態(tài)博弈。根據(jù)棋規(guī)產(chǎn)生合法走法，以使博弈公正地進(jìn)行，亞馬遜棋是一種比較新的，典型的占領(lǐng)地。根據(jù)對亞馬遜棋的描述，雙方行棋的目的。亞馬遜棋的棋盤格子位置用數(shù)字00-99表示，

　　

【正文】 搜索適合用于解決節(jié)點(diǎn)個數(shù)少的問題，深度優(yōu)先搜索一般用來求解節(jié)點(diǎn)數(shù)特別多的問題。極大極小算法雖然是經(jīng)典的搜索算法，但是在搜索過程中總要判斷哪一方要取極大值哪一方要取極小值。因此，選擇它的優(yōu)化算法負(fù)極大值算法，雖然它本質(zhì)上與極大極小算法是一樣的，仍然是一種窮盡搜索算法，但與極大極小算法相比較，程序要短而且簡單。 αβ 剪枝算法可以進(jìn)行有效的剪枝。綜合以上考慮，考慮選擇 αβ 剪枝算法，深度優(yōu)先搜索和負(fù)極大值搜索算法相結(jié)合作為基本搜索算法。 ? 用 αβ剪枝搜索算法首先要設(shè)定合適的 α、 β值，然后對當(dāng)前棋局根據(jù)深度優(yōu)先原則進(jìn)行博弈樹展開。 ? 在負(fù)極大值搜索和 αβ剪枝算法相結(jié)合的基礎(chǔ)上，根據(jù)亞馬遜棋對弈一定回合后必然出現(xiàn)每方的棋子在某固定區(qū)域的特點(diǎn)，本程序加入了一些信息，主要是對一些特殊區(qū)域的判斷，也就是地盤的判斷。 ? 圖中局勢，黑方四顆棋子全在區(qū)域 (A， B， C， D)內(nèi)，白方不能進(jìn)入。 ? 定義一個區(qū)域判斷函數(shù)。判斷棋子是否全在固定的區(qū)域后，使用不同的搜索函數(shù)。 ? 對棋局進(jìn)行區(qū)域判斷： ? (1) 經(jīng)過區(qū)域判斷，如果棋子不全在限定的區(qū)域內(nèi)，那么按正常的方法搜索，定義搜索函數(shù)為： ? Search(int depth,int alpha,int bate,boolismyturn,int first,bool myturn) ? ismyturn//輪到哪方走棋，依層數(shù)改變 ? myturn //當(dāng)前哪方走棋，不依層數(shù)改變 ? 主要搜索部分的代碼如下： ? GoNumber=PMakeHowDo(GoWay,ismyturn)。//不全在區(qū)域內(nèi)的著法生成函數(shù) ? if(depth!=first)//判斷是否走棋 ? { ? for(i=0。iGoNumber。i++) //所有可能的走法 ? { ? makemove(GoWay[i][0],GoWay[i][1],GoWay[i][2],ismyturn)。//將當(dāng)前局面應(yīng)用此走法，變?yōu)樽庸?jié)點(diǎn)的局面 ? value=Search(depth1,bate,alpha,!ismyturn,first,myturn)。//遞歸搜索子節(jié)點(diǎn) ? unmakemove(GoWay[i][0],GoWay[i][1],GoWay[i][2],ismyturn)。 ? //撤銷搜索過的子節(jié)點(diǎn) ? if(alphavalue) ? alpha=value。 //保存最大值 ? if(alpha=bate) ? return alpha。//beta剪枝 ? } ? return alpha。//返回極大值 ? } ? else ? { ? for(i=0。iGoNumber。i++) ? { ? makemove(GoWay[i][0],GoWay[i][1],GoWay[i][2],ismyturn)。 ? value=Search(depth1,bate,alpha,!ismyturn,first,myturn)。 ? unmakemove(GoWay[i][0],GoWay[i][1],GoWay[i][2],ismyturn)。 ? if(alphavalue) ? { ? alpha=value。//設(shè)置最佳走法 ? bestgo=i。//最佳走法就是電腦選擇的著法 ? } ? } ? } ? (2) 經(jīng)過區(qū)域判斷，如果棋子全在限定的區(qū)域內(nèi)，那么進(jìn)行特定的搜索。定義搜索函數(shù)為： ? Search1(int depth,int first,int stu)//只搜索一個子 ? 主要搜索部分的代碼如下： ? GoNumber=PMake1HowDo(GoWay,stu)。//全部在區(qū)域內(nèi)的著法生成函數(shù) ? if(depth!=first) ? { ? for(i=0。iGoNumber。i++) ? { ? makemove(GoWay[i][0],GoWay[i][1],GoWay[i][2],false)。 ? value=Search1(depth1,first,GoWay[i][1])。 ? unmakemove(GoWay[i][0],GoWay[i][1],GoWay[i][2],false)。 ? if(alphavalue) ? alpha=value。 ? } ? return alpha。 ? } ? Else ? { ? for(i=0。iGoNumber。i++) ? { ? makemove(GoWay[i][0],GoWay[i][1],GoWay[i][2],false)。 ? value=Search1(depth1,first,GoWay[i][1])。 ? unmakemove(GoWay[i][0],GoWay[i][1],GoWay[i][2],false)。 ? if(alphavalue) ? { ? alpha=value。 ? bestgo=i。 ? } ? } ? } ? αβ剪枝算法通過“剪枝”技巧很大程度上縮小了博弈樹的規(guī)模，另外，在搜索之前對棋局進(jìn)行區(qū)域判斷，對特定的棋局狀態(tài)進(jìn)行不同的搜索函數(shù)搜索，搜索效率明顯得到提高。 ? 搜索引擎的完整過程的流程 估值函數(shù)的設(shè)計(jì) ? 評估函數(shù)是除了搜索算法以外，另一個對博弈樹求解的重要方面。只有有了良好的估值函數(shù)才能保證較快地找到最佳著法。而估值函數(shù)是對棋局的綜合評估，該函數(shù)的好壞直接決定棋力的強(qiáng)弱。通常情況下，估值函數(shù)在很大程度上依賴于具體的游戲規(guī)則和我們對該游戲的經(jīng)驗(yàn)知識。同時評估函數(shù)和搜索算法一樣是博弈樹搜索的核心。 ? 由于亞馬遜棋博弈的復(fù)雜性，在搜索樹展開時不可能到達(dá)最終的狀態(tài)，所以如果能對某些中間的狀態(tài)進(jìn)行較為準(zhǔn)確的評估就不需要展開到真正的最終狀態(tài)便可以得到不錯的結(jié)果。所以，只有有了良好的評估函數(shù)，搜索模塊才能保證有效地找到最優(yōu)解，該函數(shù)的好壞直接影響搜索過程中的取舍而決定著法的好壞。雖然并不存在絕對準(zhǔn)確的評估函數(shù)，但綜合大量的亞馬遜棋的相關(guān)知識，把局面的好壞程度轉(zhuǎn)化為一個相對準(zhǔn)確的數(shù)字，這個數(shù)字可以代表這個棋局的性質(zhì)。 ? 在亞馬遜棋博弈過程中，棋子的自由度是影響棋局非常重要的因素。本博弈系統(tǒng)中，在考慮棋子的自由度的基礎(chǔ)上，計(jì)算棋子所在位置的八個方向上可行空格子的數(shù)量，而且對可行格子的數(shù)量賦予較大的分值 10，每增加一個格子就加上 10。其中黑方賦予正值，白方賦予負(fù)值。 ? 對棋子所在位置情況的分析主要從棋子在棋盤邊框，四周位置是己方棋子、對方棋子、障礙、空格五方面來對某一方布子所形成的棋局狀態(tài)的評估。根據(jù)不同的情況對棋子的影響程度不同，分別對五種情況設(shè)定合適的分值。 ? 設(shè)定在邊框賦予分值 3；周圍為障礙賦予 4；為對方棋子賦予 3；為己方棋子賦予 5。其中黑方為負(fù)值，白方為正值。雙方棋子是鄰居，賦一次分值。 ? 一般來講，某方棋子之間的位置聯(lián)系相對小，也就是意味著本方棋子分布均勻，對棋盤的掌控能力也相對大。在對弈過程中雙方的可行區(qū)域越來越小，構(gòu)造的評估函數(shù)為： ? (1) 對弈 50步以下時 ? Value=freedom+score+a+b ? 定義 value為總的評估值， freedom為對棋子自由度的評估值， score為棋子所在位置旁邊八個方向的情況的評估值， a、 b為己方棋子、對方棋子之間的位置關(guān)系。 ? (2) 對弈 50步以上時 ? Value=freedom+score ? 式中，只包括棋子的自由度和己方棋子和對方棋子所在位置周圍的情況。 ? 通過全盤搜索，對以上因素進(jìn)行統(tǒng)計(jì)，然后根據(jù)評估函數(shù)賦值，對葉子節(jié)點(diǎn)進(jìn)行估值。 界面設(shè)計(jì) ? 程序的主要功能主要在鼠標(biāo)的左鍵消息中實(shí)現(xiàn)，它的流程圖如右： 第 6章總結(jié) ? (1)通過加入各個棋種的策略來優(yōu)化搜索算法 。剪枝搜索算法能夠在龐大的博弈樹中利用已經(jīng)搜索的信息剪掉不影響結(jié)果的子樹，結(jié)合哈希技術(shù)，避免對相同的局面重復(fù)搜索，也有效地提高了搜索效率。在搜索中將各個棋種知識顯示的表示出來并且指導(dǎo)搜索和剪枝，會使搜索的效率大幅提高，這樣就可以節(jié)省更多的時間來做更深層次的搜索了。 第 6章總結(jié) ? （ 2） 改進(jìn)估值函數(shù)，使之對局勢的判斷更靈敏，使之對于局面的評估更為精確。 ? 改進(jìn)的估值函數(shù)對提高棋力也是必不可少的。亞馬遜棋雖然采用的是傳統(tǒng)的靜態(tài)估值函數(shù)，但對各種因素的權(quán)值存在一些主觀的因素加以判斷，對局勢的好壞判斷不夠靈敏。由于估值函數(shù)是與具體的棋類知識緊密結(jié)合的一部分，所以我們可以在估值函數(shù)中加入更多的棋種知識，使之對于局面的評估更為精確。 第 6章總結(jié) ? (3)在開局階段單獨(dú)使用負(fù)極大值（或最大最小值）形式的 αβ剪枝搜索算法運(yùn)作速度慢。加入開局庫、殘局庫，提高亞馬遜棋開局和殘局階段的速率和準(zhǔn)確率。 ? (4) 完善人機(jī)界面，建立博弈公共平臺，減少后期開發(fā)代價。