005章 對抗搜尋

Post date: 2012/8/25 上午 05:57:02

對抗搜尋

考察有其他代理人計畫與我們對抗的世界中,我們試圖預先計畫時產生的問題

賽局

透過讓代理人對戰來獲得更多的資訊

賽局最佳化決策

在一班的搜尋問題中,最佳解為一系列棋步並導致一目標狀態取勝的中止狀態。

極小極大值演算法

從當前狀態計算極小極大決策。

他使用了簡單的遞迴演算法,計算每個後繼者的極小極大值,直接實作定義方程式。

騎回傳最佳可能棋步對應的行動,亦即在對手的棋步是為了使效用最小的假設下,能夠導致最佳效用值結果的棋步。

多人遊戲中的最佳決策

許多流行的遊戲允許多於兩個的參加者。

多人遊戲通常會涉及在遊戲者之間,出現正式或者非正式的聯盟(alliances)的情況。

隨著遊戲的進行,聯盟也建立或者解散。我們如何去理解這種行為呢?是否在多人遊戲中對每個遊戲者來說,

聯盟是最佳策略的一個自然結果?看起來可能是這樣的。

例如A和B相對比較弱,而C很強。那麼對於A和B而言,他們一起進攻C比等C逐個消滅他們要好,這樣通常是最佳的。

如此,合作從純自私的行為中湧現出來。

當然,一旦C在聯合攻擊下被削弱,聯盟就失去了價值,於是A或者B就會破壞協定。

某些情況下,外在的聯盟僅僅是把將要發生的具體化。

在另一些情況下,違反盟約會損害社會聲譽,所以遊戲者要在毀約得到的直接利益,和被認為不可信任而帶來的長期弊端之間,尋求平衡

A-B 剪枝

棋步排序

A-B剪枝的效率很大程度上取決於檢查後繼者的順序。

對於西洋棋,一種相當簡單的排序函數(如:吃子優先,然後是威脅、向前走子、向後走子)可以提供你最佳情況O(b^m/2)的2倍以內的結果。

不完整的即時決策

極小極大值演算法產生了整個賽局搜尋空間,而A-B演算法允許我們剪裁其中的一大部分。

然而A-B演算法仍然要搜尋至少一部份搜尋空間直到中止狀態。

這樣的搜尋深度也是不切實際的,因為棋步要在合理的時間內確定─典型情況下最多有幾分鐘。

向農的論文《電腦西洋棋程式設計》中提出應該盡早攔截搜尋,把啟發式評價函數用於搜尋中的狀態,有效地把非終止節點轉變為葉子終止節點。

評價函數

大多數的評價函數藉由計算各式的狀態特徵來發揮作用──舉例來說,於西洋棋,我們有些特徵是白棋的兵,黑棋的兵,白棋的皇后,黑棋的皇后等等。

這些特徵定義了狀態的各種類別或者等價類:

每類中的狀態對所有特徵都有相同的值。

舉例來說,所有兩個兵對抗一個兵的殘局類。一般來說,任何給定的類都會包含某些致勝的狀態、某些會導致和局狀態以及會導致失敗的狀態。

評價函數無法知道哪個狀態是哪種,不過可以返回一個反映每個結果中狀態所佔比例的單一值。

例如,假設經驗告訴我們,雙兵對一兵的類別中有 72% 的狀態是致勝的(效用值+1),20%是會輸的(0),而 8% 是和局(1/2)。

那麼對該類中狀態的一個合理評價是期望值:(0.72 * +1) + (0.20 * 0) + (0.08 * 1/2) = 0.76。大體上每個類可以確定一個期望值,產生一個對任何狀態都可行的評價函數。

對於終止狀態,評價函數不需要返回準確的期望值,只要保持狀態的排序保持不變。

截斷搜尋

修改ALPHA-BETA-SEARCH,當適合截斷搜尋時呼叫啟發式函數 EVAL。

評價函數應該只用於那些靜止的棋局───亦即,評價值在很近的未來不會出現大的搖擺變化的棋局。

水平線效應

黑棋要移動,黑棋主教注定了在劫難逃。但是黑棋能搶先於這件事之前以他的兵將白棋一軍,強迫該國王吃掉該兵。

這促使主教會不可避免失掉的情況出現在水平線之外,因此該兵的犧牲會被搜尋演算法視為一個好的棋步而非壞的棋步

前向剪枝

在某個節點上不需要進一步考慮而直接剪裁一些棋步

搜尋與查表

電腦能從一個以前下過的賽局的資料庫來蒐集統計資料來看看哪一個開局的順序在大多數的時候會贏棋。

起步的選擇並不多,因此仰賴許多專家的評論與過去下過隻賽局。通常十個棋步之後,我們面臨到很少見的位置,而程式必須從查表切換到搜尋。

隨機賽局

在現實生活中,很多不可預知的外部事件會把我們推到沒有預測到的情景中。

許多遊戲引入了隨機因素(如擲骰子)來反映這種不可預測性。

機率遊戲的評價函數

用蒙地卡羅模擬分析來評價一個位置。以A-B(或其他的)搜尋演算法開始。

從一個開始位置,讓該演算法與他自己玩上千盤賽局,使用隨機的擲骰子結果。

部分可觀察賽局

西洋棋常常被描述如迷你戰爭,但是至少他缺乏一種真實戰爭主要的特徵,及部分可觀察姓。

於戰爭的迷霧中,敵人單位的存在與否以及性格常常是未知的,直到直接接觸後才顯露出來。

Kriegspiel :部分可觀察的西洋棋

Kriegspiel 的規則如下:白棋與黑棋個各自看到看到一個僅有他們自己棋子的棋盤。

一名裁判,能看見全部的棋子,判決遊戲並且定期性的通知,且兩名遊戲者都聽得到。

輪到白棋時,白棋得向裁判提出任何沒有被黑期占用的合法棋步。如果棋步事實上是不合法的(因為黑棋),裁判宣布「不合法」這樣的話,

白旗可以一值提出棋步直到找到一個合法的棋步───於這個過程中知道更多關於黑棋的位置。一旦一個合法的棋步被提出,

裁判宣布如下:「吃掉在方格X者」如果有吃子,與「D將軍」如果黑棋國王被將,其中D是將的方向,可以是「L向(Knight)」「橫行(rank)」「縱列(file)」

「常對角向(long diagonal)」或者「短對角向(short diagonal)」其中的一種。(如果發現可以將軍,裁判可做出兩個「將軍」宣告)。

如果黑棋被將軍或者僵局,裁判會明說;否則,輪到黑棋移動。

紙牌遊戲

最先進的賽局程式

西洋棋

西洋跳棋

奧賽羅

西洋雙陸棋

圍棋

橋牌

拼字遊戲

其他方法

總結

  • 賽局遊戲透過下列元素定義:初始狀態(棋盤的設置)、每個狀態的合法行動、每個行動的結果、一個終止測試(說明什麼時候遊戲結束)和可用在終止狀態上的效用函數。
  • 再有完整資訊的兩人零和遊戲中,極小極大值演算法可以透過賽局樹的深度優先列舉,選出最佳棋步。
  • A-B搜尋演算法可以計算出和極小極大值演算法一樣的最佳棋步,不過由於蕭除了可證明無關的子樹,它的效率得以大大提高。
  • 通常,考慮整顆賽局樹是不可行的(即使是用A-B演算法),所以我們在某個點截斷搜尋,並應用可以對某個狀態的效用值進行估計的評價函數。
  • 許多賽局程式預先計算於開局及殘局時最佳棋步的資料表,使得他們能查找棋步而非搜尋。
  • 有機率因素的遊戲可以透過擴展極小極大值演算法來處理,擴展後的演算法計算其全部子節點的平均效用值來評價一個機率節點,平均效用值是用每個子節點的概率,加權平均計算得到的。
  • 對於像橋牌這樣的不完整資訊的遊戲,最佳玩法對每個遊戲者當前或者未來的信念狀態進行推理。簡單的近似可以透過對行動值在缺失資訊的每種可能配置上,進行平均而得到。
  • 最優的程式甚至勝過人類遊戲者遊戲如西洋棋,跳棋,與翻轉其。人類保有數個不完美資訊的遊戲的優勢,如撲克牌,橋牌,與Kriegspiel,以及具有非常大的分支因數且好啟發式知識幾乎闕如的遊戲,如圍棋。