博弈搜索樹(shù)算法的實(shí)現(xiàn)及其優(yōu)化

周子龍

（同濟(jì)大學(xué) 軟件學(xué)院，上海201804）

1 概述

在一般的搜索過(guò)程中，總是會(huì)有一個(gè)限定的、有限的搜索內(nèi)容集。一般的搜索算法也僅僅限于在該固定集中進(jìn)行查找操作，返回是否查找成功，即待查找的元素是否屬于該集合。而在許多情境中，該類(lèi)搜索并不能滿(mǎn)足用戶(hù)的全部需要，有時(shí)候，我們并不是搜索某一特定的元素，而是給出集合中最符合用戶(hù)需求的元素。這些元素并不是絕對(duì)確定的，當(dāng)一定是在某一些特定要求下，根據(jù)某種評(píng)估，所能在有限的搜索集合中給出最有元素；同時(shí)，搜索的集合可能在需要執(zhí)行搜索的時(shí)候還未產(chǎn)生，需要一邊搜索一邊動(dòng)態(tài)的產(chǎn)生新的元素。一般地，我們把符合上述描述的搜索稱(chēng)為動(dòng)態(tài)博弈搜索。相較于普通搜索，博弈搜索的搜索集合并不是可以立即確定的，它可能需要根據(jù)不同局中人的不同行為生成不同元素進(jìn)行不斷補(bǔ)充；以及，該過(guò)程也涉及到多個(gè)參與者，即上文提到的多個(gè)局中人，每一局中人均假設(shè)為理性博弈者，即其所作出的任何行為均是符合一定標(biāo)準(zhǔn)下利益最大化原則。綜上，動(dòng)態(tài)博弈搜索樹(shù)是一種對(duì)動(dòng)態(tài)決策的過(guò)程模擬，它在搜索的過(guò)程中同時(shí)產(chǎn)生許多新的可能的結(jié)果，依據(jù)利益最大化原則，為每一為局中人進(jìn)行操作，搜索出來(lái)的最優(yōu)行為即應(yīng)當(dāng)滿(mǎn)足如下要求：通過(guò)該最優(yōu)行為，當(dāng)所有局中人按照自己利益最大化原則進(jìn)行后續(xù)行為后，該行為為己方帶來(lái)最大收益。

在理想情況下，總是認(rèn)為考慮到的情況越多越好，但計(jì)算機(jī)的算力總是有限的，在現(xiàn)實(shí)生活中，局中人的思考能力以及思考時(shí)間也是有限的，故搜索不能無(wú)限制的進(jìn)行下去，只可能在有限的搜索深度下，得到當(dāng)前局面的最優(yōu)行為。此外，不可否認(rèn)的是，以往的經(jīng)驗(yàn)也會(huì)影響到局中人的決策。局中人總是會(huì)依據(jù)一定的經(jīng)驗(yàn)進(jìn)行判斷，而不是每遇到一個(gè)局面就從新開(kāi)始進(jìn)行判斷。據(jù)此，在算法中，我們可以考慮加入歷史數(shù)據(jù)庫(kù)，在每一次搜索做出判斷時(shí)，先行搜索歷史數(shù)據(jù)，一起到一定的啟發(fā)作用。至此，我們的目標(biāo)便已經(jīng)明確：在一定的規(guī)則下，為一個(gè)指定的局中人產(chǎn)生根據(jù)特定判斷下，特定行為局?jǐn)?shù)后，能夠?qū)υ摼种腥俗顑?yōu)利的行為。后文中，主要分析了如下的幾種搜索算法：極大極小值搜索算法、負(fù)極大值搜索算法、Alpha-Beta 剪枝算法、結(jié)合Hash 表的Alpha-Beta 剪枝算法等。

2 算法及其優(yōu)化

2.1 極大極小搜索算法

2.1.1 基本思想

根據(jù)理性博弈人的基本假設(shè)，為了簡(jiǎn)化搜索邏輯，我們可以做出這樣的簡(jiǎn)化：己方局中人在進(jìn)行判斷時(shí)，總是為自己選擇利益最大的行為，在模擬其它局中人判斷時(shí)，總是選擇使得己方局中人利益最小的行為。此時(shí)，整個(gè)的博弈過(guò)程為：輪到己方局中人行為時(shí)，進(jìn)行搜索，在當(dāng)前局面下所有可能的行為中選擇對(duì)己方局中人利益最大的一種行為。但在實(shí)際情況中，一次考慮總是遠(yuǎn)遠(yuǎn)不夠，在前文也提到了搜索深度的概念，故我們應(yīng)當(dāng)認(rèn)為，也應(yīng)該為其它局中人進(jìn)行模擬行為，并以此為己方局中人優(yōu)化決策。按照如上假設(shè)及搜索的基本思想，便是極大極小搜索，其基本思想如下：在每一次迭代中，為每一個(gè)局面生產(chǎn)所有可能的子局面，通過(guò)極大極小的原則，為不同的局中人選擇行為，在向上回溯的過(guò)程中，通過(guò)子局面的評(píng)估，給出父局面的評(píng)價(jià)。繼續(xù)向上回溯, 依次類(lèi)推, 一直到當(dāng)前局面, 最終相對(duì)的最優(yōu)行為也就搜索出來(lái)了。如圖1 中：第一階段輪到藍(lán)方行為，藍(lán)方將選擇所有局面評(píng)估中對(duì)藍(lán)方最有利的一種(57)，之后藍(lán)方將模擬紅方行為，并選擇對(duì)藍(lán)方評(píng)估最小的行為(19)。

圖1

對(duì)這種極大極小過(guò)程的模擬，即是極大極小搜索算法。根據(jù)這種思想，Shannon 最先于1950 年提出該算法，從而奠定了整個(gè)博弈搜索的理論基礎(chǔ)。但在整個(gè)極大極小的過(guò)程，我們需要為不同的局中人執(zhí)行不同的操作，為己方取極大值，為另一方取極小值，為了消除這兩方面的差別，Kunth(1975)提出的負(fù)極大值算法通過(guò)將父節(jié)點(diǎn)的評(píng)估值設(shè)定為所有子節(jié)點(diǎn)的負(fù)數(shù)的極大值，從而達(dá)到為雙方取相同的操作，使得算法更加簡(jiǎn)潔，但由于其原理于極大極小搜索算法完全等效，故本文不再給出其具體實(shí)現(xiàn)。

2.1.2 性能分析

在某一深度D 下，所有可能的行為數(shù)N 對(duì)于任何局中人來(lái)說(shuō)應(yīng)當(dāng)認(rèn)為是相近的。每一次生成所有走法涉及到N 次操作，對(duì)于每一次評(píng)估操作，不妨設(shè)其時(shí)間復(fù)雜度為o(E)，執(zhí)行和撤銷(xiāo)所有行為可以認(rèn)為其時(shí)間復(fù)雜度為o(ND)，則該算法具體的時(shí)間復(fù)雜度為o(END)。

在每一局面中，均為所有可能的行為生成了相應(yīng)行為棧進(jìn)行存貯，棧的大小大致于所有可能的行為數(shù)相當(dāng)，則空間復(fù)雜度應(yīng)為o(ND)。不難看出，該算法的執(zhí)行時(shí)間復(fù)雜度以及空間復(fù)雜度均隨著搜索深度指數(shù)增長(zhǎng)，在具體的博弈過(guò)程中是亟待優(yōu)化的。

2.2 Alpha-Beta 搜索算法

2.2.1 基本思想

針對(duì)極大極小搜索算法巨大的時(shí)間空間消耗，進(jìn)一步分析其搜索過(guò)程，不難發(fā)現(xiàn)有許多搜索是無(wú)用的。其中存在著兩種明顯的冗余計(jì)算。第一種是極大值冗余現(xiàn)象?？紤]這樣一種情況：假定在某一次搜索中父節(jié)點(diǎn)A 的評(píng)估值為子節(jié)點(diǎn)B、C 中的較大者?，F(xiàn)子節(jié)點(diǎn)B 已經(jīng)全部搜索完畢，程序開(kāi)始搜索子節(jié)點(diǎn)C。根據(jù)極大極小原理，子節(jié)點(diǎn)C 的評(píng)估值應(yīng)為其全部子節(jié)點(diǎn)中的最小值，在搜索C 的子節(jié)點(diǎn)C1 時(shí)，已經(jīng)得到C1 的評(píng)估值小于B 節(jié)點(diǎn)的評(píng)估值，那么，對(duì)于C 節(jié)點(diǎn)余下的子節(jié)點(diǎn)便失去了搜索的必要。這是因?yàn)镃 節(jié)點(diǎn)是選擇其子節(jié)點(diǎn)最小值，并最小值不會(huì)大于C1 的值，故C 節(jié)點(diǎn)的值不會(huì)大于C1，又因C1 小于B，因而得出B 必定大于C，所以C 節(jié)點(diǎn)的估值在此時(shí)便可以判定不會(huì)影響父節(jié)點(diǎn)A 的評(píng)估。故而C 節(jié)點(diǎn)接下來(lái)的搜索便是多余的。

圖2

類(lèi)似的，第二種情況便是極小值冗余現(xiàn)象。現(xiàn)在考慮相反的情況：當(dāng)父節(jié)點(diǎn)A 要取子節(jié)點(diǎn)中最小值，此時(shí)子節(jié)點(diǎn)B 已經(jīng)搜索完畢得到估值，程序開(kāi)始繼續(xù)搜索子節(jié)點(diǎn)C，而C 節(jié)點(diǎn)應(yīng)為其子節(jié)點(diǎn)中的最大值，這時(shí)，倘若C 的某一個(gè)子節(jié)點(diǎn)C1 的估值大于B 節(jié)點(diǎn)，類(lèi)似的，可以得出C 節(jié)點(diǎn)的余下子節(jié)點(diǎn)的估值便對(duì)父節(jié)點(diǎn)A 的評(píng)估沒(méi)有任何貢獻(xiàn)。

圖3

我們稱(chēng)第一種冗余為極大冗余，對(duì)應(yīng)的，當(dāng)發(fā)現(xiàn)產(chǎn)生這種情況時(shí)便對(duì)這些多余的搜索分支進(jìn)行修剪，稱(chēng)為Alpha 剪枝。對(duì)第二種優(yōu)化稱(chēng)為Beta 剪枝。將這兩種優(yōu)化方案運(yùn)用到極大極小搜索算法中便構(gòu)成了Alpha-Beta 搜索算法。其具體的實(shí)現(xiàn)為：在每一次搜索過(guò)程中，記錄搜索極大值的節(jié)點(diǎn)的當(dāng)前最優(yōu)值為α,搜索極小值的節(jié)點(diǎn)的當(dāng)前最值為β。在每一次搜索開(kāi)始時(shí)，將α,β 分別設(shè)置為機(jī)器最小值和機(jī)器最大值。這樣，在搜索的過(guò)程中間便能使得α,β 構(gòu)成一個(gè)窗口，從而跳過(guò)沒(méi)有落在這個(gè)窗口的子節(jié)點(diǎn)的搜索分支，達(dá)到減少搜索次數(shù)的優(yōu)化目的。

其總的行為流程圖如下：

圖4

2.2.2 Alpha-Beta 性能分析

根據(jù)Kunth 等人的證明，在子節(jié)點(diǎn)排列最理想的情況下，即搜索到的第一個(gè)子節(jié)點(diǎn)估值就不落在[α,β] 窗口內(nèi)內(nèi)，使用Aplha-Beta 搜索D 層生成的節(jié)點(diǎn)數(shù)目N 為

ND= 2bD/2-1 ( D 為偶數(shù))

ND= b(D+1)/2+b(D-1)/2-1 ( D 為奇數(shù))

這樣，時(shí)間復(fù)雜度降到了約極大極小搜索算法1/2 倍，為o(END/2)。

2.3 對(duì)上述搜索策略的優(yōu)化

通過(guò)Alpha-Beta 剪枝過(guò)后，我們極大的優(yōu)化了搜索次數(shù)，但從Kunth 等人的假設(shè)也不難看出，真正優(yōu)化程度于節(jié)點(diǎn)的排列序列高度相關(guān)。由于Alpha-Beta 剪枝對(duì)中體的子節(jié)點(diǎn)排序，即當(dāng)前局面的下一步的行為高度相關(guān)，那么，如果能夠粗略的對(duì)當(dāng)前局面產(chǎn)生的所有可能的行為有一個(gè)判斷，以便能更快地縮小[α,β]的范圍，從而產(chǎn)生更多的剪枝。這就涉及到了關(guān)于行為排序的思想。其次，在之前的多次索索中，難免會(huì)出現(xiàn)許多重復(fù)估值的現(xiàn)象，即可能通過(guò)不同的行為順序達(dá)到同一局面，這也會(huì)造成時(shí)間上的浪費(fèi)，故可在搜索是建立歷史數(shù)據(jù)庫(kù)，以期之后遇到重復(fù)局面時(shí)能夠減小評(píng)估開(kāi)銷(xiāo)，從而降低時(shí)間復(fù)雜度。這便是結(jié)合歷史經(jīng)驗(yàn)進(jìn)行判斷的思想。

2.3.1 行為排序

為了進(jìn)行行為排序，我們需要對(duì)當(dāng)前局面進(jìn)行大致判斷，將當(dāng)前局面看似最無(wú)意義的行為放在搜索的后面，將可能產(chǎn)生最優(yōu)解的行為放在前面進(jìn)行搜索。這便十分依賴(lài)于博弈者所面臨的具體博弈的條件，下面僅僅以中國(guó)象棋為例，簡(jiǎn)要闡明該思想。岳金朋(2008)在討論針對(duì)中國(guó)象棋的優(yōu)化中提出了一種靜態(tài)評(píng)價(jià)的啟發(fā)，他將行為分為了吃子行為和非吃子行為。在吃子行為中，通過(guò)簡(jiǎn)單的對(duì)被吃子是否有其它棋子保護(hù)，而導(dǎo)致吃子后我方棋子可能被吃來(lái)對(duì)每一吃子行為進(jìn)行排序。簡(jiǎn)而言之，他將被吃子的分?jǐn)?shù)減去我方行為完后可能被吃子的分?jǐn)?shù)作為判斷依據(jù)進(jìn)行排序。對(duì)與非吃子行為，岳金朋提出可以首先生成車(chē)的行為，最后生成帥的行為，在生成車(chē)的行為中，先考慮向前走的行為，后考慮向后走的行為，也可以起到一定的排序選擇作用。

2.3.2 歷史啟發(fā)

由于歷史啟發(fā)策略需要用到歷史數(shù)據(jù)庫(kù)，對(duì)每一個(gè)歷史局面進(jìn)行保存。Zobrist(1970)提出了一種根據(jù)目前局面的所應(yīng)方法，經(jīng)過(guò)驗(yàn)證，該方法在搜索局面時(shí)十分高效。Zobrist 的具體方法是，對(duì)于每一個(gè)局面而言，其唯一的標(biāo)示就是當(dāng)前所有狀態(tài)的異或值。同時(shí)，Zobrist 提出，在所有的博弈搜索算法中，層次更深的搜索往往意味著更加穩(wěn)健的評(píng)估，故對(duì)于每一個(gè)歷史局面的保存應(yīng)該考慮到該局面的搜索深度。進(jìn)而結(jié)合上文提到的行為排序的思想，我們也應(yīng)當(dāng)考慮某一局面能夠引發(fā)的剪枝數(shù)量，一般而言，如果在同一層次的搜索中，如果能夠?qū)⒛軌蛞l(fā)剪枝數(shù)量更多的行為先行搜索，也可以極大的優(yōu)化算法的時(shí)間復(fù)雜度，因此，我們也應(yīng)該保存某一行為所能引發(fā)的剪枝數(shù)量。在Zobrist 的局面表示方法下，我們以此生成Hash 表進(jìn)行存儲(chǔ)每一個(gè)局面的具體信息。具體的Hash 表的實(shí)現(xiàn)原理于此不過(guò)多贅述，參見(jiàn)參考文獻(xiàn)[6]。具體而言，假設(shè)現(xiàn)在要對(duì)某一局面進(jìn)行d 層搜索，當(dāng)前窗口是[α,β]，而通過(guò)上述方法發(fā)現(xiàn)歷史中該局面已經(jīng)存在，評(píng)價(jià)為v，類(lèi)型為t，經(jīng)過(guò)了d’層搜索。如果t 為精確型估值，即在歷史中的搜索該局面沒(méi)有因?yàn)榧糁Χ艞壦阉?，便可以直接返回v 而代替索索。如果t 為模糊型，則判定是否高過(guò)邊界，從而判斷是否可以直接引發(fā)剪枝。

2.4 淺層搜索優(yōu)化策略

與Shell 對(duì)插入排序算法的優(yōu)化類(lèi)似，Krof(1985)也提出了對(duì)Alpha-Beta 搜索算法的一種可能的優(yōu)化方案。Krof 的基本思想是，在生成走法時(shí)，先進(jìn)行較為初級(jí)的淺層搜索，在上文中對(duì)Alpha-Beta 搜索算法的性能分析中我們不難看出，搜索復(fù)雜度伴隨著搜索層次成指數(shù)級(jí)增加。對(duì)于一個(gè)D 層的搜索而言，（D-2）層的搜索的復(fù)雜度完全與其不在一個(gè)數(shù)量級(jí)上。倘若在搜索生成走法前，先通過(guò)一個(gè)d 層的淺層搜索來(lái)對(duì)所有行為進(jìn)行排序，那么，那些在淺層搜索中的較優(yōu)行為就將在深層搜索中較前被嘗試，從而得到更高的剪枝效率。

2.5 本文提出的優(yōu)化方案——偽搜索策略

上述的諸多改進(jìn)全部是基于既定時(shí)間內(nèi)盡可能搜索多的深度，以深度提高程序的智能程度。然而，上述改進(jìn)全部是基于搜索前的改進(jìn)，這可以極大的減少搜索量級(jí)，以換取更多的搜索時(shí)間。不過(guò)，本文在實(shí)際中發(fā)現(xiàn)，在同一搜索量集中，不同搜索次數(shù)并不會(huì)很大的影響搜索時(shí)間，如共執(zhí)行N 次搜索和執(zhí)行2N 次搜索時(shí)間開(kāi)銷(xiāo)并不大。但后者無(wú)疑進(jìn)行了更多次的搜索，在表現(xiàn)上理應(yīng)更加高效。因此，倘若在所有搜索結(jié)束，再進(jìn)行一些淺層的判斷，對(duì)程序的表現(xiàn)無(wú)疑是有益處的。設(shè)初始量級(jí)為N，每層生成M 個(gè)行為，共搜索D 層，則有：N=MD。若對(duì)第D 層行為進(jìn)行復(fù)雜度為P 的淺層判斷，則總共的量級(jí)N'應(yīng)有：

N'=N+M×P

其中：M×P＜＜N

故對(duì)總的程序無(wú)顯著影響，而判斷次數(shù)更高，可以獲得更好的表現(xiàn)。

3 測(cè)試

至此，我們完成了對(duì)整個(gè)博弈搜索過(guò)程的優(yōu)化。由于本文并不針對(duì)任何一種博弈過(guò)程，只是提出針對(duì)博弈搜索過(guò)程的算法及其優(yōu)化，無(wú)法進(jìn)行具體的性能分析，下文將以中國(guó)象棋為例，討論優(yōu)化的具體效果。在基于挑夾棋游戲規(guī)則進(jìn)行以類(lèi)似本文2.2 的Alpha-Beta 搜索和通過(guò)2.3.1 行為排序進(jìn)行優(yōu)化后的算法進(jìn)行比較，得到如下結(jié)果：

表1

通過(guò)2.4 淺層搜索優(yōu)化，與普通的Alpha-Beta 搜索進(jìn)行比較，得到如下結(jié)果：

表2