最近很火的山楂串小游戲桶现，游戲鏈接http://www.wesane.com/game/848/也糊，是一個(gè)合成類的小游戲藤抡，游戲截圖如下所示咏窿。這個(gè)游戲我曾經(jīng)打到過31串碌秸。作為一名程序員荷腊，一個(gè)自然而然的問題就是艳悔，能否寫一個(gè)山楂串求解器打出更高的分?jǐn)?shù)。編寫這樣一個(gè)求解器大概相當(dāng)于leetcode中等難度的題目女仰，但是我想從更多的角度來看這個(gè)問題猜年。
我的第一版代碼是用python寫的，算法就是簡單的暴力求解+剪枝疾忍，包括測試代碼在內(nèi)也就200行出頭乔外。但是我遇到了第一個(gè)問題：程序的性能太低了，完成一次4步運(yùn)算需要的時(shí)間為20s左右一罩。這個(gè)時(shí)間是不可忍受的杨幼，我的期望值是做到秒的量級。于是我進(jìn)行了第一步改進(jìn)：多線程聂渊。但出乎我意料的是推汽，python多線程的性能反而降低了。性能數(shù)據(jù)顯示歧沪，python并沒有完全做到多線程歹撒。在網(wǎng)上搜索之后，我發(fā)現(xiàn)問題出在python解釋器的GIL上诊胞。這是一個(gè)全局鎖暖夭，每個(gè)線程只有搶到這個(gè)鎖之后才能執(zhí)行锹杈，從而造成了運(yùn)行時(shí)間不降反升。于是我開始嘗試突破GIL迈着，一個(gè)直觀的方法就是換一個(gè)支持多線程的python解釋器竭望，我選擇了jython，Jython是用java寫的python解釋器裕菠。實(shí)際測試結(jié)果不理想咬清，除了要忍受jython較長的啟動(dòng)時(shí)間，實(shí)際運(yùn)算時(shí)間在12s左右奴潘，這離我的期望還是很遠(yuǎn)旧烧。
隨后我開始考慮換用其他編程語言來完成這件事，我想到了lua画髓，號稱具有python的便利性和接近C的性能掘剪。于是我用lua語言重寫了相關(guān)代碼。Lua的單線程測試結(jié)果為4s奈虾，這個(gè)結(jié)果到達(dá)了我的接受范圍夺谁。在此基礎(chǔ)，我再次嘗試編寫多線程的代碼肉微。但是我驚奇的發(fā)現(xiàn)匾鸥，lua也不支持多線程，而是支持所謂的協(xié)程碉纳，其效果與python類似勿负，也是搶占式的執(zhí)行。
事已至此村象，我決定編寫C++的代碼笆环，此前覺得C++的代碼有些難寫，因此一直回避厚者。但為了性能躁劣，還是需要C++的幫助。我用C++重寫了單線程代碼库菲，在使用了-O2的編譯選項(xiàng)之后账忘，C++的測試結(jié)果達(dá)到0.2s。這個(gè)結(jié)果反而再次令我陷入了沉思熙宇，因?yàn)樵谶@個(gè)基礎(chǔ)上進(jìn)行多線程擴(kuò)展鳖擒，可能已經(jīng)沒有多少性能可以繼續(xù)挖掘了。
在實(shí)現(xiàn)CPP的多線程版本時(shí)烫止，發(fā)了幾個(gè)問題蒋荚。一個(gè)是thread對象不能被push進(jìn)vector，只好用thread數(shù)組加flag的方式實(shí)現(xiàn)馆蠕。二是多線程的時(shí)間測量是個(gè)問題期升，測出來的時(shí)間是所有子線程時(shí)間的總和惊奇，這里用std::chrono::system_clock::now()來統(tǒng)計(jì)墻上時(shí)間。三是直接啟動(dòng)了30個(gè)線程播赁，如果能控制系統(tǒng)中一直有8個(gè)線程可能性能會(huì)更好的一點(diǎn)颂郎。最終可以在0.05s內(nèi)計(jì)算4步。
這個(gè)項(xiàng)目到此并沒有結(jié)束容为，我還想繼續(xù)挖掘乓序。
能否實(shí)現(xiàn)在python中調(diào)用該C++代碼？
能否實(shí)現(xiàn)OCR和鼠標(biāo)點(diǎn)擊自動(dòng)打游戲坎背？
使用強(qiáng)化學(xué)習(xí)或者深度學(xué)習(xí)效果如何替劈？
能夠完成圖形界面，提供更好的游戲體驗(yàn)沼瘫？
相關(guān)代碼已經(jīng)在github開源https://github.com/ExquisiteFunction/shanzhachuan 抬纸，希望有大佬一起來繼續(xù)挖掘這個(gè)小游戲帶來的技術(shù)力咙俩。
