《對弈程序基本技術》專題
 
最小-最大和負值最大搜索
 
David Eppstein */
* 加州愛爾文大學(UC Irvine)信息與計算機科學系
 
搜索樹
 
  任何棋類游戲都要定義一棵有根的樹(即“博弈樹”),一個結點就代表棋類的一個局面,子結點就是這個局面走一步可以到達的一個局面。例如下圖是井子棋(Tic-tac-toe)的搜索樹:
 
 
 
  (實際上,這個搜索樹的根結點應該有9個子結點,但是我去掉了一些對稱的情況。如果同樣的棋盤是由兩個不同的著法順序形成的,那么我們就建立兩個結點,所以這的確是樹的結構。稍后我們會在討論散列技術的時候談到如何利用重復的結點來提高搜索速度——我們只要搜索第一個,另一個就用第一個搜索結果來代替。另外我們假設棋手是輪流下棋的,沒有人一次走多步或跳過不走的,那些復雜的情況可以把它走的一系列著法看作一個著法來處理。【譯注:復雜的情況是指一些一次能走很多步的棋類游戲,例如跳棋、西洋跳棋、黑白棋等,按照原作者的方案,可以把一方連續走的幾步棋看成一步棋。而譯者更愿意把一方連續的幾步棋拆成幾個回合,只是另一方都別無選擇地走了空著。】最后,我們假設搜索樹是有限的,這樣我們就不會遇到永無止境的棋局或者一步有無限多種著法的棋局。)
  搜索樹中有三種類型的結點:
  (1) 偶數層的中間結點,代表棋手甲要走的局面;
  (2) 奇數層的中間結點,代表棋手乙要走的局面;
  (3) 葉子結點,代表棋局結束的局面,即棋手甲或棋手乙獲勝,或者是和局。
 
博弈樹的評價
 
  假設某個中間結點的所有子結點都是葉子結點,那么棋局會在一回合內結束。現在我們假設棋手會挑選最好的著法,如果有一個著法能使他贏下棋局,那么他一定會走這步。如果沒有可以贏的著法,但是有取得和局的著法,那么他會走這步取得和局的著法。但是,如果所有的著法都使得對手獲勝,那么無論如何他都會輸。
  因此在葉子結點的上一層結點,我們就能知道棋局的結果。現在我們知道了這個結點的結果,那么我們可以用同樣的方法作推演,知道葉子結點的上兩層結點的結果,然后是上三層結點,等等,直到我們達到搜索樹的根結點。在每個結點上,棋手只要找到一個子結點能讓他獲勝,那么他就可以贏下棋局;他只要找到一個形成和局的子結點,棋局就和了;如果獲勝與和局的子結點都沒有,那么肯定是輸的。如果我們有足夠多的時間來計算,那么這就給了我們一個可以下棋的完美算法。但是對于任何常規的棋類游戲,我們都不可能有足夠的計算時間,因為搜索樹實在太大了。
  另外,“正確”的評價函數只有三個值,贏、輸或者和局。在實際的棋類程序中,我們通常使用一個更寬泛的實數來作評價值,就是因為贏、輸或者和局是不確定的。如果棋手甲獲勝的值用+1表示,和局的值用0表示,棋手乙獲勝的值用-1表示,那么博弈樹的每個中間結點的值就是子結點的最大值或最小值,這取決于棋手甲還是棋手乙著棋。
 
部分的博弈樹
 
  在實戰中,我們的搜索算法只能對博弈樹展開一部分。我們用一些“中止規則”來決定搜索樹展開到哪個結點就停下來,例如我們在8步變化以后聽下來。由于棋局沒有在葉子結點結束,我們只能用評價函數來猜哪一方獲勝。現在我們來假設在我們展開的結點中,棋手甲總是希望棋局到達評價函數大的局面,而棋手乙總是希望棋局到達評價函數小的局面。
  如果雙方都用這種方法來下棋,那么我們可以使用同樣的最小-最大過程,來確定到達的葉子結點的評價值,這個過程如下:對每個中間結點,計算子結點的最大值或最小值,這取決于是棋手甲還是棋手乙走棋。到達葉子結點的線路稱為“主要變例”(Principal Variation)。最小-最大博弈樹的基本原理,就是對博弈樹作部分展開,去找主要變例,并走出變例中的第一步。
 
廣度優先和深度優先搜索,負值最大代碼
 
  正如上面所講的,計算博弈樹的值是一個廣度優先的過程(我們要自下而上地,一次一層地計算)。然而實戰中,我們使用深度優先(即后序遍歷)的遞歸過程來遍歷搜索樹,即要得到一個結點的值,就對子結點做遞歸,然后根據它們的返回值來決定自身的返回值。這樣要節省很多空間,因為不需要來存儲整個博弈樹,而只是存儲一條線路(相對來說非常短,例如上面提到的8步中止的規則)。下次我們討論Alpha-Beta搜索時,會發現深度優先的遍歷會有很大的優勢,你可以用目前得到的信息來決定某些結點是不需要訪問的,這樣就節省下很多的時間。
  只要對搜索樹的值作一個很小的改動,就可以用一個求最大值的操作來代替最小值和最大值交替的過程。在搜索樹的奇數層(即輪到棋手乙下棋的結點),就對上面提到的評價值取負數。因此在每個結點上,這些值都可以由子結點的負值求得。我把博弈樹搜索的源代碼寫出來,恐怕就會清楚很多了。
 
// 將博弈樹搜索到一定的深度,返回根結點的評價值
double negamax(int depth) {
 if (depth <= 0 || 棋局結束)
  return eval(pos);
 else {
  double e = -infty;
  for (當前局面所有可能的著法 m) {
   執行著法 m;
   e = max(e, -negamax(depth - 1));
   撤消著法 m;
  }
  return e;
 }
}
 
  注意,這個過程只能找到評價值,但是無法得知著法。我們只要在搜索樹的根結點找到著法(盡管很多程序都返回整個主要變例)就可以了,要做到這一點,可以對根結點的搜索稍作改動:
 
// 將博弈樹搜索到一定的深度,返回根結點的著法
move rootsearch(int depth) {
 double e = -infty;
 move mm;
 for (當前局面所有可能的著法 m) {
  執行著法 m;
  double em = -negamax(depth - 1);
  if (e < em) {
   e = em;
   mm = m;
  }
  撤消著法 m;
 }
 return mm;
}
 
負值最大的分析:分枝因子和深度
 
  人們通常簡單地根據博弈樹的形狀來對博弈樹算法進行分析。我們假設每個中間結點有同樣多的子結點,其數量稱為分枝因子(Branching Factor)。我們還假設搜索到固定的深度(就如前面所提到的算法一樣),并且棋局不會很早地結束(在達到搜索深度以前結束)
  在這些假設下,很容易寫下負值最大程序所花的時間,即正比于展開結點的數量。(看上去需要乘上一個系數,以反映調用負值最大時的那個循環,但是這個循環所花的時間已經被包括在遞歸函數里了。)【譯者也不理解這句話的意思,但譯者認為程序中eval()函數所花費的時間最多,而它只是在搜索到葉子結點時才被調用,因此只計算葉子結點的數量就可以了,即bd。】如果分枝因子是b,深度是d,那么這個數就是:
1 + b + b2 + b3 + ... + bd = bd (1 - 1 / bd) / (1 - 1 / b).
  公式右端括號里的數值接近于1,所以整個運算所花費的時間接近于bd
  如果棋類游戲不符合以上假定,我們可以反過來定義一個“有效分枝因子”(Effective Branching Factor),使得這個b能夠符合程序運行所花費的時間。更簡單些,可以把“分枝因子”描述為某個棋類游戲中“典型”局面的可能著法數的平均值。
  這個公式可以告訴我們什么呢?首先它是指數形式的,這就意味著我們不可能搜索太多層,如果電腦的速度翻了番,那么我們只能把d增加很小一點。其次搜索取決于分枝因子b,在分枝因子很小的棋類中(像西洋跳棋,通常每個局面只有3個著法),我們就可以搜索的比國際象棋(一個局面有30種左右的著法)或圍棋(一個局面有幾百種著法)深得多,因此我們喜歡讓b越小越好。很不幸的是搜索函數更多地決于棋類游戲本身,而不是我們寫程序的水平。但是下一次我們要討論一個算法,稱為Alpha-Beta裁剪,它可以很大程度地減少分枝因子,如果運氣好的話,它可以減少到沒有裁剪的博弈樹的平方根那么多,這就意味著我們可以搜索原來深度(即不用Alpha-Beta搜索的深度)的兩倍那么深。b的平方根即b1/2,用一下中學數學學過的公式,(b1/2)d = bd/2,還記得嗎?】
 
迭代加深
 
  負值極大的代碼還留給我們一個問題:我們如何來給定搜索深度?簡單的棋類程序只把它設成一個固定值,這就可能使得程序走的每步棋時花的時間長短變化非常大。因此你最好根據搜索所需的時間,來決定搜索的深度。幸運的是指數特征的搜索有這樣一個好處:通過“迭代加深”(Iterated Deepening)這個手段,可以很容易地對搜索進行控制,剛開始搜索時淺一些,然后增加深度重復搜索直到時間用完為止:
 
depth = 0
while (有足夠的時間來進行下一層的搜索) {
 depth ++;
 m = rootsearch(depth);
}
執行著法 m;
 
  這看上去似乎在浪費時間,因為除了最后一次搜索外,前面的搜索都白費了。但是根據前面分析過的結果,白費的時間是很少的:不同層數所花的時間加起來是 1 + b + b2 + ...,我們已經知道它接近于最后一項bd了。所以,迭代加深所花的代價并不多,而它給我們提供了很好的時間控制的手段。它還有一個很大的作用:在做較深的搜索時,可以用淺一層搜索得到的著法順序,在Alpha-Beta搜索中,著法順序是影響搜索的速度的決定性因素。
  Iterative Deepening,字面意思是“重復加深”,就如上文所講的。但它最主要的作用是改善著法的順序,它是Alpha-Beta搜索的一種主要的啟發方式,淺一層最好的著法在深一層的搜索中首先被嘗試,本質上是一種迭代的過程,所以譯為“迭代加深”。】
 
  原文:http://www.ics.uci.edu/~eppstein/180a/970417.html
  譯者:象棋百科全書網 ([email protected])
  類型:全譯加譯注
  • 上一篇 數據結構——Zobrist鍵值
  • 下一篇 基本搜索方法——簡介()
  • 返 回 象棋百科全書——電腦象棋
  • www.ejnwjd.tw
    快乐双彩今晚开奖结果