【腾讯内部赛道-极客挑战赛第四期季军】GPU动态规划鹅罗斯方块

引言

鹅罗斯方块挑战是由10000个方块序列构成的鹅罗斯方块游戏，其中包含了大量的s型和z型，以及少数的I型方块。

战绩

积分规则

你的得分为消除时当前局面所有方块的总量乘以一个系数，当消除一行时，系数为1，两行3，三行6，四行10。需要注意的是，不要以为这里的比分是1:3:6:10，实际为1:1.5:2:2.5，因为消除一行时，失去10个格子，消除两行时失去20个格子。

从搜索开始

不需要太复杂的技巧，我们直接使用dfs深度优先搜索，每当出现一个方块，我们便在dfs树上拓展一层。

方块放到哪个具体地方，可以使用bfs实现 有了这个方法，我们的算法就不会死掉，但是他会无限搜索，以至于找不到解，这是因为他的时间复杂度是指数的。

PD启发函数

PD启发函数，即Pierre Dellacherie函数, 这个函数的分越高，我们越优先搜索，于是我们的dfs便可以很快的结束这10000轮计算，我们大概可以得到60w分。因为PD函数比较拉垮，导致每次消除时几乎是走投无路 ，满屏方块的情况。所以得分大致为 10000*4/10*(20-1)*9=684000这个分数是上届了

贪心一点

上面所说的使用PD启发函数的算法，他基于对当前局面的估计，并未利用当前局面已经获取的得分情况，对于多行消除不能很好的利用，这就导致了他往往优先选择消除，而不是等一波之后进行消除。我们可以这样来做，对于dfs树的子节点，优先选择一个当前已经获得的分数最高的进行搜索，当此节点搜索失败，则按照PD启发函数的值进行一次拓展。这次的改进，使得搜索算法可以达到90w的得分。看回放很容易发现，贪心搜索执行了很多两行的消除，但对于三行及四行的消除，几乎没有。

离开搜索，换个思路

到此搜索也走到了头，不容易有突破了。后来看直播发现优秀的策略似乎让当前的局面中不出现空洞，然后使用I型来一次性消掉四行。这种策略搜索算法无法实现。 我们考虑DP动态规划算法，首先需要有状态，什么是状态？既然不出现空洞，那么每一列就可以使用一个0到20的数来代替。于是总状态集合为10^{21} 考虑到进行消除的时候，最多只能消除4行，所以这里的状态也不用设置到这么极端，其实0到7足够了，我们只考虑最上面的8行。

为什么是8行

首先最顶行不允许出现方块，所以8行的的编码，每列最大能达到7，总状态集为 8^{10}, 很容易发现 8^{10}是最大的可以使用一个32位的int储存的情况，但是9行就不行了。另一方面，正是这里可i压缩到一个int的状态，导致了后面使用GPU加速时，更加高效

举个例子，下面的分别是局面（0空1有）和其对应的编码

0 0 0 0
0 0 1 0
0 1 1 1
编码为0121，因为第一列没有填充，第二列有一个，第三列有两个，第四列有一个

下面的局面不是合法状态，他出现了空洞

0 0 0 0
0 0 1 0
0 1 0 1

0 0 1 1
0 0 0 1
0 1 1 1

状态集

现在状态集的总量为2^{30}这个数字一点都不大，这样长的一个int数组也才4GB内存。

状态转移

判读一个状态state，经过一个shapeid编号shapeRotate旋转的方块，可以到达哪些其他状态sonstate，这里可以使用bfs计算。

总结

现在只要给我一个初始状态，然后给我一组方块，我就能构建一个庞大的dp转移图。如下图，初始状态在s，经过一系列的方块，他可以往后如此拖拓展

在我们构建dp状态图以后，就可以在图上按照拓扑序进行转移，最终s会有一些最优转移路径

细节

接下来是时间复杂度和空间复杂度分析，

空间复杂度

我们的转移图有10000层，每层只往后一层连边，经过统计，每层大致会收敛于10^8个状态，于是状态总计10^{12}，需要占用300GB内存。

时间复杂度

每层计算下一层的状态时，需要 10^8次bfs，每层bfs假设需要10000条机器指令，则共计 10000*10^8*10000=10^7*10^9 ,大概需要 10^7 秒，是2700多天。

时空优化

300G内存，很大，由于我们进行每一层状态拓展时，用不到上一层的状态，所以可以按照层，将状态保存到磁盘。计算DP转移路径的时候，再从磁盘读取，这样每个时间点，内存中只需要保持一层的数据，这个完全可以接受。 2700天无法接受了，首先他有10^8个状态，我们选出其中当前以后的分数最高的10^6个状态向后拓展，于是时间复杂度降低100倍，约为27天。紧接着由于每个状态计算后继时互相独立的，所以这写状态的bfs计算，可以使用GPU并行化，得到100倍的提升，最后这个算法只需要半天即可跑完。

得分

由于代码过于仓促以及个人原因，导致我写完以后，剩下的时间不足以跑完整个DP，我对前5000层，均保留10^6个状态，后5000层由于时间不够，只保留了3*10^5个状态，最终的统计信息表明，我的提交序列中使用了111次单行消除，246次双行消除，730次三行消除，299次四行消除。最终可以上120w

初始状态（地基）

DP只能处理最高的8层，对于底下的12层，需要在进行DP算法前就搭好，这里可以直接使用普通的dfs，保证空洞越少越好即可。