機器博弈研究報告

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