【文章內(nèi)容簡介】 繼續(xù)搜索同一層的下一個節(jié)點時，必須要恢復(fù)棋盤為原來的棋局狀態(tài)。 著法生成模塊的設(shè)計 ? 著法生成是博弈樹展開的依據(jù)，它是根據(jù)當(dāng)前的棋局和走棋方信息，給出所有可能著法的那一部分程序，也就是用來告訴引擎的其他部分下一步可以怎么走的模塊，從而不斷擴展博弈樹。不同的棋類有不同的規(guī)則，不同的復(fù)雜程度，所以要有一個相應(yīng)的走法產(chǎn)生機制。 ? 在亞馬遜棋對弈中，著法生成是一個很關(guān)鍵的問題。掃描棋盤尋找所有的可行棋位，羅列出所有符合規(guī)則的下一步著法。 ? 亞馬遜棋著法生成步驟： ? (1) 確定走動的棋子的位置； ? (2) 根據(jù)規(guī)則，掃描棋盤，找到全部合理落子位置； ? (3) 根據(jù)落子位置，掃描棋盤，找到全部合理的設(shè)障礙的位置。 ? 定義著法函數(shù)： ? makemove(Ifrom, Ito, Iput, Lmyturn) ? 函數(shù)包括 4個參數(shù)： ? int Ifrom //提子位置 ? int Ito //落子位置 ? int Iput //放箭位置 ? bool Lmyturn //是黑方還是白方 搜索算法的研究 ? 選擇著法時要充分考慮到對手的存在，考慮己方和對方以后幾步棋的可能下法，需要展開博弈樹，搜索最佳著法。 ? 在博弈過程中，按照博弈規(guī)則和著法狀態(tài)過程分析，客觀評判博弈雙方在各自分枝節(jié)點上所獲得的分?jǐn)?shù)估計值，并以其中任何一方的角度而依次生成具有得分值表示的與或搜索樹，稱為博弈樹。博弈樹是根在上部，然后向下遞歸產(chǎn)生的一棵包含著所有可能的對弈過程的搜索樹，是完全搜索樹，包含了下棋者和計算機所有可能的著法和局面。搜索算法是計算機“思維”的核心。 ? 一般，計算機直接通過棋盤信息判斷某個著法的好壞并不精確。棋類程序中，通常通過使用“搜索”函數(shù)來尋找可能著法。搜索函數(shù)獲得棋局信息，然后尋找對于計算機來說最好的著法。判斷著法好壞的一個辦法就是考察棋局走下去的結(jié)果，可以由博弈樹向下搜索幾步，然后比較發(fā)展下去的結(jié)果。 ? 雙方進(jìn)行對弈，假設(shè)輪到白方走棋，對其任何一種走法，黑方也有若干種與之相對應(yīng)的走法，對黑方的任何一種走法白方又有若干種與之相對應(yīng)的走法，如此往復(fù)，構(gòu)造出一棵博弈樹，將所有的走法羅列出來。在博弈樹中，節(jié)點為局面，樹枝為著法，其中根結(jié)點為當(dāng)前時刻的棋局，它的兒子節(jié)點是假設(shè)再行棋一步之后的各種棋局，孫子節(jié)點是從兒子節(jié)點的棋局再行棋一步的各種棋局，以此類推。雙方輪流出手，偶數(shù)層節(jié)點屬于白方，奇數(shù)層節(jié)點屬于黑方。如果葉節(jié)點還不能給出勝負(fù)的最終局面，則要對葉節(jié)點進(jìn)行評估，以便從有利局面選擇當(dāng)前著法，這便是博弈搜索的職能。 極小值搜索 ? 極大極小值算法是香儂教授在 1950年首先提出來的，極大極小值算法也是當(dāng)代計算機博弈各種搜索算法的基礎(chǔ)。由于對弈雙方都是理智的，都想贏棋，在選擇著法的時候都盡量讓棋局朝著有利于自己的方面轉(zhuǎn)化，所以在博弈樹上，在不同層上就要有不同的選擇標(biāo)準(zhǔn)。 ? 極大極小搜索算法的基本思想： ? (1) 在偶數(shù)層節(jié)點的著法即輪到 Max走棋的節(jié)點時， Max應(yīng)考慮最好的情況，選擇其全部子節(jié)點中評估值最大的一個，即 ? F(v) = max{F(v1), F(v2), ……, F(v n)} ? 其中， F ( ) 為節(jié)點估值， v1， v2， …… … vn為節(jié)點 v的子節(jié)點。 ? (2) 在奇數(shù)層節(jié)點的著法即輪到 Min走棋的節(jié)點時， Max應(yīng)考慮最壞的情況，選擇其全部子節(jié)點中評估值最小的一個，即 ? F(v) = min{F(v1), F(v2), ……, F(v n)} ? 其中， F ( ) 為節(jié)點估值， v1， v2， …… … vn為節(jié)點 v的子節(jié)點。 ? (3) 評價往回倒推時，相當(dāng)于兩個局中人的對抗策略，交替使用 (1)、 (2)兩種方法傳遞倒推值。 ? 在進(jìn)行極大 極小搜索的時候，首先要在有限深度內(nèi)展開全部葉子節(jié)點，并進(jìn)行評估，然后自下而上地進(jìn)行搜索計算，一直反推到根結(jié)點。在反推的過程中始終要記住算出該值的子節(jié)點是誰，這樣就可以得到一個從根結(jié)點到葉子節(jié)點的一條路徑，這就是最佳路徑，它是雙方表現(xiàn)最佳的對弈著法序列。如圖所示的博弈樹， MAX層取下一層的極大值， MIN層取下一層的極小值。 極大極小算法偽代碼 ? int minimax(position p,int depth) { ? int bestvalue,value。 ? if(gameover) // 檢查棋局是否結(jié)束 ? return evaluation(p)。 // 棋局結(jié)束，返回估值 ? if depth=0) // 是否是葉子節(jié)點 ? return evaluation(p)。 // 葉子節(jié)點，返回估值 ? if(==RED) // 是否輪到紅方走棋 ? bestvalue=INFINITY。 // 是，令初值最大值為極小 ? else ? bestvalue=INFINITY。 // 否，令初值最小值為極大 ? for(each possibly move m) { // 對每一可能的走法 m ? makemove(m)。 // 產(chǎn)生第 i 個棋面（子節(jié)點） ? value=minimax(p, depth 1)。 // 遞歸調(diào)用向下搜索子節(jié)點 ? unmakemove(m)。 // 恢復(fù)當(dāng)前棋面 ? if(==RED) ? bestval ue=max(value,bestvalue)。 // 取最大值 ? else ? bestval ue=min(value,bestvalue)。 // 取最小值 ? } ? return bestvalue。 // 返回最大值或最小值 ? } ? 極大極小搜索是一種“變性”搜索，在偶數(shù)層進(jìn)行 Max搜索，而在奇數(shù)層進(jìn)行 Min搜索。如果把極大極小值算法稍做變形，就是負(fù)極大值算法。負(fù)極大值算法是 Knuth和Moore在 1975年提出的，是對極大極小算法的優(yōu)化。 ? 負(fù)極大值算法的思想在于：父節(jié)點的值是各子節(jié)點的值的負(fù)數(shù)的極大值，如圖所示。在負(fù)極大值算法下，無論輪到人或者電腦走棋，選取的都是子節(jié)點負(fù)數(shù)最大的分枝，即 ? F(v) = max{F(v1), F(v2), ……, F(vn)} ? 其中， F ( ) 為節(jié)點估值， v1， v2， …… … vn為節(jié)點 v的子節(jié)點。 負(fù)極大值搜索算法偽代碼 ? int negamax(position p,int depth) { ? int n, value, bestvalue=INFINITY。 ? if(gameover) // 檢查棋局是否結(jié)束 ? return evaluation(p)。 // 棋局結(jié)束，返回估值 ? if depth=0) // 是否葉子節(jié)點 ? return evaluation(p)。 // 葉子節(jié)點，返回估值 ? for(each possibly move m) { // 對每一可能的走法 m ? makemove(m)。 // 產(chǎn)生第 i 個局面（子節(jié)點） ? value=negamax(p, depth 1)。 // 遞歸調(diào)用 minimax 向下搜索子節(jié)點 ? unmakemove(m)。 // 恢復(fù)當(dāng)前局面 ? if(value = bestvalue) ? bestvalue= value。 // 取最小值 ? } ? return bestvalue。 // 返回最大值或最小值 ? } ? 寬度優(yōu)先搜索的基本思想是從初始節(jié)點開始，逐層地對節(jié)點進(jìn)行擴展并考查它是否為目標(biāo)節(jié)點。在第 n層的節(jié)點沒有全部擴展并考查之前，不對第 1 + n 層的節(jié)點進(jìn)行擴展。寬度優(yōu)先搜索是一種盲目搜索，時間和空間復(fù)雜度都比較高。 ? 深度優(yōu)先搜索的基本思想是從初始節(jié)點開始擴展，沿著樹的最大深度方向進(jìn)行的。只有當(dāng)上次訪問的節(jié)點不是目標(biāo)節(jié)點且沒有其它節(jié)點生成的時候才轉(zhuǎn)到上次訪問節(jié)點的父節(jié)點。深度優(yōu)先搜索的優(yōu)點是比寬度優(yōu)先搜索算法需要較少的空間，該算法只需保存搜索樹的一部分，它由當(dāng)前正在搜索的路徑和該路徑上還沒有完全展開的節(jié)點標(biāo)志所組成。 ? 在復(fù)雜度很高的機器博弈搜索中，比較適合選擇深度優(yōu)先搜索方法，可以在搜索過程中的任何時候僅僅生成整棵樹的一小部分，搜索過的部分被立即刪去。 αβ剪枝算法 ? 在極大極小搜索過程中，遍歷了整棵博弈樹，每個節(jié)點都訪問了一次，這樣做的缺點是效率低下。在極大 極小搜索的基礎(chǔ)上，以窗口的形式引進(jìn)αβ 剪枝技術(shù)，使得搜索的效率顯著提高。 ? αβ 剪枝把生成的搜索樹和估值格局這兩個過程結(jié)合起來，再根據(jù)一定的條件判定，有可能盡早剪掉一些無