热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

AI玩微信跳一跳的正确姿势:跳一跳AutoJump算法详解

最近,微信小游戏跳一跳可以说是火遍了全国,从小孩子到大孩子仿佛每一个人都在刷跳一跳,作为无(zhi)所

最近,微信小游戏跳一跳可以说是火遍了全国,从小孩子到大孩子仿佛每一个人都在刷跳一跳,作为无(zhi)所(hui)不(ban)能(zhuan)的 AI 程序员,我们在想,能不能用人工智能(AI)和计算机视觉(CV)的方法来玩一玩这个游戏?


于是,我们开发了微信跳一跳 Auto-Jump 算法,重新定义了玩跳一跳的正确姿势,我们的算法不仅远远超越了人类的水平,在速度和准确度上也远远超越了目前已知的所有算法,可以说是跳一跳界的 state-of-the-art,下面我们详细介绍我们的算法。


算法的第一步是获取手机屏幕的截图并可以控制手机的触控操作,我们的 github 仓库里详细介绍了针对 Android 和 IOS 手机的配置方法。


Github 地址:

https://github.com/Prinsphield/Wechat_AutoJump


你只需要按照将手机连接电脑,按照教程执行就可以完成配置。在获取到屏幕截图之后,就是个简单的视觉问题。我们需要找的就是小人的位置和下一次需要跳的台面的中心。


如图所示,绿色的点代表小人当前的位置,红点代表目标位置。




多尺度搜索 Multiscale Search


这个问题可以有非常多的方法去解,为了糙快猛地刷上榜,我一开始用的方式是多尺度搜索。我随便找了一张图,把小人抠出来,就像下面这样。




另外,我注意到小人在屏幕的不同位置,大小略有不同,所以我设计了多尺度的搜索,用不同大小的进行匹配,最后选取置信度(confidence score)最高的。


多尺度搜索的代码长这样:




我们来试一试,效果还不错,应该说是又快又好,我所有的实验中找小人从来没有失误。


不过这里的位置框的底部中心并不是小人的位置,真实的位置是在那之上一些。




同理,目标台面也可以用这种办法搜索,但是我们需要收集一些不同的台面,有圆形的,方形的,便利店,井盖,棱柱等等。由于数量一多,加上多尺度的原因,速度上会慢下来。


这时候,我们就需要想办法加速了。首先可以注意到目标位置始终在小人的位置的上面,所以可以操作的一点就是在找到小人位置之后把小人位置以下的部分都舍弃掉,这样可以减少搜索空间。


但是这还是不够,我们需要进一步去挖掘游戏里的故事。小人和目标台面基本上是关于屏幕中心对称的位置的。这提供了一个非常好的思路去缩小搜索空间。


假设屏幕分辨率是(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 开源协议,以商业目的使用该算法造成的一切后果须由使用者本人承担。


原文链接:https://zhuanlan.zhihu.com/p/32636329




推荐阅读
  • 在机器学习领域,深入探讨了概率论与数理统计的基础知识,特别是这些理论在数据挖掘中的应用。文章重点分析了偏差(Bias)与方差(Variance)之间的平衡问题,强调了方差反映了不同训练模型之间的差异,例如在K折交叉验证中,不同模型之间的性能差异显著。此外,还讨论了如何通过优化模型选择和参数调整来有效控制这一平衡,以提高模型的泛化能力。 ... [详细]
  • EST:西湖大学鞠峰组污水厂病原菌与土著反硝化细菌是多重抗生素耐药基因的活跃表达者...
    点击蓝字关注我们编译:祝新宇校稿:鞠峰、袁凌论文ID原名:PathogenicandIndigenousDenitrifyingBacte ... [详细]
  • 近期,微信公众平台上的HTML5游戏引起了广泛讨论,预示着HTML5游戏将迎来新的发展机遇。磊友科技的赵霏,作为一名HTML5技术的倡导者,分享了他在微信平台上开发HTML5游戏的经验和见解。 ... [详细]
  • javax.mail.search.BodyTerm.matchPart()方法的使用及代码示例 ... [详细]
  • 本文回顾了作者初次接触Unicode编码时的经历,并详细探讨了ASCII、ANSI、GB2312、UNICODE以及UTF-8和UTF-16编码的区别和应用场景。通过实例分析,帮助读者更好地理解和使用这些编码。 ... [详细]
  • 在多线程并发环境中,普通变量的操作往往是线程不安全的。本文通过一个简单的例子,展示了如何使用 AtomicInteger 类及其核心的 CAS 无锁算法来保证线程安全。 ... [详细]
  • 本文对比了杜甫《喜晴》的两种英文翻译版本:a. Pleased with Sunny Weather 和 b. Rejoicing in Clearing Weather。a 版由 alexcwlin 翻译并经 Adam Lam 编辑,b 版则由哈佛大学的宇文所安教授 (Prof. Stephen Owen) 翻译。 ... [详细]
  • Python 3 Scrapy 框架执行流程详解
    本文详细介绍了如何在 Python 3 环境下安装和使用 Scrapy 框架,包括常用命令和执行流程。Scrapy 是一个强大的 Web 抓取框架,适用于数据挖掘、监控和自动化测试等多种场景。 ... [详细]
  • 在软件开发过程中,经常需要将多个项目或模块进行集成和调试,尤其是当项目依赖于第三方开源库(如Cordova、CocoaPods)时。本文介绍了如何在Xcode中高效地进行多项目联合调试,分享了一些实用的技巧和最佳实践,帮助开发者解决常见的调试难题,提高开发效率。 ... [详细]
  • 深入解析国内AEB应用:摄像头和毫米波雷达融合技术的现状与前景
    本文作者程建伟,武汉极目智能技术有限公司CEO,入选武汉市“光谷3551人才计划”。文章详细探讨了国内自动紧急制动(AEB)系统中摄像头与毫米波雷达融合技术的现状及未来前景。通过分析当前技术的应用情况、存在的挑战以及潜在的解决方案,作者指出,随着传感器技术的不断进步和算法优化,AEB系统的性能将大幅提升,为交通安全带来显著改善。 ... [详细]
  • 在《数字图像处理及应用(MATLAB)第4章》中,详细探讨了“逢七必过”游戏规则的实现方法,并结合数字图像处理技术进行了深入分析。本章通过丰富的实例和代码示例,展示了如何利用MATLAB实现这一游戏规则,并介绍了数字图像处理的基本原理和技术应用。内容涵盖了图像增强、滤波、边缘检测等多个方面,为读者提供了全面的技术支持和实践指导。 ... [详细]
  • 二分查找算法详解与应用分析:本文深入探讨了二分查找算法的实现细节及其在实际问题中的应用。通过定义 `binary_search` 函数,详细介绍了算法的逻辑流程,包括初始化上下界、循环条件以及中间值的计算方法。此外,还讨论了该算法的时间复杂度和空间复杂度,并提供了多个应用场景示例,帮助读者更好地理解和掌握这一高效查找技术。 ... [详细]
  • 提升视觉效果:Unity3D中的HDR与Bloom技术(高动态范围成像与光线散射)
    提升视觉效果:Unity3D中的HDR与Bloom技术(高动态范围成像与光线散射) ... [详细]
  • Hadoop平台警告解决:无法加载本机Hadoop库的全面应对方案
    本文探讨了在Hadoop平台上遇到“无法加载本机Hadoop库”警告的多种解决方案。首先,通过修改日志配置文件来忽略该警告,这一方法被证明是有效的。其次,尝试指定本地库的路径,但未能解决问题。接着,尝试不使用Hadoop本地库,同样没有效果。然后,通过替换现有的Hadoop本地库,成功解决了问题。最后,根据Hadoop的源代码自行编译本地库,也达到了预期的效果。以上方法适用于macOS系统。 ... [详细]
  • 独家解析:深度学习泛化理论的破解之道与应用前景
    本文深入探讨了深度学习泛化理论的关键问题,通过分析现有研究和实践经验,揭示了泛化性能背后的核心机制。文章详细解析了泛化能力的影响因素,并提出了改进模型泛化性能的有效策略。此外,还展望了这些理论在实际应用中的广阔前景,为未来的研究和开发提供了宝贵的参考。 ... [详细]
author-avatar
张三三
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有