國中時有同學帶了尖瑞出版社的一本 "解題畫冊"(我忘了當時的書名) 來學校玩，那時還不流行數獨，不過就類似那感覺，每一頁就是一題，用紙筆加上邏輯推理，解出謎底的圖案。印象中那時會跟同學抄題目到自己的計算紙上玩。雖然覺得很有趣但好像沒有一直玩下去，現在回想大概是抄題、解題太累了，而且沒有跟同學競技的快感 (那時還會玩三角殺棋(當時我們叫三角棋)，幾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月)，這回我就幫忙修改比賽規則，改回單純的比賽解題速度，可是也比較無趣 (相較於其他棋類你來我往的廝殺)，往後幾年比賽的規則大致上延用。
沒有留言 :
張貼留言