【文章內(nèi)容簡介】 的 DiscoveryAgent 類 和 DiscoveryListener 接 口 提 供 了 需 要 發(fā) 現(xiàn) 服 務(wù) 的 方 法 . ()方法可將設(shè)備設(shè)置為查詢模式,為了充分利用這種模式, 取消時會調(diào)用 ()方法. 如果一臺設(shè)備不想等待發(fā)現(xiàn)其它的設(shè)備, 可以使用 () 列表,或者返回一個預(yù)知的設(shè)備列表,返回哪種列表取決于傳遞的參數(shù),當(dāng)檢測到 一臺新的藍牙設(shè)備時,需要使用 DiscoveryListener 接口來通知. (3)服務(wù)發(fā)現(xiàn) 服務(wù)發(fā)現(xiàn)允許發(fā)現(xiàn)附近的服務(wù), 而不管哪一臺設(shè)備提供的該服務(wù). DiscoverAgent 提供的方法可以用來發(fā)現(xiàn)藍牙設(shè)備上的服務(wù), 被發(fā)現(xiàn)以前, 多任務(wù),包括創(chuàng)建描述所提供的服務(wù)記錄,接受來自客戶端的連接,向服務(wù)設(shè)備的 服務(wù)發(fā)現(xiàn)數(shù)據(jù)庫(SDDB)添加新的服務(wù)記錄.  本章將介紹象棋引擎算法的工作流程和引擎算法中用到的各個模塊,包括走法 產(chǎn)生器,AlphaBeta 搜索算法,評估算法等 引擎工作流程 首先使用一個數(shù)據(jù)結(jié)構(gòu)來描述棋局信息,對某一特定的棋局信息由走法生成器 取走法并調(diào)用局面評估函數(shù)對該走法所產(chǎn)生的后繼局面進行評估打分,從中選出一 31 所示: 圖 31 引擎工作流程 棋盤表示 通常, 一個 910 個字節(jié)的二維數(shù)組來表示,數(shù)組中每一個字節(jié)代表棋盤上的一個交點, 14 棋引擎部分的地基,之后所有的操作都將建立在其基礎(chǔ)上. 中國象棋初始棋盤如圖 32 所示: 圖 32 棋盤表示數(shù)組 棋子位置的結(jié)構(gòu): public class CHESSMANPOS { public int x = 0。 public int y = 0。 } 走法的結(jié)構(gòu): public class CHESSMOVE { public int ChessID = 0。//標明是什么棋子 public CHESSMANPOS From = new CHESSMANPOS()。//起始位置 public CHESSMANPOS To = new CHESSMANPOS()。//走到的位置 public int Score = 0。//值 } 有了對棋盤局面和走法的表示之后,程序才能夠完成以下操作: (1)生成所有合法走法。 (2)針對某一局面進行評估. 走法生成 在走法生成器中,基本思想就是:掃描整個棋盤,當(dāng)發(fā)現(xiàn)有當(dāng)前下棋方的棋子 時先判斷它是何種類型的棋子,然后根據(jù)其棋子類型而相應(yīng)地找出其所有合法走法 并存入走法隊列. 15 合法走法包括以下幾點: (1)各棋子按其行子規(guī)則走子. (2)走子不能越出棋盤的界限. (3)走子的半路上不能有子阻攔(炮吃子除外)以及走子的目的點不能有本方棋 子(不能自己吃自己) . (4)將帥不能碰面. 產(chǎn)生了走法后將其存入走法隊列以供搜索之用,由于會搜索多層(即考慮雙方 你來我往好幾步),所以在把走法存入走法隊列的時候還要同時存儲該走法所屬的搜 MoveList[8][80],其中第一個數(shù)組下 標為搜索層數(shù),第二個數(shù)組下標為每一層的全部走法數(shù). 關(guān)于搜索層數(shù),我將數(shù)組下標設(shè)定為 8,實際使用的是 2 到 會顯著提高引擎的下棋水平(當(dāng)然計引擎的棋力在很大程度上也依賴于局面評估) . 在手機模擬器上最多只能搜索 4 層,再多將導(dǎo)致搜索時間達到令人無法容忍的地步. 對于每一層的走法數(shù),也就是當(dāng)前下棋方針對當(dāng)前局面的所有可選的合法走法, 為 80,應(yīng)當(dāng)可以保證十分的安全. 走法生成為搜索部分提供了原料 ,接下來的任務(wù)就交給搜索和局面評估了. 搜索算法 ,驅(qū)動著 (從某種角度上,它影響著 ,引擎必須在有限的時間內(nèi)完成思考,搜索速度快意味著在 相同的時間內(nèi)程序可以看得更遠, 想的更多) .關(guān)于棋類對弈程序中的搜索 算法,經(jīng)前人的努力已形成了非常成熟的 AlphaBeta 搜索算法以及其它一些輔助增 強算法(還有眾多基于 AlphaBeta 算法的派生,變種算法) .鑒于目前知識儲備, 時間,精力等均達不到推陳出新,另開爐灶的要求,再加之前人的算法著實已相當(dāng) 完善,所以我在程序中直接借鑒了 AlphaBeta 搜索算法并輔以了歷史啟發(fā). 用一棵博弈樹 (一棵 n 叉樹)來表示下棋的過程——樹中每一個結(jié)點代表棋 盤上的一個局面,對每一個局面(結(jié)點)根據(jù)不同的走法又產(chǎn)生不同的局面(生出 新的結(jié)點) ,如此不斷直到再無可選擇的走法,即到達葉子結(jié)點(棋局結(jié)束) .中國 16 象棋的博弈樹的模型如圖 33 所示: 圖 33 象棋博弈樹 該樹包含三種類型的結(jié)點: (1)奇數(shù)層的中間結(jié)點(以及根結(jié)點) ,表示輪到紅方走棋。 (2)偶數(shù)層的中間結(jié)點,表示輪到黑方走棋。 (3)葉子結(jié)點,表示棋局結(jié)束. 現(xiàn)在讓引擎下棋, 它應(yīng)當(dāng)選擇一步對它最有利的走法 (最終導(dǎo)致它取勝的走法) . 獲得最佳走法的方法就是試走每一種可能的走法,比較它們所產(chǎn)生的不同后果, 然后從中選出能夠產(chǎn)生對自己最有利的局面的走法. 結(jié)合上面所講的博弈樹, 如果給每個結(jié)點都打一個分值來評價其對應(yīng)的局面 (這 一任務(wù)由后面所講的局面評估來完成) ,那么可以通過比較該分值的大小來判斷局面 ,甲勝的局面是一個極大值(一個很大的正數(shù)) ,那么乙 勝的局面就是一個極小值 (極大值的負值) 和棋的局面則是零值 , (或是接近零的值) . 如此,當(dāng)輪到甲走棋時他會盡可能地讓局面上的分值大,相反輪到乙走棋時他會選 ,即如果假設(shè)奇數(shù)層表示輪到甲方走 棋,則在偶 數(shù)層上挑選分值最大的結(jié)點——偶數(shù)層的結(jié)點是甲走完一步棋之后的棋盤局面,反 ,由于乙方希望棋盤上的分值盡可能小,那 么在奇數(shù)層上就選擇分值最小的結(jié)點. 這就是 最小最大 (Minimax)的基本思想. 這樣搜索函數(shù)在估值函數(shù)的協(xié)助下可以通過在奇數(shù)層選擇分值最大(最小)的結(jié)點, 在偶數(shù)層選擇分值最小(最大)的結(jié)點的方式來搜索以當(dāng)前局面為根結(jié)點,限定搜 索層數(shù)以內(nèi)的整棵樹來獲得一個最佳的走法. 17 然而不幸的是,博弈樹相當(dāng)龐大(它會成指數(shù)增長) ,因而搜索(限定層數(shù)以內(nèi) 的)整棵樹是一件相當(dāng)費時的工作——其時間復(fù)雜度為 O(bn).其中 b 是分枝因子, 即針對各種局面的合法走法的數(shù)目的平均值,n , 在中盤時平均走法數(shù)目大約是 40 種左右,那么搜索 4 層需要檢查 250 萬條路線,搜 索 5 層需要檢查 1 億條路線,搜索 6 層需要檢查 40 億條路線! 幸運的是,AlphaBeta 為,如果考慮到下棋是一個你來我往的交替進行并且相互較勁 一方都會盡可能將局面導(dǎo)向?qū)ψ约河欣鴮Ψ讲焕姆较?那么某些局面由于能 能產(chǎn)生很糟糕的局面時,應(yīng)當(dāng)立刻停止對其剩余子結(jié)點的分析——不要對它再抱任 何幻想了,如果選擇了它, 大程度上減少搜索的工作量,提高搜索效率,這稱為樹的裁剪 . 下面用圖 34 來進一步說明樹的裁剪 .為了簡便起見,假設(shè)博弈樹的每個結(jié) 點只有三個分支. 圖 34 簡化的博弈樹 現(xiàn)在假定棋盤上的局面發(fā)展到了結(jié)點 A,現(xiàn)在輪到最大者走棋了——即最 大者樹的裁剪對提 高搜索效率的幫助. 首先,考察結(jié)點 A 的子結(jié)點 B 所屬的這一層是輪到對方——最小者 18 走棋, 最小者 B 的各個子結(jié) 點,查看它們的分值(因為事先約定好了搜索兩層,現(xiàn)在已達到搜索深度的要求了, 所以就停下來調(diào)用局面評估函數(shù)來給它打分) .結(jié)點B的第一個子結(jié)點(從左到右算 起)返回 10,第二個子結(jié)點返回了5, 最小者來做選擇,假設(shè)最小者一定會做出明智的選擇,那么最小者會 選擇返回值為5 的那個結(jié)點. 我們再來分析結(jié)點 A 的第二個子結(jié)點 C,結(jié)點 C 與結(jié)點 B 同屬一層,它依然是輪 到最小者 C 的各個子結(jié)點的分值,其第一個子結(jié)點返回 ,該是裁剪 C 的剩余子結(jié)點了,因 為結(jié)點 C 很糟糕,不管結(jié)點 C 的剩余子結(jié)點有怎樣的分值, 與前面已經(jīng)分析過的結(jié)點 B 所傳回5 相比較,作為最大者顯然更不愿意看到8 , 最大者當(dāng)然不會選擇相應(yīng)的走法使得局面發(fā)展成為結(jié)點 如果那樣的話,下一步最小者就會帶給最大者一個分值不高于8 的局面. 由此,在不影響搜索質(zhì)量的前提下避免了搜索無價值的結(jié)點 C 的剩余子結(jié) 點,從而節(jié)省了寶貴時間,為在同樣機器配置下搜索更多的層數(shù)提供了可能. 最小最大的思想再加上對樹的裁剪 ,這就是 AlphaBeta 搜索算法的核 AlphaBeta 算法的代碼如下: int AlphaBeta(int depth, int alpha, int beta){ if (depth == 0) //如果是葉子節(jié)點(到達搜索深度要求) return Eveluate ()。 //則由局面評估函數(shù)返回估值 CreatePossibleMove ()。 //產(chǎn)生所有合法走法 while (MovesLeft()){ //遍歷所有走法 MakeMove ()。//執(zhí)行走法 int val = AlphaBeta(depth 1, beta, alpha)。 //遞歸調(diào)用 UnMakeMove ()。//撤銷走法 if (val = beta) //裁剪 return beta。 if (val alpha) //保留最大值 alpha = val。 } return alpha。 } 歷史啟發(fā)及走法排序(搜索輔助) AlphaBeta 搜索算法在最小最大的基礎(chǔ)上引入樹的裁剪的思想以期提 19 高效率,它的效率在很大程度上取決于樹的結(jié)構(gòu)——如果搜索了沒多久就發(fā)現(xiàn)可以 裁剪了,那么需要分析的工作量將大大減少,效率自然也就大大提高。而如果 直至分析了所有的可能性之后才能裁剪,那此時裁剪也已經(jīng)失去了它原有的 ,要想保證 AlphaBeta 搜索算法的效率就需要調(diào)整樹的結(jié)構(gòu),即調(diào)整待 搜索的結(jié)點的順序,使得裁剪可以盡可能早地發(fā)生. 根據(jù)部分已經(jīng)搜索的結(jié)果來調(diào)整將要進行搜索的節(jié)點順序是一個可行的方向. 通常當(dāng)一個局面經(jīng)過搜索被認為較好時,其子結(jié)點中往往有一些與它相似的局面也 所提出的歷史啟發(fā) (History Heuristic)就是建立 ,每當(dāng)發(fā)現(xiàn)一個好的走法,就給該走法累 加一個增量以記錄其 歷史得分 一個多次被搜索并認為是好的走法的 , 歷史得分 ,按照歷史得分的高低對它們進行排序,保證 較好的走法( 歷史得分高的走法)排在前面,這樣 AlphaBeta 搜索就可以盡可 能早地進行裁剪 ,從而保證了搜索的效率. 對于走法的排序可以使用各種排序算法, 的空間復(fù)雜度為 O(n),時間復(fù)雜度為 O(nlog2n),具有較高的效率. 局面評估 ,那么局面評估 ,而局面評估則負責(zé)對搜索的內(nèi)容進行判斷 和評價. 在中國象棋中所要考慮的最基本的幾個因素包括如下三點: (1)棋子的價值評估 棋子的價值評估,可以 讓一個車價值為 500,一個馬價值為 300,一個兵價值為 100, 將的價值為無限大 (通常用一個遠大于其他棋子的數(shù)) : SideValue=Sum(PieceNumber*PieceValue) 其中 PieceNumber 是某種棋子的數(shù)量,PieceValue 是該種棋子的價值,Sum 是對各 ,通常意 SideValue 之差越大,優(yōu)勢也就越大. 20 (2)棋子的靈活性與棋盤控制 棋子的靈活性是指棋子的活動范圍, 棋局中發(fā)揮重要作用。同樣, 活性較