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

腾讯云开发者

发布于 2021-08-27 11:10:20

7370

发布于 2021-08-27 11:10:20

导语 | 在腾讯腾讯云开发者社区联合腾讯码客、腾讯安全平台部全新打造的创新赛事【腾讯极客挑战赛 | 鹅罗斯方块】中，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优的游戏局面。第一层搜索每次从桶里拿出一个游戏局面进行第二层搜索，再将搜索结果放回对应的桶内。第二层搜索则是一个简单的广搜，用来搜索可能的「阶段」。第二层搜索对游戏局面进行广度优先搜索，直到出现消行操作才停止拓展，也就是说这棵搜索树的叶子都是经过某次消行操作后的游戏局面。第二层搜索结束后会把搜索树叶子上的游戏局面返回给第一层搜索进行更新。

（二）算法框架

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

// 返回场面上已被占用格子数inline int getGrids(){    boradGrids = 0;    for (int y = 1; y <= LIMITHEIGHT; y++)        boradGrids += bit(gridInfo[nowGame][y]) - 2;    return boradGrids;}
// 返回场面上纵行方向上方块从有到无的变化次数，越少场面越平整inline int getTransitions(bool recount = true){    if (recount) // 重新计算该值    {        boardRowTransitions = 0;        boardColTransitions = 0;        for (int y = 1; y <= LIMITHEIGHT; y++)            boardRowTransitions += bit(gridInfo[nowGame][y] ^ (gridInfo[nowGame][y] >> 1)) - 1, // 各行中变换之和            boardColTransitions += bit(gridInfo[nowGame][y] ^ gridInfo[nowGame][y - 1]);        // 各列中变换之和    }    return boardRowTransitions + boardColTransitions;}

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