人工智能與博弈論
——從阿爾法圍棋談起

安 波

?

人工智能與博弈論
——從阿爾法圍棋談起

安 波

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

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

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

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

和AlphaGo不同的是，Clau-do的策略基于撲克博弈的近似均衡。圍棋比賽本身是一種完全信息博弈，而撲克是不完全信息博弈（玩家不能觀測(cè)到對(duì)手手中的牌），因此比完全信息博弈更難解決。Clau-do通過下面這三個(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ī)玩家，以致于人類玩家終其一生也無法戰(zhàn)勝它。這并不是說 Cepheus一局也不會(huì)輸，但是從長期來看，結(jié)果只能是平手，或者計(jì)算機(jī)獲勝。需要注意的是，有上限投注德州撲克博弈比無上限投注德州撲克博弈要容易求解。

由于圍棋和撲克在本質(zhì)上都是博弈問題，我們這里談?wù)劜┺恼撘约白鳛榍蠼鈸淇瞬┺牡乃惴ú┺恼摗?944年，John von Neumann與Oskar Morgenstern合著《博弈論與經(jīng)濟(jì)行為》，標(biāo)志著現(xiàn)代系統(tǒng)博弈理論的初步形成，因此他被稱為“博弈論之父”。盡管歷年來，博弈論與計(jì)算學(xué)科學(xué)不時(shí)有顯著的重疊，但在早期，博弈論主要為經(jīng)濟(jì)學(xué)家所研究應(yīng)用。事實(shí)上，博弈論現(xiàn)在也是微觀經(jīng)濟(jì)學(xué)理論的主要分析框架。 博弈論在經(jīng)濟(jì)教科書中的應(yīng)用非常廣泛。在經(jīng)濟(jì)科學(xué)領(lǐng)域，很多杰出的博弈理論家曾榮獲諾貝爾獎(jiǎng)，如2012年諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)得主羅斯和沙普利。

就在博弈論理論出現(xiàn)不久后，人工智能領(lǐng)域緊隨其后得到開發(fā)。事實(shí)上，人工智能的開拓者如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ì)算和博弈理論模型，被稱為算法博弈論。近幾年來，算法博弈論發(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ù)雜性問題、機(jī)制設(shè)計(jì)（包括在線拍賣、在線廣告）、計(jì)算社會(huì)選擇等，并在包括撲克等的很多領(lǐng)域得到應(yīng)用。過去幾年，算法博弈論在安全領(lǐng)域的資源分配及調(diào)度方面的理論——安全博弈論逐漸建立并且在若干領(lǐng)域得到成功應(yīng)用。

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

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