為何Google圍棋AI AlphaGo可能會把李世石擊潰

 

GoogleDeepMind開發的人工智能圍棋程序AlphaGo以5:0的壓倒性優勢擊敗了歐洲圍棋冠軍、專業二段棋手Fan Hui,這是最近一周來最火爆的新聞了。16年3月份AlphaGo會和最近10年平均成績表現最優秀的韓國九段、世界冠軍李世石進行對弈,這無疑也是最吸引眼球的一場人機世紀大戰,如果此役AlphaGo獲勝,這意味著人工智能真正里程碑式的勝利,從此起碼在智力博弈類遊戲範圍內,碳基體人類將無法抵擋矽基類機器的狂風驟雨,不知這是該令人驚恐還是令人興奮呢?

反正我是屬於看了這個新聞像被注射了興奮劑似得那類具備反人類人格犯罪分子的興奮類型@^^@。

當然,本文的標題有點嘩眾取寵,但是並非毫無根據的。現在的問題是:三月份的人機大戰中,李世石的勝率能有多高?是AlphaGo擊敗人類還是李世石力挽狂瀾,維護人類尊嚴?此前眾說紛紜,各種說法都有。但是看上去都是沒什麼依據的猜測。我在深入了解了AlphaGo的AI運作機制後,鬥膽做出如下預測,到時可看是被打臉還是能夠成為新世紀的保羅,首先強調一點,我這個預測是有科學根據的,至於依據是什麼,後文會談。

如果是5番棋,預測如下:
如果李世石首局輸掉,那麼AlphaGo很可能獲得壓倒性勝利,我預估AlphaGo會以4:1甚至5:0獲勝;
如果李世石首局贏,但是第二局輸掉,那麼AlphaGo可能會以3:2甚至4:1勝出;
如果李世石首局和第二局都贏,那麼AlphaGo可能會碾壓性失敗,局面可能是0:5或者1:4;
也就是說,局面很可能是一方壓倒性勝利,要麼是AlphaGo要麼是李世石,而且首局勝敗可能起到關鍵作用,為什麼這麼說呢?我們要了解AlphaGo是怎麼下棋的。

|下圍棋的本質是什麼?

圖1 下圍棋是在幹什麼

下圍棋的本質是在幹什麼?圖1其實基本就說明了問題了。兩個棋手(這兩個棋手可能其中一個人類一個AI,也許兩個都是人類或者兩個都是AI,這不重要)剛開始都是面對一個19*19的空棋盤,執黑先下子,下子是什麼意思?就是在當前棋局S下(剛開始S就是空棋盤),判斷下個子應該放在哪裡更好,所有合法的落子位置都在考慮範圍,比如開局第一子,任何一個棋盤位置落子都是可以的,但是這裡面有些是好的落子位置,有些是不好的落子範圍,至於到底好不好,因為棋還沒下完,暫時不知道,只有最後決出輸贏才能說這個子落得好不好。

如果黑方選定了一個落子位置,則棋局局面從S進入到S1,此時該白方下,一樣的,白方面對很多可能的落子選擇,然後選擇一個他認為最好的…..就這麼依次下下去,直到決出輸贏為止。

從這裡可以看出,從落第一個子到下完,整個下子的決策空間形成了一個非常巨大的樹形結構。之所以我們說圍棋難,就是因為這顆樹的寬度(就是應該落哪個子)和深度(就是一步一步輪著下子)都太大了,組合出的可能空間巨大無比,基本靠搜尋遍整個空間是不可能做到的。

所以你看到下圍棋本質是什麼,就是在這顆超大的樹搜尋空間裡面,從樹的根節點,也就是空棋盤,順著樹一路下行,走出一條路徑,路徑的末尾就是已經決出勝負的棋局狀態。

因為搜尋空間太大,所以圍棋AI不可能遍歷所有可能的下棋路徑,那麼只能學習一些策略或者評估函數,根據這些策略能夠大量減少搜尋空間,包括樹的寬度和深度。





有了這個基礎,我們可以講AlphaGo了。

AlphaGo的技術總體架構如果一句話總結的話就是:採用深層CNN神經網路架構結合蒙特卡洛搜尋樹。深度學習神經網路訓練出兩個落子策略和一個局面評估策略,這三個策略的神經網路架構基本相同,只是學習完後網路參數不同而已。而且這三個策略是環環相扣的:落子策略SL是通過學習人類對弈棋局,來模擬給定當前棋局局面,人如何落子的思路,這是純粹的學習人類下棋經驗,它的學習目標是:給定某個棋局形式,人會怎麼落子?那麼AlphaGo通過人類對弈棋局來學習這些落子策略,也就是說SL策略學習到的是像人一樣來下下一步棋;

落子策略RL是通過AlphaGo自己和自己下棋來學習的,是在SL落子策略基礎上的改進模型,RL策略的初始參數就是SL落子策略學習到的參數,就是它是以SL落子策略作為學習起點的,然後通過自己和自己下棋,要進化出更好的自己,它的學習目標是:不像SL落子策略那樣只是學習下一步怎麼走,而是要兩個AlphaGo不斷落子,直到決出某盤棋局的勝負,然後根據勝負情況調整RL策略的參數,使得RL學習到如何能夠找到贏棋的一系列前後聯繫的當前棋局及對應落子,就是它的學習目標是贏得整盤棋,而不是像SL策略那樣僅僅預測下一個落子。

局面評估網路Value Network採用類似的深度學習網路結構,只不過它不是學習怎麼落子,而是給定某個棋局盤面,學習從這個盤面出發,最後能夠贏棋的勝率有多高,所以它的輸入是某個棋局盤面,通過學習輸出一個分值,這個分值越高代表從這個棋盤出發,那麼贏棋的可能性有多大;

有了上面的三個深度學習策略,AlphaGo把這三個策略引入到蒙特卡洛搜尋樹中,所以它的總體架構還是蒙特卡洛搜尋樹,只是在應用蒙特卡洛搜尋樹的時候在幾個步驟集成了深度學習學到的落子策略及盤面評估。

AlphaGo的整體技術思路就是上面說的,那麼我們從這些技術原理可以得出什麼結論呢?我對各個部分的分析和結論如下,這也是為何本文開頭作出那個人機大戰預測的科學依據所在。

|SL落子策略
首先,我們看落子策略SL,就是那個根據人類對弈過程來學習像人一樣落子的策略。這個策略重要嗎?重要,但是只靠這個策略能夠戰勝人類世界冠軍嗎?我的結論是不可能,靠這個策略一萬年也贏不了人類。為什麼呢?你要考慮到很關鍵的一點:AlphaGo這個策略是通過看了16萬局人類對弈棋局來學習的,但是問題的關鍵是,這些下棋的人素質總體有多高?如果以職業棋手水平來衡量,平均下來總體素質其實是不高的,裡面大量棋局是業餘選手下的,即使有不少專業選手下,高段位選手肯定不會太多。那麼AlphaGo從這些二流選手下棋落子能夠學到每步棋都達到九段水平嗎?這不太可能。


圖2 AlphaGo和fan hui對弈過程中的SL落子策略得分,圖中某些位置的得分代表AlphaGo認為落子位置有多像人會選擇的落子位置

所以我的結論是:如果人工智能程序只能從人類棋手下的盤面學習,按照目前的學習方式,機器永遠也無法戰勝最好的人類,因為它學習的對象平庸者居多,三流師父永遠教不出一流的徒弟,這個道理很簡單。如果只用這個方法,就算AlphaGo看到再多人類的比賽也無法戰勝人類,除非它看到的都是超一流選手的盤面,那麼它可以成為超一流選手,但是面對人類最強手,並沒有必勝的把握。

那麼豈不是說三月的對決中,AlphaGo必敗無疑了?其實不然,上面這點說的是SL策略的弱點,但是AlphaGo的論文給出了數據,SL策略比傳統單純使用蒙特卡洛搜尋樹的策略下子準確率從44%提升到了55%左右,這個55%是什麼意思?意思是SL策略做了100次落子,其中55個落子是和人落子位置相同的。

看上去55%好像也不太高麼,沒什麼可怕的,你肯定這麼想,是吧?你錯了!你要看44%到55%的提升幅度,因為SL策略只是決定了單步落子,而單步落子小幅度的準確率提升,會極大提升最終贏棋的勝率,因為你想啊,一個棋局是由幾百個落子構成的,每一步的小幅度準確率提升,經過幾百次不斷累積,那最終結果差異是非常大的,這就是所謂的「積小勝為大勝」的道理。這是機器對人很大的一個優勢,因為它穩定,如果準確率達到一定程度,就不容易出昏招,只要依靠每一步的小優勢不斷積累就能獲得巨大的累積優勢。






人類其實相對機器還有一個很大的劣勢:人的理性決策太容易受到情緒影響,一旦自己局面處於不利地位,或者自己下了一步臭棋,可能後面連續若干落子都會受到影響,而且下到後面人可能比較疲勞了,算棋能力下降難免,但是機器完全沒有這兩個問題,可以很冷血很冷靜的跟你下,下了好棋也沒見AlphaGo笑,下了臭棋也沒見AlphaGo哭,體力無敵,只要你不拔它的電源插頭,它就面無表情地跟你死磕到底,是不是這個道理?

所以說,即使AlphaGo只有SL落子策略,如果它的落子水平是5段,那麼其實考慮到這些優勢,它基本上是能穩贏人類5段這種相同段位棋手的。這也是為何本文開頭預測三月人機大戰可能是如此結果的一個重要參考因素。李世石肩上擔著這麼個重擔,而且這是世界矚目的一場比賽,他完全沒有心理負擔是不可能的,也許他看了AlphaGo和Fan Hui的棋局,現在心理上同時蔑視AlphaGo和Fan Hui棋力渣,但是如果初賽不利,很可能會被冷血的機器打崩潰。

|RL落子策略

然後,我們再來看落子策略RL。前面提到,它學習的目的和落子策略SL不一樣,落子策略SL就是學習單步如何像人一樣落子,至於後面這局棋是輸掉還是贏了它其實沒學到什麼東西,它只要保證說面對目前的棋盤布局,像人一樣落下下一個子就行了。而落子策略RL學習目標則是以贏棋為目的,是說經過若干輪博弈,最終贏棋那麼它就認為在這個對弈過程中的相應的棋局和落子就是值得鼓勵的,並把這些鼓勵體現到深度學習模型參數裡面,意思是以後看到類似的局面,更傾向於這麼去落子,因為這麼落子很可能最終會贏棋。它自己和自己下完一局棋,如果勝利了,那麼在這條通向勝利結果過程中的所有棋局對應的落子都會得到鼓勵。

其實對於人類來說,這種自己和自己下棋的RL落子策略才是真正可怕的,因為它可以通過這種方式不斷自我進化。它自己和自己下了一盤棋等於幹了個什麼事情?等於說在下棋落子巨大的樹組合空間中,搜尋找到了其中一條從空棋盤開始到最終勝負已分通向勝利的一條落子路徑,而根據這個路徑是贏了還是輸了調整模型參數,使得模型以後更傾向於選擇這條路徑;意思是如果以後和人下棋,一旦有一局中某個落子方式在它的這個學習路徑中,那麼它就傾向於走出那一系列讓它贏的策略。

因為它的核心目的等於是在所有樹空間裡搜尋,然後學習找到那些容易贏的路徑,學習的結果是更傾向找到那些導致最終贏旗的路徑,這個只要不斷地自己和自己下理論上能力是能夠不斷提高的,因為圍棋組合出的樹空間雖然巨大無比,畢竟還是有限的,自己和自己對戰等於在不斷找出並記住那些能夠贏棋的落子路徑,對戰次數越多,窮舉出這些路徑的可能性越大,也就意味著它棋力在不斷提升。從這個角度看,這也是為何說它可怕在此處的一個原因。

當然,這個左右互搏的自閉症兒童式的自我下棋,它也不是沒有弱點,它的弱點是:AlphaGo是根據一個贏旗的路徑走的,傾向於學習這個路徑上的落子策略,但是在真實下棋過程中,也許對手不會選擇這條路徑,那麼後面學到的看似就沒用了,但是這個弱點其實在現實場景中問題也不大:因為AlphaGo的自我下棋的對手(也是它自己)也是有一定水平的,所以對手選擇的落子也會很高概率落在真正人類選手選擇的落子位置,即是說它選擇的這個路徑是在再次和其它對手下很可能走的一條路,如果再完全重走這條路徑,那麼計算機必贏。

綜上分析,落子策略RL通過這種自我對戰來在巨大的樹搜尋空間中找到贏棋路徑的方法是比較可怕的,因為理論上它只要不斷自我對弈,是能夠不斷提高下棋水平的。這是人機對決中人類不樂觀的的一個方面,因為就像上面說的,只要你不拔機器的電門,它就可以不眠不休地去玩自閉症遊戲,其實人工智能不可怕,可怕的是能夠不斷自我學習自我進化的人工智能。

|棋局評估Value Network
Value Network也是通過3000萬盤AlphaGo自我對戰來進行學習的,它是建立在RL落子策略之上的,因為此刻RL落子策略已經代表了一個棋力比較高的棋手了,不過這個棋手就是AlphaGo自身而已。Value Network它要學習什麼東西?它要學的是:給定當前棋局布局,也就是AlphaGo看到的當前棋盤情況,那麼這個棋盤布局有多大可能會導致最後贏棋?這就是它學習的目標。

Value Netwok的本質思想是:如果當前棋局處於局面S,那麼假設這時候有兩個目前最強的棋手,就是兩個採取RL策略的棋手從局面S開始繼續往下下棋,那麼從局面S出發,最終贏旗的可能性有多大;因為這兩個RL棋手會盡可能走那些局面S出發產生的子樹裡面,它們各自認為能夠導致勝利的路徑,所以一般是樹搜尋子空間裡面容易被棋手選擇到的路徑,評估了這些路徑後綜合出這種棋局S最終可能勝利的可能性,獲勝可能性越大,意味著從棋局S出發的這個搜尋個子樹空間裡面通向勝利局面的路徑越多,所以它是個「大面積搜尋路徑覆蓋」的策略;

其實綜合上面三個策略,可以看出:SL落子策略類似於點覆蓋,因為它只考慮下步旗子怎麼走,只覆蓋了一步棋;RL落子策略類似於線覆蓋,因為它其實在找一條能夠贏棋的走棋路徑;而Value Network類似於面覆蓋,因為它評估的是當前棋局S出發,所有可能走的搜尋路徑中綜合看通向勝利的下棋路徑有多少,越多越好;AlphaGo就是這麼利用深度學習來進行搜尋空間點線面結合來提升棋力的。

圖3  AlphaGo和Fan Hui對弈過程中,對棋局的評估,對應位置的得分意味著如果把旗子落子這個位置,那麼這個落子後的棋局最後贏棋的可能性
|蒙特卡洛搜尋樹
蒙特卡洛搜尋樹可以說是一項導致圍棋人機對戰過程中突破性的技術進展,有了蒙特卡洛搜尋樹,就把機器選手從沒資格和人類對戰帶到了有資格和業餘選手進行對戰的境地,但是僅僅靠蒙特卡洛樹是不夠的,因為樹搜尋空間太大,如果蒙特卡洛采樣太多,固然容易找到下棋的最優路徑,但是速度會太慢,跟它下人類選手會掀桌子的,所以在實戰中采樣不可能太多,那麼很可能就找不到最優下棋路徑,這也是為何在獲得能和業餘選手對戰後,難以再獲得大的突破的主要原因。

AlphaGo本質上大的技術框架還是蒙特卡洛樹,但是根本的不同在於把上面講的兩個落子策略和一個局面評估神經網路引到蒙特卡洛樹搜尋過程中。蒙特卡洛搜尋樹也需要對棋局盤面進行評估,AlphaGo採用了上面講的Value Network和傳統的采樣評估相結合的思路來做;在采樣進行過程中,要模擬兩個棋手對弈,AlphaGo採用了落子策略SL來模擬兩個對戰棋手;而落子策略RL則用在了Value Network網路中,我們講過Value Network是在RL策略基礎之上的,其作用也是類似兩個採取RL策略的棋手去下棋。

決定蒙特卡洛搜尋樹效果的其實主要有兩個因素,一個就是上面講的采樣數量,數量越大效果越好,但是速度會比較慢,在這點上AlphaGo其實並沒太在意;第二點是模擬兩個棋手對弈,那麼這個棋手棋力越強,那麼快速探索出優秀路徑的可能性越大,AlphaGo其實把工作重心放在這裡了,也就是那兩個落子策略和Value Network棋局評估策略。這也是為何說AlphaGo有技術突破的地方,因為它的重心不在暴力搜尋上,而是尋找好的下棋策略。






前一陣子網上討論Facebook圍棋AI 「暗黑森林」和AlphaGo誰先誰後問題,其實你看過他們各自發的論文就明白這種爭論完全沒有必要,之前有幾項工作都是結合深度學習學習落子策略和蒙特卡洛搜尋樹方法結合的文獻,但是效果應該仍然徘徊在和業餘棋手對弈的階段,包括Facebook的圍棋AI,本質上並沒有跳出這個思路。導致AlphaGo和其它工作最大的不同其實是那個通過3000萬局自我對戰產生的RL落子策略和Value Network,而這兩者在其中發揮的作用也是最大的,所以AlphaGo對圍棋AI產生質的飛越是無可置疑的。而沒有疑問的一個壞消息是,即使3月份AlphaGo輸掉比賽,從機制上講,AI勝過人類選手是必然的,這只是時間問題而已。

AlphaGo的意義不僅僅在於圍棋領域,由於DeepMind採用通用的AI技術來研發AlphaGo,其關鍵算法能夠平滑遷移到很多其它領域,並有望在很多其它領域獲得突破性進展。另外,我的個人意見,DeepMind是個令人尊敬的技術團隊,他們關注的都是深度學習中重大的問題並不斷有突破性成果出來,搞研究其實就應該以這種團隊作為榜樣。

上面這段看上去好像是要結尾的意思,其實並不是,我們最後再附上一小段技術流。

|深度學習網路架構
上面講過兩個落子策略以及棋局評估神經網路,其架構都是類似的,其中兩個落子策略的架構如圖5所示,棋局評估神經網路的架構如圖6所示。


圖5  Policy Network網路結構


圖6 Value Network網路結構

對於兩個落子策略來說,其神經網路的輸入是19*19*48的三維數據,19*19是一個棋盤的畫面,48是因為選擇了48類特徵來從不同角度描述這個棋盤,所以輸入是三維結構。經過12層CNN的卷積層,然後最後套上一個SoftMax分類層。輸入是棋盤局面S,輸出是針對這個棋盤局面,下面應該如何落子,所以SoftMax分類層給出的是各種合法落子位置的分類概率。AlphaGo就選擇概率最高的那個位置去落子。

對於SL落子策略來說,訓練數據就是3000萬<S,a>集合,就是人下棋的過程,S是面對的某種棋局,a是人接下來把旗子放到哪裡,這樣通過CNN網路,根據輸入棋局,就能學會人大概率會把旗子落在哪個位置,所以說它學的是人如何單步落子。3000萬看上去多,其實並不多,這是落子數量,真正的對弈棋局數量也就16萬局對弈過程,因為每個對弈過程包含很多落子步驟,所以總數看上去多而已。

對於RL落子策略來說,它學的是如何贏得一局,這裡用到了增強學習的Q函數。但是學習過程跟SL是類似的,無非是兩個AlphaGo先下一盤,然後看看是輸了贏了,並把輸贏的分數賦給整個過程中的每個棋局及其對應的落子步驟,這樣每個棋局及其落子步驟都會有個輸贏得分,根據這個得分調整之前學到的SL落子策略學習到的參數,這樣就通過自我對弈來學會如何贏得一局棋。

對於局面評估Value Network來說,其網路架構如圖6所示,這裡和圖5的結構稍微有不同,就是輸出層不是SoftMax分類,而是一個回歸函數,學習到一個數值,而不是分類。這個正常,因為它的目的是給當前棋局一個估分,而不是學習落子策略。它的輸入是從自我對戰的3000萬局比賽中隨機抽取某個時間的棋局狀態,並賦予這個棋局狀態一個贏棋得分,然後把這些數據當成訓練數據,交給這個神經網路去學習給定一個局面,如何給出一個贏棋可能的打分。

好了,整個過程感覺已經說清楚了,就到這吧,覺得寫得還算不錯的話….你看著辦吧,要知道,寫東西其實是個挺消耗時間和體力的事情,尤其是類似本文這種精品@^^@。

來源:布洛卡區

作者:張俊林

閱讀原文


關於作者:
ChinaHadoop-小象社區官方公眾號,專注大數據、數據分析、數據挖掘。

微信號:ChinaHadoop