【参赛经验分享】外部赛道Rank 2解题报告：状态取舍下的动态规划

2021-08-18 10:30:30 浏览数 (1)

在七月末，出于偶然了解到腾讯极客挑战赛这个充满趣味性和挑战性的竞赛，于是便报名参加。这次第四期的赛题叫做“鹅罗斯方块”，要求参赛者用所能尽到的各种方式，在一个JS开发的俄罗斯方块游戏中取得尽可能高的分数。经过一周多的持续思考与努力优化，最终通过动态规划 状态取舍，拿到1378178分，获得外部赛道银奖，也算是如愿以偿。下面是我的比赛经过：

1. 在线的启发式算法—EI-Tetris

试玩了两三下我就知道我的手速绝对不可能赶上方块出现的速度（最高级每块0.1s）了。于是我想到要找一个合适的AI算法，然后用自动按键在界面上操作方块。在算法上我选取了名为EI-Tetris的算法：

原作者的文章：El-Tetris – An Improvement on Pierre Dellacherie’s Algorithm | imake

一些中文的解释：俄罗斯方块 AI 算法讲解 - 没事造轮子 (wangzhechao.com)

简单地说，这个算法的思路是提取一个结果局面的六个特征点：

Landing Height：表示当前方块放置之后的高度；

Rows eliminated：表示当前方块落下后被消减的行数；

Row Transitions：水平方向上变换次数；

Column Transitions：垂直方向上的变换次数；

Number of Holes：空洞个数；

Well Sums，所有“深井”的深度和；

接着将六个特征和权重参数向量点积求和，得到结果局面的估价，其中权重参数是经过粒子群算法迭代选取的：

特征

权重

Landing Height

-4.500158825082766

Rows eliminated

3.4181268101392694

Row Transitions

-3.2178882868487753

Column Transitions

-9.348695305445199

Number of Holes

-7.899265427351652

Well Sums

-3.3855972247263626

估价越大，则认为结果局面越好。

每一次我们枚举所有的方块放置位置，选取最好的局面作目标，执行决策，就是算法的总流程。可以看出这个算法很易于实现。

开发方面我Web不太了解，对Qt比较熟悉。于是把游戏页面用QWebEngine加载，这样我就可以在窗口中用Qt的方式对游戏进行操作了：

然而辛苦地倒腾大半天，最后只能拿到大概23W的分数。原因是方块的数量是居然是有限的（10000块），哪怕AI再灵活，用完方块之后游戏就结束了。看来保证“不死”不是关键，得分的要素还是在于迎合特殊的计分方式上。

2. 对规则与游戏代码的分析

游戏包含10000块，其计分是这样的：

一次性消除的行数

得到分数

1行

已有格子数×1

2行

已有格子数×2

3行

已有格子数×3

4行

已有格子数×10

显然我们要一次性消去尽量多的行，同时局面还要垒得足够高。比方留一个凹槽专门给长条，那么就有很好的收益。

此外我更仔细地看了网页和JS文件的源代码，发现方块的序列是完全固定的：由一个固定种子的随机数生成器来决定方块的种类，又由已有方块数对4取模得到方块的朝向，所有的方块中心在坐标(0,4)（上至下第0行，左至右边第4行）

这样的话，可以用离线的方式去拼凑方块，来获得比在线响应更好的结果了。

3. 状态取舍下的动态规划

很容易想到动态规划的思想，我们拿第i步后产生的局面作为一个状态s，维护到达该状态的最大分数text{Score}_{i,s}，那么我们最好的解就是max_{sin S_{N}}({text{Score}_{N,s}}) ，N=10000，其中S_{N}是N步后所有的合法状态。我采用四个uint64_t的整数存储局面，每个存储20times 10的局面中的五行。每一次对新方块，遍历当前状态集合中所有的局面，得到新局面集合，并计算到新局面的最大积分。

然而，可能的状态数目实在太多了，有2^{20times 10}种，没有办法在动态规划中全部保存。 势必有状态取舍。

我一开始的想法是首先在扩展的过程中，按照安全性估价函数筛查出固定数目状态进行保存（主要目标是局面安全），经过固定步数，再对分数进行贪心，取出唯一最高分状态继续扩展（主要目标是高分）。

在实践的过程中经过比对，决定把分数的因素引入估价函数，不再额外对做分数做贪心。每一步都按照估价函数保留一定数目的状态，并在维护其分数，记忆操作序列和前驱序列。

主体框架：

代码语言：txt复制
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个数的状态
}

4. 估价函数的选取

在保存状态数目一样的情况下，估价函数决定了哪些状态值得保留，对于算法的表现尤为重要。

我的估价函数由安全估分和局面分两部分组成，以得分小的局面为优：

代码语言：javascript复制
auto evaluation = BoardEvaluator::evaluate(it->first) - it->second.score * scoreWeight;

其中第一项得到了之前EI-Tetris算法的启发，实现如下：

代码语言：javascript复制
double BoardEvaluator::evaluate(const Board &board) {
    return params[0] * board.getCount()   params[1] * board.getRowTransition()  
           params[2] * board.getColumnTransition()   params[3] * board.getNumberOfHoles();
}

其中params取值如下：

代码语言：javascript复制
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。

当然，中间确定估价还经过了大量的尝试，很多尝试发现没有必要，这里就不再赘述。

实现完毕之后发现效果异常地好，程序会很自然地将方块叠到两边，中间留出了凹槽，每来一个长条都能有很高的分。

算法的源代码放在了 MaxDumbledore/Tencent_Geek_Competition_4: 腾讯极客挑战赛第四期 鹅罗斯方块 rank4 (github.com)

默认设置的reservedBoardCount为1000 ，已经能跑出130W的成绩了，本机大概用时两分钟。设置为30000，能跑出137W的成绩，大概用时一个半小时。

5. 一些可能的改进

首先调参的技术活可能需要额外的算法做帮助，人工调参确实很困难。

其次扩张时没有搜索所有的可放置状态，为了方便只是考虑了旋转 降落的情况，通过观察其他选手的回放，发现考虑在内是有价值的。

另外对于算法性能上，一些数据结构可以优化，另外应该加入OpenMP或者多线程做并行化。

最后，该算法的得分点过于偏向对长条的利用，没有利用好其他方块的消行得分。后期增大保留的状态数对于分数增长帮助也不是很大，估计采用这个算法架构能到达的上限不会超过140W。如果要突破的话还是需要对其他选手的算法借鉴一二。

总结

总得来说，我的思路并不复杂，高分也有一定运气成分。赛后通过对其他选手解法的学习，我的眼界也有了开拓。所谓极客挑战赛，就是不断追求极致，不断学习和突破的过程。这是很愉快的参赛经历，同时我十分期待下一期会有什么不一样的新挑战。

腾讯极客挑战赛

0 人点赞