安 波

?

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

安 波

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

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

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

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

和AlphaGo不同的是，Clau-do的策略基于撲克博弈的近似均衡。圍棋比賽本身是一種完全信息博弈，而撲克是不完全信息博弈（玩家不能觀測到對手手中的牌），因此比完全信息博弈更難解決。Clau-do通過下面這三個步驟決定其策略。第一步：原始博弈被近似為更小的抽象博弈，保留了最初博弈的戰(zhàn)略結(jié)構(gòu)。第二步：計算出小的抽象博弈中的近似均衡。第三步：用逆映射程序的方法從抽象博弈的近似均衡建立一個原始博弈的策略。Clau-do的成功必須歸功于算法博弈論最近幾年的進展。在2015年年初《科學(xué)》雜志發(fā)布的一篇論文中，加拿大阿爾伯塔大學(xué)計算機科學(xué)教授Michael Bowling帶領(lǐng)的研究小組介紹了求解有上限投注德州撲克博弈均衡的算法，基于該均衡策略的程序Cepheus是接近完美的有上限投注德州撲克計算機玩家，以致于人類玩家終其一生也無法戰(zhàn)勝它。這并不是說 Cepheus一局也不會輸，但是從長期來看，結(jié)果只能是平手，或者計算機獲勝。需要注意的是，有上限投注德州撲克博弈比無上限投注德州撲克博弈要容易求解。

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

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

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

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