【参赛经验分享】一个全程DFS的解题总结（内部赛道）

TL;DR: 主要思路是基于“残局”（地基）的启发式dfs。第一版用python实现(GUI+solver)大概是70W+，后面把solver部分移植到了rust上，结合一些性能优化和各种限制条件后达到100W+，再优化感觉就比较难提升了。最后分数是1060356，内部赛道第8名。

初探

第一件事是确定方块序列怎么生成的，看了下js有很友好的给出源文件地址，随机数生成核心： return (v * a + C) % M;`，种子也是固定的，就放弃了RL的想法。

然后用pygame根据js的逻辑先写了一个简陋的本地客户端辅助调试，功能上能让方块不主动下降，可以向上，可以悔棋（但此时悔棋是通过重放序列到倒数第二个N实现的），打印调试信息等，同时根据玩的过程可以生成序列。

这时手动大概玩了500多个方块，3.8W分左右，按比例算的话全完成也就70多W。（膜拜一下前面TAS方法的大佬）

于是就决定还是要实现求解器。以前给Shenzhen IO的纸牌小游戏solitaire和Opus Magnum的minigame sigmar's garden实现bot时使用的都是基于启发式的DFS方法，就按照相同的思路实现了。核心思路其实就是通过评估函数给行动排序，“引导”、“启发”程序进行搜索。几个实现的细节：

• 这时已经发现可以直接通过"N"让方块悬空，但生成possible moves考虑到空间太大，就先只考虑"落地"的情况。生成方法是先对每种形状（0~3的形状state，重复的不考虑）列出地上的目标位置，通过bfs寻路看能不能通过操作达成，得到实际可到达的moves
• 给possible moves排序(heuristic score)，也就是所说的“评估函数”，优先搜索“更好”的move。初始时以高度和作为评判标准。
• 从零开始进展缓慢，于是改用“残局”模式，手动玩了30~40块左右，再让求解器在这个基础上继续执行。这样不好的move很快就会因为游戏结束而回退

UI示例

图上两个红色的数字上面是brick_count(方块序号)，下面是分数。提交时由另一个脚本对序列文件生成相应的js代码，复制到浏览器console中提交。

这种方式很容易就能玩到10000块不死，大概70W左右

优化

花了2晚把求解器移植到了rust（期间有个形状的坐标复制错了，还调了近一晚bug），再结合一些其它的优化：

• 之前dfs探索时使用的是复制整个游戏状态的方式，改为了in-placed的方式，并改回退的实现方式从“重放序列”为真正的”回退“（直接恢复上一方块状态），显著减小了大量的allocation消耗
• 优化前，见过的状态用类型HashMap<u32, HashSet<String>>保存(String是游戏当前“棋盘”的一种编码形式)，key为当前的brick_count，这样内存过大时可以释放掉一些brick_count较小的entry。运行时发现内存占用过大，意识到由于只用判断存在与否，改成了HashMap<u32, HashSet<u64>>的类型，显著降低了内存需求(计算hash使用了fxhash)
• 用hashbrown的HashSet方法替换了std的HashSet以节省一些内存
• 修改heuristic score评估函数返回Option，也就是其它语言的Optional或Maybe类型。这样可以在评估函数里通过返回None告诉上层直接放弃掉不想要的状态

此外还手动玩了几个比较好的”残局“，使低层每行只有一个空洞。同时一直在调整heuristic score的策略。尝试过使用PD算法，但看上去没有什么效果，又加上了一些其它的策略：

• 把只消一行的方案直接放弃(最后的序列基本上是消2行，少数3行和4行，提升较大）
• 把只消二行的方案概率性放弃（少许提升）

限制消除的行数不要太少

• 有消除时判断现有方块总数，少于164的放弃（168的试了几轮，很快会失败）
• 少于168的概率性放弃

限制剩余的方块不要太少

这时大概103W

最后的小优化

因为序列固定，生成了一些间隔比较大的"I"和"J"的序号列表(HashSet)，在评估函数中判断如果在这些方块时没有达到3消或4消，就概率性放弃。这个改动显著增加了运行时间(体感跑完大概要1天)，但最终只提升了3W+左右，到达106W+

总结

• 和前几名的差距还是很大的，要有显著提升可能还是得换搜索效率更高的一些方法（结合更好的剪枝方案）
• 当前评估函数对全局的的分数计算还是基于高度、空洞等的加权和（差），感觉引入其它思路还有优化空间
• 感谢组委会的这次比赛，学习到很多也见识到很多，过程也十分有趣。期待下一次的比赛。