淺談圍棋機器博弈

高夢萱

摘 要：本文首先闡述了計算機博弈的概念與歷史，討論了難度最高的圍棋機器博弈并比較了不同項目間復雜度；隨后從歷史發展的角度介紹了圍棋機器博弈在各個階段的發展情況以及取得的成就；之后分析了圍棋機器博弈當前面臨的問題并給出建議，最后論述了圍棋機器博弈未來可能的發展方向。

關鍵詞：機器博弈；圍棋；發展

中圖分類號：TP18 文獻標識碼：A 文章編號：1671-2064（2018）19-0247-02

相信很多人都還記得十年前那場人機對戰—IBM公司研發的計算機“深藍”對戰國際象棋特級大師卡斯帕羅夫，最終，卡斯帕羅夫以2.5：3.5（1勝2負3平）輸給了“深藍”，震驚了世界，同時也讓人們對機器博弈有了更深的認識。

從上世紀五十年代開始，許多著名計算機科學家如阿蘭·圖靈（Alan Turing），信息論創始人科勞德·香農（Claude E.Shannon），人工智能（Artificial Intelligence，AI）的創始人麥卡錫（John McCarthy）以及馮·諾依曼等都在進行機器博弈相關的研究。計算機博弈也稱機器博弈（Computer Games），最早是由從事計算機棋牌競技研究的科學家們給出了定義，他們認為Computer Games就是讓計算機能夠像人一樣會思考和決策，能夠下棋[1]。Computer Games直譯為計算機游戲，為了便于和計算機游戲區分，Computer Games中文譯為機器博弈，或者計算機博弈。機器博弈屬于人工智能領域的一個重要分支，機器博弈的水平在一定程度上也代表了人工智能的發展水平。在機器博弈中，圍棋被公認為難度最大，但隨著計算機技術的快速發展，人工智能在圍棋機器博弈領域也取得了驕人的成績。2016年3月，由谷歌Deep Mind團隊研發的AlphaGo與韓國圍棋世界冠軍、職業九段棋手李世石進行了比拼，被稱為圍棋人機大戰，最終AlphaGo以4比1的總比分獲勝；2017年5月，在中國烏鎮圍棋峰會上，它與排名世界第一的世界圍棋冠軍柯潔對戰，以3比0的總比分獲勝[2]。AlphaGo圍棋的勝利打破了人們長久以來認為只有人類擅長下圍棋的看法，此前，研究人員普遍認為具備思考能力的人工智能還需要數十年才會出現。本文將對圍棋機器博弈的基本概念、發展歷史、現狀等內容進行詳細論述，以期讓人們對圍棋機器博弈有一個全面、深入的認識。

1 圍棋機器博弈概述

圍棋機器博弈是機器博弈中的重要組成部分。它之所以被認為是棋類機器博弈中最為復雜的項目，根本原因就在于所研究對象圍棋的搜索空間遠大于國際象棋等其它棋種。博弈問題中衡量問題的復雜性主要根據狀態空間復雜度和博弈樹復雜度兩項指標，博弈過程的局面稱為狀態，而博弈問題的狀態復雜度是指從初始局面出發，產生的所有合法局面的總和。對于完備信息的博弈系統如圍棋、國際象棋等，其搜索還通常基于博弈樹搜索算法。博弈樹復雜度是指從初始局面開始，其得到理論解所需展開的最小搜索樹的所有葉子節點的總和。表1給出了部分棋類博弈問題的復雜度，可以看出，對于局面復雜、形式變幻多樣的圍棋來說，無論是狀態復雜度還是博弈樹復雜度都遠高于其它棋種，因此，精確計算圍棋博弈的狀態復雜度幾乎是不可能的。圍棋博弈的難度主要體現在兩方面：一是搜索空間巨大—合法的圍棋的變化（10172）大于宇宙中原子數（1080）；二是局面判斷難—從此前各種研究成果中看來，對于圍棋不可能有一個很好的靜態局面評估函數[1，3]。圍棋機器博弈是一個高復雜度的完備信息博弈問題，求出圍棋的均衡策略基本是不可能的，另一方面，正是圍棋機器博弈研究的高難度與復雜性吸引著眾多人工智能研究的許多科研機構和科學家。

2 圍棋機器博弈的發展歷程

2.1 第一代圍棋人工智能

歷史上第一個完整下完一盤圍棋的程序是1968年在美國完成的，由此開啟了近20年人們對于圍棋AI的探索。一直到1990年，中山大學化學系教授陳志行編寫出了名為“手談”的程序，在問世以后實力快速提升，不斷用實力獲取回報，甚至于1995至1998年贏得計算機圍棋世錦賽七連冠，一度成為九十年代的神話。“手談”的成功，與其中前所未有的“勢力函數”的應用有著密切的關系。“勢力”在圍棋中代表一個棋子對周圍空間的影響，將這種影響量化便得到了作為標準的“勢力函數”。同時，這種函數還能夠初步解決棋的走向問題，也就是得出了圍棋中最高深玄妙的“下法”。這在當時無疑是一次突破，也為后來圍棋人工智能的持續發展打下了堅實的基礎。同時期的圍棋AI還有陳克訓的Go Intellect，在1992及1994年兩度奪得應氏杯，雷秀瑜的Wulu，David Fotland的MFG也曾問鼎應氏杯，由此，圍棋AI進入到繁榮階段[4，5]。

2.2 第二代圍棋人工智能

在此之后，圍棋人工智能不斷發展，衍生出各種更加完備的算法，例如用評分判定下法對于自己利弊的極小化極大搜索算法以及以概率統計理論為指導用于判斷棋局結果的蒙特卡洛算法。這兩種算法相較于先前的程序，更加充分地利用了電腦的計算能力，并且能夠很好地支持并行計算，提升了工作效率，但同時也存在缺少前后邏輯關聯等問題。在誕生于這個時代的圍棋人工智能里，最成功的叫做Zen，也被稱作天頂圍棋。ZEN是由日本的加藤英樹教授及其團隊開發的，是集成各種算法應用的一次突破。在2011年的歐洲圍棋大會上，Zen初露鋒芒，在19路盤上讓五子擊敗日本職業棋手林耕三六段。在此之后，Zen能力盡顯，于2012年3月被讓四子擊敗了日本圍棋高手武宮正樹九段，這是圍棋AI第一次在讓四子的情況下戰勝圍棋職業選手，也是圍棋程序的一次歷史性的突破。2016年，Zen的升級版DeepZenGo在第二屆日本圍棋電王戰第二局大勝“不老傳說”趙治勛，雖然最終總比分1-2落敗，但已經展現出與職業九段抗衡的實力。

2.3 第三代圍棋人工智能

在經歷過幾次勝利之后，圍棋AI的發展又陷入了停滯。在這段安靜的日子里，飛速成長的AlphaGo已初露鋒芒，并在賽場上不斷證明自己的實力。AphaGo的非凡之處在于，它采用了一項叫做深度卷積神經網絡的核心技術，使得程序有了思維，能夠進行主動思考。這種人工神經網絡與人腦中的神經網絡類似，在面對一個局面時輸入信息，就好似大腦思考的過程，這項技術的應用讓圍棋人工智能的發展走上了又一高峰，2015、2017年AlphaGo相繼擊敗了人類圍棋冠軍。

2017年10月19日凌晨，谷歌下屬公司DeepMind發表研究論文報告了其最新版圍棋程序AlphaZero，它能夠從空白狀態學起，在無任何人類輸入的條件下，能夠迅速自學，并以100：0的戰績擊敗了前輩AlphaGo。對于僅擁有四個TPU，零人類經驗的AlphaZero來說，在自我訓練時間僅為三天的情況下，自我對弈的棋局數量能達到490萬盤，并達到非常不錯的水平，著實體現了圍棋人工智能的大幅進步。在舉世聞名的人機大戰之后，圍棋人工智能再一次刷新了眾人的眼界，這樣的發展可以說是空前的。

3 討論

從最初的圍棋程序到最新的AlphaZero，可以看到圍棋機器博弈的前途無疑是光明的。隨著技術的不斷進步，機器博弈也從只能對人類的簡單需求做出響應，到了擁有類人的“神經網絡”，能夠運用深度學習算法進行自主學習的“超級程序”。在人工智能持續發展的六十多年中，計算機博弈經歷了起步、發展、成熟、飛躍四個階段，于如今已達到了絕無僅有的空前水平。現階段的完備信息博弈技術已經比較成熟，非完備信息博弈和隨機類博弈技術還需進一步發展。

4 結語

計算機博弈作為信息時代的代表，依舊是擁有很大的發展前途。相信在正確利用后，它會與其它領域的技術更廣泛、更緊密地融合，推動人工智能產業本身迅速發展，從而實現技術快速提升。

參考文獻

[1]中國人工智能系列白皮書-機器博弈 [EB/OL].中國人工智能協會，2017.

[2]安波.人工智能與博弈論—從阿爾法圍棋談起[J].中國發展觀察，2016，（6）：13-13.

[3]嚴達浚.圍棋博弈中的人工智能研究[D].復旦大學，2007.

[4]師軍.圍棋與人工智能[J].中國體育科技，2005，41（6）：135-138.

[5]唐艷.圍棋博弈機器學習算法的研究及應用[D].重慶理工大學，2012.