【文章內容簡介】 8 ?2 … …… 采用 “裁剪”方法。不必再繼續(xù)考察結點 C 的剩余子結點了，因為結點 C 已經夠糟糕的了，不管結點 C 的剩余子結點有怎樣的分值，它最多只能傳回8（有可能其剩余子結點中還有分值更小的結點，因而結點 C 還有可能傳回更小的值）。而與前面已經分析過的結點 B 所傳回2 相比較，作為“最大一方”的你顯然更不愿意看到 2 的局面。所以，你當然不會選擇相應的著法使得局面發(fā)展成為結點 C。因為那樣的話，下一步你的對手就會帶給你一個分值不高于 2 的局面。由此，在不影響搜索質量的前提下避免了搜索“無價值的”結點 C 的剩余子結點的大量工作，從而節(jié)省了寶貴時間，為在同樣機器配置下搜索更多的層數提供了可能?！白钚∽畲蟆钡乃枷朐偌由稀皩涞牟眉簟?，這就是 AlphaBeta 搜索算法的核心。最基本的 AlphaBeta 算法的代碼如下：int AlphaBeta(int depth, int alpha, int beta){if (depth == 0) //如果是葉子節(jié)點（到達搜索深度要求）return Evaluate()。 //則由局面評估函數返回估值GenerateLegalMoves()。 //產生所有合法著法while (MovesLeft()) //遍歷所有著法{MakeNextMove()。 //執(zhí)行著法int val = AlphaBeta(depth 1, beta, alpha)。 //遞歸調用 UnmakeMove()。 //撤銷著法if (val = beta) //裁剪return beta。if (val alpha) //保留最大值alpha = val。}return alpha。} 著法排序AlphaBeta 搜索算法是在“最小最大”的基礎上引入 “樹的裁剪”的思想以期提高效率，它的效率將在很大程度上取決于樹的結構——如果搜索了沒多久就發(fā)現可以進行“裁剪”了，那么需要分析的工作量將大大減少，效率自然也就大大提高；而如果直至 分析了所有的可能性之后才能做出“裁剪”操作，那此時“裁剪”也已經失去了它原有的價值（因為你已經分析了所有情況，這時的 AlphaBeta 搜索已和“最小最大”搜索別無二致了） 。因而，要想保證 AlphaBeta 搜索算法的效率就需要調整樹的結構，即調整待搜索的結點的順序，使得“裁剪”可以盡可能早地發(fā)生。可以根據部分已經搜索過的結果來調整將要搜索的結點的順序。因為，通常當一個局面經過搜索被認為較好時，其子結點中往往有一些與它相似的局面（如個別無關緊要的棋子位置有所不同）也是較好的。由 所提出的“歷史啟發(fā)” （History Heuristic）就是建立在這樣一種觀點之上的。在搜索的過程中，每當發(fā)現一個好的走法，就給該走法累加一個增量以記錄其“歷史得分” ，一個多次被搜索并認為是好的走法的“歷史得分”就會較高。對于即將搜索的結點，按照“歷史得分”的高低對它們進行排序，保證較好的走法（“歷史得分”高的走法）排在前面，這樣 AlphaBeta 搜索就可以盡可能早地進行“裁剪” ，從而保證了搜索的效率。對于著法的排序可以使用各種排序算法，在程序中采用了歸并排序。歸并排序的空間復雜度為 O(n)，時間復雜度為 O(nlog2n)，具有較高的效率。 局面評估前文已經講過了棋局表示、著法生成、搜索算法（包括搜索輔助“歷史啟發(fā)” ） ， 在象棋程序中如果說搜索算法是心臟，那么局面評估就是大腦。搜索算法負責驅動整個程序，而局面評估則負責對搜索的內容進行判斷和評價。因而搜索與局面評估是整個下棋引擎的核心。首先，先介紹一下在局面評估中需要考慮的因素。就不同的棋類可能要考慮的因素略有差異。在中國象棋中所要考慮的最基本的幾個因素包括如下四點：子力總和子力是指某一棋子本身所具有的價值。通俗地講就是一個棋子它值個什么價。例如，車值 10 的話，那可能馬值 6，卒值 2 等等。所以在評估局面時，首先要考慮雙方的子力總和的對比。比如紅方擁有士象全加車馬炮，而黑方只有殘士象加雙馬，則紅方明顯占優(yōu)。棋子位置棋子位置，或稱控制區(qū)域，是指某一方的棋子在棋盤上所占據（控制）的位置。例如，沉底炮、過河卒、以及車占士角等都是較好的棋子位置狀態(tài)，而窩心馬、將離開底線等則屬較差的棋子位置狀態(tài)。 棋子的機動性棋子的機動性指棋子的靈活度（可移動性） 。例如，起始位置的車機動性較差，所以下棋講究早出車。同樣四面被憋馬腿的死馬機動性也較差（對于一步也不能走的棋子，可以認為其機動性為零） 。棋子的相互關系這一點的分析較為復雜，因為一個棋子與其它子之間往往存在多重關系。如：一個馬可能在對方的炮的攻擊之下同時它又攻擊著對方的車。在程序中，估值函數最后返回的是每一方的總分的差值，而各方的總分就是上面所提到的四個因素的打分的總和。對于子力打分和控制區(qū)域打分，只要遍歷棋盤，當遇到棋子時簡單地去查事先定義好的“子力價值表”和“控制區(qū)域價值表” ，取出相對應的值進行累加即可。對于機動性打分，需要求出各個子總共有多少種走法，然后根據各個子所不同的機動性價值每多一種走法就加一次相應的分數。 對棋子間相互關系的打分，要用到以下幾個數據：int m_BaseValue[15]。 //存放棋子基本價值int m_FlexValue[15]。 //存放棋子靈活性分值short m_AttackPos[10][9]。 //存放每一位置被威脅的信息BYTE m_GuardPos[10][9]。 //存放每一位置被保護的信息BYTE m_FlexibilityPos[10][9]。//存放每一位置上棋子的靈活性分值int m_chessValue[10][9]。 //存放每一位置上棋子的總價值其中計算機會進行所有棋子值的判斷，AttackPos 和 GuardPos 分別記錄該棋子受到的威脅和被保護的值。當遍歷一遍棋盤之后，子力打分、控制區(qū)域打分和機動性打分都可以完成，而關系表也可以填完。之后，再根據關系表來具體考察棋子的相互關系，進行關系打分。分析關系時，首先，對王的攻擊保護應分離出來單獨考慮，因為對王的保護沒有任何意義，一旦王被吃掉整個游戲就結束了。其次，對一個普通子，當它既受到攻擊又受到保護的時候要注意如下幾個問題：攻擊者子力小于被攻擊者子力，攻擊方將愿意換子。比如，一個車正遭受一個炮的攻擊，那么任何對車的保護都將失去意義——對方肯定樂意用一個炮來換一個車。多攻擊/單保護的情況，并且攻擊者最小子力小于被攻擊者子力與保護者子力之 和，則攻擊方可能以一子換兩子。三攻擊/兩保護的情況，并且攻擊者子力較小的二者之和小于被攻擊者子力與保護者子力之和，則攻擊方可能以兩子換三子。攻擊方與保護方數量相同，并且攻擊者子力小于被攻擊者子力與保護者子力之和再減去保護者中最大子力，則攻擊方可能以 n 子換 n 子。當然，上述四條只是覆蓋了最常見的幾種情況，覆蓋并不全面。而且，在程序中并沒有直接地重新考慮雙方兌子之后的控制區(qū)域及機動性變化情況（之所以說沒有“直接地重新考慮” ，是因為搜索繼續(xù)展開結點后仍會考慮這些因素，只是目前不知這樣效果是否受影響——考察這兩種方法在效果上的差異需要一定數量的試驗數據的支持） 。所以，如果今后要對引擎進行改進，提高程序的下棋水平的話，還應當在此進行研究。 悔棋和還原功能的實現悔棋和還原是棋類軟件中較為基本的功能。要實現悔棋和還原功能，首先要明確哪些信息應當被保存以供悔棋和還原所使用。在程序中保存了如下信息：棋局表示中所定義的棋盤數組；各棋子的貼圖位置；這里需要特別說明的是通常象棋程序處于程序效率的考慮并不保存所有棋子的信息，而只是保存之前一步的走棋信息。此后當悔棋的時候，需要撤銷著法；還原的時候，需要執(zhí)行著法。然而，在編寫自己的程序時一來考慮到程序的可讀性和不易出錯性，二來考慮到對當今的計算機的配置來說這點開銷基本上不會對程序的效率產生什么影響。因此保存了全部棋子的信息。根據所要保存的數據定義了如下基本結構類型：typedef struct{ CHESSMOVE cmChessMove。 short nChessID。//被吃掉的棋子}UNDOMOVE。在對弈過程中，每一回合都將棋局信息（這里指前面所說的需要保存的信息）保存至走法隊列，以供悔棋所用。還原功能是與悔棋功能相對應的，只有當產生了悔棋功能之后，還原功能才會被激活。一個回合的結束意味著前一次操作沒有悔棋功能的產生，因此還原隊列也應被清空。 在悔棋中主要完成了以下任務：下棋回合數減一；將當前局面信息保存至走法隊列，以供還原所用；從走法隊列中取出上一回合的棋局信息，恢復到當前局面，然后將其從隊列中剔除掉；將顯示著法名稱的列表框中的本回合的著法名稱保存到一個著法名稱隊列，以供還原所用。然后從列表框中刪除它。而在還原中所做的剛好和悔棋相反：下棋回合數加一；將當前局面信息保存至隊列，以供悔棋所用；從隊列中取出最近一次悔棋前的棋局信息，恢復到當前局面，然后將其從隊列中剔除；從走法隊列中取出最近一次存入的著法名稱（兩項，因為每回合會產生兩步著法） ，將其重新顯示到列表框中。然后將其從中剔除。以上便是悔棋和還原功能所完成的具體操作，其代碼分別寫入悔棋和還原按鈕（Button）的事件處理函數中。 著法名稱顯示功能的實現每當下棋者（用戶或是計算機）走一步棋，在棋盤旁邊的一個列表框控件（List