在calcitem朋友的幫助下,我硬著頭皮學了cpp,之後製作了一個「混亂時鐘」的破解程式。
2月17日左右,我用js完成了這個程式的基本邏輯算法。但是js的性能只允許從第七步算起。(目標是從開局開始算)
後來我就把程式邏輯原封不動的改寫成了cpp,程式效能提升到了第五步。
後來我偶然想到,可以改成位運算:long有8byte,每個字節有8bit。每四個bit可以表示一個數字。
於是我就用位運算改寫了這個程式,版本為chaosclock2。
後來加入了哈希排重(chaosclock3.cpp),能算到開局了!當時我欣喜若狂,calcitem也很開心。
但是仍然有些局面算不完。後來經研究,程式總會重覆行走某些能夠循環繞圈的棋子。在加上了限制循環走子之後,現在的最新版本是choasclock4.cpp。
曾兩度想要放棄
這場cpp開發馬拉松,實在是曠日持久,有時我跟calcitem都不約而同的開發到半夜一兩點,興奮著不知疲倦。
在2月23日時,我其實已經準備爛尾了。我當時感歎:做個弈棋AI好像還是有點太難了!
當日我還生成了經典的「第七頁局面」。
但是calcitem不知道我將放棄的打算,他還在提交和更新他的代碼,只是他寫的無法判定同輸,然後我還拍了視頻來介紹何為同輸。
3月3日,當我向calcitem介紹了我寫的(爛尾)版本之後,calcitem認為是可行的,並幫我優化了它的效能。這樣,原本已經放棄的我又重新啟動了。
後來我想到要用位運算重新寫一個,就能極大增加運算效率。在加了位運算和哈希排重後,它終於算到了開局。這時我跟calcitem都很興奮。
這時我們都以為「成功」了,因為連這麼複雜的第七頁局面都能算出來,那還有甚麼局面是算不了的?
然而,我低估了混亂時鐘的可能複雜程度,後來又遇到了一個難以算完的局面。
這時我再度想要放棄,因為即便提高了map的容量,以及各種方法(包括「困難模式」等等),仍然算不完這個局面。
當時我還想是否先去購兩根大的內存條,之後再來開發。
轉念一想又不對,「買內存條」絕不是一個對的方向。
於是我著手研究,為何這個似乎不算複雜的局面會算不完?
查到,2,3,4,6,8,9,10這幾個數字,在棋盤上可以循環走子。很多情況下,循環走子是無意義的。會增加非常龐大的無效數據。
最終我想到了限制循環走子,減少這種無意義的走動。經過測試,這個剪枝方法是有效的。那個局面從第8步起禁止循環,就能算完全部走法。
這樣第二個出現的困難,柳暗花明,最終得以戰勝。
鳴謝
calcitem朋友為這個項目,給出了很多有效的指導意見,付出了比我更多的勞動。如此熱情,寡人在此表示衷心感謝!無以為報,日後若有可效勞之處,寡人定當鼎力相助!
calcitem製作的san-mill(直棋)是享譽全球弈棋界的一款開源作品,當初只跑在android上,現在對windows、ios、linux都跨平臺支持。AI棋力也相當高,不是人類能輕易戰勝的。寡人非常榮幸能得到calcitem的指教!