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

　　

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