最近， 微信小遊戲跳一跳可以說是火遍了全國， 從小孩子到大孩子仿佛每一個人都在刷跳一跳， 作為無（zhi）所（hui）不（ban）能（zhuan）的AI程式師， 我們在想， 能不能用人工智慧（AI）和電腦視覺（CV）的方法來玩一玩這個遊戲？
於是， 我們開發了微信跳一跳Auto-Jump演算法， 重新定義了玩跳一跳的正確姿勢， 我們的演算法不僅遠遠超越了人類的水準， 在速度和準確度上也遠遠超越了目前已知的所有演算法， 可以說是跳一跳界的state-of-the-art。
自動跳一跳的安裝教程請參考GitHub倉庫： https://github.com/Prinsphield/Wechat_AutoJump
下面我們詳細介紹我們的演算法。
演算法的第一步是獲取手機螢幕的截圖並可以控制手機的觸控操作， 我們的github倉庫裡詳細介紹了針對Android和IOS手機的配置方法
你只需要按照將手機連接電腦， 按照教程執行就可以完成配置。 在獲取到螢幕截圖之後， 就是個簡單的視覺問題。 我們需要找的就是小人的位置和下一次需要跳的檯面的中心。
如圖所示， 綠色的點代表小人當前的位置， 紅點代表目標位置。
多尺度搜索（Multiscale Search）
這個問題可以有非常多的方法去解， 為了糙快猛地刷上榜， 我一開始用的方式是多尺度搜索。 我隨便找了一張圖， 把小人摳出來， 就像下面這樣。
另外， 我注意到小人在螢幕的不同位置，
多尺度搜索的代碼示例：
我們來試一試， 效果還不錯， 應該說是又快又好， 我所有的實驗中找小人從來沒有失誤。 不過這裡的位置框的底部中心並不是小人的位置，
同理， 目標檯面也可以用這種辦法搜索， 但是我們需要收集一些不同的檯面， 有圓形的， 方形的， 便利店， 井蓋， 棱柱等等。 由於數量一多， 加上多尺度的原因， 速度上會慢下來。 這時候， 我們就需要想辦法加速了。
首先可以注意到目標位置始終在小人的位置的上面， 所以可以操作的一點就是在找到小人位置之後把小人位置以下的部分都捨棄掉， 這樣可以減少搜索空間。 但是這還是不夠， 我們需要進一步去挖掘遊戲裡的故事。 小人和目標檯面基本上是關於螢幕中心對稱的位置的。 這提供了一個非常好的思路去縮小搜索空間。 假設螢幕解析度是（1280， 720）的， 小人底部的位置是（h1, w1),那麼關於中心對稱點的位置就是（1280 - h1， 720 - w1）， 以這個點為中心的一個邊長300的正方形內， 我們再去多尺度搜索目標位置， 就會又快有准了。
效果見下圖， 藍色框是（300， 300）的搜索區域， 紅色框是搜到的檯面， 矩形中心就是目標點的座標了。
加速的奇技淫巧（Fast-Search）
玩遊戲需要細心觀察。我們可以發現，小人上一次如果跳到檯面中心，那麼下一次目標檯面的中心會有一個白點，就像剛才所展示的圖裡的。更加細心的人會發現，白點的RGB值是（245，245，245），這就讓我找到了一個非常簡單並且高效的方式，就是直接去搜索這個白點，注意到白點是一個連通區域，圖元值為（245，245，245）的圖元個數穩定在280-310之間，所以我們可以利用這個去直接找到目標的位置。這種方式只在前一次跳到中心的時候可以用，不過沒有關係，我們每次都可以試一試這個不花時間的方法，不行再考慮多尺度搜索。
講到這裡，我們的方法已經可以運行的非常出色了，基本上是一個永動機。下面是用我的手機玩了一個半小時左右，跳了859次的狀態，我們的方法正確的計算出來了小人的位置和目標位置，不過我選擇狗帶了，因為手機卡的已經不行了。
這裡有一個示例視頻：
視頻載入中...到這裡就結束了嗎？那我們和業餘玩家有什麼區別？下面進入正經的學術時間，非戰鬥人員請迅速撤離！
CNN Coarse-to-Fine 模型
考慮到IOS設備由於螢幕抓取方案的限制（WebDriverAgent獲得的截圖經過了壓縮，圖像圖元受損，不再是原來的圖元值，原因不詳，歡迎瞭解詳情的小夥伴提出改進意見~）無法使用fast-search，同時為了相容多解析度設備，我們使用卷積神經網路構建了一個更快更魯棒的目標檢測模型，下面分資料獲取與預處理，coarse模型，fine模型，cascade四部分介紹我們的演算法。
資料獲取與預處理
基於我們非常準確的multiscale-search、fast-search模型，我們採集了7次實驗資料，共計大約3000張螢幕截圖，每一張截圖均帶有目標位置標注，對於每一張圖，我們進行了兩種不同的預處理方式，並分別用於訓練coarse模型和fine模型，下面分別介紹兩種不同的預處理方式。
Coarse 模型資料預處理
由於每一張圖像中真正對於當前判斷有意義的區域只在螢幕中央位置，即人和目標物體所在的位置，因此，每一張截圖的上下兩部分都是沒有意義的，因此，我們將採集到的大小為1280*720的圖像沿x方向上下各截去320*720大小，只保留中心640*720的圖像作為訓練資料。
我們觀察到，遊戲中，每一次當小人落在目標物中心位置時，下一個目標物的中心會出現一個白色的圓點，
考慮到訓練資料中fast-search會產生大量有白點的資料，為了杜絕白色圓點對網路訓練的干擾，我們對每一張圖進行了去白點操作，具體做法是，用白點周圍的純色圖元填充白點區域。
Fine 模型資料預處理
為了進一步提升模型的精度，我們為fine模型建立了資料集，對訓練集中的每一張圖，在目標點附近截取320*320大小的一塊作為訓練資料，
為了防止網路學到trivial的結果，我們對每一張圖增加了50圖元的隨機偏移。fine模型資料同樣進行了去白點操作。
Coarse 模型
我們把這一問題看成了回歸問題，coarse模型使用一個卷積神經網路回歸目標的位置
經過十小時的訓練，coarse模型在測試集上達到了6圖元的精度，實際測試精度大約為10圖元，在測試機器（MacBook Pro Retina, 15-inch, Mid 2015, 2.2 GHz Intel Core i7）上inference時間0.4秒。這一模型可以很輕鬆的拿到超過1k的分數，這已經遠遠超過了人類水準和絕大多數自動演算法的水準，日常娛樂完全夠用，不過，你認為我們就此為止那就大錯特錯了~
Fine 模型
fine模型結構與coarse模型類似，參數量稍大，fine模型作為對coarse模型的refine操作
經過十小時訓練，fine模型測試集精度達到了0.5圖元，實際測試精度大約為1圖元，在測試機器上的inference時間0.2秒。
Cascade
總體精度1圖元左右，時間0.6秒。
總結
針對這一問題，我們利用AI和CV技術，提出了合適適用於IOS和Android設備的完整解決方案，稍有技術背景的使用者都可以實現成功配置、運行，我們提出了Multiscale-Search，Fast-Search，CNN Coarse-to-Fine三種解決這一問題的演算法，三種演算法相互配合，可以實現快速準確的搜索、跳躍，使用者針對自己的設備稍加調整跳躍參數即可接近實現“永動機”。講到這裡，似乎可以宣佈，我們的工作terminate了這個問題，微信小遊戲跳一跳game over！
友情提示：適度遊戲益腦，沉迷遊戲傷身，技術手段的樂趣在於技術本身而不在遊戲排名，希望大家理性對待遊戲排名和本文提出的技術，用遊戲娛樂自己的生活
聲明：本文提出的演算法及開原始程式碼符合MIT開源協定，以商業目的使用該演算法造成的一切後果須由使用者本人承擔
End.
運行人員：中國統計網小編
中國統計網，是國內最早的大資料學習網站
//www.itongji.cn
加速的奇技淫巧（Fast-Search）
玩遊戲需要細心觀察。我們可以發現，小人上一次如果跳到檯面中心，那麼下一次目標檯面的中心會有一個白點，就像剛才所展示的圖裡的。更加細心的人會發現，白點的RGB值是（245，245，245），這就讓我找到了一個非常簡單並且高效的方式，就是直接去搜索這個白點，注意到白點是一個連通區域，圖元值為（245，245，245）的圖元個數穩定在280-310之間，所以我們可以利用這個去直接找到目標的位置。這種方式只在前一次跳到中心的時候可以用，不過沒有關係，我們每次都可以試一試這個不花時間的方法，不行再考慮多尺度搜索。
講到這裡，我們的方法已經可以運行的非常出色了，基本上是一個永動機。下面是用我的手機玩了一個半小時左右，跳了859次的狀態，我們的方法正確的計算出來了小人的位置和目標位置，不過我選擇狗帶了，因為手機卡的已經不行了。
這裡有一個示例視頻：
視頻載入中...到這裡就結束了嗎？那我們和業餘玩家有什麼區別？下面進入正經的學術時間，非戰鬥人員請迅速撤離！
CNN Coarse-to-Fine 模型
考慮到IOS設備由於螢幕抓取方案的限制（WebDriverAgent獲得的截圖經過了壓縮，圖像圖元受損，不再是原來的圖元值，原因不詳，歡迎瞭解詳情的小夥伴提出改進意見~）無法使用fast-search，同時為了相容多解析度設備，我們使用卷積神經網路構建了一個更快更魯棒的目標檢測模型，下面分資料獲取與預處理，coarse模型，fine模型，cascade四部分介紹我們的演算法。
資料獲取與預處理
基於我們非常準確的multiscale-search、fast-search模型，我們採集了7次實驗資料，共計大約3000張螢幕截圖，每一張截圖均帶有目標位置標注，對於每一張圖，我們進行了兩種不同的預處理方式，並分別用於訓練coarse模型和fine模型，下面分別介紹兩種不同的預處理方式。
Coarse 模型資料預處理
由於每一張圖像中真正對於當前判斷有意義的區域只在螢幕中央位置，即人和目標物體所在的位置，因此，每一張截圖的上下兩部分都是沒有意義的，因此，我們將採集到的大小為1280*720的圖像沿x方向上下各截去320*720大小，只保留中心640*720的圖像作為訓練資料。
我們觀察到，遊戲中，每一次當小人落在目標物中心位置時，下一個目標物的中心會出現一個白色的圓點，
考慮到訓練資料中fast-search會產生大量有白點的資料，為了杜絕白色圓點對網路訓練的干擾，我們對每一張圖進行了去白點操作，具體做法是，用白點周圍的純色圖元填充白點區域。
Fine 模型資料預處理
為了進一步提升模型的精度，我們為fine模型建立了資料集，對訓練集中的每一張圖，在目標點附近截取320*320大小的一塊作為訓練資料，
為了防止網路學到trivial的結果，我們對每一張圖增加了50圖元的隨機偏移。fine模型資料同樣進行了去白點操作。
Coarse 模型
我們把這一問題看成了回歸問題，coarse模型使用一個卷積神經網路回歸目標的位置
經過十小時的訓練，coarse模型在測試集上達到了6圖元的精度，實際測試精度大約為10圖元，在測試機器（MacBook Pro Retina, 15-inch, Mid 2015, 2.2 GHz Intel Core i7）上inference時間0.4秒。這一模型可以很輕鬆的拿到超過1k的分數，這已經遠遠超過了人類水準和絕大多數自動演算法的水準，日常娛樂完全夠用，不過，你認為我們就此為止那就大錯特錯了~
Fine 模型
fine模型結構與coarse模型類似，參數量稍大，fine模型作為對coarse模型的refine操作
經過十小時訓練，fine模型測試集精度達到了0.5圖元，實際測試精度大約為1圖元，在測試機器上的inference時間0.2秒。
Cascade
總體精度1圖元左右，時間0.6秒。
總結
針對這一問題，我們利用AI和CV技術，提出了合適適用於IOS和Android設備的完整解決方案，稍有技術背景的使用者都可以實現成功配置、運行，我們提出了Multiscale-Search，Fast-Search，CNN Coarse-to-Fine三種解決這一問題的演算法，三種演算法相互配合，可以實現快速準確的搜索、跳躍，使用者針對自己的設備稍加調整跳躍參數即可接近實現“永動機”。講到這裡，似乎可以宣佈，我們的工作terminate了這個問題，微信小遊戲跳一跳game over！
友情提示：適度遊戲益腦，沉迷遊戲傷身，技術手段的樂趣在於技術本身而不在遊戲排名，希望大家理性對待遊戲排名和本文提出的技術，用遊戲娛樂自己的生活
聲明：本文提出的演算法及開原始程式碼符合MIT開源協定，以商業目的使用該演算法造成的一切後果須由使用者本人承擔
End.
運行人員：中國統計網小編
中國統計網，是國內最早的大資料學習網站
//www.itongji.cn