vgod's blog

讓電腦自己寫程式的夢

在高三突然對於讓電腦自己寫程式產生興趣後，我每天就都想著這件事，夢想著未來某一天的電腦能跟我一起寫程式，當我把程式目的說給它聽時，它就一邊把細部的程式碼產生出來：我不用想如何命名變數，或是要用什麼演算法，還是我到底要不要把這個功能變成獨立的class…；我只要動動嘴巴：「我想寫一個橫向捲軸的射擊遊戲。玩家操縱著會變形的飛機，還有四種武器。第一關要長這樣這樣……」，然後電腦就幫我把遊戲寫出來了！如果真的可以這樣，那該有多好啊！（如果真的成真，恐怕我也要失業了？）[註一]

這個想法實在太讓人興奮了，雖然說這是一個遙遠的夢想（其實那時候我並沒有覺得這麼遙遠，只能說自己太不自量力XD），但也開啟我對於人工智慧、程式語言結構、軟體工程等領域的高度興趣。

寫程式很難？

在高中時代頗不知天高地厚的我，一邊嘗試著利用基因演算法(Genetic Algorithms)讓電腦自己產生程式碼，一邊研究各種程式語言的結構和特性。靠直覺摸索出利用tree作為中介來描述一個程式後（那時沒唸過compiler，不知道這個其實就是Abstract Syntax Tree)，我突然就對這個想法的可行性信心大增，所以一時衝動就去報名了國際科展，打算把這個想法實做出來。

真的做了以後才發現，最難的部份不是產生出程式碼。如果你把程式語言的基本元素，像是if、for、變數、運算符號等東西做成一塊塊磁體，然後拿給一隻猴子玩，那麼牠其實也能拼出一堆程式給你，問題是：「你要怎麼知道這些程式碼真的達到了你想要的目的？」

悟出這個道理後，我突然了解寫程式最難的部份是在驗證程式碼真的跟你所想表達的事情完全相同。（所以說我對於各家軟體公司的QA地位都低於RD其實感到很不平）

基本上，我們只能設計大量的可能輸入值丟進程式裡，並比對程式跑出來的結果和我們想要的輸出相不相同。即使在這種情況下，我們也只能說這個程式在測試過的這些輸入值上所產生的結果是正確的。也就是說，除非我們測試過所有可能的輸入（這意味著無限多種可能），不然永遠沒辦法知道某個程式是對還是錯。除此之外，即使只測試一個輸入值，也還有個很嚴重的問題：「我們怎麼知道這個程式要跑多久？」換句話說，當你程式跑下去，你怎麼知道他是掉入一個無窮迴圈，還是其實正在拼命計算當中？

我在參加國際科展時，認識了歐陽明教授，他告訴我這個問題叫做Halting problem，Alan Turing在70年前就證明了這是一個無解的問題。知道這件事後，才發現自己所知實在太少，對於資訊科學的基本知識實在非常不足，但這次經驗其實也給了我一個明確的方向，讓我把書中的理論和實際的目標連結在一起。

見樹又見林的學習之道

提到書本中的理論，有很多人問過我要怎麼學習寫程式或資訊相關的知識，我順便在這邊分享些心得給大家參考。

常看到許多人抱怨大學裡學的東西都是理論，畢業後找工作時才發現什麼都不會都得重學；當然企業也會抱怨，大學應該多教一些實務課程，不然出社會後還得重新訓練。說來說去，一致的口徑指向理論和實務是打死也扯不上關係的樣子，尤其念資工的人更常這麼說：「學校為什麼不教C#？為什麼不教我做網頁？好歹也要教個HTML嘛！」

我覺得學習任何事物，一定要有充分的興趣才會有效率，在不知道所學為何的情況下被逼著學習是非常痛苦且沒有效率的。最近看了一本書：沒有資優班，珍視每個孩子的芬蘭教育，書中提到芬蘭教育成功的秘密在於「見樹又見林」，這句話也是我對於如何學習最想分享的秘訣。

台灣的教育方法是「先見樹，再見林」，也就是先教你細部的方法和技術，等你都學會之後（或是硬背起來之後），出社會後就會知道為什麼要學這些東西。（很多人小時候都聽過「等你長大就知道唸書有多重要」吧。可是現在比較多人畢業後反而說「我不知道之前念那麼多書有什麼用」）在這種體制之下，許多人在還沒見到整片森林的美景前就被一棵棵大樹搞得暈頭轉向，痛苦萬分，在不知道「學了這個可以做什麼」的情況下，不管學什麼都會覺得沒有意義沒有動力。

而「見樹又見林」的學習方式，是先找到能引起自己興趣的目標，讓自己有個理由去認真學習，之後再往細部的技術和理論去學習。我從小就很想自己寫遊戲，為了達成這個目標，我就四處尋找相關的資料，慢慢的我就知道自己應該要學好一個快速的低階語言（像是C++），如果要寫繪圖引擎可能還得學一點圖學的理論和技術，如果要做網路連線還得學網路相關的技術…。

這裡有個重點是，不要看過森林後就忘記它，而又迷失在幾棵樹幹上，要讓自己一直重複見樹又見林的過程。

這跟如何有效開發軟體的秘訣是一樣的。一個有效率的軟體開發方式是用iterative process，把包含設計、實做、測試的iteration時間縮短，但要一直不斷重複這個iteration無數次來改進現有的成果。同理，在已經有目標的狀況下學習時，每當學會一些新東西，就要馬上試著把它實現出來，即使是只有幾行程式碼的prototype也沒關係。只要一直不斷的學，這個prototype就會一直被改進，一直加進最新學到的知識和技術而更接近最終的目標。

同時動腦也動手(註二)，用這種角度來學習就能充分了解自己學會的東西可以用在什麼地方，馬上得到回饋的成就感還會刺激自己繼續向前進，形成一個非常有效率的學習循環。用這種角度看學校教的東西，就能知道書本上的理論可以用在哪，並且又欠缺哪些實務知識讓自己無法做出想要的東西。

這方法理論上可以擴展到任何事物的學習，重點在找到有興趣的目標和書本裡知識的連結，我覺得這是老師應該要出力的地方，無奈的是台灣的教育體制把中小學老師們變成出考題和改考卷的機器人….。

註一:
其實，現在真的有這樣的研究，而且驚人的是目前已經有了非常接近我想像中未來的雛型。最讓我興奮的是MIT Media Lab的Hugo Liu和Henry Lieberman做的Metafor：只要對電腦用英文描述你要的程式，電腦就自動把Python code生出來給你….。

註二:
話說，MIT的校徽上就是一個拿著鎚子的工匠和一個拿著書的學者，所代表的意義就是 “Mind and Hand”，也就是期望每個學生都能手腦並用，除了做夢外也要實做出來才算數啊。

(待續)

距離要去美國的時間轉眼間只剩一個月了，最近終於也把簽證、體檢等雜事辦完，可以開始打包行李準備迎接未來的留學生生活了。因為油價上漲，能帶上飛機的行李限重越來越低，生活用品我打算都到美國再買，所以最近就開始研究起在美國購物的秘訣。

美國土地廣闊，人們都相當依賴網路購物，而在網路上買東西就一定要知道怎麼利用現金回饋(cash back)來省點錢！目前網路上最多人用的cash back網站有三個：EBates、FatWallet、Microsoft的Live search cashback。

這三個網站分別和上百家商店合作，只要透過這些cash back網站連結出去並完成交易，就可以拿到一定比例的現金回饋。這些現金回饋其實還蠻多的，一般來說是2%~5%，但也有一些店的回饋甚至超過20%。我之前在Priceline訂過旅館，就是透過Ebates連過去的，雖然只有2%的回饋，但在什麼都漲的時代把小錢累積下來也是很可觀的。如果你常買機票之類的大額支出，那更是能輕易拿到上千台幣的回饋喔。

最後順便提醒大家一個好康的情報，如果你透過我的EBates連結去註冊，馬上就能得到5塊美金的回饋喔，並且我也會有5塊美金的介紹費。（就當贊助我寫blog吧 ）

附帶一提，這不是只有住美國的人才能用喔。有些商店是能把東西寄到台灣的，而且現金回饋是以支票的方式支付，在台灣也是能收到喔。

程式設計到底是什麼?

2000年IOI在北京舉辦，這年台灣的代表隊成績還算不錯，拿到三銀一銅，比較可惜的是我第一天表現不理想而落到了銅牌，雖然不至於兩手空空無顏面對江東父老，但也知道自己的實力大概就在銀牌和銅牌的邊緣處吧。IOI結束後，我又回到了學校，但因為已經取得大學保送資格，在學校其實也是輕鬆寫意，成天就看自己的書或研究自己有興趣的東西。

在這段時間中，我開始有所警覺，我發現我雖然很會寫程式解題，但那都是一兩百行以內的小程式，真實世界的程式根本不是這個樣子的！雖然我能很快看出一個問題該用什麼演算法效率最高，並且在很短的時間內把自己的想法正確地轉換成程式碼，但我還是不知道市面上的軟體或遊戲是怎麼做出來的。

我這時才開始接觸C++和物件導向的概念，我突然發現要寫個大程式還真不是簡單的事，除了程式語言外，還有好多瑣碎的函式庫得學。像是要畫圖就要學2D的SDL或是3D的OpenGL，要做Windows GUI程式就要學Windows SDK或是MFC，要寫網路連線就得學socket，要讓遊戲執行順暢甚至得用組合語言寫某些部分…。好多好多東西不斷湧出來，學這些東西很有趣，因為我一邊學就會一邊聯想到學會這個功能後可以用在遊戲裡的什麼地方，於是整個學習過程就像把我夢想中的拼圖一塊一塊拼上去一樣，非常有成就感。

邊寫這種實用性的程式時，我也發現以往在比賽中累積了很多不好的習慣，像是濫用全域變數、變數隨便命名、把整個程式塞在main裡…。這些壞習慣在寫小程式看不出來有什麼差別，但隨著程式規模變大，這就變成了很致命的習慣。而這種習慣一但養成，之後會變得更難改，所以強烈建議初學程式設計的朋友們，一開始就不要偷懶，從認真幫變數想個好名字開始吧！

這段期間也讓我想了很多關於程式設計的有趣問題，像是寫程式到底算是科學+工程，還是藝術？寫程式必須要非常非常精確，任何一個字打錯都可能會讓整個程式跑出完全不同的結果，這對於天生就容易犯錯的人類來說實在是艱鉅的挑戰。為了避免錯誤太多，我們只能用一些固定的流程並強迫程式設計師遵守，讓可能的錯誤減到最低，這就是所謂的軟體工程。雖然有工程的影子，但寫程式卻是很難精確管理的工作，因為面對同樣的問題，不同的人絕對會寫出不同的程式，甚至是提出不同的解決方法﹔有的程式可能要跑三天三夜，有的程式卻能在瞬間得到正確解答﹔有的程式碼雜亂不堪，也有的程式碼井然有序清晰易讀﹔有的人要花三天寫1000行，也有人能在一天寫100行就達到完全相同的效果﹔這些程式的目的可能完全相同，但呈現方法卻有千萬種，軟體工程難道可以限制每個程式設計師大腦運作的方式和速度嗎？

從程式碼的觀點來看，不同的人寫出的程式碼也一定不相同。從程式碼的排版、命名、段落安排、抽象化程度、運作流程可以看出作者的個性、態度、思考邏輯及深度。從這個角度來看，寫程式更像是種藝術，就像是畫筆或樂器一樣是一種表達自我並將思想具體化的工具。

另外我很感興趣的是，人一定要寫程式才能叫電腦做這麼多複雜的工作嗎？能不能教電腦寫程式，讓人只要告訴電腦要寫什麼樣的程式就好？或是有沒有更簡單更方便的方法能和電腦溝通，並且保有同樣的控制力？

就在被這個問題困擾著的同時，我意外從一本書看到基因演算法(Genetic Algorithms)這個名詞。稍微研究過後讓我大吃一驚，因為我發現基因演算法是一個超級有效率的搜尋演算法，可以在幾近無限廣大的可能解裡面很快找到接近最佳解的答案。所以，我很快想到了，如果想要讓電腦寫程式，其實就是告訴他要寫的程式要達到什麼目的，並讓他在幾近無限大的可能程式中找出能跑出我們需要答案的那個程式。這是一種把寫程式視為搜尋的概念，我當時想到這件事非常興奮，但我並不知道其實早就有人想出同樣的概念(這叫Genetic Programming)，並已經做了許多研究。

其實有時候無知是件好事，這樣才會有勇氣在不知道這個問題有多難的情況下去嘗試看看。如果我當初就知道這問題其實是能拿好幾個博士學位甚至是得到圖靈獎(Turing Award, 資訊界的諾貝爾獎)的難題，我可能連繼續嘗試的勇氣都不會有了。

(待續)

勁敵

熱血的少年漫畫都有一種標準公式，熱血但什麼都不懂的主角，加上一個天才勁敵的刺激，讓主角能在不斷遭遇的困難和挫折中不斷爬起來進步。就像火影忍者中的鳴人和左助，或是棋靈王中的進藤光與塔矢亮，要進步最快的方法就是找到一個遠遠超過自己的勁敵作為目標並且努力打敗他。

我在高一時參加校內的資訊能力競賽初賽，在都還搞不太清楚要比賽什麼東西時就去參加了。當時只會用BASIC，知道要用筆寫程式時還嚇了一跳，還懷疑閱卷老師難道能在頭腦裡執行程式嗎? 我記得那題目不難，我每題都有寫，但最後只拿了個佳作，離學校的代表隊還遠得很(話雖如此，我也是唯一有得獎的高一生了)。過了幾個月，我非常驚訝的發現台北市的資訊能力競賽，竟然有一個建中的高一生SBB拿了一等獎，更可怕的是他接下來又在全國能力競賽拿到二等獎，才高一就已經有能選上奧林匹亞國手的氣勢，前途無可限量。

受了他的刺激，我非常拼命學習，先花一個月自己把C語言學起來，接下來就到圖書館借回所有有關資料結構和演算法的書，每天都拼命看。這是我進步最快的時期，當時我在家自己跟著已經進入IOI培訓營的選手們一起練習ACM Online Judge上的題目。每天到學校都在看Introduction to Algorithms，因為沒有電腦，只好用紙筆練習解ACM Online Judge上的問題。白天在學校想解法，回家就在電腦上把程式寫出來，並submit上去看看結果對不對。透過這種方式練習，可以看到自己解出問題的數量不斷增加，強烈的成就感能刺激自己不斷練習不斷思考，如此循環之下真的進步得非常快。

很快地，在我升上高二後，我發現我已經寫了三百多題，進入ACM Online Judge世界排行榜的前幾名了。同時我也發現有另一個跟我一樣每天都增加好幾題的人，沒想到竟然就是跟我同年的建中SBB。雖然我每天都能寫兩三題，但SBB的解題數仍遠遠在我前面，逼得我只好印出所有題目，帶去學校不管上課下課都在紙上解題。就這樣我們的差距慢慢拉進，不知不覺我們也站上排行榜的前兩名。如果我今天多寫一題，我就能暫時站上第一，但隔天馬上又會被他超越過去，彷彿他早就已經囤積了數十題起來等著慢慢折磨我一樣。

就在這樣的刺激下，我就像漫畫中的熱血主角一樣快速成長，進入了勁敵所在的境界。我順利從校內初賽、中區預賽，一路拿第一進到全國決賽。非常戲劇性的是，在這年全國能力競賽，SBB拿了滿分得到第一，我錯了半題排名第二，而全國能力競賽一向是前兩名都為一等獎，也就是說我和SBB原本應該都是一等獎，沒想到評審說我和第一名的滿分有個落差，所以一等獎就改成一名，而我就變成了二等獎第一…(實在很嘔，但也不能怎樣Q_Q)。比賽雖然輸了，但我沒有很難過，因為我知道自己還能再進步，還能變得更強，繼續努力下去我很可能可以選上奧林匹亞的國手。

國手之路

高中各學科的奧林匹亞是每年一度的國際盛事，奧林匹克運動會比的是人類體能的極限，而各學科的奧林匹亞比的則是運用腦力的極限。我第一次是從YJL那聽到這比賽名字的，但那時覺得非常遙遠，因為我看到連他這麼厲害的人都選不上國手，可見這不是一般人能輕易踏進去的領域。

改變我想法的是中一中穿堂的一張照片。中一中有個不錯的傳統，只要代表學校參加比賽或科展獲獎，學校就會把獲獎學生的照片掛在穿堂的榮譽榜上。還記得高一時在穿堂閒晃，一個個欣賞歷屆學長們偉大的功績，突然間發現有個叫CLK的學長厲害得不得了，不但在中區能力競賽拿第一，到了全國也還是第一，而且他還選上了97年IOI的國手。後來我才知道他以前也是中一中電研社的社長，而那屆的副社長也非常厲害，自己寫了一個microkernel作業系統代表台灣去美國參加國際科展。有這些如傳奇一般的學長，給了我很大的激勵作用，我這時突然覺得自己或許也能像他們一樣有照片被掛在上面的一天。現在想起來，還真不知道當時自己怎麼能這麼有信心，其實有種不知天高地厚的感覺。但或許也因為如此，才沒有被這種「看起來很困難」的目標嚇到而連嘗試的勇氣都不敢拿出來。

很有趣的是，在我剛上高一時，CLK是中一中第一個也是唯一一個資訊國手。但就在我高一下的時候，有三個高三的學長竟然同時選上99年IOI的國手。因為一年資訊國手名額只有四個，一直以來都是建中學生呼聲最高，這年我們一口氣拿下三個名額簡直是不可思議的奇蹟。我也因此而信心大增，彷彿我每天在他們旁邊練習也能受到逸出的強者氣息感染而變強一樣。

就在我在全國能力競賽拿到第二名後，我就開始為IOI培訓營做準備。IOI培訓營大約收30人，要關在師大內集訓四週，每天都請教授來上課，每週進行一次模擬考。第二個禮拜結束會先淘汰一次，留下來10個人再繼續廝殺，直到四個禮拜結束。培訓營過後不是馬上就能知道成績，還要過一段時間才會知道四個國手是誰，但因為留到第二階段基本上就等於有了保送任何大學資訊系的資格，所以第二階段的氣氛其實還比較歡樂一些。

在師大集訓的四週讓我認識很多在這個領域頂尖的強者們，我覺得這更勝於實際上在課堂上學到的東西。這些強者們如今都還持續在資訊界的各個領域活躍，常常覺得不管到哪參加活動或研討會都還是可以碰到這些有相同背景的人，可見這個培訓營真的也訓練出許多資訊界的中堅份子。

在集訓時，大家也不是每天各自悶著頭寫程式。其實很不好意思說，當時在培訓營進步最多的可能是魔法氣泡對戰的戰術…。雖然有電腦就會被拿來玩電動，但培訓營的學生還是比較特別。每年培訓營都會流行一些能用程式寫AI來決鬥的遊戲，像是坦克大戰、俄羅斯方塊等等，我們那年流行五子棋，大家利用空閒時間寫五子棋的AI，碰在一起時就讓各自的程式互相決鬥分個高下，玩起來比自己親自下去玩還刺激很多。

經過四個禮拜的集訓，每天討論演算法，每天寫程式，到最後連睡覺都會夢到程式碼。當時因為才高二，也不會覺得壓力很大一定要留到第二階段甚至要選上國手，一直抱持平常心反而意外表現得不錯。結訓過後，我每天沒事就盯著培訓營的網頁看，希望能趕快看到國手名單公佈。就在名單公佈的那天，我盯著螢幕驚訝的說不出話，我竟然真的選上國手了！這真的是平常完全不敢想像的事情，真的沒想到我竟然也有一天能讓自己的照片被掛在中一中的穿堂上….。

(待續)

(本來沒有想寫這麼長的，哪知道一下手後欲罷不能…。看來這系列文章會變成長連載了。)

資訊奧林匹亞與程式競賽

在升上高中前，我因緣際會透過一個國中的同班同學認識了他的哥哥YJL。YJL比我大三年，我要進中一中時他剛好畢業，很巧的是他很會寫程式，一直都是中一中的資訊能力競賽代表隊成員。剛認識他時，他就demo給我看他用QBASIC自己寫的橫向捲軸射擊遊戲，當時看得我目瞪口呆，我完全沒法想像QBASIC竟然能寫出這麼順暢且華麗的遊戲。這個demo如果不說，我一定會以為這是市面上在賣的商業遊戲(我那時還以為一定要學C才能寫出這種遊戲)。

透過YJL我也得知原來高中還有資訊能力競賽和奧林匹亞這種比賽，聽他述說跟全國的高手一起比賽寫程式時，讓我不知不覺也熱血沸騰起來。我把他高中時留下的各種參考資料全帶回家，並透過他認識了更多還在中一中的強者學長們，就這樣在踏進高中校門的同時也決定了我這三年的方向。

這裡我先介紹一下對於高中生最重要的資訊比賽。高中的學科能力競賽是教育部主辦的比賽，包括數學、物理、化學、生物、地球科學、資訊，每間高中通常會先辦個校內初賽來選出代表選手，再由這些選手參加各區域的能力競賽，最後各區的前N名(每科的人數不同)才能參加全國競賽。以資訊科來說，我記得是校內取6名，中區再取6名進全國決賽。到了全國決賽能拿到前10名，還能直接保送進資訊奧林匹亞的培訓營，不用再另外參加培訓營的入營考。至於資訊奧林匹亞(International Olympiad in Informatics, IOI)則是國際性的資訊比賽，參加的人是從每個國家挑選出來的頂尖高中生，每年輪流由一個參賽國舉辦，選手要進行兩天每次連續五個小時的頭腦比賽，其中只有一半的人可以得到獎牌。

這些比賽和一般的程式比賽其實很不一樣。這種比賽比的是解決問題的能力，不是比賽軟體實做的能力。題目比較像數學問題，只是除了紙筆外，還得用某種程式語言實做出能解出正確答案的程式，也就是說參賽者必須想出問題的解法(演算法)，再透過自己擅長的程式語言寫進電腦，讓電腦執行後輸出問題的答案。這種解題比賽主要考驗的是運用資料結構和演算法以有效率的方法解決問題，並寫出正確程式的能力。大學有個類似的比賽是ACM ICPC，問題類型和IOI很類似，但比賽的模式和方法則有很大差異，有興趣的人可以自行尋找相關資料。雖然IOI是給高中生參加的比賽，但IOI題目的水準其實非常高，如果你能輕易解出IOI的問題，那… 我跟你打賭去Google面試也有99%的機率會通過。順便一提，Google Code Jam就是一個開放給所有人參加的解題比賽，題目類型就跟IOI和ACM ICPC差不多，前一百名就有獎金，還能免費去Google Mountain View總部玩一玩喔。

參加比賽是一個評估自己實力的好方法，沒在比賽會場上較勁過，真的很難體會解題與寫程式能力的差距可以有多麼巨大。一個頂尖的程式設計師和一個普通的程式設計師，其生產力是很輕易的能有十倍甚至百倍以上的差距，而寫出來的程式碼品質及效率也是同樣會有如此巨大的落差。

透過良性的競爭，高中這段時間也成了我進步最快的一個時期…..

(待續)