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

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

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

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

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

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

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

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

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

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

1.1 起步階段

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

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

1.2 發(fā)展階段

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

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

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

1.3 成熟階段

20世紀(jì)末期，國(guó)內(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]，開(kāi)啟了深度學(xué)習(xí)在學(xué)術(shù)界的浪潮。2007年科學(xué)雜志評(píng)出的人類10大科學(xué)突破中，包括了加拿大阿爾波特大學(xué)研究人員歷時(shí)18年破解了國(guó)際跳棋(64)的研究成果，這是整個(gè)機(jī)器博弈發(fā)展史上的一個(gè)里程碑[5]。

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

1.4 飛躍階段

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

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)勝專家級(jí)人類選手[3]。2016年3月，AlphaGo又以4∶1戰(zhàn)勝世界圍棋冠軍李世石，在學(xué)術(shù)界產(chǎn)生了空前的影響，這標(biāo)志著計(jì)算機(jī)博弈技術(shù)取得重大成功，是計(jì)算機(jī)博弈發(fā)展史上新的躍遷。

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

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

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

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

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

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

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

除了以上競(jìng)賽，還有各種世界范圍內(nèi)的人機(jī)大戰(zhàn)活動(dòng)，這些競(jì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)生、搜索與評(píng)估幾個(gè)方面。

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

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

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

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

4.1 博弈樹(shù)復(fù)雜度

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

圖2 博弈樹(shù)示意圖Fig.2 Schematic diagram of game tree

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

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

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

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

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

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

4.2 博弈樹(shù)搜索

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

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

4.2.1 窮盡搜索

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

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

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)整樹(shù)的結(jié)構(gòu)，即對(duì)搜索節(jié)點(diǎn)排序，確保盡早剪枝。

2)渴望搜索[54-55]

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

3)MTD(f)搜索[56]

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

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

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

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

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

4.2.4 啟發(fā)式算法

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

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

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

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

歷史啟發(fā)也是迎合alpha-beta搜索對(duì)節(jié)點(diǎn)排列順序敏感的特點(diǎn)來(lái)提高剪枝效率的。它通過(guò)維護(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ā)可以對(duì)著法進(jìn)行動(dòng)態(tài)重排序，且提高了置換表的使用效率。

4.2.5 迭代深化[62]

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

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

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

最佳優(yōu)先的搜索算法，不受節(jié)點(diǎn)排序的影響，其搜索空間小于深度優(yōu)先的最小樹(shù)，理論上應(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)，把極大極小樹(shù)看成狀態(tài)圖，在不同的分支上展開(kāi)多條路徑，并且維護(hù)一個(gè)關(guān)于狀態(tài)圖的全局信息表。這兩種算法是兩個(gè)操作相反的過(guò)程，前者在搜索深度為偶數(shù)的極大極小搜索中表現(xiàn)較佳，后者則在深度為奇數(shù)搜索中較佳。

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

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

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

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

4.2.7 隨機(jī)搜索

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

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

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

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

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

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

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

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

2)UCT算法[13,25]

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

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

(1)

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

5 局面評(píng)估

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

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

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

提高計(jì)算機(jī)博弈能力不能單純依靠加大搜索深度，還需要將必要的相關(guān)博弈知識(shí)引入到相應(yīng)的博弈搜索中，只有協(xié)調(diào)搜索算法與評(píng)估函數(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ì)算速度，把博弈樹(shù)動(dòng)態(tài)分開(kāi)，發(fā)揮計(jì)算機(jī)多CPU強(qiáng)大的并行處理能力，同時(shí)執(zhí)行多個(gè)指令的算法。它不裁剪和縮小博弈樹(shù)的規(guī)模，通過(guò)提高搜索速度，而進(jìn)行優(yōu)化系統(tǒng)。

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

6.2 遺傳算法

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

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

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

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

深度學(xué)習(xí)是基于多層網(wǎng)絡(luò)結(jié)構(gòu)的一種機(jī)器學(xué)習(xí)方法，它逐層提取抽象特征，通過(guò)多層非線性傳輸，完成復(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)和棋局評(píng)估器(positionevaluator)。分別基于兩種不同的深度神經(jīng)網(wǎng)絡(luò)——策略網(wǎng)絡(luò)(policynetwork)和價(jià)值網(wǎng)絡(luò)(valuenetwork)，如圖4所示。前者用于學(xué)習(xí)高水平棋手的棋譜，獲得如何在盤(pán)面落子的棋感；后者通過(guò)機(jī)器的增強(qiáng)型學(xué)習(xí)，獲得形勢(shì)判斷的棋感。這兩個(gè)棋感通過(guò)蒙特卡羅搜索的技術(shù)進(jìn)行驗(yàn)證，使AlphaGo實(shí)現(xiàn)了技術(shù)突破。

盡管深度學(xué)習(xí)技術(shù)在圍棋方面取得了前所未有的成功，但在拓展應(yīng)用方面，如何合理利用深度學(xué)習(xí)方法來(lái)增強(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 面臨的問(wèn)題與展望

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

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

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

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

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

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

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

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

8 結(jié)束語(yǔ)

伴隨著人工智能科學(xué)發(fā)展的60周年，計(jì)算機(jī)博弈也經(jīng)歷了起步、發(fā)展、成熟、飛躍4個(gè)階段。依托各種形式的競(jìng)賽，極大地促進(jìn)了學(xué)術(shù)交流，檢驗(yàn)了新技術(shù)，推動(dòng)了博弈的研究與發(fā)展。當(dāng)前完備信息博弈技術(shù)相對(duì)比較成熟，非完備信息博弈和隨機(jī)類博弈技術(shù)還需進(jìn)一步發(fā)展。深度學(xué)習(xí)算法在AlphaGo圍棋計(jì)算機(jī)博弈中的成功應(yīng)用，引發(fā)了世界范圍內(nèi)對(duì)人工智能技術(shù)的高度關(guān)注，調(diào)動(dòng)了更多的專家學(xué)者開(kāi)展深入研究的積極性。盡管在計(jì)算機(jī)博弈領(lǐng)域還存在著各種各樣的問(wèn)題，許多工作還需要向更廣領(lǐng)域和更深層次推進(jìn)，但是隨著研究人員的不斷增加以及計(jì)算機(jī)博弈技術(shù)在各個(gè)領(lǐng)域的廣泛應(yīng)用，將會(huì)產(chǎn)生越來(lái)越多的研究成果。計(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ī)博弈——對(duì)于人類思維的挑戰(zhàn)[J]. 中國(guó)科技博覽, 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]李之棠, 陳華民. 博弈樹(shù)并行搜索算法[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]徐心和, 王驕. 中國(guó)象棋計(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]王驕, 王濤, 羅艷紅, 等. 中國(guó)象棋計(jì)算機(jī)博弈系統(tǒng)評(pí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]魏欽剛, 王驕, 徐心和, 等. 中國(guó)象棋計(jì)算機(jī)博弈開(kāi)局庫(kù)研究與設(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]徐長(zhǎng)明, 南曉斐, 王驕, 等. 中國(guó)象棋機(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)域——全國(guó)大學(xué)生計(jì)算機(jī)博弈大賽[J]. 計(jì)算機(jī)教育, 2012(7): 14-18.

[37]邱虹坤. 全國(guó)計(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), 等. 六子棋博弈的評(pí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)中評(pí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)中評(pí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é)俊, 王小龍, 吳蕾, 等. 六子棋中基于局部“路”掃描方式的博弈樹(shù)生成算法[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]鄒競(jìng). 基于MTD(f)的中國(guó)象棋人機(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]張明亮, 李凡長(zhǎng). 一種新的博弈樹(shù)搜索方法[J]. 山東大學(xué)學(xué)報(bào): 工學(xué)版, 2009, 39(6): 1-8.ZHANGMingliang,LIFanzhang.Anewsearchmethodforagametree[J].JournalofShandonguniversity:engineeringscience, 2009, 39(6): 1-8.

[58]焦尚彬, 劉丁. 博弈樹(shù)置換表啟發(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年生，教授，博士，中國(guó)人工智能學(xué)會(huì)常務(wù)理事，中國(guó)人工智能學(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é)生在全國(guó)計(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.