2016年3月13日 星期日

李世石「神之一手」與AlphaGo的「廢棋」

  今天李世石終於贏了第一場,不小心又猜中了。那些猜五比零的又破功了。這一局堪稱超級精采,尤其李世石對時間的掌控真是超出人類水平,無可挑剔!那種在一分鐘內不停的決策與利用電腦思考時間的「後台時間」運用(一般用來指稱電腦軟體利用人類棋手思考時間進行預設性搜索的時間運用方式,其實就是電腦模仿人類的做法。這個只是有趣的說法。),比前幾局控制得更好,甚至已經達到駕輕就熟的地步。而最終,成果扭轉了這場比賽最大的不利因素:時間。以180子逼AlphaGo投降了!其中第78子被稱為「神之一手」!
  李世石在這場世紀大戰裡面至少創下兩個記錄,一是第一個九段高手敗給電腦(AlphaGo),二是第一個九段高手下贏了電腦(至少一盤)。所以日後關於誰再與AlphaGo下棋,大家的興趣就不再濃厚了。因為第一個打贏的也是李世石(局部戰役),第一個打輸的也是李世石(全局),日後AlphaGo再經過訓練,估計還會更強,幾乎也是不用說的。Google的聖杯已經拿到,眾人免費看了一場超級精采的世紀對奕,大家皆大歡喜。
  從四場比賽看下來,Google圍棋即時講評Michael Redmond(唯一非東亞裔九段)常常能猜中AlphaGo的著法,如果詳細計算相合次數,以此為判斷基礎,AlphaGo在1202個CPU與176個GPU以及目前的演算法資料庫下,相當於人類九段的高手水準,或者「稍微」略高一點。如果考量到人類心理與生理因素對人的不利影響,可以「直覺」的說AlphaGo的棋力相當於九段。
  至於目前的AlphaGo仍然可以被九段高手擊敗已經是事實了。因此也就不用再多做分析,或者提供「方法」了。這一盤比較有意思的是,AlphaGo終於下出了我期待已久的「廢棋」(機率很低,大概只有李世石這樣的高手才能逼電腦下出來,而且幾乎可能也不多!一般而言廢棋其實不廢,只是功用太低了!),或者被稱為「死子」。這種棋之所以會被下出,不是AlphaGo的程式設計有什麼問題,而是因為,稍微離題一點,相信玩過(電腦版)國際象棋、中國象棋甚至日本將棋的棋類遊戲開發者或者敏銳的讀者都可能遇到過這種電腦下「廢棋」的狀況。電腦之所以下廢棋,正是因為它在當時的「時間控制策略」與「搜索深度」的綜合條件下已經沒法發現更好的走法,於是它選擇走出了一般棋軟在面臨被「將軍」以前都會產生的「廢棋」。事實上,如果時間多一點或者深度多一點,這著棋都可能不會走出,或者不會在那個當下走出。(搜索樹被引導到其中幾條路徑,而這些路徑的搜索與判斷時間消耗了多數的時間,來不及再對其他路徑進行同樣深度的搜索。)
  一般而言,國際象棋、中國象棋、日本將棋之類的遊戲,輸贏判定非常簡單,所以出現這種棋的情況也不少,只要人類棋手夠高段就行了。所以從這裡又可以證明,AlphaGo在當前的硬件與軟件配置下,棋力就相當於九段的程度。一如李世石的說法,還沒有到達「神」的境界!或許哪一天會達到吧,但一如更深的藍打敗卡司帕洛夫之後,就不再有人關心電腦是否已經「無敵」了一樣。相信這種情況也會出現在圍棋領域。同時,由於AlphaGo在這樣的硬件配置下對單機版AlphaGo(48個CPU+8個GPU)擁有70%的勝率,因此單機版的棋力大概介於九段與八段之間或者就是九段(因為這很難判斷)。不管如何,AlphaGo的技術短期內都不太可能被圍棋學院拿來訓練棋手,也幾乎可以肯定。至於日後誰能研發出在單顆CPU的個人電腦甚至筆記電腦上或者平板上就能完敗人類的圍棋軟體,至少可以肯定這一天應該不會這麼快到來。所以圍棋高手應該還有很長的一段時間不用改變任何「技術」。
  不管是現在的AlphaGo或者之前的更深的藍,甚至類似2006年浪潮杯的棋天大聖(中國象棋電腦冠軍),其實都是用搜索來決定下子。換句話說,這些棋軟並不存在什麼複雜策略的構思能力,而是一種路徑導向的搜索能力。這是一種基於勝率的全局式的下法,因此直白的說並非人類可以學習的,或者正確的說法是人類早就知道怎麼做了(日後有機會再交代)。在這種情況下,一個程度夠高的棋類軟體對於不同程度的對手會有不同的反應,一如之前所說,那種反應在程度低的棋手上,電腦會根據棋手拙劣的下法而給出相對不那麼高明的走法,而這就容易讓人類高階棋手產生「錯覺」。簡單的說法就是,電腦本身的方法是固定的,但隨著棋手的程度會有不同的應對方法,而一個最根本的原則就是下出勝率最高的一個走法。如果以人類的觀點來理解,有些段數不夠的來看高級棋軟的走法就可能「不明所以」或誤以為是「劣手」,其實那都是幾十步內最佳的走法,但可能「不具備」或者更精確的說「不吻合」任何人類的策略概念。(可以用「大巧若拙」來形容這種下法,由於這種下法牽涉到太深的思考,一般而言超出了人類的計算能力。但只要穩扎穩打、攻守兼備,和棋不難,贏棋有望。這次李世石有幾次的選擇都選擇比較安全的走法,可以說是最好的策略。因為太複雜的形勢,不一定對電腦不利,卻鐵定對人腦不利!)但這種棋以人類的理解方式來說,就是在對手不夠強大的情況下(雙方程度差距大),這種棋與對手的下法幾乎無關,也就是電腦不會管低級棋手怎麼下,因為棋手的下法根本不起任何作用,因此電腦的下法不是針對棋手的下法做反應,而是自己走自己的!
  在這種全局式下法而非策略導向的下法的情況下,最簡單的贏棋策略,只要人類能突破那道「檻」(深度,譬如AlphaGo的深度在第幾層+1即可)就能找出下贏的辦法。這種方法對付五子棋、國際象棋、中國象棋等都還不是很難,但對付圍棋幾乎「不可能」!(複雜的方法就暫時不說了)主因在於圍棋的「語彙」是不固定的,它的棋形即便有也太過靈活,且需考量到對方的應對方式。不像國際象棋、中國象棋的「形」或者稱「棋子的功能」(形產生功能,功能附著於形)是固定的,國際象棋、中國象棋、日本將棋的棋子的功能是固定的、走法也是固定的,如果要類比,就相當於高階語言如C++、Java(國際象棋、中國象棋、日本將棋)與機器語言(圍棋),高階語言還有很多固有的函數庫可用,程式設計相對簡單。
  我在十幾年前就開始把策略的研究觸角伸向了棋類遊戲,因為人類世界的主要兵法的規則都已經被總結在《策略的哲學》中了,但人類的戰爭歷史與案例其實多數都在重複與模仿,案例也不夠多,至少比起動輒數萬筆的棋類遊戲對局,那實在是難以比擬。因此,我開始將這些棋類遊戲的規則進行總結,企圖建構一套完整的通用策略框架,可以適用於圍棋、國際象棋、中國象棋與日本將棋等多種棋類,也可以通用於人類世界。之所以必須吸收棋類遊戲的策略,結合傳統的兵法策略,原因是一個基於方法論的思考。可惜工程進行到一半,一如其他計畫一般,被暫時擱置了。其中一個理由就是這樣的通用策略本身跟強AI有直接關連,因此,或許明年會重啟相關研究做個總結吧!有機會,就會直接設計成棋軟直接放在網路上供人挑戰。
  其他的,下次再說了!最後,也恭喜李世石扳回了一城。相信這對於許多「平民」而言,會是莫大的鼓舞!

相關新聞補充

李世乭說,「AlphaGo露出了兩個弱點,基本上,比起執白,它比較畏懼執黑;另外,它碰到沒有意料到的一手時,它會出現一種BUG型態,一連下幾手臭棋,當它意想不到時,它的對應能力就顯得較差。」

朔雪寒註:「它碰到沒有意料到的一手時,它會出現一種BUG型態,一連下幾手臭棋」,這可能是搜索樹的問題,可能有三種情況,一是AlphaGo自己對奕時沒能下到相應的情況,二是這一著棋在即時搜索中處於有太多分支而不容易剪裁或者不容易導向正確著法的情況(需結合盤面來考量,牽涉到評價函數),三是即使包含在搜索空間內也因為其他分支耗時太久未能在正確的著法上進行深入探索,或者在正確的著法上因為不夠深入的評價不高而被提早放棄。這種事情跟評價函數有很大的關係,有其他未見使用的方式可以修補,但只要深度夠(硬件、演算法夠快),其實足以抵消一般評價函數不夠客觀的缺陷。不幸的是,圍棋的可能性太大,要深度夠不那麼簡單。最好的辦法還是從演算法著手改良。

http://news.rti.org.tw/news/detail/?recordId=257642

報導指出,AlphaGo以星小目佈局,行至黑11下法與第二局如出一轍,引發棋界對超級電腦的必勝策略或有固定套路的猜測。但李世乭白12變招後,AlphaGo在下邊拆邊,不再模仿。李世乭此局使出取實不取勢的戰術,在左右的下角和兩邊撈取實地,AlphaGo則在中央取勢,並在上邊形成大模樣。

朔雪寒註:其實這就是一個簡單的擊敗電腦的「方法」,只是因為李世石只有五局對局機會,因此重複局面的機會不高,一般高手也可能不願意依照前幾局來「重下」,但這確實是突破那道「檻」的其中最簡單的方法之一。「行至黑11下法與第二局如出一轍,引發棋界對超級電腦的必勝策略或有固定套路的猜測。」要說是固定套路其實不正確,應該說是「這條路」在原本的計算中對電腦具備更大的勝算,有點類似國際象棋與中國象棋的開局法(如反宮馬)。因此,如果原本的計算深度不夠深,或者對奕時電腦自身沒有下出李世石的類似著法,就會誤以為這條路很穩當。但從另一方面來說,即便電腦發現這條路有這樣的一條不歸路,也可能會列為好的開局法,只要是譬如平均勝率大於50%,就可能繼續採用。

但在李世乭侵削中央的黑陣時,AlphaGo在右邊接連下出令人費解的走法,吃虧不少。當李世乭下出白78挖的妙手後,AlphaGo應對失當,不僅不彌補薄弱環節,還在左下角下出極端無理的黑97。李世乭隨即對左邊黑大龍施壓,並將上中央的白棋孤子聯繫起來,踏破黑色城池,鎖定勝局。

報導指出,據DeepMind首席執行官公司哈薩比斯(Demis Hassabis)在社交網站披露,AlphaGo自行計算的勝率由黑79手時70%銳減到黑87手的50%以下。此後AlphaGo四處攪局,李世乭不為所動。每秒計算10萬種棋路的AlphaGo在大勢已去後仍苦撐30多手,但李世乭殺入AlphaGo下邊唯一的大空後,AlphaGo認定絕無勝算,於180手棄子投降。

160313_w1vvzt
(棋譜取自:http://www.board19.com/news/)

朔雪寒註:
  第97棋就是我所謂的「廢棋」。一如報導所說,87手以後其實AlphaGo已經「亂」了,類似於象棋軟體即將被「將軍」的「前奏」「反應」!97棋是其中最類似與經典的著法。

http://news.rti.org.tw/news/detail/?recordId=257638

2 則留言:

  1. http://news.sina.com.tw/article/20160313/16380025.html 「大衛席爾瓦:AlphaGo不會根據對手來下棋,只是通過計算來確定每步棋勝率是多少,選擇最有可能獲勝的落點。」其實這是就兩個層面來說,記者的提問方式問的是會不會根據棋手來設定,但事實上每一盤棋都是對手與自己下出來的,除了本文所說除非對手下出太弱的棋,否則一般棋軟即使根據勝率來下,這種結果也是在整個盤面上來進行反應,因此從邏輯上來說,它還是在根據棋手來下,只是不是記者所理解的那種情況。

    回覆刪除
  2. http://news.rti.org.tw/news/detail/?recordId=257642 

    回覆刪除