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

谷歌AlphaGo（阿爾法圍棋）在與棋手李世的人機大戰中，最終以4︰1贏得勝利。這一人類智慧和人工智能的對決在世界各地掀起了對人工智能空前的關注熱潮。

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

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

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

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

和AlphaGo不同的是，Clau-do的策略基於扑克博弈的近似均衡。圍棋比賽本身是一種完全信息博弈，而扑克是不完全信息博弈（玩家不能觀測到對手手中的牌），因此比完全信息博弈更難解決。Clau-do通過下面這三個步驟決定其策略。第一步：原始博弈被近似為更小的抽象博弈，保留了最初博弈的戰略結構。第二步：計算出小的抽象博弈中的近似均衡。第三步：用逆映射程序的方法從抽象博弈的近似均衡建立一個原始博弈的策略。Clau-do的成功必須歸功於算法博弈論最近幾年的進展。在2015年年初《科學》雜志發布的一篇論文中，加拿大阿爾伯塔大學計算機科學教授Michael Bowling帶領的研究小組介紹了求解有上限投注德州扑克博弈均衡的算法，基於該均衡策略的程序 Cepheus是接近完美的有上限投注德州扑克計算機玩家，以致於人類玩家終其一生也無法戰勝它。這並不是說 Cepheus一局也不會輸，但是從長期來看，結果隻能是平手，或者計算機獲勝。需要注意的是，有上限投注德州扑克博弈比無上限投注德州扑克博弈要容易求解。由於圍棋和扑克在本質上都是博弈問題，我們這裡談談博弈論以及作為求解扑克博弈的算法博弈論。1944年，John von Neumann與Oskar Morgenstern合著《博弈論與經濟行為》，標志著現代系統博弈理論的初步形成，因此他被稱為“博弈論之父”。盡管歷年來，博弈論與計算學科學不時有顯著的重疊，但在早期，博弈論主要為經濟學家所研究應用。事實上，博弈論現在也是微觀經濟學理論的主要分析框架。 博弈論在經濟教科書中的應用非常廣泛。在經濟科學領域，很多杰出的博弈理論家曾榮獲諾貝爾獎，如2012年諾貝爾經濟學獎得主羅斯和沙普利。

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

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

（作者單位：新加坡南洋理工大學計算機工程學院）