【最强大脑】全球脑王的极客挑战赛之路:1413876分夺冠如何炼成?

来源:QQ快报
责任编辑:李志喜
字体:

导语 | 在腾讯云+社区联合腾讯码客、腾讯安全平台部全新打造的创新赛事【腾讯极客挑战赛 | 鹅罗斯方块】中,4570名参赛者为我们带来前所未有、异彩纷呈的作品。一场技术竞技,把一群志同道合的开发者聚集在一起,激发好奇心和极客精神,这是云+社区举办赛事的初衷。最终来自清华大学计算机科学与技术系的郑林楷在激烈的竞争中脱颖而出,斩获冠军!此次我们特地邀请郑林楷执笔撰稿,聊聊他以1413876超高分夺冠的那些事!

选手介绍

郑林楷,目前就读于清华大学计算机科学与技术系,主攻Web安全领域。第6季《最强大脑之燃烧吧大脑》“脑王”,有丰富的CTF赛事经验。

大佬这样说

七月末的时候看到了腾讯极客挑战赛第四期,发现这不是俄罗斯方块嘛,是之前Botzone玩过的AI游戏,于是决定来玩玩。没想到一玩玩了好几天,最后的程序也和之前在Botzone写的AI完全不一样了,最后以1413876的分数拿到了外网赛道的第一,同时该分数也是内外网赛道的最高分。

一个次高的成绩:1413770

一、分析游戏代码和规则

这次的赛题叫做「鹅罗斯方块」,名字很有鹅厂风格。其实就是在一个Web版俄罗斯方块游戏中尽可能取得最高分。贴心的鹅厂还准备了正常缩进的源代码,查看源代码可以知道方块总数共10000个,落完则游戏结束。方块的下落序列则是由一个伪随机数生成器生成的,生成器的种子也是固定的,这意味着方块的下落顺序是固定的。

这次赛题与普通俄罗斯方块不同的还有不同种类方块的生成概率,长条的出现概率被人为调低到2/29,而最难处理的S型和Z型出现概率则各被上调到6/29。赛题在计分规则上相比普通游戏也有所变化,消除时场地格子越多,一次性消除的行数越多,得到的分数越多。

计分规则

二、设计估价函数

首先从下落方块数量恒定这点来看,我们要追求的反而不是「不死」了,而是在游戏能够继续的基础上尽可能拿到高分,而绝大多数Tetris AI算法都只追求「不死」,所以套用Tetris AI算法得到的分数一般都不高。我把我在Botzone上天梯第二的程序稍微改了改跑了跑,得到的分数也只有10w不到(因为写得太优秀了全程方块高度就没超过4……)那么我第一个想法就是修改估价函数了。

原本在Botzone上的AI算法是MCTS蒙特卡洛搜索外加估价函数。在魔改了估价函数之后,分数从10w到60w再到107w,但距离当时排行榜的第一名137w还有点距离。不愿意在调参上浪费太多的我只好决定换个思路。

(一)「阶段」搜索

首先为了追求理论最高分,我不能再用MCTS了,如果用MCTS找理论最高分的操作我觉得到比赛结束都找不出。所以要搜索,要在包含10000×2200种状态的游戏中搜索出最优解。

「开玩笑呢,这么多状态数怎么搜?」「剪枝啊!」

然后我觉得也许可以用分阶段广搜。简单来说,对于初始局面,我们先搜索出3~4步后的局面有哪些,然后使用估价函数对局面做一个删减,丢掉不好的局面,只留下分数高且估价高的局面用于后续的拓展。这其实相当于每搜几步就用估价函数+贪心做一次剪枝,整体状态数也可以保持在一个合理的范围内。

然后就遇到了一个问题:估价函数势必要包含「分数」和「格子数」,这两个因素越高越好,但消行带来的影响却是矛盾的,格子数减少了但是分数增加了,这就需要写一个很好的估价函数才能让搜索搜到那个最优解。

「但估价函数很难写啊,还要各种脑洞各种比对测试……」

所以我对算法本体开刀了。实际上,上面提到的分阶段广搜中初步搜索的深度是可以随意调整的,调得越深(例如先搜索10步后的局面有哪些)状态数越多,但越能避免最优解在中途因为局面不够优秀而被丢弃。而且,这个搜索深度其实也是可以不固定的。为了解决消行带来的估价问题,我把操作序列中两次消行之间的操作定义为「阶段」,而初步搜索就是负责处理单个「阶段」的搜索。

具体来说,这次的算法分为两层。第一层的搜索树上,游戏局面每一阶段拓展一次;第二层的搜索树上,游戏局面每一轮拓展一次。第一层搜索其实有点像动态规划,我新建了10000×200个桶用来放置游戏局面,定义状态bucket[x][y],其中x是游戏轮数,y是场地格子数。每个桶实际上是一个优先队列,只保留前10优的游戏局面。第一层搜索每次从桶里拿出一个游戏局面进行第二层搜索,再将搜索结果放回对应的桶内。第二层搜索则是一个简单的广搜,用来搜索可能的「阶段」。第二层搜索对游戏局面进行广度优先搜索,直到出现消行操作才停止拓展,也就是说这棵搜索树的叶子都是经过某次消行操作后的游戏局面。第二层搜索结束后会把搜索树叶子上的游戏局面返回给第一层搜索进行更新。

(二)算法框架

如何判断游戏局面的优劣呢?对于在同一轮且格子数相等的游戏局面,我通过判断分数和行列变化次数来给各个局面排序,分数高的优先,分数一样的行列变化次数少的优先。主要是,算法框架已经够好了,估价函数反而设计得简单点好。

boardRowTransitions是指对于每一行小方格,从左往右看,从无小方格到有小方格是一种「变换」,从有小方格到无小方格也是一种「变换」,这个属性则是各行中「变换」之和。同理boardColTransitions是每一列的变换次数之和,boardTransitions是行列的变换次数总和。

boardTransitions

三、总结

具体实现方面,本来想全部代码都整合到C++中的,但因为前期写的各个算法模块的耦合度太高了,自己又不想重写,于是只好将两层搜索分开,Python负责第一层搜索,C++负责第二层搜索。反正代码能用就行了嘛……

代码见GitHub,注释应该都写得很详细了。

(参考网址:https://github.com/Konano/geekTencent-4-Tetris)

以及希望以后比赛也能来多几场直播hhhhh……这次比赛中途有一次直播放了137w成绩的后1000块记录,得到了很大的启发,在此感谢直播团队!没有你们就没有今天这成绩!

作者简介

郑林楷

清华大学计算机科学与技术系,研究领域为Web安全

目前就读于清华大学计算机科学与技术系,研究领域为Web安全。2019年,19岁的郑林楷参加《最强大脑之燃烧吧大脑》,成功捧得“脑王”奖杯。有丰富的CTF参赛经验,2020年WCTF、HITCTF、ByteCTF第一名,2021年*CTF第二名。

您可能还关注以下内容:

江苏卫视《最强大脑》真的假的?

答:曾经一度特别喜欢观看科学竞技真人秀节目,后来因为工作原因搁置了。随着江苏卫视《最强大脑》节目的横空出世,又一次把这个爱好捡拾起来。 虽然作为平凡而普通的我们,除了欣赏并佩服这些选手之外,内心深处是承认这个世界上总有非凡卓越的人才...

2016最强大脑全球脑王是陈智强吗

答:陈智强是南京南航附中的。 本周五晚,《最强大脑》第三季落幕,但当晚的“全球脑王”比赛让中国观众备感惊喜——在一众全球“最强大脑”中,本届“全球脑王”居然最后花落于一个16岁的少年陈智强!另外,南京观众更是觉得与有荣焉,因为他是一个南京人,...

最强大脑第三季全球脑王赛谁赢了

答:陈智强发挥出色,获得脑王称号 《最强大脑》第三季收官赛脑王盛典上,16岁男孩陈智强获封脑王。四位万中选一的选手在决赛中挑战脑力极限,土屋宏明现场创造了7秒47的世界纪录;申一帆挑战“核桃计划”;秘鲁魔方勇士水下盲拧挑战极限。压轴出场的...

最强大脑是什么?

答:陈智强发挥出色,获得脑王称号 《最强大脑》第三季收官赛脑王盛典上,16岁男孩陈智强获封脑王。四位万中选一的选手在决赛中挑战脑力极限,土屋宏明现场创造了7秒47的世界纪录;申一帆挑战“核桃计划”;秘鲁魔方勇士水下盲拧挑战极限。压轴出场的...

最强大脑第三季全球脑王是谁 陈智强获2016全球脑王

答:是的,最强大脑第三季脑王是陈智强 《最强大脑》第三季收官赛脑王盛典上,16岁男孩陈智强获封脑王。四位万中选一的选手在决赛中挑战脑力极限,土屋宏明现场创造了7秒47的世界纪录;申一帆挑战“核桃计划”;秘鲁魔方勇士水下盲拧挑战极限。压轴出...

世界最强大脑是谁

答:只要你真心相信自己,我想,你离世界最强大脑的人也不远。我知道的最强大脑者应该是特斯拉。

最强大脑第五季 最终谁赢

答:最强大脑第五季最终是杨易获得“2018年全球脑王。 从进入团队战开始,连轴作战的杨易可谓全程爆发一路所向披靡,成为了令所有人叹服的“常胜将军”。等到赛程进入国际赛,又以超强实力和稳定发挥成为了中国战队不可替代的“定海神针”。 中日对决为国...

最强大脑世界对决赢过哪场

答:你好,我是记忆协会会员,到过最强大脑现场,很高兴为你解答。 1、《最强大脑》第二季于每周五晚21点10分在江苏卫视准时播出,并率先在优酷土豆全网独播。第二季中节目组花大力气搜寻脑力达人,环节团队全面升级,意欲重振脑力竞技,让拥有最强...

最强大脑2019脑王是谁?

答:最强大脑2019脑王是郑林楷。 19岁的郑林凯曾参加过江苏卫视的最强大脑之燃烧吧大脑,是唯一的参加过三次国际比赛的选手。在100人淘汰赛的第一场比赛中,在“龟骨痕迹”中,他利用自己的超记忆和空间想象找出了8块640块碎片,并将它们组合成方块,...

最强大脑最后全球脑王怎么才这几个人

答:最强大脑第三季的国际赛只有四场,每场选出最难项目的获胜者角逐脑王(中日赛选了陈冉冉和土屋宏明2人),因陈冉冉退出脑王争霸赛,所以参加最后全球脑王争霸赛的只有4个人。

声明:以上内容并不代表本网赞同其观点。如有任何问题,请与不良与违法信息举报中心联系:513175919@qq.com。

www.book1234.com true http://www.book1234.com/q/20210824/20210824A0AH4R00.html report 43349
  • 最强大脑第八季脑王
  • 最强大脑8脑王
  • 最强大脑各赛季脑王
  • 第一季最强大脑脑王
  • 最强大脑所有脑王
  • 最强大脑2018脑王
  • 最强大脑历届脑王名单
  • 最强大脑各界脑王名字
  • 最强大脑第七季脑王
  • 最强大脑第8季脑王
  • 娱乐时尚
  • 江苏卫视《最强大脑》真的假的?
  • 2016最强大脑全球脑王是陈智强吗
  • 最强大脑第三季全球脑王赛谁赢了
  • 最强大脑是什么?
  • 最强大脑第三季全球脑王是谁 陈智强获2016全球脑王
  • 世界最强大脑是谁
  • 最强大脑第五季 最终谁赢
  • 最强大脑世界对决赢过哪场
  • 最强大脑2019脑王是谁?
  • 最强大脑最后全球脑王怎么才这几个人
  • 历史文化
    真视界
    旅游美食
    精彩图文
    我爱我车
    母婴健康
    关于本站 | 广告服务 | 手机版 | 商务合作 | 免责申明 | 招聘信息 | 联系我们
    Copyright © 2004-2018 book1234.com All Rights Reserved. 布客网 版权所有
    京ICP备2021021884号-4 京公网安备11010802011102号