nonogram 漫談 - 3 TCGA2015

之後約三年多沒再改程式，只是有時會想到一些沒機會實作的點子。今年春假時翻了幾篇最近幾年的論文，發現用 SAT solver 來解 nonogram 有好幾個突出的成果，讓我又冒出一些新想法(結合傳統 solver 跟 SAT solver 的用到的技術)，便考慮今年再次參賽。

再來就是了解現在參賽程式的發展。說到這個我就要抱怨一下。TCGA 及 TAAI 辦的比賽(我是指各項比賽，不只 nonogram)某些資訊不夠公開，譬如有時比賽規則細節從略，有時比賽結果只有名次，沒有比數或棋譜/數據，有幾年甚至連名次都很難找到。(今年的狀況似乎還可以)。雖然比賽後其實有結賽報告，但那只有訂閱期刊才看得到，且限於篇幅沒有完整的資料。我並不認為這是故意隱瞞，但我覺得這部分沒做好，其實是會間接影響這領域的發展的。

想像有個無聊的人(我? :p) 或是有個學生，對某個棋類感到好奇，說不定他本來看一看棋譜發現當下的程式不過爾爾，有為者亦若是寫個更強的，或是覺得某個課題有趣想找這幾年的冠軍討論。但實際上他上網查到的只有殘缺不全的資訊，說不定就澆息他的想法了，覺得那是一個自己玩自己的小圈圈。

也許我比較理想化，我覺得這比賽還算是學術活動，雖然各自的程式不公開，還是要盡量「可重現」(別人用一樣的機器、類似的做法，應該要有辦法做出類似的結果)。但實際上就算報名了比賽，可能還是不知道對方用什麼機器，看不到對方跟別人對弈的棋譜。

扯遠了，回到主題。我去信詢問這次比賽的規則及最近幾次的賽況，了解到今年規則大致上沒有差太多，這幾年 nonogram 的交大第一名的程式自 2011 年後也沒什麼改動。雖然我的程式還沒完成，還是先報名了 :) 畢竟對我而言有個寫程式自娛的機會，還到會場去看看這領域的進展，跟一些朋友、老師聊聊，都很有意思，比賽名次只是附帶的。

我也回頭看了一下我舊的程式，TAAI11 時，程式在第 510 題卡了 81 分鐘(直到比賽結束還沒解出來)，應該是程式有 bug 掉到無窮迴圈，而不是單純算得慢。

這回我的程式計畫是，先重構我舊的程式，實作交大論文的 fully probe, FP2, 還有 search heuristic 當作 baseline，然後再開始試驗結合 SAT solver (其實我有做點小實驗，效果還不錯)。程式檔名就叫 baseline，只是沒想到後來光最佳化 baseline 就用掉了我全部的時間。

照著論文實作的好處是，有數據可以對照知道自己有沒有誤解論文。我發現我大方向是對的，搜尋次數是一樣的，但問題出在算一樣的東西我的就是比較慢。用時間複雜度來說明就是，整個演算法是 O(a * b^n * n^c)，這是指數時間演算法，我的 search heuristic 跟論文相同，其他部分也正確，所以 search node 跟論文一樣多，也就是 b 一樣大。但是我的程式比較慢，也許是選用的基本資料結構不同造成 a 比較大，或是一些實作細節的不同 c 比較大……所以我就一路最佳化我的程式，從大約三倍慢一直改進到慢 40%。

這次的比賽結果，交大第一名，1000 題花了 908 秒, 我拿第二花了 1135 秒，第三名 3737 秒，第四名兩小時解了 232 題。只慢 20% 是因為我稍微調整了 choose weight 的參數(比較小的 b，不過我其實不是很有把握)。也就是說我的程式只有一點參數不同，其他部份其他部分跟第一名的程式沒什麼兩樣，這是比較無趣的地方(理想上大家用不同做法，百花齊放，有趣多了)。
(技術細節我在接下來的文章再談)

這次比賽花了我一個禮拜的休假，加上兩個禮拜下班後的時間。我原本都在 linux 上開發，由於比賽要在 windows 上跑，我在前兩天才開始下載 Visual Studio Express 2013，所以程式還沒有針對 windows/vc++ 作最佳化。在賽後我改用 mingw64-g++ 並調整 compiler 參數，還可以快 15%，也就是說跟第一名只差 5% 左右。所以我可以很阿 Q 的說，只要再一個禮拜就可以贏了 :P (我也試了 Intel system studio 2015 free trial 裡附的 intel c++ compiler 15.0，但沒有比較快，不過我跟 intel c++ compiler 參數也不熟就是了)