淺談圍棋機(jī)器博弈

高夢(mèng)萱

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

關(guān)鍵詞：機(jī)器博弈；圍棋；發(fā)展

中圖分類號(hào)：TP18 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1671-2064（2018）19-0247-02

相信很多人都還記得十年前那場(chǎng)人機(jī)對(duì)戰(zhàn)—IBM公司研發(fā)的計(jì)算機(jī)“深藍(lán)”對(duì)戰(zhàn)國(guó)際象棋特級(jí)大師卡斯帕羅夫，最終，卡斯帕羅夫以2.5：3.5（1勝2負(fù)3平）輸給了“深藍(lán)”，震驚了世界，同時(shí)也讓人們對(duì)機(jī)器博弈有了更深的認(rèn)識(shí)。

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

1 圍棋機(jī)器博弈概述

圍棋機(jī)器博弈是機(jī)器博弈中的重要組成部分。它之所以被認(rèn)為是棋類機(jī)器博弈中最為復(fù)雜的項(xiàng)目，根本原因就在于所研究對(duì)象圍棋的搜索空間遠(yuǎn)大于國(guó)際象棋等其它棋種。博弈問(wèn)題中衡量問(wèn)題的復(fù)雜性主要根據(jù)狀態(tài)空間復(fù)雜度和博弈樹(shù)復(fù)雜度兩項(xiàng)指標(biāo)，博弈過(guò)程的局面稱為狀態(tài)，而博弈問(wèn)題的狀態(tài)復(fù)雜度是指從初始局面出發(fā)，產(chǎn)生的所有合法局面的總和。對(duì)于完備信息的博弈系統(tǒng)如圍棋、國(guó)際象棋等，其搜索還通?；诓┺臉?shù)搜索算法。博弈樹(shù)復(fù)雜度是指從初始局面開(kāi)始，其得到理論解所需展開(kāi)的最小搜索樹(shù)的所有葉子節(jié)點(diǎn)的總和。表1給出了部分棋類博弈問(wèn)題的復(fù)雜度，可以看出，對(duì)于局面復(fù)雜、形式變幻多樣的圍棋來(lái)說(shuō)，無(wú)論是狀態(tài)復(fù)雜度還是博弈樹(shù)復(fù)雜度都遠(yuǎn)高于其它棋種，因此，精確計(jì)算圍棋博弈的狀態(tài)復(fù)雜度幾乎是不可能的。圍棋博弈的難度主要體現(xiàn)在兩方面：一是搜索空間巨大—合法的圍棋的變化（10172）大于宇宙中原子數(shù)（1080）；二是局面判斷難—從此前各種研究成果中看來(lái)，對(duì)于圍棋不可能有一個(gè)很好的靜態(tài)局面評(píng)估函數(shù)[1，3]。圍棋機(jī)器博弈是一個(gè)高復(fù)雜度的完備信息博弈問(wèn)題，求出圍棋的均衡策略基本是不可能的，另一方面，正是圍棋機(jī)器博弈研究的高難度與復(fù)雜性吸引著眾多人工智能研究的許多科研機(jī)構(gòu)和科學(xué)家。

2 圍棋機(jī)器博弈的發(fā)展歷程

2.1 第一代圍棋人工智能

歷史上第一個(gè)完整下完一盤(pán)圍棋的程序是1968年在美國(guó)完成的，由此開(kāi)啟了近20年人們對(duì)于圍棋AI的探索。一直到1990年，中山大學(xué)化學(xué)系教授陳志行編寫(xiě)出了名為“手談”的程序，在問(wèn)世以后實(shí)力快速提升，不斷用實(shí)力獲取回報(bào)，甚至于1995至1998年贏得計(jì)算機(jī)圍棋世錦賽七連冠，一度成為九十年代的神話?！笆终劇钡某晒?，與其中前所未有的“勢(shì)力函數(shù)”的應(yīng)用有著密切的關(guān)系?！皠?shì)力”在圍棋中代表一個(gè)棋子對(duì)周圍空間的影響，將這種影響量化便得到了作為標(biāo)準(zhǔn)的“勢(shì)力函數(shù)”。同時(shí)，這種函數(shù)還能夠初步解決棋的走向問(wèn)題，也就是得出了圍棋中最高深玄妙的“下法”。這在當(dāng)時(shí)無(wú)疑是一次突破，也為后來(lái)圍棋人工智能的持續(xù)發(fā)展打下了堅(jiān)實(shí)的基礎(chǔ)。同時(shí)期的圍棋AI還有陳克訓(xùn)的Go Intellect，在1992及1994年兩度奪得應(yīng)氏杯，雷秀瑜的Wulu，David Fotland的MFG也曾問(wèn)鼎應(yīng)氏杯，由此，圍棋AI進(jìn)入到繁榮階段[4，5]。

2.2 第二代圍棋人工智能

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

2.3 第三代圍棋人工智能

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

2017年10月19日凌晨，谷歌下屬公司DeepMind發(fā)表研究論文報(bào)告了其最新版圍棋程序AlphaZero，它能夠從空白狀態(tài)學(xué)起，在無(wú)任何人類輸入的條件下，能夠迅速自學(xué)，并以100：0的戰(zhàn)績(jī)擊敗了前輩AlphaGo。對(duì)于僅擁有四個(gè)TPU，零人類經(jīng)驗(yàn)的AlphaZero來(lái)說(shuō)，在自我訓(xùn)練時(shí)間僅為三天的情況下，自我對(duì)弈的棋局?jǐn)?shù)量能達(dá)到490萬(wàn)盤(pán)，并達(dá)到非常不錯(cuò)的水平，著實(shí)體現(xiàn)了圍棋人工智能的大幅進(jìn)步。在舉世聞名的人機(jī)大戰(zhàn)之后，圍棋人工智能再一次刷新了眾人的眼界，這樣的發(fā)展可以說(shuō)是空前的。

3 討論

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

4 結(jié)語(yǔ)

計(jì)算機(jī)博弈作為信息時(shí)代的代表，依舊是擁有很大的發(fā)展前途。相信在正確利用后，它會(huì)與其它領(lǐng)域的技術(shù)更廣泛、更緊密地融合，推動(dòng)人工智能產(chǎn)業(yè)本身迅速發(fā)展，從而實(shí)現(xiàn)技術(shù)快速提升。

參考文獻(xiàn)

[1]中國(guó)人工智能系列白皮書(shū)-機(jī)器博弈 [EB/OL].中國(guó)人工智能協(xié)會(huì)，2017.

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

[3]嚴(yán)達(dá)浚.圍棋博弈中的人工智能研究[D].復(fù)旦大學(xué)，2007.

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

[5]唐艷.圍棋博弈機(jī)器學(xué)習(xí)算法的研究及應(yīng)用[D].重慶理工大學(xué)，2012.