自微信小程序出現(xiàn)游戲“跳一跳”后，眾多微信用戶紛紛和排行榜較上了勁，頗有一些不到***不罷休的架勢(shì)。

而在離游戲“跳一跳”***上線過(guò)去了一個(gè)多月后，眾多大神也開始顯現(xiàn)。分?jǐn)?shù)上千已不是難事。

“微信之父”張小龍也在 2018 微信公開課 PRO 上透露了自己玩微信小游戲“跳一跳”的分?jǐn)?shù)，表示自己***分達(dá)到 6000+，他還稱自己玩“跳一跳”時(shí)并不會(huì)緊張和心跳加快，而是覺(jué)得很平靜，享受這個(gè)過(guò)程。

作為無(wú)（zhi）所（hui）不（ban）能（zhuan）的 AI 程序員，我們?cè)谙?，能不能用人工智能（AI）和計(jì)算機(jī)視覺(jué)（CV）的方法來(lái)玩一玩這個(gè)游戲？

于是，我們開發(fā)了微信跳一跳 Auto-Jump 算法，重新定義了玩跳一跳的正確姿勢(shì)。

我們的算法不僅遠(yuǎn)遠(yuǎn)超越了人類的水平，在速度和準(zhǔn)確度上也遠(yuǎn)遠(yuǎn)超越了目前已知的所有算法，可以說(shuō)是跳一跳界的 state-of-the-art，下面我們?cè)敿?xì)介紹我們的算法。

算法的***步是獲取手機(jī)屏幕的截圖并可以控制手機(jī)的觸控操作，我們的 Github 倉(cāng)庫(kù)里詳細(xì)介紹了針對(duì) Android 和 iOS 手機(jī)的配置方法。

Github 地址：https://github.com/Prinsphield/Wechat_AutoJump

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

如圖所示，綠色的點(diǎn)代表小人當(dāng)前的位置，紅點(diǎn)代表目標(biāo)位置。

多尺度搜索（Multiscale Search）

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

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

多尺度搜索的代碼長(zhǎng)這樣：

def multi_scale_search(pivot, screen, range=0.3, num=10): 
    H, W = screen.shape[:2] 
    h, w = pivot.shape[:2] 
 
    found = None 
    for scale in np.linspace(1-range, 1+range, num)[::-1]: 
        resized = cv2.resize(screen, (int(W * scale), int(H * scale))) 
        r = W / float(resized.shape[1]) 
        if resized.shape[0] < h or resized.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] 
 
        if found is None or res.max() > found[-1]: 
            found = (pos_h, pos_w, r, res.max()) 
 
    if found is None: 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] 

我們來(lái)試一試，效果還不錯(cuò)，應(yīng)該說(shuō)是又快又好，我所有的實(shí)驗(yàn)中找小人從來(lái)沒(méi)有失誤。

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

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

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

但是這還是不夠，我們需要進(jìn)一步去挖掘游戲里的故事。小人和目標(biāo)臺(tái)面基本上是關(guān)于屏幕中心對(duì)稱的位置的。這提供了一個(gè)非常好的思路去縮小搜索空間。

假設(shè)屏幕分辨率是（1280，720）的，小人底部的位置是（h1, w1)，那么關(guān)于中心對(duì)稱點(diǎn)的位置就是（1280 - h1， 720 - w1），以這個(gè)點(diǎn)為中心的一個(gè)邊長(zhǎng) 300 的正方形內(nèi)，我們?cè)偃ザ喑叨人阉髂繕?biāo)位置，就會(huì)又快又準(zhǔn)了。

效果見下圖，藍(lán)色框是（300，300）的搜索區(qū)域，紅色框是搜到的臺(tái)面，矩形中心就是目標(biāo)點(diǎn)的坐標(biāo)了。

加速的奇技淫巧（Fast-Search）

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

更加細(xì)心的人會(huì)發(fā)現(xiàn)，白點(diǎn)的 RGB 值是（245，245，245），這就讓我找到了一個(gè)非常簡(jiǎn)單并且高效的方式，就是直接去搜索這個(gè)白點(diǎn)。

注意到白點(diǎn)是一個(gè)連通區(qū)域，像素值為（245，245，245）的像素個(gè)數(shù)穩(wěn)定在 280-310 之間，所以我們可以利用這個(gè)去直接找到目標(biāo)的位置。

這種方式只在前一次跳到中心的時(shí)候可以用，不過(guò)沒(méi)有關(guān)系，我們每次都可以試一試這個(gè)不花時(shí)間的方法，不行再考慮多尺度搜索。

講到這里，我們的方法已經(jīng)可以運(yùn)行的非常出色了，基本上是一個(gè)永動(dòng)機(jī)。下面是用我的手機(jī)玩了一個(gè)半小時(shí)左右，跳了 859 次的狀態(tài)。

我們的方法正確的計(jì)算出來(lái)了小人的位置和目標(biāo)位置，不過(guò)我選擇狗帶了，因?yàn)槭謾C(jī)卡的已經(jīng)不行了。

以下是效果演示：

視頻鏈接：https://v.vzuu.com/video/932359600779309056

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

CNN Coarse-to-Fine 模型

考慮到 iOS 設(shè)備由于屏幕抓取方案的限制（WebDriverAgent 獲得的截圖經(jīng)過(guò)了壓縮，圖像像素受損，不再是原來(lái)的像素值，原因不詳，歡迎了解詳情的小伙伴提出改進(jìn)意見）無(wú)法使用 fast-search。

同時(shí)為了兼容多分辨率設(shè)備，我們使用卷積神經(jīng)網(wǎng)絡(luò)構(gòu)建了一個(gè)更快更魯棒的目標(biāo)檢測(cè)模型。

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

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

基于我們非常準(zhǔn)確的 multiscale-search 和 fast-search 模型，我們采集了 7 次實(shí)驗(yàn)數(shù)據(jù)，共計(jì)大約 3000 張屏幕截圖，每一張截圖均帶有目標(biāo)位置標(biāo)注。

對(duì)于每一張圖，我們進(jìn)行了兩種不同的預(yù)處理方式，并分別用于訓(xùn)練 Coarse 模型和 Fine 模型，下面分別介紹兩種不同的預(yù)處理方式。

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

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

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

我們觀察到，游戲中，每一次當(dāng)小人落在目標(biāo)物中心位置時(shí)，下一個(gè)目標(biāo)物的中心會(huì)出現(xiàn)一個(gè)白色的圓點(diǎn)。

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

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

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

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

Coarse 模型

我們把這一問(wèn)題看成了回歸問(wèn)題，Coarse 模型使用一個(gè)卷積神經(jīng)網(wǎng)絡(luò)回歸目標(biāo)的位置。

def forward(self, img, is_training, keep_prob, name='coarse'): 
    with tf.name_scope(name): 
        with tf.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) 
 
    return out 

經(jīng)過(guò) 10 個(gè)小時(shí)的訓(xùn)練，Coarse 模型在測(cè)試集上達(dá)到了 6 像素的精度，實(shí)際測(cè)試精度大約為 10 像素，在測(cè)試機(jī)器（MacBook Pro Retina, 15-inch, Mid 2015, 2.2 GHz Intel Core i7）上 inference 時(shí)間 0.4 秒。

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

Fine 模型

Fine 模型結(jié)構(gòu)與 Coarse 模型類似，參數(shù)量稍大，F(xiàn)ine 模型作為對(duì) Coarse 模型的 refine 操作。

def forward(self, img, is_training, keep_prob, name='fine'): 
    with tf.name_scope(name): 
        with tf.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) 
 
    return out 

經(jīng)過(guò) 10 個(gè)小時(shí)訓(xùn)練，F(xiàn)ine 模型測(cè)試集精度達(dá)到了 0.5 像素，實(shí)際測(cè)試精度大約為 1 像素，在測(cè)試機(jī)器上的 inference 時(shí)間 0.2 秒。

Cascade

總體精度 1 像素左右，時(shí)間 0.6 秒。

總結(jié)

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

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

講到這里，似乎可以宣布，我們的工作 terminate 了這個(gè)問(wèn)題，微信小游戲跳一跳 Game Over！ 

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

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

Git 倉(cāng)庫(kù)地址：

• https://github.com/Prinsphield/Wechat_AutoJump
• https://github.com/Richard-An/Wechat_AutoJump