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 參數也不熟就是了)

nonogram 漫談 - 2

我跟 nonogram 的故事要從國中開始說起 :)

國中時有同學帶了尖瑞出版社的一本 "解題畫冊"(我忘了當時的書名) 來學校玩，那時還不流行數獨，不過就類似那感覺，每一頁就是一題，用紙筆加上邏輯推理，解出謎底的圖案。印象中那時會跟同學抄題目到自己的計算紙上玩。雖然覺得很有趣但好像沒有一直玩下去，現在回想大概是抄題、解題太累了，而且沒有跟同學競技的快感 (那時還會玩三角殺棋(當時我們叫三角棋)，幾A幾B等等)

後來在某一年(可能是 2001)的 IOI 研習營期中考題，就有老師出了一題叫「海島地圖」其實就是 nonogram ，我那時還去幫忙寫 test data 跟參考解答。後來(應該是 2003)我到建中幫忙出校內比賽的題目，就拿一樣的題目來用。當時題目要求輸出全部符合條件的圖形，我對 nonogram 的理解就是 search 題，不過並不要求大家在比賽時限內寫出任何 heuristic，所以 n 給得並不大，只要能正確的 DFS search 就可以拿到超過一半的分數，若 search 時有稍微考慮不跟相臨顏色的條件衝突，差不多就能拿滿分。程式碼約 100~200 行就可以完成。只是印象中大部分的人都拿不到一半的分數。

後來查資料才發現，IOI '92 那年有題 "Islands in the Sea" 相信就是研習營出題的來源。'92 年的測試資料最大  8*8。另外，ICPC '93 年有一題 "Scanner" 應該也算相關的題目，記得 '97 集訓寫考古題時大家都卡住，只有 lckung 學長成功解出。

大學時出現了一系列 logic 遊戲的網站，我還有一些同學有時會玩玩上面的遊戲打發時間。這些遊戲 (Nonogram, Slither Link, Sudoku, Light Up, Bridges, Shikaku, Nurikabe, Dominosa) 有些還有人發表論文研究，有幾項還成為 Computer Olympiad 或其他類似 conference 的比賽項目。 (Computer Olympiad 每年會辦許多電腦棋類比賽(西洋棋、象棋、圍棋甚至橋牌、撲克)，我偶爾會關心一下比賽了解最近發展的狀況。)

我在 2011 年時才發現 nonogram 2010 年開始有辦比賽，也就開始讀相關的論文跟網路資訊，我發現當時網路上已經有幾個很強的 nonogram solver，但是大部分的論文都沒提到這件事(也許是論文發表的時間差，譬如 BGU 2010 年不錯的成果，論文 2012 投稿，2014 才登出來已經晚了；除此之外，我是覺得有些論文，該怎麼說呢，參考價值不高)。

我當時也覺得比賽規則有很大的問題。也許是想增加競爭趣味，比賽方式是雙方互相出題給對方解。但出題是在事先準備好的，沒有資源限制，所以可以隨機產生大量題目，用大量 CPU 把簡單的題目過濾掉，只要有足夠的計算資源，我相信可以做到比賽時限內沒有人可以解出任何一題 ;)

當時我的做法就是這樣：先隨機產生幾百個題目當種子，然後用程式去解，把解得比較快的題目丟掉，解得比較慢的題目隨機改幾個顏色(黑變白或反過來)當作新的題目。然後跟朋友借一些 CPU 來跑(我忘了多少，大概有數十顆)，跑了也許一個禮拜吧。

當時覺得這比賽參賽者可能不是很強(根據前一年的賽後報告)，比賽規則又不是很公平(或說有漏洞)，所以我就報名參賽 TCGA2011 (6月)，程式取名 Naughty，就是說我是來搗蛋的 :) 從程式開始寫到比賽不到兩個禮拜，事實上比網路上抓得到的 solver 還弱，結果拿第一名。

到了年底另一個比賽 (TAAI2011, 11月)，這回我就幫忙修改比賽規則，改回單純的比賽解題速度，可是也比較無趣 (相較於其他棋類你來我往的廝殺)，往後幾年比賽的規則大致上延用。

不過半年不見，交大的隊伍重組，程式演算法大改進，這回就換我被痛宰了 XD (現在回頭看當年的紀錄，我才發現四年前他們用的電腦比今年比賽用的還快 orz 還好近幾年規則改成統一用同一台電腦跑了)

交大 2013 年也發表了一篇 paper 解釋他們的做法，有興趣寫 nonogram solver 的話值得一讀。