由 AlphaGo 看演算法 聊聊演算法最基本的元素

由 AlphaGo 看演算法 聊聊演算法最基本的元素
Kisplay

image

在近期科技界最引人注目的新聞話題,就是電腦與人類進行圍棋對弈,名為 AlphaGo 的電腦擊敗世界排名相當高的韓國九段職業棋士李世乭。如果大家還有印象的話,在 1997 年時由 IBM 所發展的深藍擊敗當時的世界西洋棋冠軍 Garik Kimovich Weinstein,也引起相同的注目,電腦演算速度經過 18 年的進化後,終於可以在複雜度高上許多的圍棋中,擊敗世界上前幾強的職業棋士。

 

這項電腦技術上的成就,也讓這 18 年間的電腦運算速度成長有了一個重大里程碑,也就是說在相同時間限制內,在過往的電腦僅能有業餘五段的實力,但這次以分散式的運算架構,構築高達 1920 核心 CPU 與 280 核心 GPU,並搭配 Monte Carlo tree search 為基礎的演算法,來擊敗圍棋世界冠軍。能達成這樣的里程碑,其實要有兩個重要的關鍵,其一就是演算速度相當快速的電腦設備,另外一個就是合適又有效率的演算法,兩者缺一不可。

其實寫這篇前一直非常掙扎,如果寫得太詳細,那可能一篇文章要好幾萬個字,而且大家可能沒有興趣看,所以就學生時代所學習的知識,以盡量以簡單明瞭的方式來為大家說明演算法的基本元素,當然實際在設計演算法時並沒有那麼輕鬆自在,畢竟在研究所時也花了將近一年來研究驗證。

 

演算法其實簡單來說,就是找出解答的方式,這解答不一定是最好的結果,但是一定是合理的結果。就像是今天我們要解決 ”怎麼由新竹到台北” 的問題,就會有好幾種不同的答案,你可以搭高鐵、搭火車、搭客運、開車、騎 Gogoro、走路......等上百種方式,也會有上百種路線,這些都是解決方法。因應每個人的需求或是目的不同,所以也會有不同的方法。

舉個比較常遇到的問題,就像是常常會有讀者問我哪一支手機比較好,這也是有成千上百的解答,因為每個人因為其使用方式、經濟狀況,會有不同的選擇。所以接下來我會問你有沒有哪個品牌不要?你期望的價格範圍?你比較想要哪個功能?經過幾個問題的篩選後,就會找出一個或多個答案,這就是演算法的過程,這答案可能不是每個人的最好答案,但是卻是經過這個人的喜好訂定評估指標,並在許多條件限制下所得出來的合理最佳解。

 

 

好的評估指標

每一個問題都有成千上百個答案,究竟哪個答案比較好呢?這時候就要利用評估指標來做為好壞的依據。那什麼是評估指標呢?我們來使用 “怎麼由新竹到台北” 作為例子來解釋。今天如果某人希望用最短的時間從新竹到台北,我們所期待的就是以最少通勤時間為主,評估指標就是最短時間;如果某人想要的是最節省的方式,那評估指標就是花最少的錢。演算法中的評估指標非常重要,這指標將用來計算評估你解答的品質,用以找出好的答案。當然,評估指標可以是綜合指標,也就是可以把兩個以上的指標放入一個評估的算式中,這接下來我們會繼續聊。

 

 

合理的基本假設

當有了好的評估指標後,你就可以把有可能的 “怎麼由新竹到台北” 方式,來套入評估指標中計算,但這其中有個非常大的問題,底下直接用舉例的方式說明。

如果說 “怎麼由新竹到台北” 我們以最短時間來做為評估指標,我們就要開始考慮高鐵、火車、開車…等交通方式來評估,大部分的朋友一定會選擇高鐵,但如果不計成本來說,高鐵不一定是最快速的,今天如果請 F1 車手開著頂級跑車由新竹載你到台北呢?或是有直升機專程接送呢?

所以在這樣的狀況下,我們要有基本假設,把目前某人能力範圍外的選項拿掉,例如說他有懼高症,那我們就會把直升機選項拿掉;他不想花超過 1000 元,就可能把頂級跑車選項拿掉…,這樣所找到的解,才會是合理又正常的解。

但有沒有人想要便宜又快速的方式由新竹前往台北呢?這絕對有,在這狀況下,我們又要回到評估指標那邊,把時間與花費做成一個綜合性的指標,簡單說,就是把時間與花費都加上權重來衡量。這時候你可以問那個麻煩的人說,速度與金錢對你由新竹前往台北的重要性,如果速度佔 70% 重要,金錢佔 50% 重要,那你的評估指標就可以做成 速度* 70% 金錢 * 50%,寫到這裡專業人士一定會嗤之以鼻,因為我少了一個速度與金錢的標準化,但寫那個就太過麻煩了,反正知道要標準化的人也不用看這篇啦!

 

 

選擇演算法

有了評估指標、基本假設後,接下來就要擬定演算法了,對於正常的大家來說,最直覺簡單的方式,就是把有可能的選項一一放入評估指標中,看看哪個比較好就選哪一個,這就是所謂的窮舉法。窮舉法對於小型的題目來說,是非常好用的方式,因為你不用花時間去思考其他演算法,因為使用窮舉法所花的時間都比你驗證其他演算法來的短,但對於大型題目來說,窮舉法就不是個好方法。

這次就直接用主題所說的圍棋來舉例,圍棋有 19*19 的位置可以下,所以第一手就要考慮 361 種可能,如果是這樣就簡單多了,但事實並非如此。因為第一手下完後,你必須開始考量對手下的位置,也就是有360 個可能,接這還要考慮換你下的位置一直到分出勝負為止,中間還要考慮到子被吃掉後的空間,所以光想就頭皮發麻,更不要想說用窮舉法了。

那有沒有更快速的方式,當然有,就像是這次 AlphaGo 所採用的 Monte Carlo tree search並搭配Policy Network 與 Value Network 所設計的演算法。另外我在研究所的論文用的禁忌演算法、模擬退火法…也都是歷史久遠但都經過各種題型來演化修正的利害演算法。這些方法都可以在反覆求解的過程中,去除勝率較低的方式,得到一個好的解,但並不一定是最佳解。而 AlphaGo 的演算法也是,他在有限時間內,只能找出勝率最大的方式,並無法找到 100% 獲勝的走法,所以電腦效能絕對是與演算法同等重要的關鍵所在。

 

 

驗證演算法

既然說演算法沒有辦法 100% 找到最佳解,那你怎麼證明你的解法是好的?最一般的方式我們會從相同題目背景下,以小規模的方式找出最佳解進行驗證,一般來說就真的會使用窮舉法或是保證可以找到最佳解的方式來證明你的演算法是好的。若以圍棋為例,會將棋盤縮小到 10*10 甚至更小,在驗證過程中,會以下圍棋時的演算法與窮舉法來對弈,如果最後的棋力不分上下,這就表示在小規模中可以有最佳解或是很好的解,這也可證明演算法的實力。而在驗證演算法時,會花掉非常多時間,因為上一段也說明了窮舉法的組合相當龐大,以原題目規格來說,可能都要好幾年才求的出答案,所以一定要縮小規模來驗證。

另外,在同一種題型下,大多會有 Benchmark 的資料可參考,也就是前人在相同題型下得到的答案,如果你可以有比他好的答案,又花比較少的時間(電腦等級也有差異),這表示你的演算法是很優秀的。

 

上面聊到的,就是完成一個演算法所要的基本元素,當然其中還有很多機制,可以讓你更快找到更好的解,希望大家可以由這些簡單的說明,更了解演算法一點。而回到 AlphaGo 來說,他真的是無法擊敗的嗎?事實證明他是可以擊敗的,這也是每個演算法中因為演算時間限制下,只能找到比較好的解,但因為運算速度太快,所以可以考量的棋路會比人類高出許多,所以是不容易被擊敗的。過幾年後,當電腦運算效率更好時,或許真的可以讓人類無招架之地,但也僅限於圍棋這還算有範圍的問題上,要像是電影 A.I. 人工智慧的機器小孩一樣有思考,還有相當長的一段路要走。

image

科技學堂
Kisplay

Kisplay為Saydigi.com總編輯,喜好各式各樣科技生活新鮮事,也樂於以輕鬆自然方式將新知傳達給讀者,讓科技話題與生活品味永遠圍繞在彼此身邊。
--
■作者:Kisplay
■主題:3C、生活品味
■連絡方式:Kisplay@gmail.com
■FaceBook:https://www.facebook.com/KisplaySayGoodbuy/

.
一起用好點子過好生活吧!