原標(biāo)題：人工智能與博弈論——從阿爾法圍棋談起
       谷歌AlphaGo（阿爾法圍棋）在與棋手李世的人機(jī)大戰(zhàn)中,，最終以4∶1贏得勝利,。這一人類(lèi)智慧和人工智能的對(duì)決在世界各地掀起了對(duì)人工智能空前的關(guān)注熱潮。

       AlphaGo是一款圍棋人工智能程序,，由谷歌Deep Mind團(tuán)隊(duì)開(kāi)發(fā),。AlphaGo將幾項(xiàng)技術(shù)很好地集成在了一起：通過(guò)深度學(xué)習(xí)技術(shù)學(xué)習(xí)了大量的已有圍棋對(duì)局，接著應(yīng)用強(qiáng)化學(xué)習(xí)通過(guò)與自己對(duì)弈獲得了更多的棋局,，然后用深度學(xué)習(xí)技術(shù)評(píng)估每一個(gè)格局的輸贏率（即價(jià)值網(wǎng)絡(luò)）,，最后通過(guò)蒙特卡洛樹(shù)搜索決定最優(yōu)落子。同時(shí)谷歌用超過(guò)1000個(gè)CPU和GPU進(jìn)行并行學(xué)習(xí)和搜索,。

       在過(guò)去20多年中，人工智能在大眾棋類(lèi)領(lǐng)域與人類(lèi)的較量一直存在,。1997年,，IBM公司研制的深藍(lán)系統(tǒng)首次在正式比賽中戰(zhàn)勝人類(lèi)國(guó)際象棋世界冠軍卡斯帕羅夫，成為人工智能發(fā)展史上的一個(gè)里程碑,。然而,，一直以來(lái)，圍棋卻是個(gè)例外,，在這次AlphaGo取得突破性勝利之前,，計(jì)算機(jī)圍棋程序雖屢次向人類(lèi)高手發(fā)出挑戰(zhàn),，但其博弈水平遠(yuǎn)遠(yuǎn)低于人類(lèi)，之前最好的圍棋程序（同樣基于蒙特卡洛樹(shù)搜索）被認(rèn)為達(dá)到了業(yè)余圍棋五,、六段的水平,。

       這其中的一個(gè)原因就是圍棋的棋局難于估計(jì)，對(duì)局面的判斷非常復(fù)雜,。另外一個(gè)更主要的原因是圍棋的棋盤(pán)上有361個(gè)點(diǎn),，其搜索的寬度和深度遠(yuǎn)遠(yuǎn)大于國(guó)際象棋，因此,，求出圍棋的均衡策略基本是不可能的,。AlphaGo集成了深度學(xué)習(xí)、強(qiáng)化學(xué)習(xí),、蒙特卡洛樹(shù)搜索,，并取得了成功。

       我們這里順便說(shuō)一說(shuō)人工智能和人類(lèi)在另一項(xiàng)棋類(lèi)項(xiàng)目——德州撲克的較量,。德州撲克于20世紀(jì)初開(kāi)始于德克薩斯洛布斯鎮(zhèn),，后來(lái)在全美大面積流行起來(lái)。德州撲克以其易學(xué)難精的特點(diǎn),，受到各國(guó)棋牌愛(ài)好者的青睞,。世界德州撲克系列大賽（WSOP）是一個(gè)以無(wú)上限投注德州撲克為主要賽事的撲克大賽，自上世紀(jì)70年代登陸美國(guó)以來(lái),，比賽在賭城拉斯維加斯的各大賭場(chǎng)舉行,。其中，以冠軍大賽的獎(jiǎng)金額最高,，參賽人數(shù)最多,，比賽最為隆重，北美各地的體育電視頻道都有實(shí)況轉(zhuǎn)播,。有史以來(lái)第一次人類(lèi)和計(jì)算機(jī)無(wú)限注德州撲克比賽于2015年4月24日到5月8日在美國(guó)賓夕法尼亞匹茲堡的河邊賭場(chǎng)舉行,，組織者為卡內(nèi)基梅隆大學(xué)的Tuomas Sandholm教授，包括微軟研究院等多家機(jī)構(gòu)提供了獎(jiǎng)金支持,。該比賽共有兩組玩家,，一組是電腦程序“Clau-do”，另一組是該類(lèi)撲克游戲的頂級(jí)專(zhuān)家Dong Kim,、Jason Les,、Bjorn Li和Doug Polk。Clau-do是之前Tartanian（2014美國(guó)人工智能大會(huì)電腦撲克大賽冠軍所用的程序）的改進(jìn)版本,。該比賽一共進(jìn)行了8萬(wàn)回合,，最后撲克專(zhuān)家以微弱的優(yōu)勢(shì)獲得了勝利，學(xué)術(shù)界認(rèn)為Clau-do取得了很大的成功,。

       和AlphaGo不同的是,，Clau-do的策略基于撲克博弈的近似均衡,。圍棋比賽本身是一種完全信息博弈，而撲克是不完全信息博弈（玩家不能觀測(cè)到對(duì)手手中的牌）,，因此比完全信息博弈更難解決,。Clau-do通過(guò)下面這三個(gè)步驟決定其策略。第一步：原始博弈被近似為更小的抽象博弈,，保留了最初博弈的戰(zhàn)略結(jié)構(gòu),。第二步：計(jì)算出小的抽象博弈中的近似均衡。第三步：用逆映射程序的方法從抽象博弈的近似均衡建立一個(gè)原始博弈的策略,。Clau-do的成功必須歸功于算法博弈論最近幾年的進(jìn)展,。在2015年年初《科學(xué)》雜志發(fā)布的一篇論文中，加拿大阿爾伯塔大學(xué)計(jì)算機(jī)科學(xué)教授Michael Bowling帶領(lǐng)的研究小組介紹了求解有上限投注德州撲克博弈均衡的算法,，基于該均衡策略的程序 Cepheus是接近完美的有上限投注德州撲克計(jì)算機(jī)玩家,，以致于人類(lèi)玩家終其一生也無(wú)法戰(zhàn)勝它。這并不是說(shuō) Cepheus一局也不會(huì)輸,，但是從長(zhǎng)期來(lái)看,，結(jié)果只能是平手，或者計(jì)算機(jī)獲勝,。需要注意的是,，有上限投注德州撲克博弈比無(wú)上限投注德州撲克博弈要容易求解。由于圍棋和撲克在本質(zhì)上都是博弈問(wèn)題,，我們這里談?wù)劜┺恼撘约白鳛榍蠼鈸淇瞬┺牡乃惴ú┺恼摗?944年,，John von Neumann與Oskar Morgenstern合著《博弈論與經(jīng)濟(jì)行為》，標(biāo)志著現(xiàn)代系統(tǒng)博弈理論的初步形成,，因此他被稱(chēng)為“博弈論之父”,。盡管歷年來(lái)，博弈論與計(jì)算學(xué)科學(xué)不時(shí)有顯著的重疊,，但在早期,，博弈論主要為經(jīng)濟(jì)學(xué)家所研究應(yīng)用。事實(shí)上,，博弈論現(xiàn)在也是微觀經(jīng)濟(jì)學(xué)理論的主要分析框架,。 博弈論在經(jīng)濟(jì)教科書(shū)中的應(yīng)用非常廣泛。在經(jīng)濟(jì)科學(xué)領(lǐng)域,，很多杰出的博弈理論家曾榮獲諾貝爾獎(jiǎng),，如2012年諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)得主羅斯和沙普利。

       就在博弈論理論出現(xiàn)不久后,，人工智能領(lǐng)域緊隨其后得到開(kāi)發(fā)。事實(shí)上,，人工智能的開(kāi)拓者如von Neumann 和Simon 在兩個(gè)領(lǐng)域早期都有杰出貢獻(xiàn),。博弈論和人工智能實(shí)際上都基于決策理論,。例如，有一個(gè)著名觀點(diǎn)把人工智能定義為“智能體的研究和構(gòu)建”,。從20世紀(jì)90年代中期到后期,，博弈論成為計(jì)算機(jī)科學(xué)家的主要研究課題，所產(chǎn)生的研究領(lǐng)域融合計(jì)算和博弈理論模型,，被稱(chēng)為算法博弈論,。近幾年來(lái)，算法博弈論發(fā)展尤為迅速,，得到了包括哈佛大學(xué),、劍橋大學(xué)、耶魯大學(xué),、卡內(nèi)基梅隆大學(xué),、加州伯克利大學(xué)、斯坦福大學(xué)等世界各大著名研究機(jī)構(gòu)的重點(diǎn)研究,，該領(lǐng)域的會(huì)議如雨后春筍般出現(xiàn),，并與多智能系統(tǒng)研究融合，其普及程度已經(jīng)在緩慢地追趕人工智能,。算法博弈論的主要研究領(lǐng)域包括各種均衡的計(jì)算及復(fù)雜性問(wèn)題,、機(jī)制設(shè)計(jì)（包括在線拍賣(mài)、在線廣告）,、計(jì)算社會(huì)選擇等,，并在包括撲克等的很多領(lǐng)域得到應(yīng)用。過(guò)去幾年,，算法博弈論在安全領(lǐng)域的資源分配及調(diào)度方面的理論——安全博弈論逐漸建立并且在若干領(lǐng)域得到成功應(yīng)用,。

       與算法博弈論求解均衡策略或者近似均衡策略不同，基于學(xué)習(xí)以及蒙特卡洛樹(shù)搜索的AlphaGo無(wú)法在理論上給出贏棋的概率,?？紤]到將博弈抽象的思想應(yīng)用到撲克博弈上的成功，是否可能將圍棋博弈抽象成小規(guī)模的博弈,，求解（近似）均衡策略,，并產(chǎn)生原始博弈問(wèn)題的策略？即使這種策略不能有贏棋概率的保證,，這些基于均衡產(chǎn)生的策略有可能對(duì)提高AlphaGo的性能提供幫助,。從另外一個(gè)角度，深度學(xué)習(xí)技術(shù)是否會(huì)為求解大規(guī)模博弈問(wèn)題提供幫助也值得探索,。也許我們無(wú)法證明基于深度學(xué)習(xí)的策略能夠形成某種均衡,，但是可能會(huì)從實(shí)驗(yàn)?zāi)M結(jié)果來(lái)說(shuō)接近均衡策略。因此,，AlphaGo的成功不僅會(huì)引爆人工智能研究的熱潮,，也會(huì)促進(jìn)人工智能與算法博弈論的進(jìn)一步交融與發(fā)展,。

       （作者單位：新加坡南洋理工大學(xué)計(jì)算機(jī)工程學(xué)院）