一堂好課

我對課程是很挑剔的。老師教得不好、簡報難以理解、過多的背誦等,都是我時常靠北的東西。因此,這學期爭取到當助教的機會時,我很開心。我希望能在資財系上實現一堂好課,一堂系上一直缺乏的資訊好課。

不過,我能做到的東西有限。一方面必須與老師上課的模式與進度配合、一方面必須拿捏同學們可以承受的作業難度。我能做的,僅是在種種限制下,盡可能將題目出得有趣、架 Online Judge 讓同學的知識不僅限於書本中、將我能做的,為數不多的事情做好。我也並不是多麼厲害的人,只是希望能運用自己為數不多的知識,為資財系帶來一點改變。

雖然早就做好這堂課結束大概會被不少人討厭的心理準備,但在我一筆一筆改著同學們期中考卷的同時,看著同學一句一句的課程評論,心理其實也是很難過的。

這次考試,我出的題目就只有第五題 40% 的題組。接著,就讓我在這沒有人會看的地方,說說我出題的思路吧。

Gomoku

這一題主要建立在 Homework 2 上機第二題的解 OOXX 題之上。相信大家會在考試前把作業完成,應該是再合理也不過的事,因此我假設大家都已經至少知道 OOXX 的作法。

In homework 2, we’ve practiced the concepts on how to create a computer program that could decide a best position, given a tic-tac-toe game state. Now, lets utilize your knowledge on the game of Gomoku (五子棋).
In this problem, we assume that the rules are identical to standard Gomoku rules, but the board size is variable.
Input: 
bx: The height of the board. (bx ≥ 5) 
by: The width of the board. (by ≥ 5) 
role: w(white) or b(black). 
board: An array of board_x × board_y, which contains w, b, or .(empty) information.

5-1

Given a game state of Gomoku, please propose an algorithm to find out the next “best” step.

出這題其實是送分,希望大家能拿些基本的分數。只要寫過 OOXX 大概就能知道,time complexity 的話直接 DFS 爆搜就能找到最佳解。我甚至沒有寫這題的答案,就是直接從 Judge 上 OOXX 的 code template 直接複製過來就是解答了。

這也意味著其實 Judge 上的 template 根本就是完整的 pseudo code,照著寫幾乎就會過了。

5-2

Yixin (奕心) is one of the best Gomoku computer AI in the world. If time is not limited for both Yixin and your algorithm, which one do you think will win? (Your Algorithm / Yixin / Both Possible) Why?

這題在考大家有沒有理解自己在 5-1 的 algorithm 中寫了什麼。由於 5-1 會把所有可能性都看過一遍,因此絕對比任何沒有全部搜完的 AI 來得好,因為不管目前棋盤的狀態為何,你都能看到每一步對你來說的結果如何,進而做出決定。

5-3

Analyze the time complexity of your proposed algorithm in Problem 5-1.

這題在考大家 DFS 的 time complexity。由於棋盤每個位子都會試走過一遍,考慮最糟的結果就是每種走法都試到棋盤滿為止,也就是 Factorial(剩餘的格子) x DFS function 內的時間複雜度。

5-4

Given a computer that could do O(10^7) in 1 second, how many seconds would it take for it to determine the next step under the following input?
bx = 5
by = 5 
role = b 
bw... 
b...w 
.bww. 
b.bwb 
.b.w.

這題在考大家如何將時間複雜度用來估算執行時間,這是在做 Judge 每一題前都應該要做的,否則可能寫了好久才發現自己這個方法根本無法在時限內完成。

作法大家也基本上有寫出來,但許多人還是犯了些很基礎的錯誤。如果題目給你的變數是 bx, by,在寫 big O 的時候就要用 bx, by,而不是憑空創造出 n 寫成 O(n^2)。這點我記得小考就有扣過許多人分數,但還是有許多人還是犯了同樣的錯。

5-5

Since human beings have limited time, please propose another algorithm that derives a position that is still relatively good but more efficient.
(Hint: You can assume that you have a function evaluate(board, player) that returns a score representing “how good the current game state is for player”.)

這題開始才是我認為大家寫不出來是挺正常的題目,主要是希望能讓同學能自己從本來的 DFS (min max) 延伸到 alpha beta 的概念。就算無法延伸,能在 5-1 的 algorithm 上做任何能降低 time complexity 的變化我覺得都沒問題。

5-6

Using the same computer and input, how many seconds would it take for your new algorithm to determine the next step?

這題主要是讓大家比較做調整前與調整後的算法可以進步多少,體會一下一個改變能為執行時間帶來多大的進步。


我至今仍然記得自己在學的時候第一次寫出 OOXX 的成就感有多大,是多麼新奇的主題,因此這個主題早在課程開始前好一陣子就已經想好的。我希望大家能感受到,演算法並不只能拿來解解 Judge 上不存在於現實中的問題,而是能在自己的生活中運用上的。

這次第 5 題寫的好的大概僅有 5 位左右,肯定是出太難了。但我們如果再看看有寫出 Judge OOXX 題的人數:2 位。我也知道這題並不簡單,或許拿給同屆的也沒幾個人會寫。我自己好一陣子沒寫,也寫了 1 小時左右,室友也寫了約 3 個小時,或許要另一位助教寫也需要幾個小時。

然而,正是因為花了時間,才會有所進步。正是因為你經過了數小時的思考,你才能理解模擬對奕到底實際上在做什麼。上述第五題不要說在寫完之後就肯定會每一題,但幾乎可以穩拿一半的分數。而事實上,有主動來詢問我這題的人,在考試上也拿到了相對不錯的成績。

因此,這題或許不簡單,但絕非不可能完成的。


「白痴喔不要這樣搞他們啦。」還記得在跟另一個助教討論本題的時候,他突然說出了這樣一句話。老實說,我其實是挺生氣的。

怎麼樣出才能有一個脈絡?怎麼樣出才能讓同學運用自己現有的知識,再用自己的力量多踏出一步?這些題目都我是自己花時間構思出來的,上網查絕對找不到一樣的問題。每一題也都有確實想考驗同學的觀念,而不是為難而難。

我也可以出跟課本一模一樣的題目,讓大家翻翻講義,答案背起來,三個小時內準備完考試。但是,這樣真的學得到東西嗎?把看過的東西原封不動地寫上答案卷,真的有意義嗎?在職場上遇到問題時,Google 就查得到的東西,真的有需要你們背起來嗎?

我期待大家得到的是知識,而不是只有成績單上的一欄修課證明,以及一個數年後便毫無用處的成績。


關於同學反映的意見,我們也都有在討論如何改進。以下是我的個人看法,並不代表老師跟助教的立場。

  • 上課內容與作業考試關係不大,那不如就不要上課好了?
沒錯!線上課程的好處是你可以先寫作業,不會再回去看線上課程,至少我都是這麼做的。我喜歡先理解問題的形式,這樣更有助於理解解決問題的作法,也就是所謂的 Top-Down Learning。而如果你已經理解觀念了,不上課當然沒有任何問題。
  • 上課應該講解題目?
這點我認為是否定的。老師上課就是把某個演算法的觀念教給你而已,將其運用並解決問題是你的工作。如果解不出來,可以參考網路上相似題目的作法、不會再問同學、再不會就把自己嘗試過的東西統整起來,並把有疑問的地方拿來問助教。

關於不能改進的部分,大概就是以上兩點了。我們能做的大概就是開一個討論區,讓大家能夠更容易地發問與討論。我們沒辦法改變老師的上課模式、逼同學寫作業、或直接告訴同學作業哪一題會考。

如果有任何對課堂的其他建議,也歡迎直接私訊我。


最後,該調的分還是會調,但該有的水準還是要有。希望大家不要看到成績就打退堂鼓,能堅持下去,從這堂課中帶走些東西,也希望同學們在修完這堂課時能夠認為,這是一堂有學到東西的課,一堂好課。