機(jī)器博弈研究報(bào)告

機(jī)器博弈及其搜索算法的研究摘要機(jī)器博弈是人工智能一種老式的研究領(lǐng)域。本文從機(jī)器博弈的基本理論談起，簡(jiǎn)介了機(jī)器博弈理論和機(jī)器博弈系統(tǒng)的一般構(gòu)成，尤其論述了現(xiàn)今已存在的多種機(jī)器博弈搜索算法及其優(yōu)缺陷。關(guān)鍵詞博弈系統(tǒng)博弈搜索算法alpha-beta搜索最佳優(yōu)先搜索1序言機(jī)器博弈的研究廣泛而深入。早在上世紀(jì)五十年代，就有人設(shè)想運(yùn)用機(jī)器智能來(lái)實(shí)現(xiàn)機(jī)器與人的對(duì)弈。國(guó)內(nèi)外許多著名學(xué)者和著名科研機(jī)構(gòu)都曾經(jīng)涉足這方面的研究，歷經(jīng)半個(gè)多世紀(jì)，到目前為止已經(jīng)獲得了許多驚人的成就。1997年IBM的“深藍(lán)”戰(zhàn)勝了國(guó)際象棋世界冠軍卡斯帕羅夫，驚動(dòng)了世界。除此之外，加拿大阿爾伯塔大學(xué)的奧賽羅程序Logistello和西洋跳棋程序Chinook也相繼成為確定的、二人、零和、完備信息游戲世界冠軍[1]，而西洋雙陸棋這樣的存在非確定原因的棋類(lèi)也有了美國(guó)卡內(nèi)基梅隆大學(xué)的西洋雙陸琪程序BKG這樣的世界冠軍[1]。對(duì)圍棋、中國(guó)象棋、橋牌、撲克等許多種其他種類(lèi)游戲博弈的研究也正在進(jìn)行中。機(jī)器博弈的關(guān)鍵技術(shù)是博弈搜索算法，這也是機(jī)器博弈研究的熱點(diǎn)。本文首先簡(jiǎn)介機(jī)器博弈的基本理論和機(jī)器博弈系統(tǒng)的一般構(gòu)成，然后重點(diǎn)講述現(xiàn)存的多種博弈搜索算法。2機(jī)器博弈的基本思想機(jī)器博弈的關(guān)鍵思想并不復(fù)雜，實(shí)際上就是對(duì)博弈樹(shù)節(jié)點(diǎn)的估值過(guò)程和對(duì)博弈樹(shù)搜索過(guò)程的結(jié)合。[7]在博弈的任何一種中間階段，站在博弈雙方其中一方的立場(chǎng)上，可以設(shè)想一種博弈樹(shù)。這個(gè)博弈樹(shù)的根節(jié)點(diǎn)是目前時(shí)刻的棋局，它的兒子節(jié)點(diǎn)是假設(shè)再行棋一步后來(lái)的多種棋局，孫子節(jié)點(diǎn)是從兒子節(jié)點(diǎn)的棋局再行棋一步的多種棋局，以此類(lèi)推，構(gòu)造整棵博弈樹(shù)，直到可以分出勝敗的棋局。整棵的博弈樹(shù)非常龐大，且不一樣的棋類(lèi)有所不一樣，分支因子大的如圍棋的博弈樹(shù)顯然要比分支因子小的如國(guó)際象棋的博弈樹(shù)要大得多。博弈程序的任務(wù)就是對(duì)博弈樹(shù)進(jìn)行搜索找出目前最優(yōu)的一步行棋。對(duì)博弈樹(shù)進(jìn)行極大極小搜索，可以到達(dá)這一目的。極大極小搜索，是由于博弈雙方所要到達(dá)的目的相反，一方要尋找的利益恰是一方失去的利益，因此博弈的一方總是但愿下一走是兒子節(jié)點(diǎn)中取值最大者，而另一方恰恰相反。這便形成了極大極小過(guò)程。當(dāng)然，程序不能也沒(méi)有必要做到搜索整棵博弈樹(shù)的所有節(jié)點(diǎn)，對(duì)于某些已經(jīng)確定為不佳的走步可以將以它為根節(jié)點(diǎn)的子樹(shù)剪掉。并且，搜索也不必真地進(jìn)行到分出勝敗的棋局，只需要在一定深度范圍內(nèi)對(duì)局面進(jìn)行評(píng)價(jià)即可。只有搜索空間縮小到一定程度，搜索才可以真正的進(jìn)行。當(dāng)搜索進(jìn)行到一定深度，用局面評(píng)價(jià)機(jī)制來(lái)評(píng)價(jià)棋局，按照極大極小的原則選出最優(yōu)，向上回溯，給出這一局面的父親節(jié)點(diǎn)的價(jià)值評(píng)價(jià)，然后再繼續(xù)向上回溯，一直到根節(jié)點(diǎn)，最優(yōu)走步就是這樣搜索出來(lái)的。在這個(gè)過(guò)程中，最為重要的是搜索算法，高效的搜索算法可以保證用盡量少的時(shí)間和空間損耗來(lái)到達(dá)尋找高價(jià)值的走步。不過(guò)真的想要博弈程序棋力提高，還必須有一種好的局面評(píng)價(jià)機(jī)制，即估值算法作后盾。就是說(shuō)，用這個(gè)估值算法評(píng)價(jià)的局面價(jià)值必須是客觀(guān)的、對(duì)的的，可以確鑿的評(píng)價(jià)局面的優(yōu)劣以及優(yōu)劣的程度。3機(jī)器博弈系統(tǒng)根據(jù)機(jī)器博弈的基本思想，可以確定一種機(jī)器博弈系統(tǒng)的一般構(gòu)成[6]。首先是知識(shí)表達(dá)的問(wèn)題，選用一種合適的措施記錄棋局。這時(shí)需要考慮在這種知識(shí)表達(dá)的數(shù)據(jù)構(gòu)造之上將要進(jìn)行的多種操作，知識(shí)表達(dá)應(yīng)當(dāng)使最常常進(jìn)行的操作花費(fèi)的時(shí)間和空間代價(jià)最小。另一方面，根據(jù)不一樣的棋類(lèi)的不一樣規(guī)則集，要有一種對(duì)應(yīng)的走法產(chǎn)生機(jī)制。它的作用是用來(lái)產(chǎn)生整棵博弈樹(shù)，即處在博弈樹(shù)的任何一種節(jié)點(diǎn)位置上，應(yīng)當(dāng)可以運(yùn)用該機(jī)制產(chǎn)生這個(gè)節(jié)點(diǎn)的所有兒子節(jié)點(diǎn)，也就是接下來(lái)的所有合法走步。除了以上兩個(gè)模塊以外，就是博弈關(guān)鍵的搜索技術(shù)和與之配合的估值技術(shù)了。這四個(gè)部分互相配合運(yùn)轉(zhuǎn)起來(lái)，就可以實(shí)現(xiàn)機(jī)器博弈。4博弈搜索博弈搜索的基本思想已經(jīng)提出半個(gè)多世紀(jì)，目前廣泛研究的是確定的、二人、零和、完備信息的博弈搜索。也就是說(shuō)，沒(méi)有隨機(jī)原因的博弈在兩個(gè)人之間進(jìn)行，在任何一種時(shí)刻，一方失去的利益即為另一方得到的利益，不會(huì)出現(xiàn)“雙贏”的局面，并且在任何時(shí)刻，博弈的雙方都明確的懂得每一種棋子與否存在和存在于哪里。二人、零和、完備信息的博弈搜索理論已經(jīng)很系統(tǒng)。極大極小算法是所有搜索算法的基礎(chǔ)。在這個(gè)基礎(chǔ)上，目前在這一領(lǐng)域的算法重要有兩類(lèi)，一類(lèi)是作為主流的深度優(yōu)先的alpha-beta搜索及其系列增強(qiáng)算法，另一類(lèi)是最佳優(yōu)先的系列算法[2]。4．1基本搜索算法1．極大極小值算法（MinimaxAlgorithm）一直站在博弈一方的立場(chǎng)上給棋局估值，有助于這一方的棋局予以一種較高的價(jià)值分?jǐn)?shù)，不利于這一方（有助于另一方）的予以一種較低的價(jià)值分?jǐn)?shù)，雙方優(yōu)劣不明顯的局面予以一種中間價(jià)值分?jǐn)?shù)。在這一方行棋的時(shí)候，選擇價(jià)值極大的兒子節(jié)點(diǎn)走步，另一方行棋則選擇價(jià)值極小的兒子節(jié)點(diǎn)走步。這就是一種極大極小過(guò)程。2．負(fù)極大值搜索（NegamaxAlgorithm）在極大極小過(guò)程中，每一次進(jìn)行極大或者極小的比較之前，都要對(duì)究竟是要選擇極大還是極小節(jié)點(diǎn)進(jìn)行判斷，1975年Knuth和Moore提出的負(fù)極大值算法意在消除兩方面的差異，使算法簡(jiǎn)潔優(yōu)雅。它的關(guān)鍵思想在于：父節(jié)點(diǎn)的值是各子節(jié)點(diǎn)的負(fù)數(shù)的極大值。負(fù)極大值搜索的原理和極大極小值是搜索同樣的，只是體現(xiàn)形式不一樣，并且由于它的簡(jiǎn)潔，目前已經(jīng)廣泛取代了極大極小值算法。4．2深度優(yōu)先的alpha-beta搜索及其增強(qiáng)算法在極大極小搜索的過(guò)程中，存在著一定程度的數(shù)據(jù)冗余，剔除這些冗余數(shù)據(jù)，是減小搜索空間的必然做法，所采用的措施就是1975年MonroeNewborn提出的alpha-beta剪枝。把a(bǔ)lpha-beta剪枝應(yīng)用到極大極小搜索或者負(fù)極大值搜索中，就形成了alpha-beta搜索。alha-beta剪枝的過(guò)程是這樣的，如圖4-1左半部所示極大極小樹(shù)的片斷，節(jié)點(diǎn)B的值為18，節(jié)點(diǎn)D的值為16，由此可以判斷節(jié)點(diǎn)C的值將不不小于等于16（取極小值）；而節(jié)點(diǎn)A的值為節(jié)點(diǎn)Max（B，C），為18，也就是說(shuō)不再需要估節(jié)點(diǎn)C的其他子節(jié)點(diǎn)如E、F的值就可以得出父節(jié)點(diǎn)A的值了。這樣將節(jié)點(diǎn)D的后繼兄弟節(jié)點(diǎn)減去稱(chēng)為alpha剪枝。圖4-1右半部所示極大極小樹(shù)的片斷，節(jié)點(diǎn)B的估值為8，節(jié)點(diǎn)D的估值為18，由此可以判斷節(jié)點(diǎn)C的值將不小于等于18（取極大值）；而節(jié)點(diǎn)A的值為節(jié)點(diǎn)Min（B，C），為8。也就是說(shuō)不再需規(guī)定節(jié)點(diǎn)C的其他子節(jié)點(diǎn)如E、F的值就可以得出父節(jié)點(diǎn)A的值了。這樣將節(jié)點(diǎn)D的后繼兄弟節(jié)點(diǎn)減去稱(chēng)為beta剪枝。圖4-1alpha-beta搜索由于過(guò)程簡(jiǎn)樸、輕易理解、且占用空間小等優(yōu)良特點(diǎn)被廣泛應(yīng)用，成為目前主流的搜索算法的基礎(chǔ)。不過(guò)它也有缺陷，即它對(duì)于節(jié)點(diǎn)的排列非常敏感。對(duì)于同一層上的節(jié)點(diǎn)，假如排列合適，剪枝效率就很高，可以使實(shí)際搜索的博弈樹(shù)到達(dá)最小樹(shù)。所謂最小樹(shù)就是一經(jīng)向下搜索，第一種節(jié)點(diǎn)就是要尋找的走步?？墒?，假如節(jié)點(diǎn)的排列次序不是從最差到最佳，就有也許使剪枝一直無(wú)法進(jìn)行，從而實(shí)際上搜索了整棵的博弈樹(shù)。大多數(shù)alpha-beta剪枝算法都采用深度優(yōu)先的搜索方略，是由于深度優(yōu)先搜索較之寬度優(yōu)先搜索節(jié)省存儲(chǔ)空間，只需保留根節(jié)點(diǎn)到目前搜索節(jié)點(diǎn)的途徑上的節(jié)點(diǎn)信息即可。針對(duì)alpha-beta搜索的特點(diǎn)，有許多種增強(qiáng)算法被提出，這些算法有些已經(jīng)被證明為是非常有效的，從而成為該領(lǐng)域的原則搜索算法。下面是alpha-beta的增強(qiáng)算法的簡(jiǎn)介?？释阉鳎ˋspirationSearch）在alpha-beta剪枝過(guò)程中，初始的的搜索窗口往往是從-∞（即初始的alpha值）到+∞（初始的beta值），在搜索進(jìn)行中再不?？s小窗口，加大剪枝效果?？释阉骶褪强释麖囊婚_(kāi)始就使用小的窗口，從而在搜索初起，就可以進(jìn)行大量的剪枝。這個(gè)初始窗口的選定很重要，假如選擇精確，即所要尋找的走步就在這個(gè)窗口內(nèi)，搜索便可以繼續(xù)進(jìn)行。假如第一步搜索的返回值證明最佳走步不小于beta值，就需要重新確定窗口。以本來(lái)的beta值為alpha值，以+∞為新的beta值重新搜索。相反假如第一步的返回值證明最佳走步不不小于alpha值，重新確定的窗口就是以-∞為alpha值，本來(lái)的alpha值為beta值了?？梢?jiàn)第一次搜索猜測(cè)的窗口非常重要，假如猜測(cè)精確，搜索時(shí)間可以大大縮短，假如不精確，這一優(yōu)勢(shì)就不明顯了。由于渴望搜索是一種基本的搜索措施，它在和背面論述的遍歷深化結(jié)合使用的時(shí)候，就可以借助前一次深度為depth的搜索的成果來(lái)猜測(cè)目前深度為depth+1搜索的窗口了。極小窗口搜索（MinimalWindowSearch）極小窗口搜索，也被稱(chēng)為是主變量導(dǎo)向搜索（PrincipalVariationSearch），常常簡(jiǎn)稱(chēng)為PVS算法或者NegaScout算法。這個(gè)算法應(yīng)用非常廣泛。它的出發(fā)點(diǎn)是和渴望搜索大體相似的，即用極小的窗口來(lái)限制剪枝范圍。它的過(guò)程是這樣的：在根節(jié)點(diǎn)處，假定第一種兒子節(jié)點(diǎn)為主變量，也就是假定它為最佳走步，對(duì)它進(jìn)行完整窗口(a,b)的搜索并得到一種返回值v，對(duì)背面的兒子節(jié)點(diǎn)依次用極小窗口（也被稱(chēng)為是零窗口）（v,v+1）來(lái)進(jìn)行搜索，假如搜索返回值不小于零窗口，則證明這一分支亦為主變量，對(duì)它進(jìn)行窗口為（v+1,b）的搜索，可是假如返回值不不小于零窗口，這一分支就可以忽視，由于它的最佳走步還不如已經(jīng)有的走步。極小窗口搜索采用了極小的窗口，剪枝效率最高，并且只對(duì)主變量進(jìn)行大窗口的搜索，因此大部分搜索動(dòng)作是有效的，搜索產(chǎn)生的博弈樹(shù)也很小。置換表（TranspositionTable）在搜索進(jìn)行中，查詢(xún)所有的走步，常常會(huì)在相似的或者不一樣的途徑上碰到相似的棋局，這樣的子樹(shù)就沒(méi)有必要反復(fù)搜索，把子樹(shù)根節(jié)點(diǎn)的估值、子樹(shù)的最佳走步和獲得這個(gè)值的深度信息保留在一種稱(chēng)為置換表的數(shù)據(jù)構(gòu)造中，下次碰屆時(shí)直接運(yùn)用即可。不過(guò)，對(duì)不一樣的狀況要區(qū)別看待。對(duì)于固定深度的搜索，假如前一次保留的子樹(shù)深度不不小于新節(jié)點(diǎn)要搜索的深度，還是要進(jìn)行重新的搜索以保證所獲得數(shù)據(jù)的精確程度。反之，假如置換表中保留的子樹(shù)信息表明，子樹(shù)的深度不小于或者等于目前的新節(jié)點(diǎn)規(guī)定的搜索深度，它的信息就可以直接運(yùn)用了。置換表增強(qiáng)假如和有效的alpha-beta搜索結(jié)合使用，成果就會(huì)使實(shí)際搜索的博弈樹(shù)不不小于最小樹(shù)。博弈樹(shù)搜索的問(wèn)題實(shí)際上是一種有向圖的搜索。那些在置換表中被命中的節(jié)點(diǎn)，就是有向圖中若干途徑的交叉點(diǎn)。只有防止這些交點(diǎn)被反復(fù)搜索，搜索過(guò)程中生成的搜索樹(shù)才有也許不不小于最小樹(shù)。這也是后來(lái)證明深度優(yōu)先的算法并不比最佳優(yōu)先的算法差的原因之一[3]。這個(gè)算法存在的問(wèn)題是，置換表的構(gòu)造，必須使對(duì)置換表的查找和插入操作不成為整個(gè)搜索的承擔(dān)，才能提高效率。一般使用散列表來(lái)實(shí)現(xiàn)。遍歷深化（IterativeDeepening）遍歷深化是因?qū)Σ┺臉?shù)進(jìn)行多次遍歷，又不停加深其深度而得名，有人還把它稱(chēng)為蠻力搜索。算法運(yùn)用了alpha-beta算法對(duì)子節(jié)點(diǎn)排序敏感的特點(diǎn)。它但愿通過(guò)淺層的遍歷給出節(jié)點(diǎn)的大體排序，把這個(gè)排序作為深層遍歷的啟發(fā)式信息。此外，算法用時(shí)間控制遍歷次數(shù)，時(shí)間一到，搜索立即停止，這也符合人類(lèi)棋手的下棋特點(diǎn)。在關(guān)鍵的開(kāi)局和殘局，由于分支較少，也可以進(jìn)行較深層次的搜索。算法的過(guò)程是，對(duì)以目前棋局為根節(jié)點(diǎn)的博弈樹(shù)進(jìn)行深度為二的遍歷，得出其兒子節(jié)點(diǎn)的優(yōu)劣排序，接著再?gòu)母?jié)點(diǎn)進(jìn)行深度為三的遍歷，這一次優(yōu)先搜索上次遍歷中得出的最優(yōu)者，從而加大剪枝效果，以此類(lèi)推，在進(jìn)行第三次、第四次的遍歷，一直到達(dá)限定期間為止。由于這個(gè)算法的每次遍歷都從根節(jié)點(diǎn)開(kāi)始，因此有人稱(chēng)其為蠻力搜索，但實(shí)際上由于每次都可以?xún)?yōu)先搜索相對(duì)好的節(jié)點(diǎn)，導(dǎo)致剪枝效率增大，其實(shí)算法效率是很高的，目前這一算法也得到了廣泛的承認(rèn)。歷史啟發(fā)搜索（HistoryHeuristic）[4]歷史啟發(fā)也是迎合alpha-beta搜索對(duì)節(jié)點(diǎn)排列次序敏感的特點(diǎn)來(lái)提高剪枝效率的，即對(duì)節(jié)點(diǎn)排序，從而優(yōu)先搜索好的走法。所謂好的走法即可以引起剪枝的走法或者是其兄弟節(jié)點(diǎn)中最佳的走法。一種這樣的走法，一經(jīng)碰到，就給其歷史得分一種對(duì)應(yīng)的增量，使其具有更高的優(yōu)先被搜索的權(quán)利。殺手啟發(fā)搜索(KillerHeuristic)殺手啟發(fā)實(shí)際上是歷史啟發(fā)的特例。它是把同一層中，引起剪枝最多的節(jié)點(diǎn)稱(chēng)為殺手，當(dāng)下次搜索時(shí)，搜索到同一層次，假如殺手走步是合法的話(huà)，就優(yōu)先搜索殺手。MTD(f)算法MTD(f)搜索的全稱(chēng)是Memory–enhancedTestDriverwithfandn。它是一種較新的算法，在1995左右年由AskePlaat等人提出。它不是單一的alpha-beta算法的增強(qiáng)，但也是alpha-beta算法的改善。在算法進(jìn)行中多次調(diào)用了零窗口的alpha-beta搜索過(guò)程。在算法初起，要給定一種初始值f，一種上界和一種下界。初始值要盡量的靠近最終要找到的最優(yōu)走步值，上界和下界要保證能把這個(gè)最優(yōu)走步包括在內(nèi)。算法實(shí)際上就是不停的應(yīng)用零窗口的alpha-beta搜索，縮小上界和下界，并移動(dòng)初始值使其靠近最優(yōu)走步。如下使這個(gè)算法的偽代碼[1]。functionMTD(n)–〉;g:=;+:=+∞;:=－∞;repeatifg=－thenγ:=g+1elseγ:=g;g:=alphabeta(n,γ-1,γ)/*g:=Alpha-Beta(n－1)isequivalent*/ifg<γthen+:=gelse－:=g;until－≥+;returng;圖4-2在這個(gè)偽代碼中，可以看出算法名稱(chēng)中的f為初始值，而n為搜索深度，這里g為最終要找的最佳走步，γ為零窗口的上界。由于算法運(yùn)用了多次alpha-beta搜索，因此需要配合置換表，這樣才能使速度足夠的快，從而到達(dá)提高效率的目的。MTD(f)算法簡(jiǎn)樸并且比前述多種算法都高效。有不少實(shí)踐者的試驗(yàn)證明，在國(guó)際象棋、西洋跳棋等博弈程序里，MTD(f)的平均體現(xiàn)要比PVS好，當(dāng)今最強(qiáng)大的國(guó)際象棋程序之一，麻省理工學(xué)院的Cilkchess就使用了并行的MTD(f)替代了其初始版本的NegaScout作為搜索算法[8]。4．3最佳優(yōu)先算法理論上，最佳優(yōu)先的搜索算法，由于不受節(jié)點(diǎn)排序的影響，其搜索空間不不小于深度優(yōu)先的最小樹(shù)，應(yīng)當(dāng)優(yōu)于深度優(yōu)先。因此在二十世紀(jì)六七十年代，相繼有人提出了最佳優(yōu)先的系列算法。不過(guò)，最佳優(yōu)先算法可以說(shuō)一直都待在研究人員的試驗(yàn)室里。真正的博弈程序開(kāi)發(fā)者很少有使用這個(gè)算法的。而Alpha-Beta通過(guò)一系列增強(qiáng)如置換表、歷史啟發(fā)、零窗探測(cè)、遍歷深化等手段，其性能已遠(yuǎn)遠(yuǎn)高于最初的Alpha-Beta。某些研究人員發(fā)既有部分基于AlphaBeta的博弈程序?qū)嶋H生成的搜索樹(shù)已不不小于最小樹(shù)[3]。最佳優(yōu)先算法分為兩類(lèi)[5]，一類(lèi)是仍然采用極大極小措施取值的SSS*算法和DUAL*算法，另一類(lèi)是沒(méi)有采用極大極小措施取值的B*和PB*算法。SSS*和DUAL*算法這兩種算法即為狀態(tài)空間搜索（StateSpaceSearch），由Stockman在1979年提出。它們是把極大極小樹(shù)的搜索當(dāng)作是對(duì)狀態(tài)圖的搜索，在不一樣的分支上展開(kāi)多條途徑，并且維護(hù)一種有關(guān)狀態(tài)圖的全局信息表。搜索過(guò)程同一般的狀態(tài)圖搜索大體同樣，還需要維護(hù)一種有序的OPEN隊(duì)列輔助。SSS*算法和DUAL*算法是兩個(gè)相對(duì)的過(guò)程，兩者對(duì)最大值或最小值的操作相反，最大化操作和最小化操作相反，OPEN隊(duì)列的排列的排列也是相反的。AskePlaat等人的研究表明SSS*算法在搜索深度為偶數(shù)的極大極小搜索中體現(xiàn)較佳，DUAL*則在深度為奇數(shù)搜索中較佳。這兩個(gè)算法的缺陷是：算法復(fù)雜，難于理解；額外的數(shù)據(jù)構(gòu)造占用空間大；并且維護(hù)有序的OPEN隊(duì)列所用的時(shí)間開(kāi)銷(xiāo)大。B*和PB*算法1969年Berliner提出了B*算法，用一種樂(lè)觀(guān)值和一種消極值來(lái)表達(dá)評(píng)價(jià)值。算法從這點(diǎn)出發(fā)，用這兩個(gè)界來(lái)證明哪個(gè)節(jié)點(diǎn)是最佳的。當(dāng)根節(jié)點(diǎn)的一種孩子的消極值不比所有其他節(jié)點(diǎn)的樂(lè)觀(guān)值差的時(shí)候，B*算法就結(jié)束了。算法的搜索控制就是盡量快的得到終止條件。B*算法的缺陷是它對(duì)局面的樂(lè)觀(guān)值和消極值的估計(jì)得可信賴(lài)程度，它對(duì)這個(gè)估值的依賴(lài)性太強(qiáng)。PB*算法就是基于概率的B*算法，由Paley在1983年提出。這個(gè)算法對(duì)概率的精確估計(jì)比較敏感，實(shí)現(xiàn)困難。5結(jié)語(yǔ)以上簡(jiǎn)要地論述了機(jī)器博弈理論的原理，并且對(duì)現(xiàn)存的二人零和完備信息搜索措施給出了比較全面的講述。二人零和完備信息博弈的研究已經(jīng)有半個(gè)多世紀(jì)的歷史，其知識(shí)構(gòu)造系統(tǒng)，層次清晰，已經(jīng)獲得了許多驚人的成果。另一種方向是非完備信息游戲的博弈研究，本文沒(méi)有波及。這方面的研究也獲得了某些成果，如拼字游戲Scrabble，橋牌和撲克，都可以實(shí)現(xiàn)人機(jī)對(duì)戰(zhàn)的過(guò)程，有某些程序還相稱(chēng)強(qiáng)大，但比之完備信息的博弈，它的研究還遠(yuǎn)遠(yuǎn)不夠廣泛。重要參照文獻(xiàn)Plaat.ReachRe:Search&Re-Search.PhDthesis,ErasmusUniversity,Dept.pfCom