星期五, 9月 30, 2005

再談 AB-game

年輕時,很容易手癢、想寫程式來解一些益智問題。

AB-game 也算是頗有趣的遊戲。因而,我在很久以前,就曾寫一支程式來(和使用者、或電腦自己)玩 AB-game。雖然那時自己其實對程式設計懂得很少,但最後還是能用 BASIC 語言,笨笨地、很暴力地 (ad hoc) 寫出「還算能夠玩」的程式。

回想起來,雖然頗覺得當時「不知天高地厚」,但心裏仍不免懷念那段年少輕狂的過去。也是因為最近試圖整理「從前感興趣的問題」,讓我回想起 AB-game。

從遊戲規則來看,要寫一支程式來檢查使用者的猜測,是相當容易的。程式可先依亂數選定一個數字,然後檢查使用者輸入的數字,回答幾 A 幾 B;直到使用者猜到程式所選的數字(回答 4A0B)為止。另一方面,要寫一支程式(扮演甲的角色來猜乙所選的數字),自動猜測使用者心裡所想的數字,似乎就不是那麼容易。

稍微分析一下,我們知道,在還沒有猜測前,乙選的數字有 10 x 9 x 8 x 7 = 5040 種可能。所以,即使乙並不需要回答幾 A 幾 B (僅需回答「是否猜中」),最糟的狀況下,我們也可以將這些可能的數字一個一個地拿來詢問「是這個數字嗎」,而在 5040 步內,猜中乙的答案。

而我們現在有乙所回答的「幾 A 幾 B」資訊,該如何利用它呢?最直接的方式,就是利用這項回答,從 5040 種可能(或者稱作「可能性空間」,possibilities space)裡,將不符合的數字刪掉。例如,如果猜測 1234 而得到回答 0A1B,那我們知道,答案不可能是 1234 (否則,回答應該是 4A0B)、不可能是 1567(若答案是 1567,猜 1234 的回答應為 1A0B)、也不可能是 8912 (回答會是 0A2B 而不是 0A1B)...。

因此,甲每猜測一次,就可以藉由乙的回答,從「可能性空間」裡,刪除一些「不可能是答案」的數字(也就是說,每一步都可以縮減可能性空間的大小)。於是,還保留在可能性空間裡的數字,就是「經過一連串猜測與回答後,仍有可能是答案」的那些數字。而我從前的程式,就是任意地從可能性空間中挑選出一個數字,來當作下個回合的猜測。

接下來的問題是:若演算法是任意由可能性空間裡,挑選一個數字,那麼最壞的情況下,需要猜測多少次呢?或者,更進一步:平均起來,需要猜幾次才能得到答案?還有:雖然可能性空間裡的數字,都有可能是答案;是否會有一些數字,它比其他的數字「更有可能」是答案?

雖然經過了這些年、似乎累積了更多電腦相關的知識;但我除了對從前的程式實作,有些改良的意見外,竟然也沒能想出更好的演算法與結果呢!

星期三, 9月 28, 2005

AB-game

雖然不知道 AB-game 的正式名稱,但我猜想,很多人都曾玩過類似的遊戲。

它是一種兩個人玩的遊戲:甲乙兩人各自在心裡想一個四位數字 (4 digits),然後輪流讓方猜測這個數字(而自己則對此猜測的數字,依下一段的說明做回應);能夠先猜出對方數字的人就算是贏家。

對於對方的猜測,回答的規則是這樣的:假設自己設想的數字是 a3a2a1a0(四位數字,在此千位數為 a3,百位數為 a2,十位數為 a1,個位數為 a0)而對方猜測的數字是 b3b2b1b0。若 x 為集合 {i | ai=ai} 的個數 (cardinality),而令 y 代表集合 {i | ai=bj, i ≠ j} 的個數,則我們的回答就是 xAyB。

換句話說,x 是「數字相同、位置也相同」的個數,y 是「數字相同、但位置不同」的個數。例如,若設想的數字是 1234,而對方猜測 3614,則我們回答 1A2B(數字 4 出現的位置相同;而數字 1、3 出現的位置不同);若設想的是 1357,對方猜 7890,則回答是 0A1B (沒有數字出現在相同的位置上;而有一個數字 7 出現在不同的位置)。

在 AB-game 裡,我們通常會要求猜想的四位數字不可重覆;也就是說,要求 ai≠aj (i ≠ j)。至於第一位(千位數)a3,一般則可以為零。因此,可猜想的數字,共有 10 x 9 x 8 x 7 = 5040 種可能。

右圖是一個可能的猜測序列。乙所選定的數字為 8590,而甲的運氣不太好:他先猜 0123,得到回答 0A1B;接著猜 1456,又得到一樣的回答 0A1B;如此這般,甲總共花了八個步驟,才猜對 8590 這個數字。

花了這麼多篇幅介紹這個遊戲,我到底想說些什麼?

我想說的,是一段聽聞與經驗有些衝突,但沒有經過驗證 (prove or disprove) 的情事:印象中,似乎曾聽人說過,「最糟的狀況,也僅需猜六次」。然而,在我的記憶裡,雖然在大多數情況下,的確只需要猜六次,但我似乎也曾有要猜七次(或七次以上)的經驗。

所以,為什麼只需要猜六次,就可以得到答案呢?

星期六, 9月 24, 2005

簡報後的檢討

昨天簡報後,自己總覺得不太對勁。

問題出在哪兒呢?我想了想,大致上或可說是:「準備不足、時間不夠、缺乏互動」。

首先,是遇到螢幕大小的問題。由於先前沒有使用「寬螢幕筆記型電腦」的經驗,不知道接上投影機後,會產生字體扭曲的現象。事後,我猜測是(筆電螢幕與投影機螢幕)解析度不同的緣故;但自己也頗好奇,為什麼產品手冊上,沒有教使用者如何處理這類狀況?

說來也真奇怪,我這回買的 HP Presario B1800 筆電,竟然沒有附產品的說明或使用手冊。大概是 HP 以為使用者都知道鍵盤上各式按鍵的使用方式、也都瞭解各類燈號的意義。可是,我就曾經因為不知道有個「打開無線網路」的按鈕而虛耗數個小時呢(參看 8 月 31 日的 post)。現在,自己碰到「螢幕解析度」的問題後,不免會想:「難道,只有我才會碰到這種狀況;只有我才會認為:它是個需被解決的問題?」

我猜測這個問題,與多重螢幕的設定有關;不過自己並不瞭解多重螢幕間,設定、切換、與運作的方式。有沒有人(喂,萬事通的貓啊,快幫我想想辦法吧)能夠提供合適的建議或解答呢?(還是,乾脆該打電話向廠商求教?)

除了「簡報顯示扭曲、自己與觀眾看了都不順眼」之外,我覺得「投影片準備不足、簡報時間不夠」也是項缺點。說投影片準備得不足,其實該說是自己並沒有想清楚:這次的簡報,究竟想達成些什麼。而簡報的時間不足,除了頭頭(項老師)有事必須提前離開;簡報期間太太數次行動電話 call-in ,也讓自己顯得手忙腳亂。

最後,關於缺乏互動的部分,自己似乎早該知道、也該事先有所準備(如此就不會對「缺乏互動」感到不安)。在做簡報前,已經有三位學弟報告過了。輪番上陣、疲勞轟炸的結果,聽眾早已心力交瘁、頭昏眼花,怎能有氣力與意願,來做良好的溝通與互動呢?

星期五, 9月 23, 2005

回實驗室給了一場簡短報告

準備了一個多星期,今天下午在實驗室給了場簡短的報告。

報告的內容,就像是上星期五所提到的,是嘗試以「見樹」的方式、換個角度看待古契書文件群。因此,雖然自己對古契書其實一點都不懂,還是努力假想了一個使用情境,然後從中看看是否能夠學習到什麼。

或許是時間不夠、或許是很久沒有在學校做過簡報,又或許是自己準備得還不夠,我總覺得許多地方講得不是很好(也就是說,詞不達意、講得不清楚啦)。不過,除了自己可以學習簡報技巧外,我還是傾向於將簡報看作「報告者與聽眾的溝通與交流」;聽眾(學弟妹們)的感受、收穫、想法與回饋,才是最實際、也最重要的。

星期四, 9月 22, 2005

科教館的玩具

如果有用心,在台北常能發現有趣的事物。

例如,士林有一座國立科學教育館,假日人潮洶湧,但上班日通常門可羅雀,非常適合帶小朋友去走走。更棒的是,即使不買門票,也常能得到許多樂趣。

我們因為常有事到士林,偶而也會帶寶寶到那兒,看看門外的「球球坐電梯」。它是一座很有趣的機器,利用傳輸帶將球帶到高處,然後讓它由高處滾動滑下、撞擊、彈跳(右圖是這座機器的部分展示 -- Blogger 似乎會把上載的動態圖弄壞)。不僅很多小朋友喜歡駐足觀賞,我也常常在那兒感到歡欣讚嘆。

該館一、二樓有賣許多玩具,也提供一些樣本讓小朋友試玩。非假日期間,寶寶通常都能玩得頗愉快。有時,也可以找到一些有趣的益智遊戲,讓大人們也都能玩上好一陣子。

昨天帶三歲的寶寶去科教館,又發現一個可愛的玩具。它其實是一隻氣球,但日本人發揮巧思,在氣球下裝上合適重量的膠紙(作為動物的腳),讓氣球漂浮在離地約 10 公分處。小傢伙用線牽著氣球走,就像是牽著真實的動物一樣可愛。

雖然價格有些偏高,但寶寶玩得高興、又覺得需要鼓勵這類的創意,我決定讓她自己挑一隻。連問數次,小傢伙都選了「小公雞」。我讓她牽著小公雞在館內四處逛、教她到二樓書局講故事給小公雞聽 -- 而或許是因為看到寶寶高興的樣子,我在那些時刻裡,確實感覺頗為幸福。

下圖就是這隻「小公雞氣球」的長相。遠遠看來,還頗像真的公雞呢。

星期一, 9月 19, 2005

AI 是什麼?

上星期五實驗室聚餐,項老師也出席了。

席間,老師半開玩笑似地說,AI(Artificial Intelligence,人工智能,從前翻譯為人工智慧)是一個很奇怪的領域。他說,AI 有許多定義,其中的一個定義是:「AI 是研究那些人腦可以做,而電腦卻不能做的事情」。

依照這個定義,老師說,AI 裡研究的主題,一旦成熟後,就會獨立出個別的學門,不再算是 AI 了。例如,幾個從前被認為算是 AI 領域的學科,像是 Image Processing(影像處理)、Theorem Proving (定理證明)、Robotics(機器人學)等,在漸漸成熟、知道如何運算出夠好的結果後,都獨立出自己的學門;而研究這些主題的學者,也都不再認為自己 是在做 AI 的研究了。

老師接著說,「所以,AI 存在的目的,就是為了消滅它自己,那真是怪異 (weird) 啊。」

其實,項老師在十年前,就講過一樣的話了。但從現實面看,就算我們真的是如此定義 AI,而 AI 的存在,也真的只是為了消滅它自己,那又如何呢?

即使最終電腦可以取代人腦,但 AI 身為衍生出這些有價值的獨立學門之母,應也足夠了,不是嗎?更何況,我是屬於「認為電腦無法取代人腦」的人;而只要存在某些事情,是人腦做得比電腦好的,那 AI 也就有存在的價值啊。

後記:由此也可看出,學數學的人(項老師)對「定義」的敏銳程度。學工程的人或許會覺得,定義沒有弄得很清楚也不打緊,系統做得出來、運作無誤就好了。但做科學研究、尤其是有志於理論研究者,似乎還是該先瞭解定義比較好。

星期五, 9月 16, 2005

即使不必上班,日子依舊忙碌

又過了兩個不必上班的星期。

這十幾天來,做了些什麼事情呢?星期一、三、五陪同太太帶寶寶出門,星期二、四在家裡陪寶寶。雖說陪寶寶玩樂、看著寶寶長大,也經常會得到強烈的幸福感,不過一旦想起「還有許多待做的事情未做」、「還有許多想看的書未看」,就會滿心愧疚。

還好,利用早上大家還在睡覺的時間,自己倒也是做了許多事情。除了寫幾篇 Blogs、嘗試著修改程式,讓迷宮更為曲折外,還有些「登不上台面」、但卻也重要的瑣事。例如,檢視前些日子從學弟妹們那裡取得的「古契書」文字檔。

雖然不甚確定,但我覺得「如何檢索這些古契書」,是項老師與學弟妹們這幾年來做「數位圖書館」研究的一個重要項目。自己的博士論文,研究的就是關於資訊檢索 (information retrieval) 的主題,所以或可提供一些自己的經驗或心得,讓學弟妹們少走些冤枉路。

聽過兩次學弟們的報告,我猜測大家對於使用 general-purposed approaches 應該已經有了相當程度的瞭解,但或許對比較特定的應用缺乏感覺。也就是說,大家看讀過、也實驗過「同時處理多篇文件」的方式(例如,利用統計方法來斷詞),但卻可能會有「見林不見樹」的遺憾(在此,每一篇文件是樹,而整個文件集合 (corpus) 就是林)。

因此,我想採取「見樹」(the small) 的方式,從比較特定的一些文件著手,看看是否能激發學弟妹們的一些想像(以公司裡使用的詞彙來說,就是「創意」)。當然啦,要「見樹」,自然得對「樹」有相當程度的瞭解;但不幸的是:我對古契書的背景與文字內容,瞭解非常貧乏(似乎也只有歷史學者才會比較瞭解 -- 但不該以此作為藉口)。因此,很可能自己花了不少氣力描繪出來的「樹」,與實際上的「樹」會有著相當大的落差。

我想,做研究就是這樣,總是得嘗試去做些「雖然辛苦、也不知是否會豐收」的事情;而這也是「做研究」與「產品開發」的一個主要不同處吧。

星期二, 9月 13, 2005

更為曲折的迷宮

在「稍微有些曲折的迷宮」貼出後,MPH 提出「曲折」的建議:盡量讓迷宮多轉些彎。

說的也是。既然手頭有程式,當然應該試著修改參數、做些實驗,看看會有怎樣不同的結果?

回想一下,我們的演算法,是採用 depth-first search (DFS) 的方式來展開迷宮樹狀結構的。原先的程式,在選擇「欲打破的牆」時,並沒有加入「盡量多轉彎」的考量。現在,我們讓迷宮路徑會轉彎的機率,比直線走的機率高。

例如,假設轉彎的機率是走直線的兩倍。再假設我們現在處於節點 (2,4),且發現其左側牆已被打通。則可知道,我們是站在節點 (2,4) 上,面向右(因為剛剛是由 (2,3) 走過來的)。於是,我們就讓 (2,4) 節點上方與下方(分別表示「左轉」與「右轉」)的牆,被打破的機率,是右側(表示「走直線」)牆的兩倍。

而這回產生的迷宮,看起來又更曲折了(參考右上方圖例,並與先前的迷宮做比較)。

這給了我們一個經驗:在定義「蜿蜒曲折」時,似乎不僅僅可「拉長兩端點間的距離」,也該考慮「轉彎的次數」!

喔,這下麻煩大了。原本「蜿蜒曲折」就是一個「未經明確定義」的詞彙;但現在它的意義,變得更複雜(拉長、多彎)後,會不會讓討論變得更模糊呢?

而且,也還有一些或許更困難、更有趣的後續討論哩。現在我們已經有了「感覺起來」頗為曲折的迷宮;但是「好」迷宮,光是蜿蜒曲折,應該還是不夠的。我們並不希望:迷宮蜿蜒曲折,但是「很好走」(例如,從入口到出口,幾乎都沒有岔路;或者,就算迷宮有很多岔路,但岔路都很短,一下就走到岔路盡頭)。

所以,接下來該怎麼延續「迷宮」的研究、討論、與實驗呢?

星期日, 9月 11, 2005

能夠「輸出自己」的程式

前些日子提到 Ackermann's function 後,也讓我回想起一些有趣的小問題。

其中一個,是寫個程式,它不管輸入什麼,都會輸出自己(這份程式)。這個問題之所以有趣,一部份的原因,是因為乍看之下,要求得一組解(寫出一個能夠「輸出自己」的程式),似乎並不困難。但真的如此容易嗎?有興趣的人可以試試看。

第一次碰到這個問題,也是在 Maryland 時,計算理論老師 (Dr. Smith) 的講義裡,某個習題提到的。當時是沒有出這項作業,但我有花幾個小時嘗試寫過,並沒有成功。(嗯,還是一樣,沒有成功解出的問題,比較會印象深刻...)

在課堂上,老師也提到過,我們可以證明:不管是哪種程式語言 (只要它們的計算能力相同,都是 Turing-complete -- 現在幾乎所有的程式語言,像是 C、BASIC、JAVA、LISP、PASCAL、PROLOG,甚至 PHP,都是 Turing-complete),總是存在著(無限多個)這樣的程式,它們可以輸出「它們自己」(此證明可參考這本書末,對習題 2.13 的解答)。

自己則是在數年後,從 BBS 上看到有人貼出用 C 語言實作的漂亮答案。我將它稍微修改,展現成 PHP 的程式碼:

<?php $s='<?php $s=%c%s%c;printf($s,39,$s,39); ?>';printf($s,39,$s,39); ?>

你能夠自己寫出這樣的程式嗎?

星期三, 9月 07, 2005

「稍微曲折的迷宮」之後

頗訝異於網路的高效率。

昨天貼出「稍微曲折的迷宮」後,不到半天就有人回應,說這裡有張曲折的迷宮圖,而這裡是它的路徑解答。

喔, 那可是張很大 (3002x3002) 的迷宮圖呢。很可惜,我沒有找到產生這張迷宮的演算法(與程式)。不過,有時直接看到答案,雖然會有「啊哈,原來如此」的痛快,但緊接著可能就會有些莫名 的失落。找不著答案,我們可以試著修改自己的演算法,想想如何才能產生蜿蜒曲折的迷宮。而探索,不也是一種樂趣嗎?

昨晚花了些時間,修改程式來做些實驗。終於,我們可以產生像右圖般的迷宮了。它看起來比昨天的迷宮,就蜿蜒曲折了許多(雖然我們也還是沒有定義出什麼叫做「蜿蜒曲折」)。

這個迷宮是如何被產生的呢?

回顧之前提過的一個想法:或許可藉由增加迷宮的直徑(diameter,就是最長的兩端點距離)來產生曲折的迷宮。但是,要用什麼方式來怎樣增加迷宮的直徑,才能夠依然保持演算法的簡潔呢?

一個「也算直觀」的想法,是在產生迷宮的樹狀圖(8 月 25 日 post 的集合 T)時,儘量增加 T 的高度(height,由根節點到任意節點的最長距離)。也就是說,每當我們從集合 C 裡,要選出「可被打破的牆」時,儘量選「能夠繼續增長迷宮樹狀圖高度」的牆來打破。

最簡單的一種方式,是當我們要將節點四周「可被打破的牆」放入集合 C 時(參考 8 月 25 日 post 的步驟 2),實際上只選一面牆放入集合 C (其他的幾面牆,則放入另一個串列 C2)。如此一來,我們可以讓 T 以類似深度優先 (depth-first) 搜尋的方式向外延伸,而能夠相對容易地增加 T 的高度。

那麼,如果 T 已經「碰到絕處」,無法用深度優先搜尋繼續往下增長時,該怎麼辦呢?此時,我們可以由 C2 取出最後面的牆來打破。如此持續進行,直到 C 與 C2 都是空集合為止。(喔,只是稍微修改 8 月 25 日 post 的「基本演算法」,產生出來的結果,竟然就會有如此大的差異...)

我想,或許迷宮真的是一個不錯的主題吧(連 MPH 從前也曾嘗試用「笨方法」產生曲折迷宮呢)。而回顧這些曾感興趣的問題,總讓我對從前懵懂的歲月,有著淡淡的感傷、歡喜與寂寞。

星期二, 9月 06, 2005

稍微有些曲折的迷宮

說過自己打算用「迷宮」來起頭,寫寫技術性文章。

也曾討論過,用 tree 來表示迷宮是一種頗為簡單、漂亮的作法。但是,從幾個產生的迷宮路徑圖來看(參考 8 月 15 日的 post),這種簡單方法所產生的迷宮「不夠蜿蜒曲折」。於是,就會想:如何才能產生比較蜿蜒曲折的迷宮呢?

一種想法是,產生迷宮時(參考 8 月 25 日的 post),讓「候選集合 C」裡,每道「可被打破的牆」被打破的機率都不一樣。不過,問題是:該用怎樣的機率分配(該如何指定每道牆被選到、被打破的機率),才能得到蜿蜒的迷宮路徑呢?到目前為止,我試了幾種簡單的機率產生方式,但對結果都不甚滿意(有沒有人可以提供建議啊?)。

換一個角度思考:我們可以觀察到,從左上到右下的路徑,必得經過中間每一直行。因此,或許可嘗試另一種方式:在迷宮中,隨意產生幾道「長長的、不可被打破的牆」,強迫從左上到右下的路徑必得「繞路」。例如,右上方的迷宮,第 10 行與第 26 行右側各有一道由上往下的長牆,第 14 行右側有一道由下往上的長牆。如此一來,產生的迷宮似乎就蜿蜒曲折了些。

我覺得,可以有「激發想法、並修改程式來實驗改進」的餘地,也是迷宮問題的有趣地方。

星期五, 9月 02, 2005

不用上班的一個星期

一般說來,「不用上班」似乎是「不用工作」的意思,是「悠閒」的代名詞。

不過,就如同 MPH 幾天前在 Blog 所言,不用上班的日子,感覺似乎更為忙碌(有時,我連早上看紐約時報的時間都不夠呢)。難道真的應驗了:「休息是為了更忙?」

我不清楚。我只知道,這幾天在家,倒是處理了許多上班時「忙碌而沒有做」的事情。通常,這類的事情必須麻煩家人來處理(所以啊,從前能夠空出一些時間,多少需要感謝家人的幫忙);而現在不用上班,就「理所當然」地該由自己來做了。

在家裡,似乎比較無法專心整理、回想、思考曾經感到興趣的電腦相關問題。因此,我會擔心:做這些「雜務事」,讓自己沒有什麼時間可以進行原先想進行的「心得、感想整理」。做這些事情,需要相當的專注、耐心、與毅力才能達成。

我希望,這幾天的忙碌,能夠算是「特例」。逐漸處理完「從前累積下來的事務」後,期待可以慢慢地「進入狀況」。

星期三, 8月 31, 2005

終於買筆記型電腦了

離職後的這幾天頗為忙碌。尤其是,終於買了一台筆記型電腦。

早在幾個星期前,我就打算買一台筆電了。想要重量輕、規格好(CPU 夠快、記憶體 1GB、硬碟也不能太小、最好還是寬螢幕)、價格也合理的機型。在網路上看了幾天、到 Nova 看了一回、嫌 Sony 的太貴,只能在 Asus 的 W5 與 acer 的小狗機之間作選擇。但 Asus W5 只支援到 768 MB RAM,acer 的品質一般來說又頗差,怎麼辦呢?

最後是找到 HP Compaq 的 B1800。除了光碟機是 Combo 外,大致上都相當滿意(不過,事後從 CNET 的報導中,知道含電池的重量其實是 1.86 公斤,比型錄上聲稱的 1.6 公斤重了不少,令我有些被騙的感覺)。

接 下來的事情,就是安裝軟體了。由於無線基地台與 Hub 的位置弄錯了,花了許多時間在安裝與測試(最後還是在貓的指導說明下,才知道弄錯了)。更扯的是,我不知道這台筆記型電腦必須在按了某個按鍵後,才會打開無線上網的功能,竟花了數個小時的時間在檢測基地台與筆電間的安全設定。

不過,安裝設定好了後,敲打著筆電的鍵盤、上網查資料寫 Blog,也覺得頗為滿足。

而花錢買東西就是這樣,經常可以得到許多「擁有新東西」的興奮。難怪許多現代人,會喜歡藉著添購新事物來抒發鬱悶、讓自己「似乎」可以活得快樂些。

星期二, 8月 30, 2005

我看紐約時報的感想

數個月前,回實驗室參加 meeting,項老師鼓勵大家看每週聯合報所附的紐約時報 (New York Times) 精選。

自己的英文程度不佳,是早就知道的事。看英文報紙,不懂的單字頗多,即使是一篇短文,都要看上半個小時。但許多知名的教授(像是李家同)都極力推薦大家看紐約時報,我想,我是該每天儘量抽出些時間來嘗試閱讀。

說真的,看了幾個星期後,我覺得台灣的報紙,真的不知道在報導些什麼。報導的主題狹窄、內容貧乏就算了,連寫篇「好文章」的基本訓練都沒有。

紐約時報的每一篇報導 --- 即使是短短的幾段文字 --- 都是自給自足 (self-contained) 的。每一篇都像個完整的故事,重要的個體(人、事、時、地、物)都有被清楚交代;而故事人物的心情起伏,描述也是生動極了(我目前其實是透過聯合報的中文 翻譯 與解說來感受的。說來也頗自卑:我對英文字詞的微妙用法了解非常有限;看到不同的形容詞此起彼落地出現,通常只能瞠目結舌,更不用說是了解吸收)。

項老師說,學習英文,除了多看多學習外,沒有其他的訣竅;而紐約時報的文章,多半都是「好的英文」。我看了這幾週後,有一個很強烈的感覺:「好東西該與好朋友分享」,真的該向大家極力推薦。

星期六, 8月 27, 2005

浮濫的商業口號

有一陣子,我對陳腔濫調的口號頗感厭煩。

部分原因是,這些口號看起來、聽起來都冠冕堂皇,合理正當,但經過一段時日後,總會覺得它們與實際的執行落差太大。由於我的邏輯感似乎常常會告訴自己:「必須強調前後的一致性」,因而時常會對於對這類的矛盾衝突感到不舒服。

恰好那時正在看「隨機的致富陷阱 -- 解開生活中的機率之謎」這本書(時報出版)。作者提到 (p.90),我們或可用隨機的方式,模擬公司執行長的言談,用以確定他說的話是真具有價值,或者只是經過修飾後的胡言亂語。

也想起傳統的人工智能 (Artificial Intelligence) 中,有著一個「電腦作文」的主題:希望電腦可以藉由一些規則與亂數,隨機地自動產生文章。要產生商業口號,應該比作文容易得多吧?心血來潮,就寫了一段小程式來玩。這個程式在剛剛的執行中,產生了這樣的幾個句子:

我們日新又新,致力於股東的持股價值
我們堅持誠信為企業之本
我們致力於追求卓越
我們發揮己長,並且改善缺點
我們相信如何對客戶提供更好的服務

雖然最後一句顯得相當古怪(「相信」如何對客戶提供更好的服務?),但大致上,讀起來也真像會議中所常聽見的執行長用詞呢。

星期五, 8月 26, 2005

珍重再見

辦完離職手續,正式與公司揮手告別。

回首過往,已如雲煙。在這家公司,工作了三年又四個半月。從早期對未來的憧憬想像、中期對產品的積極找尋、以及晚期對軟體的品質管控,自己多多少少是有著一些感觸。

就如同波普 (Karl Popper) 認為科學的真理必須靠臆測與否證 (conjecture and refutation) 來向前推進;對於公司在某個時刻的發展選擇,事後也多半隻能以成敗論英雄,卻很難累積一致的經驗與規則。以事後諸葛的角度,我們是可以舉出許多例子,來說明為何會導致現在的失敗;但是處在多種相互衝突的選擇間,其實也沒有絕對的定律來告訴管理者該如何做。

於是,我們可以看到許多彼此矛盾的商業策略、前後不一致的銷售模式,讓公司裡的員工經常無所適從。而或許也因為如此,保持「簡單、清楚、一致」的商業策略與貫徹執行,才更讓人感覺其重要性。

有趣的一個經驗是,「當你已不在乎你的職位,反而能夠做好這個職位所該做的事」、「當你不在意能夠得到什麼而盡力付出,反而能夠得到最多」。我想,這或許就是一般人的盲點:只看見自己想要的,卻忘記團隊是需要關注到他人需求後,才能夠團結併發揮力量。

星期四, 8月 25, 2005

迷宮製作的演算法與圖例

且鼓起勇氣,試著談談「電腦平面迷宮」製作的技術細節。

需要勇氣,是因為談技術,通常容易流於枯燥與沈悶。然而,若我想要寫一篇關於「迷宮」主題的文章,卻非得督促自己去嘗試描述技術細節。因此,就讓我試著接續先前對迷宮的製作,做些更深入的描述與討論吧。

先前提過,可以用樹狀結構來產生迷宮。現在,我們可以將演算法(產生迷宮的方法)說得更仔細些。注意到,在這兒一個節點就是一個迷宮的格子;而相鄰的兩個節點間,如果沒有連結,我們說兩個格子間有一道「牆」。
  1. 一開始,任選一個節點。
  2. 將這個節點四周「可被打通的牆」(不含迷宮的外圍),放入一個「連結集合」C 裡。
  3. 將此節點,放入「已處理之節點」集合 T 裡。
  4. 如果 C 為空集合,表示迷宮已經產生完畢,我們停止程式。若 C 不為空集合,從中任意挑選一道牆(假設這道牆連結節點 n1 與 n2,而 n1 在集合 T 裡),並打通它。
  5. 如果 T 的節點與節點 n2 間,有連結在 C 裡,則將這些連結從 C 裡移除。
  6. 將 n2 標示為「已處理」(放入集合 T 裡),並回到步驟 (4)。

直接看以上的演算法,可能會有「霧煞煞」的感覺。配合著一個實例來對照,應該會比較清楚。

首先,假設我們要產生一個 3x3 的小迷宮。為了方便說明,我們將迷宮的格子標上號碼(英文字母 A~I),如右圖 (a) 所示。現在,且讓我們跟著演算法的步驟走一回:
  1. 任選一個節點。假設我們選到 B。
  2. 將節點 B 四周「可打通的牆」放入集合 C。參考下圖 (1) 中的黑色虛線。
  3. 將節點 B 放入「已處理」的節點集合 T(含有圓點的格子)。如下圖 (1) 所示。
  4. 執行演算法步驟 (4)。因為 C 不為空集合(圖 (1) 中有黑色虛線存在),所以我們從中任意挑選一道牆,例如 B-E(n2 為節點 E)間的牆,把它打通。
  5. 接下來,進行演算法的步驟 (5) 與 (6),可以得到下圖 (2).

  6. 接著,我們再次進行演算法的步驟 (4),假設這回從 C 選出 A-B 間的牆來打通。進行步驟 (5) 與 (6) 之後,我們得到下圖 (3)。
  7. 重覆執行步驟 (4),假設這回選出 D-E(n2 為節點 D)間的牆來打通。
  8. 執行步驟 (5)。注意到,節點 D 與 A 之間,原本有「可被打通的牆」,但因為 A 已經被放入「已處理」的節點集合 T 裡,我們在此必須把 D-A 之間的牆從集合 C 裡移除(用紅色虛線表示已由 C 移除的牆)。
  9. 執行步驟 (6),將節點 D 加入集合 T 之中。至此我們得到下圖 (4)。
  10. 仿前步驟 (4)、(5)、(6),破除 E-H 的牆,將 H 加入 T 後,得到下圖 (5)。


  11. 依循步驟 (4)、(5)、(6),破除 H-I 的牆,將 I 加入 T 後,得到上圖 (6)。
  12. 依循步驟 (4)、(5)、(6),破除 I-F 的牆,將 F 加入 T 後,得到上圖 (7)。
  13. 依循步驟 (4)、(5)、(6),破除 F-C 的牆,將 C 加入 T 後,得到上圖 (8)。
  14. 依循步驟 (4)、(5)、(6),破除 D-G 的牆,將 G 加入 T 後,得到上圖 (9)。
  15. 至此,C 已經變成空集合(圖 (9) 裡,已經沒有黑色的虛線,表示已經沒有「可被打破的牆」)了,因此程式停止。我們最後產生的 3x3 迷宮,就如上圖 (b) 所示。
有時,會很訝異於自己是如此地沒有效率:即使是這麼短短的一小段內容,也需要自己好幾天的時間來構思、繪圖、撰寫、修改呢。

星期二, 8月 23, 2005

Stop improving yourself and start living

昨天和 MPH 在 msn 閒聊。他說,想寫關於「Stop improving yourself and start living」的系列文章。

我說,這句話說得真好。我人屆四十,才驀然發覺,自己從前汲汲於改進自己(尤其是學識上的技術相關領域),努力想在工作上有所表現;卻忘卻了:眼前的生活,才是最值得珍惜與重視的。

自上週三起,努力進行的專案就被迫停止,而公司也進行裁減人力的動作。突然間,好像「沒有事情可以做」了。而前幾天早晨,我到台大醫院抽血檢查,在二二八公園走走逛逛,聽聽鳥叫蟲鳴,很強烈地感受到很久都沒有的舒暢。

我說,我想空出一年來整理自己這些年的感想;但一年後,似乎總還得去找份「正式的工作」。只是,為什麼「工作」在現代人的生活裡,竟然扮演了如許重要的角色呢?

星期一, 8月 22, 2005

我想整理些什麼?

想花一年的時間,整理自己這些年對電腦(科學、軟體、程式)的心得與感想。

起因是這樣的:自己快要四十歲了。不知道是年歲的關係、還是工作的緣故,在電腦科學(或電腦工程?)領域浮沈了十幾年,了解的知識越多,卻越來越覺得喪失了年輕時的好奇與樂趣。

我在高中時,並沒有上過任何關於電腦的課程,也缺乏現今的網際網路來取得資訊。在大學時代,雖然仍對許多電腦相關問題感到興趣,卻總覺得缺乏一本整理過的書籍,能夠帶著我入門、領著我欣賞。如今,雖然電腦書籍已經稍嫌氾濫、Internet 與 Google 又威力龐大;但我仍然覺得,或許有些年輕朋友,會像我當初那樣,需要有人整理些有趣的主題,寫成可以動動頭腦、又可以學習到電腦技術的書籍。

因此,我想整理一些感想與心得,獻給約具備高中或大學一、二年級的數學程度、對電腦(程式)感到有興趣的朋友。此外,我也希望能藉著回顧年少輕狂,重新品嚐青春的淺淺歡樂與悲傷,讓自己的人生,有著更甘醇的韻味。

能不能做到呢?我自己也不是很有把握。在這幾個月裡,我雖然已經慢慢地從日記、筆記堆、與古早的軟碟片裡,找回一些曾經感到興趣的主題,卻總覺得不知道該如何著手來完成一篇文章。貓(LCAT)建議我從寫 Blog 開始、逐步練習寫作。我頗為贊同,所以就開始了「也是回顧」的漫筆。至於成效如何?就只能讓時間來說話了。

星期日, 8月 21, 2005

也談「說謊村」

我對益智性的小題目也頗感興趣。

「說謊村」是一類有趣的問題。在這類問題中,通常都會有
  1. 兩個地點:「老實村」與「說謊村」;與
  2. 兩種人物角色:一個是「老實村」的人,他永遠說真話;另一個是「說謊村」的人,他永遠說假話。
〈問題一〉
你來到一個村莊,卻不清楚它到底是「老實村」或「說謊村」。現在你只能詢問(當地)村民一個問題,來確認是否是在哪一種村莊裡。你該如何問這個問題呢?

對於忙碌的現代人來說,通常想個一兩分鐘,就可能懶得再去思考,直接看答案了。而看到答案是,問村民:「請問你住在這個村子裡嗎?」時,又會覺得:喔,答案好像不太容易想到?(出題、解題的人,怎麼這麼聰明啊?)

其實,我們可以反過來,從回答端來思考這個問題。也就是說,我們希望讓提問有「是」與「否」兩種回答;當聽到的回答為「是」,我們希望確定是在老實村裡;而聽到「否」 時,則了解是處在說謊村(也可以反過來提問另一種問題,聽到回答「是」表示是在說謊村,聽到「否」則表示在老實村)。

因此,關鍵是在於問一句話,讓老實村的人回答「是」,而說謊村的人回答「否」。因此,答案就浮現了:我們可以問一個「恆真」的問題,例如「請問 1+1=2 嗎?」、「請問你是(老實村或說謊村的)人嗎?」;或者,問「你住在這個村子裡嗎?」(因為我們已經假設問的是當地村民,所以這個提問必然是恆真的。)

〈問題二〉
另一個常見的問題是這樣的:「你在一條岔路上,遇到一位路人。這條岔路的一邊通往老實村,另一邊則通往說謊村;而這個路人,可能是老實村的村民,也可能是說謊村的村民。現在你只能問這位路人一句話,就必須決定岔路的哪一邊通往老實村。你該如何提問呢?」

這個問題的關鍵,其實是在問一句話,指涉到特定的一條路,讓老實村的人與說謊村的人,都會回答「是」。也就是說,對老實村的人而言,這句話是真的;而對說謊村的人來說,它卻是假的。例如,問「你從這條路回家嗎?」、「這條路通往你住的村子嗎?」。於是,我們(對於路人的回答)有如下的真值表:


而當我們聽到回答為「是」時,即表示所指的路通往老實村;聽到回答為「否」時,則表示此路通往說謊村。