博弈樹的搜索

《博弈樹的搜索》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、博弈樹搜索所謂雙人完備信息，就是兩位選手對壘，輪流走步，這時每一方不僅都知道對方過去已經(jīng)走過的棋步，而且還能估計出對方未來可能的走步。對弈的結(jié)果是一方贏（另一方則輸），或者雙方和局。這類博弈的實例有：一字棋、余一棋、西洋跳棋、國際象棋、中國象棋、圍棋等。對于帶機遇性的任何博弈，因不具有完備信息，不屬這里討論范圍，但有些論述可推廣到某些機遇博弈中應(yīng)用。博弈問題可以用產(chǎn)生式系統(tǒng)的形式來描述，例如中國象棋，綜合數(shù)據(jù)庫可規(guī)定為棋盤上棋子各種位置布局的一種描述，產(chǎn)生式規(guī)則是各類棋子合法走步的描述，目標則可規(guī)定為將（帥）被吃掉，規(guī)則作用于數(shù)據(jù)庫的結(jié)果便生

2、成出博弈圖或博弈樹。下面舉一個簡單的例子說明博弈問題可用與或圖表示，并討論搜索策略應(yīng)考慮的實際問題。中國象棋一盤棋平均走50步，總狀態(tài)數(shù)約為10的161次方。假設(shè)1毫微秒走一步，約需10的145次方年。結(jié)論：不可能窮舉。博弈樹是與/或樹雙方都希望自己能夠獲勝。因此，當任何一方走步時，都是試圖選擇對自己最為有利，而對另一方最為不利的行動方案。從MAX方的觀點看，在博弈過程的每一步，可供自己選擇的行動方案之間是“或”的關(guān)系，原因在于選擇哪個方案完全是由自己決定的；而可供MIN選擇的行動方案之間則是“與”的關(guān)系，原因是主動權(quán)掌握在MIN手里，任何一

3、個方案都有可能被MIN選中，MAX必須防止那種對自己最為不利的情況的發(fā)生。這樣，從選手的角度看，博弈樹就是一棵與或樹，其特點是：（l）博弈的初始狀態(tài)是初始節(jié)點；（2）博弈樹中的“或”節(jié)點和“與”節(jié)點逐層交替出現(xiàn)（3）整個博弈過程始終站在某一方的立場上，所有能使自己一方獲勝的終局都是本原問題，相應(yīng)的節(jié)點是可解節(jié)點；所有使對方獲勝的終局都是不可解節(jié)點。極小極大搜索過程極小極大搜索策略是考慮雙方對弈若干步之后，從可能的走步中選一步相對好棋的走法來走，即在有限的搜索深度范圍內(nèi)進行求解。為此要定義一個靜態(tài)估計函數(shù)f，以便對棋局的勢態(tài)（節(jié)點）作出優(yōu)劣估值

4、，這個函數(shù)可根據(jù)勢態(tài)優(yōu)劣特征來定義（主要用于對端節(jié)點的“價值”進行度量）。一般規(guī)定有利于MAX的勢態(tài)，f（p）取正值，有利于MIN的勢態(tài)，f（p）取負值，勢均力敵的勢態(tài)，f（p）取0值。若f（p）＝＋∞，則表示MAX贏，若f（p）＝－∞，則表示MIN贏。下面的討論規(guī)定：頂節(jié)點深度d＝0，MAX代表程序方，MIN代表對手方，MAX先走。極小極大搜索過程極大極小過程步驟：（1）以當前考察的態(tài)勢P為根節(jié)點，生成指定深度的博弈樹。（2）根據(jù)靜態(tài)估計函數(shù)f計算各葉節(jié)點的估計值。（3）自底向上計算各個非葉節(jié)點的估計值，計算的方法是MAX節(jié)點取其子節(jié)點的最

5、大值，MIN節(jié)點取其子節(jié)點的最小值。（4）將根節(jié)點的倒推值對應(yīng)的策略作為當前的最佳策略。極小極大過程05-333-3022-30-23541-30689-30-33-3-3-21-36-30316011極大極小一字棋游戲設(shè)有一個三行三列的棋盤，兩個棋手輪流走步，每個棋手走時往空格上擺一個自己的棋子，誰先使自己的棋子成三子一線為贏。設(shè)程序方MAX的棋子用（×）表示，對手MIN的棋子用（○）表示，MAX先走。靜態(tài)估計函數(shù)f（p）規(guī)定如下：1.若P是MAX的必勝局，則e(P)=+∞；2.若P是MIN的必勝局，則e(P)=-∞；3.若P對MAX、MI

6、N都是勝負未定局，則e(P)=e(+P)－e(-P)其中，e(+P)表示棋局P上有可能使×成三子一線的數(shù)目；e(-P)表示棋局P上有可能使○成三子一線的數(shù)目。一字棋游戲f(+P)=6f(P)=f(+P)-f(P)=2f(-P)=4例在搜索過程中，具有對稱性的棋局認為是同一棋局，以大大減少搜索空間。對稱棋局的例子用極大極小搜索方法為MAX尋找第一步棋的走法。（搜索深度為2）α-β剪枝極大極小過程是先生成與/或樹，然后再計算各節(jié)點的估值，即生成節(jié)點和計算估值這兩個過程是分離的。在搜索時，需要生成規(guī)定深度內(nèi)的所有節(jié)點，因此搜索效率較低。以棋盤為15

7、×15大小的五子棋為例，人機對弈，用極大極小搜索算法，搜索深度為3時，計算機（配置：CUP賽場1.7G，內(nèi)存DDR266256M）每走1步要用10min，搜索的節(jié)點數(shù)超過了107個；而搜索深度為4時，每走1步要用10個多小時，搜索節(jié)點數(shù)超過了2×109個。如果能邊生成節(jié)點邊對節(jié)點估值，并根據(jù)一定的條件，提前剪去一些沒用的分枝，那么就可以有效提高搜索效率。在這種思想的基礎(chǔ)上，人們提出了α-β剪枝技術(shù)。α-β剪枝技術(shù)采用有界深度優(yōu)先策略，當生成規(guī)定深度的節(jié)點時，計算葉節(jié)點的靜態(tài)估值，并倒推非端節(jié)點的估值。根據(jù)倒推結(jié)果，在非端節(jié)點的向下分枝中，剪掉

8、那些目前未知，但無論如何都不會改變非端節(jié)點倒推值的未擴展分枝。用α－β剪枝技術(shù)，搜索深度為3時，每走1步不到2min，搜索的節(jié)點數(shù)小于1.5×106個；而搜索深度為