計(jì)算機(jī)博弈的研究與發(fā)展

王亞杰，邱虹坤，吳燕燕，李飛，楊周鳳

(沈陽航空航天大學(xué) 工程訓(xùn)練中心，遼寧 沈陽 110136)

計(jì)算機(jī)博弈的研究與發(fā)展

王亞杰，邱虹坤，吳燕燕，李飛，楊周鳳

(沈陽航空航天大學(xué) 工程訓(xùn)練中心，遼寧 沈陽 110136)

計(jì)算機(jī)博弈是人工智能領(lǐng)域重要而極具挑戰(zhàn)性的研究方向。本文首先回顧了計(jì)算機(jī)博弈的發(fā)展歷程，以及國內(nèi)外的計(jì)算機(jī)博弈賽事情況，各種競賽為計(jì)算機(jī)博弈技術(shù)的發(fā)展提供了一個(gè)技術(shù)驗(yàn)證與學(xué)術(shù)交流的平臺(tái)。然后介紹了計(jì)算機(jī)博弈系統(tǒng)的構(gòu)成, 一個(gè)博弈系統(tǒng)包括博弈平臺(tái)、博弈樹搜索、局面評估、著法生成、機(jī)器學(xué)習(xí)等多方面技術(shù)；重點(diǎn)闡述了極大極小搜索、剪枝搜索、蒙特卡羅搜索等常用算法的原理與特點(diǎn)；對局面評估方法和各種優(yōu)化算法也進(jìn)行了分析，其中的并行計(jì)算、遺傳算法和基于神經(jīng)網(wǎng)絡(luò)的深度學(xué)習(xí)算法等都是提升機(jī)器智能的有效方法。最后，分析了計(jì)算機(jī)博弈研究面臨的問題，并展望了未來的發(fā)展方向與趨勢。

人工智能；計(jì)算機(jī)博弈；蒙特卡羅搜索；神經(jīng)網(wǎng)絡(luò)；遺傳算法；深度學(xué)習(xí)

計(jì)算機(jī)博弈，也稱之為機(jī)器博弈，是人工智能領(lǐng)域的挑戰(zhàn)性課題。它從模仿人腦智能的角度出發(fā)，以計(jì)算機(jī)下棋為研究載體，通過模擬人類棋手的思維過程，構(gòu)建一種更接近人類智能的博弈信息處理系統(tǒng)，并可以拓展到其他相關(guān)領(lǐng)域，解決實(shí)際工程和科學(xué)研究領(lǐng)域中與博弈相關(guān)的難以解決的復(fù)雜問題[1-2]。作為人工智能研究的一個(gè)重要分支，它是檢驗(yàn)計(jì)算機(jī)技術(shù)及人工智能發(fā)展水平的一個(gè)重要方向，為人工智能帶來了很多重要的方法和理論，極大地推動(dòng)了科研進(jìn)步，并產(chǎn)生了廣泛的社會(huì)影響和學(xué)術(shù)影響[3-5]。

計(jì)算機(jī)博弈是知識(shí)工程演繹的平臺(tái)，是研究人工智能科學(xué)的“果蠅”[1]。如何提高機(jī)器智能，是計(jì)算機(jī)博弈研究的精髓所在。針對該領(lǐng)域技術(shù)進(jìn)行研究，有助于更好地理解人類的智能，更好地推動(dòng)人工智能技術(shù)和相關(guān)產(chǎn)業(yè)的融合與發(fā)展。

1 計(jì)算機(jī)博弈發(fā)展

1.1 起步階段

20世紀(jì)50年代開始，許多世界上著名的學(xué)者都曾經(jīng)涉足計(jì)算機(jī)博弈領(lǐng)域的研究工作，為機(jī)器博弈的研究與開發(fā)奠定了良好的基礎(chǔ)。阿蘭·圖靈(Alan Turing)先生最早寫下了能夠讓機(jī)器下棋的指令，計(jì)算機(jī)之父馮·諾依曼(John von Neumann)提出了用于博弈的極大極小定理，信息論創(chuàng)始人科勞德·香農(nóng)[6](Claude E. Shannon)首次提出了國際象棋的解決方案，人工智能的創(chuàng)始人麥卡錫(John McCarthy)首次提出“人工智能”(artificial intelligence)這一概念。1958年阿伯恩斯坦(Alex Bernstein)等[7]在IBM704機(jī)上開發(fā)了第1個(gè)成熟的達(dá)到孩童博弈水平的國際象棋程序。1959年，人工智能的創(chuàng)始人之一塞繆[8](A.L. Samuel)編了一個(gè)能夠戰(zhàn)勝設(shè)計(jì)者本人的西洋跳棋程序，1962年該程序擊敗了美國的一個(gè)州冠軍。

研究機(jī)器博弈的學(xué)者們發(fā)現(xiàn)，博弈程序的智能水平與搜索深度有很大關(guān)系。他們研究的內(nèi)容主要涉及：如何建立有效、快速的評價(jià)函數(shù)和評價(jià)方法，使評價(jià)的效率更高，花費(fèi)的時(shí)間和空間的代價(jià)更?。蝗绾卧谏傻牟┺臉渖细鼫?zhǔn)確有效地找到最優(yōu)解，并由此發(fā)展出來各種搜索算法[9-11]。

1.2 發(fā)展階段

20世紀(jì)80年代末，隨著計(jì)算機(jī)硬件和軟件技術(shù)不斷發(fā)展，計(jì)算機(jī)博弈理論日趨完善，學(xué)者們開始對電腦能否戰(zhàn)勝人腦這個(gè)話題產(chǎn)生了濃厚的興趣，并提出了以棋類對弈的方式，向人類發(fā)起挑戰(zhàn)，計(jì)算機(jī)博弈研究進(jìn)入了快速發(fā)展的階段。

在國外，1986年7月，Hinton等[12]在自然雜志(Nature)上發(fā)表論文，首次系統(tǒng)簡潔地闡述了反向傳播算法在神經(jīng)網(wǎng)絡(luò)模型上的應(yīng)用，給機(jī)器學(xué)習(xí)帶來了希望，掀起了基于統(tǒng)計(jì)模型的機(jī)器學(xué)習(xí)熱潮。1989年IBM公司研制的“深思”在與世界棋王卡斯帕羅夫進(jìn)行的“人機(jī)大戰(zhàn)”中，以0∶2敗北。1995年IBM更新了“深藍(lán)”程序，并使用新的集成電路將思考速度提高到每秒300萬步，在1996年與卡斯帕羅夫的挑戰(zhàn)賽中以2∶4敗北。1997年“超級深藍(lán)”融入了更深的開發(fā)，以3.5∶2.5擊敗了卡斯帕羅夫，這場勝利引起了世界范圍內(nèi)的轟動(dòng)，它表明“計(jì)算機(jī)智能戰(zhàn)勝了人類天才”。

在國內(nèi)，南開大學(xué)黃云龍教授和他的學(xué)生在20世紀(jì)80年代，開發(fā)了一系列中國象棋程序。中山大學(xué)化學(xué)系教授陳志行先生在90年代初開發(fā)了圍棋程序“手談”，曾經(jīng)獲得世界冠軍。

1.3 成熟階段

20世紀(jì)末期，國內(nèi)外有許多科研機(jī)構(gòu)和學(xué)者在計(jì)算機(jī)博弈領(lǐng)域進(jìn)行深入探討和實(shí)質(zhì)性的研究。隨著極大極小算法(minimax algorithm)[11]、α-β剪枝[9,11]、上限置信區(qū)間算法(upper confidence bound apply to tree，UCT)[13]、并行搜索算法[14]、遺傳算法[15]、人工神經(jīng)網(wǎng)絡(luò)[16]等技術(shù)日趨成熟，人工神經(jīng)網(wǎng)絡(luò)、類腦思維等科學(xué)也不斷取得突破性進(jìn)展，各種機(jī)器學(xué)習(xí)模型，例如支持向量機(jī)、 Boosting算法、最大熵方法等相繼被提出，計(jì)算機(jī)博弈研究進(jìn)入了一個(gè)前所未有的階段。

2006年，Hinton和他的學(xué)生在Science上發(fā)表了一篇關(guān)于用神經(jīng)網(wǎng)絡(luò)降低數(shù)據(jù)維數(shù)的論文[16]，開啟了深度學(xué)習(xí)在學(xué)術(shù)界的浪潮。2007年科學(xué)雜志評出的人類10大科學(xué)突破中，包括了加拿大阿爾波特大學(xué)研究人員歷時(shí)18年破解了國際跳棋(64)的研究成果，這是整個(gè)機(jī)器博弈發(fā)展史上的一個(gè)里程碑[5]。

2003年，臺(tái)灣交通大學(xué)吳毅成教授發(fā)明了六子棋 (connect 6)[ 17 ]，目前被認(rèn)為是最公平的棋類。之后，東北大學(xué)徐心和教授[ 18 ]和他的團(tuán)隊(duì)[19-21]研究開發(fā)了中國象棋軟件“棋天大圣”，具有挑戰(zhàn)國內(nèi)中國象棋頂級高手的實(shí)力；北郵劉知青[22-23]帶領(lǐng)學(xué)生開發(fā)的“本手(LINGO)”圍棋程序，能夠戰(zhàn)勝高水平業(yè)余圍棋選手；哈工大王軒[24-26]、南航夏正友[27-28]分別帶領(lǐng)學(xué)生開發(fā)了四國軍棋博弈系統(tǒng)，這些程序都表現(xiàn)出較高的智能水平。

1.4 飛躍階段

最近幾年，基于人工神經(jīng)網(wǎng)絡(luò)[3]取得了突破性的進(jìn)展。運(yùn)用該技術(shù)，成功地解決了計(jì)算機(jī)博弈領(lǐng)域中許多實(shí)際問題。

2012年6月，谷歌公司的Google Brain項(xiàng)目用并行計(jì)算平臺(tái)訓(xùn)練一種稱為“深度神經(jīng)網(wǎng)絡(luò)”(deep neural networks，DNN)的機(jī)器學(xué)習(xí)模型。2013年1月，百度宣布成立“深度學(xué)習(xí)研究所”(institue of deep learning，IDL)。在2015年10月5∶0擊敗了歐洲圍棋冠軍樊麾后，2016年1月，谷歌DeepMind團(tuán)隊(duì)在自然雜志(Nature)上發(fā)表封面論文稱，他們研發(fā)出基于神經(jīng)網(wǎng)絡(luò)進(jìn)行深度學(xué)習(xí)的人工智能圍棋程序AlphaGo，能夠在極其復(fù)雜的圍棋游戲中戰(zhàn)勝專家級人類選手[3]。2016年3月，AlphaGo又以4∶1戰(zhàn)勝世界圍棋冠軍李世石，在學(xué)術(shù)界產(chǎn)生了空前的影響，這標(biāo)志著計(jì)算機(jī)博弈技術(shù)取得重大成功，是計(jì)算機(jī)博弈發(fā)展史上新的躍遷。

2 賽事與學(xué)術(shù)交流

由國際機(jī)器博弈協(xié)會(huì)(International Computer Games Association，ICGA)組織的國際計(jì)算機(jī)博弈比賽(Computer Olympiad，CO)每年一屆，已經(jīng)有了30多年的歷史。比賽項(xiàng)目包括中國象棋、六子棋、亞馬遜棋、圍棋等，通過競賽促進(jìn)了世界范圍內(nèi)的計(jì)算機(jī)博弈技術(shù)的發(fā)展。同時(shí)，ICGA還每年組織學(xué)術(shù)研討會(huì)，并出版ICGA季刊[27,30-32]。

從1969年開始，國際人工智能聯(lián)合會(huì)議(International Joint Conference on Artificial Intelligence，IJCAI)每兩年舉行一次，IJCAI是人工智能研究人員最主要國際會(huì)議之一。通過學(xué)術(shù)交流，發(fā)表計(jì)算機(jī)博弈的最新研究成果[33-35]。

2006年8月，由中國人工智能學(xué)會(huì)首次主辦中國計(jì)算機(jī)博弈錦標(biāo)賽，至今已舉辦10屆。從2011年開始，由中國人工智能學(xué)會(huì)與教育部高等學(xué)校計(jì)算機(jī)類專業(yè)教學(xué)指導(dǎo)委員會(huì)共同主辦全國大學(xué)生計(jì)算機(jī)博弈大賽暨全國錦標(biāo)賽[36-37]，目前已舉辦6屆。這項(xiàng)賽事所設(shè)定的各項(xiàng)比賽，涉及計(jì)算機(jī)博弈相關(guān)的知識(shí)庫、博弈平臺(tái)[38]、搜索引擎、神經(jīng)網(wǎng)絡(luò)、機(jī)器學(xué)習(xí)與局面評估[39-40]等多種技術(shù)，吸引了越來越多的專家、學(xué)者與計(jì)算機(jī)博弈愛好者參與到計(jì)算機(jī)博弈相關(guān)研究中，為計(jì)算機(jī)博弈技術(shù)的交流與驗(yàn)證提供了一個(gè)公平、開放的平臺(tái)。目前，競賽項(xiàng)目涵蓋了多種類型的博弈：

1)按參與人數(shù)劃分，包括雙人博弈[41](如中國象棋、圍棋)和多人博弈(如二打一撲克[42])；

2)按參與人對他人了解程度劃分，包括完備信息博弈[43](如中國象棋、圍棋、六子棋、亞馬遜棋、蘇拉卡爾塔棋等)和非完全信息博弈[24,44](如幻影圍棋、軍棋、二打一撲克)；

3)按參與人之間有無合作劃分，包括合作博弈(如橋牌[45])與非合作博弈(如中國象棋)。

除了以上競賽，還有各種世界范圍內(nèi)的人機(jī)大戰(zhàn)活動(dòng)，這些競賽活動(dòng)極大地激發(fā)了人們的挑戰(zhàn)熱情和創(chuàng)新精神，為社會(huì)培養(yǎng)了大量的科技精英，在促進(jìn)了人工智能技術(shù)快速發(fā)展的同時(shí)，還產(chǎn)生了新的科研成果。

3 計(jì)算機(jī)博弈系統(tǒng)設(shè)計(jì)

計(jì)算機(jī)博弈系統(tǒng)是指在特定規(guī)則下具有博弈能力的智能系統(tǒng)。在設(shè)計(jì)系統(tǒng)時(shí)，需要考慮知識(shí)表示、著法產(chǎn)生、搜索與評估幾個(gè)方面。

典型的計(jì)算機(jī)博弈系統(tǒng)的核心架構(gòu)設(shè)計(jì)如圖1所示，可以劃分為博弈平臺(tái)和搜索引擎兩大模塊。其中，博弈平臺(tái)主要負(fù)責(zé)界面顯示、棋規(guī)判斷、行棋過程控制、信息傳遞等[38]，在其設(shè)計(jì)過程中，通?？紤]通用性、易用性、健壯性、藝術(shù)性；博弈引擎主要負(fù)責(zé)知識(shí)學(xué)習(xí)、開(或殘)局庫設(shè)計(jì)[20,46]、棋局評估、博弈樹搜索、著法生成等。

圖1 計(jì)算機(jī)博弈系統(tǒng)典型架構(gòu)Fig.1 Typical architecture of computer game system

相對整個(gè)計(jì)算機(jī)博弈系統(tǒng)而言，后端搜索引擎是整個(gè)系統(tǒng)的核心部分，它是決定博弈勝負(fù)的關(guān)鍵，在搜索引擎的開發(fā)過程中，除了考慮與博弈平臺(tái)的接口外，還要根據(jù)各個(gè)棋種的特點(diǎn)，選擇合適的搜索算法和評估函數(shù)[47-48]。

4 博弈樹搜索技術(shù)

4.1 博弈樹復(fù)雜度

博弈樹是由樹枝和節(jié)點(diǎn)構(gòu)成單向無環(huán)圖，如圖2所示。博弈樹的節(jié)點(diǎn)對應(yīng)于某一個(gè)棋局，其分支表示走一步棋；根部對應(yīng)于開始位置，其葉表示對弈到此結(jié)束。生成博弈著法的過程，對應(yīng)博弈樹的搜索與展開[49]。計(jì)算機(jī)博弈的過程是雙方輪流給出著法，使棋局向著對本方有利的方向發(fā)展，直至最后的勝利。

圖2 博弈樹示意圖Fig.2 Schematic diagram of game tree

搜索博弈樹的目的就是在假設(shè)雙方的走法都是最佳的情況下，找到從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的最佳路徑，找出當(dāng)前的最佳著法。

博弈樹中的每個(gè)葉節(jié)點(diǎn)，都可以用評估函數(shù)來對其優(yōu)劣進(jìn)行評分，該值對于博弈雙方都是最優(yōu)的。博弈樹的子樹在搜索完成之后會(huì)返回一個(gè)博弈值，該值對于該子樹是局部最優(yōu)解，但是對整個(gè)博弈樹來說并不一定是全局最優(yōu)解。

在計(jì)算機(jī)博弈研究中，求解過程中計(jì)算復(fù)雜性是個(gè)難以逾越的難題。對于NP-complete、PSPACE-complete及EXPTIME-complete等難解的問題，不必將大量的精力花費(fèi)在尋找問題的解析解上，而只能去尋求某種近似解。國內(nèi)外學(xué)者對計(jì)算機(jī)博弈的計(jì)算復(fù)雜性[50-51]進(jìn)行研究，證明了國際象棋和西洋跳棋屬于EXPTIME-complete問題，圍棋屬于PSPACE-hard問題，中國象棋屬于EXPTIME-complete問題[52]。

對于許多棋種而言，一棵完整博弈樹的規(guī)模非常龐大，可以達(dá)到相當(dāng)可觀的天文數(shù)字，表1中列出幾種知名棋種的復(fù)雜度[53]。

表1 幾種知名棋類的復(fù)雜度

顯然，把搜索樹修整到合理范圍內(nèi)，減少其搜索空間，能夠有效地進(jìn)行展開和遍歷搜索。

4.2 博弈樹搜索

以中國象棋、國際跳棋為代表的二人零和完備信息博弈，其搜索理論已經(jīng)很系統(tǒng)。其中極大極小算法[53]是最基本的搜索算法，它奠定了計(jì)算機(jī)博弈的理論基礎(chǔ)。以極大極小算法為基礎(chǔ)的博弈樹搜索算法，從搜索方向考慮，可以分為深度優(yōu)先搜索和寬度優(yōu)先搜索；從控制策略考慮，可以分為盲目搜索和啟發(fā)搜索；從搜索范圍考慮，可以分為窮盡搜索、裁剪搜索。

相對而言，寬度優(yōu)先搜索、窮盡搜索和盲目搜索算法時(shí)間和空間開銷巨大，難以做到很深的搜索。因此，在計(jì)算機(jī)博弈的實(shí)際應(yīng)用中，很少直接使用此類算法解決問題。

4.2.1 窮盡搜索

極大極小算法[54]是典型的窮盡搜索方法，通過它可以找到對于博弈雙方都是最優(yōu)的博弈值，但該算法對博弈樹的搜索是一種變性搜索，算法實(shí)現(xiàn)相對麻煩。

負(fù)極大值算法在極大極小算法基礎(chǔ)上進(jìn)行了改進(jìn)，把極小節(jié)點(diǎn)值(返回給搜索引擎的局面估值)取絕對值，這樣每次遞歸都選取最大值。

4.2.2 裁剪搜索

裁剪算法也稱剪枝算法，是計(jì)算機(jī)博弈中最常用的主流算法，它包括深度優(yōu)先的Alpha-Beta剪枝搜索[9]和以此為基礎(chǔ)改進(jìn)與增強(qiáng)的算法，如渴望窗口搜索(aspiration search)[55]、MTD(f)(memory-enhancedtestdriverwithfandn)搜索[56]等。在具體應(yīng)用中，合理地交叉使用各種搜索方法，可以具有更高的效率[56]。

1)Alpha-Beta剪枝[9,33]

Alpha-Beta剪枝是在極大極小算法基礎(chǔ)上的改進(jìn)算法，是其他剪枝算法的基礎(chǔ)。目前，多數(shù)博弈程序都采用負(fù)極大值形式的Alpha-Beta搜索算法。為保證Alpha-Beta搜索算法的效率，需要調(diào)整樹的結(jié)構(gòu)，即對搜索節(jié)點(diǎn)排序，確保盡早剪枝。

2)渴望搜索[54-55]

渴望搜索是在Alpha-Beta搜索算法基礎(chǔ)上，縮小搜索范圍的改進(jìn)算法?？释阉鲝囊婚_始就使用小的窗口，從而在搜索之初，就可以進(jìn)行大量的剪枝。通常，渴望搜索與遍歷深化技術(shù)結(jié)合使用，以提高搜索性能。

3)MTD(f)搜索[56]

MTD(f)搜索實(shí)際上就是不斷應(yīng)用零窗口的Alpha-Beta搜索，縮小上界和下界，并移動(dòng)初始值使其接近最優(yōu)著法。MTD(f)算法簡單高效，在國際象棋、國際跳棋等博弈程序里，MTD(f) 算法平均表現(xiàn)出色。

此外，還有各種在Alpha-Beta搜索基礎(chǔ)上優(yōu)化的算法，例如，有學(xué)者提出在博弈樹同層結(jié)點(diǎn)中，用廣度優(yōu)先搜索，接力式空窗探測，平均搜索效率高于MTD(f)搜索[57]。通常，裁剪算法需要與置換表技術(shù)相結(jié)合，以減少博弈樹的規(guī)模，提高搜索效率。

4.2.3 置換表[58]技術(shù)

置換表是一個(gè)大的直接訪問表，用來存儲(chǔ)已經(jīng)搜索過結(jié)點(diǎn)(或者子樹)的結(jié)果，下次搜索遇到時(shí)直接運(yùn)用。置換表的構(gòu)造，一般使用Hash表和ZobristHash技術(shù)來實(shí)現(xiàn)。

合理使用置換表，可以提高搜索效率，當(dāng)博弈樹的深度很大時(shí)，置換表對內(nèi)存空間要求巨大。通常的對策是對置換表分配有限大小，并采用散列方式管理存取。具體應(yīng)用到各個(gè)棋種中時(shí)，還要根據(jù)實(shí)際局面的節(jié)點(diǎn)類型，進(jìn)行處理。

4.2.4 啟發(fā)式算法

“啟發(fā)”(Heuristic)是指通過排序讓Alpha-Beta剪枝的搜索樹盡可能地接近最小樹，優(yōu)先搜索好的著法。啟發(fā)通常有置換表啟發(fā)、歷史啟發(fā)和殺手啟發(fā)等常用的算法。

1)置換表啟發(fā)[58-59]

置換表啟發(fā)是置換表與Alpha-Beta剪枝算法相結(jié)合的產(chǎn)物。在中國象棋等棋種中，通過引進(jìn)置換表啟發(fā)技術(shù)來增強(qiáng)搜索效率。

2)歷史啟發(fā)[60]

歷史啟發(fā)也是迎合alpha-beta搜索對節(jié)點(diǎn)排列順序敏感的特點(diǎn)來提高剪枝效率的。它通過維護(hù)著法歷史，每當(dāng)遇到好的著法，就給其歷史得分一個(gè)相應(yīng)的增量，使其具有更高的優(yōu)先被搜索的權(quán)利。

歷史啟發(fā)是一種基于經(jīng)驗(yàn)的擇序標(biāo)準(zhǔn)，它克服了基于知識(shí)擇序存在的知識(shí)不足的缺點(diǎn)，使得算法的擇序具有很強(qiáng)的動(dòng)態(tài)適應(yīng)性。

3)殺手啟發(fā)[61]

殺手啟發(fā)可以看作是歷史啟發(fā)的特例。它把同層中引發(fā)剪枝最多的節(jié)點(diǎn)稱為殺手，當(dāng)下次搜索到同一層時(shí)，如果殺手移動(dòng)是合法的話，就優(yōu)先搜索殺手。殺手啟發(fā)可以對著法進(jìn)行動(dòng)態(tài)重排序，且提高了置換表的使用效率。

4.2.5 迭代深化[62]

迭代深化也稱為遍歷深化，是一種常用的蠻力搜索機(jī)制，經(jīng)常使用在深度優(yōu)先搜索中。迭代深化最初是作為控制時(shí)間的機(jī)制而提出的，通過對博弈樹進(jìn)行多次遍歷，并逐漸提高搜索深度，一直到指定的時(shí)間停止。

迭代深化利用Alpha-Beta剪枝算法對子節(jié)點(diǎn)排序敏感的特點(diǎn)，使用上次迭代后得到的博弈值，作為當(dāng)前迭代的搜索窗口估值，以此為啟發(fā)式信息計(jì)算當(dāng)前迭代的博弈值。另外，它利用時(shí)間控制遍歷次數(shù)，只要時(shí)間一到，搜索立即停止。在關(guān)鍵的開局和殘局，由于分支較少，可以進(jìn)行較深層次的搜索。Alpha-Beta剪枝經(jīng)過一系列技術(shù)如置換表、歷史啟發(fā)、迭代深化等增強(qiáng)后，其性能可大幅提高。

4.2.6 最佳優(yōu)先算法

最佳優(yōu)先的搜索算法，不受節(jié)點(diǎn)排序的影響，其搜索空間小于深度優(yōu)先的最小樹，理論上應(yīng)該優(yōu)于深度優(yōu)先。實(shí)際上，最佳優(yōu)先算法仍處于理論研究階段。最佳優(yōu)先算法分為兩類：采用極大極小算法取值的SSS*[63-64]算法和DUAL*算法，不采用極大極小方法取值的B*[65]和PB*[66]算法。

1)SSS*和DUAL*算法[63-64]

SSS*和DUAL*算法都屬于狀態(tài)空間搜索(StateSpaceSearch)，把極大極小樹看成狀態(tài)圖，在不同的分支上展開多條路徑，并且維護(hù)一個(gè)關(guān)于狀態(tài)圖的全局信息表。這兩種算法是兩個(gè)操作相反的過程，前者在搜索深度為偶數(shù)的極大極小搜索中表現(xiàn)較佳，后者則在深度為奇數(shù)搜索中較佳。

SSS*和DUAL*算法都過于復(fù)雜，難于理解，且時(shí)間和空間開銷較大，在計(jì)算機(jī)博弈中實(shí)際應(yīng)用較少。

2)B*和PB*算法[65-66]

B*算法用一個(gè)樂觀值和一個(gè)悲觀值來評價(jià)節(jié)點(diǎn)。當(dāng)根節(jié)點(diǎn)的一個(gè)孩子的悲觀值不比所有其他節(jié)點(diǎn)的樂觀值差的時(shí)候，B*算法就結(jié)束了。算法搜索控制的關(guān)鍵是盡快找到終止條件。由于它對局面估值的依賴性太強(qiáng)，估值的可信度將直接影響最終結(jié)果。

PB*算法就是基于概率的B*算法，這個(gè)算法對概率的準(zhǔn)確估計(jì)比較敏感，實(shí)現(xiàn)困難。

4.2.7 隨機(jī)搜索

隨機(jī)搜索有兩種算法：拉斯維加斯算法和蒙特卡羅算法。采樣越多，前者越有機(jī)會(huì)找到最優(yōu)解，后者則越接近最優(yōu)解。

通常，要根據(jù)問題的約束條件來確定隨機(jī)算法，如果對采樣沒有限制，但必須給出最優(yōu)解，則采用拉斯維加斯算法。反之，如果要求在有限采樣內(nèi)求解，但不要求是最優(yōu)解，則采用蒙特卡羅算法。

計(jì)算機(jī)博弈中，每步著法的運(yùn)算時(shí)間、堆?？臻g都是有限的，且僅要求局部優(yōu)解，適合采用蒙特卡羅算法。由于非完備信息博弈也具有不確定性博弈的一些特征，所以蒙特卡羅算法也適用于非完備信息博弈。

1)蒙特卡羅搜索(MCTS，MonteCarloTreeSearch)[67-70]

在人工智能的問題中，蒙特卡羅搜索是一種最優(yōu)決策方法，它結(jié)合了隨機(jī)模擬的一般性和樹搜索的準(zhǔn)確性。由于海量搜索空間、評估棋局和落子行為的難度，圍棋長期以來被視為人工智能領(lǐng)域最具挑戰(zhàn)的經(jīng)典游戲。近年來，MCTS在類似計(jì)算機(jī)圍棋等完備信息博弈、多人博弈以及其他隨機(jī)類博弈難題上的成功應(yīng)用而受到快速關(guān)注[71]。理論上，MCTS可以被用在以{狀態(tài)，行動(dòng)}定義并用模擬預(yù)測輸出結(jié)果的任何領(lǐng)域。

基本的MCTS算法根據(jù)模擬的輸出結(jié)果，按照節(jié)點(diǎn)構(gòu)造博弈樹，其過程如圖3所示，包括路徑選擇(Selection)、節(jié)點(diǎn)擴(kuò)展(Expansion)、模擬實(shí)驗(yàn)(Simulation)、反向傳播(Backpropagation)4個(gè)步驟。

圖3 構(gòu)造MCTS博弈樹的過程Fig.3 Process of constructing the MCTS game tree

MCTS算法適用于有較大分支因子的博弈程序，如AlphaGo就是采用MCTS算法進(jìn)行搜索[3]。

2)UCT算法[13,25]

UCT算法，即上限置信區(qū)間算法，是一種基于MCTS發(fā)展的博弈樹搜索算法，該算法通過擴(kuò)展UCB(upperconfidencebound)到極大極小樹搜索，將MCTS方法與UCB公式結(jié)合。

UCB計(jì)算方法如公式1所示，在向下遍歷博弈樹時(shí)，通過選擇最大化該值來實(shí)現(xiàn)節(jié)點(diǎn)的選擇。

(1)

式中：vi是節(jié)點(diǎn)i估計(jì)的值，ni是節(jié)點(diǎn)i被訪問的次數(shù)，而N是其父節(jié)點(diǎn)已被訪問的總次數(shù)，C是可調(diào)參數(shù)。相對于傳統(tǒng)的搜索算法，UCT時(shí)間可控，具有更好的魯棒性，可以非對稱動(dòng)態(tài)擴(kuò)展博弈樹，在超大規(guī)模博弈樹的搜索過程中，表現(xiàn)出時(shí)間和空間方面的優(yōu)勢。目前，UCT在搜索規(guī)模較大的完備信息博弈、復(fù)雜的多人博弈、非完備信息博弈以及隨機(jī)類博弈項(xiàng)目中，表現(xiàn)出色[71]。

5 局面評估

在計(jì)算機(jī)博弈系統(tǒng)中，對博弈局面評估得越全面、越準(zhǔn)確，獲勝的機(jī)率就會(huì)越高。但是，博弈有個(gè)很重要的約束條件就是時(shí)間。評估中考慮的問題越全面細(xì)致，則耗費(fèi)的時(shí)間就越多，搜索的深度和速度必然受到影響。另外，隨著搜索深度加深，信息處理量也會(huì)大幅提升。

設(shè)計(jì)評估函數(shù)需要考慮諸多因素，在完全信息博弈中雙方的子力、領(lǐng)地、位置、空間、機(jī)動(dòng)性、拍節(jié)、威脅、形狀、圖案都可以作為評估參數(shù)，非完備信息博弈中除了己方已知參數(shù)外，還要猜測對手的情況，并通過量化后加權(quán)組合而成。

國內(nèi)外有不少學(xué)者在計(jì)算機(jī)博弈評估方面做了大量深入研究[72]。針對不同棋種的特點(diǎn)，學(xué)者們提出了各種不同的方式進(jìn)行評估與優(yōu)化：通過博弈記錄來評估博弈樹搜索[73]；針對六子棋應(yīng)用遺傳算法進(jìn)行尋優(yōu)處理，優(yōu)化機(jī)器博弈評估函數(shù)[40]；在中國象棋里，把自適應(yīng)遺傳算法引入評估函數(shù)中，通過錦標(biāo)賽算法對評估函數(shù)中的參數(shù)組合進(jìn)行自動(dòng)調(diào)整和優(yōu)化[19]；根據(jù)棋子的數(shù)量、移動(dòng)范圍、攻擊范圍、子力攻擊力、盤面分值和占弧價(jià)值等對蘇拉卡爾塔棋局面評估函數(shù)進(jìn)行了研究[40]；根據(jù)亞馬遜棋領(lǐng)地、位置和機(jī)動(dòng)性等特征在不同階段的重要程度及權(quán)重值，給出一個(gè)分階段的評估函數(shù)[47,74]。

提高計(jì)算機(jī)博弈能力不能單純依靠加大搜索深度，還需要將必要的相關(guān)博弈知識(shí)引入到相應(yīng)的博弈搜索中，只有協(xié)調(diào)搜索算法與評估函數(shù)，博弈系統(tǒng)才能發(fā)揮有效作用。

6 綜合優(yōu)化技術(shù)

計(jì)算機(jī)博弈中，目前應(yīng)用較多的綜合優(yōu)化技術(shù)主要有并行計(jì)算、遺傳算法和基于神經(jīng)網(wǎng)絡(luò)的深度學(xué)習(xí)。

6.1 并行計(jì)算

并行計(jì)算[14,75]是為了提高計(jì)算速度，把博弈樹動(dòng)態(tài)分開，發(fā)揮計(jì)算機(jī)多CPU強(qiáng)大的并行處理能力，同時(shí)執(zhí)行多個(gè)指令的算法。它不裁剪和縮小博弈樹的規(guī)模，通過提高搜索速度，而進(jìn)行優(yōu)化系統(tǒng)。

并行計(jì)算有兩種體系，單機(jī)體系SMP(SymmetricMultiprocessor)和分布式體系Cluster(計(jì)算機(jī)集群)，對應(yīng)多線程并行和多機(jī)并行。兩者最大的區(qū)別是，前者可以共享存儲(chǔ)器(并且共享同一地址的存儲(chǔ)單元)，后者則必須通過網(wǎng)絡(luò)來交換數(shù)據(jù)。由于博弈搜索通常需要用到置換表，所以適合以SMP的方式多線程并行處理，但隨著大數(shù)據(jù)、云計(jì)算等技術(shù)的成熟與完善，計(jì)算機(jī)集群技術(shù)將被越來越多地運(yùn)用到計(jì)算機(jī)博弈中。

6.2 遺傳算法

遺傳算法[15]是人工智能領(lǐng)域的關(guān)鍵技術(shù)，它是一種非數(shù)值、并行、隨機(jī)優(yōu)化、搜索啟發(fā)式的算法，通過模擬自然進(jìn)化過程隨機(jī)化搜索最優(yōu)解。它采用概率化的尋優(yōu)方法，能自動(dòng)獲取和指導(dǎo)優(yōu)化的搜索空間，自適應(yīng)地調(diào)整搜索方向，不需要確定的規(guī)則，同時(shí)具有內(nèi)在的隱并行性和更好的全局尋優(yōu)能力。

遺傳算法是解決搜索問題的一種通用算法，在計(jì)算機(jī)博弈中，遺傳算法通常被用于搜索、自適應(yīng)調(diào)整和優(yōu)化局面評估參數(shù)。它的基本思想是將博弈樹看作遺傳操作的種群，博弈樹中由根節(jié)點(diǎn)到葉子節(jié)點(diǎn)組成的所有子樹為種群中的個(gè)體。根據(jù)優(yōu)化目標(biāo)設(shè)計(jì)評估函數(shù)，計(jì)算種群中每個(gè)個(gè)體的適應(yīng)度函數(shù)值，依據(jù)適應(yīng)度函數(shù)值的大小確定初始種群，讓適應(yīng)性強(qiáng)(適應(yīng)度函數(shù)值大)的個(gè)體獲得較多的交叉、遺傳機(jī)會(huì)，生成新的子代個(gè)體，通過反復(fù)迭代，可得到滿意解。

采用遺傳算法優(yōu)化局面估值時(shí)，可根據(jù)博弈程序與其他程序?qū)牡慕Y(jié)果，檢驗(yàn)?zāi)骋唤M參數(shù)獲勝的機(jī)率。經(jīng)過多次試驗(yàn)，通?？梢哉业捷^好的估值參數(shù)。傳統(tǒng)的算法一般只能維護(hù)一組最優(yōu)解，遺傳算法可以同時(shí)維護(hù)多組最優(yōu)解。在實(shí)踐中，遺傳算法被引入了中國象棋、國際象棋、亞馬遜等棋搜索與評估優(yōu)化中，效果還是很明顯的[19]。

6.3 深度學(xué)習(xí)

深度學(xué)習(xí)是基于多層網(wǎng)絡(luò)結(jié)構(gòu)的一種機(jī)器學(xué)習(xí)方法，它逐層提取抽象特征，通過多層非線性傳輸，完成復(fù)雜的目標(biāo)函數(shù)系統(tǒng)逼近。深度學(xué)習(xí)領(lǐng)域典型的網(wǎng)絡(luò)模型包括卷積神經(jīng)網(wǎng)絡(luò)(convolutionalneuralnetworks，CNN)、深層玻爾茲曼機(jī)(deepboltzmannmachine，DBM)和堆疊自動(dòng)編碼器(stackedauto-encoder，SAE)等[76]。

近幾年，基于人工神經(jīng)網(wǎng)絡(luò)的深度學(xué)習(xí)技術(shù)逐漸被應(yīng)用于計(jì)算機(jī)博弈中[3,29]，人工智能圍棋程序AlphaGo是其典型代表[3]。AlphaGo成功的關(guān)鍵在于擁有兩個(gè)大腦——落子選擇器(movepicker)和棋局評估器(positionevaluator)。分別基于兩種不同的深度神經(jīng)網(wǎng)絡(luò)——策略網(wǎng)絡(luò)(policynetwork)和價(jià)值網(wǎng)絡(luò)(valuenetwork)，如圖4所示。前者用于學(xué)習(xí)高水平棋手的棋譜，獲得如何在盤面落子的棋感；后者通過機(jī)器的增強(qiáng)型學(xué)習(xí)，獲得形勢判斷的棋感。這兩個(gè)棋感通過蒙特卡羅搜索的技術(shù)進(jìn)行驗(yàn)證，使AlphaGo實(shí)現(xiàn)了技術(shù)突破。

盡管深度學(xué)習(xí)技術(shù)在圍棋方面取得了前所未有的成功，但在拓展應(yīng)用方面，如何合理利用深度學(xué)習(xí)方法來增強(qiáng)傳統(tǒng)學(xué)習(xí)算法的性能，提升計(jì)算機(jī)博弈水平，仍是今后研究的重點(diǎn)。

圖4 AlphaGo神經(jīng)網(wǎng)絡(luò)體系結(jié)構(gòu)原理圖Fig.4 Schematic representation of the neural network architecture used in AlphaGo

7 面臨的問題與展望

近年來，計(jì)算機(jī)博弈給人工智能帶來了很多重要的方法和理論，在二人零和完備信息博弈研究方面，其知識(shí)結(jié)構(gòu)系統(tǒng)層次清晰，已經(jīng)取得了許多驚人的成果，其中，關(guān)于基于神經(jīng)網(wǎng)絡(luò)深度學(xué)習(xí)技術(shù)的研究與運(yùn)用，已經(jīng)達(dá)到新的高度。在中國象棋、圍棋等完全信息的計(jì)算機(jī)博弈中，盡管狀態(tài)空間和搜索樹復(fù)雜度都較大，但經(jīng)過大量學(xué)習(xí)與訓(xùn)練，結(jié)合大規(guī)模搜索算法，計(jì)算機(jī)占盡優(yōu)勢[78]。

另一個(gè)方面，對于軍棋、麻將、橋牌、撲克等非完備信息博弈，以及具有模糊性和隨機(jī)性的不確定性博弈，雖然在基于案例的策略研究方面有了一定進(jìn)展，但因其相關(guān)理論研究還不成熟，相應(yīng)的程序智力有限，仍難以戰(zhàn)勝人類真正的高手。因此，在非完備信息和不確定性機(jī)器博弈方面，具有高效學(xué)習(xí)與抽象思維能力的博弈技術(shù)還有待進(jìn)一步研究。另外，在計(jì)算機(jī)博弈平臺(tái)方面的研究投入相對較少，對計(jì)算機(jī)博弈技術(shù)的發(fā)展也有所制約。

可以預(yù)見，在不遠(yuǎn)的將來，計(jì)算機(jī)博弈技術(shù)將融入各個(gè)領(lǐng)域的應(yīng)用中，具體體現(xiàn)在如下幾點(diǎn)：

1)計(jì)算機(jī)博弈研究的內(nèi)容將不斷拓寬，處理的問題復(fù)雜程度越來越高，信息量將越來越大。為解決某類特定問題，技術(shù)方法將集成化，計(jì)算機(jī)博弈技術(shù)將與并行計(jì)算、大數(shù)據(jù)技術(shù)等相關(guān)技術(shù)結(jié)合。

2)計(jì)算機(jī)博弈軟件與硬件的結(jié)合越來越密切，固化博弈系統(tǒng)的智能硬件產(chǎn)品將越來越多地出現(xiàn)在人們的生活中，典型的應(yīng)用包括：有博弈思維能力機(jī)器人、智能決策控制系統(tǒng)的無人駕駛汽車和無人機(jī)。

3)計(jì)算機(jī)博弈技術(shù)將與其他學(xué)科進(jìn)一步融合，越來越緊密地應(yīng)用經(jīng)濟(jì)、生活、軍事等領(lǐng)域，注重實(shí)際工程應(yīng)用，解決實(shí)際問題。在虛擬現(xiàn)實(shí)仿真方面，特別是游戲與教育方面擁有廣闊的應(yīng)用前景。

4)計(jì)算機(jī)博弈技術(shù)將呈現(xiàn)高度智能化趨勢，通過與遺傳算法、人工神經(jīng)網(wǎng)絡(luò)、類腦思維等人工智能技術(shù)進(jìn)一步融合，類似基于神經(jīng)網(wǎng)絡(luò)深度學(xué)習(xí)的智能技術(shù)將大量涌現(xiàn)，使得計(jì)算機(jī)博弈程序的類腦智能越來越高。

5)合理拓展現(xiàn)有的博弈技術(shù)，深入研究更加智能的普適算法，構(gòu)建一個(gè)通用的計(jì)算機(jī)博弈系統(tǒng)，也將成為未來計(jì)算機(jī)博弈研究的重點(diǎn)。

8 結(jié)束語

伴隨著人工智能科學(xué)發(fā)展的60周年，計(jì)算機(jī)博弈也經(jīng)歷了起步、發(fā)展、成熟、飛躍4個(gè)階段。依托各種形式的競賽，極大地促進(jìn)了學(xué)術(shù)交流，檢驗(yàn)了新技術(shù)，推動(dòng)了博弈的研究與發(fā)展。當(dāng)前完備信息博弈技術(shù)相對比較成熟，非完備信息博弈和隨機(jī)類博弈技術(shù)還需進(jìn)一步發(fā)展。深度學(xué)習(xí)算法在AlphaGo圍棋計(jì)算機(jī)博弈中的成功應(yīng)用，引發(fā)了世界范圍內(nèi)對人工智能技術(shù)的高度關(guān)注，調(diào)動(dòng)了更多的專家學(xué)者開展深入研究的積極性。盡管在計(jì)算機(jī)博弈領(lǐng)域還存在著各種各樣的問題，許多工作還需要向更廣領(lǐng)域和更深層次推進(jìn)，但是隨著研究人員的不斷增加以及計(jì)算機(jī)博弈技術(shù)在各個(gè)領(lǐng)域的廣泛應(yīng)用，將會(huì)產(chǎn)生越來越多的研究成果。計(jì)算機(jī)博弈是一個(gè)頗有發(fā)展前途的研究領(lǐng)域。

[1]徐心和, 鄧志立, 王驕, 等. 機(jī)器博弈研究面臨的各種挑戰(zhàn)[J]. 智能系統(tǒng)學(xué)報(bào), 2008, 3(4): 288-293.XUXinhe,DENGZhili,WANGJiao,etal.Challengingissuesfacingcomputergameresearch[J].CAAItransactionsonintelligentsystems, 2008, 3(4): 288-293.

[2]徐心和. 計(jì)算機(jī)博弈——對于人類思維的挑戰(zhàn)[J]. 中國科技博覽, 2009(34): 194-195.

[3]SILVERD,HUANGAjia,MADDISONCJ,etal.MasteringthegameofGowithdeepneuralnetworksandtreesearch[J].Nature, 2016, 529(7587): 484-489.

[4]BENCH-CAPONTJM,DUNNEPE.Argumentationinartificialintelligence[J].Artificialintelligence, 2007, 171(10/15): 619-641.

[5]PENNISIE.Breakthroughoftheyear:humangeneticvariation[J].Science, 2007, 318(5858): 1842-1843.

[6]SHANNONCE.Programmingacomputerforplayingchess[J].Philosophicalmagazine, 1950, 41(314): 2562275.

[7]BERNSTEINA,ARBUCKLET,DEVROBERTSM,etal.AchessplayingprogramfortheIBM704[C]//ProceedingsoftheMay6-8, 1958,WesternJointComputerConference:ContrastsinComputers.NewYork,NY,USA:ACM, 1958: 157-159.

[8]SAMUELAL.Somestudiesinmachinelearningusingthegameofcheckers.II:recentprogress[J].IBMjournalofresearchanddevelopment, 1967, 11(6): 601-617.

[9]FULLERSH,GASCHNIGJG,GILLOGLYJJ.Analysisofthealpha-betapruningalgorithm[R].Carnegie:CarnegieMellonUniversity, 1973.

[10]KORFRE.Depth-firstiterative-deepening:anoptimaladmissibletreesearch[J].Artificialintelligence, 1985, 27(1): 97-109.

[11]ROIZENI,PEARLJ.Aminimaxalgorithmbetterthanalpha-beta?YesandNo[J].Artificialintelligence, 1983, 21(1/2): 199-220.

[12]RUMELHARTDE,HINTONGE,WILLIAMSRJ.Learningrepresentationsbyback-propagatingerrors[J].Nature, 1986, 323(6088): 533-536.

[13]GELLYS,SILVERD.CombiningonlineandofflineknowledgeinUCT[C]//Proceedingsofthe24thInternationalConferenceonMachineLearning.NewYork,USA:ACM, 2007: 273-280.

[14]李之棠, 陳華民. 博弈樹并行搜索算法[J]. 小型微型計(jì)算機(jī)系統(tǒng), 1998, 19(10): 53-56.LIZhitang,CHENHuamin.Parallelgame-treesearch[J].Mini-microsystems, 1998, 19(10): 53-56.

[15]DAVID-TABIBIO,KOPPELM,NETANYAHUNS.Geneticalgorithmsforautomaticsearchtuning[J].ICGAjournal, 2010, 33(2): 67-79.

[16]HINTONGE,SALAKHUTDINOVRR.Reducingthedimensionalityofdatawithneuralnetworks[J].Science, 2006, 313(5786): 504-507.

[17]WUIC,CHANGHC.Threat-basedproofsearchforConnect6[R].Taiwan,China:NationalChiaoTungUniversity, 2006.

[18]徐心和, 王驕. 中國象棋計(jì)算機(jī)博弈關(guān)鍵技術(shù)分析[J]. 小型微型計(jì)算機(jī)系統(tǒng), 2006, 27(6): 961-969.XUXinhe,WANGJiao.KeytechnologiesanalysisofChinesechesscomputergame[J].Mini-microsystems, 2006, 27(6): 961-969.

[19]王驕, 王濤, 羅艷紅, 等. 中國象棋計(jì)算機(jī)博弈系統(tǒng)評估函數(shù)的自適應(yīng)遺傳算法實(shí)現(xiàn)[J]. 東北大學(xué)學(xué)報(bào): 自然科學(xué)版, 2005, 26(10): 949-952.WANGJiao,WANGTao,LUOYanhong,etal.ImplementationofadaptivegeneticalgorithmofevaluationfunctioninChinesechesscomputergamesystem[J].Journalofnortheasternuniversity:naturalscience, 2005, 26(10): 949-952.

[20]魏欽剛, 王驕, 徐心和, 等. 中國象棋計(jì)算機(jī)博弈開局庫研究與設(shè)計(jì)[J]. 智能系統(tǒng)學(xué)報(bào), 2007, 2(1): 85-89.WEIQingang,WANGJiao,XUXinhe,etal.Astudyanddesignofopening-bookofcomputerChineseChess[J].CAAItransactionsonintelligentsystems, 2007, 2(1): 85-89.

[21]徐長明, 南曉斐, 王驕, 等. 中國象棋機(jī)器博弈的時(shí)間自適應(yīng)分配策略研究[J]. 智能系統(tǒng)學(xué)報(bào), 2006, 1(2): 39-43.XUChangming,NANXiaofei,WANGJiao,etal.AdaptivetimeallocationstrategyincomputergameofChineseChess[J].CAAItransactionsonintelligentsystems, 2006, 1(2): 39-43.

[22]LIUZhiqing,DOUQing.AutomaticpatternacquisitionfromgamerecordsinGO[J].ThejournalofChinauniversitiesofpostsandtelecommunications, 2007, 14(1): 100-105.

[23]LIUZhiqing,DOUQing,LIWenhong,etal.AutomaticacquisitionofpatterncollocationsinGO[J].ThejournalofChinauniversitiesofpostsandtelecommunications, 2008, 15(1): 61-67.

[24]馬驍, 王軒, 王曉龍. 一類非完備信息博弈的信息模型[J]. 計(jì)算機(jī)研究與發(fā)展, 2010, 47(12): 2100-2109.MAXiao,WANGXuan,WANGXiaolong.Theinformationmodelforaclassofimperfectinformationgame[J].Journalofcomputerresearchanddevelopment, 2010, 47(12): 2100-2109.

[25]ZHANGJiajia,WANGXuan,LINJing,etal.UCTalgorithminimperfectinformationmulti-playermilitarychessgame[C]//Proceedingsofthe11thJointConferenceonInformationSciences.AtlantisPress, 2008: 1-9.

[26]WANGX,XUZhaoyang,MAX.TD(Λ)optimizationofimperfectinformationgame’sevaluationfunction[R].Japan:WCCGC, 2007.

[27]XIAZhengyou,ZHUYongping,LUHui.UsingtheloopybeliefpropagationinSiguo[J].ICGAjournal, 2007, 30(4): 209-220.

[28]XIAZhengyou,ZHUYongping,LUHui.Evaluationfunctionforsiguogamebasedontwoattitudes[C]//ProceedingsoftheThirdInternationalConferenceonFuzzySystemsandKnowledgeDiscovery.BerlinHeidelberg:Springer, 2006: 1322-1331.

[29]BENGIOY,LAMBLINP,POPOVICID,etal.Greedylayer-wisetrainingofdeepnetworks[M]//SCH?LKOPFB,PLATTJ,HOFMANNT.AdvancesinNeuralInformationProcessingSystems,vol19.Cambridge:MITPress, 2007: 153-160.

[30]COULOMR.Computing“Eloratings”ofmovepatternsinthegameofgo[J].ICGAjournal, 2007, 30(4): 198-208.

[31]FERREIRADR.Determiningthestrengthofchessplayersbasedonactualplay[J].ICGAjournal, 2012, 35(1): 3-19.

[32]NIJSSENJAM,WINANDSMHM.Searchpoliciesinmulti-playergames1[J].ICGAjournal, 2013, 36(1): 3-21.

[33]LEIFKERDB,KANALLN.AhybridSSS*/Alpha-Betaalgorithmforparallelsearchofgametrees[C]//Proceedingsofthe9thInternationalJointConferenceonArtificialIntelligence.SanFrancisco,CA,USA:ACM, 1985, 2: 1044-1046.

[34]PLAATA,SCHAEFFERJ,PIJLSW,etal.Best-firstfixed-depthgame-treesearchinpractice[C]//Proceedingsofthe14thInternationalJointConferenceonArtificialIntelligence.SanFrancisco,CA,USA:ACM, 1995, 1: 273-279.

[35]BURNSE,LEMONSS,ZHOURong,etal.Best-firstheuristicsearchformulti-coremachines[C]//Proceedingsofthe21stInternationalJontConferenceonArtificalIntelligence.SanFrancisco,CA,USA:ACM, 2009: 449-455.

[36]王驕, 徐心和. 計(jì)算機(jī)博弈: 人工智能的前沿領(lǐng)域——全國大學(xué)生計(jì)算機(jī)博弈大賽[J]. 計(jì)算機(jī)教育, 2012(7): 14-18.

[37]邱虹坤. 全國計(jì)算機(jī)博弈大賽網(wǎng)站[EB/OL]. [2016-04-22]. 2013.http://www.caaigames.net.

[38]張利群. 實(shí)現(xiàn)蘇拉卡爾塔棋網(wǎng)絡(luò)博弈平臺(tái)的吃子算法[J]. 計(jì)算機(jī)工程與應(yīng)用, 2016, 52(7): 62-66.ZHANGLiqun.RealizationofcapturealgorithmaboutSurakartachessnetworkbattleplatformincomputergame[J].Computerengineeringandapplications, 2016, 52(7): 62-66.

[39]張小川, 陳光年, 張世強(qiáng), 等. 六子棋博弈的評估函數(shù)[J]. 重慶理工大學(xué)學(xué)報(bào): 自然科學(xué)版, 2010, 24(2): 64-68.ZHANGXiaochuan,CHENGuangnian,ZHANGShiqiang,etal.Researchonevaluationfunctionsforcomputergameofconnect6[J].JournalofChongqinguniversityoftechnology:naturalscience, 2010, 24(2): 64-68.

[40]李淑琴, 李靜波, 韓裕華, 等. 蘇拉卡爾塔博弈系統(tǒng)中評估函數(shù)的研究[J]. 北京信息科技大學(xué)學(xué)報(bào), 2012, 27(6): 42-45, 61.LIShuqin,LIJingbo,HANYuhua,etal.TheassessmentfunctionintheSurakartagamesystem[J].JournalofBeijinginformationscienceandtechnologyuniversity, 2012, 27(6): 42-45, 61.

[41]TANGPingzhong,LINFangzhen.Discoveringtheoremsingametheory:two-persongameswithuniquepureNashequilibriumpayoffs[J].Artificialintelligence, 2011, 175(14/15): 2010-2020.

[42]RUBINJ,WATSONI.Case-basedstrategiesincomputerpoker[J].AIcommunications, 2012, 25(1): 19-48.

[43]FLESCHJ,KUIPERSJ,SCHOENMAKERSG,etal.Subgame-perfectioninfreetransitiongames[J].Europeanjournalofoperationalresearch, 2013, 228(1): 201-207.

[44]GILPINA,SANDHOLMT.Losslessabstractionofimperfectinformationgames[J].JournaloftheACM, 2007, 54(5): 25.

[45]何大華, 陳傳波. 關(guān)于橋牌的取勝策略[J]. 華中科技大學(xué)學(xué)報(bào): 自然科學(xué)版, 2004, 32(7): 13-15.HEDahua,CHENChuanbo.Thestrategyforwinningbridgegame[J].JournalofHuazhonguniversityofscience&technology:naturescienceedition, 2004, 32(7): 13-15.

[46]CHENBonian,LIUPangfeng,HSUSC,etal.AggregatingconsistentendgameknowledgeinChineseChess[J].Knowledge-basedsystems, 2012, 34: 34-42.

[47]郭琴琴, 李淑琴, 包華. 亞馬遜棋機(jī)器博弈系統(tǒng)中評估函數(shù)的研究[J]. 計(jì)算機(jī)工程與應(yīng)用, 2012, 48(34): 50-54.GUOQinqin,LIShuqin,BAOHua.ResearchonevaluationfunctioncomputergameofAmazon[J].Computerengineeringandapplications, 2012, 48(34): 50-54.

[48]SCHADDMPD,WINANDSMHM.Bestreplysearchformultiplayergames[J].IEEEtransactionsoncomputationalintelligenceandAIingames, 2011, 3(1): 57-66.

[49]李學(xué)俊, 王小龍, 吳蕾, 等. 六子棋中基于局部“路”掃描方式的博弈樹生成算法[J]. 智能系統(tǒng)學(xué)報(bào), 2015, 10(2): 267-272.LIXuejun,WANGXiaolong,WULei,etal.Gametreegenerationalgorithmbasedonlocal-roadscanningmethodforconnect6[J].CAAItransactionsonintelligentsystems, 2015, 10(2): 267-272.

[50]ETESSAMIK,LOCHBIHLERA.Thecomputationalcomplexityofevolutionarilystablestrategies[J].Internationaljournalofgametheory, 2008, 37(1): 93-113.

[51]高強(qiáng), 徐心和. 時(shí)間復(fù)雜性和空間復(fù)雜性研究[J]. 智能系統(tǒng)學(xué)報(bào), 2014, 9(5): 529-535.GAOQiang,XUXinhe.Researchontimecomplexityandspacecomplexity[J].CAAItransactionsonintelligentsystems, 2014, 9(5): 529-535.

[52]GAOQiang,XUXinhe.ResearchonthecomputationalcomplexityofnxnChinesechess[J].ICGAjournal, 2015, 38(1): 47-53.

[53]VANDERHERIKHJ,UITERWIJKJWHM,VANRIJSWIJCKJ.Gamessolved:nowandinthefuture[J].Artificialintelligence, 2002, 134(1/2): 277-311.

[54]KAINDLH,SHAMSR,HORACEKH.Minimaxsearchalgorithmswithandwithoutaspirationwindows[J].IEEEtransactionsonpatternanalysisandmachineintelligence, 1991, 13(12): 1225-1235.

[55]LUHui,XIAZhengyou.AWT:aspirationwithtimersearchalgorithminSiguo[C]//Proceedingsofthe6thInternationalConferenceonComputersandGames.BerlinHeidelberg:Springer-Verlag, 2008: 264-274.

[56]鄒競. 基于MTD(f)的中國象棋人機(jī)博弈算法的設(shè)計(jì)與優(yōu)化[J]. 計(jì)算機(jī)與數(shù)字工程, 2008, 36(9): 38-43.ZOUJing.ChinesechessalgorithmdesignandoptimizebasedonMTD(f)[J].Computer&digitalengineering, 2008, 36(9): 38-43.

[57]張明亮, 李凡長. 一種新的博弈樹搜索方法[J]. 山東大學(xué)學(xué)報(bào): 工學(xué)版, 2009, 39(6): 1-8.ZHANGMingliang,LIFanzhang.Anewsearchmethodforagametree[J].JournalofShandonguniversity:engineeringscience, 2009, 39(6): 1-8.

[58]焦尚彬, 劉丁. 博弈樹置換表啟發(fā)式算法研究[J]. 計(jì)算機(jī)工程與應(yīng)用, 2010, 46(6): 42-45.JIAOShangbin,LIUDing.Researchontranslationtableheuristicalgorithm[J].Computerengineeringandapplications, 2010, 46(6): 42-45.

[59]DONKERSHHLM,UITERWIJKJWHM,VANDERHERIKHJ.Probabilisticopponent-modelsearch[J].Informationsciences, 2001, 135(3/4): 123-149.

[60]SCHAEFFERJ.TheHistoryheuristicandalpha-betasearchenhancementsinpractice[J].IEEEtransactionsonpatternanalysisandmachineintelligence, 1989, 11(11): 1203-1212.

[61]SAKUTAM,HASHIMOTOT,NAGASHIMAJ,etal.Applicationofthekiller-treeheuristicandthelambda-searchmethodtolinesofaction[J].Informationsciences, 2003, 154(3/4): 141-155.

[62]REINEFELDA,MARSLANDTA.Enhancediterative-deepeningsearch[J].IEEEtransactionsonpatternanalysisandmachineintelligence, 1994, 16(7): 701-710.

[63]MARSLANDTA,REINEFELDA,SCHAEFFERJ.LowoverheadalternativestoSSS[J].Artificialintelligence, 1987, 31(2): 185-199.

[64]PLAATA,SCHAEFFERJ,PIJLSW,etal.SSS*=alpha-beta+TT[J].ComputerScience, 2014, 8(1): 25.

[65]BERLINERH.TheB*treesearchalgorithm:abest-firstproofprocedure[J].Artificialintelligence, 1979, 12(1): 23-40.

[66]BERLINERHJ,MCCONNELLC.B*probabilitybasedsearch[J].Artificialintelligence, 1996, 86(1): 97-156.

[67]LORENTZR.UsingevaluationfunctionsinMonte-Carlotreesearch[J].Theoreticalcomputerscience, 2016, 644: 106-113.

[68]GUEZA,SILVERD,DAYANP.ScalableandefficientBayes-adaptivereinforcementlearningbasedonMonte-Carlotreesearch[J].Journalofartificialintelligenceresearch, 2013, 48(1): 841-883.

[69]BROWNECB,POWLEYE,WHITEHOUSED,etal.AsurveyofMonteCarlotreesearchmethods[J].IEEEtransactionsoncomputationalintelligenceandAIingames, 2012, 4(1): 1-43.

[70]BAIERH,WINANDSMHM.TimemanagementforMonteCarlotreesearch[J].IEEEtransactionsoncomputationalintelligenceandAIingames, 2016, 8(3): 301-314.

[71]RAIKOT,PELTONENJ.ApplicationofUCTsearchtotheconnectiongamesofHex,Y,*Star,andRenkula[C]//ProceedingsoftheFinnishAIConference.Espoo,Finland, 2008.

[72]呂艷輝, 宮瑞敏. 計(jì)算機(jī)博弈中估值算法與博弈訓(xùn)練的研究[J]. 計(jì)算機(jī)工程, 2012, 38(11): 163-166.LVYanhui,GONGRuimin.Studyonvaluationalgorithmandgametrainingincomputergame[J].Computerengineering, 2012, 38(11): 163-166.

[73]TAKEUCHIS,KANEKOT,YAMAGUCHIK.EvaluationofgameTreesearchmethodsbygamerecords[J].IEEEtransactionsoncomputationalintelligenceandAIingames, 2010, 2(4): 288-302.

[74]LIEBERUMJ.Anevaluationfunctionforthegameofamazons[J].Theoreticalcomputerscience, 2005, 349(2): 230-244.

[75]MARSLANDTA,CAMPBELLM.Parallelsearchofstronglyorderedgametrees[J].ACMcomputingsurveys, 1982, 14(4): 533-551.

[76]劉建偉, 劉媛, 羅雄麟. 深度學(xué)習(xí)研究進(jìn)展[J]. 計(jì)算機(jī)應(yīng)用研究, 2014, 31(7): 1921-1930, 1942.

LIUJianwei,LIUYuan,LUOXionglin.Researchanddevelopmentondeeplearning[J].Applicationresearchofcomputers, 2014, 31(7): 1921-1930, 1942.

[77]XIEFan,LIUZhiqing,WANGYu,etal.SystematicImprovementofMonte-CarloTreeSearchwithSelf-generatedNeural-NetworksControllers[M]//BLUMC,BATTITIR.LearningandIntelligentOptimization:LectureNotesinComputerScience.BerlinHeidelberg:Springer, 2010: 228-231.

[78]張小川, 唐艷, 梁寧寧. 采用時(shí)間差分算法的九路圍棋機(jī)器博弈系統(tǒng)[J]. 智能系統(tǒng)學(xué)報(bào), 2012, 7(3): 278-282.ZHANGXiaochuan,TANGYan,LIANGNingning.A9×9gocomputergamesystemusingtemporaldifference[J].CAAItransactionsonintelligentsystems, 2012, 7(3): 278-282.

王亞杰，女，1968年生，教授，博士，中國人工智能學(xué)會(huì)常務(wù)理事，中國人工智能學(xué)會(huì)機(jī)器博弈專業(yè)委員會(huì)主任。主要研究方向?yàn)闄C(jī)器博弈、模式識(shí)別、圖像融合，發(fā)表學(xué)術(shù)論文60余篇，主持 和參與課題20余項(xiàng)。.

邱虹坤，男，1971年生，講師，主要研究方向?yàn)闄C(jī)器博弈、智能機(jī)器人與飛行器綜合設(shè)計(jì)，指導(dǎo)學(xué)生在全國計(jì)算機(jī)博弈大賽中多次獲得亞馬遜棋冠軍，發(fā)表學(xué)術(shù)論文20余篇。

吳燕燕，女，1989年生，碩士，主要研究方向?yàn)閳D像融合、圖像處理方面的研究，發(fā)表學(xué)術(shù)論文5篇，主持或參與課題5項(xiàng)。

Research and development of computer games

WANG Yajie， QIU Hongkun， WU Yanyan， LI Fei， YANG Zhoufeng

(Engineering Training Center， Shenyang Aerospace University， Shenyang 110136， China)

Computer gaming is one of the most important and challenging research directions in the field of Artificial Intelligence (AI). First, this paper reviewed the development of computer games, and the competitions in China and abroad. All types of competitions provide a platform of technical verification and academic communication for the development of computer game technology. Second, the computer game system was introduced, which includes the game platform, the game tree search, the situation evaluation, the move generation, the machine learning and other technologies. The principles and features of the typically used algorithms were stated, such as the Minimax searching algorithm, the pruning searching algorithm, the Monte Carlo searching algorithm, and so on. The situation evaluation method and many optimization algorithms were also analyzed, among which, parallel computing, the genetic algorithm and the deep learning algorithm, based on a neural network, were effective methods to promote machine intelligence. Finally, the challenges of computer games were analyzed, and the development and future trends were proposed.

artificial intelligence; computer game; Monte Carlo tree search; neural networks; genetic algorithm; deep learning

10.11992/tis.201609006

http://www.cnki.net/kcms/detail/23.1538.TP.20170111.1705.030.html

2016-09-07.

航空科學(xué)基金項(xiàng)目(2015ZC54008)；遼寧省教育廳基金項(xiàng)目(L2015407).

邱虹坤.E-mail：qiuhk@sina.com.

TP391

A

1673-4785(2016)06-0788-011

王亞杰，邱虹坤，吳燕燕，等. 計(jì)算機(jī)博弈的研究與發(fā)展[J]. 智能系統(tǒng)學(xué)報(bào)， 2016, 11(6): 788-798.

英文引用格式：WANG Yajie， QIU Hongkun， WU Yanyan， et al. Research and development of computer games[J]. CAAI Transactions on Intelligent Systems, 2016, 11(2): 788-798.