首篇极客解题报告意外泄出！亚军竟有神操作？
导语 | 腾讯云+社区联合腾讯码客、腾讯安全平台部全新打造的创新赛事【腾讯极客挑战赛 | 鹅罗斯方块】正式落幕。玩鹅罗斯方块，玩点不一样！在短暂10天内，4570名参赛者或以自己的硬核技术诠释着 “代码无所不能”；或坚持游戏主义，手玩出一片天。 最终11263次有效提交中，涌现出一批出众的作品。快跟上团队！一睹大牛精心贡献的解题报告。
本期为大家带来亚军大佬——北航研究生陈铭煊的报告。看完他的解题过程，小编直呼“我的强迫症治好了！”（请看下方视频）
大佬这样说
在七月末，出于偶然了解到腾讯极客挑战赛这个充满趣味性和挑战性的竞赛，于是便报名参加。这次第四期的赛题叫做“鹅罗斯方块”，要求参赛者用所能尽到的各种方式，在一个JS开发的俄罗斯方块游戏中取得尽可能高的分数。经过一周多的持续思考与努力优化，最终通过动态规划+状态取舍，拿到1378178分，获得外部赛道银奖，也算是如愿以偿。下面是我的比赛经过：
一、在线的启发式算法—EI-Tetris
试玩了两三下我就知道我的手速绝对不可能赶上方块出现的速度（最高级每块0.1s）了。于是我想到要找一个合适的AI算法，然后用自动按键在界面上操作方块。在算法上我选取了名为EI-Tetris的算法：
原作者的文章：https://imake.ninja/el-tetris-an-improvement-on-pierre-dellacheries-algorithm/
一些中文的解释：https://wangzhechao.com/e-luo-si-fang-kuai-ai-suan-fa-shi-xian-jiao-cheng/
简单地说，这个算法的思路是提取一个结果局面的六个特征点：
Landing Height：表示当前方块放置之后的高度；
Rows eliminated：表示当前方块落下后被消减的行数；
Row Transitions：水平方向上变换次数；
Column Transitions：垂直方向上的变换次数；
Number of Holes：空洞个数；
Well Sums：所有“深井”的深度和。
接着将六个特征和权重参数向量点积求和，得到结果局面的估价，其中权重参数是经过粒子群算法迭代选取的：
估价越大，则认为结果局面越好。
每一次我们枚举所有的方块放置位置，选取最好的局面作目标，执行决策，就是算法的总流程。可以看出这个算法很易于实现。
开发方面我Web不太了解，对Qt比较熟悉。于是把游戏页面用QWebEngine加载，这样我就可以在窗口中用Qt的方式对游戏进行操作了：
然而辛苦地倒腾大半天，最后只能拿到大概23W的分数。原因是方块的数量是居然是有限的（10000块），哪怕AI再灵活，用完方块之后游戏就结束了。看来保证“不死”不是关键，得分的要素还是在于迎合特殊的计分方式上。
二、对规则与游戏代码的分析
但如果收游戏包含10000块，其计分是这样的：
显然我们要一次性消去尽量多的行，同时局面还要垒得足够高。比方留一个凹槽专门给长条，那么就有很好的收益。
此外我更仔细地看了网页和JS文件的源代码，发现方块的序列是完全固定的：由一个固定种子的随机数生成器来决定方块的种类，又由已有方块数对4取模得到方块的朝向，所有的方块中心在坐标(0,4)（上至下第0行，左至右边第4行）
这样的话，可以用离线的方式去拼凑方块，来获得比在线响应更好的结果了。
三、状态取舍下的动态规划
很容易想到动态规划的思想，我们拿第i步后产生的局面作为一个状态s，维护到达该状态的最大分数Scorei,s，那么我们最好的解就是maxs∈SN(ScoreN,s) ，N=10000，其中SN是N步后所有的合法状态。我采用四个uint64_t的整数存储局面，每个存储20×10的局面中的五行。每一次对新方块，遍历当前状态集合中所有的局面，得到新局面集合，并计算到新局面的最大积分。
然而，可能的状态数目实在太多了，有220×10种，没有办法在动态规划中全部保存。势必有状态取舍。
我一开始的想法是首先在扩展的过程中，按照安全性估价函数筛查出固定数目状态进行保存（主要目标是局面安全），经过固定步数，再对分数进行贪心，取出唯一最高分状态继续扩展（主要目标是高分）。
在实践的过程中经过比对，决定把分数的因素引入估价函数，不再额外对做分数做贪心。每一步都按照估价函数保留一定数目的状态，并在维护其分数，记忆操作序列和前驱序列。
主体框架：
struct ResultType { StringPtr steps; //StringPtr是一个指向String的智能指针，String储存步骤，并包含记录前驱的智能指针 int score = 0;};
ResultType Solver::solve(Board &board) { return greedyForScore(0, (int) brickSeq.size(), board);}
ResultType Solver::greedyForScore(int first, int last, Board &board) { unordered_map<Board, ResultType> boardMap, tempMap; boardMap[board]; //插入初始状态 for (int i = first; i < last; i++) { generateChoices(brickSeq[i], boardMap, tempMap); //生成新局面集合保存至tempMap boardMap.clear(); tempMap.swap(boardMap); //得到新的boardMap，清空tempMap } ResultType t{StringPtr(), -1}; for (auto &item:boardMap) if (item.second.score > t.score) t = item.second, board = item.first; //找到分数最高的最终状态 return t;}
void Solver::generateChoices(const Brick &brick, const unordered_map<Board, ResultType> &originMap, unordered_map<Board, ResultType> &targetMap) { for (const auto &item:originMap) expand(brick, item.first, item.second, targetMap); //扩张 filterHighEvaluation(targetMap, reservedBoardCount); //筛选出reservedBoardCount个数的状态}四、估价函数的选取
在保存状态数目一样的情况下，估价函数决定了哪些状态值得保留，对于算法的表现尤为重要。
我的估价函数由安全估分和局面分两部分组成，以得分小的局面为优：
auto evaluation = BoardEvaluator::evaluate(it->first) - it->second.score * scoreWeight;其中第一项得到了之前EI-Tetris算法的启发，实现如下：
double BoardEvaluator::evaluate(const Board &board) { return params[0] * board.getCount() + params[1] * board.getRowTransition() + params[2] * board.getColumnTransition() + params[3] * board.getNumberOfHoles();}其中params取值如下：
inline static constexpr double params[] = { -1.0, 3.2178882868487753, 9.348695305445199, 7.899265427351652};不同之处去掉了Landing Height和row Elimination，增加了Count参数（局面中已有方块个数）以激励堆放。这是因为实践中发现由于状态数足够多，安全性不再居于关键地位，更重要的是为后续的得分提供辅助作用。
此外，也去掉了Well Sums，因为发现引入的时候会出现局面中会留存一个宽度为2的槽的情况，去掉之后就会只要一个宽度为1的槽来供长条消去，对得分更有效益。
对于第二项，通过不断地人工调参，我将局面得分的权重scoreWeight定在了1.0/38。
当然，中间确定估价还经过了大量的尝试，很多尝试发现没有必要，这里就不再赘述。
实现完毕之后发现效果异常地好，程序会很自然地将方块叠到两边，中间留出了凹槽，每来一个长条都能有很高的分。
算法的源代码放在了以下网址：
（https://github.com/MaxDumbledore/Tencent_Geek_Competition_4）
默认设置的reservedBoardCount为1000，已经能跑出130W的成绩了，本机大概用时两分钟。设置为30000，能跑出137W的成绩，大概用时一个半小时。
五、一些可能的改进
首先调参的技术活可能需要额外的算法做帮助，人工调参确实很困难。
其次扩张时没有搜索所有的可放置状态，为了方便只是考虑了旋转+降落的情况，通过观察其他选手的回放，发现考虑在内是有价值的。
另外对于算法性能上，一些数据结构可以优化，另外应该加入OpenMP或者多线程做并行化。
最后，该算法的得分点过于偏向对长条的利用，没有利用好其他方块的消行得分。后期增大保留的状态数对于分数增长帮助也不是很大，估计采用这个算法架构能到达的上限不会超过140W。如果要突破的话还是需要对其他选手的算法借鉴一二。
六、总结
总得来说，我的思路并不复杂，高分也有一定运气成分。赛后通过对其他选手解法的学习，我的眼界也有了开拓。所谓极客挑战赛，就是不断追求极致，不断学习和突破的过程。这是很愉快的参赛经历，同时我十分期待下一期会有什么不一样的新挑战。
作者简介
陈铭煊
北京航空航天大学计算机学院硕士研究生
本科就读于北京航空航天大学大学网络空间安全学院，现于北京航空航天大学计算机学院攻读计算机视觉方向硕士研究生。曾参与过多项知名算法竞赛，其中ICPC与CCPC区域赛中获金奖，蓝桥杯软件类获C++组与Python组的省一等奖，广泛参与开发类和安全类竞赛并取得优异成绩。
推荐阅读
👇戳阅读原文前往「腾讯云+社区」作者个人主页参与交流哦~