跳一跳AI(wai gua)的实现原理详细介绍

12月28日，微信发布了V6.6.1新版本，新增了一系列小程序游戏，主推游戏“跳一跳”的每周更新排行榜也激也了一些玩家的刷分热情，现在很多大牛在github上发布了程序代玩的各种语言的实现源代码，那么我们就来讲讲代码的实现原理。

准备

由于是手机游戏，所以依赖于手机的自动化测试框架，例如android的ADB，ios的话可以选择facebook开源的WebDriverAgent(https://github.com/facebook/WebDriverAgent)来模拟对手机的操作（其实就是对屏幕的点击）。

所需环境：（andorid和python为例，比较好找）

android手机，打开 USB 调试功能
Python 3.5+(2.7也可以，没有多大影响)
ADB驱动安装完成并可以正常连接手机
matplot 、opencv、numpy（pip直接安装就好）

原理

1. 通过自动化的测试框架对手机屏幕进行截图并传输到PC。
2. PC端对图片进行处理，处理包括以下几个步骤：a. 寻找棋子坐标点（最低端中心）：这一步很简单，因为棋子的颜色是固定的，直接按照颜色找就可以了b. 寻找下一跳的落地点棋盘位置并计算棋盘中心点位置:这一步就比较麻烦一些，棋盘是在左上和右上随机出现，而且大小，形状也都不一样，这就给识别增加了难度。c.计算棋子与中心点位置距离：只要找到了两个点，做一个减法就可以了d.通过距离计算按压时间：这个是除了寻找落地棋盘以外最复杂的操作了，因为每个手机的屏幕大小不一样，所以对于不同手机像素代表的按压时间也是不一样的。e.按压时间修正：我们的每一跳都不可能跳到最中心的位置，总会有一个误差出现，如果不进行修正，这个误差可能会越来越大，导致后面的跳跃失败，所以在跳跃的每一步后都需要根据落地点与实际的中心点的差值来更新按压时间，这就跟我们在神经网络中计算误差时要达到误差最小化是相似的，这个我们后面再细说。
3. 通过自动化测试框架发送按压操作给手机，按压的时间为2.d步计算结果。
4. 休息1-2秒后继续重复步骤1

关键点代码实现:

导入基本库

import sys
import matplotlib.pylab as plt
import numpy as np

这里其实只需要numpy和matplot就可以了，opencv都没用到

读取截图

#读入文件
i = plt.imread("./1.jpg") 
#这个函数是将图片进行灰度处理，也就是说1-255的数值，越小越暗，
defto_grayscale(im, weights = np.c_[0.2989, 0.5870, 0.1140]):
    im=im[...,:3]
    tile = np.tile(weights, reps=(im.shape[0],im.shape[1],1))
    return np.sum(tile * im, axis=2)
img = to_grayscale(i)
plt.imshow(img)
plt.show()

读入完成图片后先展示下看看灰度处理的结果，然后先进行简单的找棋子的处理，棋子的处理很简单，因为颜色不变，所以在一个区间之内找就可以了，而且不需要使用灰度图，直接用原图，通过像素大小判断就可以了

#找到棋子中心点
a=[]
for h in range(i.shape[0]-1,0,-1):
    for w in range(0,i.shape[1],1):
        if50 <i[h,w,0]<60and50<i[h,w,1]<60and95<i[h,w,2]<105 :
            a.append([h,w])
point=np.mean(a, axis=0).astype(int)
#point为找到的棋子中心点
print(point)

找到棋子中心点后开始处理目标位置中心点，目标位置的中心点分为4步，先找到最上点，也就是Y轴的最大值，然后根据Y轴向下遍历，找到Y轴的最小值，取最大值和最小值的平均值（中心点Y轴坐标）确定X轴的方位，再根据X轴分别像两个方向遍历，找到X轴的最大和最小值，再取平均值（中心点Y轴坐标），在进行组合就为目标的中心点位置了。

max_diff_color=10#灰度后像素颜色差
step=5#像素点数
#找到顶点Y
y_top=0
for h in range(350, img.shape[0], step):
    last_pixel = img[h,0]
    for w in range(1, img.shape[1],step):
        pixel = img[h,w]
        a=abs(pixel-last_pixel)
        last_pixel=pixel
        if a>max_diff_color:
            y_top = [h,w] #多个像素点
            break
    if y_top:
        break
print(y_top)
#找到底端Y
y_btn=0;
last_pixel = img[y_top[0]+10,y_top[1]]
for h in range(y_top[0]+10, img.shape[0], step):
    pixel = img[h,y_top[1]]
    a=abs(pixel-last_pixel)
    last_pixel=pixel
    if a>max_diff_color:
        y_btn = [h,y_top[1]] 
        break;
print(y_btn)
#Y轴平均值，中点
avg_x=[int((y_btn[0]+y_top[0])/2),y_btn[1]]
print (avg_x)
#X轴最小值
x_left=0
last_pixel = img[avg_x[0],y_top[1]-10]
for w in range(avg_x[1],0,-step):
    pixel = img[avg_x[0],w]
    a=abs(pixel-last_pixel)
    last_pixel=pixel
    if a>max_diff_color:
        x_left = [avg_x[0],w] 
        break;
print(x_left)
#X轴最大值
x_right=0
last_pixel = img[avg_x[0],y_top[1]-10]
for w in range(avg_x[1],img.shape[1],step):
    pixel = img[avg_x[0],w]
    a=abs(pixel-last_pixel)
    last_pixel=pixel
    if a>max_diff_color:
        x_right = [avg_x[0],w] 
        break;
print(x_right)
#最后组合成中心点
mid=[avg_x[0],int((x_right[1]+x_left[1])/2)]
print(mid)

这里mid就是我们要的目标的中心点位置，下面我们查看下

img[mid[0]-10:mid[0]+10,mid[1]-10:mid[1]+10]=1
img[point[0]-10:point[0]+10,point[1]-10:point[1]+10]=300
plt.imshow(img,cmap='Greys')
plt.show()

然后就是计算距离，这里我们用欧式距离，numpy一句话就搞定了

dist=np.linalg.norm(point - mid)

最后一步，计算按压距离

#我们先定义一个系数，可以根据初始情况调整
magicnumber=1.0
press_time = dist* magicnumber
#点击后我们还要根据落地点和上一步计算出来的中心点的差值来更新magicnumber
lr=0.05# learning rate 每一次的更新值，这个可以根据实际情况调整
#下方
magicnumber=(1+lr)*magicnumber
#上方
magicnumber=(1-lr)*magicnumber

模拟点击

import os
cmd = 'adb shell input swipe {x1} {y1} {x2} {y2} {duration}'.format(
        x1=300,
        y1=300,
        x2=300,
        y2=300,
        duration=press_time
    )
os.system(cmd)

关于参数的自动更新说明

上面也说到了，这个magicnumber系数是需要根据前一跳结果和计算出来的中心点的差值对比来动态的改变。最简单的解释也是我们人的操作就是：上一次跳过了，下次相同距离的话就要按的时间短一些，反之就要多按一会。
而这个差值其实就是我们在机器学习中的loss function，（其实cost function也可以，因为一个是loss function是针对单个样本的，cost function是针对整体样本的，其实就是loss function的平均），而lr其实我们可以理解为就是使用随机梯度下降优化时的学习率，也很简单就是为了使差值最小。而magicnumber其实就是我们所需要训练的权重模型，例如在神经网络中我们经常用到的初始化 np.random.randn。

一点废话

大概完成了这个简单项目的技术要点，其实这里面一点人工智能的方法也没用到，用的最多的就是numpy对于数组或者叫矩阵的处理，如果说非要往AI上靠的话那就只能说这个项目用了一些强化学习思路吧。
如果再深入一些可以改进的地方有以下几个方面：

1，程序完全自动学习，这里的几个参数完全可以做成初始化后，通过AI自动完成，前几次肯定AI不会有太多的分数，但是后面肯定会越来越好，参考Flap Bird，已经给出了很好的答案。

2，关于learning rate，将每一跳的计算中心点与实际落点相减求导来优化权重：cost function = 计算中心点-实际落点，并且对这个值进行求导，来优化我们的权重值，我们的cost function是一条直线所以肯定是收敛的。

3，加入CV模块，通过卷积进行物体的识别，能够直接自动识别出棋子和目标，这样训练后就不需要人工再来进行标注了。如果做得再细化一下可以做到 井盖，留声机，便利店，魔方等加分的元素都进行判断，但是这样需要更多的训练样本，当然，这些训练样本可以在实际使用的时候收集，但是这就是一个很大的工程了。

成果展示

图中目标显示的白点为程序计算的目标中心点，棋子下方的黑点为计算出的棋子中心位置。

这张图可以看出由于原图中标记有中心点，所以计算出现偏差，使得计算点偏上，说明程序还有优化空间，但是经过测试，并不影响运行。

最后

这里是我收集的各个语言版本的源代码地址，有兴趣的下来看吧：

https://github.com/wangshub/wechat_jump_game 星最多，android ios都支持，ios要安装wda，已测试可用，其他python也很多

https://github.com/faceair/youjumpijump go的

https://github.com/metowolf/JumpJumpHelper 没错，php是最好的语言

https://github.com/wotermelon/toJump nodejs，js的也很多，不一一写了

https://github.com/fourbrother/WXJumpGameUtils 这个是JAVA的

https://github.com/iOSDevLog/JumpJump Kotlin，就当java看吧

https://github.com/Nihiue/JumpHelper c#的来了

https://github.com/experdot/AutoJump.NET VB.net的也来了

其他的还有很多，排名不分先后

人家写的都挺好的直接拿来用就好了，如果有需要我这篇文章代码的代码 请直接留言，我这里只有ipynb，最为研究存档使用，最后如果这篇文章对你有帮助，请转发。