er_jason 對孩子說的話: 網路編碼迷蝴蝶

2007/07/20　第97期　訂閱╱退訂　看歷史報份

	科學頭條新聞		網路編碼迷蝴蝶

	發燒新鮮事		電腦進軍圍棋界

	科學家觀點		拳頭上的風雲紀事

	本月優惠活動		未來領袖必修顯學---快看7月最新優惠！

	好康報報		「人與自然」科普寫作桂冠獎-找科普文章接班人

網路編碼迷蝴蝶

來自香江的一個小故事，戲劇性地在通訊界掀起一股全球熱潮;

撰文╱李碩彥（Shuo-Yen Robert Li）

通訊是個古老的行業。一封郵件常常要經過好幾個郵局中轉，每一個中轉站所做的事就是「儲存轉發」（store-and-forward）。古今中外，資訊的傳遞方式都採用儲存轉發，也就是信號複製。萬里長城上的烽煙如是，今日的網際網路（Internet）亦然。

複製信號是最自然的通訊方式，但資訊量太大時容易產生網路塞車的麻煩。若以圖中的網路為例，假設每個箭頭表示傳送一個信號，信號值是0或1，由A點發出兩個信號x和y，都要送到B點和C點。困難出現在M點收到x和y之後，它只能轉發一個信號，若轉發x，則B點收不到y，若轉發y，則C點收不到x。這時「網路編碼」提供了一個解決辦法：讓M點送出一個代表x與y之異同的信號，當B點收到此信號與x，即可解出y；同樣地，C點也可解出x。

這張圖，就是表達網路編碼概念最著名的「蝴蝶網」。研究網路編碼的論文，到現在已經累積了數百篇，其中大半一開始都重述一遍蝴蝶網。有些人畫蝴蝶網的時候，會略去A點，那麼圖形就更像蝴蝶了。

網路烽煙今古似

事實上，如果蝴蝶網中的M點一定要用儲存轉發的方式，把x和y兩個信號都傳遞到B點和C點，那麼就只能先轉發兩個信號其中一個，再轉發另一個。但是如此一來，就需要用兩倍的時間來完成通訊，也就是說信號的「傳輸率」降低了一半。這更意味網路編碼比儲存轉發有優越之處，雖然幾千年來用的都是後者。

圖中的x♁y信號，既不是x也不是y，而是兩者間一種數學運算的結果。它雖然簡單，卻也是一種「編碼」的形式。事實上，x♁y是所謂的「二進位和」（binary sum），它不僅代表一種編碼形式，也是數學上的「線性」編碼形式。線性編碼的數學基礎非常深厚，所以比「非線性」編碼容易實現，因此也比較實用。

當兩條或多條信號傳輸的路徑局部重疊時，用編碼來提高信號傳輸率的技術可稱為「共路徑編碼」。幾十年來，這技術被零零星星地用在各種通信網路，其中也包括一些我早期的研究。蝴蝶網是共路徑編碼之一例，有時多條路徑重疊的部份僅在由起點出發的第一步，56頁的圖就是一例，圖中x和y兩個信號都從A點向B、C、D三點傳遞

日思夜夢究真理

回想起來，網路編碼的起源充滿了戲劇性。1997年中，我開始沉浸於寫作一本名為《代數交換論及其寬頻應用》（Algebraic Switching Theory and Broadband Applications）的書。我在這領域15年的研究成果幾乎都沒有寫成論文來發表，只想用兩、三年的時間彙集成一本書，難度可不低，因此需要長期閉關修行。當時每個夜晚都會醒來數次，黑暗中寫下夢裡得到的關鍵字句或理念，翌日早晨再將橫豎潦草的字跡整理出來。

那年夏季，我在香港中文大學的同事楊偉豪應德國俾勒菲特大學的阿斯威第之邀，出訪該校，並結識了蔡寧。楊偉豪曾與美國南加州大學的張珍共同研究過衛星通訊網的信號編碼，用到了共路徑編碼技術。旅德期間，他與蔡寧一起研究共路徑編碼的信號傳輸率。楊偉豪9月返回香港中文大學，並拿了例子給我看。

不久之後，楊偉豪與蔡寧合擬了一篇初稿，從「資訊理論」（information theory）的觀點來闡明該圖的理論根基，並找我評論。當時我想專心寫書，所以只想快點應付過去。結果我發現文中某一個定理是錯的，我用很抽象的話對楊偉豪解釋為什麼那是一個錯誤，雖然這個解釋對我自己而言可能都太抽象了。

楊偉豪沒聽懂我的解釋，依然認定那個定理沒有錯，所以再三找我討論。他要我乾脆給出一個反例來徹底推翻那個定理，或者明確指出其數學證明錯在哪裡。為了避免細讀那個證明，我只好試著做前者。當時我拿起筆在白板上畫起來，福至心靈，畫出了恰好構成反例的「蝴蝶網」。楊偉豪看了略有感觸，將蝴蝶網也畫在他自己辦公室的白板上，同時又做成「標本」，掛上另一幅牆。

麻煩才剛開始。每日望著白板上的蝴蝶網，我深深相信，不論蝴蝶網背後的理論基礎是什麼，它都會是解釋這理論的最好圖例。此外，我已對楊偉豪宣稱：蝴蝶網背後的基本原理一定是很簡單的「線性代數」。於是我撇開寫書，日夜思索到了11月，寫出一份數學初稿，將它交給楊偉豪。封面上有我的自白：「這項工作並沒有我頭一百回想像得那麼簡單。」。…more

【意猶未盡嗎？欲閱讀完整全文，請參閱《科學人》雜誌2007年7月號】

電腦進軍圍棋界

新的圍棋演算法現身，目標是戰勝人腦！。

撰文╱佛蘭克（Karen A. Frenkel）
翻譯╱王怡文

10年前，IBM的西洋棋程式「深藍」（Deep Blue）在一場六回合比賽中，打敗了世界冠軍卡斯帕洛夫（Garry Kasparov），這個事件建立了一個里程碑，迫使人類再度讓出另一種策略遊戲的主宰權。唯獨亞洲的圍棋，看來可能是計算機科學的罩門，能讓人類狠狠擊敗電腦。不過，現在出現了一種新的演算法，它能與棋力高強的人類棋手匹敵，而且獲勝。

對電腦程式設計師而言，圍棋已證實是項艱鉅的挑戰，因為這個遊戲的複雜度高深莫測。這種棋戲是在九乘九或十九乘十九格線的交叉點上，放置黑棋與白棋，以佔領地域並且包圍對手為目標。特別是在大棋盤上，每一手的可能棋步都非常多，對弈當中平均每手可能的位置有200種，相較之下西洋棋只有數十種。而且圍棋的分支因數（branching factor）相當可觀，對於棋盤上有N個位置的狀況來說，可能的盤面有3N種，因為每個位置有黑棋、白棋或空點等三種可能性。小棋盤的合理盤面約有1038種，大棋盤則大約有10170種。此外並非盤面上棋子較多就必定獲勝，棋手必須兼顧局部與整體盤勢。

為了對付為數如此繁浩的選擇，人工智慧專家設計了演算法來限制搜尋次數，但那些程式都未能在大棋盤上擊敗棋力較強的人類。2006年秋天，有兩位匈牙利研究人員發表了一種演算法，勝率高出當時最佳圍棋程式大約5%，而且能夠在小棋盤上匹敵職業棋士，他們是匈牙利科學院計算與自動化研究所（位於布達佩斯）的柯西斯（Levente Kocsis），以及現任教於加拿大亞伯達大學（位於艾德蒙頓市）的季佩斯伐利（Csaba Szepesvari）。他們所發展出的這種演算法，名為「樹狀結構信賴上界法」（UCT），是從著名的蒙地卡羅法擴充而來。

蒙地卡羅法首次應用於圍棋程式是在1970年代，這個演算法的原理有點像政治民調：進行統計採樣以預測更廣大群眾的行為或特性。這個演算法在下圍棋時，會在背後試玩大量的隨機棋局來為候選棋步打分數，然後將棋步排名。然而，在每一種盤面中採用分數最高的棋步，並不保證能夠贏得棋局。相反的，這樣只是限制了可能棋步的數量。

UCT運用蒙地卡羅的方式又更進一步，它鎖定最可能獲勝的棋步，進行搜尋，柯西斯表示：「主要概念在於棋步的採樣有選擇性。」他解釋說，這個演算法必須取得一個平衡，既要試用當時看來最佳的選擇、以找出可能的弱點，又要探索「看起來比較不完美的選擇，以確保不會因為先前的估算錯誤而遺漏掉好的選擇」。

UCT計算出棋步的索引值，並且選擇索引值最高的棋步。這個演算法利用勝率（代表該盤面發展成勝局的頻率）以及該盤面已考慮過但尚未採用的次數，來計算索引值。UCT在記憶體中建造一棵決策樹，利用它追蹤這些統計數字。當UCT遇上之前未考慮過的一個棋步，就將棋步加入決策樹中，然後隨機下完剩餘的棋局。

接著，UCT判斷隨機棋局終局的輸贏，然後更新棋局中所下過全部棋步的統計數字。如果索引值等於該棋步的勝率，演算法很快就能鎖定最可能致勝的路徑；然而最初的成功路徑，並非最後產生致勝棋步的保證，所以在選擇棋步時，UCT會將贏率加權計分，較少被考慮到的候選棋步權值較高。這個點子是從吃角子老虎問題（bandit problem）借來的──賭徒玩數台吃角子老虎而不知道它們的平均報酬率時，選擇性地加權計分，能產生最大的利益。

南巴黎大學的傑利（Sylvain Gelly）和巴黎近郊法國綜合理工學院的王一早（Yizao Wang）兩位數學家，已經將UCT整合進一個他們命名為魔圍棋（MoGo）的程式，它跟之前最先進的蒙地卡羅擴充演算法相比，勝率高出95%，目前魔圍棋已經是最頂尖的圍棋演算法，它在今年春天展現實力，在九乘九棋盤上贏了棋力高強的業餘棋手，在大棋盤上也擊敗了棋力較弱的棋手。傑利說，UCT程式寫起來簡單，而且還能再改善。因此柯西斯說，最後一道防線被攻陷，終結圍棋界由人類職業棋士稱霸的時代，也許10年內就會發生。

【本文轉載自科學人2007年7月號】

拳頭上的風雲紀事

撰文╱曾至朗

他走進我的實驗室，頓時讓我感到侷促，我那原來還算寬敞的實驗空間，一下子就顯得擁擠不堪。以前在電視螢幕上，看他在方形拳擊台上快速躍動，攻勢凌厲，並不覺得他有多高大，如今在真實世界中看到他本人，六呎三吋（合191公分）的身高，魁梧健壯的體態，兩眼炯炯有神，一副胸有成竹模樣，加上自信滿滿的流利言詞，確實讓我感受到他那「王者之風」的氣度。他是原名克萊的穆罕默德•阿里（Muhammad Ali），公認為上個世紀最偉大的拳擊手。我們這些曾經在美國運動酒吧的大型螢幕上，觀賞過他幾場激烈大賽後迷人風采的人，都認為「偉大」這個封號，他絕對是「當之無愧」！

他來到我的實驗室已經是25年前的往事了，不再是當年那位叱吒風雲的拳王，他退出競技的擂台，把精力轉向推動社會公益的實際行動，以深化年輕時的民權鬥士理念。他專注於關懷弱勢族群的學童教育，成立基金會資助學習有困難的兒童，因此，前來我們研究「兒童閱讀困難」的實驗室參觀，想知道從跨語文（英文、中文）的比較研究中，可否找出一些教與學的竅門，來幫助貧民窟的兒童克服學習障礙。

阿里對中文字的排列很感興趣，認為方塊字美得不得了，但要記住那麼多不同的字型，一定要非常聰明才行，當我告訴他學中文閱讀的兒童大概有5 ~ 7 %患有先天性失讀症（developmental dyslexia），和美國及歐洲使用拼音文字的國家裡學童患有先天性失讀症的比例是差不多的，他聽了覺得很驚奇，想知道我們怎樣去研究閱讀的認知歷程，我就把他帶進我的認知心理實驗室！

一進門，阿里就東張西望，似乎在找尋什麼，我引他走到桌前，他看著眼前簡陋的設備（桌上只有個小型的電腦螢幕，而距離螢幕約一公尺處有兩個讓左、右食指可以按鍵的機鍵），一臉失望與不解，沉默了一會，有點不耐煩的說：「就這麼簡單的設備嗎？開什麼玩笑，這那能測量人類複雜快速的認知運作啊！？」

原來，他認為人的認知體系那麼複雜，沒有設計精密的「複雜」儀器，怎麼可能測量出來，所以預期一定有些大型且造型也很驚人的實驗儀器。我說：「您說對了一個很重要的概念，就是速度。那兩個按鍵就是要很準確的測出一個人在知覺到螢幕出現各種不同刺激形象時，由刺激出現到手指按鍵所需的時間。」

阿里濃眉一挑，我繼續接招：「當我們對呈現在眼前的刺激物做不同的分析作業時，簡單的決策比複雜決策所需的反應時間要快多了，靠著這個簡單的設施，就能把內在的心理計算時間和認知運作的複雜度，很有規律的結合在一齊。這些儀器設備看起來其貌不揚，但只要實驗設計得好，就能很巧妙的由簡入繁、建立客觀的科學理論，讓我們去了解更多的心理現象了。」

阿里半信半疑，坐下來說：「我能試試嗎？」我說：「當然！」就請他把右食指放在右鍵上，告訴他：「螢幕上出現紅點就按鍵，不管出現在左邊或右邊。」很快的量了50次反應時間後；我請他的右食指保持在右鍵上，但同時也把左食指放在左鍵上，然後告訴他：「紅點出現按右鍵，綠點出現按左鍵。」也做了50次，反應時間都由電腦自動記錄下來。

接下來，我要他把兩手交叉，右食指放在左鍵，而左食指放在右鍵，又再提醒他：「紅點按右鍵，綠點按左鍵，不要弄錯了。」阿里依照指示，深知小心才能免於犯錯，但見他神情凝重，眼光也更專注了，很快的5 0次又做完了，他吐了一口氣說：「我了解你剛剛說的那些話了。這三個作業都是看到刺激（紅點或綠點）就按鍵，看來都一樣，但由簡單的單一反應，到區辨顏色，到選擇手指，確實讓我感到心裡的負荷越來越大，到了最後要兩手交叉，則又要更加專注以避免按錯鍵，要反應，也要不反應，更要整理出反應鍵的空間位置與按鍵手指的左右關係，其複雜的程度確實也給我很大的壓力！現在請你讓我看看我的反應時間，是否真的和這個心理複雜度有相關！」…more