最近，微信小游戲跳一跳可以說是火遍了全國，從小孩子到大孩子仿佛每一個人都在刷跳一跳，作為無(zhi)所(hui)不(ban)能(zhuan)的 AI 程序員，我們在想，能不能用人工智能(AI)和計算機視覺(CV)的方法來玩一玩這個游戲?

于是，我們開發(fā)了微信跳一跳 Auto-Jump 算法，重新定義了玩跳一跳的正確姿勢，我們的算法不僅遠遠超越了人類的水平，在速度和準確度上也遠遠超越了目前已知的所有算法，可以說是跳一跳界的 state-of-the-art，下面我們詳細介紹我們的算法。

算法的***步是獲取手機屏幕的截圖并可以控制手機的觸控操作，我們的 github 倉庫里詳細介紹了針對 Android 和 IOS 手機的配置方法。

Github 地址：

https://github.com/Prinsphield/Wechat_AutoJump

你只需要按照將手機連接電腦，按照教程執(zhí)行就可以完成配置。在獲取到屏幕截圖之后，就是個簡單的視覺問題。我們需要找的就是小人的位置和下一次需要跳的臺面的中心。

如圖所示，綠色的點代表小人當前的位置，紅點代表目標位置。

多尺度搜索 Multiscale Search

這個問題可以有非常多的方法去解，為了糙快猛地刷上榜，我一開始用的方式是多尺度搜索。我隨便找了一張圖，把小人摳出來，就像下面這樣。

另外，我注意到小人在屏幕的不同位置，大小略有不同，所以我設計了多尺度的搜索，用不同大小的進行匹配，***選取置信度(confidence score)***的。

多尺度搜索的代碼長這樣：

defmulti_scale_search(pivot, screen, range=0.3, num=10):  
H, W = screen.shape[: 2]  
h, w = pivot.shape[: 2]  
found = None  
forscale innp.linspace( 1-range, 1+range, num)[:: -1]:  
resized = cv2.resize(screen, (int(W * scale), int(H * scale)))  
r = W / float(resized.shape[ 1])  
ifresized.shape[ 0] < h orresized.shape[ 1] < w:  
break  
res = cv2.matchTemplate(resized, pivot, cv2.TM_CCOEFF_NORMED)  
loc = np.where(res >= res.max())  
pos_h, pos_w = list(zip(*loc))[ 0]  
iffound isNoneorres.max() > found[ -1]:  
found = (pos_h, pos_w, r, res.max())  
iffound isNone: return( 0, 0, 0, 0, 0)  
pos_h, pos_w, r, score = found  
start_h, start_w = int(pos_h * r), int(pos_w * r)  
end_h, end_w = int((pos_h + h) * r), int((pos_w + w) * r)  
return[start_h, start_w, end_h, end_w, score] 

我們來試一試，效果還不錯，應該說是又快又好，我所有的實驗中找小人從來沒有失誤。

不過這里的位置框的底部中心并不是小人的位置，真實的位置是在那之上一些。

同理，目標臺面也可以用這種辦法搜索，但是我們需要收集一些不同的臺面，有圓形的，方形的，便利店，井蓋，棱柱等等。由于數(shù)量一多，加上多尺度的原因，速度上會慢下來。

這時候，我們就需要想辦法加速了。首先可以注意到目標位置始終在小人的位置的上面，所以可以操作的一點就是在找到小人位置之后把小人位置以下的部分都舍棄掉，這樣可以減少搜索空間。

但是這還是不夠，我們需要進一步去挖掘游戲里的故事。小人和目標臺面基本上是關于屏幕中心對稱的位置的。這提供了一個非常好的思路去縮小搜索空間。

假設屏幕分辨率是(1280，720)的，小人底部的位置是(h1, w1)，那么關于中心對稱點的位置就是(1280 - h1， 720 - w1)，以這個點為中心的一個邊長 300 的正方形內(nèi)，我們再去多尺度搜索目標位置，就會又快有準了。

效果見下圖，藍色框是(300，300)的搜索區(qū)域，紅色框是搜到的臺面，矩形中心就是目標點的坐標了。

加速的奇技淫巧(Fast-Search)

玩游戲需要細心觀察。我們可以發(fā)現(xiàn)，小人上一次如果跳到臺面中心，那么下一次目標臺面的中心會有一個白點，就像剛才所展示的圖里的。

更加細心的人會發(fā)現(xiàn)，白點的 RGB 值是(245，245，245)，這就讓我找到了一個非常簡單并且高效的方式，就是直接去搜索這個白點，注意到白點是一個連通區(qū)域，像素值為(245，245，245)的像素個數(shù)穩(wěn)定在 280-310 之間，所以我們可以利用這個去直接找到目標的位置。

這種方式只在前一次跳到中心的時候可以用，不過沒有關系，我們每次都可以試一試這個不花時間的方法，不行再考慮多尺度搜索。

講到這里，我們的方法已經(jīng)可以運行的非常出色了，基本上是一個永動機。下面是用我的手機玩了一個半小時左右，跳了 859 次的狀態(tài)，我們的方法正確的計算出來了小人的位置和目標位置，不過我選擇狗帶了，因為手機卡的已經(jīng)不行了。

以下是效果演示：

到這里就結束了嗎?那我們和業(yè)余玩家有什么區(qū)別?下面進入正經(jīng)的學術時間，非戰(zhàn)斗人員請迅速撤離。

CNN Coarse-to-Fine 模型

考慮到 iOS 設備由于屏幕抓取方案的限制(WebDriverAgent 獲得的截圖經(jīng)過了壓縮，圖像像素受損，不再是原來的像素值，原因不詳，歡迎了解詳情的小伙伴提出改進意見)無法使用 fast-search，同時為了兼容多分辨率設備，我們使用卷積神經(jīng)網(wǎng)絡構建了一個更快更魯棒的目標檢測模型。

下面分數(shù)據(jù)采集與預處理，coarse 模型，fine 模型，cascade 四部分介紹我們的算法。

數(shù)據(jù)采集與預處理

基于我們非常準確的 multiscale-search 和 fast-search 模型，我們采集了 7 次實驗數(shù)據(jù)，共計大約 3000 張屏幕截圖，每一張截圖均帶有目標位置標注，對于每一張圖，我們進行了兩種不同的預處理方式，并分別用于訓練 coarse 模型和 fine 模型，下面分別介紹兩種不同的預處理方式。

Coarse 模型數(shù)據(jù)預處理

由于每一張圖像中真正對于當前判斷有意義的區(qū)域只在屏幕中央位置，即人和目標物體所在的位置，因此，每一張截圖的上下兩部分都是沒有意義的。

于是，我們將采集到的大小為 1280*720 的圖像沿 x 方向上下各截去 320*720 大小，只保留中心 640*720 的圖像作為訓練數(shù)據(jù)。

我們觀察到，游戲中，每一次當小人落在目標物中心位置時，下一個目標物的中心會出現(xiàn)一個白色的圓點。

考慮到訓練數(shù)據(jù)中 fast-search 會產(chǎn)生大量有白點的數(shù)據(jù)，為了杜絕白色圓點對網(wǎng)絡訓練的干擾，我們對每一張圖進行了去白點操作，具體做法是，用白點周圍的純色像素填充白點區(qū)域。

Fine 模型數(shù)據(jù)預處理

為了進一步提升模型的精度，我們?yōu)?fine 模型建立了數(shù)據(jù)集，對訓練集中的每一張圖，在目標點附近截取 320*320 大小的一塊作為訓練數(shù)據(jù)。

為了防止網(wǎng)絡學到 trivial 的結果，我們對每一張圖增加了 50 像素的隨機偏移。fine 模型數(shù)據(jù)同樣進行了去白點操作。

Coarse 模型

我們把這一問題看成了回歸問題，coarse 模型使用一個卷積神經(jīng)網(wǎng)絡回歸目標的位置。

defforward(self, img, is_training, keep_prob, name='coarse'):  
withtf.name_scope(name):  
withtf.variable_scope(name):  
out = self.conv2d( 'conv1', img, [ 3, 3, self.input_channle, 16], 2)  
# out = tf.layers.batch_normalization(out, name='bn1', training=is_training)  
out = tf.nn.relu(out, name= 'relu1')  
out = self.make_conv_bn_relu( 'conv2', out, [ 3, 3, 16, 32], 1, is_training)  
out = tf.nn.max_pool(out, [ 1, 2, 2, 1], [ 1, 2, 2, 1], padding= 'SAME')  
out = self.make_conv_bn_relu( 'conv3', out, [ 5, 5, 32, 64], 1, is_training)  
out = tf.nn.max_pool(out, [ 1, 2, 2, 1], [ 1, 2, 2, 1], padding= 'SAME')  
out = self.make_conv_bn_relu( 'conv4', out, [ 7, 7, 64, 128], 1, is_training)  
out = tf.nn.max_pool(out, [ 1, 2, 2, 1], [ 1, 2, 2, 1], padding= 'SAME')  
out = self.make_conv_bn_relu( 'conv5', out, [ 9, 9, 128, 256], 1, is_training)  
out = tf.nn.max_pool(out, [ 1, 2, 2, 1], [ 1, 2, 2, 1], padding= 'SAME')  
out = tf.reshape(out, [ -1, 256* 20* 23])  
out = self.make_fc( 'fc1', out, [ 256* 20* 23, 256], keep_prob)  
out = self.make_fc( 'fc2', out, [ 256, 2], keep_prob)  
returnout 

經(jīng)過十小時的訓練，coarse 模型在測試集上達到了 6 像素的精度，實際測試精度大約為 10 像素，在測試機器(MacBook Pro Retina, 15-inch, Mid 2015, 2.2 GHz Intel Core i7)上 inference 時間 0.4 秒。

這一模型可以很輕松的拿到超過 1k 的分數(shù)，這已經(jīng)遠遠超過了人類水平和絕大多數(shù)自動算法的水平，日常娛樂完全夠用，不過，你認為我們就此為止那就大錯特錯了。

Fine 模型

Fine 模型結構與 coarse 模型類似，參數(shù)量稍大，fine 模型作為對 coarse 模型的 refine 操作。

defforward(self, img, is_training, keep_prob, name='fine'):  
withtf.name_scope(name):  
withtf.variable_scope(name):  
out = self.conv2d( 'conv1', img, [ 3, 3, self.input_channle, 16], 2)  
# out = tf.layers.batch_normalization(out, name='bn1', training=is_training)  
out = tf.nn.relu(out, name= 'relu1')  
out = self.make_conv_bn_relu( 'conv2', out, [ 3, 3, 16, 64], 1, is_training) 
out = tf.nn.max_pool(out, [ 1, 2, 2, 1], [ 1, 2, 2, 1], padding= 'SAME')  
out = self.make_conv_bn_relu( 'conv3', out, [ 5, 5, 64, 128], 1, is_training)  
out = tf.nn.max_pool(out, [ 1, 2, 2, 1], [ 1, 2, 2, 1], padding= 'SAME')  
out = self.make_conv_bn_relu( 'conv4', out, [ 7, 7, 128, 256], 1, is_training)  
out = tf.nn.max_pool(out, [ 1, 2, 2, 1], [ 1, 2, 2, 1], padding= 'SAME')  
out = self.make_conv_bn_relu( 'conv5', out, [ 9, 9, 256, 512], 1, is_training)  
out = tf.nn.max_pool(out, [ 1, 2, 2, 1], [ 1, 2, 2, 1], padding= 'SAME')  
out = tf.reshape(out, [ -1, 512* 10* 10])  
out = self.make_fc( 'fc1', out, [ 512* 10* 10, 512], keep_prob)  
out = self.make_fc( 'fc2', out, [ 512, 2], keep_prob)  
returnout 

經(jīng)過十小時訓練，fine 模型測試集精度達到了 0.5 像素，實際測試精度大約為 1 像素，在測試機器上的 inference 時間 0.2 秒。

Cascade

總體精度 1 像素左右，時間 0.6 秒。

總結

針對這一問題，我們利用 AI 和 CV 技術，提出了合適適用于 iOS 和 Android 設備的完整解決方案，稍有技術背景的用戶都可以實現(xiàn)成功配置、運行。

我們提出了 Multiscale-Search，F(xiàn)ast-Search 和 CNN Coarse-to-Fine 三種解決這一問題的算法，三種算法相互配合，可以實現(xiàn)快速準確的搜索、跳躍，用戶針對自己的設備稍加調(diào)整跳躍參數(shù)即可接近實現(xiàn)“永動機”。

講到這里，似乎可以宣布，我們的工作 terminate 了這個問題，微信小游戲跳一跳 Game Over!

友情提示：適度游戲益腦，沉迷游戲傷身，技術手段的樂趣在于技術本身而不在游戲排名，希望大家理性對待游戲排名和本文提出的技術，用游戲娛樂自己的生活。

聲明：本文提出的算法及開源代碼符合 MIT 開源協(xié)議，以商業(yè)目的使用該算法造成的一切后果須由使用者本人承擔。